Documentación de El libro de Sibuna 1.0.0-beta.3
Idioma: Español
English简体中文한국어日本語EspañolDeutschहिन्दीالعربية
En esta página

Parte VI: Autómatas, tries y el cortafuegos semántico

Examinamos los algoritmos que permiten clasificar en menos de un microsegundo: el autómata Aho-Corasick con etiquetas, el trie radix IPv4/IPv6, los analizadores por clases de bytes del WAF semántico y el motor declarativo de políticas con puntuación WEIGH.

Búsqueda de múltiples patrones en una pasada

Aho-Corasick como DFA denso

Sibuna tiene dos conjuntos de patrones literales: unas cuarenta firmas de bots y unas cien firmas de ataques. Comparar un campo con \(N\) patrones uno a uno cuesta \(O(NM)\); el autómata de Aho y Corasick (1975) lo recorre una sola vez en \(O(M)\) tras construir un trie con enlaces de fallo. Sibuna integra los enlaces de fallo en la tabla de transición al construirla, de modo que el recorrido hace una carga de tabla por byte de entrada, sin bifurcaciones sobre el conjunto de patrones. El autómata está en el crate sibuna-patterns:

/// Avanza desde `state` (un desplazamiento de fila) con `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
}

Cada estado se guarda como el desplazamiento de su fila en una única tabla plana, así que un paso es una suma y una carga. Los estados se numeran de modo que todo estado de coincidencia va después de todos los demás; detectar una coincidencia es entonces una sola comparación con first_match, sin una segunda tabla que cargar en el bucle interno.

Un trie que va de la raíz por G y GP hasta el estado de coincidencia GPTBot, y por C y Cl hasta el estado de coincidencia ClaudeBot; las aristas de fallo discontinuas llevan de GP y de Cl de vuelta a la raíz.
Fig. 9 Estados del trie y aristas de fallo para dos firmas

El presupuesto de estados del autómata es una opción de tiempo de ejecución. El motor de políticas reserva como máximo una raíz más la suma de las longitudes de todas las firmas, una cota segura del número de estados del trie. Así evita las tablas fijas históricamente sobredimensionadas y conserva una transición densa para cada clase de bytes. Cada patrón lleva una pequeña etiqueta de categoría (de 0 a 63, de modo que un conjunto de etiquetas cabe en una palabra de 64 bits). La conversión de mayúsculas usa una tabla de clases de bytes de 256 entradas, construida junto con el autómata: la mayúscula y la minúscula de una letra comparten clase, y los bytes que no aparecen en ningún patrón comparten una sola clase, de modo que una fila de la tabla tiene tantas columnas como bytes distintos haya en los patrones más uno, en lugar de 256. La parte VIII recoge los tamaños exactos del motor y la comparación con la búsqueda secuencial de subcadenas. Esta última usa los mismos patrones y la misma semántica de cualquier coincidencia.

Expresiones regulares, motores SIMD y la elección

Para la etapa de firmas se sopesaron tres familias:

  • Las expresiones regulares con retroceso (al estilo de los conjuntos de reglas con retroceso) ejecutan cientos de patrones por petición y asignan memoria en cada coincidencia; son la opción más lenta y la más propensa a falsos positivos.
  • Los motores de literales SIMD (Hyperscan, Vectorscan) prefiltran bloques de 16 a 32 bytes con máscaras de nibbles basadas en barajado (el algoritmo "Teddy") y verifican los candidatos con autómatas. Destacan con entradas largas y conjuntos grandes de literales. El precio es una dependencia C++ de varios megabytes, una base de patrones compilada, la falta de un destino WebAssembly y, para entradas de unos cien bytes, ninguna ventaja: el campo entero se recorre en menos tiempo que un fallo de caché.
  • Aho-Corasick denso más pequeños analizadores estructurales, en la línea de libinjection, ofrece un comportamiento lineal exacto en una tabla fija y no necesita nada fuera del ejecutable.

Los campos de Sibuna son cortos, así que la tercera familia gana tanto en memoria como en velocidad; la parte VIII registra unos 1,56 ns por byte en un cuerpo de 8 KiB (el recorrido semántico tarda 12.784,3 ns, 8kb_body_semantic_scan en benchmarks/results/primitives-latest.md). Esa es la única carga de trabajo en la que un prefiltro SIMD compensaría, y el SID 0006 la mantiene como cuestión abierta.

El trie radix para IPv4 e IPv6

Un único trie binario sobre claves de 128 bits sirve a ambas familias: los prefijos IPv6 se insertan tal cual y los prefijos IPv4 se mapean a ::ffff:0:0/96, de modo que un /24 se convierte en un camino de profundidad 120. Los nodos viven en un único Vec plano indexado por u32, con el índice cero como raíz y como "sin hijo" a la vez, así que una búsqueda hace como máximo 128 cargas dependientes, sin perseguir punteros. El trie es el PrefixTrie del crate sibuna-cidr.

Recorrer los 96 niveles del prefijo mapeado en cada búsqueda IPv4 costaría 96 cargas dependientes antes de llegar al primer bit de la dirección IPv4. Por eso el trie guarda el nodo de profundidad 96 al inicializarse y empieza allí las búsquedas 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())
};

Clasificar una dirección IPv4 cuesta 32,0 ns y una dirección IPv6, 79,3 ns (ipv4_cidr_classification e ipv6_cidr_classification en benchmarks/results/primitives-latest.md). El motor consulta el trie dos veces: los veredictos terminales allow/deny antes de la tabla de reglas, de modo que un bloqueo en todo el clúster prevalece sobre cualquier regla, y los veredictos challenge después de ella.

El cortafuegos semántico

Una lección sobre falsos positivos

La primera versión del WAF comparaba una lista plana de subcadenas con todas las cabeceras. La lista contenía /*, y todo navegador envía Accept: text/html,...,*/*;q=0.8. Todos los navegadores reales se clasificaban como inyección SQL y recibían 403. La lección dio forma al diseño: un detector solo puede activarse ante estructura, y el conjunto de pruebas pasa ahora por el motor una petición completa de Chrome, incluido un cuerpo de comentario que contiene select, -- y un apóstrofo, y comprueba que sale limpia.

Clases de bytes en una pasada

Cada campo inspeccionado se recorre una vez para recoger qué clases de bytes aparecen: comillas, =, <, separadores de shell, %, NUL, señales de canonicalización y espacios dobles. Cada detector consulta las clases en lugar de volver a recorrer el campo, y la segunda pasada canonicalizada solo se ejecuta si se vio una señal. El recorrido consulta una tabla de 256 entradas por byte, en el módulo WAF de sibuna-policy. Cuatro acumuladores mantienen cortas las cadenas de OR, y los dos pares de bytes (/* y dos espacios contiguos) solo se buscan cuando ningún byte aislado ha exigido ya la canonicalización:

pub(crate) fn scan(text: &[u8]) -> Classes {
    let (chunks, remainder) = text.as_chunks::<8>();
    // Cuatro acumuladores mantienen cortas las cadenas de OR para emitir las cargas seguidas.
    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)];
    }
    // Los pares solo importan mientras ningún byte aislado haya exigido la canonicalización.
    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 }
}

Detectores

  • Firmas. Todas las firmas fuertes de todas las categorías están en un único autómata con etiquetas; una coincidencia es un deny terminal llamado waf:sqli, waf:xss, waf:path-traversal o waf:rce.
  • Inyección SQL. Un recorrido de palabras en una pasada busca cada palabra alfanumérica (de siete bytes como máximo) en la tabla de palabras clave y, ante or / and, comprueba si hay una tautología literal = literal; id=1 or 1=1 es terminal. En otro caso, es obligatorio un byte de comilla y la evidencia debe sumar al menos 4 puntos entre: comilla (1), hasta dos palabras clave (2), un marcador de comentario (1) y un = (1). admin'-- es terminal por sí solo. "it's a group order from the shop" suma 3 y pasa.
  • Cross-site scripting. Exige <; se activa cuando una etiqueta que puede alojar un script aparece junto con un atributo on<event>= en posición de atributo. onboarding=1 no cuenta.
  • Inyección de comandos. Exige un separador; se activa cuando ;, |, &&, $(, un acento grave o un salto de línea van seguidos de un nombre de comando conocido. status ok; done | next pasa.
  • Recorrido de rutas. Firmas (../, ..%2f, /etc/passwd, id_rsa, ...) además de NUL y %00.

Se omiten las cabeceras estructurales cuya gramática contiene legítimamente comillas y asteriscos (Accept*, Content-Type, Sec-*, If-*, ...); se inspeccionan la ruta, la consulta, el User-Agent, las demás cabeceras y los primeros 8 KB del cuerpo, y los campos con escapes porcentuales, signos más, inicios de comentario o espacios colapsables se canonicalizan en un búfer de pila de 8 KB y se inspeccionan de nuevo, de modo que 1%27/**/UnIoN/**/SeLeCt y %252e%252e/ se reducen a las firmas sin codificar.

Coste

El coste de la inspección depende de los campos y bytes que recibe el motor, no solo del número de peticiones. El capítulo de pruebas de rendimiento presenta por separado los casos de Gate, Shield y cuerpos de 8 KB. La cota de 8 KB es un límite de inspección, no una afirmación de que el resto de una subida sea seguro. Un proxy de entrada que use forward-auth debe pasar la información relevante de la petición; este proceso no puede inspeccionar los bytes omitidos.

El motor declarativo de políticas

Una regla es una conjunción de criterios opcionales (patrón de ruta, patrón de User-Agent, hasta cuatro cabeceras, hasta ocho bloques CIDR IPv4/IPv6, una huella o un prefijo JA4) con una acción ALLOW, DENY, CHALLENGE o WEIGH, una dificultad opcional por regla en bits de trabajo y un algoritmo, y un weight con signo. Orden de evaluación:

  1. WAF semántico (solo Shield): una infracción es un deny terminal.
  2. Trie de reputación: los prefijos deny o allow son terminales.
  3. Reglas en orden: la primera coincidencia terminal decide; las coincidencias WEIGH se acumulan.
  4. Puntuación: los totales negativos dan allow; los totales \(\geq 40\) dan deny; los totales \(\geq 10\) dan challenge con un bit de trabajo extra por cada 5 puntos por encima del umbral, hasta un máximo de seis.
  5. Rutas estáticas exentas, después los veredictos challenge del trie y después el autómata de bots.
  6. Acción por defecto: challenge, salvo que el archivo de políticas diga otra cosa.

Las reglas integradas permiten /.well-known/*, /favicon.ico, /robots.txt y /__sibuna/*, deniegan los clientes CF-Worker y Amazonbot, y desafían todo User-Agent Mozilla: falsificar una cadena de navegador no cuesta nada, así que admitirla convertiría el control de admisión en un adorno.

{
  "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 }
  ]
}

Traza resuelta: un ataque codificado con una sesión válida

Consideremos GET /search?q=%2527%2520OR%25201%253D1 desde un cliente con una sesión válida. Primero, el analizador HTTP separa la ruta y la consulta sin copiar sus bytes. Se aplican los límites locales y después Shield inspecciona la petición. El signo de porcentaje marca el campo para canonicalizarlo. Una pasada de decodificación deja al descubierto %27%20OR%201%3D1; una segunda, ' OR 1=1.

El analizador ve ahora una comilla, la palabra clave OR y operandos literales iguales. Una denegación es un resultado terminal de la política. La sesión válida no la convierte en un permiso: la comprobación de sesión solo resuelve una decisión de desafío. El gancho de almacenamiento copia un registro de incidente acotado; el SQL se ejecuta más tarde. El camino de la respuesta no necesita retener la instantánea del motor mientras una conexión con el origen está inactiva.