Como evitar loops infinitos na classe .NET RegEx?

Question

Got uma tarefa simples para obter uma expressão XPath e retornar um prefixo que coincide com o pai do nó que (pode ser) selecionada.

Exemplo:

/aaa/bbb       =>   /aaa
/aaa/bbb/ccc   =>   /aaa/bbb
/aaa/bbb/ccc[@x='1' and @y="/aaa[name='z']"] => /aaa/bbb

Como os padrões dentro dos colchetes pode conter colchetes entre aspas, eu decidi tentar conseguir isso com o uso de expressões regulares. Aqui está um trecho de código:

string input =
    "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
                                            //  ^-- remove space for no loop
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$";

System.Text.RegularExpressions.Regex re =
    new System.Text.RegularExpressions.Regex(pattern);
bool ismatch = re.IsMatch(input); // <== Infinite loop in here
// some code based on the match

Como os padrões são bastante regular, eu procurei '/' seguido pelo identificador da seguido por um grupo opcional que partidas no final da cadeia (....)? $

O código on a trabalho, mas jogando com valores diferentes para a cadeia de entrada, descobri que simplesmente inserindo um espaço (no local mostrado no comentário), a função .NET IsMatch entra em um loop infinito, levando todo o CPU fica.

Agora, independentemente de este padrão de expressão regular é o melhor (eu tinha mais complexo, mas simplificado para mostrar o problema), isso parece mostrar que usando RegEx com qualquer coisa não trivial pode ser muito arriscado.

Estou faltando alguma coisa? Existe uma maneira de se proteger contra loops infinitos em partidas de expressão regular?

Answer 1

OK, vamos decompô-lo em seguida:

Input: /aaa/bbb/ccc[@x='1' and @y="/aaa[name='z'] "]
Pattern: /[a-zA-Z0-9]+(\[([^]]*(]")?)+])?$

(Eu suponho que você quis dizer \" no seu C corda -escaped #, não "" ... tradução do VB.NET?)

Primeiro, / [a-zA-Z0-9] + irá devorar através do primeiro colchete, deixando:

Input: [@x='1' and @y="/aaa[name='z'] "]

O grupo exterior de (\ [([^]] * (] "")?) +])? $" Deve corresponder se houver 0 ou 1 instância antes da EOL. Então, vamos dividi dentro e ver se ele corresponde a qualquer coisa.

O "[" fica devorado imediatamente, deixando-nos com:

Input: @x='1' and @y="/aaa[name='z'] "]
Pattern: ([^]]*(]")?)+]

quebrar o padrão: jogo 0 ou mais não ] caracteres e, em seguida, combinar "] 0 ou 1 vezes, e continuar fazendo isso até que você não pode. em seguida, tentar encontrar e devoram um ] depois.

O padrão corresponde com base em [^]] * até atingir o ] .

Uma vez que há um espaço entre ] e ", não pode gobble um desses personagens, mas o ? depois (] ") permite que ele retorne verdadeiro de qualquer maneira.

Agora temos correspondido com sucesso ([^]] * (] ")?) uma vez, mas o + diz que devemos tentar manter correspondência que qualquer número de vezes que pudermos.

Isso nos deixa com:

Input: ] "]

O problema aqui é que esta entrada pode corresponder ([^]] * (] ")?) um infinito de vezes sem nunca ter sido devorado, e" +" vai forçá-lo a apenas continue tentando.

Você está essencialmente combinando "1 ou mais" situações onde você pode combinar "0 ou 1" de algo seguido de "0 ou 1" de outra coisa. Uma vez que nenhum dos dois subpadrões existe na entrada restantes, ele mantém correspondência 0 de [^]] \ * e 0 de (] ")? em um loop infinito.

A entrada nunca é devorado, eo resto do padrão após o "+" nunca é avaliada.

(Espero que eu tenho o SO-escape-de-regex-escapar logo acima.)

Answer 2

O problema aqui é que esta entrada pode corresponder ([^]] * (] ")?) Um infinito de vezes sem nunca ter sido devorado, e '+' irá forçá-lo a apenas continue tentando.

Isso é um inferno de um bug na implementação RegEx do .NET. As expressões regulares simplesmente não funcionam assim. Quando você transformá-los em autômatos, você receberá automaticamente o fato de que uma repetição infinita de uma cadeia vazia ainda é uma cadeia vazia.

Em outras palavras, qualquer motor de regex não-Buggy irá executar este loop infinito instantaneamente e continuar com o resto do regex.

Se preferir, expressões regulares são uma linguagem tão limitado que é possível (e fácil) para detectar e evitar tais loops infinitos.

Answer 3

Ela mostra que o uso de código com qualquer coisa não trivial pode ser arriscado. Você criou um código que pode resultar em um loop infinito, eo compilador RegEx obrigado. Nada de novo que não tenha sido feito desde o primeiro 20 IF X = 0 THEN GOTO 10.

Se você está preocupado com isso em um caso extremo particular, você poderia gerar um segmento para RegEx e depois matá-lo depois de algum tempo de execução razoável.

Answer 4

Para responder à pergunta original (ou seja, como evitar loop infinito com regex), este tornou-se fácil com o .Net 4.5, como você pode simplesmente passar um tempo fora para os métodos de Regex. Há um temporizador interno que irá parar o loop regex quando o tempo limite expirar e criar uma RegexMatchTimeoutException

Por exemplo, você faria o seguinte

string input = "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$";
bool ismatch = Regex.IsMatch(input, pattern, RegexOptions.None, TimeSpan.FromSeconds(5));

Você pode conferir MSDN para mais detalhes