Web应用中的ReDoS检测方法研究

梁兴开，赵泽茂，黄 亮

(杭州电子科技大学通信工程学院，浙江杭州310018)

0 引言

正则表达式大量应用于Web应用中，其在表单数据校验、替换和文本处理中发挥灵活而又强大的功能［1］。而拒绝服务攻击通过向目标发送大量的攻击数据包来消耗目标的资源，这类攻击通常被称为数据包洪泛攻击。由于不合理的正则表达式语句大量部署于Web应用中，这将可能引入一种新型的拒绝服务攻击－正则表达式拒绝服务攻击(Regular Expression Deny of Service，ReDoS)［3］。由于采用不严谨的正则表达式而对其可能造成的危害了解甚少，开发者无法对Web应用中构建的正则表达式语句进行安全验证，不轻易间就可能导致系统受到拒绝服务攻击。因此，研究一种能够有效检测和抵御ReDoS攻击的检测模型是迫切的现实需要，本文提出了一种基于静态代码分析与渗透测试技术的防御ReDoS模型。

1 相关背景

正则表达式描述一种字符串匹配模式，一般其运用于两种情况:一种是在文本或字符串中查找特定的子串(搜索、匹配);另一种是查找符合特定条件的子串并编辑子串(替换、校验)。

1.1 正则表达式设计

正则表达式的语法由基本的元字符、数量和位置元字符、特殊元字符以及一些条件模式字符构成。具体的语法要点可参考文献1。Web应用中一般需要校验电子邮件的合法性，可以构建如下的正则表达式:w+(［－ +.′］w+)*@w+(［－.］w+)*.w+(［－.］w+)* 。这个模式使用的嵌套子表达式模式。

1.2 ReDoS 攻击原理

正则表达式匹配技术主要有基于非确定性有限状态机(Nondeterministic Finite Automaton，NFA)的技术、基于确定性有限状态机(Deterministic Finite Automaton，DFA)的匹配技术、基于NFA和DFA的混合技术［4－6］。许多Web开发环境都是基于NFA实现正则表达式的。基于NFA引擎是回溯引擎，可以处理更复杂的正则表达式，比如前后向引用和捕获括号的正则表达式等。与对输入字符串中的每个字符最多计算一次的DFA不同，NFA跳转到新的状态并对输入字符串中的字符计算多次，直到所有的输入符号都消费完。它检验每一个可能的路径直到它到达可接受的状态(成功匹配)或者检验完所有的路径(匹配失败)。这意味着必须对所有路径进行测试。回溯的一个负面影响是，虽然正则表达式可以快速地确定正向匹配(输入字符串与给定正则表达式匹配)，但确定反向匹配(输入字符串与正则表达式不匹配)所需的时间更长。这将导致正则表达式引擎的执行计算量呈现指数增加。攻击者只需提供简单的构造好的语句就可强制NFA引擎对所有可能的大量的路径进行匹配尝试直到不成功匹配，即可造成ReDoS攻击。

通过分析发现，不严谨的正则表达式一般包含以下两个要点:(1)包含重复捕获分组;(2)在重复捕获分组中包含替换或者重复匹配现象。而这两个要点也是防范ReDos攻击的检测模型中的静态分析模块的核心。其执行的路径复杂度就由引擎的路径匹配时间来表示并将消耗的匹配时间作为渗透测试模块中的一个判决条件。

2 ReDoS攻击的检测模型

构造完全健壮的正则表达式是比较困难的。一个原因是目前还没有合适的工具来验证开发者使用的正则表达式的严谨性。因此，本文构建一个安全的检测模型，由静态分析模块和渗透测试模块两部分构成。静态测试模块主要完成对可疑式子的定义和Web源代码的分析，并提取网页源代码中的正则表达式。渗透测试模块主要完成对静态模块获取到的正则表达式进行模糊测试并给出相应的防护措施。模型如图1所示。

图1 ReDoS检测模型

2.1 ReDoS静态分析模块

静态分析模块主要负责抓取网页源代码中所有的正则表达式，并依据可疑特征库来提取所有可疑正则表达式集合。此模块的关键部分是对可疑正则表达式的定义，因为其提取到的正则表达式集准确与否将直接影响测试模块。为了减少漏报，本模块将可疑正则表达式定义成如下:任何包含重复分组或者替换的正则表达式R称为可疑表达式，标记为Rs。Web源代码中的正则表达式一般都会包含特定的字符(比如“+”、“*”、“?”)，静态分析模块只需提取并筛选出所有可疑的正则表达式Rs，整合成可疑正则表达式集Rs－。

2.2 ReDoS 测试模块

测试模块中用到的关键的符号和数据如下:Tout为渗透测试中匹配测试设定的时间阀;T为对Rs进行匹配测试所消耗的时间。人工测试库:在模块中人工的自定义一些攻击测试用例，能够比较快速而有针对性的对可疑正则表达式Rs进行测试。将数字、字母和一些常见的特殊字符组合成人工的测试数据。随机测试库:用于产生大量的随机测试数据，对可疑正则表达式集合Rs－进行模糊测试。测试数据主要为随机的数字、字符或两者的组合等。攻击字符库:将攻击字符叠加到随机产生的测试数据之后，在反向匹配测试进行尽可能多的模糊测试。字符库包含数字、字母、标点符号、特殊符号和非可打印的ASICC字符等。

渗透测试模块的功能是对正则表达式集Rs－进行模糊测试，验证其严谨性，评判Rs是否容易导致拒绝服务攻击。此模块的一个判决因素是反向匹配时间T。如果正则表达式不能在特定的时间内完成匹配，即可被认定为不严谨的正则表达式。本模块设定Tout为1s。模块提供测试数据来计算反向匹配时间，并以此作为Rs的严谨性判决依据。测试分为2步:第1步是人工提供的测试数据，用于更快捷的检测可疑正则表达式Rs;第2步是机器自动化的模糊测试。自动化模糊测试需要随机产生大量的测试数据。如果提供的测试数据的开始部分就包含不符合正则表达式的匹配项，NFA引擎可以很容易的搜索完路径而直接拒绝测试数据，可疑正则表达式Rs就无法得到合理检测。因此，需人为的在随机测试数据后面叠加上特殊的攻击字符来组合成一系列的测试用例。渗透测试模块的具体流程图如图2所示。

图2 测试流程图

3 实例分析

人工选取了几个Web应用中常用的正则表达式来进行严谨性试验，待测试的用例来自于开源社区，测试的度量为正则引擎匹配的时间。在.NET环境下进行了初步测试，结果如表1所示。

表1 检测实例与用时

在软件测试过程中，程序被随机产生的数据大量验证，称为模糊测试。如果程序在应对这类数据上失效，开发者就知道程序某处出现了Bug。本文使用了模糊测试方法来验证正则表达式的安全性。在数据校验和过滤定义中，所使用的正则表达式必定是常规的ASCII字符组合，也就是数字、字母和常用的符号组合。在构造和选取测试数据时，如果提供地数据完全是常规的ASCII字符，则很容易经过正向匹配测试得出不合理的测试结果。而针对具体的正则式子将常规字符、特殊字符、非打印ASCII字符等组合成多个测试数据，按照模糊测试的思想，通过不断地反向匹配和迭代测试，最后得出比较合理的测试结果。

4 结束语

本文提出了防范正则表达式拒绝服务攻击的检测模型，通过静态分析和渗透测试方法对Web应用程序中的正则表达式的严谨性进行模糊测试，给出了本模块的检测算法和初步的测试数据。实例表明，引擎匹配的时间可以作为一个判断度量，可以通过模糊测试来校验正则表达式的严谨性。在使用正则表达式时需要遵循以下2点:(1)接受已知的合法数据，太过严格的正则表达式有可能产生误报;(2)拒绝已知的非法数据，太过松散的正则表达式会产生漏报。

［1］ Jeffrey E F.精通正则表达式［M］.北京:电子工业出版社，2006:143－162.

［2］ Skoudies E d.反击黑客［M］.北京:机械工业出版社，2002:120－170.

［3］ Adar Weidman.基于源代码分析保护应用程序的安全［EB/OL］.http://www.checkmarx.com/NewsDetails.aspx?id=23＆cat=3，2009 －10 －09.

［4］ Yuan M，袁真.构造正则表达式的几种NFA算法分析与比较［J］.计算机科学，2006，33(8):212－214.

［5］ 周启海.NFA→FA→GFA自动机转换算法［J］.电子科技大学学报，2005，34(3):363－365.

［6］ 徐克付，齐德昱，郑伟平，等.一种基于Bloom Filter的正则表达式集合快速搜索算法［J］.华南理工大学学报，2009，37(4):37－41.