Tcl

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.

Tcl

load ./chilkat.dll

set sbSubject [new_CkStringBuilder]

# Create data that would cause a catastrophic backtrack with the regular expression "((a+)+$)"
set i 0
while {$i < 500} {
    CkStringBuilder_Append $sbSubject "aaaaaaaaaaaaaaaaaaaa"
    set i [expr $i + 1]
}
CkStringBuilder_Append $sbSubject "X"

set pattern "((a+)+$)"

set json [new_CkJsonObject]

CkJsonObject_put_EmitCompact $json 0

# Set a time limit to prevent a catastrophic backtrack..
# (Approx) 1 second time limit.
# This should fail:
set numMatches [CkStringBuilder_RegexMatch $sbSubject $pattern $json 1000]
if {$numMatches < 1} then {
    puts [CkStringBuilder_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

    delete_CkStringBuilder $sbSubject
    delete_CkJsonObject $json
    exit
}

# We shouldn't get here.
# The above data and regular expression should've caused a catastrophic backtrack.
puts "numMatches: $numMatches"
puts [CkJsonObject_emit $json]

delete_CkStringBuilder $sbSubject
delete_CkJsonObject $json