Java Requires Chilkat v11.1.0+

Regular Expression Catastrophic Backtrack

See more Regular Expressions Examples

This example demonstrates how adding a processing time limit prevents a catastrophic backtrack.

Catastrophic backtracking in regular expressions occurs when a poorly constructed pattern causes the regex engine to try an exponential number of possibilities, especially on non-matching input. This leads to extremely slow performance or even a program hang.

Example:

(a+)+$

Applied to:

aaaaaaaaaaaaaaaaaaaaaab

The regex engine tries many combinations of grouping a+ inside another +, looking for a way to match the whole string, but it never matches due to the final b. The nested quantifiers (+ inside +) are what trigger the backtracking explosion.

How to prevent it:

• Avoid nested quantifiers like (a+)+
• Use atomic groups or possessive quantifiers if available
• Consider more efficient regex design or a parser

Catastrophic backtracking is especially dangerous when regex patterns are applied to user-controlled input.

Chilkat2 Java

import com.chilkatsoft.chilkat2.JsonObject;
import com.chilkatsoft.chilkat2.StringBuilder;

public class ChilkatExample {

    public static void main(String[] args) {
        StringBuilder sbSubject = new StringBuilder();

        // Create data that would cause a catastrophic backtrack with the regular expression "((a+)+$)"
        int i = 0;
        while (i < 500) {
            sbSubject.append("aaaaaaaaaaaaaaaaaaaa");
            i = i + 1;
        }

        sbSubject.append("X");

        String pattern = "((a+)+$)";

        JsonObject json = new JsonObject();
        json.setEmitCompact(false);

        // Set a time limit to prevent a catastrophic backtrack..
        // (Approx) 1 second time limit.
        // This should fail:
        int numMatches = sbSubject.regexMatch(pattern, json, 1000);
        if (numMatches < 1) {
            System.out.println(sbSubject.getLastErrorText());

            //     We should get an error such as the following:

            //     ChilkatLog:
            //       RegexMatch:
            //         ChilkatVersion: 11.1.0
            //         regex_match:
            //           timeoutMs: 1000
            //           Exceeded regular expression match limit.
            //           elapsedMs: Elapsed time: 797 millisec
            //           num_matches: -1
            //         --regex_match
            //       --RegexMatch
            //     --ChilkatLog

            return;
        }

        // We shouldn't get here.
        // The above data and regular expression should've caused a catastrophic backtrack.
        System.out.println("numMatches: " + numMatches);
        System.out.println(json.emit());
    }
}