[논문]TCAM을 이용한 고성능 패턴 매치 알고리즘

성정식; 강석민; 이영석; 권택근; 김봉태

doi:10.3745/kipstc.2005.12c.4.503

문제 정의

본 논문에서는 네트워크 침입 탐지, 계층 7 스위치, 바이러스 탐지 등의 기술에 이용될 수 있는 네트워크 트래픽의 페이로드를 검색하여 패턴 매치를 지원하는 수기가급의 스캐닝 성능의 고성능 패턴 매치 알고리즘에 관하여 논하였다. 본 논문에서 제안하는 고성능 패턴 매치 알고리즘은 TCAM을 기반으로 하고, 윈도우 크기가 다양하게 변할 수 있는 점핑 윈도우 패턴 매치 기법을 이용하여 패킷의 페이로드당 TCAM 룩업 횟수를 줄여 페이로드 스캐닝 성능을 높였다.
Tenary Contents Addressable Memory(TCAM) 은 하드웨어적으로 병렬 검색을 지원하므로 일반 메모리에 비해 빠른 검색을 수행할 수 있으므로 일반적으로 네트워크 프로세서는 TCAM< 사용하여 IP 룩업 및 포워딩 기능을 지원한다. 본 논문에서는 네트워크 프로세서에서 수 기가비트 급의 네트워크 성능을 보장하면서 모든 페이로드에 대해 DPI를 지원할 수 있는 TCAM을 이용한 고성능 패턴 매치 알고리즘을 제안한다. 모든 페이로드를 조사하면서 고성능을 보장하기 위해서는 TCAM 룩업 횟수를 최대한 줄이는 것이 필요하다.
따라서 수 기가비트 급의 네트워크 인터페이스를 지원하기 위해서는 TCAM을 이용한 보다 빠른 페이로드 검색이 지원되어야 한다. 본 논문에서는 점핑 윈도우 패턴 매치 기법을 사용하여 한 번의 TCAM 룩업으로 페이로드의 다수 바이트를 처리하는 고성능 패턴 매치 알고리즘을 제안한다.
전처리 단계에서 TCAM 엔트리들이 생성되면 스캐닝 단계에서 패킷의 페이로드 T에 일치하는 패턴이 있는지 알아내는 작업을 수행한다. 스캐닝 단계의 알고리즘을 설명하기 위해 <표 2>와 같은 문자 표기를 사용하고, 알고리즘 2는 스캐닝 알고리즘을 나타낸다.

가설 설정

TCAM 룩업 시간을 t, 패킷의 평균 페이로드 길이를 n, 한 패턴의 평균 길이를 I 이라고 가정하자. 슬라이딩 윈도우 패턴 매치 방식의 페이로드 스캐닝 속도는 nt이다.
즉, 패턴이 페이로드내에 존재할 수 있는 모든 위치의 패턴을 TCAM 엔트리로 생성할 경우, 패턴이 페이로드의 임의의 위치에 존재하더라도 점핑 윈도우 방식을 이용하여 패턴 매치를 수행할 수 있다. 페이로드의 길이가 n 바이트인 패킷의 페이로드 T = …, tz 이라 가정하고, 패턴 F = Po, Pi, -, Pm-l 라고 가정하자. 이때 P는 다음과 같은 7의 서브스트링 위치에 존재할 수 있다.

제안 방법

5장의 시뮬레이션에서는 본 논문에서 제안하는 알고리즘이 TCAM에 저장된 시그너처를 입력 패킷에서 제대로 검출해 내는지의 여부와 점핑 윈도우 크기에 따른 TCAM 크기와 각 패킷의 TCAM 룩업 횟수에 대해 알아보았다. 본 논문의 알고리즘을 lOGbps를 지원하는 보안 라우터 등에 이용하기 위해서는 TCAM을 이용하는 라우터 등에 직접 구현하여 그 성능을 평가하는 작업이 필요하다.
Snort 2.1.0에 존재하는 모든 규칙들을 파싱하여 이 중 'content'라는 옵션으로부터 2, 247개의 패턴을 캐치하여 TCAM 엔트리 테이블을 생성하였다. 입력 패킷은 libpcap를 이용하여 수집한 평균 페이로드 길이가 690바이트인 10, 000개의 패킷을 대상으로 하였다.
본 논문에서 제안하는 고성능 패턴 매치 알고리즘은 전처리 단계와 스캐닝 단계로 구성된다. 전처리 단계에서는 일련의 시그너처에서 패턴들을 추출하여 TCAM 엔트리 및 규칙 테이블을 생성한다.
본 논문에서 제안하는 바이트 점핑 윈도우 패턴 매치 방식은 (그림 2)와 같이 페이로드의 모든 m 바이트마다 TCAM 룩업을 수행하여 패턴를 검색해 내는 것이다. 이 때, TCAM 엔트리의 -는 don't care를 나타낸다.
모든 페이로드를 조사하면서 고성능을 보장하기 위해서는 TCAM 룩업 횟수를 최대한 줄이는 것이 필요하다. 본 논문에서 제안하는 알고리즘은 .한 번의 TCAM 룩업으로 페이로드의 다수 바이트를 처리하는 점핑윈도우 패턴 매치 (jumping window pattern matching) 기법을 이용하여 페이로드당 TCAM 룩업 횟수를 줄인다.
본 논문에서 제안하는 알고리즘이 패킷의 페이로드를 올바르게 필터링하는 지 검증하고, Snort 시그너처를 모두 처리했을 때 점핑 윈도우 크기에 따른 TCAM 엔트리수를 측정하기 위해 다음과 같은 방식으로 시뮬레이션을 해보았다. Snort 2.
본 논문에서 제안하는 고성능 패턴 매치 알고리즘은 TCAM을 기반으로 하고, 윈도우 크기가 다양하게 변할 수 있는 점핑 윈도우 패턴 매치 기법을 이용하여 패킷의 페이로드당 TCAM 룩업 횟수를 줄여 페이로드 스캐닝 성능을 높였다. 본 논문에서 제안한 점핑 윈도우 패턴 매치 기법은 패킷의 페이로드에서 일정 길이의 문자열을 한번의 TCAM 룩업 수행으로 처리하는 것으로 이는 시프트 패턴들의 생성과 해시 함수를 통하여 지원된다. 본 논문의 알고리즘은 다중 패턴 매치를 지원할 뿐만 아니라 규칙테이블과 매칭 테이블을 생성하여 하나의 규칙에 포함되어 있는 모든 패턴을 검색해 낼 수 있었다.
일치되는 것으로 볼 수 있다. 이를 위해 결과 데이터 테이블에 규칙식별자 필드와 패턴식별자 필드를 추가하였다. 이 필드들은 결과 데이터의 associated hash가 0 인 경우, 즉 패턴이 일치하는 경우에만 추가된다.
따라서 모든 서브 패턴들을 연속적으로 검색하기 위해서는 이전의 서브 패턴에 대한 정보를 연속되는 TCAM 룩업에 참조할 수 있어야 한다. 이를 위해 이전의 서브 패턴 룩업시 서브 패턴에 대한 정보를 해시값(associated hash)으로 만들어 TCAM 룩업 리턴 결과 데이타에 저장하고, 연속되는 TCAM 룩업시에 이전 TCAM 룩업 결과 데이터인 해시값을 TCAM 룩업키로 포함시킨다. TCAM 룩업 키는 (그림 4)에서 보이는 것과 같이 (해시값, 서브 패턴)으로 구성된다.
이때 해시값은 해시 리스트인 H□에 저장된 값을 이용한다. 입력 패킷의 페이로드 m 바이트에 대해 해시리스트 H□에 존재하는 해시값 수만큼의 검색키를 생성한 후, 각 검색키에 대해 TCAM 룩업을 수행한다. 입력 패킷의 페이로드의 첫번째 점핑 윈도우의 m 바이트는 해시리스트 H[0]를 가지게 되며, 이 값은 초기 해시값이므로 0으로 설정된다.

대상 데이터

0에 존재하는 모든 규칙들을 파싱하여 이 중 'content'라는 옵션으로부터 2, 247개의 패턴을 캐치하여 TCAM 엔트리 테이블을 생성하였다. 입력 패킷은 libpcap를 이용하여 수집한 평균 페이로드 길이가 690바이트인 10, 000개의 패킷을 대상으로 하였다.

성능/효과

따라서 점핑 윈도우 크기 m이 4~7일 때에는 TCAM 길이가 72bit, m이 8~16일 때에는 TCAM 길이가 144bit, m이 17~34일 때에는 TCAM 길이가 288bit로 동작하므로 (그림 11) 에서 점핑 윈도우 크기가 8, 17일 때 TCAM의 크기가 급격히 증가한다. (그림 11)에서 살펴보면, 본 논문에서 제안하는 점핑 윈도우 패턴 매치 알고리즘은 9Mbit TCAM에서 16-바이트 점핑 윈도우를 사용하면 TCAM 엔트리도 모두 수용 가능하면서 최대 성능을 낼 수 있다.
2절에서 설명한 바와 같이 한 패킷당 690/m 정도의 TCAM 룩업이 수행됨을 시험 결과에서 볼 수 있다. (그림 11)의 시험 결과에서 m의 크기가 커질수록 페이로드당 평균 TCAM 검색 횟수는 현저히 줄어들어 성능이 증가함을 알 수 있다. 반면에 한 패턴당 0~(m-1)개의 시프트 패턴이 생성되므로 m의 크기가 커질수록 TCAM의 엔트리 수는 증가함을 볼 수 있다.
본 논문의 알고리즘을 lOGbps를 지원하는 보안 라우터 등에 이용하기 위해서는 TCAM을 이용하는 라우터 등에 직접 구현하여 그 성능을 평가하는 작업이 필요하다. 당 연구실에서는 lOGbps 보안 라우터를 개발하기 위하여 현재 인텔의 KDP2850E4] 플랫폼을 이용하여 제안한 알고리즘을 구현하고 있으며, 이를 통해 lOGbps 보안 라우터에서 본 논문에서 제안한 점핑 윈도우 패턴 매치 알고리즘의 실제 스캐닝 성능을 측정할 수 있다. 현재 IXDP2850 플랫폼을 이용하여 Snort 규칙으로부터 일부 패턴을 캐치하여 TCAM 엔트리 테이블을 생성하였고, 패킷 처리 엔진에 제안한 알고리즘을 적용한 후 스캐닝 성능을 측정한 결과 IGbps 정도의 라인 속도를 보이고 있다.
슬라이딩 윈도우 패턴 매치 방식의 페이로드 스캐닝 속도는 nt이다. 반면 본 논문에서 제안하는 바이트 점핑 윈도우 패턴 매치 방식은 TCAM 룩업 당 〃; 바이트의 문자열을 페이로드에서 처리하므로 페이로드당 '패킷의 페이로드 길이/만큼의 TCAM 룩업이 수행된다. 따라서 페이로드 스캐닝 속도는 (n / m尤이다.
17Mpps). 반면에 본 논문의 점핑 윈도우 방식은 lOGbps 성능을 지원할 수 있으며, m이 증가할수록 스캐닝 속도가 줄어들게 되므로 점점 성능이 증가함을 볼 수 있다. (그림 10)은 슬라이딩 윈도우방식과 m=7일 때의 점핑 윈도우 방식에 대해 패킷 길이별로 TCAM 룩업 횟수를 비교한 것이다.
본 논문에서 제안하는 고성능 패턴 매치 알고리즘은 TCAM을 기반으로 하고, 윈도우 크기가 다양하게 변할 수 있는 점핑 윈도우 패턴 매치 기법을 이용하여 패킷의 페이로드당 TCAM 룩업 횟수를 줄여 페이로드 스캐닝 성능을 높였다. 본 논문에서 제안한 점핑 윈도우 패턴 매치 기법은 패킷의 페이로드에서 일정 길이의 문자열을 한번의 TCAM 룩업 수행으로 처리하는 것으로 이는 시프트 패턴들의 생성과 해시 함수를 통하여 지원된다.
본 논문에서 제안한 점핑 윈도우 패턴 매치 기법은 패킷의 페이로드에서 일정 길이의 문자열을 한번의 TCAM 룩업 수행으로 처리하는 것으로 이는 시프트 패턴들의 생성과 해시 함수를 통하여 지원된다. 본 논문의 알고리즘은 다중 패턴 매치를 지원할 뿐만 아니라 규칙테이블과 매칭 테이블을 생성하여 하나의 규칙에 포함되어 있는 모든 패턴을 검색해 낼 수 있었다.
현재 IXDP2850 플랫폼을 이용하여 Snort 규칙으로부터 일부 패턴을 캐치하여 TCAM 엔트리 테이블을 생성하였고, 패킷 처리 엔진에 제안한 알고리즘을 적용한 후 스캐닝 성능을 측정한 결과 IGbps 정도의 라인 속도를 보이고 있다. 이는 단일 패킷 처리 엔진에서 싱글쓰래드를 적용하였기 때문이며 또한 구현된 마이크로 코드의 최적화가 이루어지지 않은 상태에서의 성능이기 때문에, 멀티 패킷 처리 엔진 사용 및 멀티 쓰래드 방식 적용, 코드 최적화 등을 적용하면 몇 배의 성능 향상이 예측되는 니h 본 논문에서 제안한 알고리즘이 수기가급 보안 라우터에 적합할 것으로 보인다.
패킷의 평균 페이로드 길이가 690바이트이므로 4.2절에서 설명한 바와 같이 한 패킷당 690/m 정도의 TCAM 룩업이 수행됨을 시험 결과에서 볼 수 있다. (그림 11)의 시험 결과에서 m의 크기가 커질수록 페이로드당 평균 TCAM 검색 횟수는 현저히 줄어들어 성능이 증가함을 알 수 있다.
당 연구실에서는 lOGbps 보안 라우터를 개발하기 위하여 현재 인텔의 KDP2850E4] 플랫폼을 이용하여 제안한 알고리즘을 구현하고 있으며, 이를 통해 lOGbps 보안 라우터에서 본 논문에서 제안한 점핑 윈도우 패턴 매치 알고리즘의 실제 스캐닝 성능을 측정할 수 있다. 현재 IXDP2850 플랫폼을 이용하여 Snort 규칙으로부터 일부 패턴을 캐치하여 TCAM 엔트리 테이블을 생성하였고, 패킷 처리 엔진에 제안한 알고리즘을 적용한 후 스캐닝 성능을 측정한 결과 IGbps 정도의 라인 속도를 보이고 있다. 이는 단일 패킷 처리 엔진에서 싱글쓰래드를 적용하였기 때문이며 또한 구현된 마이크로 코드의 최적화가 이루어지지 않은 상태에서의 성능이기 때문에, 멀티 패킷 처리 엔진 사용 및 멀티 쓰래드 방식 적용, 코드 최적화 등을 적용하면 몇 배의 성능 향상이 예측되는 니h 본 논문에서 제안한 알고리즘이 수기가급 보안 라우터에 적합할 것으로 보인다.

후속연구

각 패킷의 TCAM 룩업 횟수에 대해 알아보았다. 본 논문의 알고리즘을 lOGbps를 지원하는 보안 라우터 등에 이용하기 위해서는 TCAM을 이용하는 라우터 등에 직접 구현하여 그 성능을 평가하는 작업이 필요하다. 당 연구실에서는 lOGbps 보안 라우터를 개발하기 위하여 현재 인텔의 KDP2850E4] 플랫폼을 이용하여 제안한 알고리즘을 구현하고 있으며, 이를 통해 lOGbps 보안 라우터에서 본 논문에서 제안한 점핑 윈도우 패턴 매치 알고리즘의 실제 스캐닝 성능을 측정할 수 있다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

TCAM을 이용한 고성능 패턴 매치 알고리즘
High-Speed Pattern Matching Algorithm using TCAM 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

성능/효과

후속연구

참고문헌 (15)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

TCAM을 이용한 고성능 패턴 매치 알고리즘 High-Speed Pattern Matching Algorithm using TCAM 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

성능/효과

후속연구

참고문헌 (15)

이 논문을 인용한 문헌

저자의 다른 논문 :

성정식 (2) 강석민 (1) 권택근 (10) 김봉태 (20)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

TCAM을 이용한 고성능 패턴 매치 알고리즘
High-Speed Pattern Matching Algorithm using TCAM 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper