Anabasis, Book 2 - Σταθμοὺς τρεῖς, παρασάγγας πεντεκαίδεκα

ἐντεῦθεν ἐξελαύνει σταθμοὺς τρεῖς παρασάγγας πεντεκαίδεκα ἐπὶ τὸν Εὐφράτην ποταμόν, ὄντα τὸ εὖρος τεττάρων σταδίων· - “From there he marches three stages, fifteen parasangs, to the river Euphrates, which is four stades in width.”

The first post of this series set out on a journey; this one keeps marching.

You may recall on which note the previous article ended. To an nftables ruleset, an IPv4 packet is a vector of at least 157 boolean variables (the exact figure depends on how many bridge interfaces the host has), and an IPv6 packet one of 349. The question an auditor wants answered, whether anything at all can reach tcp/22 from outside, concerns every one of those variables simultaneously. All claims I make about a packet have to be defensible for all 2^157 possible candidate packets at the same time. Now, while this may look insurmountable, the reason it is not is that counting packets is the wrong way to approach the issue altogether.

A packet is a point, a policy is a shape

Stop thinking about individual packets, then, and think about sets of them.

Every field a rule can inspect has a fixed width in bits. Concatenate the fields and a packet becomes a single point in a bit space of 157 dimensions. A set of packets, whether that is everything the firewall accepts, everything it drops, or everything one particular rule matches, is simply a subset of that space; and a subset of a bit space is precisely a boolean function, one that takes a packet and answers yes or no.

Reframing the issue like that carries the whole project, because every question I care about is now an algebraic question - set algebra, to be precise. Does a rule admit something it should not? To answer that question, we may intersect what that rule accepts with what the policy forbids and test the result for emptiness. Can we assert whether the claim “SSH only from the management network” is actually enforced? Let’s aggregate everything that may access port 22, subtract the management network, and test for emptiness of the resulting set. Inclusion is itself the emptiness of a difference, since A ⊆ B holds exactly when A − B = ∅. Reduced to essentials, three primitives remain: intersection, complement, and an emptiness test. Every compliance check in the tool is ultimately assembled from those three.

At this point, we should also admit that our problem has just been reduced to one which is famously intractable. Bryant says as much in the opening paragraph of his 1986 paper: deciding whether a boolean expression has a satisfying assignment, or whether two expressions denote the same function, is NP-complete or coNP-complete, and every known method is exponential in the worst case.

So the question was never whether a clever algorithm exists; it does not. The question is whether the functions that arise from real firewall rulesets are the hard instances or the easy ones. That is worth asking, because the answer turns out not to be the one the worst case threatens.

Bryant’s work in 1986

We’ll start with the most naive construction possible: a binary decision tree. The core idea is to test the first bit, with two branches pointing to the two children - one for each outcome; each of those children conducts a test on the second bit, and this continues for a total of 157 levels, at the end of which we’ll reach the leaves with a binary decision on whether the statement in question is true or false. While that approach may work in theory, it’s of endearing naivety and quite useless, with the tree having 2^157 leaves.

Look more closely at what the tree contains, though. A great many of its subtrees are identical, because most bits are irrelevant most of the time. A rule matching tcp dport 22 has no opinion about the source address, so all 2^32 of its source-address subtrees are the same subtree. We are then able to store that subtree once, point to it from everywhere it occurs, et voila! The tree has just collapsed into a directed acyclic graph (DAG). Finally, we remove every node whose two branches lead to the same successor, since a test whose outcome changes nothing carries no information at all.

Both of those moves look like mere housekeeping, an impression worth dispelling, for they are forced upon us the moment one asks what a node in such a graph actually is. Any boolean function whatsoever splits, at any variable one cares to pick, into the two functions obtained by nailing that variable down, which is Shannon’s expansion and looks like this:

A node testing x, with its low child pointing at the first of those two and its high child at the second, is that equation and nothing besides, written down as a pair of pointers. Which settles both reductions in one go. Should the two branches happen to denote the same function, then f does not depend on x whatsoever, the node conveys precisely nothing and out it goes; and should two nodes carry the same variable alongside the same pair of children, they cannot help but denote the same function, since the decomposition admits no second answer. Those two observations are what “reduced” means, and they are not yet enough for uniqueness: reduce the same function under two different variable orderings and you are left with two different graphs, both of them perfectly reduced. What is still missing is the constraint that arrives in the next paragraph.

None of this was new in 1986. C. Y. Lee had these graphs at Bell Labs in 1959, under the name “binary-decision programs”, and Akers published “Binary Decision Diagrams” under that very title in 1978. Bryant’s contribution was a brilliant idea: fix a single variable ordering, globally, and require every diagram to test its variables in that order. Then reduce. Theorem 1 of his paper is what follows, and it is what enables us to pursue this project in the first place:

For any Boolean function f, there is a unique (up to isomorphism) reduced function graph denoting f and any other function graph denoting f contains more vertices.

Unique. Not usually small, not small with luck: the same function always produces literally the same graph, and that graph is the smallest one denoting it. Once two packet sets have been constructed, deciding whether they are equal amounts to comparing two integers, and deciding whether a set is empty amounts to comparing one integer with the identifier of the false terminal. While the set of everything that survives a thirty-six-rule ruleset is an enormous object, asking whether it intersects the set of packets bound for port 22 from the outside world comes down, once both have been properly modelled and built, to ==.

That property is the reason my kernel never reorders variables once construction has begun - canonicity holds only relative to the initial ordering; should one change it, every node identifier you are holding quietly decays and becomes worse than invalid, for it confidently points at a potentially wrong answer.

Firewall rules are not the worst-case scenario, far from it

The catch, which Bryant quite candidly points out: graph size catastrophically depends on the variable ordering. His own example places two functions side by side,

which are the same function up to renaming, and yet the first needs 2n+2 nodes where the second requires 2ⁿ⁺¹. Finding the ordering that minimises the graph is, moreover, itself coNP-complete.

That ought to be alarming, yet in practice it is not, for a reason Bryant also supplies: one does not need the optimal ordering, only a reasonable one, and the problem domain usually provides that. By analysing the domain, he writes, one can generally devise a strategy for a good ordering, and many orderings prove acceptable.

Since firewalls have a predefined shape of a rule, an - at the very least acceptable - ordering follows directly from it. The fields are laid down one after another, most significant bit first within each, and I order the fields themselves roughly by how selective they tend to be: conntrack state, input interface, output interface, transport protocol, source address, destination address, source port, destination port, TCP flags, ICMP type, firewall mark.

The most-significant-bit-first layout is what does the real work. A rule matching 10.0.0.0/8 constrains the top eight bits of the source address and is indifferent to the remaining twenty-four. With the address being laid out MSB first, that rule becomes a path eight nodes deep, after which it simply stops testing. It does not enumerate 16.7 million addresses; it does not even represent them individually. A CIDR prefix and a BDD path are, structurally, the same object, a happy accident of two notations having grown up with the same shape.

This is not merely my impression - Yang and Lam proved the bound: a rule whose per-field constraints are prefixes, suffixes or intervals has a decision diagram of at most 2 + 2h nodes, where h is the number of header bits. To paraphrase that finding, the cost of a single rule, however vast the set of packets it describes, is bounded at a few hundred nodes, and a few hundred nodes is nothing to even meaningfully consider on modern hardware when using a compiled language - we’ll get to the limits of that statement in short order.

What comes free of cost

Two entries in Bryant’s table of basic operations proved to matter in ways I had not entirely anticipated.

Satisfy-one walks the graph and returns some member of the satisfying set, in time linear in the number of variables. In my terms: given the set of packets that violate an assertion, produce one. That is a single descent through 157 levels, so every finding the tool emits can carry a concrete packet, complete with source address, port, interface and conntrack state, that demonstrates the problem. Telling someone their SSH rule is too broad invites a debate. Handing them a packet from 203.0.113.7 that their firewall will accept ends one.

Satisfy-count runs in time proportional to the size of the graph and returns the cardinality of the set, so a finding can also state how large the hole is, which is the difference between something worth waking a person for and something worth a ticket.

I derived neither implementation from scratch; rather, those two implementations come with the territory and the groundwork Bryant has laid.

There is one wrinkle, of the kind that separates a working tool from a demonstration. Field widths round up to whole bits, so some bit patterns in the 157-dimensional space correspond to no real packet: conntrack state occupies three bits, which gives eight encodings for five states, and three of those encodings are nonsense. Leave them in and Satisfy-one will sooner or later present a user with a counterexample that cannot exist, and from that moment on nobody trusts the tool again. The space therefore carries an explicit domain set of the encodings that mean something, and everything is intersected with it. The mathematics does not care; the person reading the report does.

The bill

BDDs are not magic, and where they hurt is exactly where my production ruleset hurts.

The pathological input for this representation is a large number of individually listed, unrelated values in a single field, because there is no shared structure to exploit, and sharing is the entire mechanism. A CrowdSec blocklist of 23,621 individual addresses has precisely that shape. It is also, unfortunately, an entirely ordinary thing to find on a server.

Here, then, is the real cost. After compilation, that ruleset yields 949,430 nodes, about 15.2 MB, while a single cold evaluation of the input path holds 1,470,970, roughly 23.5 MB. Bryant reported in 1986 that his algorithms remained practical up to roughly 20,000 vertices, which was limited by the hardware capabilities of his time. We are running seventy times that on a desktop computer, and the credit belongs wholly to the hardware rather than to anyone having invented a smarter approach to the issue.

Then comes the part I did not expect, and found only because, like the man in the rearguard, I rode forward and looked instead of assuming.

A node insertion into the table costs 14.3 nanoseconds when the table occupies five megabytes and 129.3 nanoseconds when it occupies three hundred megabytes. This surprisingly comes out as 83 cycles against 756 on a Ryzen 9 9950X3D at 5.85GHz for an operation that does exactly the same amount of work in either case. At the same time, on the other hand, the diagram evolves to be more efficient as it grows larger, from 398 nodes per address at 64 addresses to 176 at 65,536. The work per address falls while the price of that work climbs, and when tracing that fact back to its causes, we learn that the crossover happens precisely at the point where the last-level-cache ceases to accommodate the node table.

To paraphrase - the computation is indeed not limited by the algorithm, but by the memory wall or, to be more precise, whether we hit it, depending on last-level-cache size. The same binary runs three times slower on a 48-core EPYC with 16 MiB of L3 than on my desktop running a 9950X3D with 96 MB of V-Cache, and the difference in clock speed accounts for only about two-thirds of that gap. I spent some time being irritated by this before recognising it as the more interesting result: a graph algorithm from 1986 running on a 2025 machine is not compute-bound, for it is a cache residency problem wearing a trenchcoat.

The state of affairs

We have now built the capability to build sets of packets, intersect and subtract them, decide in constant time whether they are empty, and extract a witness and a cardinality from any of them. That is the algebra, and it holds. This leads us to what we’re yet lacking: a firewall.

A ruleset is not a set in the true sense of the word, but an ordered sequence with first-match semantics, jumps into other chains, a default policy for the case where nothing matches, and a NAT stage that rewrites the packet before any later rule sees it. Turning thirty-six rules across six chains into two clean sets, accepted and dropped, is a very much separate problem with a literature of its own, which we’ll address in due course.

Beneath it lies a harder question still. Some rules act in ways this model may not represent at all, and so the question arises what a compliance tool should say when part of a ruleset falls outside what it understands. “Probably fine” is the one answer that must never appear. That constraint forces our entire design schematic to adopt a three-valued logic, which we’ll approach in the next post.