Регулярные выражения (regexes) широко используются в различных областях информатики. Однако уязвимость Regular expression Denial of Service (ReDoS) образует класс распространенных и серьезных атак алгоритмической сложности.
Существующие инструменты обнаружения ReDoS-уязвимостей имеют дефекты низкой точности или низкой скорости отзыва из-за отсутствия формальных и всеобъемлющих условий обнаружения ReDoS-уязвимостей.
Исследовательская группа во главе с проф. Чэнь Хаймин из Института программного обеспечения Китайской академии наук разработал высокопроизводительный инструмент обнаружения ReDoS-уязвимостей.
Их исследование было опубликовано на симпозиуме по безопасности USENIX 2021.
Изучив массивные РеДоС-уязвимые регексы, команда Чэня предложила условия обнаружения РеДоС-уязвимостей, а именно шаблоны РеДоС-уязвимостей, и дала необходимые условия для запуска этих шаблонов формально.
На основе этого они разработали статический и динамический комбинированный алгоритм обнаружения ReDoS-уязвимостей и разработали ReDoSHunter, инструмент обнаружения ReDoS-уязвимостей.
ReDoSHunter может определить несколько первопричин в уязвимом регулярном выражении, назначить степень уязвимости и создать строки, инициирующие атаку, и т. Д. Он достиг 100% точности и коэффициента отзыва на наборах данных Corpus, RegExLib и Snort с 37 651 regexes.
Обнаруживая публично подтвержденные практические уязвимости в Common Vulnerabilities and Exposure (CVE), ReDoSHunter может обнаружить 100% CVE, связанных с ReDoS.
В своем предыдущем исследовании команда Чэня предложила фреймворк программирования по примерам FlashRegex для генерации регулярных выражений anti-ReDoS путем синтеза или восстановления из заданных примеров. Это первый фреймворк, который интегрирует синтез и восстановление регулярных выражений с осознанием уязвимостей ReDoS.
FlashRegex может эффективно генерировать или восстанавливать регулярные выражения без ReDoS-уязвимостей, и в восстановленных регулярных выражениях есть 0 ReDoS-уязвимостей.
