Improving the Efficiency of Misuse Detection by Means of the q-gram Distance

Misuse detection-based intrusion detection systems (IDS) perform search through a database of attack signatures in order to detect whether any of them are present in incoming traffic. For such testing, fault-tolerant distance measures are needed. One of the appropriate distance measures of this kind is constrained edit distance, but the time complexity of its computation is too high. We propose a two-phase indexless search procedure for application in misuse detection-based IDS that makes use of q-gram distance instead of the constrained edit distance. We study how well q-gram distance approximates edit distance with special constraints needed in IDS applications. We compare the performances of the search procedure with the two distances applied in it. Experimental results show that the procedure with the q-gram distance implemented achieves for higher values of q almost the same accuracy as the one with the constrained edit distance implemented, but the efficiency of the procedure that implements the q-gram distance is much better.