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+))+` 这类深嵌套漏检——要覆盖得住上括号配对分析
10// 七条分支合成一条 alternation：原先干净输入要顺序扫七条正则，而它们都以
11// 字面量 `\(` 开头——1 MB 的全 `(` 输入里预筛每步都能命中，七遍加起来才是
12// `paren_flood_stays_linear` 那份耗时里的大头。合成后只扫一遍。
13// 七条都没有 flags，故无需逐条包裹。
14static PATTERNS: LazyLock<Regex> = LazyLock::new(|| {
15    // 外层量词：`*` / `+` / `{n,}` 都会让内层量词的回溯次数相乘
16    const Q: &str = r"(?:[+*?]|\{\d+,\})";
17    // 被重复的原子限定为可打印 ASCII：真实正则的原子是 ASCII，而 `价格 (元+)* 说明`
18    // 这类中文正文里的括号星号是散文，不是正则。非 ASCII 原子一律放过。
19    Regex::new(
20        &[
21            // (a+)+ / (a*)* / (.+)+ / (\w+\s?)*：量词套量词
22            r"\([!-~]{1,60}[+*?]\)[+*]",
23            // (a+){2,}：量词套有界重复
24            r"|\([!-~]{1,60}[+*?]\)\{\d+,\}",
25            // (a{2,})* / (a{2,}){3,}：{n,} 套外层量词
26            r"|\([!-~]{1,60}\{\d+,\}\)[+*]",
27            r"|\([!-~]{1,60}\{\d+,\}\)\{\d+,\}",
28            // (.|x)+ / (a|b|.)*：`.` 与任何分支重叠，必然回溯。只认 `|.` / `.|`
29            // ——`.` 得是分支本身。写成"括号里有 `.`"会连 `(图 1.2)*` 这种脚注标记一起报。
30            r"|\([!-~]{0,60}(?:\|\.|\.\|)[!-~]{0,60}\)",
31            Q,
32            // (\d|\w)* / (\w|y)*：字符类分支与落在类里的分支重叠。
33            // ([0-9]|[a-z]) 这类互斥字符类不算，`(a|b)*` 这类互斥单字符更不算。
34            r"|\(\\[dwsDWS]\|(?:\\[dwsDWS]|[A-Za-z0-9_])\)",
35            Q,
36            // (x|)* / (|x)*：空分支能匹配任何东西，与其余分支全重叠
37            r"|\((?:[!-~]{0,60}\||\|[!-~]{0,60})\)",
38            Q,
39        ]
40        .concat(),
41    )
42    .unwrap()
43});
44
45/// `regex` crate 没有反向引用，`(a|a)*`（分支相同）和 `(a|ab)*`（分支同前缀）只有逐字符
46/// 比较才能判定——正则表达不了。只解析最外层括号、只看"首分支是单字符"的情形：它正是
47/// 被"首分支 ≤1 字符即重叠"启发式误伤的那一类。返回命中的 `(` 位置与外层量词前面的长度。
48fn repeated_prefix_branch(input: &str) -> Option<(usize, usize)> {
49    // 每个 `(` 原本都从自己往后找 `)`，没有 `)` 时每次重扫到串尾——O(n²)：release 版
50    // 1 MB 的 `(` 要 66 秒（本机 debug 实测 148 秒），可从请求体远程触发。先取最后一个
51    // `)` 定上界（越过它的 `(` 不可能有配对），再缓存「下一个 `)`」：各次重扫的区间
52    // 互不重叠，整体线性。
53    let last_close = input.rfind(')')?;
54    let mut next_close = input.find(')')?;
55    for (open, _) in input.match_indices('(') {
56        if open > last_close {
57            break;
58        }
59        if open > next_close {
60            next_close = open + input[open..].find(')')?;
61        }
62        let close = next_close;
63        // 只认紧跟 * / + / {n,}（带逗号才算无上界，`{2}` 是有界重复，不爆炸）
64        let tail = &input[close + 1..];
65        let quant_len = match tail.chars().next() {
66            Some('*' | '+') => 1,
67            Some('{') => match tail.find('}') {
68                Some(e) if tail[..e].contains(',') => e + 1,
69                _ => 0,
70            },
71            _ => continue,
72        };
73        if quant_len == 0 {
74            continue;
75        }
76        let mut branches = input[open + 1..close].split('|');
77        // 首分支必须是单个 ASCII 字母数字：`[0-9]` 这类字符类分支不在本函数范围内
78        let Some(first) = branches.next() else {
79            continue;
80        };
81        let mut fc = first.chars();
82        let (Some(c), None) = (fc.next(), fc.next()) else {
83            continue;
84        };
85        if c.is_ascii_alphanumeric() && branches.any(|b| b.starts_with(c)) {
86            return Some((open, quant_len));
87        }
88    }
89    None
90}
91
92pub struct ReDoSDetector;
93
94impl Detector for ReDoSDetector {
95    fn name(&self) -> &'static str {
96        "redos"
97    }
98
99    fn detect(&self, input: &str) -> Option<DetectionResult> {
100        if let Some((open, quant_len)) = repeated_prefix_branch(input) {
101            let end = input[open..]
102                .find(')')
103                .map_or(input.len(), |e| open + e + 1 + quant_len);
104            return Some(DetectionResult {
105                attack_type: self.name().to_string(),
106                category: AttackCategory::Data,
107                severity: Severity::Medium,
108                matched_pattern: input[open..end].to_string(),
109                offset: open,
110                message: "Catastrophic backtracking pattern detected".into(),
111            });
112        }
113        regex_detect(
114            std::slice::from_ref(&*PATTERNS),
115            self.name(),
116            AttackCategory::Data,
117            Severity::Medium,
118            "Catastrophic backtracking pattern detected",
119            input,
120        )
121    }
122}
123
124#[cfg(test)]
125mod tests {
126    use super::*;
127    use crate::test_helpers::{assert_clean, assert_detected};
128
129    fn det() -> ReDoSDetector {
130        ReDoSDetector
131    }
132
133    fn assert_hit(input: &str) {
134        assert_detected(&det(), input, AttackCategory::Data, Severity::Medium);
135    }
136
137    #[test]
138    fn name_is_redos() {
139        assert_eq!(det().name(), "redos");
140    }
141
142    #[test]
143    fn detects_nested_quantifiers() {
144        for input in [
145            "(a+)+",
146            "(a*)*",
147            "(.+)+",
148            "([a-z]*)+",
149            "(\\d+)+$",
150            "^([a-zA-Z]+)*$",
151        ] {
152            assert_hit(input);
153        }
154    }
155
156    #[test]
157    fn detects_nested_bounded_repeats() {
158        for input in [
159            "(a+){2,}",
160            "(a{2,})*",
161            "(a{2,}){3,}",
162            "(\\d{1,}){1,}",
163            "^(a{3,})+$",
164        ] {
165            assert_hit(input);
166        }
167    }
168
169    #[test]
170    fn detects_overlapping_alternation() {
171        for input in [
172            "(a|a)*",
173            "(.|x)+",
174            "(\\w|y)*",
175            "(x|)*",
176            "(a|a){1,}",
177            "^(a|b|.)*$",
178        ] {
179            assert_hit(input);
180        }
181    }
182
183    #[test]
184    fn detects_in_longer_expression() {
185        for input in [r"^\s*(a+)+$", r"^(\w+\s?)*$", r"^([a-z]+)*$"] {
186            assert_hit(input);
187        }
188    }
189
190    #[test]
191    fn ignores_safe_regexes() {
192        for input in [
193            r"^\d{4}-\d{2}-\d{2}$",
194            r"^[a-z]+$",
195            r"(GET|POST)",
196            r"(GET|POST)*",
197            r"(foo|bar)*",
198            r"^[a-z0-9._%+-]+@[a-z0-9.-]+\.[a-z]{2,}$",
199            r"\(escaped\)+",
200        ] {
201            assert_clean(&det(), input);
202        }
203    }
204
205    #[test]
206    fn ignores_disjoint_alternation() {
207        // 分支互斥 = 没有回溯歧义，(a|b)* 是线性匹配。旧启发式只看"首分支 ≤1 字符"，
208        // 把这类正常正则和中文正文里的括号星号全算成了 ReDoS。
209        for input in [
210            "(a|b)*",
211            "(0|1)+",
212            "(y|n)*",
213            "(x|y|z)+",
214            "^(a|b)+$",
215            "(a|b){2,}",
216            "(?i)(a|b)*",
217            "选项(是|否)*",
218            "步骤(1|2)*3",
219            "价格 (元+)* 说明",
220            "注意(重要+)*提醒",
221        ] {
222            assert_clean(&det(), input);
223        }
224    }
225
226    #[test]
227    fn ignores_benign_inputs() {
228        for input in [
229            "Hello, this is a normal text input. Nothing suspicious here.",
230            "5*(3+2)",
231            "the (very) long text",
232            "function(a, b)",
233            "穿越之霸道总裁爱上我--重生之都市修仙",
234        ] {
235            assert_clean(&det(), input);
236        }
237    }
238
239    #[test]
240    fn still_reports_same_prefix_branches() {
241        // 分支相同 / 同前缀才是真重叠——`regex` crate 没有反向引用，这条走字符串比较
242        for input in ["(a|a)*", "(a|ab)*", "(a|a){1,}"] {
243            assert_hit(input);
244        }
245        // 有界重复 `{2}` 不爆炸
246        assert_clean(&det(), "(a|a){2}");
247    }
248
249    /// 回归守卫：旧实现里每个 `(` 都从自己往后 `find(')')`，没有 `)` 时每次重扫到串尾，
250    /// 复杂度 O(n²)：1 MB 的 `(` 要 66 秒 CPU（release 实测；本机 debug 实测 148 秒），
251    /// 且来自请求体、可远程触发。
252    ///
253    /// 计时只压在「无 `)`」这一形态上：它的线性实现是一次 `rfind`（微秒级），比上限低
254    /// 五个数量级，CI 再拥挤也撞不穿；O(n²) 则是上限的 15 倍。带 `)` 的形态线性开销是
255    /// O(n) 次循环（毫秒级），在本机负载 9~14 / 8 核的环境里挂钟时间会被拉长几十倍
256    /// （实测把 45 ms 拉过 3 秒），给它定上限必然误报——所以它只钉正确性。
257    #[test]
258    fn paren_flood_stays_linear() {
259        use std::time::{Duration, Instant};
260        // 1 MB 的 `(`，一个 `)` 都没有：正是报告里那个 66 秒的请求体
261        let unclosed = "(".repeat(1_000_000);
262        let t = Instant::now();
263        let hit = repeated_prefix_branch(&unclosed);
264        let elapsed = t.elapsed();
265        assert!(hit.is_none(), "光有括号不是 ReDoS");
266        assert!(
267            elapsed < Duration::from_secs(10),
268            "二次方重扫回来了：{} 个字符耗时 {elapsed:?}（线性实现是微秒级）",
269            unclosed.len()
270        );
271        // 带 `)` 的形态（走缓存的 close）只钉正确性，不钉时间
272        let closed = format!("{})", "(".repeat(200_000));
273        assert!(repeated_prefix_branch(&closed).is_none());
274    }
275
276    /// 真实语料：代码与散文里的括号不该被当成 ReDoS。
277    #[test]
278    fn ignores_realistic_source_and_prose() {
279        for input in [
280            // Python 源码：大量括号、管道、量词，但没有嵌套量词
281            "def summarize(items, limit=10):\n    names = [i.name for i in items if i.name]\n    top = names[:limit]\n    return (len(top), top)\n",
282            "if (a or b) and not (c or d):\n    print((a, b))\n",
283            "PATTERN = re.compile(r\"^[a-z0-9]+$\")  # (safe) no nested quantifier\n",
284            // 工单 / 文档散文
285            "步骤(1|2)*3 是笔误，正确写法是 (a|b)*，请核对",
286            "价格 (元+)* 说明：括号里的加号是正文，不是正则",
287            "See (a) and (b)* in the appendix; (x|y)* means repeat either.",
288            "The customer wrote: 我的号码是 (010) 1234-5678, 请回电",
289        ] {
290            assert_clean(&det(), input);
291        }
292    }
293
294    #[test]
295    fn edge_cases() {
296        assert_clean(&det(), "");
297        assert_clean(&det(), "   ");
298        assert_clean(&det(), "()");
299        assert_clean(&det(), "()*");
300        assert_clean(&det(), "(a)");
301        // 量词在括号外但组内无重复——(really)* 是安全的
302        assert_clean(&det(), "(really)*");
303        // 已知缺口：深嵌套括号 + 长分支重叠看不到，单层括号启发式的上限
304        assert_clean(&det(), r"^(([a-z])+.)+[A-Z]([a-z])+$");
305        assert_clean(&det(), "^([0-9]|[0-9]){1,}$");
306    }
307}
security_rust/data/redos.rs

security_rust/data/
redos.rs
