Modeling Complex Packet Filters with Finite State Automata

Designing an efficient and scalable packet filter for modern computer networks becomes each day more challenging: faster link speeds, the steady increase in the number of encapsulation rules (e.g., tunneling) and the necessity to precisely isolate a given subset of traffic cause filtering expressions to become more complex than in the past. Most of current packet filtering mechanisms cannot deal with those requirements because their optimization algorithms either cannot scale with the increased size of the filtering code, or exploit simple domain-specific optimizations that cannot guarantee to operate properly in case of complex filters. This paper presents pFSA, a new model that transforms packet filters into Finite State Automata and guarantees the optimal number of checks on the packet, also in case of multiple filters composition, hence enabling efficiency and scalability without sacrificing filtering computation time.