시그니처 해싱 알고리즘[9]은 해시 테이블을 사용하여 네트워크 침입방지시스템(Intrusion Prevention System)을 위한 빠른 패턴 매칭 속도를 제공한다. 시그니처 해싱 알고리즘은 모든 규칙에서 2 바이트를 선택하여 해쉬 값을 구한 후 해쉬 테이블에 링크시킨다. 이렇게 하여 패턴매칭 시에 실제 검사하는 규칙의 개수를 줄임으로써 성능이 향상되는 장점을 가진다. 그러나 규칙의 개수와 상관관계가 증가할 경우 같은 해쉬값을 가지는 규칙의 개수가 증가하여 성능이 떨어지는 단점이 있다. 본 논문에서는 시그니처 해싱 알고리즘의 단점을 보완하기 위해 규칙의 개수와 상관관계에 무관하게 모든 규칙을 해쉬 테이블 상에 고르게 분포시키는 방법을 제안한다. 제안된 방법에서는 해쉬 테이블에 규칙을 링크하기 전에 해당 해쉬 값에 링크된 규칙이 있는지 검사한다. 만약 링크된 규칙이 없으면 해당 해쉬 값에 규칙을 링크하고, 링크된 규칙이 있으면 다른 위치에서 해쉬 값을 다시 계산한다. 제안한 방법은 리눅스커널 모듈 형태로 PC에서 구현하였고, 네트워크 성능 측정 툴인 Iperf를 이용하여 실험하였다. 실험 결과에 의하면 기존 방식에서는 시그니처 개수 및 규칙의 상관관계가 증가함에 따라 성능이 저하되었지만, 본 논문에서 제안한 방식은 시그니처 개수와 규칙의 상관관계에 무관하게 일정한 성능을 유지하였다
The signature hashing algorithm[9] provides the fast pattern matching speed for network IPS(Intrusion Prevention System) using the hash table. It selects 2 bytes from all signature rules and links to the hash table by the hash value. It has an advantage of performance improvement because it reduces the number of inspecting rules in the pattern matching. However it has a disadvantage of performance drop if the number of rules with the same hash value increases when the number of rules are large and the corelation among rules is strong. In this paper, we propose a method to make all rules distributed evenly to the hash table independent of the number of rules and corelation among rules for overcoming the disadvantage of the signature hashing algorithm. In the proposed method, it checks whether or not there is an already assigned rule linked to the same hash value before a new rule is linked to a hash value in the hash table. If there is no assigned rule, the new rule is linked to the hash value. Otherwise, the proposed method recalculate a hash value to put it in other position. We implemented the proposed method in a PC with a Linux module and performed experiments using Iperf as a network performance measurement tool. The signature hashing method shows performance drop if the number of rules with the same hash value increases when the number of rules are large and the corelation among rules is strong, but the proposed method shows no performance drop independent of the number of rules and corelation among rules.
