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

Chilkat2 Perl

use strict;
use warnings;
use Chilkat2;

my $sbSubject = Chilkat2::StringBuilder->new;

# Create data that would cause a catastrophic backtrack with the regular expression "((a+)+$)"
my $i = 0;
while ($i < 500) {
    $sbSubject->Append('aaaaaaaaaaaaaaaaaaaa');
    $i = $i + 1;
}

$sbSubject->Append('X');

my $pattern = '((a+)+$)';

my $json = Chilkat2::JsonObject->new;
$json->EmitCompact(0);

# Set a time limit to prevent a catastrophic backtrack..
# (Approx) 1 second time limit.
# This should fail:
my $numMatches = $sbSubject->RegexMatch($pattern, $json, 1000);
if ($numMatches < 1) {
    print $sbSubject->LastErrorText, "\n";

    #     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

    exit;
}

# We shouldn't get here.
# The above data and regular expression should've caused a catastrophic backtrack.
print 'numMatches: ', $numMatches, "\n";
print $json->Emit(), "\n";