(PureBasic) Regular Expression Catastrophic Backtrack

See more Regular Expressions Examples

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.

Note: This example requires Chilkat v11.1.0 or greater.

Chilkat PureBasic Module Download Chilkat PureBasic Module

IncludeFile "CkStringBuilder.pb"
IncludeFile "CkJsonObject.pb"

Procedure ChilkatExample()

    sbSubject.i = CkStringBuilder::ckCreate()
    If sbSubject.i = 0
        Debug "Failed to create object."
        ProcedureReturn
    EndIf

    ; Create data that would cause a catastrophic backtrack with the regular expression "((a+)+$)"
    i.i = 0
    While i < 500
        CkStringBuilder::ckAppend(sbSubject,"aaaaaaaaaaaaaaaaaaaa")
        i = i + 1
    Wend
    CkStringBuilder::ckAppend(sbSubject,"X")

    pattern.s = "((a+)+$)"

    json.i = CkJsonObject::ckCreate()
    If json.i = 0
        Debug "Failed to create object."
        ProcedureReturn
    EndIf

    CkJsonObject::setCkEmitCompact(json, 0)

    ; Set a time limit to prevent a catastrophic backtrack..
    ; (Approx) 1 second time limit.
    ; This should fail:
    numMatches.i = CkStringBuilder::ckRegexMatch(sbSubject,pattern,json,1000)
    If numMatches < 1
        Debug CkStringBuilder::ckLastErrorText(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

        CkStringBuilder::ckDispose(sbSubject)
        CkJsonObject::ckDispose(json)
        ProcedureReturn
    EndIf

    ; We shouldn't get here.
    ; The above data and regular expression should've caused a catastrophic backtrack.
    Debug "numMatches: " + Str(numMatches)
    Debug CkJsonObject::ckEmit(json)


    CkStringBuilder::ckDispose(sbSubject)
    CkJsonObject::ckDispose(json)


    ProcedureReturn
EndProcedure