论文标题
通过反模式提高开发人员对否决服务工具的理解并修复策略
Improving Developers' Understanding of Regex Denial of Service Tools through Anti-Patterns and Fix Strategies
论文作者
论文摘要
正则表达式用于各种目的，包括输入验证和防火墙。不幸的是，它们还可以导致一个称为REDOS（正则表达服务）的安全漏洞，这是由超级线性最差的案例执行时间在正则匹配期间引起的。由于重做的严重程度和流行率，过去的工作提出了自动工具来检测和修复正性。尽管这些工具在自动实验中进行了评估，但尚未研究它们的可用性。可用性不是先前工作的重点。我们的见解是，如果我们用反平底语和修复脆弱的言论的策略来补充现有工具来检测和修复正则发行的可用性。我们开发了针对弱势言论的新颖的反版社，并为解决方案提供了一系列修复策略。我们得出了反庞大的反对意见，并从一种新颖的无限歧义理论中确定了策略 - 这是易于重做的正性行为的必要条件。我们证明了理论的健全性和完整性。在自动实验和手动应用时，我们都评估了反模式的有效性。然后，我们评估了我们的反庞大和修复策略有多少改善了开发人员对检测和修复工具结果的理解。我们的评估发现，我们的抗模式在大的Regexes数据集（n = 209,188）中有效：100％精度和99％的召回，提高了最先进的状态50％的精度和87％的召回率。当手动应用时，我们的反模式也比最有效的（n = 20）更有效：100％开发人员有效地使用它们，而对于最新情况，则有效地使用了它们。最后，我们的反模式和修复策略使用自动工具（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.
