redos_detector/
lib.rs

1//! Static ReDoS analysis for ECMA-262 regular expressions.
2//!
3//! This crate scores how vulnerable a regular expression is to ReDoS
4//! (regular-expression denial of service). It does not run the pattern. It
5//! enumerates the ways an input prefix could match and counts how many distinct
6//! paths can match the same prefix. More ambiguity means more backtracking, so a
7//! higher score. A score of `1` means every input matches at most one way. An
8//! infinite score means backtracking is unbounded.
9//!
10//! Start with [`is_safe`] for a check that reads flags from the pattern string,
11//! or [`is_safe_pattern`] for a raw pattern with explicit options. [`to_friendly`]
12//! renders a result as text. [`downgrade_pattern`] rewrites unsupported patterns
13//! into supported ones.
14//!
15//! Recoverable input problems return [`Error`]: an unsupported flag, a
16//! conflicting config, or a pattern that fails to parse. A successful check
17//! returns a [`Report`]. When the analysis hits a cap the report carries an
18//! [`AnalysisLimit`] in its `error` field, which is a different axis from input
19//! validation.
20//!
21//! ```
22//! use redos_detector::{is_safe, Config};
23//!
24//! let result = is_safe("(a+)+$", "", &Config::default()).unwrap();
25//! assert!(!result.is_safe());
26//! ```
27#![forbid(unsafe_code)]
28#![warn(missing_docs)]
29
30mod arrays;
31mod ast;
32mod character_groups;
33mod character_reader;
34mod checker_reader;
35mod code_point;
36mod collect_results;
37mod downgrade_pattern;
38mod infinite_loop_tracker;
39mod is_unbounded_reader;
40mod map;
41mod node_extra;
42mod our_range;
43mod parse;
44mod quantifier;
45mod reader;
46mod result_cache;
47mod to_friendly;
48mod tree;
49
50use crate::ast::{NodeKind, RcNode};
51use crate::character_reader::level0::StackEntry;
52use crate::checker_reader::{Clock, Trail as CheckerTrail};
53use crate::collect_results::{collect_results, CollectInput};
54use crate::downgrade_pattern::is_missing_start_anchor;
55use std::collections::HashSet;
56use std::time::Duration;
57
58pub use crate::downgrade_pattern::{downgrade_pattern, DowngradedRegexPattern};
59pub use crate::to_friendly::{to_friendly, ToFriendlyConfig};
60
61/// The package version.
62pub const VERSION: &str = env!("CARGO_PKG_VERSION");
63
64/// Default score cap.
65pub const DEFAULT_MAX_SCORE: u64 = 200;
66/// Default step cap.
67pub const DEFAULT_MAX_STEPS: u64 = 20000;
68/// Default multi-line mode.
69pub const DEFAULT_MULTI_LINE: bool = false;
70/// Default unicode mode.
71pub const DEFAULT_UNICODE: bool = false;
72/// Default case-insensitive mode.
73pub const DEFAULT_CASE_INSENSITIVE: bool = false;
74/// Default dot-all mode.
75pub const DEFAULT_DOT_ALL: bool = false;
76
77/// A location in the checked pattern. The first character has offset `0`.
78#[derive(Clone, Copy, Debug, PartialEq, Eq)]
79pub struct NodeLocation {
80    /// The UTF-16 offset.
81    pub offset: usize,
82}
83
84/// A node in the checked pattern.
85#[derive(Clone, Debug, PartialEq, Eq)]
86pub struct Node {
87    /// The end location (exclusive).
88    pub end: NodeLocation,
89    /// The node's source text.
90    pub source: String,
91    /// The start location (inclusive).
92    pub start: NodeLocation,
93}
94
95/// A backreference in a trail side.
96#[derive(Clone, Debug, PartialEq, Eq)]
97pub struct BackReference {
98    /// The 1-based index of the group the backreference points at.
99    pub index: u64,
100    /// The backreference node.
101    pub node: Node,
102}
103
104/// A quantifier iteration in a trail side.
105#[derive(Clone, Debug, PartialEq, Eq)]
106pub struct QuantifierIteration {
107    /// The iteration number. The first iteration is `0`.
108    pub iteration: u64,
109    /// The quantifier node.
110    pub node: Node,
111}
112
113/// One side of a trail entry.
114#[derive(Clone, Debug, PartialEq, Eq)]
115pub struct TrailEntrySide {
116    /// The backreference stack the node is part of, outermost last.
117    pub backreference_stack: Vec<BackReference>,
118    /// The node.
119    pub node: Node,
120    /// The iteration of each quantifier the node is part of.
121    pub quantifier_iterations: Vec<QuantifierIteration>,
122}
123
124/// A trail entry showing two ways through the pattern side by side.
125#[derive(Clone, Debug, PartialEq, Eq)]
126pub struct TrailEntry {
127    /// The `a` side.
128    pub a: TrailEntrySide,
129    /// The `b` side.
130    pub b: TrailEntrySide,
131}
132
133/// A trail: a pair of distinct ways to match the same input.
134#[derive(Clone, Debug, PartialEq, Eq)]
135pub struct Trail {
136    /// The entries of the trail.
137    pub entries: Vec<TrailEntry>,
138}
139
140/// The error reported for an unsafe result.
141///
142/// Match with a wildcard arm. New limits may be added in a future version.
143#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
144#[non_exhaustive]
145pub enum AnalysisLimit {
146    /// The score reached or passed the cap. This covers two cases that both
147    /// report `Score::Infinite`: a finite count that crossed `max_score`, and a
148    /// pattern the checker proved has unbounded backtracking (seen even with
149    /// `max_score: None`).
150    HitMaxScore,
151    /// The step cap was hit.
152    HitMaxSteps,
153    /// The timeout was hit.
154    TimedOut,
155}
156
157/// An internal checker error.
158#[derive(Clone, Copy, Debug, PartialEq, Eq)]
159pub(crate) enum CheckError {
160    /// The step cap was hit.
161    HitMaxSteps,
162    /// The timeout was hit.
163    TimedOut,
164}
165
166/// A score. `Finite` carries the count; `Infinite` means unbounded backtracking.
167///
168/// A score is a count of distinct ways to match the same input prefix, so it is
169/// a whole number.
170#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
171#[non_exhaustive]
172pub enum Score {
173    /// A finite count.
174    Finite(u64),
175    /// Unbounded backtracking.
176    Infinite,
177}
178
179/// The result of a check.
180#[derive(Clone, Debug, PartialEq, Eq)]
181pub struct Report {
182    /// The error, or `None` when safe.
183    pub error: Option<AnalysisLimit>,
184    /// The checked pattern, downgraded if needed.
185    pub pattern: String,
186    /// Whether the pattern was downgraded.
187    pub pattern_downgraded: bool,
188    /// The score.
189    pub score: Score,
190    /// The discovered trails.
191    pub trails: Vec<Trail>,
192}
193
194impl Report {
195    /// Whether the pattern is safe. A pattern is safe when no analysis limit
196    /// was hit.
197    pub fn is_safe(&self) -> bool {
198        self.error.is_none()
199    }
200}
201
202/// An input error from a public entry point.
203///
204/// This covers recoverable problems with the call: a bad flag, a conflicting
205/// config, or a pattern that fails to parse. It is separate from
206/// [`AnalysisLimit`], which reports that the analysis hit a cap and is part of
207/// a successful [`Report`].
208///
209/// Match with a wildcard arm. New variants may be added in a future version.
210#[derive(Clone, Debug, PartialEq, Eq)]
211#[non_exhaustive]
212pub enum Error {
213    /// A flag letter outside `u g s y i d m`.
214    UnsupportedFlag(char),
215    /// `case_insensitive` was set together with `unicode`.
216    CaseInsensitiveWithUnicode,
217    /// `atomic_group_offsets` was set together with `downgrade_pattern: true`.
218    AtomicGroupOffsetsWithDowngrade,
219    /// `timeout` was zero.
220    InvalidTimeout,
221    /// `max_steps` was zero.
222    InvalidMaxSteps,
223    /// The pattern failed to parse. The string is the parser message.
224    Parse(String),
225    /// `downgrade_pattern` was off and the pattern has no start anchor.
226    MissingStartAnchor,
227    /// `downgrade_pattern` was off and the pattern has a backreference the
228    /// analyzer cannot handle without downgrading, such as a reference to a
229    /// group of unbounded size.
230    UnsupportedReference,
231}
232
233impl std::fmt::Display for Error {
234    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
235        match self {
236            Error::UnsupportedFlag(flag) => write!(f, "Unsupported flag: {}", flag),
237            Error::CaseInsensitiveWithUnicode => {
238                write!(f, "`caseInsensitive` cannot be used with `unicode`.")
239            }
240            Error::AtomicGroupOffsetsWithDowngrade => write!(
241                f,
242                "`atomicGroupOffsets` cannot be used with `downgradePattern: true`."
243            ),
244            Error::InvalidTimeout => write!(f, "`timeout` must be a positive number."),
245            Error::InvalidMaxSteps => write!(f, "`maxSteps` must be a positive number."),
246            Error::Parse(message) => write!(f, "{}", message),
247            Error::MissingStartAnchor => write!(
248                f,
249                "Pattern is not bounded at the start and needs downgrading. See the `downgradePattern` option."
250            ),
251            Error::UnsupportedReference => write!(
252                f,
253                "Pattern has an unsupported reference and needs downgrading. See the `downgradePattern` option."
254            ),
255        }
256    }
257}
258
259impl std::error::Error for Error {}
260
261/// Options for [`is_safe`] and [`is_safe_pattern`].
262#[derive(Clone, Debug)]
263pub struct Config {
264    /// The score cap. Above this the pattern is considered unsafe. `None` means
265    /// no cap.
266    pub max_score: Option<u64>,
267    /// The step cap. `None` means no cap.
268    pub max_steps: Option<u64>,
269    /// The wall-clock budget. `None` means no timeout.
270    pub timeout: Option<Duration>,
271    /// Case-insensitive mode.
272    pub case_insensitive: bool,
273    /// Dot-all mode.
274    pub dot_all: bool,
275    /// Multi-line mode.
276    pub multi_line: bool,
277    /// Unicode mode.
278    pub unicode: bool,
279    /// Whether to downgrade an unsupported pattern.
280    pub downgrade_pattern: bool,
281    /// Offsets of groups to treat as atomic. Only used with `downgrade_pattern`
282    /// set to `false`.
283    pub atomic_group_offsets: Option<HashSet<usize>>,
284}
285
286impl Default for Config {
287    fn default() -> Self {
288        Config {
289            max_score: Some(DEFAULT_MAX_SCORE),
290            max_steps: Some(DEFAULT_MAX_STEPS),
291            timeout: None,
292            case_insensitive: DEFAULT_CASE_INSENSITIVE,
293            dot_all: DEFAULT_DOT_ALL,
294            multi_line: DEFAULT_MULTI_LINE,
295            unicode: DEFAULT_UNICODE,
296            downgrade_pattern: true,
297            atomic_group_offsets: None,
298        }
299    }
300}
301
302struct SystemClock;
303
304impl Clock for SystemClock {
305    fn now(&self) -> f64 {
306        use std::time::{SystemTime, UNIX_EPOCH};
307        SystemTime::now()
308            .duration_since(UNIX_EPOCH)
309            .map(|d| d.as_secs_f64() * 1000.0)
310            .unwrap_or(0.0)
311    }
312}
313
314/// Parses a flag string into the four matching options.
315///
316/// The flags `u i s m` change matching. `g y d` are accepted and ignored. An
317/// unsupported letter returns [`Error::UnsupportedFlag`].
318fn parse_flags(flags: &str) -> Result<(bool, bool, bool, bool), Error> {
319    let mut unicode = false;
320    let mut case_insensitive = false;
321    let mut dot_all = false;
322    let mut multi_line = false;
323    for flag in flags.chars() {
324        match flag {
325            'u' => unicode = true,
326            'i' => case_insensitive = true,
327            's' => dot_all = true,
328            'm' => multi_line = true,
329            'g' | 'y' | 'd' => {}
330            other => return Err(Error::UnsupportedFlag(other)),
331        }
332    }
333    Ok((unicode, case_insensitive, dot_all, multi_line))
334}
335
336/// Checks whether `source` and its inline `flags` are safe from ReDoS.
337///
338/// Flags are read from `flags`, the part after a regex literal's closing `/`.
339/// The flags `u i s m` change matching. `g y d` are accepted and ignored. The
340/// flags override the matching options on `config`.
341///
342/// Returns [`Error`] on an unsupported flag, a conflicting config, or a pattern
343/// that fails to parse.
344pub fn is_safe(source: &str, flags: &str, config: &Config) -> Result<Report, Error> {
345    let (unicode, case_insensitive, dot_all, multi_line) = parse_flags(flags)?;
346
347    let merged = Config {
348        case_insensitive,
349        dot_all,
350        multi_line,
351        unicode,
352        ..config.clone()
353    };
354    is_safe_pattern(source, &merged)
355}
356
357/// Checks whether `input_pattern` is safe from ReDoS using explicit options.
358///
359/// Returns [`Error`] on a conflicting config or a pattern that fails to parse.
360pub fn is_safe_pattern(input_pattern: &str, config: &Config) -> Result<Report, Error> {
361    is_safe_pattern_with_clock(input_pattern, config, SystemClock)
362}
363
364/// Maps a count cap to the float the collector compares against. `None` becomes
365/// positive infinity, which never trips the cap.
366fn cap_to_f64(cap: Option<u64>) -> f64 {
367    cap.map_or(f64::INFINITY, |value| value as f64)
368}
369
370/// Maps a timeout to milliseconds for the checker clock. `None` becomes positive
371/// infinity, which never times out.
372fn timeout_to_f64(timeout: Option<Duration>) -> f64 {
373    timeout.map_or(f64::INFINITY, |duration| duration.as_secs_f64() * 1000.0)
374}
375
376fn is_safe_pattern_with_clock<C: Clock>(
377    input_pattern: &str,
378    config: &Config,
379    clock: C,
380) -> Result<Report, Error> {
381    if config.case_insensitive && config.unicode {
382        return Err(Error::CaseInsensitiveWithUnicode);
383    }
384    if config.downgrade_pattern && config.atomic_group_offsets.is_some() {
385        return Err(Error::AtomicGroupOffsetsWithDowngrade);
386    }
387    if config.timeout == Some(Duration::ZERO) {
388        return Err(Error::InvalidTimeout);
389    }
390    if config.max_steps == Some(0) {
391        return Err(Error::InvalidMaxSteps);
392    }
393
394    let (pattern, atomic_group_offsets) = if config.downgrade_pattern {
395        let downgraded = downgrade_pattern(input_pattern, config.unicode)?;
396        (downgraded.pattern, downgraded.atomic_group_offsets)
397    } else {
398        (
399            input_pattern.to_string(),
400            config.atomic_group_offsets.clone().unwrap_or_default(),
401        )
402    };
403
404    let pattern_downgraded = config.downgrade_pattern && input_pattern != pattern;
405
406    let ast = parse::parse(&pattern, config.unicode).map_err(|e| Error::Parse(e.0))?;
407
408    if !config.downgrade_pattern {
409        if is_missing_start_anchor(&ast) {
410            return Err(Error::MissingStartAnchor);
411        }
412        // The analyzer panics on references it cannot follow without a rewrite.
413        // Downgrading rewrites exactly those references, so a pattern the
414        // downgrade would change (after ruling out the missing-anchor rewrite
415        // above) is one the analyzer cannot handle here.
416        if downgrade_pattern(input_pattern, config.unicode)?.pattern != input_pattern {
417            return Err(Error::UnsupportedReference);
418        }
419    }
420
421    let result = collect_results(
422        CollectInput {
423            atomic_group_offsets,
424            case_insensitive: config.case_insensitive,
425            dot_all: config.dot_all,
426            max_score: cap_to_f64(config.max_score),
427            max_steps: cap_to_f64(config.max_steps),
428            multi_line: config.multi_line,
429            node: ast,
430            timeout: timeout_to_f64(config.timeout),
431        },
432        clock,
433    );
434
435    Ok(build_result(result, pattern, pattern_downgraded))
436}
437
438fn build_result(
439    result: collect_results::CollectResults,
440    pattern: String,
441    pattern_downgraded: bool,
442) -> Report {
443    let trails = result.trails.iter().map(map_trail).collect::<Vec<Trail>>();
444
445    Report {
446        error: result.error,
447        pattern,
448        pattern_downgraded,
449        score: result.score,
450        trails,
451    }
452}
453
454fn map_trail(trail: &CheckerTrail) -> Trail {
455    Trail {
456        entries: trail
457            .iter()
458            .map(|entry| TrailEntry {
459                a: TrailEntrySide {
460                    backreference_stack: to_backreference_stack(&entry.right.stack),
461                    node: to_node(&entry.right.node),
462                    quantifier_iterations: to_quantifier_iterations(&entry.right.stack),
463                },
464                b: TrailEntrySide {
465                    backreference_stack: to_backreference_stack(&entry.left.stack),
466                    node: to_node(&entry.left.node),
467                    quantifier_iterations: to_quantifier_iterations(&entry.left.stack),
468                },
469            })
470            .collect(),
471    }
472}
473
474fn to_node(node: &RcNode) -> Node {
475    Node {
476        end: NodeLocation {
477            offset: node.range.1,
478        },
479        source: node.raw.clone(),
480        start: NodeLocation {
481            offset: node.range.0,
482        },
483    }
484}
485
486fn to_backreference_stack(stack: &[StackEntry]) -> Vec<BackReference> {
487    let mut references: Vec<RcNode> = stack
488        .iter()
489        .filter_map(|entry| match entry {
490            StackEntry::Reference { reference } => Some(reference.clone()),
491            _ => None,
492        })
493        .collect();
494    references.reverse();
495    references
496        .iter()
497        .map(|reference| {
498            let index = match &reference.kind {
499                NodeKind::Reference { match_index } => *match_index,
500                _ => 0,
501            };
502            BackReference {
503                index,
504                node: to_node(reference),
505            }
506        })
507        .collect()
508}
509
510fn to_quantifier_iterations(stack: &[StackEntry]) -> Vec<QuantifierIteration> {
511    let reversed: Vec<&StackEntry> = stack.iter().rev().collect();
512    let reference_index = reversed
513        .iter()
514        .position(|entry| matches!(entry, StackEntry::Reference { .. }));
515    let portion_len = reference_index.unwrap_or(stack.len());
516    let mut portion: Vec<&StackEntry> = reversed[..portion_len].to_vec();
517    portion.reverse();
518
519    portion
520        .iter()
521        .filter_map(|entry| match entry {
522            StackEntry::Quantifier {
523                iteration,
524                quantifier,
525            } => Some(QuantifierIteration {
526                iteration: *iteration,
527                node: to_node(quantifier),
528            }),
529            _ => None,
530        })
531        .collect()
532}
533
534#[cfg(test)]
535mod api_tests {
536    use super::*;
537    use std::cell::Cell;
538
539    fn inf_steps() -> Config {
540        Config {
541            max_score: None,
542            max_steps: Some(5000),
543            ..Config::default()
544        }
545    }
546
547    /// A clock that advances by one millisecond on each read.
548    struct FakeClock {
549        time: Cell<f64>,
550    }
551
552    impl Clock for FakeClock {
553        fn now(&self) -> f64 {
554            let next = self.time.get() + 1.0;
555            self.time.set(next);
556            next
557        }
558    }
559
560    #[test]
561    fn version_is_crate_version() {
562        assert_eq!(VERSION, env!("CARGO_PKG_VERSION"));
563    }
564
565    #[test]
566    fn respects_max_score() {
567        let config = Config {
568            max_score: Some(2),
569            ..Config::default()
570        };
571        assert_eq!(is_safe("^a?a?$", "", &config).unwrap().error, None);
572        let config = Config {
573            max_score: Some(1),
574            ..Config::default()
575        };
576        assert_eq!(
577            is_safe("^a?a?$", "", &config).unwrap().error,
578            Some(AnalysisLimit::HitMaxScore)
579        );
580    }
581
582    #[test]
583    fn respects_max_steps() {
584        let config = Config {
585            max_steps: Some(20),
586            ..Config::default()
587        };
588        assert_eq!(
589            is_safe("a?a?a?", "", &config).unwrap().error,
590            Some(AnalysisLimit::HitMaxSteps)
591        );
592    }
593
594    #[test]
595    fn respects_timeout() {
596        let config = Config {
597            timeout: Some(Duration::from_millis(20)),
598            ..Config::default()
599        };
600        let clock = FakeClock {
601            time: Cell::new(0.0),
602        };
603        let result = is_safe_pattern_with_clock("a?a?a?", &config, clock).unwrap();
604        assert_eq!(result.error, Some(AnalysisLimit::TimedOut));
605    }
606
607    #[test]
608    fn rejects_zero_timeout() {
609        let config = Config {
610            timeout: Some(Duration::ZERO),
611            ..Config::default()
612        };
613        assert_eq!(is_safe("a", "", &config), Err(Error::InvalidTimeout));
614    }
615
616    #[test]
617    fn rejects_zero_max_steps() {
618        let config = Config {
619            max_steps: Some(0),
620            ..Config::default()
621        };
622        assert_eq!(is_safe("a", "", &config), Err(Error::InvalidMaxSteps));
623    }
624
625    #[test]
626    fn rejects_unsupported_flag() {
627        assert_eq!(
628            is_safe("a", "z", &Config::default()),
629            Err(Error::UnsupportedFlag('z'))
630        );
631    }
632
633    #[test]
634    fn accepts_supported_flags() {
635        for flag in ["u", "g", "s", "y", "i", "d", "m"] {
636            assert!(is_safe("a", flag, &Config::default()).is_ok());
637        }
638    }
639
640    #[test]
641    fn rejects_case_insensitive_with_unicode() {
642        let config = Config {
643            case_insensitive: true,
644            unicode: true,
645            ..Config::default()
646        };
647        assert_eq!(
648            is_safe_pattern("a", &config),
649            Err(Error::CaseInsensitiveWithUnicode)
650        );
651    }
652
653    #[test]
654    fn rejects_iterations_above_max_safe_integer() {
655        let err = is_safe_pattern("a{0,9007199254740992}", &Config::default()).unwrap_err();
656        assert!(matches!(err, Error::Parse(message)
657            if message.contains("iterations outside JS safe integer range")));
658    }
659
660    #[test]
661    fn rejects_atomic_offsets_with_downgrade() {
662        let config = Config {
663            downgrade_pattern: true,
664            atomic_group_offsets: Some(HashSet::new()),
665            ..Config::default()
666        };
667        assert_eq!(
668            is_safe_pattern("", &config),
669            Err(Error::AtomicGroupOffsetsWithDowngrade)
670        );
671    }
672
673    #[test]
674    fn supports_atomic_group_offsets() {
675        let mut offsets = HashSet::new();
676        offsets.insert(1);
677        let config = Config {
678            downgrade_pattern: false,
679            atomic_group_offsets: Some(offsets),
680            ..Config::default()
681        };
682        assert!(is_safe_pattern("^(a?)a?$", &config)
683            .unwrap()
684            .trails
685            .is_empty());
686    }
687
688    #[test]
689    fn no_options_pattern() {
690        assert_eq!(
691            is_safe_pattern("a", &Config::default()).unwrap().error,
692            None
693        );
694    }
695
696    #[test]
697    fn flags_override_config() {
698        // The 'i' flag turns on case-insensitive matching regardless of config.
699        assert!(is_safe("a", "i", &inf_steps()).is_ok());
700    }
701
702    #[test]
703    fn missing_start_anchor_without_downgrade_errors() {
704        let config = Config {
705            downgrade_pattern: false,
706            ..Config::default()
707        };
708        assert_eq!(
709            is_safe_pattern("a", &config),
710            Err(Error::MissingStartAnchor)
711        );
712    }
713}
redos_detector/lib.rs

redos_detector/
lib.rs
