Algorithmic Complexity Attacks Against WuManber

Pattern matching is one of the fundamental problems in computer science. It is the key problem of many important scopes such as network information security, information retrieval and filtration, computational biology, etc. A great number of security problems have arisen with the wide application of pattern matching, especially in network information security systems, such as intrusion detection and prevention systems, anti-virus systems, anti-spam systems, firewall, etc. A method of algorithmic complexity attacks against WuManber which is a classical multi-patterrn algorithm, and the optimal solution of creating the attacking data are presented in this article. Compared with random data and the data from network, the attacking data can greatly reduce the searching speed of WuManber. Experiments on random data sets show that the larger character set, the better attacking performance. And experiments on the data from the network show that the attacking data can reduce WuManber searching speed by more than 50%. It is found that if a small part of the pattern set is known, the attack data can be created. Defensively speaking, it is important that the pattern set must be kept secret. This article also provides some strategies of improving the security of network information security systems. The attacking data can also be used in checking the system security.