Lua Requires Chilkat v11.1.0+

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.

Lua

local chilkat = require("chilkat")

local sbSubject = chilkat.StringBuilder.new()

-- Create data that would cause a catastrophic backtrack with the regular expression "((a+)+$)"
local i = 0
while i < 500 do
    sbSubject:append("aaaaaaaaaaaaaaaaaaaa")
    i = i + 1
end

sbSubject:append("X")

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

local json = chilkat.JsonObject.new()
json.emit_compact = false

-- Set a time limit to prevent a catastrophic backtrack..
-- (Approx) 1 second time limit.
-- This should fail:
local numMatches = sbSubject:regex_match(pattern, json, 1000)
if numMatches < 1 then
    print(sbSubject.last_error_text)

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

    return
end

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