Rethinking Regex engines to address ReDoS
Rethinking Regex engines to address ReDoS
复制标题
重新思考正则表达式引擎以解决 ReDoS 问题
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
James C. Davis
中科院分区：
文献类型：
--
作者：
James C. Davis
正则表达式（regexes）是一个强大的字符串操作工具。不幸的是，在 Python、Java 和 JavaScript 等编程语言中，它们是不必要的危险，是通过最坏情况的指数匹配行为实现的。这种高时间复杂性使软件服务容易遭受正则表达式拒绝服务 (ReDoS) 攻击。我们建议对正则表达式引擎进行数据驱动的重新设计，以反映正则表达式的使用方式及其通常的外观。我们报告说，流行编程语言中大约 95% 的正则表达式可以在线性时间内进行评估。正则表达式引擎是编程语言的基本组件，任何更改都有可能引入兼容性问题。因此，我们认为完全重新设计是不切实际的，因此我们描述了如何通过对现有算法进行较小而非主要的更改来实现绝大多数正则表达式匹配的线性时间。我们的原型表明，在正则表达式语言的内核上，我们可以用空间换时间来使正则表达式匹配安全
Regular expressions (regexes) are a powerful string manipulation tool. Unfortunately, in programming languages like Python, Java, and JavaScript, they are unnecessarily dangerous, implemented with worst-case exponential matching behavior. This high time complexity exposes software services to regular expression denial of service (ReDoS) attacks. We propose a data-driven redesign of regex engines, to reflect how regexes are used and what they typically look like. We report that about 95% of regexes in popular programming languages can be evaluated in linear time. The regex engine is a fundamental component of a programming language, and any changes risk introducing compatibility problems. We believe a full redesign is therefore impractical, and so we describe how the vast majority of regex matches can be made linear-time with minor, not major, changes to existing algorithms. Our prototype shows that on a kernel of the regex language, we can trade space for time to make regex matches safe
DOI：
10.1145/3236024.3236072
发表时间：
2018-10
期刊：
Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering
影响因子：
--
作者：
Peipei Wang;Kathryn T. Stolee
通讯作者：
Peipei Wang;Kathryn T. Stolee