security_rust/data/
redos.rs

1// Copyright (c) 2026 erik <erik@erik.xyz> — https://erik.xyz
2
3use crate::{AttackCategory, DetectionResult, Detector, Severity, regex_detect};
4use regex::Regex;
5use std::sync::LazyLock;
6
7// 防御方视角：调用方准备把用户输入当正则编译时先扫一遍。
8// 只挑无歧义会指数回溯的形态，宁可漏也不误杀。
9// ponytail: 只做单层括号，`((a+))+` 这类深嵌套漏检——要覆盖得住上括号配对分析
10static PATTERNS: LazyLock<Vec<Regex>> = LazyLock::new(|| {
11    // 外层量词：`*` / `+` / `{n,}` 都会让内层量词的回溯次数相乘
12    const Q: &str = r"(?:[+*?]|\{\d+,\})";
13    // 被重复的原子限定为可打印 ASCII：真实正则的原子是 ASCII，而 `价格 (元+)* 说明`
14    // 这类中文正文里的括号星号是散文，不是正则。非 ASCII 原子一律放过。
15    vec![
16        // (a+)+ / (a*)* / (.+)+ / (\w+\s?)*：量词套量词
17        Regex::new(r"\([!-~]{1,60}[+*?]\)[+*]").unwrap(),
18        // (a+){2,}：量词套有界重复
19        Regex::new(r"\([!-~]{1,60}[+*?]\)\{\d+,\}").unwrap(),
20        // (a{2,})* / (a{2,}){3,}：{n,} 套外层量词
21        Regex::new(r"\([!-~]{1,60}\{\d+,\}\)[+*]").unwrap(),
22        Regex::new(r"\([!-~]{1,60}\{\d+,\}\)\{\d+,\}").unwrap(),
23        // (.|x)+ / (a|b|.)*：`.` 与任何分支重叠，必然回溯。只认 `|.` / `.|`
24        // ——`.` 得是分支本身。写成"括号里有 `.`"会连 `(图 1.2)*` 这种脚注标记一起报。
25        Regex::new(&[r"\([!-~]{0,60}(?:\|\.|\.\|)[!-~]{0,60}\)", Q].concat()).unwrap(),
26        // (\d|\w)* / (\w|y)*：字符类分支与落在类里的分支重叠。
27        // ([0-9]|[a-z]) 这类互斥字符类不算，`(a|b)*` 这类互斥单字符更不算。
28        Regex::new(&[r"\(\\[dwsDWS]\|(?:\\[dwsDWS]|[A-Za-z0-9_])\)", Q].concat()).unwrap(),
29        // (x|)* / (|x)*：空分支能匹配任何东西，与其余分支全重叠
30        Regex::new(&[r"\((?:[!-~]{0,60}\||\|[!-~]{0,60})\)", Q].concat()).unwrap(),
31    ]
32});
33
34/// `regex` crate 没有反向引用，`(a|a)*`（分支相同）和 `(a|ab)*`（分支同前缀）只有逐字符
35/// 比较才能判定——正则表达不了。只解析最外层括号、只看"首分支是单字符"的情形：它正是
36/// 被"首分支 ≤1 字符即重叠"启发式误伤的那一类。返回命中的 `(` 位置与外层量词前面的长度。
37fn repeated_prefix_branch(input: &str) -> Option<(usize, usize)> {
38    for (open, _) in input.match_indices('(') {
39        let Some(rel_close) = input[open..].find(')') else {
40            continue;
41        };
42        let close = open + rel_close;
43        // 只认紧跟 * / + / {n,}（带逗号才算无上界，`{2}` 是有界重复，不爆炸）
44        let tail = &input[close + 1..];
45        let quant_len = match tail.chars().next() {
46            Some('*' | '+') => 1,
47            Some('{') => match tail.find('}') {
48                Some(e) if tail[..e].contains(',') => e + 1,
49                _ => 0,
50            },
51            _ => continue,
52        };
53        if quant_len == 0 {
54            continue;
55        }
56        let mut branches = input[open + 1..close].split('|');
57        // 首分支必须是单个 ASCII 字母数字：`[0-9]` 这类字符类分支不在本函数范围内
58        let Some(first) = branches.next() else {
59            continue;
60        };
61        let mut fc = first.chars();
62        let (Some(c), None) = (fc.next(), fc.next()) else {
63            continue;
64        };
65        if c.is_ascii_alphanumeric() && branches.any(|b| b.starts_with(c)) {
66            return Some((open, quant_len));
67        }
68    }
69    None
70}
71
72pub struct ReDoSDetector;
73
74impl Detector for ReDoSDetector {
75    fn name(&self) -> &'static str {
76        "redos"
77    }
78
79    fn detect(&self, input: &str) -> Option<DetectionResult> {
80        if let Some((open, quant_len)) = repeated_prefix_branch(input) {
81            let end = input[open..]
82                .find(')')
83                .map_or(input.len(), |e| open + e + 1 + quant_len);
84            return Some(DetectionResult {
85                attack_type: self.name().to_string(),
86                category: AttackCategory::Data,
87                severity: Severity::Medium,
88                matched_pattern: input[open..end].to_string(),
89                offset: open,
90                message: "Catastrophic backtracking pattern detected".into(),
91            });
92        }
93        regex_detect(
94            &PATTERNS,
95            self.name(),
96            AttackCategory::Data,
97            Severity::Medium,
98            "Catastrophic backtracking pattern detected",
99            input,
100        )
101    }
102}
103
104#[cfg(test)]
105mod tests {
106    use super::*;
107    use crate::test_helpers::{assert_clean, assert_detected};
108
109    fn det() -> ReDoSDetector {
110        ReDoSDetector
111    }
112
113    fn assert_hit(input: &str) {
114        assert_detected(&det(), input, AttackCategory::Data, Severity::Medium);
115    }
116
117    #[test]
118    fn name_is_redos() {
119        assert_eq!(det().name(), "redos");
120    }
121
122    #[test]
123    fn detects_nested_quantifiers() {
124        for input in [
125            "(a+)+",
126            "(a*)*",
127            "(.+)+",
128            "([a-z]*)+",
129            "(\\d+)+$",
130            "^([a-zA-Z]+)*$",
131        ] {
132            assert_hit(input);
133        }
134    }
135
136    #[test]
137    fn detects_nested_bounded_repeats() {
138        for input in [
139            "(a+){2,}",
140            "(a{2,})*",
141            "(a{2,}){3,}",
142            "(\\d{1,}){1,}",
143            "^(a{3,})+$",
144        ] {
145            assert_hit(input);
146        }
147    }
148
149    #[test]
150    fn detects_overlapping_alternation() {
151        for input in [
152            "(a|a)*",
153            "(.|x)+",
154            "(\\w|y)*",
155            "(x|)*",
156            "(a|a){1,}",
157            "^(a|b|.)*$",
158        ] {
159            assert_hit(input);
160        }
161    }
162
163    #[test]
164    fn detects_in_longer_expression() {
165        for input in [r"^\s*(a+)+$", r"^(\w+\s?)*$", r"^([a-z]+)*$"] {
166            assert_hit(input);
167        }
168    }
169
170    #[test]
171    fn ignores_safe_regexes() {
172        for input in [
173            r"^\d{4}-\d{2}-\d{2}$",
174            r"^[a-z]+$",
175            r"(GET|POST)",
176            r"(GET|POST)*",
177            r"(foo|bar)*",
178            r"^[a-z0-9._%+-]+@[a-z0-9.-]+\.[a-z]{2,}$",
179            r"\(escaped\)+",
180        ] {
181            assert_clean(&det(), input);
182        }
183    }
184
185    #[test]
186    fn ignores_disjoint_alternation() {
187        // 分支互斥 = 没有回溯歧义，(a|b)* 是线性匹配。旧启发式只看"首分支 ≤1 字符"，
188        // 把这类正常正则和中文正文里的括号星号全算成了 ReDoS。
189        for input in [
190            "(a|b)*",
191            "(0|1)+",
192            "(y|n)*",
193            "(x|y|z)+",
194            "^(a|b)+$",
195            "(a|b){2,}",
196            "(?i)(a|b)*",
197            "选项(是|否)*",
198            "步骤(1|2)*3",
199            "价格 (元+)* 说明",
200            "注意(重要+)*提醒",
201        ] {
202            assert_clean(&det(), input);
203        }
204    }
205
206    #[test]
207    fn ignores_benign_inputs() {
208        for input in [
209            "Hello, this is a normal text input. Nothing suspicious here.",
210            "5*(3+2)",
211            "the (very) long text",
212            "function(a, b)",
213            "穿越之霸道总裁爱上我--重生之都市修仙",
214        ] {
215            assert_clean(&det(), input);
216        }
217    }
218
219    #[test]
220    fn still_reports_same_prefix_branches() {
221        // 分支相同 / 同前缀才是真重叠——`regex` crate 没有反向引用，这条走字符串比较
222        for input in ["(a|a)*", "(a|ab)*", "(a|a){1,}"] {
223            assert_hit(input);
224        }
225        // 有界重复 `{2}` 不爆炸
226        assert_clean(&det(), "(a|a){2}");
227    }
228
229    #[test]
230    fn edge_cases() {
231        assert_clean(&det(), "");
232        assert_clean(&det(), "   ");
233        assert_clean(&det(), "()");
234        assert_clean(&det(), "()*");
235        assert_clean(&det(), "(a)");
236        // 量词在括号外但组内无重复——(really)* 是安全的
237        assert_clean(&det(), "(really)*");
238        // 已知缺口：深嵌套括号 + 长分支重叠看不到，单层括号启发式的上限
239        assert_clean(&det(), r"^(([a-z])+.)+[A-Z]([a-z])+$");
240        assert_clean(&det(), "^([0-9]|[0-9]){1,}$");
241    }
242}
security_rust/data/redos.rs

security_rust/data/
redos.rs
