(CkPython) 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 Python Downloads install with pip pip3 install chilkat or download... Python Module for Windows, MacOS, Linux, Alpine Linux

import sys
import chilkat

sbSubject = chilkat.CkStringBuilder()

# Create data that would cause a catastrophic backtrack with the regular expression "((a+)+$)"
i = 0
while i < 500 :
    sbSubject.Append("aaaaaaaaaaaaaaaaaaaa")
    i = i + 1

sbSubject.Append("X")

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

json = chilkat.CkJsonObject()
json.put_EmitCompact(False)

# Set a time limit to prevent a catastrophic backtrack..
# (Approx) 1 second time limit.
# This should fail:
numMatches = sbSubject.RegexMatch(pattern,json,1000)
if (numMatches < 1):
    print(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

    sys.exit()

# We shouldn't get here.
# The above data and regular expression should've caused a catastrophic backtrack.
print("numMatches: " + str(numMatches))
print(json.emit())