Existe alguma maneira de colocar código malicioso em uma expressão regular?

Quero adicionar o recurso de pesquisa de expressão regular à minha página da web pública. Além de HTML que codifica a saída, preciso fazer algo para me proteger contra entrada maliciosa do usuário?

As pesquisas no Google são inundadas por pessoas que resolvem o problema inverso - usando expressões regulares para detectar entradas maliciosas - das quais não estou interessado. No meu cenário, a entrada do usuário é uma expressão regular.

Vou usar a biblioteca Regex no .NET (C #).

Preocupações de negação de serviço

A preocupação mais comum com as expressões regulares é um ataque de negação de serviço através de padrões patológicos que se tornam exponenciais - ou até superexponenciais! - e, portanto, parece levar uma eternidade para resolver. Eles podem aparecer apenas em dados de entrada específicos, mas geralmente é possível criar um em que isso não importe.

Quais são esses dependerão um pouco da inteligência do compilador regex que você está usando, porque alguns deles podem ser detectados durante o tempo de compilação. Os compiladores Regex que implementam recursão geralmente têm um contador de profundidade de recursão interno para verificar a não progressão.

O excelente artigo de Russ Cox, de 2007, sobre a correspondência de expressões regulares pode ser simples e rápido (mas é lento em Java, Perl, PHP, Python, Ruby, ...) fala sobre maneiras pelas quais as NFAs mais modernas, que parecem derivar do código de Henry Spencer , sofrem severa degradação do desempenho, mas onde um NFA no estilo Thompson não apresenta esses problemas.

Se você apenas admitir padrões que podem ser resolvidos pelos DFAs, poderá compilá-los como tal e eles serão executados mais rapidamente, possivelmente muito mais rápido. No entanto, leva tempo para fazer isso. O documento de Cox menciona essa abordagem e seus problemas. Tudo se resume a uma troca clássica de tempo e espaço.

Com um DFA, você gasta mais tempo construindo-o (e alocando mais estados), enquanto que com um NFA você gasta mais tempo executando-o, pois pode haver vários estados ao mesmo tempo, e o retorno pode comer seu almoço - e sua CPU.

Soluções de negação de serviço

Provavelmente, a maneira mais razoável de abordar esses padrões que estão no fim perdedor de uma corrida com a morte por calor do universo é envolvê-los com um cronômetro que efetivamente coloque o tempo máximo permitido para sua execução. Normalmente, isso será muito, muito menor que o tempo limite padrão que a maioria dos servidores HTTP fornece.

Existem várias maneiras de implementá-las, variando de simples alarm(N)ao nível C, para try {}bloquear as exceções do tipo de alarme, até gerar um novo encadeamento criado especialmente com uma restrição de tempo embutida nele.

Texto explicativo de código

Em linguagens regex que admitem frases de destaque de código, deve ser fornecido algum mecanismo para permitir ou não essas da cadeia de caracteres que você irá compilar . Mesmo que as frases de destaque do código sejam apenas para codificar no idioma que você está usando, você deve restringi-las; eles não precisam chamar códigos externos, embora, se puderem, você tenha problemas muito maiores.

Por exemplo, no Perl, não é possível ter chamadas de código em expressões regulares criadas a partir da interpolação de strings (como seriam, pois são compiladas durante o tempo de execução), a menos que o pragma lexicamente de escopo especial esteja use re "eval";ativo no escopo atual.

Dessa forma, ninguém pode ocultar uma chamada de código para executar programas do sistema como rm -rf *, por exemplo. Como as frases de destaque de código são muito sensíveis à segurança, o Perl as desativa por padrão em todas as seqüências interpoladas, e você deve fazer o possível para reativá-las.

\ P {roperties} definidas pelo usuário

Resta uma questão mais sensível à segurança relacionadas com propriedades Unicode de estilo - como \pM, \p{Pd}, \p{Pattern_Syntax}, ou \p{Script=Greek}- de que podem existir em alguns compiladores regex que o apoio que notação.

O problema é que, em algumas delas, o conjunto de propriedades possíveis é extensível pelo usuário. Isso significa que você pode ter propriedades personalizadas que são chamadas de código reais para funções nomeadas em algum espaço de nome específico, como \p{GoodChars}ou \p{Class::Good_Characters}. Como seu idioma lida com isso pode valer a pena analisar.

Sandboxing

No Perl, um compartimento em área restrita por meio do Safemódulo daria controle sobre a visibilidade do espaço para nome. Outros idiomas oferecem tecnologias similares de sandbox. Se esses dispositivos estiverem disponíveis, convém procurá-los, porque eles foram projetados especificamente para execução limitada de código não confiável.

Acrescentando a excelente resposta de tchrist: o mesmo Russ Cox que escreveu a página "Expressão regular" também lançou código! re2 é uma biblioteca C ++ que garante tempo de execução O (length_of_regex) e limite configurável de uso de memória. Ele é usado no Google para que você possa digitar um regex na pesquisa de código do Google - o que significa que foi testado em batalha.

Sim.

Regexes podem ser usados ​​para executar ataques do DOS .
Não existe uma solução simples.

Você vai querer ler este artigo:

Troca insegura de contexto: inoculando expressões regulares para capacidade de sobrevivência O artigo é mais sobre o que pode dar errado com os mecanismos de expressão regular (por exemplo, PCRE), mas pode ajudar a entender o que você está enfrentando.

Você precisa não apenas se preocupar com a correspondência em si, mas como fazer a correspondência. Por exemplo, se sua entrada passar por algum tipo de fase de avaliação ou substituição de comando no caminho para o mecanismo de expressão regular, pode haver código que é executado dentro do padrão. Ou, se sua sintaxe de expressão regular permitir comandos incorporados, você também deve ter cuidado com isso. Como você não especificou o idioma em sua pergunta, é difícil dizer com certeza quais são todas as implicações de segurança.

Uma boa maneira de testar o seu RegEx quanto a problemas de segurança (pelo menos no Windows) é a ferramenta de difusão SDL RegEx, lançada recentemente pela Microsoft. Isso pode ajudar a evitar a construção RegEx patologicamente ruim.