Memory-Efficient Algorithms For Deep Packet Inspection

Deep packet inspection plays an important role in network monitoring. For the description of rules, regular expressions are of great power of expression and flexibility. Finite state machines (FSM) provide a good theoretical support for multiple regular expressions matching, but a lot of storage space is necessary. Therefore, storage compression for finite state machines is mainly researched in this thesis.For nondeterministic finite automata (NFA), the algorithm for constructing NFA through extension-mode is presented, and some methods to optimize the speed of constructing NFA and the memory usage are proposed. The experimental results show that the NFA reduce space requirements by about 27% while not decreasing performance of processing.For deterministic finite automata (DFA), on the one hand, a new hybrid FSM construction method for compressing the states of DFA is proposed. DFAs are built in different ways for the regular expressions with distinct complexities by analyzing the states of converting the regular expressions to the DFAs. This leads to the states amount of the DFA construction from quadratic/exponential to linear. On the other hand, an efficient compressing algorithm, called weighted delayed input DFA (WD2FA), for state transitions of the DFA is proposed. It can reach a reduction rate of about 95% for the regular expressions with any complexity.