Mostrar código-fonte de ReDoS

Um '''Ataque de negação de serviço por uso de expressão regular''' (também conhecido como '''ReDoS''', um [[Acrónimo|acrônimo]] em inglês para ''Regular expression Denial of Service'')<ref name="ReDoS in OWASP">{{Citar web|autor =[[OWASP]]|data=2010-02-10|url=http://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS|título=Regex Denial of Service|acessodata=2010-04-16}}</ref>
é um ataque de complexidade algorítmica que produz uma [[Ataque de negação de serviço|negação-de-serviço]], fornecendo uma [[expressão regular]] que leva muito tempo para ser avaliada. O ataque explora o fato de que a maioria das implementações de [[expressões regulares]] têm custo de [[Complexidade de Tempo|tempo exponencial]] no [[Complexidade de pior caso|pior caso]]: o tempo pode crescer exponencialmente em relação ao tamanho da entrada. Um invasor pode, portanto, fazer um programa passar uma quantidade efetivamente infinita de tempo processando fornecendo uma expressão regular como tal, deixando o programa lento ou o tornando irresponsivo.<ref name="RiverStar">{{Citar web|autor=[[RiverStar Software]]|data=2010-01-18|url=https://www.riverstarsoftware.com/kb/article/security-bulletin-caution-using-regular-expressions-17.html|título=Security Bulletin: Caution Using Regular Expressions|acessodata=2010-04-16|arquivourl=https://web.archive.org/web/20110715190436/https://www.riverstarsoftware.com/kb/article/security-bulletin-caution-using-regular-expressions-17.html|arquivodata=2011-07-15|urlmorta=yes}}</ref><ref name="ModSecurity">{{Citar livro|último =Ristic|primeiro =Ivan|título=ModSecurity Handbook|publicado=Feisty Duck Ltd|data=2010-03-15|local=London, UK|página=173|url=https://www.feistyduck.com/books/modsecurity-handbook/index.html|isbn=978-1-907117-02-2}}</ref>

== Descrição ==
Reconhecimento de expressão regulares pode ser feito através da construção de um [[autômato finito]]. As expressões regulares podem ser facilmente convertidas em [[Máquina de estados finitos não determinística|autômatos finitos não determinísticos]] (AFNs), em que, para cada estado e símbolo de entrada, podem existir vários possíveis próximos estados. Depois de construir o autômato, várias possibilidades existem:
* a máquina pode convertê-lo para um [[autômato finito determinístico]] (AFD) e executar a entrada pelo autômato resultante;
* a máquina pode tentar um por um todos os caminhos possíveis até que uma correspondência seja encontrada ou até que todos os caminhos sejam testados e falhem ("backtracking").<ref name="Crossby&Wallach">{{Citar web|autor=Crosby and Wallach, Usenix Security|ano=2003|url=http://www.cs.rice.edu/~scrosby/hash/slides/USENIX-RegexpWIP.2.ppt|título=Regular Expression Denial Of Service|acessodata=2010-01-13|arquivourl=https://web.archive.org/web/20050301230312/http://www.cs.rice.edu/~scrosby/hash/slides/USENIX-RegexpWIP.2.ppt|arquivodata=2005-03-01|urlmorta=yes}}</ref><ref name="Sullivan">{{Citar web|autor =[http://msdn.microsoft.com/en-us/magazine/ee532098.aspx?sdmr=BryanSullivan&sdmi=authors Bryan Sullivan], [[MSDN Magazine]]|data=2010-05-03|url=http://msdn.microsoft.com/en-au/magazine/ff646973.aspx|título=Regular Expression Denial of Service Attacks and Defenses|acessodata=2010-05-06}}</ref>
* a máquina pode considerar todos os caminhos possíveis através do autômato não determinístico em paralelo;
* a máquina pode converter o autômato não determinístico para um AFD [[Avaliação preguiçosa|preguiçosamente]] (''por exemplo'', enquanto roda, durante o reconhecimento).
Dos algoritmos acima, os dois primeiros são problemáticos. O primeiro é problemático, porque um autômato determinístico pode ter até <math>2^m</math> estados onde <math>m</math> é o número de estados do autômato não determinístico; assim, a conversão do AFN para um AFD pode levar [[Exptime|um tempo exponencial]]. O segundo é problemático, porque um autômato não determinístico pode ter um número exponencial de caminhos de comprimento <math>n</math>, de modo que a caminhada através de uma entrada de comprimento <math>n</math> também vai levar um tempo exponencial.<ref name="KirrageRathnayakeThielecke">{{Citar conferência|último1 =Kirrage|primeiro1 =J.|último2 =Rathnayake|primeiro2 =A.|último3 =Thielecke|primeiro3 =H.|título=Static Analysis for Regular Expression Denial-of-Service Attacks|títulolivro=Network and System Security|local=Madrid, Spain|páginas=135-148|publicado=Springer|ano=2013|url=http://link.springer.com/chapter/10.1007/978-3-642-38631-2_11|doi=10.1007/978-3-642-38631-2_11}}</ref>
Os dois últimos algoritmos, no entanto, não apresentam um comportamento patológico.

Note que para expressões regulares não-patológicas os algoritmos problemáticos são, normalmente, rápidos e, na prática, pode-se esperar que eles "[[Compilador|compilem]]" uma expressão regular em tempo O(m) e a reconheçam em tempo O(n); em vez disso, a simulação de um AFN e a computação preguiçosa do AFD tem [[Complexidade de Tempo|O]](m<sup>2</sup>n) como complexidade de pior caso.<ref>Lazy computation of the DFA can usually reach the speed of deterministic automatons while keeping worst case behavior similar to simulation of an NFA. </ref> Um Ataque de negação de serviço por uso de expressão regular ocorre quando essas expectativas são aplicadas a expressões regulares fornecidas pelo usuário, e expressões regulares mal-intencionadas fornecidas pelo usuário causam o pior caso de complexidade do reconhecedor de expressão regular.

Enquanto algoritmos regex podem ser escritos de uma forma eficiente, a maior parte das maquinas de expressão regular que existem estendem a linguagem de expressão regular com outras construções, que nem sempre podem ser resolvidas de forma eficiente. Tais [[Expressão regular|padrõe]]<nowiki/>s estendidos essencialmente forçam a implementação de expressões regulares na maioria das [[Linguagem de programação|linguagens de programação]] a usarem ''backtracking''.

== Exemplos ==

=== Regexes maliciosos ===
Regexes maliciosos que ficam emperrados em entradas modificadas podem ser diferentes dependendo do reconhecedor de expressão regular que está sob ataque. Para reconhecedores com backtrack, eles ocorrem sempre que estes fatores ocorrem:<ref name="Podcast">{{Citar web|autor =Jim Manico and Adar Weidman|data=2009-12-07|url=http://www.owasp.org/index.php/Podcast_56|título=OWASP Podcast 56 (ReDoS)|acessodata=2010-04-02}}</ref>
* a expressão regular aplica a repetição ("+", "*") para uma subexpressão complexa;
* para a subexpressão repetida, existe uma correspondência que também é um sufixo de outra correspondência válida.
A segunda condição é melhor explicada com um exemplo: na expressão regular <tt>(a[ab]*)<sup>+</sup></tt>, tanto "a" quanto "aa" podem corresponder à subexpressão repetida <tt>a[ab]*</tt>. Portanto, após o reconhecimento de "a", o autômato não determinístico pode tentar uma nova correspondência de <tt>[ab]*</tt> ou uma correspondência de <font face="monospace, Courier">"a"</font>. Se a entrada tem muitos "a"s consecutivos, cada um deles vai dobrar o número de caminhos possíveis pelo autômato. Exemplos de regexes mal-intencionados incluem o seguinte:
* <tt>(a+)+</tt>
* <tt>([a-zA-Z]+)*</tt>
* <tt>(a|aa)+</tt>
* <tt>(a|a?</tt><tt>)+</tt>
* <tt>(.*a){x}</tt> para x > 10
Todos acima são suscetíveis à entrada <tt>aaaaaaaaaaaaaaaaaaaaaaaa!</tt>. (O comprimento mínimo de entrada pode mudar ligeiramente, quando usadas máquinas mais rápidas ou mais lentas.)

Outros padrões podem não causar um comportamento exponencial, mas para entradas muito longas (geralmente algumas centenas de caracteres), elas ainda podem causar um grande tempo de reconhecimento. Um exemplo de tal padrão é "a*b?a*x" e a entrada sendo um sequência arbitrariamente longa de "a"s. Tal padrão também pode causar os reconhecedores com backtrack travar.

=== Regexes vulneráveis em repositórios online ===
Os chamados regexes  "mals" ou maliciosos foram encontrados em repositórios on-line de expressões regulares. Note que é o suficiente encontrar uma ''sub''expressão má para atacar o regex inteiro:
# [http://regexlib.com/REDetails.aspx?regexp_id=1757 RegExLib, id=1757 (validação de e-mail)] - a parte <span style="color:red">vermelha</span> é uma Regex Má<br><code>^([a-zA-Z0-9])<span style="color:red">(([\-.</code><code></span><span style="color:red">]|[_]+)?([a-zA-Z0-9]+))*</span>(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$</code>
# [[owasp:OWASP_Validation_Regex_Repository|Repositório de Validação de Regex da Owasp]], o Nome da classe Java - a parte <span style="color:red">vermelha</span> é uma Regex Má<br><code>^<span style="color:red">(([a-z])+.</span></code><code><span style="color:red">)+</span>[A-Z]([a-z])+$</code>
Estes dois exemplos também são suscetíveis a entrada <tt>aaaaaaaaaaaaaaaaaaaaaaaa!</tt>.

=== Ataques ===
Se um regex for ele próprio afetado pela entrada do usuário, o invasor pode injetar uma regex mal-intencionada e tornar o sistema vulnerável. Portanto, na maioria dos casos o ReDoS pode ser evitado eliminando a possibilidade do usuário executar padrões arbitrários no servidor. Neste caso, aplicativos web e bancos de dados são as principais aplicações vulneráveis. Alternativamente, uma página mal-intencionada pode travar o navegador da web do usuário ou fazer com que ele use uma quantidade arbitrária de memória.

No entanto, alguns dos exemplos do parágrafo acima são consideravelmente menos "artificiais" do que os outros; assim, eles demonstram como um regex vulnerável pode ser usado como um resultado de erros de programação. Neste caso scanners de email e [[Sistema de detecção de intrusos|sistemas de detecção de intrusão]] também podem ser vulneráveis. Felizmente, na maioria dos casos, expressões regulares problemáticas podem ser reescritas como padrões inofensivos. Por exemplo, <tt>(.*a){x}</tt> pode ser reescrita como<tt>([^a]*a){x}</tt>.

No caso de uma [[aplicação web]], o programador pode usar a mesma expressão regular para validar a entrada no ''client-side'' e também no ''server-side''. Um invasor pode inspecionar o código do ''client-side'', procurando as expressões regulares más, e enviar a entrada trabalhada diretamente para o servidor web para travá-lo.

== Ver também ==
* [[Ataque de negação de serviço]]
* [[Bug f00f do Pentium]]
* [[Ciberguerra|Guerra cibernética]]
* [[LOIC|Canhão de íons de baixa órbita]]
* [[Canhão de íons de alta órbita]]

== Referências ==
{{Reflist}}

== Ligações externas ==
* Exemplos de ReDoS em aplicações open source:
** [https://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2009-3277 ReDoS no DataVault]
** [https://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2009-3275 ReDoS no EntLib]
** [https://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2009-3276 ReDoS no NASD CORE.NET Terelik]
** [http://blog.malerisch.net/2015/09/net-mvc-redos-denial-of-service-vulnerability-cve-2015-2526.html ReDoS no] [http://blog.malerisch.net/2015/09/net-mvc-redos-denial-of-service-vulnerability-cve-2015-2526.html .NET Framework]
* Alguns benchmarks para ReDoS
** Achim Hoffman (2010). "[http://github.com/EnDe/ReDoS/ ReDoS - benchmark for regular expression DoS in JavaScript]". Acesso em : 2010-04-19.
** Richard M. Smith (2010). "[https://web.archive.org/web/20110722034953/http://www.computerbytesman.com/redos/ Regular expression denial of service (ReDoS) attack test results]". Acesso em : 2010-04-19.
* Artigo na implementação de expressões regulares invulneráveis a certas classes de ReDoS
** Russ Cox (2007). "[http://swtch.com/~rsc/regexp/regexp1.html Regular Expression Matching Can Be Simple And Fast]".  Acesso em : 2011-04-20.
* Uma ferramenta para a detecção de vunerabilidades a ReDoS
** H. Thielecke, A. Rathnayake (2013). "[http://www.cs.bham.ac.uk/~hxt/research/rxxr.shtml Regular expression denial of service (ReDoS) static analysis]". Acesso em : 2013-05-30.

[[Categoria:Ataques de negação de serviço]]