Java Regex Pattern match takes too much time

Question

The java regex pattern match function takes too much time to complete when the pattern and words are something like

pattern = ".*.*.*.*.*.*.*.*.*.*1";
word = aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

It takes more than 10 seconds to match the above pattern against the word. It's true that this pattern is meaningless, but in my case the pattern is taken as user input from GUI form.

I have used the following code.

        boolean matches = false;
        long startTime = System.nanoTime();
        try {
            matches = Pattern.compile(pattern).matcher(word.toLowerCase()).matches();
        } catch (Exception e) {
            e.printStackTrace();
        }
        long elapseTime = System.nanoTime() - startTime;
        elapseTime = elapseTime / 1000000000;
        System.out.println("Time taken for regex match " + elapseTime + " out put " + matches);

Answer 1

This is a more or less well known security issue with regular expressions: You can trivially Denial-of-Service any server where you can enter regexes. You can craft a regular expression that takes effectively infinite time to run against any input. Your example is pretty bad; you can get even worse.

This is INHERENT, by the way. This regex matches if your input's total length is a prime number, and fails otherwise: .?|(..+?)\\1+.

1. Finding prime numbers is hard.
2. The above is a valid regexp.
3. Therefore, regexes are potentially slow and cannot be made any faster. QED.

Thus, what you want, is impossible, unless we think out of the box. There are two solutions:

A. don't match regexes, match something else. What if we match almost-regexes: Regexes with a few exotic features removed. This gets you to something called a Thompson NFA regular expression matcher which has some slight limitations (primarily, no backreferences, no grouping extraction, not without extra effort - without backreferences, that prime number finder thing above cannot work). Perhaps you can find an implementation of this regexp variant for java. At that point, you can simply count the size of the input plus the size of the regexp and draw conclusions about how long it would take said regexp to execute.

B. You'd have to guard any regexp search with a timer thread and abort it, or, prevent the user from entering regexes. Run the regex job in a separate thread just for this purpose which has been niced (priority level set low), and is guarded by a timer thread that interrupts() it, though you'd have to test if the matcher code actually stops in its tracks if you interrupt it (I bet it won't, at which point you can't stop a runaway regex at all, and you'd have to find something not-java, or find a regexp library someplace and put if (Thread.interrupted()) throw new InterruptedException(); someplace inside one of its loops.

C. Offer something that isn't regex to the user. Maybe to implement it, you convert the user's input to a regex and then run that normally, but as part of your conversion you double check certain conditions to ensure the regexp will not be slow.

NB: Your example regexp is thompson-NFA compatible; a thompson-NFA style regexer would do it quickly. However, java's regexes isn't a t-NFA.