  The security provided by a firewall for a computer network almost completely
depends on the rules it enforces. For over a decade, it has been a well-known
and unsolved problem that the quality of many firewall rule sets is
insufficient. Therefore, there are many tools to analyze them. However, we
found that none of the available tools could handle typical, real-world
iptables rulesets. This is due to the complex chain model used by iptables, but
also to the vast amount of possible match conditions that occur in real-world
firewalls, many of which are not understood by academic and open source tools.
  In this paper, we provide algorithms to transform firewall rulesets. We
reduce the execution model to a simple list model and use ternary logic to
abstract over all unknown match conditions. These transformations enable
existing tools to understand real-world firewall rules, which we demonstrate on
four decently-sized rulesets. %After preparation with our algorithms, tools
could understand them. Using the Isabelle theorem prover, we formally show that
all our algorithms preserve the firewall's filtering behavior.
