Repository: fancy-regex/fancy-regex (language: rust)

Issue:
Add support for backtracking limit
(Moved from previous location: https://github.com/google/fancy-regex/issues/44)

Given that it's possible to run into catastrophic backtracking, I think it would be nice if fancy-regex provided a way to set a limit on backtracking. If the VM reached that limit, it would return an error. Currently, the only way to stop it is to have a separate process and then kill the process.

There's some questions on how that would work:

* Would it be a timeout (e.g. 1 second) or a number that would be incremented and checked when executing instructions
* Would it be controllable via a cargo feature or part of the API when creating a regex (probably introduce a builder). (I'm not sure the feature would work, because that would mean in a crate with multiple dependencies that used fancy-regex, the feature would change the behavior for all those dependent crates.)

@raphlinus's thoughts on this:

> This is a good idea.
>
> I strongly prefer a deterministic approach rather than time. Among other things, running the cloud can introduce random and long delays, which would make tests flaky.
>
> Adding an option at regex creation time sounds good. Note that the API is already designed to fail when MAX_STACK is exceeded, with vm::State::run already returning a Result. So I think it can also be on by default, and won't be too disruptive.
>
> Thanks for agreeing to work on it, and let me know if you want more input.
Interested to hear your thoughts on this @raphlinus, and happy to work on it!


Discussion / hints:

Fix patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index e4d5922..0355b31 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -6,6 +6,13 @@ The format is based on [Keep a Changelog](http://keepachangelog.com/en/1.0.0/).
 This project adheres to [Semantic Versioning](http://semver.org/spec/v2.0.0.html),
 with the exception that 0.x versions can break between minor versions.
 
+## [unreleased] - 2019-10-19
+### Added
+- Add limit for backtracking so that execution errors instead of running
+  for a long time in case of catastrophic backtracking.
+- Add `RegexBuilder` with `backtrack_limit` to configure the new
+  backtrack limit per regex.
+
 ## [0.2.0] - 2019-10-19
 ### Added
 - More documentation and examples
@@ -40,5 +47,6 @@ with the exception that 0.x versions can break between minor versions.
 ### Added
 - Initial release
 
+[unreleased]: https://github.com/fancy-regex/fancy-regex/compare/0.2.0...master
 [0.2.0]: https://github.com/fancy-regex/fancy-regex/compare/0.1.0...0.2.0
 [0.1.0]: https://github.com/fancy-regex/fancy-regex/commits/0.1.0
diff --git a/benches/bench.rs b/benches/bench.rs
index 1000fcf..8e0e455 100644
--- a/benches/bench.rs
+++ b/benches/bench.rs
@@ -23,7 +23,7 @@ extern crate criterion;
 
 use criterion::Criterion;
 
-use fancy_regex::internal::{analyze, compile, run};
+use fancy_regex::internal::{analyze, compile, run_default};
 use fancy_regex::Expr;
 use regex::Regex;
 
@@ -64,7 +64,7 @@ fn run_backtrack(c: &mut Criterion) {
     let a = analyze(&e, &br).unwrap();
     let p = compile(&a).unwrap();
     c.bench_function("run_backtrack", |b| {
-        b.iter(|| run(&p, "babab", 0, 0).unwrap())
+        b.iter(|| run_default(&p, "babab", 0).unwrap())
     });
 }
 
@@ -79,7 +79,17 @@ fn run_tricky(c: &mut Criterion) {
         s.push_str("ab");
     }
     s.push_str("ac");
-    c.bench_function("run_tricky", |b| b.iter(|| run(&p, &s, 0, 0).unwrap()));
+    c.bench_function("run_tricky", |b| b.iter(|| run_default(&p, &s, 0).unwrap()));
+}
+
+fn run_backtrack_limit(c: &mut Criterion) {
+    let (e, br) = Expr::parse("(?i)(a|b|ab)*(?=c)").unwrap();
+    let a = analyze(&e, &br).unwrap();
+    let p = compile(&a).unwrap();
+    let s = "abababababababababababababababababababababababababababab";
+    c.bench_function("run_backtrack_limit", |b| {
+        b.iter(|| run_default(&p, &s, 0).unwrap_err())
+    });
 }
 
 criterion_group!(
@@ -90,6 +100,7 @@ criterion_group!(
     parse_misc,
     analyze_literal_re,
     run_backtrack,
-    run_tricky
+    run_tricky,
+    run_backtrack_limit,
 );
 criterion_main!(benches);
diff --git a/examples/toy.rs b/examples/toy.rs
index 45ac368..77cce5e 100644
--- a/examples/toy.rs
+++ b/examples/toy.rs
@@ -20,7 +20,7 @@
 
 //! A simple test app for exercising and debugging the regex engine.
 
-use fancy_regex::internal::{analyze, compile, trace, Insn, Prog};
+use fancy_regex::internal::{analyze, compile, run_trace, Insn, Prog};
 use fancy_regex::*;
 use std::env;
 use std::str::FromStr;
@@ -73,7 +73,7 @@ fn main() {
             if let Some(re) = args.next() {
                 let prog = prog(&re);
                 if let Some(s) = args.next() {
-                    trace(&prog, &s, 0).unwrap();
+                    run_trace(&prog, &s, 0).unwrap();
                 }
             }
         } else if cmd == "trace-inner" {
@@ -82,7 +82,7 @@ fn main() {
                 let a = analyze(&e, &backrefs).unwrap();
                 let p = compile(&a).unwrap();
                 if let Some(s) = args.next() {
-                    trace(&p, &s, 0).unwrap();
+                    run_trace(&p, &s, 0).unwrap();
                 }
             }
         } else if cmd == "graph" {
diff --git a/src/lib.rs b/src/lib.rs
index 67d2e50..d1a3de7 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -126,7 +126,6 @@ assert!(!re.is_match("abc").unwrap());
 */
 
 #![doc(html_root_url = "https://docs.rs/fancy-regex/0.2.0")]
-
 #![deny(missing_docs)]
 #![deny(missing_debug_implementations)]
 
@@ -187,8 +186,12 @@ pub enum Error {
     InnerError(regex::Error),
 
     // Run time errors
-    /// Max stack size exceeded for backtracking while executing regex
+    /// Max stack size exceeded for backtracking while executing regex.
     StackOverflow,
+    /// Max limit for backtracking count exceeded while executing the regex.
+    /// Configure using
+    /// [`RegexBuilder::backtrack_limit`](struct.RegexBuilder.html#method.backtrack_limit).
+    BacktrackLimitExceeded,
 
     /// This enum may grow additional variants, so this makes sure clients don't count on exhaustive
     /// matching. Otherwise, adding a new variant could break existing code.
@@ -196,6 +199,10 @@ pub enum Error {
     __Nonexhaustive,
 }
 
+/// A builder for a `Regex` to allow configuring options.
+#[derive(Debug)]
+pub struct RegexBuilder(RegexOptions);
+
 /// A compiled regular expression.
 pub struct Regex(RegexImpl);
 
@@ -205,12 +212,12 @@ enum RegexImpl {
     Wrap {
         inner: regex::Regex,
         inner1: Option<Box<regex::Regex>>,
-        original: String,
+        options: RegexOptions,
     },
     Fancy {
         prog: Prog,
         n_groups: usize,
-        original: String,
+        options: RegexOptions,
     },
 }
 
@@ -250,6 +257,50 @@ pub struct SubCaptureMatches<'c, 't> {
     i: usize,
 }
 
+#[derive(Clone, Debug)]
+struct RegexOptions {
+    pattern: String,
+    backtrack_limit: usize,
+}
+
+impl Default for RegexOptions {
+    fn default() -> Self {
+        RegexOptions {
+            pattern: String::new(),
+            backtrack_limit: 1_000_000,
+        }
+    }
+}
+
+impl RegexBuilder {
+    /// Create a new regex builder with a regex pattern.
+    ///
+    /// If the pattern is invalid, the call to `build` will fail later.
+    pub fn new(pattern: &str) -> Self {
+        let mut builder = RegexBuilder(RegexOptions::default());
+        builder.0.pattern = pattern.to_string();
+        builder
+    }
+
+    /// Build the `Regex`.
+    ///
+    /// Returns an [`Error`](enum.Error.html) if the pattern could not be parsed.
+    pub fn build(&self) -> Result<Regex> {
+        Regex::new_options(self.0.clone())
+    }
+
+    /// Limit for how many times backtracking should be attempted for fancy regexes (where
+    /// backtracking is used). If this limit is exceeded, execution returns an error with
+    /// [`Error::BacktrackLimitExceeded`](enum.Error.html#variant.BacktrackLimitExceeded).
+    /// This is for preventing a regex with catastrophic backtracking to run for too long.
+    ///
+    /// Default is `1_000_000` (1 million).
+    pub fn backtrack_limit(&mut self, limit: usize) -> &mut Self {
+        self.0.backtrack_limit = limit;
+        self
+    }
+}
+
 impl fmt::Debug for Regex {
     /// Shows the original regular expression.
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
@@ -258,9 +309,19 @@ impl fmt::Debug for Regex {
 }
 
 impl Regex {
-    /// Parse and compile a regex.
+    /// Parse and compile a regex with default options, see `RegexBuilder`.
+    ///
+    /// Returns an [`Error`](enum.Error.html) if the pattern could not be parsed.
     pub fn new(re: &str) -> Result<Regex> {
-        let (raw_e, backrefs) = Expr::parse(re)?;
+        let options = RegexOptions {
+            pattern: re.to_string(),
+            ..RegexOptions::default()
+        };
+        Self::new_options(options)
+    }
+
+    fn new_options(options: RegexOptions) -> Result<Regex> {
+        let (raw_e, backrefs) = Expr::parse(&options.pattern)?;
 
         // wrapper to search for re at arbitrary start position,
         // and to capture the match bounds
@@ -303,7 +364,7 @@ impl Regex {
             return Ok(Regex(RegexImpl::Wrap {
                 inner,
                 inner1,
-                original: re.to_string(),
+                options,
             }));
         }
 
@@ -311,15 +372,15 @@ impl Regex {
         Ok(Regex(RegexImpl::Fancy {
             prog,
             n_groups: info.end_group,
-            original: re.to_string(),
+            options,
         }))
     }
 
     /// Returns the original string of this regex.
     pub fn as_str(&self) -> &str {
         match &self.0 {
-            RegexImpl::Wrap { ref original, .. } => original,
-            RegexImpl::Fancy { ref original, .. } => original,
+            RegexImpl::Wrap { options, .. } => &options.pattern,
+            RegexImpl::Fancy { options, .. } => &options.pattern,
         }
     }
 
@@ -338,8 +399,10 @@ impl Regex {
     pub fn is_match(&self, text: &str) -> Result<bool> {
         match &self.0 {
             RegexImpl::Wrap { ref inner, .. } => Ok(inner.is_match(text)),
-            RegexImpl::Fancy { ref prog, .. } => {
-                let result = vm::run(prog, text, 0, 0)?;
+            RegexImpl::Fancy {
+                ref prog, options, ..
+            } => {
+                let result = vm::run(prog, text, 0, 0, options)?;
                 Ok(result.is_some())
             }
         }
@@ -365,8 +428,8 @@ impl Regex {
             RegexImpl::Wrap { inner, .. } => Ok(inner
                 .find(text)
                 .map(|m| Match::new(text, m.start(), m.end()))),
-            RegexImpl::Fancy { prog, .. } => {
-                let result = vm::run(prog, text, 0, 0)?;
+            RegexImpl::Fancy { prog, options, .. } => {
+                let result = vm::run(prog, text, 0, 0, options)?;
                 Ok(result.map(|saves| Match::new(text, saves[0], saves[1])))
             }
         }
@@ -402,8 +465,13 @@ impl Regex {
                     enclosing_groups: 0,
                 })
             })),
-            RegexImpl::Fancy { prog, n_groups, .. } => {
-                let result = vm::run(prog, text, 0, 0)?;
+            RegexImpl::Fancy {
+                prog,
+                n_groups,
+                options,
+                ..
+            } => {
+                let result = vm::run(prog, text, 0, 0, options)?;
                 Ok(result.map(|mut saves| {
                     saves.truncate(n_groups * 2);
                     Captures(CapturesImpl::Fancy { text, saves })
@@ -473,8 +541,13 @@ impl Regex {
                     }))
                 }
             }
-            RegexImpl::Fancy { prog, n_groups, .. } => {
-                let result = vm::run(prog, text, pos, 0)?;
+            RegexImpl::Fancy {
+                prog,
+                n_groups,
+                options,
+                ..
+            } => {
+                let result = vm::run(prog, text, pos, 0, options)?;
                 Ok(result.map(|mut saves| {
                     saves.truncate(n_groups * 2);
                     Captures(CapturesImpl::Fancy { text, saves })
@@ -874,7 +947,7 @@ pub fn detect_possible_backref(re: &str) -> bool {
 pub mod internal {
     pub use crate::analyze::analyze;
     pub use crate::compile::compile;
-    pub use crate::vm::{run, trace, Insn, Prog};
+    pub use crate::vm::{run_default, run_trace, Insn, Prog};
 }
 
 #[cfg(test)]
diff --git a/src/vm.rs b/src/vm.rs
index 05837a5..0d8837c 100644
--- a/src/vm.rs
+++ b/src/vm.rs
@@ -73,10 +73,10 @@ use regex::Regex;
 use std::collections::BTreeSet;
 use std::usize;
 
-use crate::codepoint_len;
 use crate::prev_codepoint_ix;
 use crate::Error;
 use crate::Result;
+use crate::{codepoint_len, RegexOptions};
 
 const OPTION_TRACE: u32 = 1;
 
@@ -391,22 +391,34 @@ fn codepoint_len_at(s: &str, ix: usize) -> usize {
 }
 
 /// Run the program with trace printing for debugging.
-pub fn trace(prog: &Prog, s: &str, pos: usize) -> Result<Option<Vec<usize>>> {
-    run(prog, s, pos, OPTION_TRACE)
+pub fn run_trace(prog: &Prog, s: &str, pos: usize) -> Result<Option<Vec<usize>>> {
+    run(prog, s, pos, OPTION_TRACE, &RegexOptions::default())
 }
 
-/// Run the program.
-pub fn run(prog: &Prog, s: &str, pos: usize, options: u32) -> Result<Option<Vec<usize>>> {
-    let mut state = State::new(prog.n_saves, MAX_STACK, options);
-    if options & OPTION_TRACE != 0 {
+/// Run the program with default options.
+pub fn run_default(prog: &Prog, s: &str, pos: usize) -> Result<Option<Vec<usize>>> {
+    run(prog, s, pos, 0, &RegexOptions::default())
+}
+
+/// Run the program with options.
+pub(crate) fn run(
+    prog: &Prog,
+    s: &str,
+    pos: usize,
+    option_flags: u32,
+    options: &RegexOptions,
+) -> Result<Option<Vec<usize>>> {
+    let mut state = State::new(prog.n_saves, MAX_STACK, option_flags);
+    if option_flags & OPTION_TRACE != 0 {
         println!("pos\tinstruction");
     }
+    let mut backtrack_count = 0;
     let mut pc = 0;
     let mut ix = pos;
     loop {
         // break from this loop to fail, causes stack to pop
         'fail: loop {
-            if options & OPTION_TRACE != 0 {
+            if option_flags & OPTION_TRACE != 0 {
                 println!("{}\t{} {:?}", ix, pc, prog.body[pc]);
             }
             match prog.body[pc] {
@@ -415,7 +427,7 @@ pub fn run(prog: &Prog, s: &str, pos: usize, options: u32) -> Result<Option<Vec<
                     // with an explicit group; we might want to
                     // optimize that.
                     //state.saves[1] = ix;
-                    if options & OPTION_TRACE != 0 {
+                    if option_flags & OPTION_TRACE != 0 {
                         println!("saves: {:?}", state.saves);
                     }
                     return Ok(Some(state.saves));
@@ -619,13 +631,19 @@ pub fn run(prog: &Prog, s: &str, pos: usize, options: u32) -> Result<Option<Vec<
             }
             pc += 1;
         }
-        if options & OPTION_TRACE != 0 {
+        if option_flags & OPTION_TRACE != 0 {
             println!("fail");
         }
         // "break 'fail" goes here
         if state.stack.is_empty() {
             return Ok(None);
         }
+
+        backtrack_count += 1;
+        if backtrack_count > options.backtrack_limit {
+            return Err(Error::BacktrackLimitExceeded);
+        }
+
         let (newpc, newix) = state.pop();
         pc = newpc;
         ix = newix;


Test patch:
diff --git a/tests/matching.rs b/tests/matching.rs
index d9132bd..f8223dd 100644
--- a/tests/matching.rs
+++ b/tests/matching.rs
@@ -1,3 +1,5 @@
+use fancy_regex::{Error, RegexBuilder};
+
 mod common;
 
 #[test]
@@ -88,6 +90,21 @@ fn atomic_group() {
     assert_no_match(r"^a(?>bc(?=d)|b)cd$", "abcd");
 }
 
+#[test]
+fn backtrack_limit() {
+    let re = RegexBuilder::new("(?i)(a|b|ab)*(?=c)")
+        .backtrack_limit(100_000)
+        .build()
+        .unwrap();
+    let s = "abababababababababababababababababababababababababababab";
+    let result = re.is_match(s);
+    assert!(result.is_err());
+    match result.err() {
+        Some(Error::BacktrackLimitExceeded) => {}
+        _ => panic!("Expected Error::BacktrackLimitExceeded"),
+    }
+}
+
 fn assert_match(re: &str, text: &str) {
     let result = match_text(re, text);
     assert_eq!(