PowerBuilder

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.

PowerBuilder

integer li_rc
oleobject loo_SbSubject
integer i
string ls_Pattern
oleobject loo_Json
integer li_NumMatches

loo_SbSubject = create oleobject
li_rc = loo_SbSubject.ConnectToNewObject("Chilkat.StringBuilder")
if li_rc < 0 then
    destroy loo_SbSubject
    MessageBox("Error","Connecting to COM object failed")
    return
end if

// Create data that would cause a catastrophic backtrack with the regular expression "((a+)+$)"
i = 0
do while i < 500
    loo_SbSubject.Append("aaaaaaaaaaaaaaaaaaaa")
    i = i + 1
loop
loo_SbSubject.Append("X")

ls_Pattern = "((a+)+$)"

loo_Json = create oleobject
li_rc = loo_Json.ConnectToNewObject("Chilkat.JsonObject")

loo_Json.EmitCompact = 0

// Set a time limit to prevent a catastrophic backtrack..
// (Approx) 1 second time limit.
// This should fail:
li_NumMatches = loo_SbSubject.RegexMatch(ls_Pattern,loo_Json,1000)
if li_NumMatches < 1 then
    Write-Debug loo_SbSubject.LastErrorText

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

    destroy loo_SbSubject
    destroy loo_Json
    return
end if

// We shouldn't get here.
// The above data and regular expression should've caused a catastrophic backtrack.
Write-Debug "numMatches: " + string(li_NumMatches)
Write-Debug loo_Json.Emit()


destroy loo_SbSubject
destroy loo_Json