Research and Implementation of a DFA Compression Algorithm with No Matching Time Loss

Start-of-the-art deep packet inspection system uses deterministic finite automata (DFA) algorithms to perform regular expression matching. Nevertheless, the storage consumption problem caused by DFA make it difficult to apply to FPGA with scarce on-chip resources. At present, there are many algorithms aiming at solving the space explosion problem of DFA, but it affects the detection speed of the system to some extent while bringing better compression ratio. In this paper, a DFA compression algorithm without matching time loss is proposed. Based on the hardware platform of FPGA, a single DFA matching engine is designed and implemented. Experimental results show that the algorithm can achieve a compression rate of 10% to 30% without affecting the matching performance of the whole system. © 2020, Chinese Institute of Electronics. All right reserved.