title: Regular Expression High CPU
body: <p>We are encountering issues in our production environment with 100% CPU utilization and thread dump shows our "Black List" implementation stuck on following.</p>
  
  <pre><code>[11/14/13 10:12:42:745 CST] 0000000d ThreadMonitor W   WSVR0605W: Thread "Thread-002" (0000003b) has been active for 604063 milliseconds and may be hung.  There is/are 1 thread(s) in total in the server that may be hung.
      at java.lang.Character.isLetterOrDigit(Character.java:3516)
      at java.util.regex.Pattern$Bound.check(Pattern.java:4820)
      at java.util.regex.Pattern$Bound.match(Pattern.java:4832)
      at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
      at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
      at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
      at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
      at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
      at java.util.regex.Matcher.match(Matcher.java:1127)
      at java.util.regex.Matcher.matches(Matcher.java:502)
  </code></pre>
  
  <p>The problem is this does not happen always which mean it is data dependent and we have following list of Regular Expressions in our Black List implementation.</p>
  
  <p>I would appreciate if someone can tell which regular expression out of the following can potentially cause the 100% CPU (I would guess due to back tracking).</p>
  
  <pre><code># zero/null bytes 
  .*\x00.*
  
  # javascript
  .*\bjavascript\b.* &amp;&amp;! ^[\w.,;/*+= -]*\b(:?application/x-javascript|text/javascript)\b[\w.,;/*+= -]*$
  # vbscript
  .*\bvbscript\b.*
  
  # &lt;script or &lt;/script&gt;
  .*&lt;\s*/?\s*script\b.*|.*\bscript\s*&gt;.*
  # &lt;img or &lt;/img&gt;
  .*&lt;\s*/?\s*img\b.*|.*\bimg\s*&gt;.*
  # &lt;div or &lt;/div&gt;
  .*&lt;\s*/?\s*div\b.*|.*\bdiv\s*&gt;.*
  # &lt;html or &lt;/html&gt;
  .*&lt;\s*/?\s*html\b.*|.*\bhtml\s*&gt;.*
  # &lt;body or &lt;/body&gt;
  .*&lt;\s*/?\s*body\b.*|.*\bbody\s*&gt;.*
  # &lt;link or &lt;/link&gt;
  .*&lt;\s*/?\s*link\b.*|.*\blink\s*&gt;.* &amp;&amp;! ^&lt;\?xml .*$
  # &lt;meta or &lt;/meta&gt;
  .*&lt;\s*/?\s*meta\b.*|.*\bmeta\s*&gt;.*
  # &lt;base or &lt;/base&gt;
  .*&lt;\s*/?\s*base\b.*|.*\bbase\s*&gt;.*
  # &lt;span or &lt;/span&gt;
  .*&lt;\s*/?\s*span\b.*|.*\bspan\s*&gt;.*
  # &lt;input or &lt;/input&gt;
  .*&lt;\s*/?\s*input\b.*|.*\binput\s*&gt;.*
  # &lt;style or &lt;/style&gt;
  .*&lt;\s*/?\s*style\b.*|.*\bstyle\s*&gt;.*
  # &lt;table or &lt;/table&gt;
  .*&lt;\s*/?\s*table\b.*|.*\btable\s*&gt;.*
  # &lt;embed or &lt;/embed&gt;
  .*&lt;\s*/?\s*embed\b.*|.*\bembed\s*&gt;.*
  # &lt;frame or &lt;/frame&gt;
  .*&lt;\s*/?\s*frame\b.*|.*\bframe\s*&gt;.*
  # &lt;iframe or &lt;/iframe&gt;
  .*&lt;\s*/?\s*iframe\b.*|.*\biframe\s*&gt;.*
  # &lt;object or &lt;/object&gt;
  .*&lt;\s*/?\s*object\b.*|.*\bobject\s*&gt;.*
  
  # &lt; onload= &gt;
  .*&lt;.+\bonload\s*=.+&gt;.*
  # &lt; onerror= &gt;
  .*&lt;.+\bonerror\s*=.+&gt;.*
  # &lt; onmouseover= &gt;
  .*&lt;.+\bonmouseover\s*=.+&gt;.*
  # &lt; src= &gt;
  .*&lt;.+\bsrc\s*=.+&gt;.*
  # &lt; href= &gt;
  .*&lt;.+\bhref\s*=.+&gt;.*
  # &lt; style= &gt;
  .*&lt;.+\bstyle\s*=.+&gt;.*
  # &lt; content= &gt;
  .*&lt;.+\bcontent\s*=.+&gt;.*
  
  # document.
  .*\bdocument\s*\..+
  # element.
  .*\belement\s*\..+
  
  # url(
  .*\burl\s*\(.+
  # eval(
  .*\beval\s*\(.+
  # alert(
  .*\balert\s*\(.+
  
  # /* */
  .*/\*.*\*/.*
  
  
  # HTTP response splitting
  .*\bHTTP/\d+\.\d+.+
  
  
  # Path traversal
  #.*\.\.[/\\].*
  .*\.\.[/\\]\.\.[/\\].*
  
  
  # SQL injection (probably not very useful)
  
  # from HttpServletBase.java
  .*select\s+\S*\s*from\s+\S+(?:\s+where\s+.+)?.*
  .*insert\s+\S*\s*into\s+\S+(?:\s+values\s+.+)?.*
  .*update\s+\S*\s*set\s+\S+(?:\s+where\s+.+)?.*
  .*delete\s+\S*\s*from\s+\S+(?:\s+where\s+.+)?.*
  </code></pre>