Repairing DoS Vulnerability of Real-World Regexes

Nariyoshi Chida, Tachio Terauchi

研究成果: Conference contribution

3 被引用数 (Scopus)


There has been much work on synthesizing and repairing regular expressions (regexes for short) from examples. These programming-by-example (PBE) methods help the users write regexes by letting them reflect their intention by examples. However, the existing methods may generate regexes whose matching may take super-linear time and are vulnerable to regex denial of service (ReDoS) attacks. This paper presents the first PBE repair method that is guaranteed to generate only invulnerable regexes. Importantly, our method can handle real-world regexes containing lookarounds and backreferences. Due to the extensions, the existing formal definitions of ReDoS vulnerabilities that only consider pure regexes are insufficient. Therefore, we first give a novel formal semantics and complexity of backtracking matching algorithms for real-world regexes, and with them, give the first formal definition of ReDoS vulnerability for real-world regexes. Next, we present a novel condition called real-world strong 1-unambiguity that is sufficient for guaranteeing the invulnerability of real-world regexes, and formalize the corresponding PBE repair problem. Finally, we present an algorithm that solves the repair problem. The algorithm builds on and extends the previous PBE methods to handle the realworld extensions and with constraints to enforce the real-world strong 1-unambiguity condition.

ホスト出版物のタイトルProceedings - 43rd IEEE Symposium on Security and Privacy, SP 2022
出版社Institute of Electrical and Electronics Engineers Inc.
出版ステータスPublished - 2022
イベント43rd IEEE Symposium on Security and Privacy, SP 2022 - San Francisco, United States
継続期間: 2022 5月 232022 5月 26


名前Proceedings - IEEE Symposium on Security and Privacy


Conference43rd IEEE Symposium on Security and Privacy, SP 2022
国/地域United States
CitySan Francisco

ASJC Scopus subject areas

  • 安全性、リスク、信頼性、品質管理
  • ソフトウェア
  • コンピュータ ネットワークおよび通信


「Repairing DoS Vulnerability of Real-World Regexes」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。