正则灾难性回溯与防御方法

| ~ |

灾难性回溯

考虑用正则表达式 (x+x+)+y 匹配字符串 xxxxxxxxxxy (10 个 x). 显然正则可以改写为 xx+y 或者 x{2,}y, 但先不管这点, 该例旨在展示匹配机制.

  • 第一个 x+ 匹配 10 个 x, 第二个 x+ 没匹配上; 于是第一个 x+ 回溯 到匹配 9 个 x, 第二个 x+ 匹配一个 x. 至此 group 1 x+x+ 完成了一次匹配.
  • Group 1 尝试重复, 但失败了, 于是 (x+x+)+ 完成了一次匹配. 接下来匹配 y, 完成匹配.

删除字符串结尾的 y 使得正则匹配失败会导致 灾难性回溯 (catastrophic backtracking).

  • 正则末尾 y 匹配失败后开始回溯. 第 2 个 x+ 因为只匹配了一个 x, 无法回溯. 第 1 个 x+ 匹配 8 个 x, 第 2 个 x+ 匹配 xx.
  • 末尾 y 匹配失败后开始回溯. 第 2 个 x+ 匹配 x. Group 1 尝试重复失败, 末尾 y 匹配失败.
  • 第 1 个 x+ 匹配 7 个 x, 第 2 个 x+ 匹配 xxx -> xx -> x. Group 1 尝试重复匹配到 xx (每个 x+ 各一个 x), 末尾 y 匹配失败.
  • 如上的 (7, 1), (1, 1) 组合失败了, 接下来是 (6, 4) -> (6, 3) -> (6, 2), (1, 1) -> … -> (6, 1), (2, 1) -> … -> (6, 1), (1, 2) -> …

在 regex101 上尝试不同长度的 x, 可见复杂度为 O(2^n), 其中 n 为字符串长度.

示例: 匹配 CSV

用 ^(.*?,){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 个 .*?, 转而匹配 “11,12,”, 而后面的 “13” 依然不以 P 开头, 于是回溯. 第 11 个 .*?, 继续往后匹配, 失败后回溯到处理第 10 个 .*?,.
  • 于是第 10 个 .*?, 匹配 “10,11,”, 第 11 个 .*?, 匹配 “12,”…
  • 失败后回溯到第 9 个 .*?,匹配 “9,10,”…

示例: 匹配 HTML

考虑 <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 没有现成的支持 (可以参考 这个, 但总体不推荐).

进一步优化正则

  • 去掉不需要的捕获组 (用 (?:...)), 参考 这里.
  • 注意类似 (one|two)* 的正则, 回溯时选择肢很多, 参考 这里.

参考

扩展阅读 (我没读过)