ReDoS检测、修复系统

1. 成果简介

正则表达式拒绝服务（ReDoS）攻击是一种通过利用正则表达式引擎在处理特定恶意输入时的性能缺陷而实施的非对称拒绝服务（DoS）攻击。此类攻击通过触发正则引擎的超线性匹配复杂度，从而消耗大量系统资源，导致拒绝服务。现有的工作主要分为针对回溯引擎和非回溯引擎的ReDoS检测方法。

在针对回溯引擎ReDoS检测工作上，现有的方法主要利用静态或者是动态的方法来进行检测，然而静态方法很难完全建模现实正则引擎的匹配过程，导致会出现大量的误报，动态方法虽然能够模拟引擎的匹配过程，但是由于搜索空间的庞大导致其饱受低效率的困扰。

针对上述的现状，我们提出首个动静态混合的ReDoS检测方法（如图一所示），该方法设计提出了最为全面的ReDoS漏洞模式，并形式化地给出了触发这些模式的必要条件，其工具ReDoSHunter通过分析正则表达式的语法树以及Glushkov映射集合间的关系识别可能导致ReDoS的模式，接着定位可重复的可泵子串以及前后缀以生成攻击串，最后在正则引擎中执行该攻击串以测量匹配时间验证ReDoS是否存在。

图 1 ReDoSHunter的概览

在检测ReDoS漏洞数量方面，ReDoSHunter超越现有最先进工具，在Corpus,RegExLib,Snort三个大型数据集（共计37651个正则表达式）上实现了100%的准确率和召回率。在检测ReDoS漏洞相关的CVEs（Common Vulnerabilities and Exposures通用漏洞披露）方面，ReDoSHunter能成功检测出100%的CVEs。此外，ReDoSHunter 的应用对于寻找、纠正广大的开源社区的ReDoS漏洞发挥了重大作用。该工具已应用在Python源码、CKEditor和prismjs等开源项目的ReDoS漏洞检测中。同时，该团队与知名安全公司Snyk建立了长期的合作关系，共同致力于高效披露ReDoS漏洞。在已发现的200多个尚未被披露的漏洞中，截至目前已获批了27个CVEs, 并收到多个项目的官方致谢。 

现有ReDoS检测方法在生成被拒绝串（Rejected Strings）、利用无穷歧义（Infinite Ambiguity）与考虑匹配函数等方面存在显著不足。本课题组提出一种新型ReDoS攻击串——“正则表达式的无穷歧义见证串”（Witness for Infinite Ambiguity,WIA），它是一种能证明并利用正则表达式无穷歧义的被拒绝串。每个见证串均对应正则表达式的有穷自动机上的一对见证状态。为有效求解正则表达式无穷歧义见证串问题，我们开发了检测工具Grewia，该工具使用两种技术：(1) 增量式算法：快速生成最短见证串，用于检验漏洞的存在性，并定位见证状态；(2) 减量式算法：减量式构造任意两见证状态对应的自动机，用于生成随机攻击串以绕过响应式防御系统。实验结果显示，Grewia在检测效果和绕过防御能力上均显著优于6种SOTA工具，已在86个流行项目中发现63个新漏洞，其中17个漏洞收到开发者的确认和1个获得了CVE编号。

图 2 Grewia的概览

现有工作主要集中于研究正则级别的ReDoS检测，而忽略了正则在程序中的上下文关系，我们提出了程序级别的ReDoS检测技术，其工具ReDSE（如图2所示）先将输入的代码进行切片即将与正则无关的代码消去，紧接着执行动态符号提取程序的约束，之后将提取到的约束和ReDoS漏洞的检测约束结合起来，并送进求解器中求解，最后得到相应的攻击串。我们将该工具应用在github中前3500高星开源项目中，在103个项目中确定了93个零日ReDoS漏洞，其中30个已获得CVE编号，展示出了我们工具在现实场景中的高有效性。

图 3 ReDSE的概览

大部分ReDoS检测工作主要集中在针对回溯引擎上，甚至有工作认为非回溯引擎可以消除ReDoS漏洞的风险，尽管已有工作GadgetCA设计实验说明使用此运算符的正则表达式可能会导致非回溯引擎上的ReDoS攻击，但其采用的模型仅在一类语法层面上受限的正则表达式上有效，适用性极为有限，这使得非回溯引擎的ReDoS漏洞的成因与有效检测仍然是一个开放问题。针对上述现状，课题组提出k-简单串问题建模非回溯引擎的ReDoS检测问题，并证明了其复杂性的上下界。利用课题组提出的k-简单串问题的增量判定算法，课题组设计了非回溯引擎ReDoS漏洞检测工具EvilStrGen（如图二所示）。EvilStrGen首先预处理输入的正则表达式、引擎、匹配函数类型等信息，然后通过k-简单串求解器逐字节生成攻击字符串，并应用两种高效的搜索策略优化这一过程。为了进一步提高效率，当搜索遇到超过给定阈值的冲突时，采用非时序回溯策略来约减状态空间。如果攻击串长度未达k，检测器重复调用k-简单串求解器并拼接到先前结果。最终生成的字符串根据引擎、匹配函数送入验证阶段，通过验证器判定是否存在漏洞。

图 4 EvilsStrGen的概览

在非回溯引擎ReDoS检测上，实验结果表明EvilStrGen在非回溯引擎和回溯引擎的ReDoS检测上展现出先进的检测能力。此外Hyperscan在GadgetCA文中认为无懈可击，然而我们找到了2,327个可能触发Hyperscan的ReDoS漏洞的正则。我们还将我们的工具应用于85个现实项目，并确定了34个未披露的ReDoS漏洞。

正则表达式以难以掌握著称，其现有的自动化合成与修复工作均忽略了ReDoS漏洞，使其结果可能受到该漏洞的攻击。 我们提出了首个抗ReDoS漏洞正则表达式的合成与修复算法，其通过去除正则表达式的歧义来生成或修复出无ReDoS漏洞的正则表达式。为加速合成和修复过程，团队使用了确定性自动机和局部约束加强启发式策略，并且设计实现了相应的工具——FlashRegex （如图三所示）。 该工具已应用到实际开源项目中修复ReDoS漏洞，得到postccs、nltk和Python源码等十多个项目维护者及知名安全公司Snyk的一致认可或致谢。

图 5 FlashRegex的概览

更进一步地，为了使ReDoS修复不仅仅局限于给定的示例。我们提出RegexScalpel，该工具通过高效的自动化方式定位病理性因子，从而修复ReDoS漏洞，并在修复后能保留原正则表达式语义。

图 6 RegexScalpel的概览

通过对448个易受攻击的正则表达式设计了一系列实验，我们发现，相较于现有最佳的自动正则修复技术，RegexScalpel可以多修复348个正则表达式。此外，我们采用RegexScalpel检测了包括Python和NLTK在内的10个热门项目，并发现了16个易受攻击的正则表达式。然后我们应用RegexScalpel成功地修复了所有的漏洞，这些修复被维护者合并到后来的版本中，产生了8个已确认的CVE。

2. 技术先进性

该系统先进性主要体现在以下方面：

   （1）ReDoS 检测方面：

    回溯引擎检测：首次提出了基于ReDoS漏洞模式的动静态结合的 ReDoS 检测技术；设计了首个利用无穷歧义见证串的高效 ReDoS 检测算法；并提出了针对程序级别 ReDoS 的先进检测方法。