💻 computer science

Towards Efficient Matching of Regexes with Backreferences using Register Set Automata (Technical Report)

Este relatório técnico propõe o uso de autômatos de conjuntos de registradores (RSAs) para permitir a correspondência rápida e robusta de expressões regulares com referências reversas, demonstrando que essa abordagem oferece complexidade de tempo linear ou quadrática, resolve o problema de vazio de forma decidível e supera significativamente os limitadores dos matchers de estado da arte.

Autores originais: Vojtěch Havlena, Lukáš Holík, Ondřej Lengál, Jan Vašák, Sabína Gulčíková

Publicado 2026-04-16

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Vojtěch Havlena, Lukáš Holík, Ondřej Lengál, Jan Vašák, Sabína Gulčíková

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 você é um detetive tentando encontrar um padrão específico em uma montanha de documentos. Às vezes, o padrão é simples, como "encontrar todas as palavras que começam com 'A'". Mas, às vezes, o padrão é um quebra-cabeça complexo: "Encontre uma frase onde a primeira palavra seja exatamente igual à última, e a segunda seja igual à penúltima".

No mundo da computação, isso é feito usando Expressões Regulares (Regex). Elas são como receitas para encontrar textos. O problema é que, quando essas receitas têm "referências" (como pedir para repetir uma parte que já foi encontrada antes), os computadores tradicionais ficam confusos. Eles começam a tentar todas as combinações possíveis, como um rato num labirinto que volta e recua infinitamente. Se alguém enviar um texto malicioso, esse "rato" pode travar o computador inteiro, causando o que chamamos de ataque ReDoS (negação de serviço por expressão regular). É como se um ladrão entrasse no seu sistema e dissesse: "Vou te fazer procurar por uma agulha num palheiro, mas vou te fazer procurar em cada palha, uma por uma, por 100 anos".

A Solução: O "Cesto de Memória" Inteligente

Os autores deste artigo, da República Tcheca e Dinamarca, propuseram uma nova maneira de fazer essa busca, chamando-a de Autômatos de Conjuntos de Registradores (RSAs).

Para entender como funciona, vamos usar uma analogia:

1. O Método Antigo (O "Backtracking" ou "Devolução")

Imagine que você está tentando montar um quebra-cabeça gigante. O método antigo pega uma peça, tenta encaixar, não serve, tira, tenta outra, não serve, tira, e volta para a primeira tentativa. Se o quebra-cabeça for grande e tiver peças parecidas, você pode passar a vida inteira tentando encaixar as mesmas peças de formas diferentes. É lento e perigoso.

2. O Novo Método (Os "Registradores de Conjuntos")

A nova ideia é ter cestos (os registradores) que não guardam apenas uma coisa, mas um conjunto de coisas.

O Problema: Imagine que você precisa lembrar de todas as cores de bolas que você já viu para saber se a próxima bola é nova ou repetida.
O Velho Registrador: Era como ter um único balde onde você só podia colocar uma bola por vez. Se você visse uma bola vermelha, guardava. Se visse uma azul, tinha que jogar a vermelha fora para guardar a azul. Se precisasse lembrar das duas, entrava em pânico e tentava todas as combinações.
O Novo Registrador (RSA): É como ter um balde grande onde você pode jogar todas as bolas que vê.
- Se você vê uma bola vermelha, joga no balde.
- Se vê uma azul, joga no mesmo balde.
- Agora, o balde contém {Vermelho, Azul}.
- Quando chega uma bola nova, você só olha dentro do balde. Se a cor já estiver lá, você sabe que é uma repetição. Se não estiver, você joga ela no balde também.

Isso elimina a necessidade de "voltar e tentar de novo". O computador segue o caminho direto, como se tivesse um mapa completo, em vez de se perder no labirinto.

Por que isso é importante?

Velocidade e Segurança: Com essa nova técnica, o computador não trava, não importa quão complexo seja o padrão ou quão malicioso seja o texto de entrada. A busca é feita em tempo linear (se o texto tem 100 letras, o computador dá 100 passos, nem um a mais). Isso protege sites e servidores contra ataques que tentam derrubá-los.
A "Mágica" da Determinização: Os autores criaram um algoritmo que transforma essas receitas complexas (Regex) em máquinas determinísticas (DRSAs). É como transformar uma receita de bolo escrita em um código secreto confuso em uma lista de instruções passo-a-passo que qualquer um pode seguir sem errar.
Teoria vs. Prática: Eles provaram matematicamente que essa nova máquina é poderosa (pode resolver problemas que outras não conseguem) e que, embora seja complexa de construir, uma vez construída, ela funciona de forma previsível e rápida.

Resumo da Ópera

Pense no mundo digital como uma biblioteca gigante. Antigamente, se você pedisse para o bibliotecário encontrar "todos os livros onde o autor do capítulo 1 é o mesmo do capítulo 3", ele poderia passar dias vasculhando as prateleiras, pegando e devolvendo livros, ficando exausto e talvez desistindo (ou travando o sistema).

Com os Autômatos de Conjuntos de Registradores, o bibliotecário ganha um cesto mágico. Ele pega o autor do capítulo 1 e joga no cesto. Pega o do capítulo 2 e joga no cesto. Quando chega no capítulo 3, ele só olha no cesto. Se o nome estiver lá, ele sabe imediatamente. Se não, ele joga no cesto e segue em frente.

O resultado? A biblioteca nunca mais trava, o bibliotecário nunca fica exausto e os "ladrões" que tentavam fazer o sistema colapsar agora encontram apenas um sistema rápido, eficiente e seguro.

Os autores criaram um protótipo que já mostra que essa ideia funciona na prática, superando os métodos atuais e tornando a internet um lugar mais seguro contra esse tipo de ataque específico.

Título: Para uma Correspondência Eficiente de Expressões Regulares com Referências Reversas usando Autômatos de Conjuntos de Registradores (RSAs)

1. O Problema

A correspondência de expressões regulares (regex) é uma tarefa fundamental em ciência da computação, utilizada em validação de dados, busca, análise de logs e detecção de intrusões. No entanto, a performance degrada-se drasticamente quando se utilizam referências reversas (backreferences), uma extensão comum que permite que uma parte da expressão corresponda a uma captura anterior (ex: (.).*\1 para encontrar strings repetidas).

Desafio de Performance: A maioria dos matchers modernos (como PCRE2, Python re, Java java.util.regex) utiliza algoritmos de backtracking (retrocesso) para lidar com referências reversas. Isso pode levar a uma complexidade exponencial no pior caso, tornando o sistema vulnerável a ataques de negação de serviço por expressão regular (ReDoS).
Limitação dos Autômatos Determinísticos: Algoritmos baseados em autômatos determinísticos (DFA), que oferecem complexidade linear e são robustos contra ReDoS, não suportam nativamente referências reversas, pois a linguagem gerada por regexes com backreferences pode não ser regular.
Gap Atual: Ferramentas de alta performance como RE2 e HyperScan não suportam referências reversas devido à falta de um modelo de autômato determinístico eficiente para esse fim.

2. Metodologia e Modelo Proposto

Os autores propõem um novo modelo formal chamado Autômatos de Conjuntos de Registradores (Register Set Automata - RSAs) e um pipeline completo para convertê-los em uma forma determinística e eficiente.

2.1. O Modelo: Register Set Automata (RSA)

Diferente dos Autômatos de Registradores (RAs) tradicionais, onde um registrador armazena um único símbolo de dados, os RSAs permitem que os registradores armazenem conjuntos de símbolos (de um alfabeto potencialmente infinito).

Operações Suportadas: Adicionar valores de entrada aos registradores, fundir (union) conjuntos de registradores, limpar registradores e testar a pertinência de um valor em um conjunto.
Vantagem: A capacidade de manter conjuntos permite que o autômato "lembre" de múltiplos valores vistos anteriormente simultaneamente, superando a limitação de memória dos RAs clássicos.

2.2. Pipeline de Correspondência

O trabalho apresenta um fluxo de três etapas para transformar uma Regex com referências reversas em um matcher determinístico:

Conversão Regex $\to$ RA (Nondeterminístico): Utilização de uma construção baseada em derivadas parciais de Antimirov para converter a regex em um Autômato de Registradores (RA). Esta etapa lida com a sintaxe de grupos de captura e referências.
Determinização (RA $\to$ DRSA): Desenvolvimento de um semi-algoritmo de determinização que transforma um RA (nondeterminístico) em um DRSA (Deterministic Register Set Automaton).
- O algoritmo utiliza uma construção de subconjuntos (similar a Rabin-Scott) mas com tratamento especial para registradores.
- Para lidar com a imprecisão ao converter testes de desigualdade ( $in \neq r$ ) para testes de não-pertinência ( $in \notin r$ ), o algoritmo rastreia classes de tamanho dos conjuntos nos registradores (0, 1, ou >1).
- Se o algoritmo falhar (retornar $\bot$ ), significa que a regex não pode ser determinizada com este modelo específico.
Correspondência (Matching): Execução do DRSA determinístico sobre o texto de entrada.

3. Principais Contribuições

Introdução do Modelo RSA: Definição formal e análise teórica dos RSAs, mostrando que eles generalizam os RAs e são incomparáveis em poder expressivo com outros modelos (como Autômatos de Registradores Alternantes).
Algoritmo de Determinização: Um algoritmo (semi-)completo para transformar uma classe significativa de RAs em DRSAs. O algoritmo é completo para linguagens obtidas a partir de RAs com um único registrador e sem testes de desigualdade, combinados por operações booleanas.
Complexidade de Correspondência:
- Para alfabetos finitos: Complexidade linear em relação ao tamanho da entrada ( $O(|w|)$ ).
- Para alfabetos infinitos: Complexidade quadrática ( $O(|w|^2)$ ).
- Para uma subclasse "copy-free" (sem cópia de registradores), a complexidade é linear mesmo em alfabetos infinitos.
Análise Teórica de Decidibilidade:
- O problema de vazio (emptiness) para RSAs é decidível, mas com complexidade alta: F $\omega$ -completo (nível de Ackermann), o que é significativamente mais caro que para RAs (PSPACE-completo), mas ainda tratável para verificação.
- O problema de inclusão de linguagens para DRSAs é decidível.
Implementação e Avaliação Experimental: Criação de um protótipo (rsamatch em Python) e avaliação contra matchers de última geração (PCRE2, grep, Python re, etc.).

4. Resultados Experimentais

Os autores testaram o rsamatch em um conjunto de dados real contendo 12.046 regexes (incluindo vetores de ataque ReDoS gerados pela ferramenta Rengar).

Robustez contra ReDoS: O rsamatch demonstrou ser significativamente mais robusto. Enquanto matchers baseados em backtracking (como PCRE2 e Python re) frequentemente excederam o tempo limite (100s) ou levaram dezenas de segundos para processar entradas maliciosas, o rsamatch manteve tempos de execução consistentes, geralmente abaixo de 1 segundo (na maioria dos casos, milissegundos).
Taxa de Sucesso na Determinização:
- Para regexes com referências reversas de letra única (uma grande parcela dos casos reais), o algoritmo conseguiu gerar um DRSA em 91% dos casos.
- Para o conjunto total de regexes, a taxa de sucesso foi de cerca de 34,5%, limitando-se principalmente por regexes com grupos de captura de comprimento não limitado ou estruturas complexas que o algoritmo atual não consegue determinizar.
Previsibilidade: A variância (desvio padrão) dos tempos de execução do rsamatch foi ordens de magnitude menor que a dos concorrentes, eliminando a imprevisibilidade associada ao backtracking.

5. Significado e Impacto

Segurança: A proposta oferece uma solução prática para mitigar ataques ReDoS em cenários onde referências reversas são necessárias (ex: validação de formulários web, processamento de XML/JSON), preenchendo uma lacuna crítica deixada por ferramentas de alta performance atuais.
Teoria de Autômatos: Estabelece uma nova classe de autômatos sobre palavras de dados (data words) que equilibra poder expressivo e decidibilidade, posicionando-se entre os modelos existentes.
Aplicabilidade Prática: Demonstra que, para uma grande classe de regexes do mundo real (especialmente aquelas com grupos de captura de letra única), é possível obter a robustez de um autômato determinístico sem sacrificar a capacidade de expressar padrões complexos com referências reversas.

Conclusão

O artigo apresenta um avanço significativo na correspondência de expressões regulares. Ao introduzir os Register Set Automata e um algoritmo de determinização eficaz, os autores conseguem transformar um problema NP-difícil (no caso geral de backtracking) em um problema de complexidade linear ou quadrática para uma vasta classe de casos práticos. Isso oferece uma alternativa viável e segura para sistemas que dependem de regexes com referências reversas, protegendo-os contra ataques de negação de serviço.