A Robust Approach for Matching Mixed Casesensitive and Case-insensitive Patterns

As one of the key methods as well as a bottleneck for Network Intrusion Detection Systems (NIDSes) to detect and eliminate malicious traffic, pattern matching is increasingly gaining popularity while also faces threats from hackers\´ overloading attempts. The support of mixed case-sensitive and case-insensitive patterns, which is essential for NIDSes to detect possible attacks targeting different applications and operating systems, is currently a potential vulnerability since the widely used Convert-Search-Verify (CSV) approach encounters severe performance degradation in the worst-case scenarios. This paper firstly gives a thorough analysis on the reasons causing jams in the worst case, and then boosts up the performance by leveraging a novel mechanism named Convert-Search-incrementally-Verify (CSiV). CSiV differs from CSV in that it first merges possible case-sensitive matches to suspicious segments in the "Search" phase, and then leverages an Aho-Corasick like algorithm to verify them. The infeasibility of the simple Double Search (DS) approach is also explained by analyzing its low average-case throughput. Extensive experiments based on real pattern sets along with both collected and artificial traffic traces show that, the performance of the proposed approach outperforms the DS approach by a factor of 2 in the ordinary cases, and is better than the CSV approach up to 5 times under the worst-case scenario, indicating both its feasibility and robustness for a worst-case safe NIDS.