Building Dependable Intrusion Prevention Systems

Intrusion prevention systems (IPSs) have become widely recognized as a powerful tool and an important element of IT security safeguards. Essential to every network intrusion prevention system is the ability to search through packets and identify patterns that match known attacks. Resource- and time-efficient string matching algorithms are therefore important for identifying these packets at the line rate. Recently these systems have become a target of attacks - the example is the infamous Witty worm. The devices which use algorithms with low worst-case performance could be a target of algorithmic complexity attacks. For example, poorly prepared hash tables can degenerate to linked lists with carefully chosen input. An attacker can effectively compute an input data that will diminish the device throughput. This can lead to denial of service attacks, which are very dangerous for networks and computational environments. In this article new hardware implementation architecture of the Karp-Rabin algorithm was introduced. The result is a software, which generates a pattern matching module that could be easily used to create intrusion prevention systems implemented in reconfigurable hardware. The prepared module matches the subset of the Snort IPS signatures achieving throughput of over 2 Gbps and have the worst-case performance similar to the best-case one. This means that the presented implementation architecture is immune to algorithmic complexity attacks