네트워크 보안을 위한 강력한 문자열 매칭 알고리즘
Robust Quick String Matching Algorithm for Network Security
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
String matching is one of the key algorithms in network security and many areas could be benefit from a faster string matching algorithm. Based on the most efficient string matching algorithm in sual applications, the Boyer-Moore (BM) algorithm, a novel algorithm called RQS is proposed. RQS utilizes an improved bad character heuristic to achieve bigger shift value area and an enhanced good suffix heuristic to dramatically improve the worst case performance. The two heuristics combined with a novel determinant condition to switch between them enable RQS achieve a higher performance than BM both under normal and worst case situation. The experimental results reveal that RQS appears efficient than BM many times in worst case, and the longer the pattern, the bigger the performance improvement. The performance of RQS is 7.57~36.34% higher than BM in English text searching, 16.26~26.18% higher than BM in uniformly random text searching, and 9.77%higher than BM in the real world Snort pattern set searching.
Abstract
String matching is one of the key algorithms in network security and many areas could be benefit from a faster string matching algorithm. Based on the most efficient string matching algorithm in sual applications, the Boyer-Moore (BM) algorithm, a novel algorithm called RQS is proposed. RQS utilizes an improved bad character heuristic to achieve bigger shift value area and an enhanced good suffix heuristic to dramatically improve the worst case performance. The two heuristics combined with a novel determinant condition to switch between them enable RQS achieve a higher performance than BM both under normal and worst case situation. The experimental results reveal that RQS appears efficient than BM many times in worst case, and the longer the pattern, the bigger the performance improvement. The performance of RQS is 7.57~36.34% higher than BM in English text searching, 16.26~26.18% higher than BM in uniformly random text searching, and 9.77%higher than BM in the real world Snort pattern set searching.
참고문헌 (12)
- M. Norton, "The new Snort", Computer security journal, 19(3), pp.37~47 (2003)
- M. Roesch, "Snort: lightweight intrusion detection for networks", Proc. 13th System Administration Conference and Exhibition (LISA’1999), pp.229~238 (1999)
- R. Boyer, "A fast string searching algorithm", Communications of the ACM, 20(10), pp.762~772 (1977)
- E. P. Markatos, "EXB : Exclusion-based signature matching for intrusion detection", Proc. The CCN’02 (2002)
- K. G. Anagnostakis, "E2XB: A domain-specific string matching algorithm for intrusion detection", Proc. 18th IFIP International Information Security Conference (SEC2003) (2003)
- Fast content-based packet handling for intrusion detection, "M. Fisk", UCSD, ~, pp.Technical Report CS2001-0670 (2001)
- 정수목, "동영상의 블록내 지역성을 이용하는 효율적인 다단계 연속 제거알고리즘", (사)디지털산업정보학회 논문지, 5(4), pp.179~187 (2009), (사)디지털산업정보학회
- S. Antonatos, "Generating realistic workloads for network intrusion detection systems", Software engineering notes, 29(1), pp.207~215 (2004)
- R. N. Horspool, "Practical fast searching in strings", Software practice and experience, 10(6), pp.501~506 (1980)
- R. M. Karp, "Efficient randomized pattern-matching algorithms", IBM J. Res. Dev, 31(2), pp.249~260 (1987)
- D. Knuth, "Fast pattern matching in strings", SIAM journal on computing, 6(2), pp.323~350 (1977)
- 구윤모, "잡음 영상에서의 에지 검출", (사)디지털산업정보학회 논문지, 8(3), pp.41~48 (2012), (사)디지털산업정보학회