(Android™) 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 Android™ Downloads Android™ Java Libraries Android C/C++ Libraries

// Important: Don't forget to include the call to System.loadLibrary
// as shown at the bottom of this code sample.
package com.test;

import android.app.Activity;
import com.chilkatsoft.*;

import android.widget.TextView;
import android.os.Bundle;

public class SimpleActivity extends Activity {

  private static final String TAG = "Chilkat";

  // Called when the activity is first created.
  @Override
  public void onCreate(Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);

    CkStringBuilder sbSubject = new CkStringBuilder();

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

    sbSubject.Append("X");

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

    CkJsonObject json = new CkJsonObject();
    json.put_EmitCompact(false);

    // Set a time limit to prevent a catastrophic backtrack..
    // (Approx) 1 second time limit.
    // This should fail:
    int numMatches = sbSubject.RegexMatch(pattern,json,1000);
    if (numMatches < 1) {
        Log.i(TAG, 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

        return;
        }

    // We shouldn't get here.
    // The above data and regular expression should've caused a catastrophic backtrack.
    Log.i(TAG, "numMatches: " + String.valueOf(numMatches));
    Log.i(TAG, json.emit());

  }

  static {
      System.loadLibrary("chilkat");

      // Note: If the incorrect library name is passed to System.loadLibrary,
      // then you will see the following error message at application startup:
      //"The application <your-application-name> has stopped unexpectedly. Please try again."
  }
}