DataFlex 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.

DataFlex

Use ChilkatAx-win32.pkg

Procedure Test
    Handle hoSbSubject
    Integer i
    Boolean iSuccess
    String sPattern
    Variant vJson
    Handle hoJson
    Integer iNumMatches
    String sTemp1

    Get Create (RefClass(cComChilkatStringBuilder)) To hoSbSubject
    If (Not(IsComObjectCreated(hoSbSubject))) Begin
        Send CreateComObject of hoSbSubject
    End

    //  Create data that would cause a catastrophic backtrack with the regular expression "((a+)+$)"
    Move 0 To i
    While (i < 500)
        Get ComAppend Of hoSbSubject "aaaaaaaaaaaaaaaaaaaa" To iSuccess
        Move (i + 1) To i
    Loop

    Get ComAppend Of hoSbSubject "X" To iSuccess

    Move "((a+)+$)" To sPattern

    Get Create (RefClass(cComChilkatJsonObject)) To hoJson
    If (Not(IsComObjectCreated(hoJson))) Begin
        Send CreateComObject of hoJson
    End
    Set ComEmitCompact Of hoJson To False

    //  Set a time limit to prevent a catastrophic backtrack..
    //  (Approx) 1 second time limit.
    //  This should fail:
    Get pvComObject of hoJson to vJson
    Get ComRegexMatch Of hoSbSubject sPattern vJson 1000 To iNumMatches
    If (iNumMatches < 1) Begin
        Get ComLastErrorText Of hoSbSubject To sTemp1
        Showln sTemp1

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

        Procedure_Return
    End

    //  We shouldn't get here.
    //  The above data and regular expression should've caused a catastrophic backtrack.
    Showln "numMatches: " iNumMatches
    Get ComEmit Of hoJson To sTemp1
    Showln sTemp1


End_Procedure