• 순차 탐색의 문제점

컴퓨터과학에서 패턴 매칭이란 데이터를 검색할 때 특정 패턴이 출현하는지, 또는 어디에 출현하는지 등을 특정하는 방법의 일종이다. 이 글에서는 대상 문자열에서 일치하는 것이 있는지를 찾는 문자열 패턴 매칭에 대해서 다룰 것이다.

문자열에서 패턴과 일치하는 것을 찾으려면, 앞에서부터 비교해서 일치하는 것을 찾으면 된다. 찾아야 할 패턴이 여러 개라면 앞에서 말한 방법을 반복적으로 수행하면 된다. 패턴이 몇 개 되지 않거나, 성능이 요구되지 않는다면 이와 같이 할 수도 있다. 패턴의 수가 수백 수천개가 된다면, 이런 방식으로 동작하는 보안 장비가 중간에 개입하고 있다면, 인터넷이 매우 느려지거나 먹통이 될 수 있을 것이다.

위 그림은 리스트를 이용하여 순차 탐색하는 방법을 보여준다. 대상 문자열을 반복적으로 순회하여 패턴을 찾는다. 패턴 리스트에서 앞쪽에 위치하는 패턴과 매칭이 된다면, 빠르게 탐색을 할 수 있지만, 매칭되는 것이 없거나, 패턴 리스트의 뒤쪽에 위치한다면 매칭되는 것을 찾는데 꽤 오랜 시간을 소요하게 된다.

■ 개선을 위한 방법

패턴 매칭의 성능 개선을 위해서 몇 가지 고려해야 할 것들이 있다.

• 패턴의 변경은 자주 발생하지 않는다.
• 구현이 쉽고 단순해야 한다.
• 와일드카드 문자를 사용할 수 있어야 한다.
• 메모리 사용량에 제한이 있다. 여러 개의 프로세스가 뜨고, 각각이 동일한 패턴들을 로딩해야 하므로, 전체 메모리를 나눠서 사용해야 한다.
• 패턴은 우리가 만든다.

다중 문자열 패턴 매칭 방법으로 Aho-Corasick이 많이 알려져 있다. 이 방법은 Trie라는 자료구조를 사용하는 것으로, 한번의 경로 탐색으로 일치하는 패턴을 탐지 할 수 있다. 문자열 검색에 가장 좋은 성능 보이는 것으로 알려져 있다. 입력되는 패턴에 따라 메모리를 과도하게 사용할 수 있고, 와일드 카드 문자를 사용하기 어려운 단점이 존재한다.  그래서 적당한 메모리를 사용하고 성능을 개선할 수 있는 방법을 찾아보고자 한다.

[그림] Trie 자료구조 예시

새로운 방법은 사전 처리 단계와 패턴 매칭 단계로 이루어진다. 사전 처리 단계는 패턴의 변경이 자주 발생하지 않으므로, 패턴 매칭의 성능을 개선하기 위한 전용의 구조(패턴맵)로 만드는 단계이다.  한번 만들어지면 패턴이 변경되기 전까지 다시 수행할 필요가 없다.

위 그림은 패턴들이 어떻게 구조화 되는지를 보여준다. 패턴의 앞 2바이트를 인덱스로 해서 분류해서 저장한다. 64K 크기를 갖는 리스트의 배열로 보면 된다. 각 리스트에는 동일한 2바이트로 시작하는 패턴들이 오름차순으로 정렬되어 있다. 정렬된 리스트의 각 항목을 가리키는 포인터 배열인 레퍼러(Referer)가 존재한다. 레퍼러는 이진검색을 하기 위한 요소이다. 각 리스트에는 패턴의 최소 길이 정보가 있어서, 대상 문자열이 최소 길이보다 작으면 매칭을 생략할 수 있다.

패턴 매칭 단계는 앞에서 만들어진 패턴맵을 사용해서 일치하는 것을 찾는 단계이다. 이 단계의 빨라야 성능이 개선될 수 있다.

위 그림은 대상 문자열에서 패턴을 매칭하는 과정을 보여준다. 대상 문자열의 시작에서 부터 1바이트씩 이동하면서 2바이트를 인덱스로 추출하고, 패턴맵에서 추출된 인덱스에 해당하는 패턴 리스트를 다이렉트로 찾고, 패턴 리스트는 레퍼러를 이용하여 이진 검색으로 일치하는 패턴을 찾는다.

이 방법은 전체 패턴을 앞의 2바이트 기준으로 64K 리스트 중의 하나에 분배한다. 이렇게 함으로써 전체적인 비교횟수를 줄일 수 있고, 대상 문자열 내에서 나타나는 순서대로 찾아낼 수 있다. 각각의 리스트는 정렬되어 있어서 이진 검색을 함으로써, 패턴의 수가 증가하더라도 성능 하락이 크지 않다.

물론 모든 패턴의 앞 2바이트가 동일하다면, 하나의 리스트에 분배가 되는 최악의 상황이 발생한다. 그렇더라도 이진 검색을 할 수 있으므로, 일반적인 순차 검색 보다는 나은 성능을 보인다. 실제 이런 상황이 발생할 일은 거의 없을 것이고, 패턴을 그렇게 만들지 않으면 된다.

■ 결론

지금까지 설명한 방법은 이론적으로 이상적인 방법은 아니다. 분명 단점들도 존재한다. 그렇지만 충분한 성능 개선을 할 수 있고, 구현하기 쉽다. 모니터랩의 제품에 사용되는 특정 패턴의 경우에 Aho-Corasick보다 더 나은 성능을 보인다. 물론 앞부분이 일치하는 패턴이 많다면 Aho-Corasick을 따라갈 수 없다. 단순히 프로그래밍만으로 모든 것을 해결하기는 어렵다. 하지만 앞에서 말한 구조에 맞춰서 패턴을 만들거나, 패턴의 특성을 잘 이해하여 그에 맞는 형태로 개발한다면, 원하는 성능 개선을 할 수 있다.