Anabasis, Book 6 - Καὶ διηγοῦνται ταὐτά

σπείσας δʼ εὐθὺς ἦγε τοὺς νεανίσκους παρὰ τὸν Χειρίσοφον, καὶ διηγοῦνται ταὐτά - “having poured the libation he took the young men straight to Cheirisophus, and they told the same story”

Since I’ll be away for a couple days following this post, I’ve decided to up the ante on my post cadence - enjoy!

Book four, chapter three. The army is pinned against the Kentrites, with Armenian cavalry drawn up on the far bank and the Carduchians closing in from behind, and Xenophon is at breakfast - which, as everyone in the camp knew, was no protection whatsoever against being interrupted by anyone with news bearing on the war. In that moment, two young men come running. They’d been out gathering brushwood, they say, when they spotted an old man and some women stowing bundles of clothes in a hollow rock across the water, and it occurred to them that if those people could cross the river, so could they. So they stripped, took their knives, waded in expecting to swim - and got across without the water reaching their waists.

Xenophon pours a libation on the spot, and right then, he does the very thing this post is about: he walks the two young men over to Cheirisophus, who commands the other half of the army, and has them recount what happened once more. καὶ διηγοῦνται ταὐτά. And they told the same story.

He didn’t need a second telling to learn where the ford was; much rather, he needed to be certain, for the first telling was about to move ten thousand people across a river in the face of cavalry, and one account of an observation is not evidence - it’s a report. Two independent accounts of the same thing, given to two people who can each judge it on its own merit, might just be something you can act on. That very distinction is the entire subject of this post, and I’ve been quietly running up a debt against it for five instalments.

The debt to the truth

Let us recap what this here series has asserted about the kernel:

• that an accept verdict ends the current base chain but not the ruleset, so a packet has to survive every base chain on its path;
• that return means one thing after a jump and something else entirely after a goto;
• that destination translation happens before filtering, so the chain that decides is looking at a rewritten packet;
• that a strict reverse-path check discards a packet before any chain sees it;
• that a frame switched between two ports of a bridge never meets the ip hooks unless br_netfilter shows it to them;
• that ibrname "br0" selects exactly the frames that iif over br0’s ports selects;
• that nft compiles arp operation request into an ethertype test which stays positive even when the field comparison is negated, so such a rule is exactly empty in an IP packet space rather than unknown.

For some of those assertions, I quoted the manual. For others I wrote “measured on a kernel” and moved on, and you had no way to check the veracity of that claim. Worse, from my own perspective: for a good while I had no way to check my assertions for correctness either, and the tool has two engines that could have agreed with each other about a misreading indefinitely.

That’s the specific hazard I needed to address, for Anabasis evaluates a ruleset twice: there’s the symbolic evaluator from posts two through four, which turns chains into sets of packets, and there’s a concrete interpreter, which walks a single packet through the same IR the ordinary way, rule by rule. Every ordinary test in the repository compares those two against each other, and it’s a useful comparison in its own right, since it catches the whole class of errors where the set algebra and the step-by-step walk drift apart. What it cannot catch - not once, not ever - is both of them reading the same rule wrongly in the same way - they share an IR. A mistake made in the lowering is a mistake both of them inherit, and their agreement about that mistake would make it a failure mode nigh impossible to catch.

The file that guards against this opens by making a bold statement:

Every other test in this repository compares the engine against itself: the concrete interpreter and the symbolic evaluator read the same IR, so a shared misreading is invisible to both. These cases load the same ruleset into a real kernel and put real packets through it, which is the only place a wrong reading of the manual can actually surface.

Asking the kernel

So there is a third party to this dance, and it’s Linux itself.

The oracle takes a ruleset, loads it into an actual kernel, fires actual packets at it, watches what the kernel does, and compares that against what both engines predicted. For the tests to pass, all three have to agree:

Holds the three answers side by side: what the kernel did, what the concrete interpreter says it should have done, and what the symbolic evaluator says about the set the packet belongs to. Agreement of all three is the only outcome that counts as a pass; a probe that could not be delivered as intended is reported as inconclusive rather than being quietly counted either way.

That last clause matters more than one would presume after reading it for the first time. A differential test that scores “we could not deliver the packet” as agreement is a test that passes hardest when it is most broken, and I’ll come back to that at the end of this post with a story I did absolutely not enjoy being a part of.

The obvious objection is the one you’re already forming: you can’t go loading firewall rules into the kernel of the machine that’s running your test suite. Quite right, indeed. You may, however, load them into a kernel that has no other job but to serve as a testbed for those rules.

A machine that does not exist - yet

Every oracle session forks a child, and the child moves itself into a fresh user namespace and a fresh network namespace before it does anything else. Inside, it’s alone - its own interfaces, its own routing table, its own nftables ruleset, its own conntrack - nothing it does is visible outside of these confines, and nothing outside is visible to it. It then builds the topology the test needs (veth pairs, dummy interfaces, bridges, addresses), loads the ruleset, and then sits waiting to be asked about packets.

Three properties of that arrangement are worth spelling out, because each of them is a decision that could have easily gone the other way:

It refuses to run as root. That isn’t a nicety. From the header:

Refuses to run as root. The oracle has to demonstrate that it works unprivileged, and a root run would hide exactly the mistakes that matter - a namespace that was never entered still looks like it works when the caller may have the privilege to change the real one.

If the test process is privileged and the unshare silently fails, the child goes on merrily configuring interfaces and loading rules - in the host’s namespace. The tests would pass. They’d pass because the oracle had quietly stopped being an oracle and started reconfiguring the developer’s machine. Refusing privilege makes that failure mode impossible rather than merely unlikely.

The parent never enters the child’s namespace, and this assertion is checked rather than assumed. The caller records its own network namespace identity before spawning and compares it afterwards; a sandbox that changed it equals a failed test. It’s a small, yet powerful thing to write, and it converts a convention that some future contributor could break into an invariant that fails loudly the moment they do.

Everything crosses a pipe as a fixed-size record written in a single call. That sounds like fussiness until you consider what the parent has to be able to tell apart: a child that answered, a child that answered partially, and a child that died mid-sentence. An atomic write of a fixed-size record makes a short read impossible unless something has truly gone wrong, and the record carries a magic number - 0x414E4B4F, which spells ANKO, and I will not be taking questions about that - so a desynchronised pipe is noticed rather than being read as data that might happen to parse.

Loading rules the way nft does, not the way nft looks

The child doesn’t shell out to nft. It talks to netlink directly through libnftnl, building the same batch of messages the real tool builds and committing it in one transaction.

That’s rather more work than running a command, and it buys us two things. The first payoff is that the test is testing the kernel’s opinion rather than the userspace tool’s parser. The second is subtler and paid off immediately: the encoder can place the IR rule id into each rule’s user data, so once the batch commits the child dumps the ruleset back, reads the handles the kernel assigned, and builds a map from kernel handle to my rule. Without that, correlating a kernel trace event with the rule in the model is guesswork.

The mapping is keyed on family, table and handle together, and the comment explains why:

the kernel numbers rules per table, so two tables routinely both hold a rule with handle 3, and a map keyed on the handle alone would attribute a trace event to whichever of them was inserted last.

The encoder also refuses to translate anything it doesn’t fully understand, rather than dropping the construct and loading what’s left, since silently dropping a match would load a ruleset that is more permissive than the one under test, and the oracle would then compare the engine against the wrong firewall, which would produce a meaningless answer about whether the implementation behaves as expected.

Firing real packets, which is harder than it sounds

The probe is a real frame on a real interface, and how you deliver it decides which hooks it traverses - which makes injection part of the semantics under test rather than mere plumbing:

a frame sent on a veth’s peer is received on the interface itself, so it enters at prerouting and, its destination being local, goes on to input. That is the arrival a filter chain on the input hook sees.

loopback has no peer, so a probe for it is sent through a raw IPv4 socket to 127.0.0.1: it leaves through output and postrouting and comes back in through prerouting and input.

A dummy interface would not do for either: it discards on transmit.

Conntrack required a trick of its own to get working. To observe a packet in the established state you can’t simply assert that it’s established; you have to make that statement true. So the child first opens the connection outwards from the namespace, letting conntrack record the original direction, and only then sends the probe inwards as a reply. The comment notes the detail that makes this work at all: conntrack confirms the entry in the last hook of the outgoing packet’s path, before any neighbour has to be resolved, so it doesn’t matter that nothing on the far end ever answers the ARP.

After that’s accomplished, having sent the probe, how do you know what the kernel did with it? Not by watching whether it arrived, which conflates a dozen possible causes. The child subscribes to NFNLGRP_NFTRACE and reads the kernel’s own trace stream: every chain the packet entered, every rule that matched, every verdict, in order, straight from the evaluation itself. The kernel derives one trace id per packet and repeats it across every hook, which is what lets the child gather a packet’s events and discard everybody else’s.

Two details from that corner, both hard-won by trial and error: Only the first event of a packet carries its headers, so correlation has to run on the trace id rather than on the addresses - and because nothing tells you when a packet’s events have stopped arriving, the child sends a sentinel probe afterwards - a packet whose sole purpose is to be observed, aimed at the discard port so that no fixture could plausibly be about it - and treats its first event as the end of the probe’s trace.

Both sides are then reduced to a canonical sequence of steps - chain, rule, action - and compared step by step, and not just the final verdict, either, but the path the packet takes through the ruleset: two rulesets can reach the same verdict by different routes, and if the model gets the route wrong, it will almost certainly get some other packet wrong later.

What the oracle actually checks

Twenty-seven hand-written semantics cases, and the list reads like an index of everything this series has claimed. I’m going to quote the test names verbatim, because they are the guardians ensuring correctness of my implementation:

AcceptContinuesToTheNextBaseChain
DropEndsTheWholeRuleset
GotoReturnFallsToThePolicy
JumpReturnResumesTheCaller
ThePolicyDecidesWhatNoRuleClaims
PriorityDecidesWhichBaseChainRunsFirst
DestinationTranslationHappensBeforeFiltering
ARedirectRewritesOnlyThePort
ConntrackStateIsSeenAsTheProbeStagesIt
StrictReversePathDropsBeforeAnyChain
WithoutReversePathTheSameSourceIsDecidedByTheRules
WithForwardingOffTheForwardChainIsNeverReached
ASwitchedFrameIsDecidedByTheBridgeChainAndNotByTheIpOne
ABridgeNameDecidesTheSameFramesAsItsPortsDo
TwoBridgesDoNotSwitchBetweenEachOthersPorts
AnArpRuleLeavesAnIpProbeToTheRulesBehindIt
ARulesetsOwnReversePathCheckAgreesWithTheKernelsFib

Every “measured on a kernel” in the previous five posts cross-references a name on that list - the bridge claim from Book five, that ibrname "br0" decides exactly the frames its ports decide, is ABridgeNameDecidesTheSameFramesAsItsPortsDo. The goto trap from Book four is part of GotoReturnFallsToThePolicy. The reverse-path demonstration that carried Book five is a part of StrictReversePathDropsBeforeAnyChain, with its negative control sitting immediately below it.

Hand-written cases have a structural weakness, though, and it’s the most obvious one: they check the semantics somebody thought of asking about, so there’s a second tier for the cases nobody remembered: A generator produces rulesets full of jumps, gotos, verdict maps, sets and negations arranged in combinations no reviewer chose, and every packet of a grid is put through the kernel and both engines. From this afternoon’s run:

900 probes over 10 seeds: 246 accepted, 654 dropped, 0 inconclusive

The accepted-versus-dropped split is reported on purpose, because agreement on a ruleset that says yes to everything is not evidence of anything at all. A 27:73 split means the generated rules are actually discriminating between packets, and all three parties still tell the same story about every one of them.

The third tier is the real thing. The production dump from the first post - the one with the 23,621-address blocklist - gets loaded into a namespace and interrogated:

11 accepted, 5 dropped, 0 inconclusive

Sixteen packets isn’t that many. What it establishes, however, is that the entire pipeline survives contact with a live ruleset nobody specifically designed to be testable, which is a different mode than the synthetic sets altogether.

The whole oracle encompasses thirty-five tests and finishes in about two and a half seconds, which is surprisingly much for C++-based tests, and yet surprisingly little once you realize the guarantees it provides.

The promise in a build flag

One more design decision, and it’s the one I’d defend most stubbornly.

-DBUILD_KERNEL_ORACLE=ON does not mean “run these tests if the environment permits”. It means the kernel was consulted. An environment that can’t host the oracle fails rather than skips, and the check that establishes this is deliberately not a test:

This is a gate, not a test. It belongs in SetUpTestSuite rather than in a TEST, for gtest lets a test be filtered out, shuffled or skipped, and any check that can potentially be skipped is not a check altogether.

Anyone who has run a CI pipeline for any length of time knows the failure mode being guarded against here. A test that skips when a module is missing is a test that skips on the build machine, silently, for eight months, and the green tick means nothing, since few would have the tenacity to actually check all of the tests which ran for completeness. The preflight gate forks a sandbox that does everything a real run does - fresh namespaces, verified fresh; a dummy interface; a veth pair; an address; the trace subscription; a small conntrack-matching ruleset - and if any of it fails, the run fails, naming what the operator has to change: unprivileged user namespaces, the nf_tables nft_ct nf_conntrack veth dummy bridge modules, iproute2, a kernel new enough. Guarantees, then, rather than hoping for the best.

The time the harness broke in the worst possible way

I promised this story at the end of the last post, and it’s the best argument I have for why differential testing requires a paranoia all of its own.

A clang build in CI started failing. Not with an assertion, not with a mismatch, not with any of the careful diagnostics above - the test binary simply exited 42. No gtest epilogue, no summary line, no JUnit XML for the pipeline to collect. Just a number, and a job that had gone red for no reason anybody could see from the log.

The cause was three characters long. When an oracle session is destroyed it sends a quit record to its child - a child which, in the ordinary case, has already finished and exited. Writing to a pipe whose reader is gone raises SIGPIPE, and the default disposition for SIGPIPE is to terminate the process on the spot. No unwinding, no flushing; terminate. Every buffered byte of the gtest report died in the process’s stdio buffers, which is why the log simply stopped altogether.

The fix for this particular issue is an IIFE four lines long, installed before the first fork so the disposition is inherited:

void tolerateBrokenPipes() noexcept
{
    static const bool once = []
    {
        struct ::sigaction ignore{};
        ignore.sa_handler = SIG_IGN;
        ::sigemptyset(&ignore.sa_mask);

        return ::sigaction(SIGPIPE, &ignore, nullptr) == 0;
    }();

    static_cast<void>(once);
}

What I want to put emphasis on here isn’t the bug; it’s what the bug looked like, and how very nearly it could’ve been missed.

Consider a slightly different arrangement of the same mistake, one where the signal arrives a moment later, after the report has been flushed. The suite would print [ PASSED ], the process would die on its way out, and on a good many CI configurations that’s a green tick with a slightly odd exit status nobody reads. The oracle would have stopped testing anything and gone on reporting success indefinitely - precisely the failure mode the entire apparatus exists to prevent, arriving through the back door, in the apparatus itself.

Which is why the regression test for it doesn’t check that the fix was called. It reads the signal disposition back out of the kernel:

struct ::sigaction current{};
ASSERT_EQ(::sigaction(SIGPIPE, nullptr, &current), 0);
EXPECT_EQ(current.sa_handler, SIG_IGN);

This assertion sits alongside three others of the same character: that the test process isn’t privileged; that it’s single-threaded (because PR_SET_PDEATHSIG is per-thread and not inherited across a fork, so a sandbox spawned from a threaded process could outlive the run); and that a sandbox leaves the parent’s namespace exactly as it found it.

A test harness is software, therefore it has bugs, and its bugs are a good deal more dangerous than the bugs in the thing it tests, for the failure mode of a broken test is silence, and silence is indistinguishable from success right up until it isn’t. So the oracle tests itself, and the facts it checks about itself are all assertions about the state we require the oracle to be in rather than which function was executed.

The concerns this assuaged

Six posts ago I described an area where the theory has been settled for twenty years and the tools all point at a language Linux has since replaced. Everything since has been about closing that distance: packets as points and policies as shapes; a bracket around every answer, so that uncertainty is carried into the report rather than compounded by guessing; a ruleset folded into a set; a machine underneath it that decides which packets ever arrive; and now a kernel that gets the final say on whether any of it was read correctly.

The oracle is brought up towards the end of the series due to it being what lets everything before it be stated as fact rather than intention. I have erred during development of Anabasis several times - about the operation cache, about which direction the NAT preimage runs, about whether spreading routes across prefix lengths costs more or less. In every one of those cases, what corrected me was a measurement or a test, and this here oracle is the ultimate test: a test whether Anabasis truthfully represents kernel behavior and interprets it correctly.

Two young men waded a river and came back with the clothes to prove their crossing, and upon returning, they recounted it twice, to two people who could each act on it, and the story didn’t permutate between these iterations. That isn’t ceremony. It’s the difference between something you believe to be true and something you can march an army across.

The tool is called Anabasis. It’s C++23, it’s MIT licensed, and at some point fairly soon there will be a post about the specification language itself - how one writes down “only these three addresses may reach SSH” in a form a machine can decide and a human can review in a pull request.

And isn’t that exactly what the whole march is for ?