KDOC 707: Rubyの正規表現は後方参照があるとメモ化が効かず指数的に遅くなることがある

• 作成
  • <署名>

• レビュー
  • <署名>

正規表現は、パターンと入力によってはバックトラックが爆発し、入力の長さに対して指数的に遅くなる。信頼できない入力を食わせるとサービス停止(ReDoS)になりうる。Ruby 3.2からは多くのパターンがメモ化で線形時間になったが、後方参照を含むパターンなどは対象外で、 Regexp.linear_time? で確かめられる。対象外のパターンには Regexp.timeout で上限を付ける。

puts "後方参照なし: #{Regexp.linear_time?(/\A(a|a)*\z/)}、後方参照あり: #{Regexp.linear_time?(/\A(a|a)*\1\z/)}"
[20, 22, 24].each do |n|
  t = Time.now
  /\A(a|a)*\1\z/.match?("a" * n + "b")
  printf("後方参照あり、%d文字: %.3f秒\n", n, Time.now - t)
end

後方参照なし: true、後方参照あり: false
後方参照あり、20文字: 0.030秒
後方参照あり、22文字: 0.108秒
後方参照あり、24文字: 0.445秒

2文字増えるたびに時間は約4倍になる。30文字の入力1つで数十秒止まる計算である。 Regexp.timeout を付けておけば、そこで打ち切れる。

Regexp.timeout = 1.0
t = Time.now
begin
  /\A(a|a)*\1\z/.match?("a" * 30 + "b")
rescue Regexp::TimeoutError => e
  printf("後方参照あり、30文字: %.1f秒で %s\n", Time.now - t, e.class)
end

後方参照あり、30文字: 1.0秒で Regexp::TimeoutError

Returns true if matching against re can be done in linear time to the input string.

Regexp.linear_time? - Ruby 3.4

The cache-based optimization is introduced. Many (but not all) Regexp matching is now in linear time, which will prevent regular expression denial of service (ReDoS) vulnerability.

NEWS for Ruby 3.2.0 (Regexp)

When either a regexp source or a target string comes from untrusted input, malicious values could become a denial-of-service attack; to prevent such an attack, it is wise to set a timeout.

Regexp (Timeouts) - Ruby 3.4

なし。