255 for finding out whether a string of 28 \texttt{a}s matches the regular |
255 for finding out whether a string of 28 \texttt{a}s matches the regular |
256 expression \texttt{a?\{28\}\,a\{28\}}. Ruby is even slightly |
256 expression \texttt{a?\{28\}\,a\{28\}}. Ruby is even slightly |
257 worse.\footnote{In this example Ruby uses the slightly different |
257 worse.\footnote{In this example Ruby uses the slightly different |
258 regular expression \texttt{a?a?a?...a?a?aaa...aa}, where the |
258 regular expression \texttt{a?a?a?...a?a?aaa...aa}, where the |
259 \texttt{a?} and \texttt{a} each occur $n$ times. More such test |
259 \texttt{a?} and \texttt{a} each occur $n$ times. More such test |
260 cases can be found at \url{http://www.computerbytesman.com/redos/}.} |
260 cases can be found at \url{https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS}.} |
261 Admittedly, these regular expressions are carefully chosen to exhibit |
261 Admittedly, these regular expressions are carefully chosen to exhibit |
262 this exponential behaviour, but similar ones occur more often than one |
262 this exponential behaviour, but similar ones occur more often than one |
263 wants in ``real life''. For example, on 20 July 2016 a similar regular |
263 wants in ``real life''. For example, on 20 July 2016 a similar regular |
264 expression brought the webpage \href{http://stackexchange.com}{Stack |
264 expression brought the webpage \href{http://stackexchange.com}{Stack |
265 Exchange} to its knees: |
265 Exchange} to its knees: |