Anabasis, Book 8 - Δίκην ὑποσχεῖν

ἔδοξε δὲ καὶ τοὺς στρατηγοὺς δίκην ὑποσχεῖν τοῦ παρεληλυθότος χρόνου. – “It was further resolved that the generals themselves should undergo a judicial examination in reference to their conduct in past time.”

Book five, chapter eight. The army has reached Cotyora, on the Black Sea coast; the snow, the Carduchians and the poisoned honey lie behind it, the sea it cheered from the top of Theches is now at its elbow, and for once nobody is pressing on its heels. So the army does what armies seldom do and what this one does with a certain relish: it turns round and examines itself. The camp is purified, on the advice of Xenophon and the seers, and then it is resolved that the generals shall answer for their conduct in past time. Philesius and Xanthicles are fined twenty minae for a shortfall in the cargoes they were set to guard, Sophaenetus ten, for neglecting a command he had been elected to. And then certain men stand up and accuse Xenophon of having beaten them.

What follows is, to my mind, the finest piece of cross-examination in the whole work. Xenophon asks the first accuser where and when he was struck; in the snow, comes the answer, when they were perishing of cold. Was it a debt, then? A quarrel over a boy? Was Xenophon drunk? No, no and no. It emerges that Xenophon had forced the man to carry a soldier who could march no further, and, coming up later with the rearguard, found him digging a trench to bury that soldier – at which point the comrade twitched his leg, and the bystanders cried out that the man was alive. Alive or not as he likes, said the accuser, I am not going to carry him. Then Xenophon struck him. The accuser’s rejoinder is the line this post is built around: was he any the less dead when I reported him to you? And Xenophon’s reply: by the same token we shall all one day be dead, but that is no reason why meantime we should all be buried alive.

A man was reported dead who was not. The report was plausible and it was convenient, and yet, it was wrong, and the general went and verified before he accepted it. Doveryay, no proveryay. That is the first subject of this post, the second one being that the generals were examined at all: an army that has successfully conducted a march still owes an account of how it achieved that, and so does a tool, a compliance tool more than most. This being the last post before the release, that debt is due now. The lint layer examines the rules, the measurements examine the tool - but didn’t we forget something here?

The rules on trial

Everything so far has been about what a ruleset does: which packets it accepts, and whether that matches what somebody decreed. There is a second question, older than this project by two decades, which can be asked without any specification at all: does every rule in the ruleset actually do anything?

A rule can be present, well-formed, syntactically impeccable and entirely inert, because the rules above it have already decided every packet it could ever have matched. The header of the lint layer states the difficulty in a sentence:

What makes it worth computing is that none of it is visible in the text: a rule that never fires looks exactly like one that does.

The taxonomy goes back to Al-Shaer and Hamed; the formulation Anabasis implements is FIREMAN’s, which restates the anomalies as conditions on the sets a first-match scan has accumulated by the time it reaches rule j. Write P_j for the packets the rule matches wherever they come from, R_j for the packets still undecided when the scan reaches it, and O_j for what the chain has already decided the other way – the packets dropped so far when rule j accepts, the packets accepted so far when it drops. Then:

A masked rule never fires: nothing it matches is still present to be matched. If some of what it matches was decided differently than what the masked rule would have decreed, the rule is shadowed, and somebody’s intent has been contradicted by a rule they had forgotten about. If none of it was, the rule is merely redundant, dead weight that changes nothing when removed. A correlated rule, by contrast, does fire; only part of what it was written to decide had already been decided against it.

None of this is new computation. Book four built the fold that walks a chain, carrying the undecided set from rule to rule. At every rule it already holds R_j, together with the accept and drop sets accumulated so far. The lint layer merely asks the evaluation to keep them, and reads the anomalies off afterwards. A handful of intersections per rule is the whole price; there is no second walk.

One place where the code departs from the paper needs to be stated precisely. FIREMAN splits a masked rule three ways: shadowed only if everything it matches was decided the other way, redundant if nothing was, and “redundancy and correlation” for the mixture. Anabasis calls the mixture shadowed. The rule is dead either way, and a dead rule that is even partly contradicted by earlier ones is the case that deserves the stronger word; a report that told an operator their rule was “redundant and correlated” would leave them to work out for themselves that it contradicts something.

In practice, two refinements matter more than the conditions. A regular chain reached by several jumps is evaluated once per caller, and a rule can be dead in one context and alive in another; the header is explicit that “a rule is only reported when it is anomalous in every context it was reached from”. Also, a rule about another protocol is not a dead rule. ip saddr cannot match a packet in an IPv6 space, and an ARP match cannot match one in an IP space; the compiler rightly answers both with the empty set, which looks exactly like a rule an earlier one has swallowed. The code consequently declines to draw the conclusion, and its comment might have been written at Cotyora:

an empty set is indistinguishable from one an earlier rule already took, and calling such a rule dead is an accusation nothing here supports. It fires; just not for the packets this walk is about.

Alive or not as he likes, in other words, the tool will carry him.

Errors, warnings and the intention gap

Not every anomaly is a mistake at all, and FIREMAN was candid about it. The section that introduces the taxonomy speaks of the milder two:

Generalization or correlation may not be an error but a commonly used technique to exclude part of a larger set from certain action.

Drop a blocklist, then accept a service: the accept is correlated with the drop by construction, and that is exactly what its author meant. FIREMAN’s authors called the resulting uncertainty the intention gap – “we, as tool writers, do not know the intention of the administrator” – and drew the only honest conclusion:

Our tool raises “warnings” and leaves the decision to the administrator, who surely knows his/her own intention.

Anabasis follows suit. Shadowed and redundant rules are errors, because a rule that cannot fire is either a mistake or dead weight. Correlation is a warning, “because narrowing a later rule with an earlier one is a technique, not a defect”, as the severity’s doc comment has it. The structural findings below are notes. Severity lives in the lint layer and not in the specification, because lint runs without a specification. That is the point of lint: it is the part of the tool that is useful on the first morning, on a host nobody has written a policy for.

Here is a small input chain, policy drop, written the way input chains tend to accumulate:

ct state established,related accept                          # handle 2
tcp dport 443 accept                                         # handle 3
ip saddr 198.51.100.0/24 tcp dport 443 accept                # handle 4
ip saddr 203.0.113.0/24 tcp dport 22 drop                    # handle 5
ip saddr 203.0.113.66 tcp dport 22 accept                    # handle 6
tcp dport 22 accept                                          # handle 7

and what anabasis lint makes of it, fingerprint lines omitted:

Rules that do not do what they say
  [redundant rule] ip/filter/input/handle:4
      the rule never fires: earlier rules already decide every packet it matches, the same way
      rule: match saddr == 198.51.100.0/24 match(implicit) l4proto == 6 match dport == 443 verdict accept
  [correlated rule] ip/filter/input/handle:5
      part of what the rule matches was already decided the other way
      rule: match saddr == 203.0.113.0/24 match(implicit) l4proto == 6 match dport == 22 verdict drop
  [shadowed rule] ip/filter/input/handle:6
      the rule never fires: earlier rules already decide every packet it matches, the other way
      rule: match saddr == 203.0.113.66 match(implicit) l4proto == 6 match dport == 22 verdict accept
  [correlated rule] ip/filter/input/handle:7
      part of what the rule matches was already decided the other way
      rule: match(implicit) l4proto == 6 match dport == 22 verdict accept

0 failed, 0 undecided, 0 satisfied, 0 not applicable, 4 anomalous rules

Handle 4 is the one everybody has written at some point: a narrower accept below a broader one, typically for a network that was going to get some special treatment and ultimately never did. Handle 6 is the one that matters – an exception for one address inside a range dropped two lines earlier, which will never fire under any ordering of events whatsoever, and whose author presumably believes that it works. Handle 7 is the textbook technique, drop a range and then accept the port for everyone else. And handle 5 is instructive in a way I did not set out to make it: a drop placed after ct state established,related accept is correlated with that accept, because established traffic from 203.0.113.0/24 to port 22 was accepted before the drop was reached. That is true, it is a warning rather than an error, and on a real host it is exactly the arrangement one wants; the report says so and leaves the decision where FIREMAN left it. The run exits 1, because two findings are errors; --fail-on moves that threshold.

Two managers, one hook

The classic taxonomy assumes a single ordered list of rules. nftables has no such thing, and Book three spent a paragraph on the consequence: accept ends the current base chain, drop ends the ruleset, so a packet has to survive every base chain on its path. The lint layer adds the anomaly that only exists because of that, and its doc comment says where it lives:

Invisible to any analysis that stops at the first accept, and the normal shape of a host running several firewall managers at once.

Two tables, then, each with a base chain on input – the host’s own, which opens 8080 for a service, and a hardening table somebody added later, at priority 10, which drops 8080 because nothing was supposed to be listening there. The host’s table also carries a chain called legacy-admin that nothing jumps to any longer, and a set called old-office that no rule consults:

Rules that do not do what they say
  [nullified accept] ip/filter/input/handle:6
      the rule accepts traffic that a later base chain on the same path drops
      rule: match(implicit) l4proto == 6 match dport == 8080 verdict accept
  [unreachable chain] ip/filter/legacy-admin
      no jump or goto reaches the chain
  [unused set] ip/old-office
      no rule looks anything up in the set

0 failed, 0 undecided, 0 satisfied, 0 not applicable, 3 anomalous rules

Read on its own, the accept at handle 6 is perfectly healthy: nothing above it in its chain touches port 8080, and a chain-local analysis would pass it without comment. It is dead at the level of the ruleset sum total, because every packet it accepts is dropped by the next base chain on the path; the condition is simply that what the rule matched has an empty intersection with the path’s accept set, and that set is the one Book four spent a whole post computing. The other two findings are notes, and they are structural – visible from the ruleset alone, without evaluating anything – which is why this run exits 0.

The production host

And the ruleset this series has kept returning to, the one from Book one with its 23,621-address blocklist:

Rules that do not do what they say
  [correlated rule] ip/filter/input/handle:14
      part of what the rule matches was already decided the other way
      rule: match saddr == @crowdsec-blacklists counter verdict drop
  [correlated rule] ip/filter/input/handle:16
      part of what the rule matches was already decided the other way
      rule: match(implicit) l4proto == 6 match dport == 80 443 18080 18081 counter verdict accept

This yields two warnings, no errors, exit code 0. Both are deliberate, and both are the technique FIREMAN described. The blocklist drop at handle 14 sits below the rules that admit loopback, established connections, DNS from the container bridges and the database from its own bridge, so part of what it matches – a blocklisted address arriving on one of those – was already accepted in the first place; the published services at handle 16 are accepted for everyone the blocklist did not take.

There is also something lint is not, and it is better said here than discovered in an incident. Lint tells you that a rule contradicts or duplicates others. It cannot tell you that the rule is the wrong rule. To drive the point home, I moved the accept for the published services above the blocklist drop – two rules swapped, nothing else touched – which opens every published port to all 23,621 addresses on the list. Lint’s verdict on the damaged ruleset:

Rules that do not do what they say
  [correlated rule] ip/filter/input/handle:14
      part of what the rule matches was already decided the other way
      rule: match saddr == @crowdsec-blacklists counter verdict drop

0 failed, 0 undecided, 0 satisfied, 0 not applicable, 1 anomalous rules

The number of warnings drops to one, and exit code 0: by the only measure lint has, the broken ruleset looks tidier than the correct one, since the accept no longer overlaps anything the drop decided. The drop still fires, for every blocklisted packet not bound for a published port, so it is neither shadowed nor redundant, and nothing in the taxonomy can say that it now fires for the wrong half of its packets. The specification, however, can, because it states the intent:

  [fail] blocklisted-sources-reach-no-published-service (deny input, ip)
      traffic the specification forbids is accepted
      example: ip tcp 1.12.48.131:0 -> 0.0.0.0:80 ct state new iif br-vm1
      ...
      decided by ip/filter/input handle 16: accept [match(implicit) l4proto == 6 match dport == 80 443 18080 18081 counter verdict accept]

1 failed, 0 undecided, 10 satisfied, 0 not applicable

Lint asks whether every rule pulls its weight. Whether the weight is pulled in a direction anybody intended to go in is a question only the specification can answer, and a host needs to be interrogated with regards to both questions.

Lint findings are fingerprinted like assertion findings, and they are also suppressed the same way. The one difference is what goes into the hash: there is no witness, so the fingerprint covers the rule’s text, and that raised a question I had to answer when the trace output was made readable. The comment on the fingerprint function records the answer:

The rule’s canonical text, never its readable one: the readable rendering may improve between releases, and a suppression has to outlive that.

So the rule text has two forms. The one people read renders 203.0.113.10 as an address; the one the fingerprint hashes still says 3405803786, as it did before anybody noticed, and is byte-stable by contract.

The tool on trial

The generals at Cotyora were fined for shortfalls, and the second half of this post is the tool’s account of its own – the places where it cost more than it should have, and the places where I believed something about its cost that turned out to be false.

One rule governs every figure below: each names the machine it came from, since two machines appear in what follows and they disagree by better than threefold about the same quantity. The development machine is a 9950X3D at 5.85 GHz with 96 MB of last-level cache; the build runner is an EPYC Zen 4 in a virtual machine at 2.75 GHz, reporting 16 MiB. One cold evaluation of the production dump’s input path costs 50.0 ms on the first and 182.3 ms on the second. The clock accounts for a factor of 2.13 of that 3.6. The cache accounts for most of the rest.

Construction is bound by the memory system, not by arithmetic. On the development machine, the same node insertion costs 14.3 ns when the unique table is five megabytes and 129.3 ns when it is three hundred – 83 cycles against 756, a ninefold degradation for an operation that has not changed. Over the same range the diagram grows more efficient per address, 398 nodes each at 64 addresses and 176 at 65,536; the work per address falls while its cost rises, and only the memory hierarchy explains that. The break sits where the footprint crosses the last-level cache, and the production dump sits on that line rather than safely inside it: compiling it holds 949,430 nodes, 15.2 MB, and one cold walk of its input path 1,470,970 nodes, 23.5 MB. That fits comfortably in 96 MB and does not fit in 16 MiB, and that accounts for most of the remaining gap between the two machines.

Operation cache hit rates. It hits 6.7 % while compiling and 22.2 % while evaluating, and a hit rate of 6.7 % looks for all the world like a broken hash. The key really was sloppy – twenty-eight-bit identifiers shifted into a single word so that the fields begin to overlap once identifiers pass 2²⁰ – and I was ready to fix it. Raising the cache from one megabyte to two hundred and sixty-eight moved the rate to 6.8 %. Of 552,620 lookups, 512,361 are operations the run has never performed before, and no hash and no capacity can answer a question nobody has asked yet in a more timely manner; canonicalising commutative operands so that and(a,b) and and(b,a) share a slot changed the hit count by two in 339,129 and was reverted. The decision log closes on the moral, which I intend to keep: “a suspicious-looking number is a reason to measure, not a diagnosis.” I did fix the key in the end, together with the unique table’s, which overlapped in the same fashion from 2²⁴ onwards, and the fix achieved precisely what the measurement had predicted: thirty hits more while compiling, seventy-five fewer while evaluating, and an extra round of mixing on every lookup. Nevertheless, it’s here to stay. Neither key could ever produce a wrong answer, since every entry is compared in full; but past those thresholds, and the node budget admits 2²⁸, whole families of distinct keys would have shared a bucket on every table size, and a hash whose behaviour depends on how large the diagram grows is not one I am willing to ship, least of all for a gain of a few milliseconds of walltime.

The lever turned out to be the unique table’s load factor, and I only found it because a second measurement contradicted the first. A lookup walks a bucket’s chain by index into the node table, so a long chain means a string of random reads scattered across megabytes. My first sweep put the best load factor at three eighths: 23.2 ms to compile the dump, against 31.5 ms at the conventional three quarters. A third off. That looks like a result, and I treated it as one. Then I took medians of seven runs, and the same configuration came out at 29.8 ms – worse than the three quarters it was supposed to have beaten. What settled the matter was alternating the two builds, five rounds each. Rehashing at one half takes compilation from a median of 28.3 ms to 24.6 ms, with no round of one build overlapping any round of the other, and a cold evaluation from 52.7 ms to 50.0 ms. Thirteen per cent, and five. Not the third the first sweep had promised. Below a quarter it reverses, because at that point the bucket array itself stops fitting in cache – the same boundary the construction curve had found from the other side.

I also tried a parallel BDD library, and turned it down. Sylvan is the obvious candidate for anyone who builds decision diagrams and owns more than one core, so I measured it against the three things that would have justified pulling it in. Construction is memory-bound, as above, and parallelism does nothing about that. The operation Sylvan parallelises natively isn’t where the time goes: one difference over two multi-million-node diagrams costs under one per cent of what it cost to build them. And the parallel ceiling is low even when nothing is shared at all. Twelve workers, twelve completely independent kernels, no lock, no common table – and they reach 3.51×, an efficiency of 29 %. A good part of that apparent win turned out to be partitioning, which you can attain single-threaded simply by not building one enormous diagram in the first place. A library would have had to beat that while adding contention on a shared table, and it would have cost me a process-global singleton, worker threads in a process whose kernel oracle refuses to fork from one, and a vendored submodule. So the kernel stays in-house, and the lever is locality.

A layer I built, and removed. The literature on atomic predicates is persuasive, and I built the layer during the evaluation milestone: partition the packet space into the minimal set of regions every predicate respects, and answer questions as unions of region identifiers. The partition was as small as promised, 24 atoms for 36 rules. Measured against the plain diagram path on the production dump, it was 11.7× slower for sixteen questions, 12.9× for sixty-four and 23.9× for two hundred and fifty-six – the gap widening, which is the opposite of amortisation. The cause is structural: exactness requires every question’s predicate to be in the partition, so the partition grows with the number of questions - therefore, the concept was stricken from Anabasis altogether.

Measuring the measurement

The load-factor episode is a small instance of a larger problem, and I ran into the larger one this week in the most mundane way possible. The compiler on my machine was rebuilt without debug symbols, and before it was, I took a baseline of the entire benchmark suite, 111 measurements, so that I could tell whether the new compiler had changed anything. Afterwards I ran the suite again, and then, having rebuilt once more, a third time.

Within any one run, the suite is superbly stable: Google Benchmark reports a coefficient of variation per measurement across its repetitions, and the median of those is 0.30 %, the 95th percentile 2.1 %. By that standard, anything that moves by more than a few per cent has moved. Between the two builds made from the same source with the same compiler, the median measurement moved by 3.5 %, the 90th percentile by 13.3 %, the 95th by 28.3 %, and the worst by 59.5 %; parsing the production dump was 42 % slower in one build than in the other.

The coefficient of variation measures the run-to-run spread of one binary. It says nothing about the spread between two binaries that ought to be identical, and that spread – code placement, alignment of hot loops, the partitioning a link-time optimiser happens to choose – is an order of magnitude larger. This remains an assumption, since I did not conduct a deep dive into the generated assembly code and binary layout, yet the practical consequence is a humbling one. This suite can tell me, reliably, that a change made one binary slower than itself; it cannot tell me, from a single pair of builds, that a compiler upgrade cost five per cent, because a rebuild alone costs up to twenty-eight at the 95th percentile. The comparison I ran for the compiler upgrade found exactly one genuine change – small synthetic parses got faster, most plausibly because the library assertions of the previous build were gone – and everything else it flagged vanished on the rebuild.

This is why the pipeline’s regression gate, Bencher, keeps every compiler and machine pair as a separate testbed with its own baseline and never compares across them, and why the scaling families cannot be given tight thresholds at all: a gate tuned tighter than the noise between two identical builds is a gate that cries wolf until somebody switches it off, and Book seven had a good deal to say about that kind of gate.

What the march changed

Three pieces of engineering deserve a line each before the fines are read out, each of them closing a thread that an earlier post opened.

The first is the intermediate representation, which Book six leaned on without naming: both engines, the symbolic evaluator and the concrete interpreter, read the same normalised model of the ruleset and share nothing else, which is what made their agreement mean something and their shared misreadings dangerous. The IR is index-typed and value-semantic, and anabasis dump-ir prints it; when a report about a rule looks wrong, the lowered form of that rule is the first thing worth looking at.

The second answers Book one. That post complained that upgrading nft reorders the dump and re-spells five of its thirty-six rules, so that byte-comparing drift detection fires on a firewall that has not changed and “every suppression you’ve ever written expires at once”. The recording was loaded into a throwaway namespace and dumped again by nft 1.1.7, eight minor releases after the 1.0.9 that recorded it, and a test now holds the two side by side. From its doc comment:

The fingerprint is the strict part. A verdict that merely agreed would leave room for the witness to have moved, and a moved witness is a moved suppression: every suppressions: entry a user has written would stop applying the day they upgrade nft.

The same profile produces the same eleven findings and the same two anomalies – the correlated warnings above – with byte-identical fingerprints from both emissions. A second test checks that the two fixtures really are different documents, since without it the first would pass just as happily if somebody accidentally copied one file over the other, and would then guard nothing whatsoever.

The fines

Philesius and Xanthicles paid twenty minae each. Here is what v1 does not do, stated the way the report states it – which matters, because Book three drew a line between the two ways the tool can decline to answer, and the line holds here too.

Some things are outside the model but do not change a verdict on their own, and the report lists them under assumptions: policy routing, VRFs and any routing table other than main and local; accept_local and route_localnet; the source address on the output path, which IP_FREEBIND and transparent proxies leave free; and IPv6 reverse-path filtering, which the kernel does not offer. On the bridged path, the bridge family’s own input and output hooks are reported as a boundary rather than modelled on a guess, and so are ethernet addresses and VLAN tags as fields.

Other things the tool does not model at all, and a rule that uses them makes its verdict inconclusive with the construct named: the arp and netdev families as paths of their own, flowtables, queue to user space, map-driven and dynamic NAT targets, conntrack helpers and expectations, the simulation of connection tracking itself, and IPv6 extension headers beyond the protocol abstraction.

Two things were never in scope for a tool of this shape: analysis across several hosts at once, for which FIREMAN’s trees of access lists would be the template if anybody ever wanted it, and incremental re-verification as the ruleset changes, which is a daemon’s problem and a different algorithm altogether. And one belongs to the lint layer specifically. FIREMAN’s taxonomy has a fourth member, generalization – a later rule that matches a superset of an earlier one with the opposite verdict – and Anabasis does not report it under that name. The packets are not lost: when the earlier rule fires at all, what it decided is part of what the later rule matches, decided the other way, so every generalization surfaces as a correlated warning – handle 7 in the first example is one – or as a shadowed rule if nothing is left for the later rule at all. What is missing is the distinction, the statement that the later rule covers the earlier one entirely rather than merely overlapping it.

None of this is concealed. Each item, wherever a ruleset touches it, appears in the report by name, as an assumption or as the reason a finding is undecided, which is the only form in which a limit is of any use to the person reading the report.

Remember the good as well

Xenophon’s defence at Cotyora does not end with the buried man. He goes through the others who had been struck – the stragglers, the men who sat down in the snow and would not get up, the one who left the ranks to loot – and then he turns on the assembly with a complaint that I suspect every engineer who has ever sat through a post-mortem will recognise:

“But really,” he added, “it does surprise me with what keenness you remember and recount the times when I incurred the hatred of some one; but some other occasions when I eased the burden of winter and storm for any of you, or beat off an enemy, or helped to minister to you in sickness and want, not a soul of you remembers these.”

Whereupon, one after another, the soldiers stood up and began recalling incidents of that kind, “and things ended not so unpleasantly after all”.

This post has been the examination, and I have tried to keep it honest: the rules that do nothing, the benchmark I believed and should not have, the library I measured and refused, the layer I built and deleted, the anomaly I have not yet implemented, and the long list of things the kernel does that v1 does not model. The other side of the ledger is the seven posts before it. Packets as points and policies as shapes; a bracket around every answer, so that what the tool does not know is carried into the report rather than guessed at; a ruleset folded into a set, NAT included; the host underneath it that decides which packets ever arrive; a kernel that gets the final say on whether any of it was read correctly; and a specification language in which one writes down what was decreed, and a report that says, with a packet in evidence, whether it was carried out.

The army stood on Theches and saw the sea in Book one. At Cotyora it is on the coast, it has counted its losses and it has answered for its conduct, and there is still a way to go before anyone is home.

Anabasis will release in the near future, with the release date planned to be on October 15th or earlier, at which time, an announcement to that effect will be made on this blog. If you wish to be notified, keep in mind that this blog is fediverse-capable and may be followed via @roman@rospies.dev; afterwards, you may enable notifications regarding new posts on your fediverse platform of choice.

Thank you for joining me on this journey, and I hope to hear some feedback from fellow engineers as soon as Anabasis releases!

εἰς αὖθις