Unicode C

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.

Unicode C

#include <C_CkStringBuilderW.h>
#include <C_CkJsonObjectW.h>

void ChilkatSample(void)
    {
    HCkStringBuilderW sbSubject;
    int i;
    const wchar_t *pattern;
    HCkJsonObjectW json;
    int numMatches;

    sbSubject = CkStringBuilderW_Create();

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

    CkStringBuilderW_Append(sbSubject,L"X");

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

    json = CkJsonObjectW_Create();
    CkJsonObjectW_putEmitCompact(json,FALSE);

    // Set a time limit to prevent a catastrophic backtrack..
    // (Approx) 1 second time limit.
    // This should fail:
    numMatches = CkStringBuilderW_RegexMatch(sbSubject,pattern,json,1000);
    if (numMatches < 1) {
        wprintf(L"%s\n",CkStringBuilderW_lastErrorText(sbSubject));

        // 	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

        CkStringBuilderW_Dispose(sbSubject);
        CkJsonObjectW_Dispose(json);
        return;
    }

    // We shouldn't get here.
    // The above data and regular expression should've caused a catastrophic backtrack.
    wprintf(L"numMatches: %d\n",numMatches);
    wprintf(L"%s\n",CkJsonObjectW_emit(json));


    CkStringBuilderW_Dispose(sbSubject);
    CkJsonObjectW_Dispose(json);

    }