Addressing KMP Limits on SQL Injection Detection with Aho-Corasick Algorithm
摘要
Attack detection, particularly in the context of SQL injection attacks, is a critical component of ensuring the security and integrity of information systems. The Knuth-Morris-Pratt (KMP) algorithm is commonly employed for string-matching tasks in attack detection; however, it has notable limitations in efficiency and the identification of complex attack patterns. These limitations can result in increased processing time and a higher likelihood of undetected threats. To address these challenges, this research explores the implementation of the Aho-Corasick (AC) algorithm as a more effective alternative. Unlike the KMP algorithm, the Aho-Corasick algorithm constructs a finite state automaton, facilitating the simultaneous matching of multiple patterns with greater efficiency. Through experimental evaluation, this study demonstrates that the Aho-Corasick algorithm significantly outperforms the KMP algorithm in attack detection, as its theoretical running time of O(m × n) aligns with the actual implementation performance where AC average running time falls between 2.032 × 10−4 to 7.007 × 10−4, compared to average running time of 7.344 × 10−4 on KMP, across all four risk levels. Furthermore, based on the accuracy of detection, AC implementation constantly has 3 × accuracy compared to KMP. The improved efficiency of the Aho-Corasick algorithm reduces computational overhead, making it more suitable for real-time security applications. Therefore, integrating the Aho-Corasick algorithm into attack detection systems enhances both detection accuracy and processing efficiency, ultimately providing a more robust and reliable approach to mitigating cybersecurity threats.