2023-10-14
Stateful versus stateless firewalls, and why stateful is attractive
One of the distinctions in network firewalls is between ones that primarily operate with state entries for connections and ones that are primarily stateless. Somewhat famously, OpenBSD's PF packet filter wants to be stateful, although you can coerce it to operate in a stateless mode. This stateful mode can create problems with things like denial of service attacks, so you might ask why OpenBSD prefers stateful operation. The simple answer is that a stateful packet filter will often perform better, although this depends on what sort of traffic it sees.
The reason a stateful packet filter can perform better is that it usually has an easier job. Generally speaking, the state entries for 'connections' (which for UDP and other stateless protocols are really flows) are orderless and almost always unique. For example, for UDP and TCP, the tuple of source IP, source port, destination IP, and destination port uniquely identify a connection (possibly augmented with local context such as whether the packet is being received or sent, and on what network interface). When you have orderless and generally unique state entries like this, there are plenty of data structures that provide fast lookups for them, so it's easy for the packet filter to find the state entry for a given packet (if it exists) and proceed from there.
By contrast, packet filtering rules are almost always ordered and not easily established as unique. A given packet often may potentially match multiple rules, and the order that you check rules for a match is usually semantically meaningful (often the first matching rule decides the packet's fate). This means that you need to evaluate rules in order, or at least provide results that are the same as if you actually did that. In practice, even though you may have a lot of packet filtering rules, a given packet can only possibly match a few of them; however, transforming a general list of packet filtering rules into efficient data structures for rapid minimal matching is a non-trivial programming exercise and is rarely done automatically. This leaves packet filters to do a bunch of rule checking for every stateless packet.
(In theory you can hand-optimize your firewall rules. In practice the optimized versions may be much harder to understand and change, which isn't necessarily a good tradeoff.)
The fly in this ointment is the question of what sort of traffic your packet filter actually sees. Common firewall implementations only establish state for successful connections (or flows); if the firewall rejects packets, they don't create state. Thus, the more rejected traffic that your firewall sees compared to accepted traffic, the less state entries are helping you since every rejected packet always requires checking some or all of your firewall rules.
(But at least the accepted traffic gets a fast pass through the filter, which may be important even if you're spending a lot of system resources on checking rules for packets that you reject.)