고성능 네트워크 침입방지시스템을 위한 개선된 시그니처 해싱 알고리즘
An Improved Signature Hashing Algorithm for High Performance Network Intrusion Prevention System
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
시그니처 해싱 알고리즘[9]은 해시 테이블을 사용하여 네트워크 침입방지시스템(Intrusion Prevention System)을 위한 빠른 패턴 매칭 속도를 제공한다. 시그니처 해싱 알고리즘은 모든 규칙에서 2 바이트를 선택하여 해쉬 값을 구한 후 해쉬 테이블에 링크시킨다. 이렇게 하여 패턴 매칭 시에 실제 검사하는 규칙의 개수를 줄임으로써 성능이 향상되는 장점을 가진다. 그러나 규칙의 개수와 상관관계가 증가할 경우 같은 해쉬 값을 가지는 규칙의 개수가 증가하여 성능이 떨어지는 단점이 있다. 본 논문에서는 시그니처 해싱 알고리즘의 단점을 보완하기 위해 규칙의 개수와 상관관계에 무관하게 모든 규칙을 해쉬 테이블 상에 고르게 분포시키는 방법을 제안한다. 제안된 방법에서는 해쉬 테이블에 규칙을 링크하기 전에 해당 해쉬 값에 링크된 규칙이 있는지 검사한다. 만약 링크된 규칙이 없으면 해당 해쉬 값에 규칙을 링크하고, 링크된 규칙이 있으면 다른 위치에서 해쉬 값을 다시 계산한다. 제안한 방법은 리눅스 커널 모듈 형태로 PC에서 구현하였고, 네트워크 성능 측정 툴인 Iperf를 이용하여 실험하였다. 실험 결과에 의하면 기존 방식에서는 시그니처 개수 및 규칙의 상관관계가 증가함에 따라 성능이 저하되었지만, 본 논문에서 제안한 방식은 시그니처 개수와 규칙의 상관관계에 무관하게 일정한 성능을 유지하였다
Abstract
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.
참고문헌 (16)
- 정보흠, "침입방지시스템 기술 현황 및 전망", 주간기술동향, 통권 : 1098 (2003)
- X. Zhang, "Intrusion Prevention System Design", Proceedings of the Fourth International Conference on Computer and Information Technology (2004)
- Knuth DE, "Fast pattern matching in strings", SIAM Journal of Computing (1977)
- Boyer RS, "A Fast String Searching Algorithm", Communications of the ACM (1977)
- A fast algorithm for multi-pattern searching. in: Department of Computer Science, "S.Wu", University of Arizona, ~, pp.Technical Report TR-94-17 (1994)
- A. Aho, "Efficient string matching: an aid to biliographic search", Comm. ACM, 18, pp.333~340 (1975)
- 전용희, "침입방지시스템(IPS)의 기술 분석 및 성능평가 방안", 정보보호학회지, 15(2) (2005)
- 왕정석, "시그너처 해싱 기반 고성능 침입방지 알고리즘 설계 및 구현", 정보처리학회논문지C, 14(3), pp.209~220 (2007), 한국정보처리학회
- Christoph M. Hoffmann, "Pattern Matching in Trees", Journalo f the Assoclallonf or ComputingM achinery, 29(I) (1982)
- S. Dharmapurikar, "Deep Packet Inspection Using Parallel Bloom Filters", The International Symposium on High Performance Interconnects (HotI), (2003)
- J. Lockwood, "Fast and Scalable Pattern Matching for Content Filtering", Architectures for Networking and Communication System(ANCS) (2005)
- Sarang Dharmapurikar, "Fast and Scalable Pattern Matching for Network Intrusion Detection Systems", IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 24(10) (2006)
- Ristic, "Apache Security", & Associates
- 고중식, "규칙과 페이로드에 따른 Snort의 성능 분석", 한국정보보호학회 춘계학술대회, pp.325~328 (2008)