MDC-DFA: A multi-dimensional cube deterministic finite automata-based feature matching algorithm

The regular expression matching algorithm (REM) is widely applied in the deep packet inspection(DPI), which is more flexible and efficient compared with conventional exact matching algorithm. The REM based on the deterministic finite automaton (DFA) is applicable in the high speed networks due to its linear matching speed. However, it faces the problem of the state explosion simultaneously. Therefore, we propose a multi-dimensional cube deterministic finite automata algorithm (MDC-DFA) for anomaly feature matching. The algorithm divides and compresses redundant states by each dimension, and achieves equivalent state transition by constructing dynamic nodes. Theory and simulation results show that, compared with conventional deterministic finite automata algorithm, the algorithm achieves a logarithm-level compression to the number of states and the storage space while maintaining the time complexity.