Text Search (lib/textsearch)

리눅스 커널의 텍스트 검색 프레임워크(lib/textsearch.c)를 심층 분석합니다. ts_config/ts_state/ts_ops 3-계층 구조 설계, KMP(Knuth-Morris-Pratt)·Boyer-Moore·FSM(유한 상태 기계) 3가지 플러그인 알고리즘의 내부 구현과 전처리 비용, skb 분산 데이터에 대한 선형화 없는 검색, netfilter xt_string 모듈과 nf_conntrack 헬퍼에서의 실전 활용, 알고리즘 선택 기준과 성능 벤치마크까지 포괄합니다.

텍스트 검색 프레임워크 개요

리눅스 커널의 텍스트 검색 프레임워크는 lib/textsearch.c에 구현된 범용 패턴 매칭 인프라입니다. 2004년 Thomas Graf가 netfilter의 문자열 매칭 요구를 일반화하여 도입했으며, 핵심 설계 목표는 다음 세 가지입니다.

• 알고리즘 독립성 — 검색 알고리즘을 플러그인으로 교체할 수 있어, 사용 패턴에 맞는 최적 알고리즘을 선택할 수 있습니다.
• 데이터 소스 추상화 — 연속 메모리 버퍼뿐 아니라 skb의 비선형 fragment 체인에서도 동일한 API로 검색할 수 있습니다.
• 동시성 안전 — 설정(config)과 상태(state)를 분리하여 같은 패턴 설정을 여러 컨텍스트에서 동시에 사용할 수 있습니다.

프레임워크는 3계층 구조로 동작합니다. 최상위의 호출자(xt_string, conntrack helper 등)가 textsearch API를 통해 검색을 요청하면, API 계층은 ts_config에 바인딩된 ts_ops의 콜백(Callback)을 호출하여 실제 알고리즘을 실행합니다. 이 구조 덕분에 호출자는 어떤 알고리즘이 사용되는지 알 필요가 없습니다.

프레임워크 도입 배경

텍스트 검색 프레임워크 도입 전, netfilter의 문자열 매칭은 xt_string 모듈 내부에 직접 구현된 단순 brute-force 알고리즘을 사용했습니다. 이 방식에는 몇 가지 문제가 있었습니다.

• O(n*m) 최악 성능 — 악의적으로 조작된 패킷이 최악 경우를 유발하여 CPU DoS 공격에 취약
• 알고리즘 교체 불가 — 사용 시나리오에 맞는 최적 알고리즘 선택 불가능
• 코드 중복 — conntrack 헬퍼들이 각각 자체 문자열 검색 로직을 구현
• skb 처리 비효율 — 비선형 skb를 먼저 선형화해야 검색 가능

프레임워크 도입 후, 이 모든 문제가 해결되었습니다. KMP/Boyer-Moore의 O(n+m) 보장으로 DoS 위험이 감소하고, 플러그인 아키텍처로 알고리즘을 자유롭게 선택할 수 있으며, get_next_block 콜백으로 skb의 비선형 데이터를 선형화 없이 검색할 수 있게 되었습니다.

커널 버전별 변화

ts_config / ts_state 구조체(Struct)

텍스트 검색 프레임워크의 핵심은 설정(config)과 상태(state)의 명확한 분리입니다. 이 설계는 SMP 환경에서 동시 검색을 가능하게 하는 핵심 요소입니다.

ts_config — 불변 검색 설정

/* include/linux/textsearch.h */
struct ts_config {
    struct ts_ops       *ops;       /* 검색 알고리즘 (KMP/BM/FSM) */
    int                 flags;      /* TS_AUTOLOAD 등 */

    /**
     * get_next_block - 다음 데이터 블록을 가져오는 콜백
     * @consumed: 지금까지 소비한 바이트 수
     * @dst:      블록 포인터 반환 위치
     * @conf:     설정 구조체
     * @state:    검색 상태
     *
     * skb처럼 분산된 데이터에서 블록 단위 순회 가능
     */
    unsigned int        (*get_next_block)(unsigned int consumed,
                            const u8 **dst,
                            struct ts_config *conf,
                            struct ts_state *state);
    void                (*finish)(struct ts_config *conf,
                            struct ts_state *state);
};

ts_state — per-call 가변 상태

/* include/linux/textsearch.h */
struct ts_state {
    unsigned int        offset;     /* 현재 검색 오프셋 */
    char                cb[40];     /* 알고리즘별 콜백 데이터 */
};

ts_state는 각 검색 호출마다 스택에 할당됩니다. offset 필드는 현재까지 검색을 진행한 위치를 추적하고, cb[] 배열은 알고리즘이 자유롭게 사용할 수 있는 40바이트 스크래치 공간입니다. 스택 할당이므로 별도의 메모리 할당/해제가 필요 없습니다.

ts_ops 인터페이스

ts_ops는 텍스트 검색 알고리즘이 구현해야 하는 인터페이스입니다. 이 구조체를 등록하면 프레임워크가 해당 알고리즘을 이름으로 찾아 사용할 수 있습니다.

/* include/linux/textsearch.h */
struct ts_ops {
    const char         *name;       /* "kmp", "bm", "fsm" */
    struct ts_config * (*init)(const void *pattern,
                                unsigned int len,
                                gfp_t gfp_mask,
                                int flags);
    unsigned int       (*find)(struct ts_config *conf,
                                struct ts_state *state);
    void               (*destroy)(struct ts_config *conf);
    struct ts_config * (*get_pattern)(struct ts_config *conf);
    unsigned int       (*get_pattern_len)(struct ts_config *conf);
    struct module      *owner;      /* THIS_MODULE */
    struct list_head   list;        /* 전역 알고리즘 리스트 */
};

알고리즘 등록/해제

/* lib/textsearch.c */
int textsearch_register(struct ts_ops *ops)
{
    int err = -EEXIST;
    struct ts_ops *o;

    if (ops->name == NULL || ops->find == NULL
        || ops->init == NULL)
        return -EINVAL;

    spin_lock(&ts_mod_lock);
    list_for_each_entry(o, &ts_ops_list, list) {
        if (!strcmp(o->name, ops->name))
            goto errout;
    }
    list_add_tail_rcu(&ops->list, &ts_ops_list);
    err = 0;
errout:
    spin_unlock(&ts_mod_lock);
    return err;
}
EXPORT_SYMBOL(textsearch_register);

KMP 알고리즘 (ts_kmp)

Knuth-Morris-Pratt(KMP) 알고리즘은 텍스트 검색에서 가장 널리 사용되는 정확 매칭 알고리즘입니다. 핵심 아이디어는 실패 함수(failure function)를 전처리하여, 불일치 발생 시 이미 매칭된 접두사 정보를 재활용(Recycling)하는 것입니다.

실패 함수(Failure Function) 구축

실패 함수 F[i]는 패턴의 처음 i+1개 문자로 구성된 부분 문자열에서 접두사이면서 접미사인 최대 길이를 저장합니다. 이 테이블을 통해 불일치 시 패턴을 얼마나 이동시킬지 결정합니다.

/* lib/ts_kmp.c — 실패 함수 구축 (simplified) */
static void compute_prefix_tbl(const u8 *pattern, unsigned int len,
                                unsigned int *prefix_tbl)
{
    unsigned int k = 0;
    prefix_tbl[0] = 0;

    for (unsigned int q = 1; q < len; q++) {
        while (k > 0 && pattern[k] != pattern[q])
            k = prefix_tbl[k - 1];
        if (pattern[k] == pattern[q])
            k++;
        prefix_tbl[q] = k;
    }
}

커널 KMP 검색 구현

/* lib/ts_kmp.c — kmp_find() 핵심 루프 */
static unsigned int kmp_find(struct ts_config *conf,
                             struct ts_state *state)
{
    struct ts_kmp *kmp = ts_config_priv(conf);
    unsigned int text_len, consumed = state->offset;
    const u8 *text;
    unsigned int q = 0;  /* 패턴 내 현재 위치 */

    while ((text_len = conf->get_next_block(consumed, &text,
                                            conf, state)) > 0) {
        for (unsigned int i = 0; i < text_len; i++) {
            while (q > 0 && kmp->pattern[q] != text[i])
                q = kmp->prefix_tbl[q - 1];
            if (kmp->pattern[q] == text[i])
                q++;
            if (q == kmp->pattern_len) {
                state->offset = consumed + i + 1;
                return state->offset - kmp->pattern_len;
            }
        }
        consumed += text_len;
    }
    return UINT_MAX;  /* 매칭 실패 */
}

KMP 대소문자 무시 (TS_IGNORECASE)

TS_IGNORECASE 플래그가 설정된 경우, KMP는 전처리 단계에서 패턴을 소문자로 변환하고, 검색 시에도 텍스트를 소문자로 변환하여 비교합니다.

/* ts_kmp.c — 대소문자 무시 비교 */
static inline int kmp_char_eq(u8 a, u8 b, int icase)
{
    if (icase)
        return tolower(a) == tolower(b);
    return a == b;
}

KMP 연속 검색 패턴

하나의 ts_config로 여러 매칭을 찾으려면 textsearch_find() 후 textsearch_next()를 반복 호출합니다. ts_state.offset이 자동으로 갱신되어 이전 매칭 위치 이후부터 검색합니다.

/* 모든 매칭 위치 출력 */
unsigned int pos;
pos = textsearch_find(conf, &state);
while (pos != UINT_MAX) {
    pr_info("match at offset %u\n", pos);
    pos = textsearch_next(conf, &state);
}

Boyer-Moore 알고리즘 (ts_bm)

Boyer-Moore 알고리즘은 패턴을 오른쪽에서 왼쪽으로 비교하면서, 불일치 시 두 가지 시프트 규칙을 적용하여 큰 폭으로 건너뛰는 알고리즘입니다. 긴 패턴과 큰 알파벳에서 KMP보다 빠른 평균 성능을 보입니다.

나쁜 문자 시프트 (Bad Character Shift)

텍스트에서 불일치가 발생한 문자가 패턴에 없으면 패턴 전체를 건너뛰고, 있으면 해당 문자의 패턴 내 마지막 위치에 맞춰 이동합니다.

좋은 접미사 시프트 (Good Suffix Shift)

이미 매칭된 접미사가 패턴의 다른 위치에도 나타나면, 그 위치에 맞춰 이동합니다.

커널 Boyer-Moore 구현

/* lib/ts_bm.c — 주요 구조체 */
struct ts_bm {
    u8              *pattern;
    unsigned int    patlen;
    unsigned int    bad_shift[ASIZE];  /* 256 엔트리 (바이트 알파벳) */
    unsigned int    good_shift[];     /* patlen 크기 */
};

/* lib/ts_bm.c — bm_find() 핵심 루프 (simplified) */
static unsigned int bm_find(struct ts_config *conf,
                            struct ts_state *state)
{
    struct ts_bm *bm = ts_config_priv(conf);
    unsigned int i = bm->patlen - 1;  /* 텍스트 시작 위치 */
    const u8 *text;
    unsigned int text_len, consumed = state->offset;

    while ((text_len = conf->get_next_block(consumed, &text,
                                            conf, state)) > 0) {
        while (i < text_len) {
            int j = bm->patlen - 1;
            while (j >= 0 && text[i] == bm->pattern[j]) {
                i--; j--;
            }
            if (j < 0) {
                state->offset = consumed + i + 1;
                return state->offset;
            }
            i += max(bm->bad_shift[text[i]],
                     bm->good_shift[j]);
        }
        consumed += text_len;
    }
    return UINT_MAX;
}

Boyer-Moore 전처리 상세

Boyer-Moore의 전처리는 두 테이블을 구축합니다. bad_shift[256] 테이블은 모든 바이트 값에 대해 시프트 거리를 저장하며, O(|Σ|) = O(256)에 구축됩니다. good_shift[m] 테이블은 패턴의 각 위치에서 매칭된 접미사에 대한 시프트를 저장합니다.

/* lib/ts_bm.c — bad_shift 테이블 구축 */
static void compute_bad_shift(struct ts_bm *bm)
{
    int i;

    /* 기본값: 패턴에 없는 문자는 패턴 길이만큼 시프트 */
    for (i = 0; i < ASIZE; i++)
        bm->bad_shift[i] = bm->patlen;

    /* 패턴에 있는 문자: 마지막 출현 위치 기반 시프트 */
    for (i = 0; i < bm->patlen - 1; i++)
        bm->bad_shift[bm->pattern[i]] = bm->patlen - 1 - i;
}

FSM 알고리즘 (ts_fsm)

FSM(Finite State Machine) 알고리즘은 단순 문자열이 아닌 토큰 기반 패턴을 매칭할 수 있는 유한 상태 기계입니다. 정규식의 간소화된 버전으로, 문자 클래스·반복·와일드카드를 지원합니다.

FSM 토큰 정의

/* include/linux/textsearch_fsm.h */
enum ts_fsm_token_type {
    TS_FSM_SPECIFIC,    /* 특정 문자 매칭 */
    TS_FSM_WILDCARD,    /* 임의 문자 매칭 (.) */
    TS_FSM_CNTRL,       /* 제어 문자 */
    TS_FSM_LOWER,       /* 소문자 [a-z] */
    TS_FSM_UPPER,       /* 대문자 [A-Z] */
    TS_FSM_PUNCT,       /* 구두점 */
    TS_FSM_SPACE,       /* 공백 */
    TS_FSM_DIGIT,       /* 숫자 [0-9] */
    TS_FSM_ALPHA,       /* 알파벳 [a-zA-Z] */
    TS_FSM_ALNUM,       /* 알파벳+숫자 */
    TS_FSM_ASCII,       /* ASCII 문자 */
    __TS_FSM_TYPE_MAX,
};

enum ts_fsm_token_recur {
    TS_FSM_SINGLE,      /* 정확히 1번 */
    TS_FSM_PERHAPS,     /* 0 또는 1번 (?) */
    TS_FSM_ANY,         /* 0회 이상 (*) */
    TS_FSM_MULTI,       /* 1회 이상 (+) */
    TS_FSM_HEAD_IGNORE, /* 앞부분 무시 */
};

struct ts_fsm_token {
    u16     type;       /* ts_fsm_token_type */
    u8      recur;      /* ts_fsm_token_recur */
    u8      value;      /* TS_FSM_SPECIFIC일 때 매칭할 문자 */
};

FSM 매칭 사용 예시

/* FSM으로 "GET /[alpha]+ HTTP/1." 패턴 구성 */
struct ts_fsm_token http_get_pattern[] = {
    { .type = TS_FSM_SPECIFIC, .recur = TS_FSM_SINGLE,
      .value = 'G' },
    { .type = TS_FSM_SPECIFIC, .recur = TS_FSM_SINGLE,
      .value = 'E' },
    { .type = TS_FSM_SPECIFIC, .recur = TS_FSM_SINGLE,
      .value = 'T' },
    { .type = TS_FSM_SPACE,    .recur = TS_FSM_SINGLE },
    { .type = TS_FSM_SPECIFIC, .recur = TS_FSM_SINGLE,
      .value = '/' },
    { .type = TS_FSM_ALPHA,    .recur = TS_FSM_MULTI },
    /* TS_FSM_MULTI = 1회 이상 반복 (+) */
    { .type = TS_FSM_SPACE,    .recur = TS_FSM_SINGLE },
    { .type = TS_FSM_SPECIFIC, .recur = TS_FSM_SINGLE,
      .value = 'H' },
    { .type = TS_FSM_SPECIFIC, .recur = TS_FSM_SINGLE,
      .value = 'T' },
    { .type = TS_FSM_SPECIFIC, .recur = TS_FSM_SINGLE,
      .value = 'T' },
    { .type = TS_FSM_SPECIFIC, .recur = TS_FSM_SINGLE,
      .value = 'P' },
    { .type = TS_FSM_SPECIFIC, .recur = TS_FSM_SINGLE,
      .value = '/' },
    { .type = TS_FSM_DIGIT,   .recur = TS_FSM_SINGLE },
    { .type = TS_FSM_SPECIFIC, .recur = TS_FSM_SINGLE,
      .value = '.' },
};

struct ts_config *conf;
conf = textsearch_prepare("fsm",
                          http_get_pattern,
                          ARRAY_SIZE(http_get_pattern),
                          GFP_KERNEL,
                          TS_AUTOLOAD);

알고리즘 선택 가이드

세 알고리즘은 각각 다른 시나리오에서 최적의 성능을 보입니다. 선택 기준은 패턴 길이, 데이터 특성, 재사용 빈도입니다.

선택 기준 요약

대부분의 네트워크 보안 규칙에서 패턴은 4~30바이트 범위이며, 이 범위에서 KMP와 Boyer-Moore의 성능 차이는 미미합니다. 알고리즘 선택보다 --from/--to를 통한 검색 범위 최적화가 전체 성능에 훨씬 큰 영향을 미칩니다.

전처리 비용

각 알고리즘의 init() 콜백에서 수행하는 전처리는 패턴이 변경될 때만 한 번 실행되며, 이후 검색은 전처리된 테이블을 재사용합니다. iptables 규칙이 로드될 때 textsearch_prepare()가 호출되고, 이후 모든 패킷 검사는 textsearch_find()만 호출합니다.

메모리 할당은 kmalloc()으로 수행되며, ts_config 구조체 뒤에 알고리즘별 private 데이터가 연속 할당됩니다. 단일 할당으로 구조체와 private 데이터를 함께 배치하면 캐시(Cache) 지역성이 향상되고, 해제 시에도 kfree() 한 번으로 충분합니다.

/* lib/textsearch.c — textsearch_prepare() 할당 구조 */
/* +------+----------+------------------+
 * | hdr  | ts_config | algo private data |
 * +------+----------+------------------+
 * ^                   ^
 * conf               ts_config_priv(conf)
 */
struct ts_config *conf;
conf = kmalloc(sizeof(struct ts_config) + priv_size, gfp_mask);
/* priv_size는 알고리즘이 요구하는 추가 크기 */

API 레퍼런스

텍스트 검색 프레임워크의 공개 API는 6개의 핵심 함수로 구성됩니다.

textsearch_prepare()

struct ts_config *textsearch_prepare(
    const char *algo,           /* "kmp", "bm", "fsm" */
    const void *pattern,        /* 검색 패턴 */
    unsigned int len,           /* 패턴 길이 */
    gfp_t gfp_mask,             /* GFP_KERNEL 등 */
    int flags                   /* TS_AUTOLOAD | TS_IGNORECASE */
);

알고리즘 이름으로 ts_ops를 찾고, ops->init()을 호출하여 패턴을 전처리합니다. 반환된 ts_config *를 이후 검색에 사용합니다.

textsearch_find() / textsearch_next()

static inline unsigned int textsearch_find(
    struct ts_config *conf,
    struct ts_state *state)
{
    state->offset = 0;
    return textsearch_next(conf, state);
}

static inline unsigned int textsearch_next(
    struct ts_config *conf,
    struct ts_state *state)
{
    unsigned int ret = conf->ops->find(conf, state);
    if (ret != UINT_MAX)
        state->offset = ret + 1;
    return ret;
}

textsearch_find()는 오프셋을 0으로 리셋하고 첫 매칭을 반환합니다. textsearch_next()는 이전 매칭 이후부터 다음 매칭을 찾습니다. 반환값이 UINT_MAX이면 매칭이 없습니다.

textsearch_destroy()

static inline void textsearch_destroy(struct ts_config *conf)
{
    if (conf->ops->destroy)
        conf->ops->destroy(conf);
    module_put(conf->ops->owner);
    kfree(conf);
}

textsearch_register() / textsearch_unregister()

int textsearch_register(struct ts_ops *ops);
int textsearch_unregister(struct ts_ops *ops);

알고리즘 모듈이 로드/언로드될 때 호출됩니다. ts_mod_lock spinlock으로 보호되는 전역 리스트에 추가/제거합니다. 같은 이름의 알고리즘이 이미 등록되어 있으면 -EEXIST를 반환합니다.

skb와 텍스트 검색

네트워크 패킷은 sk_buff(skb) 구조체에 담기며, 페이로드가 선형 영역과 비선형 fragments로 분산될 수 있습니다. skb_find_text()는 이 분산 데이터를 선형화하지 않고 순회하며 패턴을 검색하는 래퍼 함수입니다.

/* net/core/utils.c */
unsigned int skb_find_text(struct sk_buff *skb,
                           unsigned int from,
                           unsigned int to,
                           struct ts_config *config)
{
    struct ts_state state;
    unsigned int ret;

    BUILD_BUG_ON(sizeof(struct skb_seq_state) >
                 sizeof(state.cb));

    config->get_next_block = skb_ts_get_next_block;
    config->finish = skb_ts_finish;

    skb_prepare_seq_read(skb, from, to, TS_SKB_CB(&state));
    ret = textsearch_find(config, &state);

    return ret;
}

skb_seq_state 반복자

skb_seq_state는 skb의 선형 영역, frags[], frag_list를 순차적으로 순회하는 반복자입니다. get_next_block() 콜백에 바인딩되어 텍스트 검색 알고리즘에 블록 단위로 데이터를 제공합니다.

/* include/linux/skbuff.h */
struct skb_seq_state {
    __u32           lower_offset;  /* 검색 시작 오프셋 */
    __u32           upper_offset;  /* 검색 종료 오프셋 */
    __u32           frag_idx;      /* 현재 fragment 인덱스 */
    __u32           stepped_offset;/* 현재까지 진행한 바이트 */
    struct sk_buff  *root_skb;     /* 원본 skb */
    struct sk_buff  *cur_skb;      /* 현재 순회 중인 skb */
    __u8            *frag_data;    /* kmap된 fragment 데이터 */
    __u32           frag_off;      /* fragment 내 오프셋 */
};

skb 데이터 레이아웃과 검색 범위

skb의 데이터 영역은 선형 영역(head~tail), 페이지(Page) fragments(skb_shinfo->frags[]), frag_list(GSO/GRO 결합 패킷)로 구성됩니다. skb_find_text()의 from/to 매개변수는 이 전체 영역에 대한 논리적 오프셋입니다.

/* skb 데이터 영역 구조 */
/*
 * offset 0                    skb->len
 * |                           |
 * +--------+----------+-------+--------+
 * | linear | frag[0]  |frag[1]|frag_lst|
 * | (head~ | (page    | (page | (chained
 * |  tail) |  frag)   |  frag)|  skbs)
 * +--------+----------+-------+--------+
 *          ^                           ^
 *      skb->data_len 시작        skb->len 끝
 *
 * skb_find_text(skb, from, to, config)
 *   from/to는 이 전체 범위 내의 오프셋
 */

skb_seq_read 상태 전이

skb_seq_read()는 호출될 때마다 다음 연속 데이터 블록을 반환합니다. 내부적으로 3단계 상태 전이를 거칩니다.

netfilter xt_string

xt_string은 netfilter의 문자열 매칭 확장 모듈로, iptables/ip6tables의 -m string 옵션을 구현합니다. 패킷 페이로드에서 특정 문자열을 검색하여 매칭 여부를 판단합니다.

xt_string 구현

/* net/netfilter/xt_string.c */
static bool string_mt(const struct sk_buff *skb,
                      struct xt_action_param *par)
{
    const struct xt_string_info *conf = par->matchinfo;
    bool invert = conf->u.v1.flags & XT_STRING_FLAG_INVERT;

    return (skb_find_text((struct sk_buff *)skb,
                          conf->from_offset,
                          conf->to_offset,
                          conf->config) != UINT_MAX) ^ invert;
}

규칙 초기화 (checkentry)

static int string_mt_check(const struct xt_mtchk_param *par)
{
    struct xt_string_info *conf = par->matchinfo;

    /* 알고리즘 선택: "kmp"(기본) 또는 "bm" */
    conf->config = textsearch_prepare(conf->algo,
                        conf->pattern,
                        conf->patlen,
                        GFP_KERNEL,
                        TS_AUTOLOAD);
    if (IS_ERR(conf->config))
        return PTR_ERR(conf->config);
    return 0;
}

nf_conntrack 활용

netfilter 연결 추적(conntrack) 헬퍼는 텍스트 검색을 사용하여 Application Layer Gateway(ALG) 프로토콜을 파싱합니다. FTP, SIP, IRC 등의 프로토콜에서 데이터 연결에 필요한 주소/포트 정보를 페이로드에서 추출합니다.

FTP 헬퍼 사례

FTP의 PORT/PASV 명령은 데이터 연결을 위한 IP 주소와 포트를 ASCII 텍스트로 전송합니다. conntrack FTP 헬퍼는 이 텍스트를 검색하여 관련(related) 연결을 기대(expect)합니다.

/* nf_conntrack_ftp.c — 텍스트 검색 활용 (개념) */
static struct ts_config *ts_port;
static struct ts_config *ts_pasv;

/* 모듈 초기화 */
ts_port = textsearch_prepare("kmp", "PORT ", 5,
                             GFP_KERNEL, TS_AUTOLOAD);
ts_pasv = textsearch_prepare("kmp", "227 ", 4,
                             GFP_KERNEL, TS_AUTOLOAD);

/* 패킷 처리 시 */
unsigned int pos = skb_find_text(skb, dataoff, skb->len, ts_port);
if (pos != UINT_MAX) {
    /* PORT 명령 발견 → 주소/포트 파싱 후 expect 생성 */
    parse_port_command(skb, pos);
}

SIP 헬퍼 사례

SIP(Session Initiation Protocol) 헬퍼는 INVITE/BYE/ACK 메시지와 SDP(Session Description Protocol) 본문에서 미디어 스트림의 IP 주소와 포트를 추출합니다. NAT 환경에서 SIP 통화가 정상 작동하려면 이 텍스트 검색이 필수적입니다.

/* nf_conntrack_sip.c — SIP 헤더 검색 (개념) */
static struct ts_config *ts_sip_via;
static struct ts_config *ts_sip_contact;
static struct ts_config *ts_sip_content;

/* 모듈 초기화 */
ts_sip_via = textsearch_prepare("kmp", "\r\nVia:", 6,
                                GFP_KERNEL, TS_AUTOLOAD);
ts_sip_contact = textsearch_prepare("kmp", "\r\nContact:", 10,
                                    GFP_KERNEL, TS_AUTOLOAD);
ts_sip_content = textsearch_prepare("kmp", "\r\nContent-Type:", 15,
                                    GFP_KERNEL, TS_AUTOLOAD);

/* 패킷 처리 시 — Via 헤더에서 주소 추출 */
unsigned int pos = skb_find_text(skb, dataoff, datalen,
                                 ts_sip_via);
if (pos != UINT_MAX) {
    /* Via: SIP/2.0/UDP 192.168.1.100:5060 파싱 */
    parse_via_header(skb, pos + 6, &addr, &port);
    /* NAT 변환을 위한 expect 등록 */
    nf_ct_expect_init(exp, NF_CT_EXPECT_CLASS_DEFAULT,
                       nf_ct_l3num(ct), &addr, ...);
}

conntrack 헬퍼 보안 고려

# 자동 헬퍼 할당 비활성화 (수동 설정으로 전환)
echo 0 > /proc/sys/net/netfilter/nf_conntrack_helper

# 필요한 헬퍼만 명시적으로 할당 (nftables)
nft add ct helper inet filter ftp-helper \
  { type "ftp" protocol tcp \; }
nft add rule inet filter input \
  tcp dport 21 ct helper set "ftp-helper"

# 기대(expect) 테이블 모니터링
conntrack -E expect   # 실시간 expect 이벤트 추적
conntrack -L expect   # 현재 expect 목록 조회

iptables/nftables 설정

실제 운영 환경에서 텍스트 검색을 활용하는 방법을 iptables와 nftables 예제로 설명합니다.

iptables -m string 기본 문법

# KMP 알고리즘(기본)으로 HTTP GET 요청에서 "/admin" 검색
iptables -A INPUT -p tcp --dport 80 \
  -m string --string "/admin" --algo kmp \
  --from 40 --to 200 -j DROP

# Boyer-Moore로 대소문자 무시 검색
iptables -A INPUT -p tcp --dport 80 \
  -m string --string "password" --algo bm \
  --icase -j LOG --log-prefix "[PASSWD_LEAK] "

# 16진수 패턴 매칭 (바이너리 시그니처)
iptables -A FORWARD -m string \
  --hex-string "|7f 45 4c 46|" --algo kmp \
  -j DROP   # ELF 바이너리 전송 차단

# --from/--to로 검색 범위 제한 (성능 최적화)
iptables -A INPUT -p tcp --dport 443 \
  -m string --string "TLS_RSA" --algo bm \
  --from 0 --to 100 -j LOG

nftables 설정

# nftables에서 텍스트 검색 (nft expression)
nft add rule inet filter input \
  tcp dport 80 \
  meta l4proto tcp \
  @th,160,1280 "GET /admin" \
  drop

# payload match를 활용한 HTTP 메서드 필터링
nft add rule inet filter input \
  tcp dport 80 \
  tcp payload offset 0 length 3 "GET" \
  counter accept

실전 DPI 규칙 예시

# SQL Injection 기본 방어 (여러 패턴 체인)
iptables -A INPUT -p tcp --dport 80 \
  -m string --string "UNION SELECT" --algo kmp --icase \
  -j DROP

iptables -A INPUT -p tcp --dport 80 \
  -m string --string "OR 1=1" --algo kmp --icase \
  -j DROP

# DNS 터널링 탐지 (긴 하위 도메인)
iptables -A OUTPUT -p udp --dport 53 \
  -m string --hex-string "|3f|" --algo bm \
  -m length --length 200: -j LOG --log-prefix "[DNS_TUNNEL] "

xt_string 옵션 상세

iptables 규칙 최적화 전략

# 나쁜 예: 모든 패킷에 string 검색 적용
iptables -A INPUT -m string --string "malware" --algo kmp -j DROP
iptables -A INPUT -p tcp --dport 80 -j ACCEPT

# 좋은 예: 먼저 포트로 좁히고, 해당 트래픽에만 string 검색
iptables -A INPUT -p tcp --dport 80 -j WEB_INSPECT
iptables -A WEB_INSPECT -m conntrack --ctstate ESTABLISHED -j ACCEPT
iptables -A WEB_INSPECT -m string --string "malware" --algo kmp \
  --from 40 --to 500 -j DROP
iptables -A WEB_INSPECT -j ACCEPT

nftables와 payload 표현식

nftables에서는 @th(transport header) 또는 @ih(inner header) 표현식을 사용하여 더 정밀한 페이로드 검색이 가능합니다. nftables의 집합(set)과 결합하면 다수의 패턴을 효율적으로 매칭할 수 있습니다.

# nftables 연결 추적 헬퍼 명시적 할당
nft add ct helper inet filter ftp-helper \
  { type "ftp" protocol tcp \; }
nft add rule inet filter input \
  tcp dport 21 ct helper set "ftp-helper"

# nftables 문자열 매칭 (rawpayload 사용)
nft add rule inet filter input \
  tcp dport 80 \
  tcp flags syn / syn,ack \
  counter accept

nft add rule inet filter input \
  tcp dport 80 \
  meta l4proto tcp \
  @th,160,800 "GET /admin" \
  counter drop

성능 벤치마크

세 알고리즘의 성능은 패턴 길이, 텍스트 특성, 매칭 빈도에 따라 크게 달라집니다. 아래는 일반적인 네트워크 페이로드(HTTP 트래픽)에서의 벤치마크 경향입니다.

벤치마크 분석 상세

패턴 길이별 성능 특성을 더 자세히 분석합니다.

softirq 경로에서의 영향

netfilter에서 텍스트 검색은 주로 softirq 컨텍스트에서 실행됩니다. 패킷당 검색 시간이 길어지면 softirq 처리 시간이 증가하여 네트워크 지연(latency)에 직접적 영향을 줍니다. 다수의 string 규칙이 체인에 있으면 각 규칙마다 전체 페이로드를 스캔해야 하므로, 규칙 수에 비례하여 CPU 사용량이 증가합니다.

# softirq CPU 사용량 모니터링
mpstat -P ALL 1 | grep -E "CPU|soft"

# NET_RX softirq에서 textsearch 오버헤드 확인
perf top -e cpu-clock -g --symbol-filter="kmp_find\|bm_find\|string_mt"

주요 커널 호출자

텍스트 검색 프레임워크를 사용하는 커널 서브시스템은 주로 네트워킹 관련 코드에 집중되어 있습니다.

TC ematch 텍스트 분류

Traffic Control(TC)의 ematch 모듈도 텍스트 검색을 활용하여 패킷을 분류합니다. 이를 통해 특정 페이로드 패턴을 가진 트래픽에 QoS 정책을 적용할 수 있습니다.

# TC ematch로 텍스트 기반 트래픽 분류
tc filter add dev eth0 parent 1:0 protocol ip \
  u32 match ip dport 80 0xffff \
  action ematch text("video", kmp) \
  flowid 1:10   # video 트래픽을 1:10 큐로 분류

em_text 내부 구현

net/sched/em_text.c는 TC ematch 프레임워크의 텍스트 매칭 모듈입니다. xt_string과 유사하게 textsearch_prepare()로 초기화하고 skb_find_text()로 검색합니다.

/* net/sched/em_text.c — 핵심 매칭 함수 */
static int em_text_match(struct sk_buff *skb,
                        struct tcf_ematch *m,
                        struct tcf_pkt_info *info)
{
    struct text_match *tm = EM_TEXT_PRIV(m);
    int from, to;

    from = tcf_get_base_ptr(skb, tm->from_layer)
           + tm->from_offset;
    to = tcf_get_base_ptr(skb, tm->to_layer)
         + tm->to_offset;

    return (skb_find_text(skb, from, to,
                          tm->config) != UINT_MAX);
}

텍스트 검색 활용 가능 영역

현재 커널에서는 네트워킹 서브시스템이 주요 사용처이지만, 텍스트 검색 프레임워크는 범용적으로 설계되어 있어 다음 영역에서도 활용 가능합니다.

• 보안 모듈 — LSM에서 파일 내용 기반 접근 제어(Access Control)
• 감사(audit) — 시스템 콜(System Call) 인자 문자열 패턴 매칭
• 파일 시스템 — 파일 내용 검색 (커널 공간에서의 grep)
• 디바이스 드라이버 — 펌웨어(Firmware) 응답 파싱, AT 명령 처리

구현 상세

텍스트 검색 프레임워크의 내부 구현에서 주요한 설계 결정과 구현 세부사항을 분석합니다.

모듈 등록과 자동 로드

/* lib/ts_kmp.c — 모듈 초기화 */
static struct ts_ops kmp_ops = {
    .name       = "kmp",
    .find       = kmp_find,
    .init       = kmp_init,
    .get_pattern     = kmp_get_pattern,
    .get_pattern_len = kmp_get_pattern_len,
    .owner      = THIS_MODULE,
};

static int __init init_kmp(void)
{
    return textsearch_register(&kmp_ops);
}

static void __exit exit_kmp(void)
{
    textsearch_unregister(&kmp_ops);
}

module_init(init_kmp);
module_exit(exit_kmp);
MODULE_ALIAS("ts_kmp");

MODULE_ALIAS("ts_kmp")은 request_module("ts_kmp")가 호출될 때 이 모듈을 자동으로 찾을 수 있게 합니다.

slab 할당과 메모리 레이아웃

/* textsearch_prepare() 내부 할당 흐름 */
struct ts_config *textsearch_prepare(const char *algo, ...)
{
    struct ts_ops *ops;
    struct ts_config *conf;

    /* 1. 알고리즘 이름으로 ts_ops 찾기 */
    ops = lookup_ts_algo(algo);
    if (!ops && flags & TS_AUTOLOAD) {
        request_module("ts_%s", algo);
        ops = lookup_ts_algo(algo);
    }

    /* 2. ops->init()이 ts_config + private data 할당 */
    conf = ops->init(pattern, len, gfp_mask, flags);
    conf->ops = ops;

    return conf;
}

RCU 보호

전역 ts_ops_list는 list_add_tail_rcu()/list_del_rcu()로 관리됩니다. 검색 중인(hot path) textsearch_find()는 RCU 읽기 측이므로 락 없이 ts_ops에 접근할 수 있습니다. 알고리즘 등록/해제는 ts_mod_lock spinlock으로 직렬화(Serialization)됩니다.

flags 비트 필드

#define TS_AUTOLOAD    1  /* 알고리즘 모듈 자동 로드 */
#define TS_IGNORECASE  2  /* 대소문자 무시 (icase) */

TS_IGNORECASE가 설정되면 패턴과 텍스트를 비교할 때 tolower()를 적용합니다. iptables --icase 옵션이 이 플래그를 활성화합니다.

get_next_block 콜백 메커니즘

get_next_block()은 텍스트 검색 프레임워크의 핵심 추상화입니다. 이 콜백을 통해 알고리즘은 데이터 소스가 연속 메모리인지, skb fragment 체인인지 알 필요 없이 동일한 방식으로 데이터를 순회합니다.

/* 연속 메모리 버퍼용 get_next_block */
static unsigned int simple_get_next_block(
    unsigned int consumed,
    const u8 **dst,
    struct ts_config *conf,
    struct ts_state *state)
{
    struct ts_linear_state *st = (struct ts_linear_state *)state->cb;

    if (consumed >= st->len)
        return 0;  /* 데이터 소진 */

    *dst = st->data + consumed;
    return st->len - consumed;
}

/* skb용 get_next_block — skb_seq_read() 활용 */
static unsigned int skb_ts_get_next_block(
    unsigned int consumed,
    const u8 **dst,
    struct ts_config *conf,
    struct ts_state *state)
{
    return skb_seq_read(consumed, dst,
                         TS_SKB_CB(state));
}

모듈 참조 카운트(Reference Count)

textsearch_prepare()는 알고리즘 모듈의 참조 카운트를 증가시키고(try_module_get()), textsearch_destroy()에서 감소시킵니다(module_put()). 이를 통해 검색 설정이 활성 상태인 동안 알고리즘 모듈이 언로드되는 것을 방지합니다.

/* textsearch_prepare() 내부 */
if (!try_module_get(ops->owner))
    return ERR_PTR(-EBUSY);

/* textsearch_destroy() 내부 */
module_put(conf->ops->owner);

Kconfig 옵션

/* lib/Kconfig (관련 설정) */
config TEXTSEARCH
    bool

config TEXTSEARCH_KMP
    tristate "Knuth-Morris-Pratt"
    select TEXTSEARCH

config TEXTSEARCH_BM
    tristate "Boyer-Moore"
    select TEXTSEARCH

config TEXTSEARCH_FSM
    tristate "Finite state machine"
    select TEXTSEARCH

TEXTSEARCH는 bool 타입으로 직접 선택할 수 없고, 알고리즘 모듈이 선택될 때 자동으로 활성화됩니다. xt_string은 CONFIG_NETFILTER_XT_MATCH_STRING으로 활성화하며, 이것이 TEXTSEARCH_KMP를 자동 선택합니다.

ts_config_priv 매크로(Macro)

알고리즘별 private 데이터에 접근하는 표준 방법은 ts_config_priv() 인라인 함수(Inline Function)입니다.

/* include/linux/textsearch.h */
static inline void *ts_config_priv(struct ts_config *conf)
{
    return ((u8 *)conf + TS_PRIV_ALIGN(sizeof(*conf)));
}

/* 사용 예: KMP의 private 데이터 접근 */
struct ts_kmp *kmp = ts_config_priv(conf);
/* kmp->pattern, kmp->prefix_tbl 등에 접근 */

TS_PRIV_ALIGN은 private 데이터가 올바르게 정렬되도록 ts_config 크기를 ALIGNOF(unsigned long) 경계에 맞춥니다. 이를 통해 알고리즘의 전처리 테이블이 정렬되지 않은 메모리 접근(unaligned access)으로 인한 성능 저하를 방지합니다.

에러 처리 패턴

/* textsearch_prepare() 에러 처리 모범 사례 */
struct ts_config *conf;
conf = textsearch_prepare("kmp", pattern, len,
                          GFP_KERNEL, TS_AUTOLOAD);
if (IS_ERR(conf)) {
    switch (PTR_ERR(conf)) {
    case -ENOENT:
        pr_err("algorithm not found\n");
        break;
    case -ENOMEM:
        pr_err("memory allocation failed\n");
        break;
    case -EINVAL:
        pr_err("invalid pattern\n");
        break;
    }
    return PTR_ERR(conf);
}

디버깅(Debugging) 가이드

텍스트 검색 관련 문제를 진단하는 방법과 도구를 설명합니다.

iptables 규칙 확인

# 현재 string 매칭 규칙 확인
iptables -L -v -n | grep "STRING match"

# 상세 규칙 정보 (알고리즘, 패턴, 범위)
iptables -L INPUT -v -n --line-numbers

# 규칙별 패킷/바이트 카운터로 매칭 빈도 확인
iptables -L -v -n -x

# 실시간 매칭 모니터링
watch -n 1 'iptables -L INPUT -v -n -x | grep "STRING"'

커널 모듈 상태 확인

# textsearch 모듈 로드 상태
lsmod | grep ts_

# 예상 출력:
# ts_kmp                  16384  1 xt_string
# ts_bm                   16384  0

# xt_string 모듈 의존성
modinfo xt_string
modinfo ts_kmp

# 모듈 수동 로드 (자동 로드 실패 시)
modprobe ts_kmp
modprobe ts_bm
modprobe xt_string

성능 프로파일링(Profiling)

# perf로 textsearch 함수 프로파일링
perf record -g -a -- sleep 10
perf report --symbol-filter="textsearch\|kmp_find\|bm_find"

# ftrace로 함수 추적
echo 1 > /sys/kernel/debug/tracing/events/nf_tables/enable
echo "kmp_find bm_find" > /sys/kernel/debug/tracing/set_ftrace_filter
echo function > /sys/kernel/debug/tracing/current_tracer
cat /sys/kernel/debug/tracing/trace_pipe

# BPF를 활용한 상세 지연 분석
# bpftrace -e 'kprobe:kmp_find { @start = nsecs; }
#              kretprobe:kmp_find { @latency = hist(nsecs - @start); }'

textsearch 설정 디버깅 코드

/* 커널 모듈에서 textsearch 동작 확인 */
static void test_textsearch(void)
{
    struct ts_config *conf;
    struct ts_state state;
    const char *text = "Hello World Hello";
    unsigned int pos;

    conf = textsearch_prepare("kmp", "Hello", 5,
                              GFP_KERNEL, TS_AUTOLOAD);
    if (IS_ERR(conf)) {
        pr_err("textsearch_prepare failed: %ld\n",
               PTR_ERR(conf));
        return;
    }

    /* get_next_block을 간단한 버퍼 반복자로 설정 */
    textsearch_find_continuous(conf, &state,
                               text, strlen(text));

    pos = textsearch_find(conf, &state);
    pr_info("First match at: %u\n", pos);  /* 0 */

    pos = textsearch_next(conf, &state);
    pr_info("Next match at: %u\n", pos);   /* 12 */

    pos = textsearch_next(conf, &state);
    pr_info("No more: %u\n", pos);        /* UINT_MAX */

    textsearch_destroy(conf);
}

자주 발생하는 문제와 해결

textsearch 관련 커널 로그 확인

# textsearch 관련 커널 메시지 확인
dmesg | grep -i "textsearch\|ts_kmp\|ts_bm\|xt_string"

# netfilter LOG 타겟으로 매칭 상세 정보 수집
iptables -A INPUT -p tcp --dport 80 \
  -m string --string "/admin" --algo kmp \
  -j LOG --log-prefix "[TS_MATCH] " --log-level 4

# LOG 출력 확인
journalctl -k | grep "TS_MATCH"

# NFLOG로 유저 공간에서 패킷 상세 분석
iptables -A INPUT -p tcp --dport 80 \
  -m string --string "/admin" --algo kmp \
  -j NFLOG --nflog-group 1

# ulogd 또는 tcpdump로 NFLOG 패킷 수집
tcpdump -i nflog:1 -w /tmp/matched_packets.pcap

KMP 알고리즘 심층 분석

KMP(Knuth-Morris-Pratt) 알고리즘의 정확성과 시간 복잡도를 수학적으로 증명하고, 실패 함수의 오토마톤 관점 해석, 잠재 함수(potential function) 기반의 상각 분석, 그리고 최악 사례 패턴에서도 O(n+m)을 보장하는 원리를 심층 분석합니다.

실패 함수의 수학적 정의와 정확성 증명

패턴 P[0..m-1]에 대해 실패 함수 F[q]는 다음과 같이 정의됩니다:

F[q] = max { k : k < q ∧ P[0..k-1] = P[q-k+1..q] }

즉, P[0..q]의 진접두사(proper prefix)이면서 동시에 접미사인
최대 길이 문자열의 길이입니다.

예시: 패턴 "ABABAC" (m=6)
  q=0: F[0] = 0  (단일 문자, 진접두사 없음)
  q=1: F[1] = 0  ("AB" → 접두사=접미사인 것 없음)
  q=2: F[2] = 1  ("ABA" → "A" = "A")
  q=3: F[3] = 2  ("ABAB" → "AB" = "AB")
  q=4: F[4] = 3  ("ABABA" → "ABA" = "ABA")
  q=5: F[5] = 0  ("ABABAC" → 없음)

잠재 함수 기반 상각 분석 (O(n+m) 증명)

KMP의 검색 단계에서 텍스트 위치 i와 패턴 위치 q가 동시에 사용됩니다. 잠재 함수 Φ = q로 정의하면:

잠재 함수: Φ = q (현재 패턴에서 매칭된 위치)

Case 1: P[q] == T[i] (일치)
  - 실제 비용: 1 (비교 1회)
  - Φ 변화: +1 (q가 1 증가)
  - 상각 비용: 1 + 1 = 2

Case 2: P[q] != T[i], q > 0 (불일치, 실패 링크 따라감)
  - 실제 비용: 0 (비교 없이 q만 조정)
  - Φ 변화: -(q - F[q-1]) ≤ -1 (q가 감소)
  - 상각 비용: 0 + (-(q - F[q-1])) ≤ -1

Case 3: P[q] != T[i], q == 0 (불일치, 패턴 시작)
  - 실제 비용: 1 (비교 1회)
  - Φ 변화: 0
  - 상각 비용: 1

총 비용:
  - Φ는 0에서 시작하고, 0 이상을 유지하며, 최대 n만큼 증가 가능
  - Case 2의 Φ 감소 총합 ≤ Case 1의 Φ 증가 총합 ≤ n
  - 따라서 Case 2 실행 횟수 ≤ n
  - Case 1 + Case 3 실행 횟수 = n (매 실행마다 i 증가)
  - 총 비교 횟수 ≤ 2n → O(n)

icase 처리와 커널 최적화

/* lib/ts_kmp.c — 대소문자 무시 KMP 검색 */
static unsigned int kmp_find(struct ts_config *conf,
                             struct ts_state *state)
{
    struct ts_kmp *kmp = ts_config_priv(conf);
    unsigned int q = 0, text_len, consumed = state->offset;
    const u8 *text;
    const int icase = conf->flags & TS_IGNORECASE;

    while ((text_len = conf->get_next_block(consumed, &text,
                                            conf, state)) > 0) {
        for (unsigned int i = 0; i < text_len; i++) {
            u8 c = icase ? toupper(text[i]) : text[i];

            while (q > 0 && kmp->pattern[q] != c)
                q = kmp->prefix_tbl[q - 1];

            if (kmp->pattern[q] == c)
                q++;

            if (q == kmp->pattern_len) {
                state->offset = consumed + i + 1;
                return state->offset - kmp->pattern_len;
            }
        }
        consumed += text_len;
    }
    return UINT_MAX;
}

Boyer-Moore 변형과 최적화

Boyer-Moore 알고리즘의 핵심 강점은 텍스트를 건너뛸 수 있다는 점이지만, 기본 구현에는 O(nm) 최악 사례가 존재합니다. Galil Rule, Horspool 단순화, Turbo-BM 등 다양한 변형이 이를 해결하며, 리눅스 커널이 왜 특정 변형을 선택했는지 분석합니다.

Galil Rule: O(nm) 최악 사례 방지

Galil Rule은 매칭이 발견된 후 패턴의 주기(period)만큼만 비교하면 되도록 하여, 이미 비교한 접미사 부분을 다시 비교하지 않는 최적화입니다.

Galil Rule 원리:
  패턴 P의 주기(period) = m - F[m-1] (F는 KMP 실패 함수)

  매칭 성공 후:
    다음 정렬 위치에서 처음 period 문자만 비교하면 됨
    나머지 (m - period) 문자는 이전 매칭에서 이미 확인됨

  예: 패턴 "ABAB" (period = 2)
    Text:  ... A B A B A B A B ...
    1st:       A B A B  ← 매칭!
    2nd:           A B [A B]  ← "AB"만 새로 비교, "AB"는 보장됨

  → 이렇게 하면 최악 O(n) 비교로 모든 매칭 위치를 찾을 수 있음

Horspool 단순화와 커널 적용

Boyer-Moore-Horspool은 good suffix 테이블을 제거하고 bad character shift만 사용합니다. 구현이 단순하고 실전 성능이 우수합니다.

Turbo-BM 개념

Turbo-BM: 이전 매칭 시도에서 얼마나 매칭됐는지를 기억

  turbo_shift = u - v  (u: 이전 매칭 길이, v: 현재 good_suffix)
  최종 시프트 = max(good_suffix[j], bad_char[text[i]], turbo_shift)

  이렇게 하면 이미 비교한 문자를 건너뛰어 O(n) 보장
  하지만 추가 변수(u) 관리 필요 → 분기 예측 실패 증가

FSM 내부 구현 심층

FSM(유한 상태 기계) 검색 알고리즘 ts_fsm은 단순 문자열이 아닌 토큰 패턴을 매칭합니다. 각 토큰은 문자 클래스(digit, alpha, space 등) 또는 와일드카드(TS_FSM_ANY)를 나타내며, greedy/non-greedy 매칭과 백트래킹 동작을 지원합니다.

토큰 타입과 ctype 매핑

FSM 매칭 핵심 루프

/* lib/ts_fsm.c — fsm_find() 핵심 매칭 로직 (simplified) */
static unsigned int fsm_find(struct ts_config *conf,
                             struct ts_state *state)
{
    struct ts_fsm *fsm = ts_config_priv(conf);
    unsigned int consumed = state->offset;
    const u8 *text;
    unsigned int text_len;

    while ((text_len = conf->get_next_block(consumed, &text,
                                            conf, state)) > 0) {
        for (unsigned int i = 0; i < text_len; i++) {
            unsigned int match_start = consumed + i;
            int result = fsm_match_tokens(fsm, text + i,
                                          text_len - i, &i);
            if (result == FSM_MATCH) {
                state->offset = match_start;
                return match_start;
            }
            /* FSM_NOMATCH: try next start position */
        }
        consumed += text_len;
    }
    return UINT_MAX;
}

/* 토큰 하나를 매칭하는 내부 함수 */
static int match_token(struct ts_fsm_token *tok, u8 c)
{
    switch (tok->type) {
    case TS_FSM_SPECIFIC:
        return (c == tok->value);
    case TS_FSM_DIGIT:
        return isdigit(c);
    case TS_FSM_ALPHA:
        return isalpha(c);
    case TS_FSM_XDIGIT:
        return isxdigit(c);
    case TS_FSM_SPACE:
        return isspace(c);
    case TS_FSM_ANY:
        return 1;  /* 항상 매칭 */
    }
    return 0;
}

skb Fragment 횡단 검색 심층

네트워크 패킷은 sk_buff 내에서 여러 조각(fragment)으로 분산 저장됩니다. 텍스트 검색 프레임워크의 핵심 과제 중 하나는 패턴이 두 fragment의 경계를 걸쳐 있을 때도 정확히 매칭하는 것입니다. 이 섹션에서는 skb_seq_read 기반의 블록 순회와 알고리즘별 경계 처리 방식을 심층 분석합니다.

skb 데이터 구조와 fragment 종류

skb_seq_read와 get_next_block 상호작용

/* net/core/skbuff.c — skb_seq_read (simplified) */
unsigned int skb_seq_read(unsigned int consumed,
                          const u8 **data,
                          struct ts_state *st)
{
    struct sk_buff *skb = st->skb;
    unsigned int head_len = skb_headlen(skb);

    /* Phase 1: 선형 데이터 영역 */
    if (consumed < head_len) {
        *data = skb->data + consumed;
        return min(head_len - consumed, st->block_size);
    }

    /* Phase 2: paged fragments */
    consumed -= head_len;
    for (int i = 0; i < skb_shinfo(skb)->nr_frags; i++) {
        const skb_frag_t *frag = &skb_shinfo(skb)->frags[i];
        unsigned int frag_size = skb_frag_size(frag);

        if (consumed < frag_size) {
            *data = kmap_local_page(skb_frag_page(frag))
                    + skb_frag_off(frag) + consumed;
            return frag_size - consumed;
        }
        consumed -= frag_size;
    }

    /* Phase 3: frag_list (재귀적) */
    /* ... frag_list 순회 생략 ... */

    return 0;  /* 데이터 끝 */
}

다중 패턴 검색과 Aho-Corasick

현재 리눅스 커널 텍스트 검색 프레임워크는 단일 패턴 매칭만 지원합니다. 그러나 netfilter에서 여러 -m string 규칙을 사용하면 동일 패킷에 대해 다중 패턴을 순차 검색해야 하며, 이는 O(n*k) 오버헤드를 유발합니다. Aho-Corasick 알고리즘은 이 문제를 O(n+m+z)로 해결할 수 있습니다.

현재 다중 패턴 처리의 비효율성

# 3개 패턴으로 HTTP 악성 요청 탐지 — 패킷당 3번 전체 스캔
iptables -A INPUT -p tcp --dport 80 \
  -m string --string "/etc/passwd" --algo kmp -j DROP
iptables -A INPUT -p tcp --dport 80 \
  -m string --string "../../../" --algo kmp -j DROP
iptables -A INPUT -p tcp --dport 80 \
  -m string --string "<script>" --algo kmp -j DROP

# 각 규칙이 독립적으로 패킷을 전체 스캔
# 패킷 1500 bytes × 3 규칙 = 4500 bytes 분량의 비교 연산

Aho-Corasick 알고리즘 개요

Aho-Corasick은 KMP를 다중 패턴으로 확장한 알고리즘입니다. 모든 패턴으로 트라이(trie)를 구축하고, KMP의 실패 함수에 해당하는 실패 링크를 트라이 노드 간에 설정합니다.

커스텀 검색 알고리즘 구현

텍스트 검색 프레임워크의 플러그인 구조를 활용하여 새로운 검색 알고리즘을 커널 모듈로 구현할 수 있습니다. 이 섹션에서는 Rabin-Karp 롤링 해시 알고리즘을 예제로 사용하여 전체 구현 과정을 단계별로 안내합니다.

Rabin-Karp 롤링 해시 개념

완전한 ts_rk 커널 모듈

/* ts_rk.c — Rabin-Karp 텍스트 검색 알고리즘 커널 모듈 */
#include <linux/module.h>
#include <linux/textsearch.h>
#include <linux/slab.h>

#define RK_BASE      256ULL
#define RK_MOD       1000000007ULL

struct ts_rk {
    u8           *pattern;
    unsigned int patlen;
    u64          pat_hash;     /* 패턴 해시 */
    u64          high_pow;     /* RK_BASE^(patlen-1) mod RK_MOD */
};

static u64 rk_hash(const u8 *data, unsigned int len)
{
    u64 h = 0;
    for (unsigned int i = 0; i < len; i++)
        h = (h * RK_BASE + data[i]) % RK_MOD;
    return h;
}

static unsigned int rk_find(struct ts_config *conf,
                            struct ts_state *state)
{
    struct ts_rk *rk = ts_config_priv(conf);
    unsigned int consumed = state->offset;
    const u8 *text;
    unsigned int text_len;
    u64 h;
    unsigned int i;

    /* 단순화: 연속 블록 가정 (실제에는 블록 간 처리 필요) */
    text_len = conf->get_next_block(consumed, &text, conf, state);
    if (text_len < rk->patlen)
        return UINT_MAX;

    /* 초기 윈도우 해시 */
    h = rk_hash(text, rk->patlen);

    for (i = 0; i <= text_len - rk->patlen; i++) {
        if (h == rk->pat_hash) {
            /* 해시 일치 → 실제 문자 비교 (충돌 확인) */
            if (memcmp(text + i, rk->pattern, rk->patlen) == 0) {
                state->offset = consumed + i;
                return state->offset;
            }
        }
        /* 롤링 해시 업데이트 */
        if (i + rk->patlen < text_len) {
            h = (h + RK_MOD - text[i] * rk->high_pow % RK_MOD)
                % RK_MOD;
            h = (h * RK_BASE + text[i + rk->patlen]) % RK_MOD;
        }
    }
    return UINT_MAX;
}

static struct ts_config *rk_init(const void *pattern,
                                 unsigned int len,
                                 gfp_t gfp_mask,
                                 int flags)
{
    struct ts_config *conf;
    struct ts_rk *rk;

    conf = alloc_ts_config(sizeof(*rk) + len, gfp_mask);
    if (IS_ERR(conf))
        return conf;

    conf->flags = flags;
    rk = ts_config_priv(conf);
    rk->patlen  = len;
    rk->pattern = (u8 *)(rk + 1);
    memcpy(rk->pattern, pattern, len);

    /* 패턴 해시 및 high_pow 전처리 */
    rk->pat_hash = rk_hash(rk->pattern, len);
    rk->high_pow = 1;
    for (unsigned int i = 0; i < len - 1; i++)
        rk->high_pow = (rk->high_pow * RK_BASE) % RK_MOD;

    return conf;
}

static void rk_destroy(struct ts_config *conf) { }

static struct ts_ops rk_ops = {
    .name    = "rk",
    .find    = rk_find,
    .init    = rk_init,
    .destroy = rk_destroy,
    .owner   = THIS_MODULE,
};

static int __init ts_rk_init(void)
{
    return textsearch_register(&rk_ops);
}

static void __exit ts_rk_exit(void)
{
    textsearch_unregister(&rk_ops);
}

module_init(ts_rk_init);
module_exit(ts_rk_exit);
MODULE_LICENSE("GPL");
MODULE_ALIAS_TS("rk");

메모리 레이아웃과 캐시 최적화

텍스트 검색 프레임워크의 각 알고리즘은 ts_config 구조체 뒤에 private 데이터를 연속 할당합니다. 이 레이아웃이 캐시 성능에 미치는 영향을 분석합니다.

alloc_ts_config 메모리 할당

/* lib/textsearch.c — ts_config 할당 */
struct ts_config *alloc_ts_config(size_t payload,
                                  gfp_t gfp_mask)
{
    struct ts_config *conf;

    /* ts_config + payload를 하나의 kmalloc으로 할당 */
    conf = kmalloc(TS_PRIV_ALIGN(sizeof(*conf)) + payload,
                   gfp_mask);
    if (!conf)
        return ERR_PTR(-ENOMEM);

    memset(conf, 0, sizeof(*conf));
    return conf;
}

/* private 데이터 접근 */
static inline void *ts_config_priv(struct ts_config *conf)
{
    return (u8 *)conf + TS_PRIV_ALIGN(sizeof(*conf));
}

DPI 회피 기법과 대응

DPI(Deep Packet Inspection)에서 텍스트 검색을 사용할 때, 공격자는 다양한 회피 기법을 통해 패턴 매칭을 우회할 수 있습니다. IP/TCP 조각화, 인코딩 변환, 대소문자 혼합 등의 기법과 커널에서의 대응 메커니즘을 분석합니다.

회피 기법 분류와 대응

IP 조각화 회피 방어 코드

# nf_defrag_ipv4 활성화 확인 (conntrack이 자동으로 로드)
lsmod | grep nf_defrag

# conntrack 기반 재조립 보장 — string 매칭 전에 conntrack 활성화
iptables -A INPUT -m conntrack --ctstate ESTABLISHED,RELATED -j ACCEPT
iptables -A INPUT -p tcp --dport 80 \
  -m string --string "/etc/passwd" --algo kmp -j DROP

# TCP MSS 클램핑으로 과도한 분할 방지
iptables -A FORWARD -p tcp --tcp-flags SYN,RST SYN \
  -j TCPMSS --clamp-mss-to-pmtu

# 비정상 조각 차단
iptables -A INPUT -f -j DROP  # 모든 IP fragment 차단 (주의: 정상 트래픽도 차단)

TC ematch 텍스트 분류 심층

텍스트 검색 프레임워크는 netfilter뿐 아니라 TC(Traffic Control) 서브시스템의 em_text ematch에서도 활용됩니다. 이를 통해 패킷 페이로드의 텍스트 내용을 기반으로 QoS 정책을 적용할 수 있습니다.

em_text 아키텍처

em_text는 TC의 확장 매칭(extended match) 프레임워크 위에 구현됩니다. 네트워크 계층(link/network/transport)별 오프셋을 지정하여 검색 범위를 제한할 수 있습니다.

TC 텍스트 매칭 설정 예제

# HTB qdisc 설정
tc qdisc add dev eth0 root handle 1: htb default 30
tc class add dev eth0 parent 1: classid 1:10 htb rate 1mbit ceil 2mbit
tc class add dev eth0 parent 1: classid 1:20 htb rate 10mbit ceil 20mbit
tc class add dev eth0 parent 1: classid 1:30 htb rate 5mbit ceil 10mbit

# HTTP 동영상 트래픽을 저대역폭 클래스로 분류
tc filter add dev eth0 parent 1: protocol ip prio 1 \
  basic match 'text(pattern "video/mp4" from transport layer) or
               text(pattern "Content-Type: video" from transport layer)' \
  classid 1:10

# API 트래픽을 고대역폭 클래스로 분류
tc filter add dev eth0 parent 1: protocol ip prio 2 \
  basic match 'text(pattern "/api/" from transport layer)' \
  classid 1:20

# 정적 파일 요청에 rate limit 적용
tc filter add dev eth0 parent 1: protocol ip prio 3 \
  basic match 'text(pattern ".jpg" from transport layer) or
               text(pattern ".png" from transport layer)' \
  action police rate 500kbit burst 100k conform-exceed drop/continue

실전 패턴 설계

효과적인 DPI 패턴을 설계하려면 프로토콜 구조를 이해하고, 오탐(false positive)을 최소화하면서 정확한 탐지를 달성해야 합니다. --from/--to 옵션을 활용한 검색 범위 최적화와 프로토콜별 시그니처 설계 기법을 다룹니다.

프로토콜별 검색 범위 최적화

프로토콜 시그니처 테이블

오탐(False Positive) 감소 기법

# Bad: 짧은 패턴 → 오탐 다수
iptables -A INPUT -m string --string "GET" --algo bm -j DROP
# "GET"은 일반 바이너리 데이터에도 빈번하게 출현

# Good: 충분히 긴 패턴 + 범위 제한
iptables -A INPUT -p tcp --dport 80 \
  -m string --string "GET /" --algo bm \
  --from 40 --to 50 -j ACCEPT

# Better: 복합 조건 (포트 + 프로토콜 + 문자열)
iptables -A INPUT -p tcp --dport 80 \
  -m conntrack --ctstate ESTABLISHED \
  -m string --string "/wp-login.php" --algo kmp \
  --from 40 --to 200 \
  -m hashlimit --hashlimit-above 5/min --hashlimit-mode srcip \
    --hashlimit-name wp-login \
  -j DROP

# hex-string: 바이너리 프로토콜 매칭
iptables -A INPUT -p tcp \
  -m string --hex-string "|0d 0a 0d 0a|" --algo bm \
  --from 40 --to 500 \
  -j LOG --log-prefix "HTTP-HDR-END "
# \r\n\r\n — HTTP 헤더 끝 감지

커널 테스트 모듈 작성

3가지 텍스트 검색 알고리즘(KMP, BM, FSM)의 성능을 정량적으로 비교하는 커널 모듈을 작성합니다. ktime_get_ns()를 사용한 고정밀 벤치마킹과 통계 분석 방법론을 포함합니다.

완전한 벤치마크 모듈

/* ts_bench.c — textsearch 벤치마크 커널 모듈 */
#include <linux/module.h>
#include <linux/textsearch.h>
#include <linux/slab.h>
#include <linux/ktime.h>
#include <linux/random.h>

#define BENCH_ITERATIONS  10000
#define WARMUP_RUNS       5
#define TEXT_SIZE         4096

struct bench_result {
    u64 total_ns;
    u64 min_ns;
    u64 max_ns;
    int match_count;
};

static void run_bench(const char *algo,
                      const char *pattern, int patlen,
                      const u8 *text, int textlen,
                      struct bench_result *res)
{
    struct ts_config *conf;
    struct ts_state state;
    u64 start, end, elapsed;
    int i, pos;

    conf = textsearch_prepare(algo, pattern, patlen,
                              GFP_KERNEL, TS_AUTOLOAD);
    if (IS_ERR(conf)) {
        pr_err("ts_bench: prepare failed for %s\n", algo);
        return;
    }

    /* 캐시 워밍 */
    for (i = 0; i < WARMUP_RUNS; i++) {
        memset(&state, 0, sizeof(state));
        textsearch_find_continuous(conf, &state, text, textlen);
    }

    /* 본 측정 */
    res->total_ns = 0;
    res->min_ns = U64_MAX;
    res->max_ns = 0;
    res->match_count = 0;

    preempt_disable();
    local_irq_disable();

    for (i = 0; i < BENCH_ITERATIONS; i++) {
        memset(&state, 0, sizeof(state));
        start = ktime_get_ns();
        pos = textsearch_find_continuous(conf, &state,
                                         text, textlen);
        end = ktime_get_ns();

        elapsed = end - start;
        res->total_ns += elapsed;
        if (elapsed < res->min_ns) res->min_ns = elapsed;
        if (elapsed > res->max_ns) res->max_ns = elapsed;
        if (pos != UINT_MAX) res->match_count++;
    }

    local_irq_enable();
    preempt_enable();

    pr_info("ts_bench [%s] pattern=%d text=%d: "
            "avg=%llu ns, min=%llu ns, max=%llu ns, "
            "matches=%d/%d\n",
            algo, patlen, textlen,
            res->total_ns / BENCH_ITERATIONS,
            res->min_ns, res->max_ns,
            res->match_count, BENCH_ITERATIONS);

    textsearch_destroy(conf);
}

static int __init ts_bench_init(void)
{
    u8 *text;
    struct bench_result res;
    const char *algos[] = { "kmp", "bm" };
    int a;

    /* 테스트 텍스트 생성 (끝 부분에 패턴 삽입) */
    text = kmalloc(TEXT_SIZE, GFP_KERNEL);
    if (!text) return -ENOMEM;
    get_random_bytes(text, TEXT_SIZE);
    memcpy(text + TEXT_SIZE - 16,
           "HELLO WORLD TEST", 16);

    pr_info("ts_bench: === Starting benchmarks ===\n");

    /* 시나리오 1: 짧은 패턴 (4바이트) */
    for (a = 0; a < 2; a++)
        run_bench(algos[a], "TEST", 4,
                  text, TEXT_SIZE, &res);

    /* 시나리오 2: 긴 패턴 (16바이트) */
    for (a = 0; a < 2; a++)
        run_bench(algos[a], "HELLO WORLD TEST", 16,
                  text, TEXT_SIZE, &res);

    /* 시나리오 3: 비매칭 패턴 */
    for (a = 0; a < 2; a++)
        run_bench(algos[a], "ZZZZZZZZ", 8,
                  text, TEXT_SIZE, &res);

    pr_info("ts_bench: === Benchmarks complete ===\n");

    kfree(text);
    return -EAGAIN;  /* 모듈 로드 실패시켜 자동 언로드 */
}

static void __exit ts_bench_exit(void) { }

module_init(ts_bench_init);
module_exit(ts_bench_exit);
MODULE_LICENSE("GPL");

예상 벤치마크 결과

사용자 공간 IDS/IPS와 비교

커널 textsearch 기반 패턴 매칭과 Snort, Suricata, nDPI 같은 사용자 공간 IDS/IPS를 아키텍처, 성능, 기능, 안전성 측면에서 비교합니다. 각 접근 방식의 장단점과 적절한 사용 시나리오를 분석합니다.

아키텍처 비교

기능 비교 테이블

XDP/eBPF: 커널-사용자 공간 사이의 대안

/* XDP 기반 텍스트 매칭 개념 코드 (eBPF) */
SEC("xdp")
int xdp_text_match(struct xdp_md *ctx)
{
    void *data = (void *)(long)ctx->data;
    void *data_end = (void *)(long)ctx->data_end;
    struct ethhdr *eth = data;
    struct iphdr *ip;
    struct tcphdr *tcp;
    unsigned char *payload;
    int payload_len;

    /* 헤더 경계 검증 (verifier 통과 필수) */
    if (data + sizeof(*eth) > data_end)
        return XDP_PASS;

    ip = data + sizeof(*eth);
    if ((void *)ip + sizeof(*ip) > data_end)
        return XDP_PASS;

    tcp = (void *)ip + ip->ihl * 4;
    if ((void *)tcp + sizeof(*tcp) > data_end)
        return XDP_PASS;

    payload = (void *)tcp + tcp->doff * 4;
    payload_len = data_end - (void *)payload;

    /* 간단한 패턴 매칭 (verifier 친화적 루프) */
    if (payload_len >= 4 && payload + 4 <= data_end) {
        if (payload[0] == 'G' && payload[1] == 'E' &&
            payload[2] == 'T' && payload[3] == ' ')
            return XDP_DROP;  /* HTTP GET 차단 */
    }

    return XDP_PASS;
}

관련 문서

텍스트 검색 프레임워크와 관련된 주제를 더 깊이 이해하려면 다음 문서를 참고하세요.

• Netfilter — netfilter 프레임워크 전체 구조, 훅 포인트, 체인/테이블
• 네트워킹 스택 — sk_buff 구조, 패킷 수신/송신 경로
• 해시 테이블(Hash Table) — 커널 자료구조, 해싱 알고리즘
• 커널 모듈 — 모듈 로드/언로드, MODULE_ALIAS, request_module
• 동기화 기법 — spinlock, RCU 등 텍스트 검색 내부에서 사용하는 동기화
• 메모리 관리(Memory Management) — slab 할당, kmalloc, GFP 플래그
• RCU — Read-Copy-Update, ts_ops_list 보호에 사용
• 커널 보안 — 커널 보안 개요, DPI와 패킷 필터링 보안 측면
• eBPF 보안 — eBPF 프로그래밍과 네트워크 필터링, XDP 고속 패킷 처리
• GSO/GRO — 세그먼테이션 오프로드, super-packet과 skb fragment 관계
• TC (트래픽 제어) — 트래픽 제어, ematch 텍스트 분류, qdisc 계층

참고 자료

• include/linux/textsearch.h — 텍스트 검색 프레임워크의 핵심 헤더로, ts_config·ts_state·ts_ops 구조체와 API 선언을 포함합니다
• lib/textsearch.c — 텍스트 검색 프레임워크의 코어 구현으로, textsearch_find·textsearch_prepare·textsearch_register 등 공통 API를 제공합니다
• lib/ts_kmp.c — Knuth-Morris-Pratt 알고리즘 기반 텍스트 검색 모듈(ts_kmp) 구현입니다
• lib/ts_bm.c — Boyer-Moore 알고리즘 기반 텍스트 검색 모듈(ts_bm) 구현으로, 긴 패턴에서 높은 성능을 발휘합니다
• lib/ts_fsm.c — 유한 상태 기계(FSM) 기반 텍스트 검색 모듈(ts_fsm) 구현으로, 와일드카드 패턴을 지원합니다
• net/netfilter/xt_string.c — netfilter 문자열 매칭 모듈로, textsearch 프레임워크를 활용하여 패킷 페이로드에서 문자열을 검색합니다
• net/netfilter/nf_conntrack_ftp.c — FTP 연결 추적 헬퍼로, textsearch를 사용하여 FTP 명령어 패턴을 매칭합니다
• 커널 문서: Text Search Infrastructure — 리눅스 커널 공식 문서의 텍스트 검색 인프라 설명입니다
• LWN.net: Generic text search infrastructure — Thomas Graf가 제안한 커널 텍스트 검색 프레임워크의 설계 배경과 구현 방향을 다룬 LWN 기사입니다
• LWN.net: The kernel string search API — 커널 내 문자열 검색 API의 사용법과 알고리즘 선택 기준을 설명하는 기사입니다
• Wikipedia: Knuth-Morris-Pratt 알고리즘 — ts_kmp 모듈이 구현하는 KMP 알고리즘의 이론적 배경으로, O(n+m) 시간 복잡도를 보장합니다
• Wikipedia: Boyer-Moore 문자열 검색 알고리즘 — ts_bm 모듈이 구현하는 Boyer-Moore 알고리즘으로, 나쁜 문자·좋은 접미사 규칙을 활용하여 긴 패턴에서 최적 성능을 달성합니다
• Wikipedia: 유한 상태 기계(FSM) — ts_fsm 모듈의 기반 이론으로, 정규 표현식과 유사한 패턴 매칭을 가능하게 합니다
• iptables-extensions: string match — iptables의 -m string 확장 모듈 사용법으로, --algo 옵션을 통해 kmp 또는 bm 알고리즘을 선택할 수 있습니다
• net/sched/em_text.c — TC(트래픽 제어)의 ematch 텍스트 분류기로, textsearch 프레임워크를 사용하여 패킷 분류를 수행합니다