Are all firewall systems equally powerful?

Firewalls are a fundamental tool for managing and protecting computer networks. They not only permit specifying which packets are allowed to enter a network, but also how these packets are modified by translating IP addresses and performing port redirection (NAT). Many firewalls systems are available which provide different tools and configuration languages. In contrast with the intuition, the most widespread languages cannot express the same configurations, even when simple filtering and NAT transformations are considered. This paper formally investigates the power of firewall languages of the most used tools in Unix and Linux. In particular, we introduce two kinds of expressivity. The first concerns the ways a packet can be transformed by NAT. According to this criterion iptables is strictly more expressive than ipfw and pf that are equivalent. The second kind is more finer-grained and considers the dependencies among the management of all packets. Our results show that some configurations are expressible in a system, but not in another one. Indeed, iptables is incomparable with the others, and ipfw is more expressive than pf.