Este artigo foi traduzido por máquina.

Informativos sobre segurança

Ataques de negação de serviço de expressão regular e defesas

Bryan Sullivan

Na edição de novembro de 2009, escrevi um artigo intitulado “ XML negação de serviço de ataques e defesas ” (MSDN.Microsoft.com/magazine/ee335713), em que descrevi alguns particularmente eficaz de negação de técnicas de ataque do serviço (DoS) contra analisadores de XML. Recebi muitos emails sobre este artigo de querer saber mais, os leitores que encoraja realmente me pessoas entendam como graves DoS ataques podem ser.

Acredito que nos próximos quatro ou cinco anos, como o escalonamento de privilégios ataques mais difícil executar devido ao aumento da adoção de proteção de memória, como prevenção de execução de dados (DEP), Address Space Layout aleatória (ASLR) e isolamento e técnicas de redução de privilégio, os invasores mudará o foco para ataques de chantagem. Os desenvolvedores podem continuar a proteger seus aplicativos, permanecer à frente da curva ataque tendência e endereçamento vetores potenciais de negação de serviço futuras hoje.

Um desses vetores potenciais de negação de serviço futuras é a negação de serviço de expressão regular. Da conferência de Israel OWASP (Open Web Application Security Project) 2009, diretor de Checkmarx Architect Alex Roichman e sênior programador Adar Weidman apresentado alguns excelente pesquisa no tópico da expressão regular DoS ou “ refaça. ” Suas pesquisas revelaram que uma expressão regular mal-escrito pode ser explorada para que tenham uma seqüência de caracteres de ataque relativamente curto (menos de 50 caracteres) horas ou mais para avaliar. No pior cenário, o tempo de processamento é realmente exponencial do número de caracteres na seqüência de entrada, que significa que adicionar um caractere único para a seqüência de caracteres dobra o tempo de processamento.

Neste artigo, descreverei o que torna um regex vulneráveis a esses ataques. Também apresentarei código para um difusor Regex, um utilitário de teste criado para identificar regexes vulnerável, avaliando-os contra milhares de entradas aleatórias e sinalizar se qualquer uma das entradas demorado um demais para o processamento completo.

(observação: Neste artigo, suponho que você está familiarizado com a sintaxe de expressões regulares. Se não for esse o caso, convém pincel ao ler o artigo “ .NET Framework Regular Expressions ” em MSDN.Microsoft.com/Library/hs600312, ou para um Mergulho profundo, leia excelente referência livro de Jeffrey Friedl, “ Mastering Regular Expressions 3ª edição ” [O’Reilly 2006].)

Backtracking: A raiz do problema

Existem basicamente dois tipos diferentes de mecanismos de expressão regular: Mecanismos de automação finite (DFA) determinista e mecanismos de automação não determinísticas finite (NFA). Uma análise completa das diferenças entre esses tipos de dois mecanismo está além do escopo deste artigo; precisamos apenas para se concentrar em dois fatos:

1. NFA mecanismos são mecanismos backtracking. Ao contrário do DFAs, qual avaliar cada caractere em uma seqüência de caracteres de entrada no máximo uma vez, mecanismos NFA podem avaliar cada caractere em uma seqüência de caracteres de entrada várias vezes. (Posteriormente demonstrarei como funciona esse algoritmo avaliação backtracking.) A abordagem backtracking tem benefícios, em que esses mecanismos podem processar expressões regular mais complexa, como aqueles que contêm referências anteriores ou captura parênteses. Ele também apresenta desvantagens, em que o tempo de processamento muito pode exceder que DFAs.
2. As classes Microsoft .NET Framework System.Text.RegularExpression usam mecanismos NFA.

Um importante efeito colateral backtracking é que, embora o mecanismo de regex pode confirmar rapidamente uma correspondência positiva (ou seja, uma seqüência de caracteres de entrada corresponder ao dado um regex), confirmar uma correspondência negativa (a seqüência de caracteres de entrada não corresponde a regex) pode demorar bastante um pouco mais. Na verdade, o mecanismo deve confirmar que nenhum dos possíveis “ caminhos ” a cadeia de caracteres de entrada corresponder ao regex, o que significa que todos os caminhos tem de ser testada.

Com uma expressão regular simples do agrupamento não, o tempo gasto para confirmar a correspondências negativas não é um enorme problema. Por exemplo, suponha que a expressão regular para ser comparado com é:

^\d+$

Este é um regex muito simples que combina se a seqüência de caracteres de entrada inteira é composta de apenas caracteres numéricos. O ^ e $ caracteres representam o início e o fim da seqüência de caracteres, respectivamente, \d expressão representa um caractere numérico, e + indica que corresponderá a um ou mais caracteres. Teste Let’s essa expressão usando 123456X como uma seqüência de caracteres de entrada.

Essa seqüência de caracteres de entrada é, obviamente, não uma correspondência, porque X não é um caractere numérico. Mas quantos caminhos a regex exemplo teria a ser avaliada como para chegar a essa conclusão? Ele deve começar sua avaliação no início da seqüência de caracteres e ver que o caractere 1 é um caractere numérico válido e corresponde a regex. Ele seria, em seguida, vá para o caractere 2, que também deve corresponder ao. Para que o regex tenha correspondente a seqüência de caracteres de 12 neste momento. Em seguida ele seria tente 3 (e corresponder 123), e assim por diante até que ele tem de X, que não deve corresponder.

No entanto, como o nosso mecanismo é um mecanismo NFA backtracking, ele não dá neste momento. Em vez disso, faz o backup de sua correspondência atual (123456) para sua correspondência de boa conhecida última (12345) e tentará novamente a partir daí. Como o próximo caractere após 5 não é o fim da cadeia de caracteres, o regex não é uma correspondência e faz o backup dos seu anterior última conhecida boa correspondência (1234) e tentará novamente. Isso continua completamente até que o mecanismo obtém de volta para sua primeira correspondência (1) e descobre que o caractere após 1 não é o fim da cadeia de caracteres. Neste momento o regex desistirá; nenhuma correspondência foi encontrada.

Enfim, o mecanismo avaliada seis caminhos: 123456, 12345, 1234, 123, 12 e 1. Se a seqüência de caracteres de entrada fosse um caractere a mais, o mecanismo seria ter um caminho mais avaliada. Portanto, essa expressão regular é um algoritmo linear contra o comprimento da seqüência de caracteres e não está em risco de causar uma negação de serviço. Um objeto System.Text.RegularExpressions.Regex usando ^ \d+$ para seu padrão é rápida o suficiente para desfazer praticamente instantaneamente por meio de seqüências de entrada mesmo enormes (mais de 10.000 caracteres).

Agora altere let’s a expressão regular para grupo de caracteres numéricos:

^(\d+)$

Isso não altera substancialmente o resultado das avaliações de; ele simplesmente permite ao desenvolvedor acessar qualquer correspondência como um grupo capturado. (Essa técnica pode ser útil em expressões regulares mais complicadas em que você pode querer aplicar operadores de repetição, mas neste caso específico não possui nenhum valor.) Adicionar parênteses agrupamento nesse caso não substancialmente altera velocidade de execução da expressão, ou. Teste o padrão contra 123456X entrada ainda faz com que o mecanismo para avaliar apenas seis caminhos diferentes. No entanto, a situação é significativamente diferente se fizermos uma alteração pequena mais a regex:

^(\d+)+$

O extra + caractere após a expressão de grupo (\d+) informa ao mecanismo de regex para coincidir qualquer número de grupos capturados. O mecanismo continuará como antes, conhecendo 123456 antes backtracking para 12345.

Eis aqui onde as coisas ficam “ interessantes ” (como no terrivelmente perigoso). Em vez de apenas verificar que o próximo caractere após 5 não é o fim da cadeia de caracteres, o mecanismo trata o próximo caractere, 6, como uma nova captura de grupo e inicia rechecking de lá. Depois que essa rota falhar, ele faz até 1234 e, em seguida, tenta 56 como um grupo de captura separado e, em seguida, 5 e 6 cada como grupos de captura separado. O resultado final é que o mecanismo realmente acaba avaliando 32 caminhos diferentes.

Se agora adicionamos apenas um caractere numérico mais para a seqüência de avaliação, o mecanismo terá que avaliar 64 caminhos — o dobro — para determinar que não é uma correspondência. Este é um aumento exponencial do volume de trabalho sendo executado pelo mecanismo de regex. Um invasor poderia fornecer uma seqüência de caracteres de entrada relativamente curta — 30 caracteres ou menos — e força o mecanismo de processo de centenas de milhões de caminhos, associando-lo para horas ou dias.

Ar sua lavanderia Dirty

É ruim suficiente quando um aplicativo tem capaz de negação de serviço regexes exponencial enfiados imediatamente no código do lado do servidor. É ainda pior quando um aplicativo anuncia suas vulnerabilidades no código do lado do cliente. Muitos dos controles de validação ASP.NET derivados System.Web.UI.WebControls.BaseValidator, incluindo RegularExpressionValidator, serão executado automaticamente a mesma lógica de validação no cliente em JavaScript como faziam no servidor no código. NET.

Na maioria das vezes, isso é algo bom. É recomendável salvar o tempo de ida e volta de envio de um formulário para o servidor apenas para que ele seja rejeitada por um validador porque o usuário digitado incorretamente um campo de entrada do usuário. É recomendável salvar o servidor o tempo de processamento muito. No entanto, se o aplicativo está usando um regex defeituoso no seu código do servidor, esse regex incorreto também for utilizado em seu código de cliente e agora será extremamente fácil para um invasor localizar esse regex e desenvolver uma seqüência de caracteres de ataque para ele.

Por exemplo, digamos que eu crie um novo formulário da Web e adicione um TextBox e um RegularExpressionValidator para esse formulário. Eu defina a propriedade ControlToValidate do validator com o nome da caixa de texto e defina a ValidationExpression para dentre as regexes incorreto que discuti:

this.RegularExpressionValidator1.ControlToValidate = "TextBox1";

this.RegularExpressionValidator1.ValidationExpression = @"^(\d+)+$";

Se eu agora abrir esta página em um navegador e exibir sua origem, vejo o seguinte código JavaScript próximo à parte inferior da página:

<scripttype="text/javascript">

//< ![CDATA[

var RegularExpressionValidator1 = document.all ? 

  document.all["RegularExpressionValidator1"] : 

  document.getElementById("RegularExpressionValidator1");

RegularExpressionValidator1.controltovalidate = "TextBox1";

RegularExpressionValidator1.validationexpression = "^(\\d+)+$";

//]] >

</script>

Ele é, para o mundo inteiro ver: regex exponencial visíveis sem formatação na última linha do bloco de script.

Mais padrões de problemas

Obviamente, ^(\d+)+$ is not the only bad regular expression in the world. Basicamente, qualquer expressão regular que contém uma expressão de agrupamento com repetição que é repetido vai ser vulnerável. Isso inclui regexes como:

^(\d+)*$
^(\d*)*$
^(\d+|\s+)*$

Além disso, qualquer grupo que contém a alternação onde subexpressions alternativos se sobrepõem outro também é vulnerável:

^ (\d|\d\d)+$
^(\d|\d?)+$

Se você viu uma expressão como no exemplo anterior em seu código agora, você poderia provavelmente poderá identificá-lo como vulneráveis apenas a partir do visto de. Mas podem deixar uma vulnerabilidade no mais, expressão mais complicado (e mais realista):

^ ([0-9a-zA-Z]([-. \w]*[0-9a-zA-Z])*@(([0-9a-zA-Z])+([-\w]*[0-9a-zA-Z])*\.)+ [a-zA-Z] {2,9}) $

Isso é uma expressão regular encontrada no site do Regular Expression Library Web (regexlib.com) deve ser usado para validar um endereço de email. No entanto, também é vulnerável a ataques. Você pode encontrar essa vulnerabilidade através da inspeção de manuais de código ou talvez não. Uma técnica melhor para localizar esses problemas é necessária e que é o que vou discutir a seguir.

Localizando Regexes incorreta em seu código

Idealmente, deve haver uma maneira de localizar regexes exponenciais em seu código em tempo de compilação e avisá-lo sobre eles. Presumivelmente, para analisar uma cadeia de caracteres regex e analisá-los para pontos fracos em potencial, seria necessário mais um regex. Neste ponto, eu sinto como largar um regex: “ Don preciso de Ajuda, eu só preciso mais regexes ”! Infelizmente, minhas habilidades regex não são até a tarefa de escrever um regex para analisar regexes. Se você acredita que você tem trabalho código para isso, envie-o para mim e eu ficará feliz em dar você crédito na coluna de resumos de segurança do mês que vem. Enquanto isso, porque eu Don têm uma maneira de detectar regexes incorreto em tempo de compilação, farei a segunda melhor coisa: Escreverei um difusor de regex.

A difusão é o processo de fornecer dados aleatórios e malformados para entradas de um aplicativo para torná-la falhar. As fuzzing mais iterações você executar, melhor a chance de você encontrará um bug, portanto, é comum para as equipes executar milhares ou milhões de iterações por entrada. As equipes de segurança da Microsoft descobriu que isso seja uma maneira incrivelmente eficiente de encontrar bugs, portanto, a equipe de SDL fez um requisito para todas as equipes de produtos e serviços de difusão.

Para meu difusor desejo difuso aleatórias seqüências de caracteres de entrada a minha expressão regular. Começarei definindo uma seqüência de caracteres const para meu regex, um método testInputValue que verifica a regex e seqüências de caracteres de alimentação para testInputValue de entrada de um método runTest que irá coletar aleatório.

const string regexToTest = @"^(\d+)+$";



static void testInputValue(string inputToTest)

{

  System.Text.RegularExpressions.Regex.Match(inputToTest, regexToTest);

}



void runTest()

{

  string[] inputsToTest = {};



  foreach (string inputToTest in inputsToTest)

  testInputValue(inputToTest);

}

Observe que não há nenhum código ainda para gerar valores de entrada fuzzed; abordarei a isso em breve. Observe também que o código não se preocupe em para verificar o valor de retorno do Regex.Match. Isso ocorre porque eu realmente Don importa se a entrada coincide com o padrão ou Don. Tudo o que me preocupar nessa situação é se leva muito tempo para decidir se a entrada coincide com o mecanismo de regex.

Normalmente os fuzzers são usadas para tentar encontrar vulnerabilidades de elevação de privilégio pode ser explorado, mas novamente, neste caso, estou apenas interessado em encontrar vulnerabilidades de negação de serviço. Eu simplesmente não pode alimentar meus dados de aplicativo de teste para ver se ele falha; eu precisa ser capaz de detectar se ele está travado. Embora não possa ser o método científica maioria, pode fazer isso efetivamente executando cada teste regex seqüencialmente em um segmento de trabalho separado e definindo um valor de tempo limite para a conclusão do thread que. Se o thread não concluir seu processamento dentro de um período razoável de tempo, diz cinco segundos para uma única entrada de teste, presumimos que a expressão regular foi que gostaria de negação de serviço. Eu irá adicionar um ManualResetEvent e modificar os métodos testInputValue e runTest da mesma forma, conforme mostrado no Figura 1.

Figura 1 Teste com segmentos de trabalho separado

static ManualResetEvent threadComplete = new ManualResetEvent(false);



static void testInputValue(object inputToTest)

{

  System.Text.RegularExpressions.Regex.Match((string)inputToTest, 

    regexToTest);

  threadComplete.Set();

}



void runTest()

{

  string[] inputsToTest = {};



  foreach (string inputToTest in inputsToTest)

  {

    Thread thread = new Thread(testInputValue);

    thread.Start(inputToTest);



    if (!threadComplete.WaitOne(5000))

    {

      Console.WriteLine("Regex exceeded time limit for input " + 

        inputToTest);

      return;

    }



    threadComplete.Reset();

  }



  Console.WriteLine("All tests succeeded within the time limit.");

}

Agora é hora de gerar os valores de entrada. Isso é na verdade, mais difícil do que parece. Se eu gerar apenas dados aleatórios completamente, é improvável que nada dela corresponderia suficiente regex para revelar uma vulnerabilidade. Por exemplo, se eu testo a regex ^ (\d+)+$ com XdO(*iLy@Lm4p$, the regex will instantly not match and the problem will remain hidden. entrada Preciso gerar entradas seja bastante próximos para que o aplicativo espera para o teste sejam úteis e para que eu precisa de uma maneira de gerar dados aleatórios que corresponda a um determinado regex.

Planos de geração de dados em ação

Felizmente, há um recurso em projetos de banco de dados Visual Studio que pode fazer exatamente isso: Planeje a geração de dados. Se você estiver usando o Visual Studio Team Suite, você também terá acesso a esse recurso. Planos de geração de dados são usados para preencher rapidamente os bancos de dados com os dados de teste. Eles podem preencher tabelas com aleatória de seqüências de caracteres ou valores numéricos ou (Felizmente para nós) seqüências de caracteres de correspondência especificada expressões regulares.

Você precisa primeiro criar uma tabela em um SQL Server 2005 ou 2008 banco de dados no qual você pode gerar dados de teste. Uma vez feito isso, volte para o Visual Studio e criar um novo projeto SQL Server Database. Edite as propriedades do projeto de banco de dados fornecê-la com uma seqüência de caracteres de conexão ao seu banco de dados. Depois de inserido uma seqüência de caracteres de conexão e testado-o para verificar se que ele funciona, retorne ao Solution Explorer e adicione um novo item do plano de geração de dados para o projeto. Neste ponto, você deve visualizar algo como Figura 2.

Figura 2 Um item do plano de geração de dados no Visual Studio

Agora escolha a tabela e coluna que você deseja preencher com dados de entrada do difusor. Na seção de tabela, defina o número de teste de valores a serem gerados (linhas a inserir coluna). Escrevi anteriormente que fuzzers geralmente testem centenas de milhares ou milhões de iterações para tentar encontrar problemas. Embora eu geralmente aprovar este nível de rigor, é um exagero para fins de difusor esse regex. Se um regex travar, vai fazê-lo dentro de duas iterações de teste centenas. Sugira a configuração de linhas para inserir valor para 200, mas se você desejar testar mais, sinta-se à vontade.

Na seção colunas, agora definir o gerador para expressões regulares e insira o valor de padrão regex que deseja testar como o valor da propriedade Expression no guia de propriedades da coluna. É importante observar que a propriedade Expression não dá suporte a todos os caracteres legais de expressão regular. Não é possível inserir âncoras inicial e final de linha ^ e $ (ou mais precisamente, você pode inseri-los, mas o gerador de gerará um literal ^ ou o caractere $ no teste de entrada). Basta deixe esses caracteres check-out. Você encontrará uma lista completa dos operadores que suporte o gerador de expressões regulares em MSDN.Microsoft.com/Library/aa833197(VS.80).

Um problema maior é que a propriedade Expression também não oferece suporte notações abreviada comuns, como \d para dígitos numéricos ou \w para caracteres alfabéticos. Se sua regex usa essas, você terá para substituí-los com seus equivalentes da classe de caractere: [0-9], em vez de \d, [a-zA-Z0-9_] em vez de \w e assim por diante. Se você precisar substituir \s (caractere de espaço em branco), você pode inserir um espaço literal em seu lugar.

Sua última tarefa no projeto do banco de dados é realmente preencher o banco de dados com os dados de teste de acordo com suas especificações. Para fazer isso, escolhendo os dados | DataGenerator | gerar dados item de menu ou apenas pressione F5.

Adicionando o ataque

Voltar no código do difusor, modifique o método runTest para que ele recebe dados de teste gerados do banco de dados. Você pode pensar terminar depois de fazer isso, mas na verdade, há uma alteração mais importante a fazer. Se você executar o difusor agora, até mesmo contra um regex ruins conhecido como ^(\d+)+$, it will fail to find any problems and report that all tests succeeded. Isso ocorre porque todos os dados de teste gerados é uma correspondência válida para sua regex.

Se lembrar de anteriormente eu afirmou que mecanismos de regex NFA podem rapidamente confirme que problemas e uma correspondência positiva realmente só acontecerá em correspondências negativas. Além disso, por causa da natureza backtracking ’ NFAs, problemas só ocorrem quando há um grande número de caracteres correspondentes no início da entrada e o caractere incorreto é exibido no final. Se um caractere incorreto apareceu na frente da seqüência de caracteres de entrada, o teste deve concluir instantaneamente.

A alteração final para fazer o código do difusor é anexar caracteres inválidos para o final das entradas de teste. Tornar uma matriz de seqüência de caracteres que contém alfabéticos, numéricos, pontuação e caracteres de espaço em branco:

 

string[] attackChars = { "0", "1", "9", "X", "x", "+", 

"-", "@", "!", "(", ")", "[", "]", "\\", "/", 

"?", "<", ">", ".", ",", ":", ";", " ", "" };

Agora modifique o código para que cada seqüência de caracteres de entrada recuperada do banco de dados é testada com cada um desses caracteres de ataque acrescentados a ele. Portanto, a primeira seqüência de caracteres de entrada deve ser testada com um caractere 0 anexado a ele, em seguida, com um 1 caractere acrescentado a ele e assim por diante. Depois que a seqüência de caracteres de entrada foi testada com cada um dos caracteres de ataque, mover para a próxima seqüência de caracteres de entrada e testá-la com cada um dos caracteres de ataque.

foreach (string inputToTest in inputsToTest)

{

  foreach (string attackChar in attackChars)

  {

    Threadthread = new Thread(testInputValue);

    thread.Start(inputToTest + attackChar);

...

Agora você tem dois problemas

Há uma cotação famosa pela Netscape ex engenharia Zawinski Jaime sobre expressões regulares:

“ Achar que algumas pessoas, quando confrontados com um problema, ‘ sei, eu use expressões regulares. ’ Agora eles têm dois problemas. ”

Enquanto estou longe próximo cínico sobre regexes como SR.. Zawinski, eu irá admitir o que pode ser bastante desafiador apenas para escrever um regex correto, muito menos um regex correto é seguro contra ataques de negação de serviço. Eu recomendo que você para examinar todas as regexes exponencial da complexidade e usar técnicas de fuzzing para verificar suas descobertas.

Bryan Sullivan é um gerente do programa de segurança para a equipe do Microsoft Security Development Lifecycle, onde especialista em aplicativo Web e .NET problemas de segurança. Ele é autor de “ AJAX Security ” (Addison-Wesley, 2007).

Graças aos seguintes especialistas técnicos para revisar este artigo: Barclay Hill, Michael Howard, Ron Petrusha e Justin van Patten