Research On Exact Single Pattern Matching Algorithm In Netfilter/iptables Firewall

With the development of computer and network technology, the network become more and more important in people's life, at the same time, the number of network uesrs is exploding. But because of the network is complexity and openness, on the one hand people enjoy the convenience of their lives on the Internet, on the other hand, network security is also being tested as never before, network security issues also plagued the people. How to avoid the occurrence of network security incidents, has become an important issue to maintain a safe and harmonious network enviroment, firewall plays a very important role in this situation. In firewall of most nowadays network using attacking feature to detect attacks.First, the system extract feture from attacks and build feture library, then use pattern-matching to match the feture.In these system, pattern-matching is very important.This paper studied both Linux's Netfilter/iptables firewall system and string pattern matching in this firewall, and the efficiency were analyzed. After that, an optimization method is presented to the pattern macthing module.In the new method, patterns will be preprocessed in the userspace's iptables but not kernel's Netfilter. According to the results of test on the openwrt router, when dealing with a large matching rules and/or a busy network, the new module has a high efficiency than original matching module. In the latest Netfilter/iptables firewall there only two pattern matching algorithm. So this paper studies the macthing include KMP matching algorithm that based on prefix search, and the HORSPOOL algorithm that based on suffix search, the algorithm HORSPOOL is a improved algorithm of BM. After this paper proposed a new pattern macthing algorithm IKMPH that based on the KMP and HORSPOOL, new algorithm IKMPH combines the KMP's partial table and the HORSPOOL's bad word table. In the contrast with KMP, BM and HORSOPOOL, the efficiency of the new algorithm IKMPH and IKMPHS are higher than the other four algorithms compared in the most cases. Finally, we ported the new algorithm IKMPH and IKMPHS to the Netfilter/iptables firewall and contrast with the BM and KMP algorithm. It's found that the efficiency of the firewall that use the IKMPH and/or IKMPHS algorithm is higher than the other two matching algorithm.