VBScript

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.

VBScript

Dim fso, outFile
Set fso = CreateObject("Scripting.FileSystemObject")
'Create a Unicode (utf-16) output text file.
Set outFile = fso.CreateTextFile("output.txt", True, True)

set sbSubject = CreateObject("Chilkat.StringBuilder")

' Create data that would cause a catastrophic backtrack with the regular expression "((a+)+$)"
i = 0
Do While i < 500
    success = sbSubject.Append("aaaaaaaaaaaaaaaaaaaa")
    i = i + 1
Loop
success = sbSubject.Append("X")

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

set json = CreateObject("Chilkat.JsonObject")
json.EmitCompact = 0

' 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) Then
    outFile.WriteLine(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

    WScript.Quit
End If

' We shouldn't get here.
' The above data and regular expression should've caused a catastrophic backtrack.
outFile.WriteLine("numMatches: " & numMatches)
outFile.WriteLine(json.Emit())

outFile.Close