#7 Ruby 3.2.0 のReDoSに対する正規表現の改善を試してみる

Ruby 3.2.0 リリース

昨年末12月25日にRubyの3.2.0がリリースされました。今回の主な改善はWebAssemblyサポートと正規表現の改善でしたが本記事では正規表現に関してどのような改善が行われたかまとめてみました。リリースノートによると改善内容は

Regexpのマッチングアルゴリズムの改善
Regexpのタイムアウトの導入

の二つになりますが、どちらもReDoSに対する対策になります。

ReDoSとは

そもそもReDoSとは、何だぁ～～？ということですが、 Regular expression Denial of Serviceの省略で、こちらのページによると

The Regular expression Denial of Service (ReDoS) is a Denial of Service attack, that exploits the fact that most Regular Expression implementations may reach extreme situations that cause them to work very slowly

とあり、極端な文字列のマッチングで計算リーソースが過剰に消費されることを悪用した攻撃のことを指します。

Regexpのマッチングアルゴリズムの改善

起票されたチケットはこちら。内容を深堀するとオートマトンなどを説明しないといけないのですがここでは割愛（というか説明できない）。具体的にどのように動きが変わったか実際のコードで見ていきます。実行コードはこちらのQiitaの記事を参考にしています。 ReDoSの説明もあるのでもし興味があれば読んでみてください。

以下、実行時の引数のマッチングをテストするスクリプトで実行時間を見ていきます。

> cat regex01.rb 
re = /^(([a-zA-Z0-9])+)+$/

str = ARGV[0]
puts "INPUT: #{str}"

start_time = Time.now

str.match(re) { |match| puts "MATCHED" if match }
puts "RUNNING TIME: #{Time.now - start_time}[s]"

Rubyのバージョンが3.1.3の場合

Rubyのバージョンを確認。

> ruby -v
ruby 3.1.3p185 (2022-11-24 revision 1a6b16756e) [arm64-darwin21]

マッチする文字列をテストする。実行時間は約4秒。

> ruby regex01.rb abcdef                           
INPUT: abcdef
MATCHED
RUNNING TIME: 4.0e-06[s]

次にマッチングしない文字列をテストする。実行時間は約93秒。このような文字列が極端に長くなるとリソースを消耗してしまう。

> ruby regex01.rb AbCdEfGh1JkLmN0pQR5TuAbCdEfGh1Jk@
INPUT: AbCdEfGh1JkLmN0pQR5TuAbCdEfGh1Jk@
RUNNING TIME: 93.541195[s]

Rubyのバージョンが3.2.0の場合

次に3.2.0で同じパターンを試す。

> ruby -v
ruby 3.2.0 (2022-12-25 revision a528908271) [arm64-darwin21]
> ruby regex01.rb abcdef  
INPUT: abcdef
MATCHED
RUNNING TIME: 4.0e-06[s]
> ruby regex01.rb AbCdEfGh1JkLmN0pQR5TuAbCdEfGh1Jk@
INPUT: AbCdEfGh1JkLmN0pQR5TuAbCdEfGh1Jk@
RUNNING TIME: 5.0e-06[s]

同じ文字列でもパターンの解析時間が大幅に短縮している。このように実行時間の短縮＝リソースの消耗を防ぐことでReDoS攻撃の対策を行っている。

Regexpのタイムアウトの導入

次に正規表現のタイムアウトに関して確認する。起票されたチケットはこちら。

先ずはタイムアウト無しで検証

上記スクリプトを改良してマッチする文字列をテストする。

> cat regex02.rb       
TIMES=50000000.freeze # Integer

re = /^(([a-zA-Z0-9])+)+$/

str = ARGV[0]  # Command line argument
puts "INPUT: #{str} * #{TIMES}"

start_time = Time.now

target = str * TIMES

begin
  target.match(re) { |match| puts "MATCHED" if match }
ensure
  puts "RUNNING TIME: #{Time.now - start_time}[s]"
end

実行時間は約4秒。

projects/ruby-test  > ruby regex02.rb abcdef
INPUT: abcdef * 50000000
MATCHED
RUNNING TIME: 4.065616[s]

`Regexp.timeout` を設定して検証。

> cat regex02.rb        
TIMES=50000000.freeze # Integer
TIMEOUT=1.0 # Float

Regexp.timeout = TIMEOUT

re = /^(([a-zA-Z0-9])+)+$/

str = ARGV[0]  # Command line argument
puts "INPUT: #{str} * #{TIMES}"

start_time = Time.now
target = str * TIMES

begin
  target.match(re) { |match| puts "MATCHED" if match }
ensure
  puts "RUNNING TIME: #{Time.now - start_time}[s]"
end

処理時間約1秒で Regexp::TimeoutError が発生する。

projects/ruby-test  > ruby regex02.rb abcdef
INPUT: abcdef * 50000000
RUNNING TIME: 1.023424[s]
regex02.rb:17:in `match': regexp match timeout (Regexp::TimeoutError)
    from regex02.rb:17:in `match'
    from regex02.rb:17:in `<main>'

正規表現オブジェクトに個別でタイムアウトを設定して検証。

> cat regex02.rb 
TIMES=50000000.freeze # Integer
TIMEOUT=1.0 # Float

Regexp.timeout = TIMEOUT

re = Regexp.new('^(([a-zA-Z0-9])+)+$', timeout: 2.0)

str = ARGV[0]  # Command line argument
puts "INPUT: #{str} * #{TIMES}"

start_time = Time.now

target = str * TIMES

begin
  target.match(re) { |match| puts "MATCHED" if match }
ensure
  puts "RUNNING TIME: #{Time.now - start_time}[s]"
end

全体のタイムアウトは1秒で設定されているが、処理時間約2秒で Regexp::TimeoutError が発生する。

projects/ruby-test  > ruby regex02.rb abcdef
INPUT: abcdef * 50000000
RUNNING TIME: 2.023538[s]
regex02.rb:17:in `match': regexp match timeout (Regexp::TimeoutError)
    from regex02.rb:17:in `match'
    from regex02.rb:17:in `<main>'