Para cada expressão regular 'má', existe uma alternativa não-má ou o diabo está na gramática?

Aparentemente, os ataques ReDos exploram características de algumas expressões regulares (de outra forma úteis) ... essencialmente causando uma explosão de caminhos possíveis através do gráfico definido pela NFA.

É possível evitar esses problemas escrevendo uma regex 'não-má' equivalente? Se não (assim, a gramática não pode ser tratada no espaço / tempo prático por uma NFA), que abordagens de análise seriam melhores? Por quê?

Depende se você tem uma expressão regular ou uma expressão regular: expressões regulares são más, mas expressões regulares são uma coisa de beleza e nunca se tornarão más para você.

Por regexp, quero dizer uma expressão regular moderna: ou seja, uma expressão regular com recursos modernos adicionais, como referências anteriores - por exemplo, uma expressão regular compatível com Perl. Isso é mais poderoso do que uma expressão regular clássica de um livro formal de teoria de linguagens / autômatos, pois as expressões regulares clássicas não permitem referências anteriores, lookahead, lookbehind e assim por diante.

Para uma expressão regular clássica, se você tiver uma boa implementação para o correspondente, nenhuma expressão regular será muito ruim. Em particular, um algoritmo padrão para correspondência é converter a expressão regular em um NFA e, em seguida, executar o NFA em uma sequência de entrada. Para esse algoritmo, o pior caso de execução para testar uma cadeia de caracteres é O ( n ) , quando a expressão regular é corrigida. Isso significa que o tempo de execução não pode explodir muito rapidamente. Não existe uma sequência que cause um aumento exponencial no tempo de execução. Portanto, se você estiver usando um combinador que usa esse algoritmo, nenhuma expressão regular clássica será má.$n$$O(n)$

Isso depende da implementação do correspondente de expressão regular. Se você tem uma implementação ingênua ou ruim do correspondente, a correspondência pode levar um tempo exponencial; certamente existem algoritmos com essa propriedade. Mas a melhor resposta para isso é provavelmente não mudar a expressão regular; provavelmente é melhor escolher um parceiro melhor, se você estiver preocupado com ataques de negação de serviço.

Em comparação, alguns regexps modernos são inevitavelmente maus. Se você possui uma regexp moderna, a correspondência pode exigir um tempo exponencial. Em particular, regexps com referências anteriores podem reconhecer linguagens NP-hard. Conseqüentemente, sob suposições plausíveis, existe uma classe de más expressões no qual os testes para uma partida levam um tempo exponencial. Assim, alguns regexps modernos são inevitavelmente maus: não há maneira viável de encontrar um regexp equivalente que não cause uma explosão exponencial no tempo de execução.

(Esse equivalente pode existir e pode até ser encontrado na teoria, mas sob suposições plausíveis, encontrar o regexp equivalente levará um tempo exponencial, o que não é possível na prática. Se você tivesse um procedimento sistemático para encontrar o regexp equivalente em tempo polinomial , então você pode resolver o problema de NP-difícil em tempo polinomial, provando que P = NP. Não faz muito bem que exista um regexp equivalente se não houver como encontrá-lo durante a sua vida.)

Antecedentes e fontes:

• Quais idiomas as expressões regulares compatíveis com Perl reconhecem? e Expressividade de expressões regulares modernas fornece referências para justificar que os regexps modernos podem reconhecer linguagens NP-hard.

• Como simular referências anteriores, lookaheads e lookbehinds em autômatos de estados finitos? e Quando uma expressão regular não é uma expressão regular? pode ser útil entender a diferença entre expressões regulares e expressões regulares.

• Este artigo de Russ Cox tem uma boa explicação de duas maneiras diferentes de criar um correspondente de expressão regular e explica por que o tempo de execução, se você usar o algoritmo adequado, é linear no comprimento da string de entrada (quando a expressão regular é mantida fixa e seu comprimento é tratado como uma constante). Em particular, o algoritmo baseado em NFA - também conhecido como algoritmo Thompson - possui um tempo de execução linear no pior dos casos. Ele também mostra como algumas linguagens populares têm implementações de regexp que podem se tornar exponenciais em alguns regexps e discute quais aspectos dos regexps modernos podem introduzir tempos de execução exponenciais.

• Neste post, assumo P! = NP. Mais exatamente, quando me refiro a "suposições plausíveis", refiro-me à hipótese do tempo exponencial .

Essa resposta terá uma visão mais abrangente dessa situação incomum de corte transversal, onde a teoria da complexidade é aplicável à segurança cibernética e o exemplo contém algumas das nuances / sutilezas significativas que podem ocorrer nessa área. Isso é essencialmente semelhante a um "ataque de injeção", em que certas entradas inesperadas causam um comportamento patológico, travando um sistema ou levando um tempo anormalmente longo.

A Wikipedia possui 15 categorias de ataques de negação de serviço e esse ataque se enquadra nas "inundações no nível do aplicativo" nessa lista. Outro exemplo um tanto semelhante é um ataque que preenche os logs do aplicativo.

Uma correção para ataques de injeção é "limpar a entrada". O designer do aplicativo pode reavaliar se for necessário compilar regexps arbitrários fornecidos por um usuário potencialmente malicioso. Apenas retirar expressões aninhadas no regexp ou alguma outra limitação semelhante provavelmente seria suficiente para evitar esse ataque. Embora sejam intrínsecos a muitos softwares modernos, grandes quantidades de funcionalidade podem ser fornecidas sem avaliar expressões regulares. O contexto importa, alguns aplicativos não exigiriam essa segurança.

Outra abordagem para melhorar a tolerância a falhas / resiliência aplicável aqui são os tempos limites especificados em diferentes níveis da pilha / hierarquia de software. A idéia seria especificar um limite de tempo / CPU ou instrução em uma avaliação de expressão regular "média" e terminar mais cedo, se excedido. Eles podem ser implementados com soluções personalizadas, mas pouco software ou linguagens de programação possuem tempos limite ou estruturas integrados para esse fim.

Aqui está um bom exemplo do uso de tempos limite para melhorar a tolerância a falhas e mostra um design / arquitetura / pov de alto nível para mitigar esses problemas: Tolerância a falhas em um sistema distribuído / Netflix de alto volume . Não tem nada especificamente conectado a expressões regulares, mas esse é o ponto aqui: virtualmente toda / qualquer lógica em nível de aplicativo pode se encaixar nessa estrutura ou algo semelhante.

Este artigo mostra como o retorno em particular pode levar à correspondência lenta de regexp. Regexps têm muitos recursos diferentes e pode-se tentar avaliar quais levam a comportamentos de pior caso.

Aqui está uma boa pesquisa científica deste tópico em particular com as soluções de análise estática propostas:

• Análise estática para tempo de execução exponencial de expressão regular via lógica subestrutural / Rathnayake, Thielecke

  A correspondência de expressão regular usando backtracking pode ter tempo de execução exponencial, levando a um ataque de complexidade algorítmica conhecido como REDoS na literatura de segurança de sistemas. Neste artigo, construímos uma análise estática publicada recentemente que detecta se uma determinada expressão regular pode ter tempo de execução exponencial para algumas entradas. Construímos sistematicamente uma análise mais precisa, formando poderes e produtos das relações de transição e, assim, reduzindo o problema de REDoS à acessibilidade. A correção da análise é comprovada usando um cálculo subestrutural das árvores de busca, onde a ramificação da árvore que causa a explosão exponencial é caracterizada como uma forma de não linearidade.