安全简报

  • 项目

正则表达式拒绝服务攻击和防御

Bryan Sullivan

在 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) 引擎。这两种引擎类型的完整差异分析超出本文范围，我们仅着重探讨以下两个方面：

  1. NFA 引擎是回溯引擎。与对输入字符串中的每个字符最多计算一次的 DFA 不同，NFA 引擎可以对输入字符串中的每个字符计算多次。（我将在稍后说明此回溯计算算法的计算原理。）回溯方法具有诸多优势，因为这些引擎可以处理更复杂的 正则表达式，如包含向后引用或捕获括号的正则表达式。它也具有一些缺点，因为其处理时间大大超过 DFA 的处理时间。
  2. 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+)$

这并不能从根本上改变这些计算的结果；它只是让开发人员获得任何作为捕获组的匹配。（此技巧在更复杂的正则表达式中很有用，在这些正则表达式中，您可能要应用重复运算符，但在此特殊情况下，它没有任何价值。）在此情况下，添加分组括号也不能从根本上改变此表达式的执行速度。针对输入 123456X 测试此模式仍然会导致此引擎仅计算六种不同的路径。但是，如果我们再对此正则表达式进行细微的更改，情况可能大为不同：

^(\d+)+$

分组表达式 (\d+) 后面额外的 + 字符表明此正则表达式引擎可匹配任何数量的捕获组。此引擎按以前的方式进行计算，在到达 123456 之后回溯到 12345。

这就是关键所在（因为存在非常可怕的危险）。此引擎不仅会检查到 5 后面的下一个字符不是此字符串的结尾，而且还会将下一个字符 6 作为新的捕获组，并从那里开始重新检查。一旦此途径失败，它会返回到 1234，将 56 作为单独的捕获组，然后将 5 和 6 分别作为单独的捕获组。最终结果是该引擎实际上完成了 32 个不同路径的计算。

现在，我们只要向此计算字符串再增加一个数字字符，该引擎将必须计算 64 个路径（翻了一倍）才能确定它不是匹配项。这会使正则表达式引擎执行的工作量呈指数增加。攻击者只要提供相对较短的输入字符串（30 个字符左右）就可强制引擎处理数亿个路径，所需时间多达几小时或几天。

将您的代码中的漏洞公之于众

如果某个应用程序在服务器端代码中加入了大量启用 DoS 的指数型正则表达式，则会有大麻烦。如果某个应用程序在客户端代码中显现其漏洞，那情况更糟。许多从 System.Web.UI.WebControls.BaseValidator 派生的 ASP.NET 验证器控件（包括 RegularExpressionValidator）都会自动在客户端上通过 JavaScript 执行验证逻辑，该验证逻辑与它们在服务器上通过 .NET 代码执行的验证逻辑相同。

大多数情况下，这是件好事。这有助于节省用户向服务器提交窗体和由于用户在输入字段中的错误键入导致验证器拒绝窗体所需的往返时间。这也有助于服务器节省处理时间。但是，如果此应用程序在其服务器代码中使用错误的正则表达式，则此错误的正则表达式也将用于其客户端代码中，这样，攻击者现在可非常容易地找到此正则表达式，并对其开发攻击字符串。

例如，假设我创建一个新的 Web 窗体，并将 TextBox 和 RegularExpressionValidator 添加到该窗体中。我将此验证器的 ControlToValidate 属性设置为文本框的名称，然后将其 ValidationExpression 设置为我们讨论的错误正则表达式：

this.RegularExpressionValidator1.ControlToValidate = "TextBox1";

this.RegularExpressionValidator1.ValidationExpression = @"^(\d+)+$";

现在，如果我在浏览器中打开此页面并查看其源代码，则可以在靠近页面底部的位置看到以下 JavaScript 代码：

<scripttype="text/javascript">

//< ![CDATA[

var RegularExpressionValidator1 = document.all ? 

  document.all["RegularExpressionValidator1"] : 

  document.getElementById("RegularExpressionValidator1");

RegularExpressionValidator1.controltovalidate = "TextBox1";

RegularExpressionValidator1.validationexpression = "^(\\d+)+$";

//]] >

</script>

这就让全世界都知道：脚本块的最后一行中明显存在指数型正则表达式。

更多有问题的模式

当然，^(\d+)+$ 不是世界上唯一的错误正则表达式。包含具有自我重复的重复性分组表达式的任何正则表达式基本上都容易受到攻击。这包括如下所示的正则表达式：

^(\d+)*$
^(\d*)*$
^(\d+|\s+)*$

另外，包含替换的任何组（其中，替换子表达式会相互覆盖）也容易受到攻击：

^(\d|\d\d)+$
^(\d|\d?)+$

如果您在代码中看到的表达式与上一示例类似，则您只要检查该表达式即可确定该表达式是否容易受到攻击。但在更长更复杂（并且实际上更为常见）的表达式中，您很可能会错过漏洞：

^([0-9a-zA-Z]([-.\w]*[0-9a-zA-Z])*@(([0-9a-zA-Z])+([-\w]*[0-9a-zA-Z])*\.)+[a-zA-Z]{2,9})$

这是在正则表达式库网站 (regexlib.com) 上找到的正则表达式，专用于验证电子邮件地址。但是，它也容易受到攻击。通过手动代码检查，您可能会找到此漏洞，也可能找不到此漏洞。要找出这些问题，需要使用更有效的技巧，这就是我们接下来要讨论的内容。

发现您的代码中错误的正则表达式

最理想的方法是在编译时查找代码中的指数型正则表达式，并向您发出相关警告。为了分析正则表达式字符串并分析它是否存在潜在弱点，您可能还需要另外一个正则表达式。在这点上，我就像一个正则表达式痴迷者：“我不需要帮助，我只需要更多的正则表达式”！但很遗憾，我的正则表达式技能无法编写一个正则表达式来分析这些正则表达式。如果您认为您有适用于此任务的有效代码，可以发送给我，我会很荣幸地在下个月的“安全简报”专栏中对您表示感谢。同时，由于我在编译时无法检测错误的正则表达式，因此，我将做另一件最有意义的工作：我将编写一个正则表达式模糊测试程序。

模糊测试是向应用程序的输入中提供格式错误的随机数据以尝试使应用程序运行失败的过程。您运行的模糊测试迭代次数越多，您发现错误的几率就越高，因此，团队通常都会对每个输入运行数千次或数百万次迭代。Microsoft 安全团队发现这是查找错误的有效可靠方法，因此，安全开发生命周期团队将模糊测试作为所有产品和服务团队的一项要求。

对于我的模糊测试程序，我要将随机输入字符串与我的正则表达式进行模糊测试。一开始，我将为我的正则表达式定义一个常量字符串、一个用于检查正则表达式的 testInputValue 方法和一个用于收集随机输入字符串以供 testInputValue 使用的 runTest 方法。

const string regexToTest = @"^(\d+)+$";



static void testInputValue(string inputToTest)

{

  System.Text.RegularExpressions.Regex.Match(inputToTest, regexToTest);

}



void runTest()

{

  string[] inputsToTest = {};



  foreach (string inputToTest in inputsToTest)

  testInputValue(inputToTest);

}

注意，还没有用于生成模糊测试输入值的代码；我将很快编写此代码。另请注意，此代码不会检查 Regex.Match 的返回值。这是因为我实际上并不在乎输入是否与此模式匹配。这种情况下，我在乎的是正则表达式引擎在确定输入是否匹配所花的时间是否过长。

通常，模糊测试程序用于尝试查找可利用的权限升级漏洞，但在此情况下，我仅对查找 DoS 漏洞感兴趣。我不能仅凭我的应用程序测试数据来证明应用程序是否崩溃；我必须能够检测到该应用程序是否被锁定。虽然这不是最科学的方法，但我可以通过对单独的工作线程按顺序运行每个正则表达式测试并为该线程设置完成超时值来有效完成此检测。如果线程没有在合理的时间内完成处理任务，比如测试单个输入需要五秒钟，则我们假定此正则表达式受到 DoS 攻击。我将添加一个 ManualResetEvent，并相应地修改 testInputValue 和 runTest 方法，如图 1 所示。

图 1 使用单独的工作线程进行测试

static ManualResetEvent threadComplete = new ManualResetEvent(false);



static void testInputValue(object inputToTest)

{

  System.Text.RegularExpressions.Regex.Match((string)inputToTest, 

    regexToTest);

  threadComplete.Set();

}



void runTest()

{

  string[] inputsToTest = {};



  foreach (string inputToTest in inputsToTest)

  {

    Thread thread = new Thread(testInputValue);

    thread.Start(inputToTest);



    if (!threadComplete.WaitOne(5000))

    {

      Console.WriteLine("Regex exceeded time limit for input " + 

        inputToTest);

      return;

    }



    threadComplete.Reset();

  }



  Console.WriteLine("All tests succeeded within the time limit.");

}

现在该是生成输入值的时候了。实际上，这件事情说起来容易做起来难。如果我生成的数据全部都是随机数据，则任何数据都不可能充分匹配正则表达式，因而无法找到漏洞。例如，如果我使用输入 XdO(*iLy@Lm4p$ 测试正则表达式 ^(\d+)+$，则此正则表达式将不会立即匹配，这样就会留下隐患。我需要生成与应用程序所需的内容相当接近的输入，才能对测试有用，因此，我需要一种用于生成与给定正则表达式匹配的随机数据的方法。

补救性数据生成计划

很幸运，Visual Studio 数据库项目中有一个专用于数据生成计划的功能。如果您使用 Visual Studio Team Suite，也可以访问此功能。数据生成计划用于快速使用测试数据填充数据库。它们可以使用随机字符串或数字值或与指定正则表达式匹配的字符串（幸好与我们的情况相符）来填充表。

您首先需要在 SQL Server 2005 或 2008 数据库中创建一个表，以便向其中生成测试数据。一旦生成表，请返回到 Visual Studio，并创建一个新的 SQL Server 数据库项目。编辑此数据库项目属性，并为其提供指向您的数据库的连接字符串。一旦输入了连接字符串并对其进行了测试以确保该字符串工作正常，请返回到“解决方案资源管理器”，并向此项目中添加新的“数据生成计划”项。此时，您应该看到类似图 2 的内容。


图 2 Visual Studio 中的“数据生成计划”项

现在，选择要使用模糊测试程序输入数据填充的表和列。在表部分，设置要生成的测试值数量（“要插入的行”列）。我在前面说过，模糊测试程序通常要测试数亿次迭代来尝试找出问题。虽然我一直认可此严格程度，但对于此正则表达式模糊测试程序却过于苛刻。如果打算锁定某个正则表达式，则可以在几百次测试迭代范围内实现锁定。我建议将“要插入的行”值设置为 200，但如果您要进行进一步的测试，可根据需要自由设置此值。

现在，在列部分中，可以将“生成器”设置为“正则表达式”，并在此列的“属性”选项卡中输入要作为“表达式”属性值进行测试的正则表达式模式值。请注意，不是所有的合法正则表达式字符都在“表达式”属性中受支持，这点很重要。您不能输入行开头和结尾定位符 ^ 和 $（或更准确地说，您可以输入这两个字符，但生成器将会在测试输入中生成字符 ^ 或 $）。可以不考虑这两个字符。您可在 msdn.microsoft.com/library/aa833197(VS.80) 中找到正则表达式生成器支持的运算符完整列表。

更严重的问题是，“表达式”属性还不支持常用的简化符号，如表示数字的 \d 或表示字符的 \w。如果您的正则表达式使用这些符号，则必须使用其等效字符类将其替换：[0-9] 代替 \d，[a-zA-Z0-9_] 代替 \w 等。如果需要替换 \s（空格字符），可以在其位置上输入一个空格。

数据库项目的最后一项任务实际上是根据您的指定使用测试数据填充数据库。可以通过选择“数据”|“数据生成器”|“生成数据”菜单项或按 F5 来完成此操作。

添加攻击

返回到模糊测试程序代码中，修改 runTest 方法，以便从数据库中提取生成的测试数据。此操作之后，您可能认为已完成任务了，但实际上还需要进行几项重要更改。如果您现在运行模糊测试程序，即使对已知错误的正则表达式（如 ^(\d+)+$），它也不能找出任何问题，但会报告所有测试都成功。这是因为您生成的所有测试数据是您的正则表达式的有效匹配。

记得我在前面说过，NFA 正则表达式引擎能够相当迅速地确定肯定匹配，只会在确定否定匹配时出现问题。并且，由于 NFA 的回溯特性，只会在输入开头处存在大量的匹配字符和结尾处出现错误字符时出现问题。如果输入字符串的前面部分中出现错误字符，则此测试会快速完成。

要对模糊测试程序代码进行的最后更改是将错误字符追加到测试输入结尾处。确保字符串数组包含数字、字母、标点符号和空格字符：

 

string[] attackChars = { "0", "1", "9", "X", "x", "+", 

"-", "@", "!", "(", ")", "[", "]", "\\", "/", 

"?", "<", ">", ".", ",", ":", ";", " ", "" };

现在修改此代码，这样，就会使用这些追加的每个攻击字符测试从数据库中检索的每个输入字符串。因此，系统会使用追加的 0 字符对第一个输入字符串进行测试，然后使用追加的 1 字符对其进行测试，依次类推。一旦使用每个攻击字符对输入字符串进行了测试，就会移到下一个输入字符串，然后使用每个攻击字符对其进行测试。

foreach (string inputToTest in inputsToTest)

{

  foreach (string attackChar in attackChars)

  {

    Threadthread = new Thread(testInputValue);

    thread.Start(inputToTest + attackChar);

...

实际上又引入了一个新的问题

前 Netscape 工程师 Jamie Zawinski 有句关于正则表达式的名言：

“有些人在遇到问题时会这么想，‘我知道，我将使用正则表达式解决此问题’，但实际上又引入了一个新的问题：正则表达式问题。”

虽然我不会像 Mr. Zawinski 一样对正则表达式持有那么多的批评意见，但我承认，要编写正确的正则表达式确实是一个很大的挑战，很少有能够安全抵御 DoS 攻击的正确的正则表达式。我建议您检查您的所有正则表达式中是否存在指数型复杂性，并使用模糊测试技巧验证您发现的问题。           

Bryan Sullivan* 是 Microsoft 安全开发生命周期团队的一名安全项目经理，专门负责 Web 应用程序和 .NET 的安全问题。他是“Ajax Security”（Addison-Wesley，2007）一书的作者。*

衷心感谢以下技术专家，感谢他们审阅了本文：Barclay Hill、Michael Howard、Ron Petrusha 和 Justin van Patten