title: "正则灾难性回溯与防御方法" categories: Tech updated: comments: true
考虑用正则表达式 (x+x+)+y 匹配字符串 xxxxxxxxxxy (10 个 x). 显然正则可以改写为 xx+y 或者 x{2,}y, 但先不管这点, 该例旨在展示匹配机制.
x+ 匹配 10 个 x, 第二个 x+ 没匹配上; 于是第一个 x+ 回溯 到匹配 9 个 x, 第二个 x+ 匹配一个 x. 至此 group 1 x+x+ 完成了一次匹配. (x+x+)+ 完成了一次匹配. 接下来匹配 y, 完成匹配.删除字符串结尾的 y 使得正则匹配失败会导致 灾难性回溯 (catastrophic backtracking).
<!-- more -->x+ 因为只匹配了一个 x, 无法回溯. 第 1 个 x+ 匹配 8 个 x, 第 2 个 x+ 匹配 xx. x+ 匹配 x. Group 1 尝试重复失败, 末尾 y 匹配失败.x+ 匹配 7 个 x, 第 2 个 x+ 匹配 xxx -> xx -> x. Group 1 尝试重复匹配到 xx (每个 x+ 各一个 x), 末尾 y 匹配失败.在 regex101 上尝试不同长度的 x, 可见复杂度为 O(2^n), 其中 n 为字符串长度.
用 ^(.*?,){11}P 匹配 CSV 文件中第 12 列开头为 P 的行. 用它匹配 "1,2,3,4,5,6,7,8,9,10,11,12,13" 会发生灾难性回溯.
^(.*?,){11} 匹配到 "1,2,3,4,5,6,7,8,9,10,11," 之后由于后面不是 P, 开始回溯. .*?, 转而匹配 "11,12,", 而后面的 "13" 依然不以 P 开头, 于是回溯. 第 11 个 .*?, 继续往后匹配, 失败后回溯到处理第 10 个 .*?,..*?, 匹配 "10,11,", 第 11 个 .*?, 匹配 "12,"....*?,匹配 "9,10,"...考虑 <html>.*?<head>.*?<title>.*?</title>.*?</head>.*?<body[^>]*>.*?</body>.*?</html> 匹配 HTML 文件 (开 single line mode 应对换行).
如果 HTML 文件少了一些 tags, 会导致灾难性回溯. 比如去掉文件末尾的 </html>, 末尾匹配失败后, 放弃 </body>.*? 匹配的部分, </body> 前面的 .*? 向后查找第二个 </body>, 失败... 一共 7 个 .*?, 因此复杂度是 O(n^7).
一开始的正则表达式 (x+x+)+y 可以改写为 (x+x+)++y, 其中额外的 + 是 possessive quantifier; 或者改写为 (?>(x+x+)+)y, 其中 ?> 表示 atomic group. Python 3.11 才终于把这两个特性加入标准库 re 中.
独占模式. 例如用 b{1,3}+bc 匹配 "bbc". 类似贪婪模式, 首先 b{1,3}+ 尽可能多地匹配, 匹配到 "bb", 之后用 b 匹配 "c" 失败尝试回溯. 此时独占模式 b{1,3}+ 视为整体不在里面回溯, 导致整体匹配直接失败.
匹配 CSV. 希望逗号作为分隔符, 正则 ^(.*?,){11}P 可以改写为 ^([^,\r\n]*,){11}P, 这样只需回溯 11 次. 也可以改写为 ^(?>(.*?,){11})P. 原子组 匹配到的东西视为一个整体 (所以叫原子). 正则引擎会
^, 进入原子组匹配 (.*?,){11}, 匹配到 " 1,2,3,4,5,6,7,8,9,10,11,"P 失败. 尝试回溯时因为原子组视为整体, 进一步回溯到开头 ^, 导致整个正则匹配失败, 结束匹配.进一步优化正则可写为 ^(?>((?>[^,\r\n]*),){11})P, 因为独占+贪婪模式比懒惰模式更快; 或者用独占模式写为更简洁的 ^(?>([^,\r\n]*+,){11})P.
匹配 HTML. 原始正则 <html>.*?<head>.*?<title>.*?</title>.*?</head>.*?<body[^>]*>.*?</body>.*?</html> 可用原子组写为 <html>(?>.*?<head>)(?>.*?<title>)(?>.*?</title>)(?>.*?</head>)(?>.*?<body[^>]*>)
(?>.*?</body>).*?</html> 因为明确知道这些 tags 只会出现一次, 以此避免回溯.
如果服务端自己写死了正则, 那么自己排查即可. (可以参考 这篇文章 提到的检测工具, 我没用过.) 遇到过正则攻击 (regular expression denial of service) 的案例包括
如果接受用户端自定义的正则, 有这些方法.
正则引擎有两种: 文本导向 (text-directed, 或者 DFA) 和正则导向 (regex-directed, 或者 NFA). 前面谈论的灾难性回溯问题都假定用了正则导向的引擎, 这也是大多数正则引擎的实现方式 (包括 Python). 文本导向的引擎保证了线性时间复杂度, 但因为不支持回溯, 也不支持 backreference 和 lookaround (比如 (?=...), (?<=...) 等), 表达性不如正则导向的引擎.
绝大多数情况下两种引擎匹配结果相同. 可以考虑换用文本导向引擎, 如 Google 的 re2 (对 Python 来说, 遇到引擎不支持的特性时, 会 fall back 到原生的 re 库). 用 re2 时性能问题见 issues/420.
很多语言支持设置正则最大匹配时间/回溯次数等. 但是 Python 没有现成的支持 (可以参考 这个, 但总体不推荐).
扩展阅读 (我没读过)