Consistency Verification of Stateful Firewalls is not Harder than the Stateless Case

Abstract

Firewalls play an important role in the enforcement of access control policies in contemporary networks. However, firewalls are effective only if they are configured correctly such that their access control rules are consistent and the firewall indeed implements the intended access control policy. Unfortunately, due to the potentially large number of rules and their complex relationships with each other, the task of firewall configuration is notoriously error-prone, and in practice, firewalls are often misconfigured leaving security holes in the protection system. In this paper, we address the problem of consistency verification of stateful firewalls that keep track of already existing connections. For the first sight, the consistency verification of stateful firewalls appears to be harder than that of stateless firewalls. We show that, in fact, this is not the case: consistency verification of stateful firewalls can be reduced to the stateless case, and hence, they have the same complexity. We also report on our prototype implemetation of an automated consistency verification tool that can handle stateful firewalls.