💻 computer science

Towards the Systematic Testing of Regular Expression Engines

O artigo apresenta o ReTest, um framework que combina fuzzing consciente de gramática e testes metamórficos baseados em álgebra de Kleene para realizar testes sistemáticos e independentes de dialeto em motores de expressões regulares, superando as limitações das abordagens atuais e identificando novas vulnerabilidades de segurança.

Autores originais: Berk Çakar, Dongyoon Lee, James C. Davis

Publicado 2026-03-03

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Berk Çakar, Dongyoon Lee, James C. Davis

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que as Expressões Regulares (ou "Regex") são como receitas de bolo que os programadores usam para encontrar padrões específicos em textos. Por exemplo, uma receita pode dizer: "Encontre qualquer e-mail que termine em .com".

O problema é que essas receitas são executadas por "cozinheiros" chamados Motores de Regex. Existem muitos desses motores (alguns vêm com a linguagem de programação, outros são bibliotecas externas). O artigo que você enviou fala sobre como esses "cozinheiros" às vezes cometem erros: podem queimar o bolo (travar o sistema), envenenar a cozinha (vulnerabilidades de segurança) ou simplesmente dizer que o bolo está pronto quando na verdade está cru (resposta errada).

Os autores, da Universidade Purdue e da Stony Brook, criaram um novo método chamado ReTest para testar esses motores de forma mais inteligente. Vamos explicar como funciona usando analogias do dia a dia:

1. O Problema: Como testar um "cozinheiro" sem uma receita perfeita?

Atualmente, testar esses motores é como tentar adivinhar se um cozinheiro é bom de duas formas ruins:

O Método "Comparação Cega" (Teste Diferencial): Você pede para dois cozinheiros diferentes fazerem o mesmo prato e compara o resultado. Se um faz um bolo de chocolate e o outro de baunilha, você acha que um deles errou.
- O problema: Às vezes, eles são de culturas diferentes! Um cozinheiro pode ser brasileiro e o outro japonês. O brasileiro usa açúcar, o japonês usa adoçante. Ambos estão "certos" segundo a cultura deles, mas o teste acha que há um erro. Isso gera muitos "falsos positivos".
O Método "Jogar Farinha Aleatória" (Fuzzing Tradicional): Você joga ingredientes aleatórios na mesa (leite, areia, sapatos, farinha) para ver se o cozinheiro quebra a panela.
- O problema: A maioria dos ingredientes jogados é lixo (sintaticamente inválida). O cozinheiro nem começa a cozinhar; ele apenas diz "Isso não é comida" e descarta. Você nunca vê se ele sabe cozinhar de verdade, apenas se ele sabe dizer "não".

2. A Solução: O ReTest (O "Chefe de Cozinha" Inteligente)

Os autores criaram o ReTest, que combina duas técnicas inteligentes para resolver esses problemas:

A. O "Cozinheiro que Entende a Receita" (Fuzzing Consciente de Gramática)

Em vez de jogar ingredientes aleatórios, o ReTest usa uma biblioteca de receitas reais (mais de 500.000 receitas do mundo real).

Ele pega uma receita válida.
Em vez de jogar areia, ele faz substituições inteligentes. Se a receita diz "adicionar 2 ovos", ele pode trocar por "adicionar 3 ovos" ou "adicionar 1 ovo e 1 clara", mas mantém a estrutura da receita.
Analogia: É como um editor de texto que sabe que você não pode trocar um "ovo" por um "carro" em uma receita, mas pode trocar "ovo" por "ovo de codorna". Isso garante que o "cozinheiro" (o motor) realmente execute a lógica de cozimento, não apenas rejeite o pedido.

B. O "Teste de Lógica Interna" (Teste Metamórfico)

Como não temos uma "receita oficial universal" (já que cada motor tem seu próprio estilo), como saber se o resultado está certo?

O ReTest usa leis da matemática (Álgebra de Kleene) que são verdadeiras para qualquer receita, não importa o estilo.
Exemplo: Se você tem uma receita que diz "Faça o bolo 2 vezes", e outra que diz "Faça o bolo 1 vez e depois faça de novo", o resultado final deve ser o mesmo.
O sistema pega uma receita, aplica uma transformação matemática (que deveria não mudar o resultado) e roda no mesmo motor. Se o motor disser que o resultado mudou, ele encontrou um erro.
Analogia: É como pedir para o cozinheiro: "Faça o bolo. Agora, faça o bolo de novo, mas inverta a ordem de adicionar os ingredientes (que matematicamente não deve mudar o gosto)". Se o sabor mudar, o cozinheiro errou, mesmo que você não saiba qual é o "sabor perfeito" original.

3. O Que Eles Encontraram?

Ao testar um motor popular chamado PCRE (usado em muitos sites e programas):

Cobertura: O ReTest conseguiu testar 3 vezes mais partes do código do motor do que os métodos antigos.
Descobertas: Eles encontraram 3 novos bugs graves de segurança (erros que poderiam permitir que hackers invadissem sistemas), que os métodos antigos não conseguiram achar.
Análise de Histórico: Eles olharam para 1.007 erros antigos e viram que a maioria (82%) foi descoberta por usuários comuns (que usaram o software e reclamaram), e não por testes automáticos. Isso mostra que o sistema atual de testes está falhando em pegar os erros antes que eles cheguem ao público.

Resumo Final

Imagine que os motores de Regex são como portões de segurança em um aeroporto.

Os testes antigos eram como jogar pedras aleatórias no portão para ver se ele quebra (muitas pedras não servem) ou comparar dois portões de marcas diferentes (um pode ser de ferro, o outro de madeira, e ambos funcionam, mas parecem diferentes).
O ReTest é como um inspetor de segurança superinteligente. Ele usa chaves que sabem exatamente como o portão foi feito (para não travar na fechadura) e usa leis físicas (se eu empurrar o portão para a esquerda e depois para a direita, ele deve voltar ao lugar original). Se o portão não voltar, o inspetor sabe que há um defeito, mesmo sem saber como o portão "deveria" funcionar exatamente.

O objetivo final é ajudar os desenvolvedores a consertar esses portões antes que alguém consiga forçá-los a abrir indevidamente, tornando a internet mais segura para todos nós.

Título: Rumo ao Teste Sistemático de Engines de Expressões Regulares

1. O Problema

As expressões regulares (regex) são fundamentais na engenharia de software para validação de entrada, processamento de texto e extração de dados. Elas são suportadas por engines de regex (como PCRE, RE2, módulos nativos de Python/Java, etc.). No entanto, essas engines são propensas a bugs e vulnerabilidades de segurança.

O artigo identifica três lacunas críticas nas práticas atuais de teste:

Falta de Padronização Semântica: Diferentes engines implementam dialetos distintos (ex: POSIX vs. PCRE) com semânticas ligeiramente diferentes. Isso torna o teste diferencial (comparar saídas entre engines) ineficaz, gerando muitos falsos positivos devido a variações esperadas de dialeto, não a bugs reais.
Geração de Entrada Ineficiente: O fuzzing (testes de fuzz) atual é frequentemente baseado em mutações aleatórias de bytes. Isso gera padrões de regex sintaticamente inválidos que são rejeitados pelo parser, falhando em exercitar a lógica interna de matching (correspondência) da engine.
Problema do Oráculo: É difícil determinar se o resultado de uma engine está correto sem uma especificação universal. A maioria dos bugs (especialmente erros semânticos) não causa travamentos (crashes), tornando-os invisíveis para oráculos baseados apenas em falhas de execução.

2. Metodologia: O Framework ReTest

Os autores propõem o ReTest, um framework de teste sistemático que combina duas técnicas principais para superar as limitações acima:

Fuzzing Consciente de Gramática (Grammar-Aware Fuzzing):
- Em vez de mutação de bytes, o ReTest analisa os padrões de regex como Árvores de Sintaxe Abstrata (AST).
- Utiliza um corpus de mais de 500.000 padrões reais do mundo real como sementes.
- Realiza substituições de subárvores estruturadas. O mutador entende o contexto sintático (ex: não substitui um quantificador por uma âncora), garantindo que os inputs gerados sejam sintaticamente válidos e exercitem profundamente a lógica de correspondência da engine.
- Utiliza rastreamento de cobertura de código (edge coverage) para guiar a mutação e explorar caminhos não testados.
Teste Metamórfico (Metamorphic Testing - MT):
- Para resolver o problema do oráculo sem depender de comparações entre engines, o ReTest utiliza propriedades algébricas derivadas da Álgebra de Kleene.
- Define Relações Metamórficas (MRs): transformações que preservam a semântica (ex: $r^* \equiv (r^*)^*$ ).
- O teste verifica se, para um mesmo input, a engine produz resultados consistentes entre o padrão original $r$ e o padrão transformado $T(r)$ . Se a engine falhar em manter essa equivalência interna, é um bug semântico, independente do dialeto.
Oráculos de Segurança:
- Integra sanitizadores de tempo de execução (AddressSanitizer, MemorySanitizer, UBSan) para detectar violações de segurança (estouro de buffer, uso após liberação, etc.) que causam travamentos.

3. Contribuições Principais

Os autores realizaram um estudo empírico extensivo e desenvolveram o protótipo do ReTest:

Estudo Empírico de Práticas de Teste:
- Analisaram 22 engines de regex (10 nativas de linguagens e 12 bibliotecas de terceiros).
- Identificaram que 82% dos bugs são relatados por usuários, e apenas 2 das 22 engines utilizam fuzzing consciente de gramática.
- Mapearam 12 técnicas de teste, mostrando que a maioria depende de testes manuais e unitários.
Análise de Bugs e CVEs:
- Analisaram 1.007 bugs reais e 156 CVEs (vulnerabilidades de segurança).
- Descobertas: Bugs semânticos representam 35% dos defeitos; vulnerabilidades de segurança de memória dominam os CVEs (52%). O PCRE sozinho responde por 32% dos CVEs de engines de regex.
Catálogo de Relações Metamórficas:
- Compilaram um catálogo de 16 relações metamórficas baseadas na Álgebra de Kleene (ex: associatividade, comutatividade, leis de Kleene star) que servem como oráculos independentes de dialeto para a fragmentação K-regex (regexes regulares).
Framework ReTest:
- Implementação que integra geração de inputs baseada em AST e verificação metamórfica.

4. Resultados Preliminares

O ReTest foi avaliado na engine PCRE v8.45 e comparado com duas abordagens de base (baselines):

B1 (Fuzzing Nave): Fuzzing aleatório de bytes (OSS-Fuzz padrão).
B2 (Fuzzing Consciente de Gramática Simples): Abordagem baseada em expansão de regras de produção (sem contexto sintático profundo).

Resultados de Cobertura:

O ReTest alcançou 40,12% de cobertura de arestas (edge coverage).
Isso representa um aumento de 3x em comparação com as abordagens existentes (B1: ~11,8% e B2: ~12,6%).
O ReTest atingiu uma cobertura inicial alta (29%) devido ao corpus de sementes, e as mutações conscientes de contexto adicionaram mais 11 pontos percentuais.

Descoberta de Bugs:

O ReTest descobriu 3 novos bugs de segurança de memória no PCRE v8.45 (dois envolvendo corrupção de heap e um estouro de buffer global), relacionados a sequências de escape específicas e recursão.
Nenhuma das abordagens de base (B1 ou B2) encontrou bugs durante o mesmo período de teste.

5. Significância e Conclusão

O trabalho demonstra que o teste de engines de regex pode ser sistematizado e automatizado de forma eficaz, superando as limitações do teste diferencial e do fuzzing cego.

Impacto na Segurança: Ao focar em bugs de memória e erros semânticos que não causam travamentos, o ReTest aborda as duas classes mais perigosas de defeitos em engines de regex.
Independência de Dialetos: A abordagem metamórfica permite testar qualquer engine, independentemente de qual dialeto ela implementa, eliminando a necessidade de uma "engine de referência" perfeita.
Futuro: Os autores planejam expandir o catálogo de relações metamórficas para regexes estendidos (E-regexes, que incluem referências posteriores e lookarounds) e realizar avaliações em larga escala em todas as 22 engines estudadas.

Em suma, o ReTest oferece um caminho viável para melhorar a confiabilidade e segurança da infraestrutura crítica de software que são as engines de expressões regulares.