알맞은 검색알고리즘과 데이터 구조에 대한 질문

lastpaba의 이미지

현재 리눅스에서 패킷캡쳐를 제작중입니다. 이 캡쳐는 필터링기능을 위해 configure파일을 가지는데, 최대 필터조건은 128레코드입니다. 하나의 레코드는 4개의 필드로 나누고 소스주소,포트,대상주소,포트를 입력하게 합니다.(각 필드에 any를 입력가능)

프로그램의 동작방법은 수신한 패킷의 정보를 필터파일 128개의
래코드와 비교하는데 각 래코드의 필드전체를 만족해야 캡쳐를 하고 전송하는 방법입니다. (애니가 들어있는 필드는 무조건 조건에 일치한것으로 함. 단, 다른 필드가 불일치의 경우는 패스함)

즉, 선형으로 128*4을 모두 검색해야한다는 의견이 많은데, 좀더 나은 알고리즘은 없을런지요. 또한 래코드의 데이타 구조는 어떻게하는것이 좋을런지요.
데이타는 주소는 32비트 풀로 사용하고 포트는 아직 정해지지 않았습니다.

ssehoony의 이미지

이런 경우 필터조건 레코드의 수정의 매우 드물고 검색이 난무하는 상황이군요.
그렇다면 당연히 단순한 배열에 binary search 가 좋을 것 같네요.

happyjun의 이미지

linux kernel의 netfilter나 snort 의 소스를 보시면 어느정도 최적화된 방법을 찾으실 수 있습니다.

가장 간단한 방법은 질문하신 분이 말씀하신 것과 같이 선형적인 검사 방법입니다.

any 값을 허용하고 IP 필드는 사실 192.168.0/24 와 같은 값도 허용해야 하므로 입력된 주소 & 마스크 == 원하는 주소 와 같이 하나하나 비교해야 합니다.

조금 더 최적화된 방법을 찾으시면 필터링 규칙을 그룹화하는 방법이 있습니다.

소스주소가 any인 그룹, 대상주소가 80인 그룹, ... 등과 같이 해서 비교할 대상을 줄이는 방법입니다.

이론적으로 가장 빠른 방법은 모든 경우를 테이블로 만들어 한번의 lookup으로 찾는 방법입니다.

bool filterTable[ 0xFFFFFFFF /* source IP */ ][ 0xFFFF /* source port */ ][ 0xFFFFFFFF /* target IP */][ 0xFFFF /* target port */];

를 만들면 됩니다. 하지만 너무 많은 메모리를 소비하므로 앞의 구룹화하는 방법이나 해쉬테이블을 이용하는 방법 또는 snort와 같이 btree (오래되서 정확하지 않습니다)를 사용하시면 됩니다.

----------------------------------------
http://moim.at
http://mkhq.co.kr

htna의 이미지

만약 속도에 중심을 두는 것이라면 hash table을 사용하는게 낫다고 봅니다.
더구나 128개라면 그리 많지 않은 양이기에 충분한 크기의 hash table을 사용할경우
일반적으로 1~2 번 정도의 hash key를 구하는 것으로 원하는 결과를 얻을 수 있을 것입니다.
물론 hash key를 어떤방법을 이용해서 구하느냐가 관건입니다만.
이는 찾아보시기 바랍니다.

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

익명 사용자의 이미지

오늘 저희팀이 두차례에 걸친 회의끝에 결론은 여러분의 답변과
유사한점이 많이 있습니다.

첫째, 가장 문제가 되는것은 any를 허용한다면 그룹을 분류해도,
결국은 조건에 맞는 값이 없을 경우는 any의 그룹을 검색해야
한다는 문제입니다.

둘째, 위사항은 어쩔수 없는 사항이므로 가능한 효율적이며,
빠른 방법을 모색하는것인데, 이 역시도 선형구조에 트리를
가미한 방법과 해쉬를 각각 성능테스트해 보기로 했습니다.
(사실 결과를 봐야알겠지만 순차검색이 위의 경우에 오히려
개발에서부터 간단하고 속도면에서도 느리지 않을듯합니다.)

그리고, 이번 개발에서는 무엇보다 40만BHCA에 견뎌내야하므로
저희들 테스트 결과로는 libpcap등은 로스가 많아서 포기하고
현재는 커널 수정을 하고있는 형편이라서 더 이상은 개발 시간이
없는듯해서 일단은 순차를 기본으로 생각중입니다.

답변해주신 모든분께..감사합니다.

ssehoony의 이미지

좀 늦은것 같지만

전 아무리 생각해 binary search 가 최선의 선택일 것 같은데요.
128개의 경우 최악의 경우라도 binary search 경우 7번으로 찾아 낼 수 있습니다. (any 를 처리하려면 다른게 좀 가미가 되야 할 것 같긴 하지만요)
worst case 에서도 7번이 보장된다는게 매력적이지 않나요?

그리고 잠시 생각해 봤는데 any 도 하나의 값으로 처리한다면
원본 소스의 필드를 any 로 치환해서 비교하면 any 치환 가지수가 2^4 = 16 가지 이므로 기본 비교 7 번 그리고 16가지 any 치환비교 16 * 7 = 112
16 + 112 = 128
음.. 최악의 경우 any 비교까지 128 번 비교로 찾는다로 결론이 나는군요. (음... 위 계산에 오류있나?)
근데 이건 그냥 선형 비교랑 똑 같다는 결론이 나와버리는 군요 ㅡ.ㅡ;

기왕이면 binary search 까지 벤치마킹 해서 결과를 올려주시면 어떨까요?
다른 분들도 도움이 많이 될 것 같은데요. :D

그럼 좋은 결과 있길...

htna의 이미지

하하 문제를 다시 읽어보다보니 any 라는 놈이 있었군요.
그렇다면 각 any를 이용해 조합 가능한 종류별로 hash table을 만들어 사용하는 편이 낫겠군요.

128개의 record에, 4개의 field를 조합 가능한 set이 15개(모든 field가 any인것은 필요 없겠죠..)이므로,

하나의 어레이에 record 가 들어가고, (128*4)
hash table이 가지는 값으로 위의 인덱스를 가지면 되므로... (hash_table_size*1)
총 15개의 hash table이 사용되므로
(hash_table_size*15 + 128*4)의 메모리로 해결할 수 있습니다.
검색은 하나의 hash table에서 검색하는 정도이므로 속도도 크케 나빠지지 않을 것입니다.

처음에 데이터들을 초기화하는게 좀 xxx 같을지는 모르겠지만.
제한된 환경하에서는 최적일것 같군요...

int hash_table_size = 128 * 2/3;
record  _configure[128];
int  _hash_table_for____X[hash_table_size];
int  _hash_table_for___X_[hash_table_size];
int  _hash_table_for__X__[hash_table_size];
int  _hash_table_for_X___[hash_table_size];
int  _hash_table_for___XX[hash_table_size];
...
int  _hash_table_for_XXX_[hash_table_size];
int  _hash_table_for_XXXX[hash_table_size];

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

happyjun의 이미지

수정하신 커널이 독점적 라이센스를 보장하거나 BSD류가 아닌 Linux라면 공개하셔야 합니다.

----------------------------------------
http://moim.at
http://mkhq.co.kr

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.