Resumo Técnico: PUFFERDOS

Declaração do Problema

Ataques de Negação de Serviço por Expressão Regular (ReDoS) exploram o comportamento de execução de pior caso patológico de mecanismos de regex de retrocesso (backtracking), forçando-os a explorar um número superlinear ou exponencial de caminhos de correspondência. Isso consome recursos excessivos de CPU, levando à degradação ou indisponibilidade do serviço. Embora existam inúmeras ferramentas de detecção para identificar regex vulneráveis e gerar strings de prova de conceito de ataque, as abordagens atuais sofrem de duas limitações críticas que dificultam a exploração prática:

1. Comprimentos de Entrada Impraticáveis: As ferramentas existentes frequentemente geram strings de ataque que são irrealistemente longas (por exemplo, exigindo centenas de milhares de caracteres) para desencadear uma lentidão significativa. Em implantações do mundo real, restrições de entrada (como limites de cabeçalho HTTP) frequentemente truncam essas strings antes que elas possam alcançar a regex vulnerável, tornando o ataque ineficaz.
2. Falta de Validação ao Nível de Programa: Muitas strings geradas são validadas apenas contra a regex isoladamente. Elas falham em considerar restrições de fluxo de dados, lógica de filtragem ou truncamento de entrada dentro do programa hospedeiro. Consequentemente, essas strings muitas vezes não conseguem alcançar a regex vulnerável em um contexto de execução real, levando desenvolvedores a descartar vulnerabilidades relatadas como de baixa severidade ou inexploráveis.

Metodologia

Os autores propõem o PUFFERDOS, um framework híbrido projetado para sintetizar strings de ataque que sejam tanto eficientes (maximizando o custo de correspondência dentro de orçamentos de comprimento realistas) quanto eficazes (validadas para alcançar a regex vulnerável no programa real). A metodologia consiste em três componentes principais:

1. Análise Formal e Taxonomia de Padrões

Os autores primeiro formalizam a relação entre a estrutura da string de ataque e o custo de correspondência. Através de provas formais (Lemmas 3.2–3.4 e Teorema 3.5), eles estabelecem que o custo de correspondência aumenta quando:

• As unidades de repetição são o mais curtas possível.
• As unidades de repetição são selecionadas da interseção dos alfabetos de Expressões de Loop (LEs) adjacentes, permitindo que múltiplas LEs consumam a mesma substring.
• Os pontos de parada (índices onde as LEs terminam) estão separados em vez de intercalados, forçando o mecanismo a reprocessar segmentos de entrada mais longos durante o backtracking.

Com base nisso, eles definem três padrões vulneráveis para guiar a geração de strings:

• Exponencial de Um Loop (EOL - Exponential One-Loop): Uma única LE com subregexes de desdobramento possuindo alfabetos sobrepostos.
• Interseção de Loop-Loop (LIL - Loop-Intersect-Loop): Duas LEs adjacentes separadas por um segmento de não-loop que pode ser correspondido por ambas as LEs.
• Multi-Loop Polinomial (PML - Polynomial Multi-Loop): LEs adjacentes com alfabetos ou separadores disjuntos que não podem ser consumidos por ambas.

2. Geração de Strings de Ataque Baseada em Estrutura

O PUFFERDOS analisa regex vulneráveis em uma Árvore de Sintaxe Abstrata (rAST) para identificar o padrão vulnerável específico (EOL, LIL ou PML). Ele então sintetiza candidatas a strings de ataque ($s_a = x \cdot y^q \cdot z$) usando regras específicas de padrão:

• Geração de Infixo: Seleciona a unidade de repetição mais curta ($y$) da interseção do alfabeto das LEs relevantes. Para padrões com múltiplas LEs, ele concatena unidades repetidas independentemente para garantir que os pontos de parada estejam separados, maximizando os passos de backtracking.
• Construção de Prefixo/Sufixo: Deriva o prefixo ($x$) do prefixo de não-loop da regex e o sufixo ($z$) do sufixo de não-loop, garantindo que a string final seja rejeitada pela regex para disparar o backtracking exaustivo.

3. Refinamento Concolic Composicional Específico para ReDoS

Para garantir que a string gerada alcance a regex vulnerável em um programa real, o PUFFERDOS emprega uma estratégia de execução concolic composicional:

• Extração de Caminho: Constrói um grafo de chamadas para identificar caminhos viáveis desde os pontos de entrada do programa até a regex vulnerável.
• Sumarização de Função: Realiza testes unitários concolicos em funções ao longo do caminho para gerar sumarizações de função específicas para ReDoS. Diferente das sumarizações tradicionais, estas são podadas para reter apenas comportamentos relevantes para a propagação da string de ataque (por exemplo, transformações de identidade ou retornos constantes), descartando o raciocínio de regex não relacionado que causa explosão de caminho.
• Refinamento de Nível de Sistema: Utiliza as sumarizações para guiar a execução concolica de nível de sistema, resolvendo restrições interprocedurais para refinar a string de ataque de modo que ela ultrapasse os filtros e alcance a regex alvo sem exceder orçamentos realistas de comprimento de entrada.

Principais Contribuições

1. Prova Formal de Eficiência: O artigo prova formalmente que selecionar caracteres específicos e ordená-los para separar os pontos de parada em LEs adjacentes amplifica significativamente o custo de correspondência de regex. Isso leva à derivação de três padrões de regex vulneráveis e regras de geração comprovadamente eficientes.
2. Framework PUFFERDOS: O desenvolvimento de um gerador híbrido que integra regras de geração formal com refinamento concolico composicional específico para ReDoS. Esta abordagem preenche a lacuna entre a detecção teórica e a exploração prática, garantindo que as strings sejam curtas o suficiente para restrições do mundo real e válidas dentro do fluxo de dados do programa.
3. Avaliação Abrangente: A ferramenta é avaliada em um corpus de larga escala de 17.962 regex vulneráveis, 31 CVEs conhecidos e 12 projetos de código aberto populares.

Resultados

A avaliação demonstra melhorias significativas em relação à ferramenta de estado da arte, RENGAR:

• Eficiência: O PUFFERDOS gera strings de ataque que são de 97,2× a 3.872,4× mais curtas que as produzidas pelo RENGAR, mantendo os mesmos limiares de tempo de correspondência (0,1s, 1s e 10s).
• Reprodução de CVE: O PUFFEDOS reproduziu com sucesso 96,8% das CVEs de ReDoS exploradas, comparado a 77,4% do RENGAR.
• Novas Vulnerabilidades: Aplicado a 12 projetos de código aberto populares, o PUFFEDOS descobriu 59 instâncias exploráveis de ReDoS (25 a mais que o RENGAR). Desenvolvedores de seis desses projetos validaram 21 das descobertas.
• Impacto no Mundo Real: Em um exemplo motivador envolvendo uma biblioteca de destaque de sintaxe, o PUFFEDOS gerou uma string de 1.000 caracteres que causou um travamento do sistema superior a 4.000 segundos, enquanto métodos tradicionais exigiam 500.000 caracteres e falharam em disparar um travamento devido ao truncamento de entrada no programa real.

Significância

O artigo argumenta que a utilidade prática da detecção de ReDoS é atualmente limitada porque as strings de ataque geradas são frequentemente muito longas ou falham em propagar através da lógica do programa. Ao abordar essas deficições específicas, o PUFFEDOS fornece um mecanismo para gerar evidências praticamente exploráveis de vulnerabilidades. Isso é significativo porque aborda diretamente a razão pela qual os desenvolvedores frequentemente ignoram relatórios de ReDoS (percebendo-os como de baixa severidade ou inexploráveis). Ao fornecer strings de ataque curtas e válidas, o PUFFEDOS permite uma avaliação de risco mais precisa e facilita a remediação de vulnerabilidades de ReDoS em sistemas de software do mundo real.