title: How can I recognize an evil regex?
body: <p>I recently became aware of <a href="https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS">Regular expression Denial of Service</a> attacks, and decided to root out so-called 'evil' regex patterns wherever I could find them in my codebase - or at least those that are used on user input. The examples given at the <a href="https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS">OWASP link</a> above and <a href="https://en.wikipedia.org/wiki/ReDoS">wikipedia</a> are helpful, but they don't do a great job of explaining the problem in simple terms.</p>
  
  <p>A description of evil regexes, from <a href="https://en.wikipedia.org/wiki/ReDoS#Evil_regexes">wikipedia</a>:</p>
  
  <ul>
  <li>the regular expression applies repetition ("+", "*") to a complex subexpression;</li>
  <li>for the repeated subexpression, there exists a match which is also a suffix of another valid match.</li>
  </ul>
  
  <p>With examples, again from <a href="https://en.wikipedia.org/wiki/ReDoS#Evil_regexes">wikipedia</a>:</p>
  
  <ul>
  <li><code>(a+)+</code></li>
  <li><code>([a-zA-Z]+)*</code></li>
  <li><code>(a|aa)+</code></li>
  <li><code>(a|a?)+</code></li>
  <li><code>(.*a){x}</code> for x > 10</li>
  </ul>
  
  <p>Is this a problem that just doesn't have a simpler explanation? I'm looking for something that would make it easier to avoid this problem while writing regexes, or to find them within an existing codebase.</p>