1. 3

We propose a packet filtering technique based on the generation and composition of Finite-State Automata (FSA), in contrast to most traditional imperative approaches. FSAs provide a formal framework with well-defined composition operations and enable the generation of optimized executable code without resorting to multiple and opportunistic optimization algorithms. Memory safety in filters is enforced with minimal run-time overhead and termination can be proved without restricting filter control flow graphs to be acyclic, thus enabling full parsing of complex protocol formats and multiple encapsulation layers. Experimental evidence shows that this approach is viable and improves the state of the art in terms of filter performance and scalability without incurring in the most common FSA deficiencies, such as state space explosion.