Efficient pattern matching algorithm for security and Binary Search Tree (BST) based memory system in Wireless Intrusion Detection System (WIDS)

摘要

Wireless Intrusion Detection System (WIDS) has been introduced for providing enhanced security level in WLANs, owing to the numerous and potentially devastating threats against it. WIDS are software- or hardware-based. The hardware-based approaches focus on memory efficiency in pattern matching. This paper proposes a pattern matching algorithm called All-Ready State Traversal pattern matching algorithm. This algorithm constructs the state traversal machine with 1280 bytes size, and enables users to store large sized string patterns in the pattern database. The state traversal machine facilitates the easy retrieval of these patterns through the path vector. Further, the proposed work also follows a number of basic ASCII characters with 128 bytes size; and designs the memory architecture using Binary Search Tree (BST) structure. The hardware generates the addresses of input strings. State traversal machine and bits split algorithms are used to merge together the common addresses of input strings. The merged addresses are encrypted and decrypted by Blowfish algorithm to allow the valid packets and to discard the invalid packets using WIDS. Thus, the proposed algorithm provides a significant reduction in memory usage than that of Aho-Corasick algorithm.