Regular expressions (Regexp) are the fundamental text-processing tool for programmers. Ruby also has Regexp functions as the standard feature. Regexp is helpful, but it may cause some problems. The typical issue is ReDoS (Regular expression Denial of Service), a vulnerability in Regexp matching. When Regexp matching is implemented by back-tracking, a matching time could explode. This explosion overloads a service and makes it hard to provide the service. Such a DoS attack using Regexp matching is called ReDoS. For example, it caused damage to Cloudflare. Previous Ruby's Regexp implementation could cause ReDoS. In Ruby 3.2.0, Regexp matching has been optimized to prevent ReDoS. This optimization makes Regexp, which previously took exponential matching time, be matched in linear time. In this talk, I will describe a Regexp matching implementation and the details of the Regexp matching optimization implemented in Ruby 3.2.0.
Ph.D. student at SOKENDAI (NII, National Institute of Informatics). Researcher for information security and formal language. Ruby committer. I am the author of Regexp optimization to prevent ReDoS in Ruby 3.2.0.