Improving Developers’ Understanding of Regex Denial of Service Tools through Anti-Patterns and Fix Strategies
Improving Developers’ Understanding of Regex Denial of Service Tools through Anti-Patterns and Fix Strategies
复制标题
DOI：
10.1109/sp46215.2023.10179442
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Sk Adnan Hassan;Zainab Aamir;Dongyoon Lee;James C. Davis;Francisco Servant
中科院分区：
文献类型：
--
作者：
Sk Adnan Hassan;Zainab Aamir;Dongyoon Lee;James C. Davis;Francisco Servant
正则表达式用于各种目的，包括输入验证和防火墙。不幸的是，它们还可能导致称为ReDoS（正则表达式拒绝服务）的安全漏洞，这是由正则表达式匹配期间的超线性最坏情况执行时间引起的。由于ReDoS的严重性和普遍性，过去的工作建议使用自动工具来检测和修复正则表达式。虽然这些工具在自动实验中进行了评估，但它们的可用性尚未得到研究；可用性并不是之前工作的重点。我们的见解是，如果我们用反模式和修复易受攻击的正则表达式的策略来补充现有工具，那么检测和修复正则表达式的可用性将得到改善。我们为易受攻击的正则表达式开发了新的反模式，并开发了一组修复策略来修复它们。我们的反模式和修复策略来自于正则表达式无限模糊的新理论——这是易受ReDoS攻击的正则表达式的必要条件。我们证明了我们理论的正确性和完整性。我们评估了反模式的有效性，包括在自动实验和手动应用时。然后，我们评估了我们的反模式和修复策略在多大程度上提高了开发人员对检测和修复工具的结果的理解。我们的评估发现，我们的反模式在一个大型正则表达式数据集（N=209,188）上是有效的：100%的准确率和99%的召回率，提高了50%的准确率和87%的召回率。我们的反模式在手动应用时也比目前的技术水平更有效（N=20）： 100%的开发人员有效地应用了它们，而在目前的技术水平上，只有50%的开发人员有效地应用了它们。最后，我们的反模式和修复策略增加了开发人员使用自动工具的理解（N=9）：在检测漏洞时，从中间值“非常弱”到中间值“强”，在修复漏洞时，从中间值“非常弱”到中间值“非常强”。
Regular expressions are used for diverse purposes, including input validation and firewalls. Unfortunately, they can also lead to a security vulnerability called ReDoS (Regular Expression Denial of Service), caused by a super-linear worst-case execution time during regex matching. Due to the severity and prevalence of ReDoS, past work proposed automatic tools to detect and fix regexes. Although these tools were evaluated in automatic experiments, their usability has not yet been studied; usability has not been a focus of prior work. Our insight is that the usability of existing tools to detect and fix regexes will improve if we complement them with anti-patterns and fix strategies of vulnerable regexes.We developed novel anti-patterns for vulnerable regexes, and a collection of fix strategies to fix them. We derived our anti-patterns and fix strategies from a novel theory of regex infinite ambiguity — a necessary condition for regexes vulnerable to ReDoS. We proved the soundness and completeness of our theory. We evaluated the effectiveness of our anti-patterns, both in an automatic experiment and when applied manually. Then, we evaluated how much our anti-patterns and fix strategies improve developers’ understanding of the outcome of detection and fixing tools. Our evaluation found that our anti-patterns were effective over a large dataset of regexes (N=209,188): 100% precision and 99% recall, improving the state of the art 50% precision and 87% recall. Our anti-patterns were also more effective than the state of the art when applied manually (N=20): 100% developers applied them effectively vs. 50% for the state of the art. Finally, our anti-patterns and fix strategies increased developers’ understanding using automatic tools (N=9): from median "Very weakly" to median "Strongly" when detecting vulnerabilities, and from median "Very weakly" to median "Very strongly" when fixing them.