Efficient Regular Expression Grouping Algorithm Based on Label Propagation
Xi Chen, Shuqiao Chen, Ming Mao · 2016
Regular expression grouping is the practical way to address the state explosion problem of Deterministic Finite Automaton (DFA).Previous grouping algorithms have poor grouping time, and difficult to meet application needs.In this work, we present an efficient regular expression grouping algorithm based on label propagation.Through the deterministic initial grouping and based on similarity of the propagation process to achieve faster convergence.Experimental results show that.Compared with other algorithms, GBLP algorithm has the minimum total number of states and grouping time for the same number of groups. Introduction.With the increasing network security threats, Deep Packet Inspection (DPI) is becoming more and more important in security application and research.It describes the threats (e.g.spam, virus or anonymous intrusion) by default description of the signatures, to identify the network flows with malicious information in the payload of their packets.Nowadays, regular expressions have gradually become the main description language of DPI signatures owing to its expressiveness and flexibility.Regular expression is usually achieved by Finite Automata (FA).The Deterministic Finite Automata (DFA) with its linear and predictable matching speed becomes the research hotspot.However, the DFA may require a huge amount of memory become of the state explosion problem.The number of DFA states can be exponential in size of regular expression as shown in Fig. 1.So many algorithms for the DFA storage optimization have been proposed.