FPGA-based satisfiability filters for deep packet inspection

Satisfiability (SAT) filters have been recently proposed as a fast and storage-efficient way of implementing set membership operations. In this paper we discuss the application of the random SAT filters with k hash functions (k-SAT filters), for detecting the potential presence of known malicious signatures (byte patterns) in packet payloads to prevent cyber attacks. We developed and verified the operation of a FPGA-based 3-SAT filter with 3 hash functions per signature. The hash functions are implemented with bit stream processing circuits using the CRC-32 polynomial. The 3-SAT filter with 1,024 variables has a single-instance architecture with 64 solutions for a set of 3,360 input test patterns extracted from the content fields of the known malicious signatures in the Snort intrusion detection system database. During a filter construction phase, the 64 'good' solutions with the maximum Hamming distance between them have been selected among the 8,000 solutions found by a SAT solver. A Digilent Arty A7 with an Artix-7 FPGA was used to implement the filter design. The complete FPGA filter system operates at a 200 MHz clock rate and uses 720 Kbit of BRAM, 17,606 LUTs, and 20,296 flip-flops. The experimentally observed false positive rate for 50,000 randomly-generated signatures of different lengths was ∼1.6%. The 3-SAT FPGA design can be used to work with any set of signatures of interest with no need for changing and re-synthesizing VHDL code and reprogramming the entire FPGA. The results of this project allow for better understanding and planning of our next steps in the work on k-SAT filter applications for deep packet inspection.