在 2009 年 11 月刊中，我写了一篇标题为“XML 拒绝服务攻击和防御” (msdn.microsoft.com/magazine/ee335713) 的文章，在这篇文章中，我介绍了一些对 XML 分 析程序特别有效的拒绝服务 (DoS) 攻击技巧。我从读者那里收到许多有关此文章的电子邮件， 他们都想了解有关这方面的更多知识，这让我真正意识到人们已经了解 DoS 攻击的严重性。
我相信，在未来的四到五年中，随着权限升级，执行攻击会变得更加困难，这是由于不断采 用诸如数据执行保护 (DEP)、地址空间布局随机化 (ASLR) 以及隔离和权限降低技巧之类的内 存保护措施所致，攻击者会将其目标转移到 DoS 敲诈攻击。目前，开发人员可以通过领先于攻 击趋势变化并针对未来可能的 DoS 演变方向继续保护其应用程序。
正则表达式 DoS 就是这些未来可能的 DoS 演变方向之一。在以色列召开的 2009 年“开放 式 Web 应用安全项目 (OWASP)”会议上，Checkmarx 首席架构师 Alex Roichman 和高级程序 员 Adar Weidman 做了有关正则表达式 DoS（也称为“ReDoS”）的深入研究报告。他们的研究 表明，编写不严谨的正则表达式可能会受到攻击，以致计算相对较短的攻击字符串（少于 50 个字符）需要数小时或更长时间。在最坏的情况下，处理时间实际上相当于输入字符串中字符 数的幂数，这意味着，向字符串中增加一个字符串就会使处理时间翻倍。
在本文中，我将介绍正则表达式在哪些情况下容易受到这些攻击。我还将提供“正则表达式 模糊测试程序”代码，这一测试程序是专为识别易受攻击的正则表达式设计的，其识别方法为 通过针对成千上万的随机输入计算正则表达式，并标记完成处理所需时间长度不可接受的输入 。
（注意：在本文中，我假设您熟悉正则表达式的语法。如果您不熟悉此语法，可能需要阅读 “.NET Framework 正则表达式”这篇文章（网址为 msdn.microsoft.com/library/hs600312） 来补充这些知识，如果要深入研究，请阅读 Jeffrey Friedl 编写的参考手册《精通正则表达 式第 3 版》[O’Reilly，2006]。
回溯：问题的根源
从本质上讲，存在两种不同类型的正则表达式引擎：确定性有穷自动机 (DFA) 引擎和非确 定性有穷自动机 (NFA) 引擎。这两种引擎类型的完整差异分析超出本文范围，我们仅着重探讨 以下两个方面：
NFA 引擎是回溯引擎。与对输入字符串中的每个字符最多计算一次的 DFA 不同，NFA 引擎 可以对输入字符串中的每个字符计算多次。（我将在稍后说明此回溯计算算法的计算原理。） 回溯方法具有诸多优势，因为这些引擎可以处理更复杂的正则表达式，如包含向后引用或捕获 括号的正则表达式。它也具有一些缺点，因为其处理时间大大超过 DFA 的处理时间。
Microsoft .NET Framework System.Text.RegularExpression 使用 NFA 引擎。
回溯的一个重要负面影响是，虽然正则表达式可以相当快速地确定肯定匹配（即，输入字符 串与给定正则表达式匹配），但确定否定匹配（输入字符串与正则表达式不匹配）所需的时间 更长。实际上，此引擎必须确定输入字符串中没有任何可能的“路径”与正则表达式匹配，这 意味着必须对所有路径进行测试。
利用简单的非分组正则表达式，确定否定匹配所花的时间并不是一个大问题。例如，假设要 匹配的正则表达式为：
^\d+$
如果整个输入字符串仅包含数字字符，则这是一个相当简单的匹配正则表达式。^ 和 $ 字 符分别表示字符串的开头和结尾，表达式 \d 表示数字字符，+ 指示将有一个或多个字符匹配 。我们使用 123456X 作为输入字符串测试此表达式。
此输入字符串很明显不是匹配项，因为 X 不是数字字符。但此示例正则表达式必须计算多 少个路径才能得出此结论呢？它会在此字符串开头处开始计算，发现字符 1 是一个有效的数字 字符，与此正则表达式匹配。然后它会移动到字符 2，该字符也匹配。因此，在此时，此正则 表达式与字符串 12 匹配。接下来，它会尝试 3（匹配 123），依次类推，直到到达 X，该字 符不匹配。
但是，由于我们的引擎是回溯 NFA 引擎，它不会在此点上停止。而是从其当前的匹配 (123456) 返回到其上一个已知的匹配 (12345)，然后从那里再次尝试匹配。由于 5 后面的下 一个字符不是此字符串的结尾，因此，此正则表达式不是匹配项，它会返回到其上一个已知的 匹配 (1234)，然后再次尝试匹配。按这种方式进行所有匹配，直到此引擎返回到其第一个匹配 (1)，发现 1 后面的字符不是此字符串的结尾。此时，正则表达式停止，没有找到任何匹配。
总的说来，此引擎计算了六个路径：123456、12345、1234、123、12 和 1。如果此输入字 符串再增加一个字符，则引擎会多计算一个路径。因此，此正则表达式是相对于字符串长度的 线性算法，不存在导致 DoS 的风险。对其模式使用 ^\d+$ 的 System.Text.RegularExpressions.Regex 对象计算速度非常快，足以迅速拆分计算大量输入字 符串（超过 10,000 个字符）。
现在，让我们更改此正则表达式，以对数字字符分组：
^(\d+)$