Title: Improving Developers' Understanding of Regex Denial of Service Tools through Anti-Patterns and Fix Strategies Show Chinese title

Title: 通过反模式和修复策略提高开发人员对正则表达式拒绝服务工具的理解

Abstract: 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. Show Chinese abstract

Abstract: 正则表达式被用于各种目的，包括输入验证和防火墙。 不幸的是，它们也可能导致一种称为ReDoS（正则表达式拒绝服务）的安全漏洞，这是由于正则表达式匹配期间的超线性最坏情况执行时间引起的。 由于ReDoS的严重性和普遍性，过去的工作提出了自动工具来检测和修复正则表达式。 尽管这些工具在自动实验中进行了评估，但它们的可用性尚未被研究；可用性并不是之前工作的重点。 我们的见解是，如果我们将现有的检测和修复正则表达式的工具与易受攻击的正则表达式的反模式和修复策略相结合，它们的可用性将得到改善。 我们开发了针对易受攻击正则表达式的新型反模式，并收集了一系列修复策略来修复它们。 我们的反模式和修复策略是从正则表达式无限歧义的新理论中推导出来的——这是正则表达式容易受到ReDoS攻击的必要条件。 我们证明了我们理论的正确性和完备性。 我们评估了我们的反模式的有效性，既在自动实验中，也手动应用时。 然后，我们评估了我们的反模式和修复策略在多大程度上提高了开发人员对检测和修复工具结果的理解。 我们的评估发现，在一个包含大量正则表达式的数据集（N=209,188）中，我们的反模式有效：100%的精确率和99%的召回率，比现有技术提高了50%的精确率和87%的召回率。 当手动应用时，我们的反模式也比现有技术更有效（N=20）：100%的开发人员有效地应用了它们，而现有技术为50%。 最后，我们的反模式和修复策略提高了使用自动工具的开发人员的理解力（N=9）：在检测漏洞时，从中位数“非常弱”提升到中位数“强烈”，在修复时从中位数“非常弱”提升到中位数“非常强烈”。