我之前在写代码时用到了一个正则表达式来匹配 URL，CodeQL 检测出其存在问题：

This part of the regular expression may cause exponential backtracking on strings starting with '0' and containing many repetitions of '0'.

这其实是 CWE-1333，表明一个正则表达式可能出现极为低效的情况。接下来我们来看看具体是怎么回事。

正则表达式通常会被解析为一个非确定性有限自动机（NFA），其中每对状态和输入符号可能存在​​多个可能的后续状态。算法会逐一尝试所有可能的路径，直到找到匹配项。这一情况通常被称为 backtracking。

例如，对于正则表达式 ^(aa|.)+$，如果输入为无法匹配到的 aaX，算法会尝试以下路径：

1. 按照左侧的 aa 匹配，匹配一次
2. 按照右侧的 . 匹配，匹配两次

我们可以将正则表达式改为 ^(aa|[^a])+$，这样就可以避免同一输入存在多个匹配方法的情况。

一个更加直观的例子是 ^(a+)+$，对于无法匹配的输入 aaaaX，算法会尝试以下路径：

1. aaaa
2. aaa + a
3. aa + aa
4. a + aaa
5. aa + a + a
6. a + aa + a
7. a + a + aa
8. a + a + a + a

可以看到，如此简单的正则表达式都有了 8 种匹配的可能方式；而对于 aaaaaaaaaaaaaaaaaX，算法会尝试 \(2^{16} = 65536\) 种匹配方式，导致性能严重下降。

我们可以编写代码进行测试：

import time
import re

def test_regex_performance(regex_pattern, test_input):
    start = time.time()
    try:
        re.match(regex_pattern, test_input)
    except:
        pass
    return time.time() - start

bad_input = 'a' * 30 + 'X'
print(test_regex_performance(r'^(a+)+$', bad_input))  # 29.655
print(test_regex_performance(r'^a+$', bad_input))     # 0.0

在上面的代码中，我们使用了 Python 的 re 模块来测试正则表达式的性能。我们可以看到，使用 ^(a+)+$ 的正则表达式时，耗时 29.655 秒，而使用 ^a+$ 时，耗时几乎为 0。

对于攻击者来说，正则表达式的性能问题是一个很好的攻击向量。攻击者可以通过构造输入来导致正则表达式的性能下降，甚至导致拒绝服务（DoS）攻击。这种手段被称为正则表达式拒绝服务（ReDoS）攻击。ReDoS 攻击有许多现实案例，例如 CVE-2022-31129 等。

一些正则表达式引擎（例如 grep 等）使用确定性有限自动机（DFA）来避免 backtracking 的问题。DFA 是一种状态机，它在每个状态下只有一个可能的后续状态，因此不需要 backtracking。DFA 的性能通常比 NFA 更好，但 DFA 的实现通常更复杂。然而，由于扩展正则表达式的引入，正则表达式引擎很难完全实现 DFA，这使得其退化为了 NFA。例如：

• ​​反向引用：匹配先前捕获的组，如 (\w+)\1，这无法完全使用 DFA 实现
• 环视：如 (?=...) 正向肯定查找、(?<!...) 反向否定查找等，可能触发​​多次子表达式匹配​​

要想避免 ReDoS 也不难，通常可以检查这样几点：

• 避免嵌套量词 (a+)+、重叠选择分支 (a|aa)+ 等情况
• 使用原子组 (?>...) 使得匹配失败后不会回溯
• 禁用扩展语法，使用纯 DFA 引擎
• 禁止输入过长的字符串