Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-6393051

Provide notification in Matcher.find() for regular expressions with exponential resolution time

XMLWordPrintable

    • Icon: Enhancement Enhancement
    • Resolution: Won't Fix
    • Icon: P2 P2
    • None
    • 1.4.2_06
    • core-libs

      Sometimes using a long input string with some regular expressions the java.util.regex.Matcher.find() method never exit and cpu usage is 100%

      The problem can be reproduced on any system with any jvm version (1.4.2_xx, 1.5.0_xx, 1.6.0) but customer is using 1.4.2_06 with Application Server 8.1

      A notification system is needed (try/catch or similar) to avoid the hang of jvm (or the process which loaded jvm)

      In attachment there is a simple testcase with both a wrong (testpattern/Main) and a fixed (fixedpattern/Main) pattern for the same input string

      The java.util.regex.Pattern which generate the problem is

      Pattern.compile("(<frame(\\s+\\w+(=[\"\']?[^\"\']*[\"\']?)*)*(\\s+src\\s*=\\s*[\"\']?))([^\"\']+)([\"\']?(\\s+\\w+(=[\"\']?[^\"\']*[\"\']?)*)*\\s*/?\\s*>)",Pattern.CASE_INSENSITIVE);

      The java.util.regex.Matcher is initialized with a StringBuffer which is a frame tag from an html page with a very long src attribute

      The stack is really deep

      "main" prio=10 tid=0x00036a10 nid=0x1 runnable [0xffbea000..0xffbeede0]
              at java.util.regex.Pattern$Ctype.match(Pattern.java:3533)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4223)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4242)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
              at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
              at java.util.regex.Pattern$Loop.match(Pattern.java:4706)
              at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4235)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$SingleA.match(Pattern.java:3372)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.matchInit(Pattern.java:4716)
              at java.util.regex.Pattern$Prolog.match(Pattern.java:4653)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4235)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4242)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
              at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
              at java.util.regex.Pattern$Loop.match(Pattern.java:4706)
              at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4235)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$SingleA.match(Pattern.java:3372)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
              at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4235)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$SingleA.match(Pattern.java:3372)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
              at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4235)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$SingleA.match(Pattern.java:3372)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
              at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4235)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$SingleA.match(Pattern.java:3372)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
              at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4235)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$SingleA.match(Pattern.java:3372)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
              at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4235)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$SingleA.match(Pattern.java:3372)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
              at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4235)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$SingleA.match(Pattern.java:3372)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
              at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4235)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$SingleA.match(Pattern.java:3372)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
              at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4235)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$SingleA.match(Pattern.java:3372)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.matchInit(Pattern.java:4716)
              at java.util.regex.Pattern$Prolog.match(Pattern.java:4653)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4235)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4242)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.match(Pattern.java:4697)
              at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
              at java.util.regex.Pattern$Loop.match(Pattern.java:4706)
              at java.util.regex.Pattern$GroupTail.match(Pattern.java:4629)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4235)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Ques.match(Pattern.java:4144)
              at java.util.regex.Pattern$SingleA.match(Pattern.java:3372)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.matchInit(Pattern.java:4716)
              at java.util.regex.Pattern$Prolog.match(Pattern.java:4653)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4235)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$Curly.match0(Pattern.java:4242)
              at java.util.regex.Pattern$Curly.match(Pattern.java:4197)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Loop.matchInit(Pattern.java:4716)
              at java.util.regex.Pattern$Prolog.match(Pattern.java:4653)
              at java.util.regex.Pattern$SliceA.match(Pattern.java:3831)
              at java.util.regex.Pattern$GroupHead.match(Pattern.java:4570)
              at java.util.regex.Pattern$Start.match(Pattern.java:3019)
              at java.util.regex.Matcher.search(Matcher.java:1092)
              at java.util.regex.Matcher.find(Matcher.java:528)
              at testpattern.Main.main(Main.java:37)

      The pattern which works is:

      Pattern.compile("((<frame\\s.*src\\s*=\\s*[\"\']?)([^\"\'>]*)([\"\']?)(.*>))",Pattern.CASE_INSENSITIVE)

            sherman Xueming Shen
            cmassi Claudio Massi (Inactive)
            Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

              Created:
              Updated:
              Resolved:
              Imported:
              Indexed: