FULL PRODUCT VERSION :
java version "1.6.0"
Java(TM) SE Runtime Environment (build 1.6.0-b105)
Java HotSpot(TM) Client VM (build 1.6.0-b105, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Microsoft Windows XP [Version 5.1.2600]

A DESCRIPTION OF THE PROBLEM :
Following the general discussion on http://perlmonks.org/index.pl?node_id=502408 regarding java / perl regex handling (this link is a good reading for a deep understanding of the problem) the following regular expression

^(\s*foo\s*)*$

was tested using the input string

foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo fo

(note the ending is "fo" and not "foo")

which results in a program execution of the Matcher.find() method that will take hundreds of years to finish (exponential duration) rendering this method useless in cases of the same nature like the simplified sample above.



STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Execute the source code provided as a test case

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Method executing within a few milliseconds
ACTUAL -
Method has an exponential execution time (de-facto infinite execution time)

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.regex.*;

    public class JavaBugRegEx {
        public static final void main(String[] args) {
            System.out.println("Start");
            final Pattern pattern = Pattern.compile("^(\\s*foo\\s*)*$");
            System.out.println("Compiled pattern");
            final Matcher matcher = pattern.matcher("foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo fo");
            System.out.println("Created matcher");
            final boolean found = matcher.find();
            System.out.println("Finished (found="+found+")");
        }
    }
---------- END SOURCE ----------