一句话：提出三阶段灰盒分析技术，自动生成最大化匹配时间的 ReDoS 攻击字符串。
现代正则表达式被广泛用于字符串处理，但设计不当的正则可能产生指数级匹配步骤，在精心构造的输入下导致正则表达式拒绝服务（ReDoS）攻击。本文提出 ReScue，一种三阶段灰盒分析技术，用于自动生成能够暴露给定正则漏洞的 ReDoS 字符串。ReScue 依次通过遗传搜索进行播种、再次通过遗传搜索进行孵化，并最终利用正则专用算法进行泵送，从而生成搜索时间最大化的字符串。作者实现了 ReScue 工具，并在真实项目中的 29,088 个实用正则上进行了评估。结果表明，与当时最佳现有技术相比，ReScue 多发现 49% 的攻击字符串，并将其应用于流行 GitHub 项目后发现了十个此前未知的 ReDoS 漏洞。
Regular expression (regex) with modern extensions is one of the most popular string processing tools. However, poorly-designed regexes can yield exponentially many matching steps, and lead to regex Denial-of-Service (ReDoS) attacks under well-conceived string inputs. This paper presents Rescue, a three-phase gray-box analytical technique, to automatically generate ReDoS strings to highlight vulnerabilities of given regexes. Rescue systematically seeds (by a genetic search), incubates (by another genetic search), and finally pumps (by a regex-dedicated algorithm) for generating strings with maximized search time. We implemenmted the Rescue tool and evaluated it against 29,088 practical regexes in real-world projects. The evaluation results show that Rescue found 49% more attack strings compared with the best existing technique, and applying Rescue to popular GitHub projects discovered ten previously unknown ReDoS vulnerabilities.
DOI 原文 ·
@inproceedings{paperbot4750,
title = {ReScue: crafting regular expression DoS attacks},
author = {Yuju Shen and Yanyan Jiang and Chang Xu and Ping Yu and Xiaoxing Ma and Jian Lu},
booktitle = {ASE},
year = {2018},
doi = {10.1145/3238147.3238159}
}