시그내쳐 기반의 네트워크 침입 방지에서 고속의 패킷 필터링을 위한 시스템 구조

김대영(Dae Young Kim),김선일(Sun Il Kim),이준용(Jun Yong Lee) 한국정보과학회 2007 정보과학회논문지 : 시스템 및 이론 Vol.34 No.1·2

네트워크 침입 방지에서 공격 패킷은 시그내쳐에 기반을 둔 방법에 의해 발견되어 제거된다. 패턴 매칭(Pattern Matching)은 공격 시그내쳐를 발견하기 위해 광범위하게 사용되고 있고, 또한 네트워크 침입방지 시스템에서 시간적으로 가장 많이 수행되는 부분이다. 네트워크 침입방지 시스템에 사용되는 패턴 매칭은 주로 하드웨어를 사용하여 가속화되며 회선 속도로 수행되어야 한다. 그러나 이것만으로는 충분치 않고 다음과 같은 조건들이 더 요구된다. 첫째, 패턴 매칭 하드웨어는 패턴 인덱스 번호와 패턴 발견 위치를 포함한 충분한 패턴 매칭 정보를 회선 속도에 맞게 제공해야 한다. 둘째, 불필요한 패턴 매칭을 줄이기 위한 패턴 그룹을 지원할 수 있어야 한다. 셋째, 패턴의 개수가 증가하더라도 최저 성능을 보장 할 수 있어야 한다. 마지막으로, 수행 중단 없이 몇분 또는 몇초 이내에 패턴 업데이트가 가능해야 한다. 본 논문에서는 위의 요구사항을 만족하는 시스템 구조를 제안한다. 이 시스템은 여러 개의 패턴 문자를 동시에 처리하고 파이프라인 구조를 사용하여 고속의 처리를 가능케 한다. Xilinx FPGA 시뮬레이션을 통해 제안된 시스템이 10Gbps 이상의 속도에서 동작하며 위의 모든 요구사항을 만족시킴을 보였다. In network intrusion prevention, attack packets are detected and filtered out based on their attack signatures. Pattern matching is extensively used to find attack signatures and the most time-consuming execution part of Network Intrusion Prevention Systems(NIPS). Pattern matching is usually accelerated by hardware and should be performed at wire speed in NIPS. However, that alone is not good enough. First, pattern matching hardware should be able to generate sufficient pattern match information including the pattern index number and the location of the match found at wire speed. Second, it should support pattern grouping to reduce unnecessary pattern matches. Third, it should always have a constant worst-case performance even if the number of patterns is increased. Finally it should be able to update patterns in a few minutes or seconds without stopping its operations, We propose a system architecture to meet the above requirement. The system architecture can process multiple pattern characters in parallel and employs a pipeline architecture to achieve high speed. Using Xilinx FPGA simulation, we show that the new system scales well to achieve a high speed over 10Gbps and satisfies all of the above requirements.

네트워크 침입방지 시스템을 위한 고속 패턴 매칭 가속 시스템

김선일,Kim Sunil 한국정보처리학회 2005 정보처리학회논문지 A Vol.12 No.2

패턴 매칭(Pattern Matching)은 네트워크 침입방지 시스템에서 가장 중요한 부분의 하나며 많은 연산을 필요로 한다. 날로 증가되는 많은 수의 공격 패턴을 다루기 위해, 네트워크 침입방지 시스템에서는 회선 속도로 들어오는 패킷을 처리 할 수 있는 다중 패턴 매칭 방법이 필수적이다. 본 논문에서는 현재 많이 사용되고있는 네트워크 침입방지 및 탐지 시스템인 Snort와 이것의 패턴 매칭 특성을 분석한다. 침입방지 시스템을 위한 패턴 매칭 방법은 다양한 길이를 갖는 많은 수의 패턴과 대소문자 구분 없는 패턴 매칭을 효과적으로 다룰 수 있어야 한다. 또한 여러 개의 입력 문자들을 동시에 처리 할 수 있어야 한다. 본 논문에서 Shift-OR 패턴 매칭 알고리즘에 기반을 둔 다중 패턴 매칭 하드웨어 가속기를 제시하고 여러 가지 가정 하에서 성능 측정을 하였다. 성능 측정에 따르면 제시된 하드웨어 가속기는 현재 Snort에서 사용되는 가장 빠른 소프트웨어 다중 패턴 매칭 보다 80배 이상 빠를 수 있다. Pattern matching is one of critical parts of Network Intrusion Prevention Systems (NIPS) and computationally intensive. To handle a large number of attack signature fattens increasing everyday, a network intrusion prevention system requires a multi pattern matching method that can meet the line speed of packet transfer. In this paper, we analyze Snort, a widely used open source network intrusion prevention/detection system, and its pattern matching characteristics. A multi pattern matching method for NIPS should efficiently handle a large number of patterns with a wide range of pattern lengths and case insensitive patterns matches. It should also be able to process multiple input characters in parallel. We propose a multi pattern matching hardware accelerator based on Shift-OR pattern matching algorithm. We evaluate the performance of the pattern matching accelerator under various assumptions. The performance evaluation shows that the pattern matching accelerator can be more than 80 times faster than the fastest software multi-pattern matching method used in Snort.

정규 표현식을 이용한 패턴 매칭 엔진 개발

고광만(Kwang-Man Ko),박홍진(Hong-Jin Park) 한국콘텐츠학회 2008 한국콘텐츠학회논문지 Vol.8 No.2

스트링 패턴 매칭 알고리즘은 특정 검색어, 키워드를 검색하는 속도에서는 우수성이 다양한 방법으로 입증되었지만 다양한 패턴에 대해서는 기존의 알고리즘으로는 한계를 가지고 있다. 본 논문에서는 정규표현식을 이용하여 특정 키워드를 포함하여 다양한 패턴의 검색어에 대해서도 효율적인 패턴 매칭을 수행하여 패턴 검색의 효율을 높이고자 한다. 이러한 연구는 기존의 단순한 키워드 매칭에 비해 각종 유해한 스트링 패턴을 효과적으로 검색할 수 있으며 스트링 패턴 매칭 속도에서도 기존의 알고리즘에 비해 우수성을 갖는다. 본 연구에서 제안한 LEX로부터 생성된 스트링 검색 엔진은 패턴 검색 속도에 대한 실험에서 패턴의 수가 1000개 이상인 경우에서는 BM&AC 알고리즘보다 효율적이지만 키워드 검색에서는 유사한 결과를 얻었다. In various manners, string pattern matching algorithm has been proven for prominence in speed of searching particular queries and keywords. Whereas, the existing algorithms are limited in terms of various pattern. In this paper, regular expression has been utilized to improve efficiency of pattern matching through efficient execution towards various pattern of queries including particular keywords. Such as this research would enable to search various harmful string pattern more efficiently, rather than matching simple keywords, which also implies excellent speed of string pattern matching compared to that of those existing algorism. In this research, the proposed string search engine generated from the LEX are more efficient than BM & AC algorithm for a string patterns search speed in cases of 1000 with more than patterns, but we have got similar results for the keywords pattern matching.

은닉 마코프 모델을 이용한 시계열 데이터의 의미기반 패턴 매칭

조영희(Young-Hee Cho),전진호(Jin-Ho Jeon),이계성(Gye-Sung Lee) 한국콘텐츠학회 2008 한국콘텐츠학회논문지 Vol.8 No.5

시계열 데이터에서 패턴을 찾고 검색하는 문제는 여러 분야에서 오랫동안 관심을 가지고 연구되어 왔다. 본 논문은 시간의 흐름에 따라 값의 변화를 나타내는 시계열 형태의 주식 데이터에 적용할 수 있는 새로운 패턴 매칭 방법을 제안한다. 우선, 의미를 기반으로 패턴을 정의하고 정의된 패턴에 일치하는 데이터들을 추출하여 학습모델을 작성한다. 그리고 새로운 질의 시퀀스가 어떤 종류의 패턴과 일치하는가는 각 학습 모델과의 유사도를 측정하여 결정하게 된다. 학습 모델은 시계열을 잘 설명하는 것으로 알려진 은닉 마코프 모델을 사용하여 작성하였다. 실험 결과 은닉 마코프 모델의 특성을 사용하여 생성된 각 학습 모델은 주어진 의미를 잘 나타내는 패턴을 생성하였으며, 새로운 시퀀스가 주어졌을 때 일치하는 패턴에 따라서 시퀀스가 가진 의미를 파악할 수 있었다. Pattern matching and pattern searching in time series data have been active issues in a number of disciplines. This paper suggests a novel pattern matching technology which can be used in the field of stock market analysis as well as in forecasting stock market trend. First, we define conceptual patterns, and extract data forming each pattern from given time series, and then generate learning model using Hidden Markov Model. The results show that the context-based pattern matching makes the matching more accountable and the method would be effectively used in real world applications. This is because the pattern for new data sequence carries not only the matching itself but also a given context in which the data implies.

순위다중패턴매칭문제에 대한 공간효율적인 해싱기반 알고리즘

박정훈(Jeonghoon Park),김영호(Youngho Kim),심정섭(Jeong Seop Sim) 한국정보과학회 2018 정보과학회 컴퓨팅의 실제 논문지 Vol.24 No.8

길이가 같은 두 문자열 x, y가 주어졌을 때, x와 y의 문자들의 순위가 모두 일치하면 x와 y는 순위동형이라 한다. 순위다중패턴매칭문제는 텍스트 T와 k개의 패턴들로 구성된 패턴집합 P이 주어질때, P에 속한 패턴과 순위동형을 이루는 T의 모든 부분문자열을 찾는 문제이다. 본 논문에서는 q-그램의 크기를 q라 하고 패턴들의 길이의 총합을 M이라 할 때, 기존의 순위다중패턴매칭문제를 해결하는 해싱기반 알고리즘을 개선하여 공간복잡도를 O(q!+k+M)에서 O(k+M)으로 줄인 알고리즘을 제시한다. Given two strings x and y of the same length, when all ranks of characters in x and y are the same, x is order-isomorphic to y. Given a text T and a pattern set P consisting of k patterns, order-preserving multiple pattern matching problem is to find all substrings in T that are order-isomorphic to any pattern in P. In this paper, when the size of a q-gram is q and the sum of lengths of patterns is M, we propose a space-efficient hashing-based algorithm for order-preserving multiple pattern matching problem to reduce space complexity from O(q!+k+M) to O(k+M).

패턴 영상을 이용한 측정 데이터의 결합

조택동,이호영,양상민 한국기계기술학회 2003 한국기계기술학회지 Vol.5 No.1

이진인코딩을 이용한 순위다중패턴매칭 알고리즘

공준호,김영호,심정섭 한국차세대컴퓨팅학회 2022 한국차세대컴퓨팅학회 논문지 Vol.18 No.6

Given a text and a set of patterns , the order-preserving multiple pattern matching problem is to find all substrings of that are order-isomorphic to any pattern in . An -time algorithm using -grams and factorial number system for the problem was proposed where is the length of the shortest pattern, is the length of the longest pattern, and is the sum of lengths of all patterns in , respectively. In this paper, we propose an -time algorithm using fingerprints of binary-encoded texts. We also present a parallel implementation performing the search process in time. Experimental results show that as grows, our algorithm becomes slower than the previous algorithm, but uses less space. The proposed parallel implementation is similar in execution time to the previous algorithm and is more space-efficient. 순위다중패턴매칭문제는 길이가 인 텍스트 와 패턴들의 집합 가 주어졌을 때, 에 속한 패턴들과 순위동형인 의 모든 부분문자열들을 찾는 문제이다. 개의 연속적인 문자인 -그램, 에서 가장 짧은 패턴의 길이를 , 가장 긴 패턴의 길이를 , 모든 패턴들의 길이의 합을 이라 할 때, -그램과 계승수체계를 이용하여 시간에 순위다중패턴매칭문제를 해결하는 알고리즘이 제시되었다. 본 논문에서는 이진인코딩된 텍스트의 핑거프린트를 이용하여 시간에 순위다중패턴매칭문제를 해결하는 알고리즘을 제시한다. 또한, 시간에 탐색 과정을 수행하는 병렬 구현 방법을 제시한다. 실험 결과, 가 커질수록 제시한 알고리즘의 기존 알고리즘보다 수행시간이 느려지지만 공간사용량은 적어졌다. 제시한 병렬 구현 방법은 기존 알고리즘보다 공간효율적이면서 수행시간은 유사하다.

DFA 패턴 매칭을 위한 코드 최적화기의 자동적 생성

윤성림,오세만,Yun, Sung-Lim,Oh, Se-Man 한국정보처리학회 2007 정보처리학회논문지 A Vol.14 No.1

주어진 입력 프로그램과 의미적으로 동등하면서 좀 더 효율적인 코드로 바꾸는 것을 코드 최적화라 하며, 이런 과정은 코드 최적화기예 의해 수행된다. 본 논문에서는 코드 최적화기를 자동적으로 생성하는 도구인 코트 최적화긴 생성기를 설계하고 구현하였다. 즉 패턴 형식에 대한 표현을 입력으로 받아 기술된 형태의 최적화 코드를 찾아내는 DFA 패턴 매칭을 위한 코드 최적화기를 자동적으로 생성하는 것이다. DFA 패턴 매칭은 패턴들의 정규화 과정을 통해 패턴 검색 시 발생하는 중복 비교를 제거하여, 패턴 형태의 단순화 및 구조를 개선함으로 비용이 적게든다. DFA 패턴 매칭을 위한 코드 최적화기의 자동적 생성은 다양한 형태의 중간코드로 바뀌더라도 해당하는 코트 최적화기를 만들어야 하는 수고를 덜어줌으로써 코드 최적화에 대한 정형화(formalism)를 할 수 있다. 또한, DFA로 구성되어 최적화를 하기 때문에 최적화 속도가 빠르고, 코드 최적화기를 만드는데 필요한 시간과 비용을 절약할 수 있는 장점을 가진다. Code Optimization is converting to a code that is equivalent to given program but more efficient, and this process is processed in Code Optimizer. This paper designed and processed Code Optimizer Generator that automatically generates Code Optimizer. In other words Code Optimizer is automatically generated for DFA Pattern Matching which finds the optimal code for the incoming pattern description. DFA Pattern Matching removes redundancy comparisons that occur when patterns are sought for through normalization process and improves simplification and structure of pattern shapes for low cost. Automatic generation of Code Optimization for DFA Pattern Matching eliminates extra effort to generate Code Optimizer every time the code undergoes various transformations, and enables formalism of Code Optimization. Also, the advantage of making DFA for optimization is that it is faster and saves cost of Code Optimizer Generator.

FPGA 기반 네트워크 침입탐지 시스템 하드웨어 설계 및 구현

김택훈(Taek-Hun Kim),윤상균(Sang-Kyun Yun) 한국컴퓨터정보학회 2012 韓國컴퓨터情報學會論文誌 Vol.17 No.4

침입 탐지에 가장 시간이 많이 소요되는 작업은 패킷 데이터에 침입 패턴이 있는지를 검사하는 심층 패킷검사이다. 고속 네트워크에서 이 작업을 실시간으로 처리하기 위해서는 하드웨어 기반 패턴매칭이 필요하다. 본 논문에서는 침입탐지 시스템 구현에 하드웨어 기반 패턴매칭을 사용할 수 있도록 네트워크의 패킷을 수집하여 Snort 패턴규칙에 따라서 패턴매칭을 수행하고 결과를 소프트웨어에게 제공할 수 있도록 하는 하드웨어를 Virtex-6 FPGA를 사용하여 Microblaze 기반의 SoC 형태로 설계하여 구현하였다. 구현된 시스템은 인위적인 트래픽 생성과 실제 트래픽을 사용하여 동작을 검증하였고 패킷이 네트워크 인터페이스에서 메모리로 복사되는 동안 패턴매칭 동작을 정확하게 수행하여 소프트웨어에게 결과를 제공하였다. 본 연구 결과는 실시간 처리가 가능하도록 침입탐지 시스템을 고속화 하기위한 하드웨어로 사용될 수 있다. Deep packet inspection which perform pattern matching to search for malicious patterns in the packet is most computationally intensive task. Hardware-based pattern matching is required for real-time packet inspection in high-speed network. In this paper, we have designed and implemented network intrusion detection hardware as a Microblaze-based SoC using Virtex-6 FPGA, which capture the network input packet, perform hardware-based pattern matching for patterns in the Snort rule, and provide the matching result to the software. We verify the operation of the implemented system using traffic generator and real network traffic. The implemented hardware can be used in network intrusion detection system operated in wire-speed.

PCB 패턴 검출을 위한 FPGA 기반 패턴 매칭 시스템 구현

정광성(Kwang Sung Jung),문철홍(Cheol Hong Moon) 한국전자통신학회 2016 한국전자통신학회 논문지 Vol.11 No.5

본 논문에서는 PCB(: Printed Circuit Board) 패턴 검출을 위하여 Camera Link(Medium)을 지원하는 FPGA 기반 패턴 매칭 시스템을 구현하였다. 최근 생산되고 있는 PCB 패턴은 고집적화 시스템을 위해 점점 미세해지고 복잡해지고 있다. PCB 생산 공정의 비전 자동화를 위하여 고속 처리가 가능한 FPGA 기반 시스템을 제작하였고, 패턴 검출을 위해 사용되는 비전 라이브러리를 IP(: Intellectual property)로 구현하였다. 구현한 IP는 Camera Link IP, 패턴 매칭 IP, VGA IP, 에지 검출 IP, 메모리 IP이다. This study materialized an FPGA-based system to extract PCB patterns. The Printed Circuit Boards that are produced these days are becoming more detailed and complex. Therefore, the importance of a vision system to extract defects of detailed patterns is increasing. This study produced an FPGA-based system that has high speed handling for vision automation of the PCB production process. A vision library that is used to extract defect patterns was also materialized in IPs to optimize the system. The IPs materialized are Camera Link IP, pattern matching IP, VGA IP, edge extraction IP, and memory IP.