How Boolean Logic Can Be Used to Build Firewall ACLs

An Access Control List (ACL) is a set of rules used to filter network traffic and perform actions based on packet information — more specifically, packet header information. These actions may include blocking traffic, redirecting it, or performing any other operation. ACLs are mainly used to control access to network resources and manage traffic flow.

They are commonly used in many network devices such as routers, NATs, switches, firewalls, proxies, and many others.

Example of a Simple ACL Rule

Action Protocol Source-ip Source-port Destination-ip Destination-port

permit tcp 192.168.1.0 0.0.0.255 8080 any 80

This rule can be divided into:

• Action: Specifies whether matching traffic is allowed or denied.
• Protocol: Specifies the traffic protocol (in this case TCP).
• Source IP: The source IP range (192.168.1.0 to 192.168.1.255).
• Source Port: The source port is 8080.
• Destination IP: Any destination IP address.
• Destination Port: The destination port is 80.

First Match Wins

This means the order of rules in an ACL is critical because ACLs are processed sequentially from top to bottom.

But why is that? :)

It is common practice in firewalls to deny every packet by default unless it is explicitly allowed. To achieve this, we first add rules that allow specific traffic and then add another rule that blocks everything else.

Keep this point in mind — we will get back to it soon.

Building a Simple ACL

If I wanted to build a simple ACL, my naive approach would be to use some sort of dictionary for lookups. The dictionary key would contain all packet properties, while the value would be the action.

packet-hash = protocol + source-ip + source-port + destination-ip + destination-port
ACL[packet-hash] = action

Okay, this is straightforward and gives us very fast lookups, but I have a few issues with it:

• How do we handle IP ranges? :( To encode IP ranges, I would have to loop through every IP address in the range. This applies to both source and destination addresses. Memory usage would grow massively and would not scale well.
• Order please! Remember the point about rule ordering? If we use a dictionary, we cannot guarantee rule priority.
• Can’t grow. This design is limited and difficult to extend with additional features.

To solve these issues, I had to research a different method: representing ACL rules as Boolean functions. This would allow me to add logic and ordering to the matching process while keeping lookups efficient.

That search eventually led me to BDDs.

Reduced Ordered Binary Decision Diagram (ROBDD)

The Reduced Ordered Binary Decision Diagram (ROBDD), commonly referred to as a BDD, was introduced by Bryant in 1986.

A BDD is a data structure that uses a directed acyclic graph (DAG) for representing and manipulating Boolean functions. It has been used in model checking, digital circuit synthesis, Boolean optimization, and many other cool applications.

But here we will use it for ACLs :)

Every BDD consists of:

• Root Node: Serves as the entry point for evaluation.
• Decision Nodes: Each node represents a Boolean variable and has two outgoing edges: a low edge (0) and a high edge (1).
• Terminal Nodes: Represent the final Boolean outcomes.

Example of a BDD

example of OBDD Representation from https://www.cs.cmu.edu/~bryant/pubdir/hmc-bdd18.pdf

Okay, How Can I Convert an ACL Rule to a BDD?

To do this, I first need to convert the rule information into binary form so it can be represented as a Boolean function.

A simple way is to combine all components using the AND operator:

Rule = Protocol ∧ Src-IP ∧ Src-Port ∧ Des-IP ∧ Des-Port ∧ Action

I will assume we are only building ACLs for IPv4 — I don’t want to complicate my life :)

IPv4 is a 32-bit value consisting of four octets separated by dots, for example:

192.0.2.50

We can represent an IP address as:

IP = ip[0] ∧ ip[1] ∧ ip[2] ∧ ip[3]

Each octet is converted into an 8-bit vector, which can then be transformed into a Boolean expression.

Similarly, we can represent ports. Since ports range from 0 to 65535, we need a 16-bit vector.

For protocols, in my case I only support TCP and UDP. A single bit is enough:

0 = TCP
1 = UDP

Of course, you could extend this to support more protocols.

The action can also be represented using a single bit:

1 = Accept
0 = Deny

Again, this could be extended later if you wanted more actions.

Now that we have converted all packet information into binary form, the next step is to represent it in a BDD.

If a bit is 1, we use the variable node (N).

Get Mustafa Abdalwahab’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

If a bit is 0, we use the negated variable node (~N).

Combining Multiple Rules While Preserving Order

Okay, I have encoded a single rule into binary form.

Now how do I combine multiple rules into an ACL while preserving rule order?

This is where Boolean operators come in.

Suppose we have three rules: R1, R2, and R3.

The ACL can be represented as:

ACL = R1 ∨ (~R1 ∧ R2) ∨ (~R1 ∧ ~R2 ∧ R3)

The expression means:

• Execute R1.
• If R1 does not match, execute R2.
• If neither R1 nor R2 matches, execute R3.

This preserves the first match wins behavior because each rule is only evaluated if all previous rules failed to match.

Performing Lookups

Now that the ACL is encoded as a BDD, how do we perform lookups?

To do this, I take advantage of the absorption law:

(A ∨ B) ∧ A = A

For an incoming packet, I build a BDD representation of the packet and perform an AND operation with the ACL BDD.

If the result equals the packet BDD, we have a match:

if (bdd_packet AND acl) == bdd_packet then
    we have match

So the lookup process becomes very simple.

Storing ACLs

Now I have a fully functioning ACL that can encode rules and match packets.

However, from an operational perspective, I wouldn’t want to rebuild and re-encode the ACL every time the firewall starts.

A better approach is to build the ACL once and store it as a binary file that can be loaded at startup.

This raises another question:

What if I want to update a rule?

Updating Rules Using XOR

Here we can take advantage of another useful property from Boolean algebra:

A ⊕ B = X
X ⊕ A = (A ⊕ B) ⊕ A = B

To update a rule:

1. Convert the old rule into a BDD.
2. Convert the new rule into a BDD.
3. XOR them together.
4. XOR the result with the ACL.

tmp_rule = old_rule ⊕ new_rule
acl = acl ⊕ tmp_rule

This effectively swaps the old rule with the new one.

Deleting Rules

What if we want to delete a rule?

By now, I guess we all know there is always a Boolean trick :)

The ACL is a superset of rules and we want to remove one specific rule.

Mathematically:

acl = acl - rule

Unfortunately, BDDs do not directly support the difference operation.

However, we can transform it into an intersection with the complement:

A − B = A ∧ ~B

So deleting a rule becomes:

ACL = ACL ∧ ~rule

The complement of the rule can be calculated using DeMorgan’s law on the Boolean expression that represents the rule.

Closing Thoughts

There are more tricks up the sleeve, such as detecting intersecting rules or identifying when one rule shadows another. But I’m tired of writing for today :)

If for some reason you want to see some weekend code that makes all of this work, I have a GitHub repository where I built a simple firewall that doesn’t actually block anything — it just prints to the logs whenever a packet matches https://github.com/msf37/bdd-acl .

BDD is an old technique, but it is still used in production systems today. It works, and it is definitely worth reading Bryant’s original paper if you are interested in the topic https://www.cs.cmu.edu/~bryant/pubdir/hmc-bdd18.pdf .

It is also worth mentioning that i found a group of researchers approached the problem from a completely different angle. Instead of representing packet headers as Boolean functions, they introduced the concept of Header Space Analysis.

The idea is surprisingly simple and mind-blowing at the same time: what if packet headers were treated as points in a geometric space, and we applied geometric operations to reason about networks?

Their paper is available here:

https://www.usenix.org/system/files/conference/nsdi12/nsdi12-final8.pdf

It would be fun to explore that approach another time.