Estou ciente da negação de serviço de expressão regular (ReDoS). Existe alguma maneira razoável de permitir que os usuários criem regexes personalizadas, garantindo que eles não enviem um padrão exponencialmente lento?
regular-expressions
icirellik
fonte
fonte
Respostas:
O problema com expressões regulares não é o próprio regex, mas o mecanismo de regex que possui todos os tipos de recursos "convenientes", como o retorno. Portanto, o uso de um mecanismo regex sem esses recursos evita.
Expressões regulares que o conceito de ciência da computação pode sempre corresponder em tempo linear após serem compiladas em uma máquina de estados finitos. Portanto, um mecanismo regex baseado em máquina de estado não pode ser usado para ReDoS. No entanto, as máquinas de estado necessárias podem se tornar bastante grandes em exemplos patológicos. Porém, limitar a memória disponível tende a ser mais fácil do que limitar o tempo de computação disponível.
O mecanismo RE2 foi desenvolvido especificamente para lidar com regexes não confiáveis e foi projetado para execução em tempo linear.
Outra alternativa é montar as expressões regulares a partir de uma notação simplificada. Por exemplo, você pode permitir que os usuários usem padrões glob (como
*.txt). Você pode analisar isso de uma maneira que evite o retorno, por exemplo, impedindo o aninhamento e usando apenas quantificadores gananciosos. Para muitos casos de uso, uma notação de padrão simplificada é completamente suficiente.fonte
Analisar uma expressão regular para ver se ela será lenta ou não, sem que a análise se torne lenta , equivale a resolver o problema de parada. Em outras palavras, não é possível encontrar uma solução correta e completa.
Você pode, é claro, encontrar uma solução que está correto e em completa. Por exemplo, você pode trabalhar com uma lista branca restritiva de recursos que são seguros de usar (por exemplo, classes de caracteres sim, repetição não ...). Isso permitiria que você passasse por muitas regexes acríticas, rejeite todas as críticas e (erroneamente) rejeite algumas que estão bem, mas são muito complicadas para se provar seguras automaticamente.
fonte
Como autor do analisador para o projeto lazarus, eu diria que não há maneiras de entender, para uma expressão regular, quais recursos serão consumidos em um determinado texto.
Sem gastar os mesmos recursos, quero dizer (pelo menos em grande-O).
Portanto, a melhor abordagem - execute o analisador em um thread separado e mate-o após o tempo limite.
fonte
Além das outras respostas, uma solução também pode ser a rolagem de sua própria biblioteca de expressões regulares, que permite a instrumentação de desempenho durante a execução e, portanto, fornece os meios para eliminar a execução no meio do caminho, se alguns critérios forem atendidos.
Da mesma forma, você pode executar as expressões regulares em outro encadeamento e eliminá-las se elas demorarem muito.
fonte