CVE-2022-31099: Uncontrolled Recursion (CWE-674)
value: rulex is a new, portable, regular expression language. When parsing untrusted rulex expressions, the stack may overflow, possibly enabling a Denial of Service attack. This happens when parsing an expression with several hundred levels of nesting, causing the process to abort immediately. This is a security concern for you, if your service parses untrusted rulex expressions (expressions provided by an untrusted user), and your service becomes unavailable when the process running rulex aborts due to a stack overflow. The crash is fixed in version **0.4.3**. Affected users are advised to update to this version. There are no known workarounds for this issue.
CWE description: The product does not properly control the amount of recursion that takes place,  consuming excessive resources, such as allocated memory or the program stack.
CVSS v3 base score: 6.5
Published: 2022-06-27T23:15Z
Repository: https://github.com/rulex-rs/rulex
Language: Rust
Files changed: rulex-lib/src/error/parse_error.rs, rulex-lib/src/lib.rs, rulex-lib/src/parse/input.rs, rulex-lib/src/parse/parsers.rs
Commit date: 2022-06-19 00:16:30 +0200
Commit message: Add recursion limit

Diff: diff --git a/rulex-lib/src/error/parse_error.rs b/rulex-lib/src/error/parse_error.rs
index ac4ad8a..c41562c 100644
--- a/rulex-lib/src/error/parse_error.rs
+++ b/rulex-lib/src/error/parse_error.rs
@@ -93,10 +93,13 @@ pub(crate) enum ParseErrorKind {
     #[error(transparent)]
     Repetition(RepetitionError),
     #[error(transparent)]
     Unsupported(UnsupportedError),
 
+    #[error("Recursion limit reached. Try a less nested expression")]
+    RecursionLimit,
+
     #[error("Unknown error: {:?}", .0)]
     Nom(nom::error::ErrorKind),
     #[error("Incomplete parse")]
     Incomplete,
 }
diff --git a/rulex-lib/src/lib.rs b/rulex-lib/src/lib.rs
index ca56570..c944da8 100644
--- a/rulex-lib/src/lib.rs
+++ b/rulex-lib/src/lib.rs
@@ -82,11 +82,11 @@ impl<'i> Rulex<'i> {
     /// Parse a `Rulex` without generating code.
     ///
     /// The parsed `Rulex` can be displayed with `Debug` if the `dbg` feature is
     /// enabled.
     pub fn parse(input: &'i str, options: ParseOptions) -> Result<Self, ParseError> {
-        let rule = parse::parse(input)?;
+        let rule = parse::parse(input, 256)?;
         rule.validate(&options)?;
         Ok(Rulex(rule))
     }
 
     /// Compile a `Rulex` that has been parsed, to a regex
diff --git a/rulex-lib/src/parse/input.rs b/rulex-lib/src/parse/input.rs
index acf8a76..7842341 100644
--- a/rulex-lib/src/parse/input.rs
+++ b/rulex-lib/src/parse/input.rs
@@ -11,14 +11,19 @@ use super::token::Token;
 
 #[derive(Clone)]
 pub(crate) struct Input<'i, 'b> {
     source: &'i str,
     tokens: &'b [(Token, Span)],
+    recursion: u16,
 }
 
 impl<'i, 'b> Input<'i, 'b> {
-    pub(super) fn from(source: &'i str, tokens: &'b [(Token, Span)]) -> Result<Self, ParseError> {
+    pub(super) fn from(
+        source: &'i str,
+        tokens: &'b [(Token, Span)],
+        recursion: u16,
+    ) -> Result<Self, ParseError> {
         let error = tokens.iter().find_map(|&(t, span)| match t {
             Token::Error => Some((span, None)),
             Token::ErrorMsg(m) => Some((span, Some(m))),
             _ => None,
         });
@@ -27,11 +32,23 @@ impl<'i, 'b> Input<'i, 'b> {
                 Some(msg) => Err(ParseErrorKind::LexErrorWithMessage(msg).at(span)),
                 None => Err(ParseErrorKind::UnknownToken.at(span)),
             };
         }
 
-        Ok(Input { source, tokens })
+        Ok(Input { source, tokens, recursion })
+    }
+
+    pub(super) fn recursion_start(&mut self) -> Result<(), ParseError> {
+        self.recursion = self
+            .recursion
+            .checked_sub(1)
+            .ok_or_else(|| ParseErrorKind::RecursionLimit.at(self.span()))?;
+        Ok(())
+    }
+
+    pub(super) fn recursion_end(&mut self) {
+        self.recursion += 1;
     }
 
     pub(super) fn is_empty(&self) -> bool {
         self.tokens.is_empty()
     }
@@ -99,11 +116,11 @@ impl<'i, 'b> InputIter for Input<'i, 'b> {
     fn iter_indices(&self) -> Self::Iter {
         self.iter_elements().enumerate()
     }
 
     fn iter_elements(&self) -> Self::IterElem {
-        Input { source: self.source, tokens: self.tokens }
+        Input { ..*self }
     }
 
     fn position<P>(&self, predicate: P) -> Option<usize>
     where
         P: Fn(Self::Item) -> bool,
@@ -129,14 +146,14 @@ impl<'i, 'b> InputLength for Input<'i, 'b> {
 
 impl<'i, 'b> InputTake for Input<'i, 'b> {
     fn take(&self, count: usize) -> Self {
         let tokens = &self.tokens[..count];
 
-        Input { source: self.source, tokens }
+        Input { tokens, ..*self }
     }
 
     fn take_split(&self, count: usize) -> (Self, Self) {
         let (left, right) = self.tokens.split_at(count);
 
-        (Input { source: self.source, tokens: left }, Input { source: self.source, tokens: right })
+        (Input { tokens: left, ..*self }, Input { tokens: right, ..*self })
     }
 }
diff --git a/rulex-lib/src/parse/parsers.rs b/rulex-lib/src/parse/parsers.rs
index 116012c..0a7b0af 100644
--- a/rulex-lib/src/parse/parsers.rs
+++ b/rulex-lib/src/parse/parsers.rs
@@ -33,22 +33,38 @@ use crate::{
 
 use super::{Input, Token};
 
 pub(super) type PResult<'i, 'b, T> = IResult<Input<'i, 'b>, T, ParseError>;
 
-pub(crate) fn parse(source: &str) -> Result<Rule<'_>, ParseError> {
+pub(crate) fn parse(source: &str, recursion: u16) -> Result<Rule<'_>, ParseError> {
     let tokens = super::tokenize::tokenize(source);
-    let input = Input::from(source, &tokens)?;
+    let input = Input::from(source, &tokens, recursion)?;
 
     let (rest, rules) = parse_modified(input)?;
     if rest.is_empty() {
         Ok(rules)
     } else {
         Err(ParseErrorKind::LeftoverTokens.at(rest.span()))
     }
 }
 
+fn recurse<'i, 'b, O>(
+    mut parser: impl Parser<Input<'i, 'b>, O, ParseError>,
+) -> impl FnMut(Input<'i, 'b>) -> PResult<'i, 'b, O> {
+    move |mut input| {
+        input.recursion_start().map_err(nom::Err::Failure)?;
+
+        match parser.parse(input) {
+            Ok((mut input, output)) => {
+                input.recursion_end();
+                Ok((input, output))
+            }
+            Err(e) => Err(e),
+        }
+    }
+}
+
 pub(super) fn parse_modified<'i, 'b>(input: Input<'i, 'b>) -> PResult<'i, 'b, Rule<'i>> {
     enum ModifierKind {
         Enable,
         Disable,
     }
@@ -76,19 +92,19 @@ pub(super) fn parse_modified<'i, 'b>(input: Input<'i, 'b>) -> PResult<'i, 'b, Ru
                 map(
                     tuple((
                         "let",
                         cut(Token::Identifier),
                         cut(Token::Equals),
-                        cut(parse_or),
+                        cut(recurse(parse_or)),
                         cut(Token::Semicolon),
                     )),
                     |((_, span_start), (name, name_span), _, rule, (_, span_end))| {
                         (Stmt::Let(Let::new(name, rule, name_span)), span_start.join(span_end))
                     },
                 ),
             ))),
-            parse_or,
+            recurse(parse_or),
         ),
         |(stmts, mut rule): (Vec<(Stmt, Span)>, _)| {
             if stmts.len() > 1 {
                 let mut set = HashSet::new();
                 for (stmt, _) in &stmts {
@@ -135,22 +151,22 @@ pub(super) fn parse_sequence<'i, 'b>(input: Input<'i, 'b>) -> PResult<'i, 'b, Ru
 }
 
 pub(super) fn parse_fixes<'i, 'b>(input: Input<'i, 'b>) -> PResult<'i, 'b, Rule<'i>> {
     alt((
         try_map(
-            pair(Token::Not, opt(parse_fixes)),
+            pair(Token::Not, opt(recurse(parse_fixes))),
             |(_, rule)| {
                 if let Some(mut rule) = rule {
                     rule.negate()?;
                     Ok(rule)
                 } else {
                     Err(ParseErrorKind::Expected("expression"))
                 }
             },
             nom::Err::Failure,
         ),
-        map(pair(parse_lookaround, parse_modified), |((kind, span), rule)| {
+        map(pair(parse_lookaround, recurse(parse_modified)), |((kind, span), rule)| {
             let span = span.join(rule.span());
             Rule::Lookaround(Box::new(Lookaround::new(rule, kind, span)))
         }),
         try_map2(
             pair(parse_atom, many0(parse_repetition)),
@@ -280,11 +296,14 @@ pub(super) fn parse_group<'i, 'b>(input: Input<'i, 'b>) -> PResult<'i, 'b, Rule<
             (Capture::new(name.map(|(s, _)| s)), span1)
         })(input)
     }
 
     map(
-        pair(opt(parse_capture), tuple((Token::OpenParen, parse_modified, cut(Token::CloseParen)))),
+        pair(
+            opt(parse_capture),
+            tuple((Token::OpenParen, recurse(parse_modified), cut(Token::CloseParen))),
+        ),
         |(capture, (_, rule, (_, close_paren)))| match (capture, rule) {
             (None, rule) => rule,
             (Some((capture, c_span)), Rule::Group(mut g)) if !g.is_capturing() => {
                 g.set_capture(capture);
                 g.span = c_span.join(g.span);

Vulnerable code:         let rule = parse::parse(input)?;
    pub(super) fn from(source: &'i str, tokens: &'b [(Token, Span)]) -> Result<Self, ParseError> {
        Ok(Input { source, tokens })
        Input { source: self.source, tokens: self.tokens }
        Input { source: self.source, tokens }
        (Input { source: self.source, tokens: left }, Input { source: self.source, tokens: right })
pub(crate) fn parse(source: &str) -> Result<Rule<'_>, ParseError> {
    let input = Input::from(source, &tokens)?;
                        cut(parse_or),
            parse_or,
            pair(Token::Not, opt(parse_fixes)),
        map(pair(parse_lookaround, parse_modified), |((kind, span), rule)| {
        pair(opt(parse_capture), tuple((Token::OpenParen, parse_modified, cut(Token::CloseParen)))),
Fixed code:     #[error("Recursion limit reached. Try a less nested expression")]
    RecursionLimit,

        let rule = parse::parse(input, 256)?;
    recursion: u16,
    pub(super) fn from(
        source: &'i str,
        tokens: &'b [(Token, Span)],
        recursion: u16,
    ) -> Result<Self, ParseError> {
        Ok(Input { source, tokens, recursion })
    }

    pub(super) fn recursion_start(&mut self) -> Result<(), ParseError> {
        self.recursion = self
            .recursion
            .checked_sub(1)
            .ok_or_else(|| ParseErrorKind::RecursionLimit.at(self.span()))?;
        Ok(())
    }

    pub(super) fn recursion_end(&mut self) {
        self.recursion += 1;
        Input { ..*self }
        Input { tokens, ..*self }
        (Input { tokens: left, ..*self }, Input { tokens: right, ..*self })
pub(crate) fn parse(source: &str, recursion: u16) -> Result<Rule<'_>, ParseError> {
    let input = Input::from(source, &tokens, recursion)?;
fn recurse<'i, 'b, O>(
    mut parser: impl Parser<Input<'i, 'b>, O, ParseError>,
) -> impl FnMut(Input<'i, 'b>) -> PResult<'i, 'b, O> {
    move |mut input| {
        input.recursion_start().map_err(nom::Err::Failure)?;

        match parser.parse(input) {
            Ok((mut input, output)) => {
                input.recursion_end();
                Ok((input, output))
            }
            Err(e) => Err(e),
        }
    }
}

                        cut(recurse(parse_or)),
            recurse(parse_or),
            pair(Token::Not, opt(recurse(parse_fixes))),
        map(pair(parse_lookaround, recurse(parse_modified)), |((kind, span), rule)| {
        pair(
            opt(parse_capture),
            tuple((Token::OpenParen, recurse(parse_modified), cut(Token::CloseParen))),
        ),