(SQL Server) 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 ActiveX Downloads ActiveX for 32-bit and 64-bit Windows

-- Important: See this note about string length limitations for strings returned by sp_OAMethod calls.
--
CREATE PROCEDURE ChilkatSample
AS
BEGIN
    DECLARE @hr int
    -- Important: Do not use nvarchar(max).  See the warning about using nvarchar(max).
    DECLARE @sTmp0 nvarchar(4000)
    DECLARE @sbSubject int
    EXEC @hr = sp_OACreate 'Chilkat.StringBuilder', @sbSubject OUT
    IF @hr <> 0
    BEGIN
        PRINT 'Failed to create ActiveX component'
        RETURN
    END

    -- Create data that would cause a catastrophic backtrack with the regular expression "((a+)+$)"
    DECLARE @i int
    SELECT @i = 0
    WHILE @i < 500
      BEGIN
        DECLARE @success int
        EXEC sp_OAMethod @sbSubject, 'Append', @success OUT, 'aaaaaaaaaaaaaaaaaaaa'
        SELECT @i = @i + 1
      END
    EXEC sp_OAMethod @sbSubject, 'Append', @success OUT, 'X'

    DECLARE @pattern nvarchar(4000)
    SELECT @pattern = '((a+)+$)'

    DECLARE @json int
    EXEC @hr = sp_OACreate 'Chilkat.JsonObject', @json OUT

    EXEC sp_OASetProperty @json, 'EmitCompact', 0

    -- Set a time limit to prevent a catastrophic backtrack..
    -- (Approx) 1 second time limit.
    -- This should fail:
    DECLARE @numMatches int
    EXEC sp_OAMethod @sbSubject, 'RegexMatch', @numMatches OUT, @pattern, @json, 1000
    IF @numMatches < 1
      BEGIN
        EXEC sp_OAGetProperty @sbSubject, 'LastErrorText', @sTmp0 OUT
        PRINT @sTmp0

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

        EXEC @hr = sp_OADestroy @sbSubject
        EXEC @hr = sp_OADestroy @json
        RETURN
      END

    -- We shouldn't get here.
    -- The above data and regular expression should've caused a catastrophic backtrack.

    PRINT 'numMatches: ' + @numMatches
    EXEC sp_OAMethod @json, 'Emit', @sTmp0 OUT
    PRINT @sTmp0

    EXEC @hr = sp_OADestroy @sbSubject
    EXEC @hr = sp_OADestroy @json


END
GO