正则不是越复杂越好：一次 ReDoS 把接口 P99 从 50ms 打到 30s 的事故，和 3 个引擎真相

title: 正则不是越复杂越好一次 ReDoS 把接口 P99 从 50ms 打到 30s 的事故和 3 个引擎真相tags: 正则表达式, ReDoS, NFA, Java Pattern, 性能优化description: 从一次正则回溯爆炸拖垮接口的线上事故讲清 NFA/DFA 引擎差异、回溯灾难的成因以及在 Java 里如何写打不爆的正则。我们有个商品搜索接口接收用户手写的关键词做模糊匹配匹配逻辑里有一句正则用来校验关键词里是否含有嵌套的括号表达式。平时 P99 在 50ms 左右。某天运营在后台导出了一个带几十个左括号的脏数据做测试接口直接超时P99 飙到 30 秒线程池被打满整个搜索服务雪崩。事后定位凶手就是那条正则。它在遇到特定输入时会指数级回溯专业名词叫 ReDoSRegular Expression Denial of Service正则拒绝服务。这篇文章把正则引擎的底层和这个坑讲透。Java 用的到底是哪种引擎先说一个反直觉的事实大多数开发者以为正则是确定性的模式匹配但Java 的java.util.regex是 NFA非确定有限自动机引擎不是 DFA确定有限自动机引擎。区别在哪DFA匹配时每个字符只读一遍状态机顺着走时间复杂度与输入长度线性相关且绝不会回溯。缺点是不支持反向引用、捕获组这类高级特性。NFA支持捕获组、反向引用、懒惰/贪婪量词但它的代价是——当一条路径走不通时引擎会回溯去试另一条路。回溯次数在最坏情况下会随输入长度指数爆炸。Java 选了 NFA所以你能写(a)、反向引用\1但也因此继承了回溯爆炸的风险。理解这一点是看懂 ReDoS 的前提。灾难现场那段看起来人畜无害的正则问题正则简化后长这样用来匹配被多层括号包裹的内容// 危险正则用于校验 ((...)) 形式的嵌套括号关键词 private static final Pattern NESTED Pattern.compile(\\(([a-z](\\[a-z])*)\\)); // 触发灾难的输入 public boolean isNestedKeyword(String input) { Matcher m NESTED.matcher(input); // 1. 编译一次这里复用没问题 return m.matches(); // 2. 对用户输入调用 matches —— 灾难入口 }逐行解释第 1 行Pattern.compile放在静态常量里是对的正则编译很贵绝不能每次请求都 compile。第 2 行m.matches()是真正的炸弹——当input类似((((((((((((((((((((a这种大量左括号 结尾不匹配的字符串时引擎会疯狂回溯。为什么会爆炸看正则里的([a-z](\[a-z])*)\)。[a-z]是贪婪的它会先吃掉所有字母然后发现后面没有右括号于是一步步吐回来尝试分组匹配而外层的(和可能的嵌套又制造了更多分支。输入里每多一个左括号回溯路径就近似翻倍。20 个左括号可能要试几百万次回溯30 秒一点都不夸张。怎么在 Java 里复现并守住这道防线下面这段代码是我用来验证正则安不安全的最小工具——给它一个正则和一个恶意输入看它多久跑完// 正则安全性自检用带超时的方式限制匹配耗时避免主线程被卡死 public boolean safeMatch(String regex, String input, long timeoutMs) { Pattern p Pattern.compile(regex); Matcher m p.matcher(input); // 1. 不要直接 m.matches()用有限步数的 find 手动超时兜底 long deadline System.nanoTime() timeoutMs * 1_000_000L; while (m.find()) { // 2. 用 find 而非 matches只找第一个匹配 if (System.nanoTime() deadline) { // 3. 超过预算就放弃判定为可疑正则/输入 throw new RuntimeException(regex timeout, possible ReDoS: regex); } // 处理匹配结果... } return m.hitEnd(); }逐行解释第 3 行用find()而非matches()matches()要求整串匹配会逼着引擎尝试所有可能的分割方式最容易被 ReDoS 打中。第 5 行设了一个 deadline超时即判定可疑——这是个止血手段真正的解决是改正则本身见下文。第 8 行hitEnd()表示输入在匹配中途结束常用于流式匹配判断是否需要更多数据。但我要强调超时只是兜底不是根治。根治办法是把指数回溯结构改写成线性结构。改法把贪婪嵌套换成占有量词或重写最容易被忽视的工具是占有量词possessive quantifier、*、?和原子组(?...)。它们一旦匹配就不回溯直接斩断回溯爆炸// 安全版本用占有量词杜绝回溯 private static final Pattern SAFE Pattern.compile(\\(([a-z](\\[a-z])*)\\)); public boolean isNestedKeywordSafe(String input) { return SAFE.matcher(input).matches(); // 1. [a-z] 吃掉后绝不吐回无回溯分支 }逐行解释把[a-z]改成[a-z]是关键。是占有贪婪——它匹配到尽可能多后不允许引擎回头重新分配字符给其他分支于是原本指数级的回溯路径被压成了线性。同样(\[a-z])*也用占有量词包住。改完之后那个 30 个左括号的输入瞬间返回不匹配再也不会卡 30 秒。如果不是简单量词能解决就要从结构上重写正则比如用白名单替代复杂的允许嵌套的表达式或者把嵌套括号这种需求交给真正的递归下降解析器而不是塞进一条正则。我们线上的 3 个教训教训一用户输入永远不可信尤其是进了正则的。那次事故的根因是脏数据 复杂正则的组合。任何把用户字符串直接喂给matches()/find()的地方都应先做长度和字符集白名单过滤。我们后来加了前置校验关键词长度超 64 或含异常多重复括号的直接拒绝。教训二正则越聪明越危险。嵌套、多选分支叠加、.*配.*的夹心结构都是 ReDoS 高发区。一条正则如果肉眼读起来要停顿三秒它大概率有性能雷。我们定了个规范超过 40 字符或含 2 层以上量词嵌套的正则必须写单元测试跑恶意输入。教训三监控要能抓到慢匹配。回溯卡死不会抛异常只会慢。我们给所有 regex 调用包了一层耗时统计P99 正则耗时超过 100ms 就告警。那次如果早有这个监控能在雪崩前 5 分钟就定位。三个引擎真相很多人一直搞错真相一Java 正则不是慢是可能指数慢。正常输入下Pattern很快问题只在特定病态输入。所以你不能靠压测正常数据来排除风险。真相二预编译不等于安全。很多人知道Pattern.compile要提出来但这只解决编译开销不解决回溯。编译一次照样能回溯到天荒地老。真相三正则表达式不是图灵完备但 NFA 回溯能模拟指数时间。别指望正则一定快。需要复杂结构匹配时老老实实写解析代码比和正则搏斗靠谱。我的取舍建议校验类需求邮箱、手机号、订单号用最简单的字符类 锚定能用[0-9a-zA-Z]白名单就别用.*。复杂文本解析日志、模板、DSL正则只做粗切分真正的解析交给状态机或解析库如 ANTLR别让一条正则包揽所有逻辑。凡是用到用户输入做matches/find的服务给正则调用加超时和输入白名单双保险。除了防 ReDoS还有几个 Java 正则特有的坑坑一String.matches每次都重新编译。很多人图方便写123.matches(\\d)但String.matches内部每次都Pattern.compile高频调用下编译开销肉眼可见。正确做法是把 Pattern 提成静态常量复用 Matcher。// 反例热路径里用 String.matches每次重新编译正则 public boolean isDigitBad(String s) { return s.matches(\\d); // 1. 每次调用都 compile 一次QPS 高时变慢 } // 正例预编译 复用 Matcher private static final Pattern DIGIT Pattern.compile(\\d); public boolean isDigitGood(String s) { return DIGIT.matcher(s).matches(); // 2. 编译一次反复用比重新编译便宜得多 }逐行解释第 2 行的问题不在正则本身在于matches方法签名里隐藏了Pattern.compile(s.regex)。第 7 行把编译移到静态常量JVM 只编译一次并缓存Matcher虽每次 new但比重新编译正则便宜得多。再进一步如果同一 Matcher 要匹配多个输入用matcher.reset(input)复用连 Matcher 都不用重建。我们曾在网关里把十几处String.matches改成预编译常量单个校验接口的 CPU 掉了约 15%。坑二优先用命名组而不是下标。Java 7 之后支持命名捕获组(?name...)比起group(1)、group(2)的下标玩法可读性和抗变更能力强太多// 用命名组解析 orderId123amount456 这类简单键值串 private static final Pattern KV Pattern.compile((?k[a-zA-Z])(?v\\d)); public void parse(String s) { Matcher m KV.matcher(s); while (m.find()) { // 1. 循环找所有匹配而非整串匹配 String key m.group(k); // 2. 按名字取比 group(1) 清晰 String val m.group(v); System.out.println(key - val); } }逐行解释第 2 行(?k...)把捕获组命名为k取用时用group(k)而非group(1)。当正则里插入或删除一个组时下标会全部错位命名组不受影响。第 4 行find()配合while提取串里所有键值对而不是matches()那样要求整串匹配。我们代码评审把group(数字)列为不推荐写法强制改用命名组后续改正则再没出过错位 bug。这条和 ReDoS 不冲突命名组解决可维护性占有量词解决性能两者一起用才是稳的组合。坑三.默认不匹配换行。很多人写(?s)想让.匹配换行却忘了开关导致多行文本匹配失败。如果确实要跨行匹配用Pattern.DOTALL或在表达式前加(?s)如果只想按行处理老老实实逐行find。我们日志解析就曾因为.不跨行漏匹配了带换行的堆栈排查了一下午。思考题把你代码库里所有Pattern.compile和String.matches注意String.matches内部每次都重新编译本身就是性能和安全的双重雷拉出来扫一遍有没有(a)、(.*)*、(a|a)*这类灾难三件套挑一条最复杂的构造一个超长重复输入的测试用例跑一下看看你的接口会不会也卡 30 秒。这一试往往能试出几个你从没注意过的雷。