Como lidar com correspondências intermináveis ​​de expressões regulares enviadas pelo usuário

Question

Vamos considerar as duas linhas a seguir em C# (usando o framework .NET 3.5)

Regex regex = new Regex(@"^((E|e)t )?(M|m)oi (?<NewName>[A-Za-z]\.?\w*((\-|\s)?[A-Za-z]?\w{1,})+)$", RegexOptions.Compiled | RegexOptions.IgnoreCase);
Match m = regex.Match("moi aussi jaimerai etre un ordinateur pour pas m'énnerver ");

(desculpe, é um programa francês :))

Quando eles são executados, o processo fica preso no Match() método e nunca sai.Acho que há algum problema com o espaço em branco no padrão regex, mas o que eu gostaria de fazer não é alterar o padrão (na verdade ele é definido fora do programa, pelos usuários finais da minha ferramenta), mas poder interromper o processo (com um tempo limite, por exemplo).

Alguém sabe se este é um problema bem conhecido com a expressão regular do .NET e se existe uma maneira fácil de contornar isso ou tenho que encadear essas linhas e abortá-las se necessário (definitivamente eu não gostaria de fazer isso ).

Answer 1

Eu acho que você deve simplesmente iniciar a correspondência regex em um encadeamento separado e permitir que ele seja abortado se um certo limite de tempo máximo for atingido.

Answer 2

Se eu inserir a expressão no Regexbuddy, ela apresenta a seguinte mensagem

A tentativa de partida foi abortada mais cedo porque a expressão regular é demais complexo.O mecanismo regex que você planeja usá-lo com pode não ser capaz de lidar ele em tudo e bater.Pesquisar "retrocesso catastrófico" no arquivo de ajuda para saber como evitar isso situação.

Olhando pra cima retrocesso catastrófico dá a seguinte explicação

Expressões regulares em fuga:Retrocesso catastrófico
Considere a expressão regular (x+x+)+y.Antes de gritar horrorizado e dizer este exemplo inventado deve ser escrito como xx+y para corresponder exatamente ao mesmo sem aqueles terrivelmente aninhados Quantificadores:basta supor que cada "x" representa algo mais complexo, com certas cadeias de caracteres sendo correspondidas por ambos "x".Veja a seção sobre HTML arquivos abaixo para um exemplo real.

Vamos ver o que acontece quando você se candidata este regex para xxxxxxxxxxy.O primeiro x+ corresponderá a todos os 10 caracteres x.O segundo x+ falha.O primeiro x+ então recua para 9 partidas, e o o segundo pega o x restante.O grupo já combinou uma vez.O grupo repete, mas falha no primeiro x+.Já que uma repetição foi O grupo se enfrenta.y Partidas Y e uma partida geral é fundar.O regex é declarado funcional, o código é enviado para o cliente, e seu computador explode.Quase.

O regex acima fica feio quando o y está ausente da cadeia de caracteres de assunto.Quando y falha, o mecanismo regex retrocessos.O grupo tem um iteração que ele pode retroceder.O segundo x+ correspondeu a apenas um x, então ele não pode voltar atrás.Mas o primeiro x+ pode desista de um x.O segundo x+ prontamente corresponde a xx.O grupo volta a ter um iteração, falha na próxima e o y falha.Retrocedendo novamente, o Segundo X+ agora tem um backtracking posição, reduzindo-se a corresponder a x.O grupo tenta uma segunda iteração.O primeiro x+ corresponde, mas o segundo é preso no final da corda.Retrocedendo novamente, o primeiro x+ em a primeira iteração do grupo reduz em si para 7 caracteres.O segundo x+ corresponde a xxx.Falhando y, o segundo x+ é reduzido a xx e, em seguida, x.Agora, o grupo pode corresponder a uma segunda iteração, com um x para cada x+.Mas isso (7,1),(1,1) a combinação também falha.Então vai para (6,4) e depois (6,2)(1,1) e então (6,1),(2,1) e então (6,1),(1,2) e aí eu acho que você começa para obter a deriva.

Se você tentar este regex em uma sequência de caracteres 10x no depurador do RegexBuddy, será preciso 2558 passos para descobrir o y final está faltando.Para uma cadeia de caracteres de 11x, ele precisa de 5118 passos.Para 12, é preciso 10238 passos.É evidente que temos um complexidade exponencial de O(2^n) aqui.Em 21x o depurador se curva em 2.8 milhões de passos, diagnosticando um caso ruim de retrocesso catastrófico.

Regexbuddy está perdoando, pois detecta que está acontecendo em círculos, e anula a tentativa de correspondência. Outros motores regex (como .NET) continuarão indo para sempre, enquanto outros vão bater com um estouro de pilha (como Perl, antes versão 5.10).Os estouros de pilha são particularmente desagradável no Windows, uma vez que eles tendem a fazer a sua aplicação desaparecer sem deixar vestígios ou explicações.Tenha muito cuidado se você executar uma web serviço que permite aos usuários fornecer suas próprias expressões regulares.Povo com pouca experiência regex tem habilidade surpreendente em criar regular exponencialmente complexo Expressões.

Presumo que você terá que lidar com isso no código.Eu sugiro que você entre em contato com o autor de Regexbuddy e pergunte o que é necessário para detectar esse cenário.

Answer 3

Em geral, expressões regulares podem levar mais tempo do que você espera. Você deve experimentar a expressão regular hjusing uma ferramenta como o regulador.

Answer 4

O problema é que você aninhou "loops" em seu regex, o que o torna terrivelmente ineficiente (para que basicamente demore uma eternidade devido à complexidade da expressão).

Se você disser o que gostaria de combinar, posso tentar descobrir um regex mais eficiente para isso.

Answer 5

Parece -me que é um caso que o regex corresponde a crescer exponencialmente. Veja o Blog bcl.

A melhor solução é definir um tempo limite no regex, sem mexer com threads.

Veja aqui como despoja as cordas com tempo limite.