Sibuna 기술 안내서 1.0.0-beta.3 문서
언어: 한국어
English简体中文한국어日本語EspañolDeutschहिन्दीالعربية
이 페이지의 내용

제VI부: 오토마톤, 트라이, 의미 기반 방화벽

마이크로초 미만의 분류를 가능하게 하는 알고리즘을 살펴봅니다. 태그가 붙은 Aho-Corasick 오토마톤, IPv4/IPv6 기수 트라이, 의미 기반 WAF의 바이트 클래스 토크나이저, 그리고 WEIGH 점수를 쓰는 선언형 정책 엔진입니다.

한 번의 순회로 여러 패턴 매칭하기

밀집 DFA로 구현한 Aho-Corasick

Sibuna에는 리터럴 패턴 집합이 두 개 있습니다. 봇 시그니처 약 40개와 공격 시그니처 약 100개입니다. 필드 하나를 패턴 \(N\)개와 하나씩 대조하면 \(O(NM)\)이 듭니다. Aho와 Corasick(1975)의 오토마톤은 실패 링크가 있는 트라이를 만든 뒤 필드를 \(O(M)\)에 한 번 훑습니다. Sibuna는 빌드할 때 실패 링크를 전이 테이블에 접어 넣으므로, 스캔은 입력 바이트마다 테이블 읽기 한 번이며 패턴 집합에 따른 분기가 없습니다. 오토마톤은 sibuna-patterns crate에 있습니다.

/// `state`(행 오프셋)에서 `byte` 하나만큼 전이합니다.
fn step(&self, state: usize, byte: u8) -> usize {
    self.table[state + usize::from(self.classes[usize::from(byte)])] as usize
}

pub fn find_first(&self, haystack: &[u8]) -> Option<Match> {
    let mut state = 0;
    for (index, &byte) in haystack.iter().enumerate() {
        state = self.step(state, byte);
        if state >= self.first_match {
            let id = self.first_output_in(self.match_state(state), self.all_tags)?;
            return Some(self.report(id, index + 1));
        }
    }
    None
}

상태는 평평한 테이블 하나 안의 행 오프셋으로 저장되므로, 한 단계는 덧셈 한 번과 읽기 한 번입니다. 상태 번호는 모든 매치 상태가 다른 모든 상태보다 뒤에 오도록 매깁니다. 그러면 매치 탐지는 first_match와의 비교 한 번으로 끝나며, 안쪽 루프에서 두 번째 테이블을 읽을 필요가 없습니다.

루트에서 G와 GP를 거쳐 GPTBot 매치 상태로, C와 Cl을 거쳐 ClaudeBot 매치 상태로 이어지는 트라이입니다. 점선으로 그린 실패 간선이 GP와 Cl에서 루트로 돌아갑니다.
그림 9 두 시그니처의 트라이 상태와 실패 간선

오토마톤의 상태 예산은 실행 시점 옵션입니다. 정책 엔진은 루트 하나에 모든 시그니처 길이의 합을 더한 수만큼만 예약하며, 이는 트라이 상태 수의 안전한 상한입니다. 이로써 예전처럼 고정 테이블이 지나치게 커지는 일을 피하면서도 바이트 클래스마다 밀집 전이를 유지합니다. 각 패턴에는 작은 범주 태그(0에서 63까지이므로 태그 집합은 64비트 워드 하나)가 붙습니다. 대소문자 접기에는 오토마톤과 함께 만드는 256개 항목의 바이트 클래스 테이블을 사용합니다. 한 글자의 대문자와 소문자는 같은 클래스를 공유하고, 어떤 패턴에도 나오지 않는 바이트는 모두 클래스 하나를 공유합니다. 그래서 테이블 한 행의 너비는 256이 아니라 서로 다른 패턴 바이트 수에 1을 더한 값입니다. 엔진의 정확한 크기와 순차 부분 문자열 탐색과의 비교는 제VIII부에 기록되어 있습니다. 순차 탐색은 같은 패턴과 같은 any-match 의미론을 사용합니다.

정규 표현식, SIMD 엔진, 그리고 선택

시그니처 단계에 쓸 세 가지 계열을 비교했습니다.

  • 백트래킹 정규 표현식(백트래킹 규칙 집합 방식)은 요청마다 수백 개의 패턴을 실행하고 매치마다 할당합니다. 가장 느린 선택지이며 오탐도 가장 많이 냅니다.
  • SIMD 리터럴 엔진(Hyperscan, Vectorscan)은 셔플 기반 니블 마스크("Teddy" 알고리즘)로 16에서 32바이트 블록을 미리 걸러 내고 후보를 오토마톤으로 검증합니다. 큰 리터럴 집합으로 긴 입력을 다룰 때 뛰어납니다. 대가는 수 메가바이트짜리 C++ 의존성, 컴파일 시점 패턴 데이터베이스, WebAssembly 타깃 미지원이며, 100바이트 정도의 입력에서는 이점도 없습니다. 필드 전체를 스캔하는 시간이 캐시 미스 한 번보다 짧기 때문입니다.
  • 밀집 Aho-Corasick과 작은 구조 토크나이저, 즉 libinjection 계보는 고정 테이블에서 정확한 선형 시간 동작을 제공하며, 바이너리 밖의 것은 아무것도 필요하지 않습니다.

Sibuna의 필드는 짧으므로 세 번째 계열이 메모리와 속도 모두에서 앞섭니다. 제VIII부는 8 KiB 본문에서 바이트당 약 1.56 ns를 기록합니다(의미 기반 스캔에 12,784.3 ns가 걸리며, benchmarks/results/primitives-latest.md의 8kb_body_semantic_scan입니다). SIMD 사전 필터가 효과를 낼 만한 워크로드는 이것 하나뿐이며, SID 0006은 이를 미결 항목으로 남겨 둡니다.

IPv4와 IPv6를 위한 기수 트라이

128비트 키 위의 이진 트라이 하나가 두 주소 계열을 모두 처리합니다. IPv6 접두사는 그대로 삽입하고, IPv4 접두사는 ::ffff:0:0/96으로 매핑하므로 /24는 깊이 120의 경로가 됩니다. 노드는 u32로 인덱싱하는 평평한 Vec 하나에 저장되며, 인덱스 0은 루트이자 "자식 없음"을 뜻합니다. 그래서 조회는 포인터 추적 없이 최대 128번의 의존 읽기입니다. 이 트라이는 sibuna-cidr crate의 PrefixTrie입니다.

IPv4 조회마다 매핑된 접두사의 96단계를 걸어 내려가면, IPv4 주소의 첫 비트에 닿기도 전에 의존 읽기 96번이 듭니다. 그래서 트라이는 초기화할 때 깊이 96의 노드를 기록해 두고 IPv4 조회를 거기서 시작합니다.

let (mut node, mut depth, mut best) = if is_ipv4_mapped(key) {
    let start = self.ipv4_root;
    let value = self.nodes[start as usize].value.as_ref();
    (start, IPV4_DEPTH, value.or(self.nodes[0].value.as_ref()))
} else {
    (0, 0, self.nodes[0].value.as_ref())
};

IPv4 주소 분류에는 32.0 ns, IPv6 주소 분류에는 79.3 ns가 걸립니다(benchmarks/results/primitives-latest.md의 ipv4_cidr_classification과 ipv6_cidr_classification). 엔진은 트라이를 두 번 참조합니다. 최종 판정인 allow/deny는 규칙 테이블보다 먼저 참조하므로 클러스터 전체의 차단이 모든 규칙에 우선하고, challenge 판정은 규칙 테이블 뒤에 참조합니다.

의미 기반 방화벽

오탐의 교훈

WAF의 첫 버전은 모든 헤더를 평평한 부분 문자열 목록과 대조했습니다. 목록에는 /*가 있었고, 모든 브라우저는 Accept: text/html,...,*/*;q=0.8을 보냅니다. 그래서 실제 브라우저가 모두 SQL 인젝션으로 분류되어 403을 받았습니다. 이 교훈이 설계의 방향을 정했습니다. 탐지기는 구조에만 반응해야 합니다. 이제 테스트 모음은 select, --, 아포스트로피가 들어 있는 댓글 본문을 포함한 완전한 Chrome 요청을 엔진에 통과시키고, 아무것도 탐지되지 않는지 확인합니다.

한 번의 스캔으로 바이트 클래스 수집하기

검사하는 필드는 한 번 스캔해 어떤 바이트 클래스가 나타나는지 모읍니다. 따옴표, =, <, 셸 구분자, %, NUL, 정규화 트리거, 연속된 공백입니다. 모든 탐지기는 다시 스캔하지 않고 이 클래스를 참조하며, 정규화한 두 번째 패스는 트리거가 보였을 때에만 실행합니다. 스캔은 바이트마다 256개 항목 테이블을 한 번 조회하며, 코드는 sibuna-policy의 WAF 모듈에 있습니다. 누산기 네 개가 OR 연쇄를 짧게 유지하고, 두 바이트 쌍(/*와 인접한 공백 두 개)은 단일 바이트가 아직 정규화를 요구하지 않았을 때에만 찾습니다.

pub(crate) fn scan(text: &[u8]) -> Classes {
    let (chunks, remainder) = text.as_chunks::<8>();
    // 누산기 네 개로 OR 연쇄를 짧게 유지해 읽기를 연달아 발행할 수 있게 합니다.
    let mut lanes = [0u16; 4];
    for chunk in chunks {
        lanes[0] |= TABLE[usize::from(chunk[0])] | TABLE[usize::from(chunk[4])];
        lanes[1] |= TABLE[usize::from(chunk[1])] | TABLE[usize::from(chunk[5])];
        lanes[2] |= TABLE[usize::from(chunk[2])] | TABLE[usize::from(chunk[6])];
        lanes[3] |= TABLE[usize::from(chunk[3])] | TABLE[usize::from(chunk[7])];
    }
    let mut bits = lanes[0] | lanes[1] | lanes[2] | lanes[3];
    for &byte in remainder {
        bits |= TABLE[usize::from(byte)];
    }
    // 바이트 쌍은 아직 어떤 단일 바이트도 정규화를 요구하지 않았을 때에만 의미가 있습니다.
    if bits & CANONICAL == 0
        && ((bits & SPACE != 0 && has_pair(text, b' ', b' '))
            || (bits & (SLASH | STAR) == SLASH | STAR && has_pair(text, b'/', b'*')))
    {
        bits |= CANONICAL;
    }
    Classes { bits }
}

탐지기

  • 시그니처. 모든 범주의 강한 시그니처는 태그가 붙은 오토마톤 하나에 있습니다. 적중하면 waf:sqli, waf:xss, waf:path-traversal, waf:rce라는 이름의 최종 deny가 됩니다.
  • SQL 인젝션. 한 번 순회하는 단어 스캐너가 영숫자 단어(최대 7바이트)를 키워드 테이블에서 찾고, or / and에서는 literal = literal 항진식이 있는지 확인합니다. id=1 or 1=1은 최종 판정입니다. 그 밖의 경우에는 따옴표 바이트가 반드시 있어야 하며, 증거 점수가 다음 중에서 4점 이상이어야 합니다. 따옴표(1), 최대 두 개의 키워드(2), 주석 표식(1), =(1)입니다. admin'--는 그 자체로 최종 판정입니다. "it's a group order from the shop"은 3점이므로 통과합니다.
  • 크로스 사이트 스크립팅. <가 있어야 합니다. 스크립트를 담을 수 있는 태그가 속성 위치의 on<event>= 속성과 함께 나타날 때 탐지합니다. onboarding=1은 해당하지 않습니다.
  • 명령 인젝션. 구분자가 있어야 합니다. ;, |, &&, $(, 백틱, 줄 바꿈 뒤에 알려진 명령 이름이 오면 탐지합니다. status ok; done | next는 통과합니다.
  • 경로 탐색. 시그니처(../, ..%2f, /etc/passwd, id_rsa, ...)와 NUL, %00입니다.

문법상 따옴표와 별표를 정당하게 포함하는 구조적 헤더(Accept*, Content-Type, Sec-*, If-*, ...)는 건너뜁니다. 경로, 쿼리, User-Agent, 그 밖의 헤더, 본문의 처음 8 KB를 검사합니다. 퍼센트 이스케이프, 더하기 기호, 주석 시작 기호, 줄일 수 있는 공백이 있는 필드는 8 KB 스택 버퍼에 정규화한 뒤 다시 검사합니다. 그래서 1%27/**/UnIoN/**/SeLeCt와 %252e%252e/는 원래의 시그니처로 접힙니다.

비용

검사 비용은 요청 수만이 아니라 엔진에 들어오는 필드와 바이트에 달려 있습니다. 벤치마크 장은 Gate, Shield, 8 KB 본문의 경우를 따로 보고합니다. 8 KB 상한은 검사 한도일 뿐, 업로드의 나머지 부분이 안전하다는 주장이 아닙니다. forward-auth를 쓰는 인그레스는 관련 요청 정보를 전달해야 합니다. 전달되지 않은 바이트는 이 프로세스가 검사할 수 없습니다.

선언형 정책 엔진

규칙은 선택적인 조건(경로 패턴, User-Agent 패턴, 헤더 최대 4개, IPv4/IPv6 CIDR 블록 최대 8개, JA4 지문 또는 접두사 하나)의 논리곱이며, 동작 ALLOW, DENY, CHALLENGE, WEIGH 중 하나와 선택적인 규칙별 난이도(작업 비트)와 알고리즘, 부호 있는 weight를 가집니다. 평가 순서는 다음과 같습니다.

  1. 의미 기반 WAF(Shield 전용): 위반은 최종 deny입니다.
  2. 평판 트라이: deny 또는 allow 접두사는 최종 판정입니다.
  3. 규칙(순서대로): 처음 일치한 최종 규칙의 결과를 반환하고, WEIGH 일치는 누적합니다.
  4. 점수: 합계가 음수이면 allow, \(\geq 40\)이면 deny, \(\geq 10\)이면 challenge이며, 임계값을 넘는 5점마다 작업 비트를 하나씩 더하되 최대 여섯 비트까지 더합니다.
  5. 정적 우회 경로, 그다음 트라이의 challenge 판정, 그다음 봇 오토마톤.
  6. 기본 동작은 정책 파일이 달리 정하지 않으면 challenge입니다.

내장 규칙은 /.well-known/*, /favicon.ico, /robots.txt, /__sibuna/*를 허용하고, CF-Worker 클라이언트와 Amazonbot을 거부하며, 모든 Mozilla User-Agent에 챌린지를 제시합니다. 브라우저 문자열은 비용 없이 위조할 수 있으므로, 이를 허용하면 게이트는 장식에 불과해집니다.

{
  "default_action": "CHALLENGE",
  "waf": true,
  "thresholds": { "challenge_at": 10, "deny_at": 40, "bits_step": 5 },
  "ip_rules": { "10.0.0.0/8": "ALLOW", "2001:db8::/32": "DENY" },
  "rules": [
    { "name": "internal-api", "path": "/api/*", "headers": { "X-Api-Key": ".*" },
    "action": "ALLOW" },
    { "name": "checkout", "path": "/checkout/*", "action": "CHALLENGE",
      "challenge": { "difficulty": 20, "algorithm": "posw" } },
    { "name": "headless", "user_agent": "Headless", "action": "WEIGH", "weight": 30 },
    { "name": "no-language", "headers": { "Accept-Language": "" },
    "action": "WEIGH", "weight": -5 }
  ]
}

따라가 보기: 유효한 세션을 지닌 인코딩된 공격

유효한 세션을 가진 클라이언트가 보낸 GET /search?q=%2527%2520OR%25201%253D1을 생각해 봅시다. 먼저 HTTP 파서가 바이트를 복사하지 않고 경로와 쿼리를 분리합니다. 로컬 제한이 실행된 다음 Shield가 요청을 검사합니다. 퍼센트 기호 때문에 필드는 정규화 대상으로 표시됩니다. 한 번 디코딩하면 %27%20OR%201%3D1이 드러나고, 두 번째 디코딩에서 ' OR 1=1이 드러납니다.

이제 토크나이저는 따옴표, 키워드 OR, 서로 같은 리터럴 피연산자를 봅니다. 거부는 최종 정책 결과입니다. 유효한 세션이 있어도 이 결과는 허용으로 바뀌지 않습니다. 세션 확인은 챌린지 결정만 해소합니다. 저장소 훅은 크기가 제한된 인시던트 레코드를 복사하고, SQL은 나중에 실행됩니다. 응답 경로는 원본 서버 연결이 유휴 상태인 동안 엔진 스냅숏을 붙잡고 있을 필요가 없습니다.