末尾の連続する改行文字を削除する

文字列が格納されている変数 str から、末尾の連続する改行文字を削除しようとして次のようなコードを書いた（言語：Ruby）。

str.sub(/(\r\n|\r|\n)+\z/, "")

本コードには問題がある。

1. 問題点を指摘せよ。
2. 改善案を提案せよ。

とだけ書いて、答えられる人はどのくらいいるだろうか。これは別に筆記試験というわけではない。手元に Ruby 実行環境があるなら様々な入力で試してみて欲しい。もちろん Web を検索してみても良い。

一見なんの変哲もない一行のコードだが、これはシステムをダウンさせかねない大きな問題を抱えている。読み進める前に、今、コードレビューやテストをしている段階だと考えて、ぜひそれを指摘してみてほしい。

問題点

問題点は次の通りだ。

本コードには致命的なパフォーマンス劣化を引き起こす入力が存在する。
例：

str = "\r\n"*100 + "b"

手元に Ruby の実行環境があるなら試してみてほしい。応答が返ってこないことが確認できるはずだ。もしこの str が外部入力だったら、容易に DoS 攻撃が可能なことがわかるだろう。文字列の途中に \r\n を多数連続して含めれば良いだけだ。実際のところ、この場合システム利用者は攻撃をしている認識がない可能性すらある。

ではなぜこうなるのか。

理由

この正規表現は以下のように挙動する。

1. \r\n 100 個にマッチするが、末尾アンカーにマッチしないためバックトラックする
2. \r\n 99個と \r 1個と \n 1個にマッチするが、同じくアンカーにマッチしないためバックトラックする
3. \r\n 98個と \r 1個と \n 1個 と \r\n 1個にマッチするが、同理由でバックトラックする
4. \r\n 98個と \r 1個、 \n 1個、 \r 1個、 \n 1個にマッチし、やはりバックトラックする

以下略

つまり \r\n 一個当たり、 \r\n としてマッチするか、 \r と \n でマッチするかの二通りがあり、これを連続数分それぞれについて試す。以上より、連続する \r\n の個数に応じた指数オーダーの計算時間を要する。

実際に計測してみよう。

require 'benchmark'

Benchmark.bm 2 do |r|
  (20..24).each do |i|
    r.report i do
      ("\r\n"*i + "b").sub(/(\r\n|\r|\n)+\z/, "")
    end
  end
end

結果はこうだ。

         user     system      total        real
20   1.240000   0.010000   1.250000 (  1.249022)
21   2.470000   0.000000   2.470000 (  2.484267)
22   4.930000   0.010000   4.940000 (  4.966644)
23   9.900000   0.000000   9.900000 (  9.934231)
24  19.740000   0.020000  19.760000 ( 19.783307)

見事な倍々ゲームである。 24 個で 20 秒かかるとすると、 100 個もあれば約 4 京 7918 兆年かかる計算だ。宇宙は 138 億歳くらいらしいので、宇宙の始まりからずっと計算していたと仮定してもさっぱり終わる様子がないことになる。

解決案1

もっとも無難な解決案は、 (\r\n|\r|\n) に ?> を加えてアトミックグループとすることだ。

参考： https://docs.ruby-lang.org/ja/2.5.0/doc/spec=2fregexp.html

通常の正規表現では、ある部分式がマッチに成功した後、続く式がマッチに失敗した場合、バックトラックによって成功した部分の一部を手放してマッチにリトライします。 しかし、アトミックなグループがマッチした後、後続の式がマッチに失敗した場合、一部だけをバックトラックで巻き戻すのではなく、このグループのマッチ全体を巻き戻します。つまり、正規表現のマッチのバックトラックを抑制します。
典型的にアトミックグループはバックトラックの回数を減らし 正規表現を高速化するために用います。

require 'benchmark'

Benchmark.bm 2 do |r|
  (20..24).each do |i|
    r.report i do
      ("\r\n"*i + "b").sub(/(?>\r\n|\r|\n)+\z/, "")
    end
  end
end

先ほどとは異なり、一瞬で完了する。

         user     system      total        real
20   0.000000   0.000000   0.000000 (  0.000054)
21   0.000000   0.000000   0.000000 (  0.000043)
22   0.000000   0.000000   0.000000 (  0.000045)
23   0.000000   0.000000   0.000000 (  0.000048)
24   0.000000   0.000000   0.000000 (  0.000051)

解決案2

正規表現 \R を利用する方法もある。

str.sub(/\R+\z/, "")

見た目も簡潔になって素晴らしいが、元々のコードと比べると実は少々挙動が異なる。定義は以下の通りであるらしい。

参考： https://docs.ruby-lang.org/ja/2.5.0/doc/spec=2fregexp.html

\R: (?>\x0D\x0A|[\x0A-\x0D\u{85}\u{2028}\u{2029}])
(Unicode 以外では (?>\x0D\x0A|[\x0A-\x0D]) になります)

従って

• 0x0b (\v) # VT（垂直タブ）
• 0x0c (\f) # FF（改頁）

および、更に Unicode 環境下では

• U+0085 # NEXT LINE (NEL)
• U+2028 # LINE SEPARATOR
• U+2029 # PARAGRAPH SEPARATOR

の各文字も改行として認識されることになる。意味論としては正しいが、望む動作かどうかは状況によりけりではある。

なお見ての通りアトミックグループを用いて定義されており、本件の問題にきちんと対処されていることがわかる。

解決案3

そもそも正規表現を使っているのが筋が悪いのではないか。と思って探してみるのだがこれが意外とみつからない。それっぽいものに chomp があるのだが、知っての通りこれは末尾の改行一文字を取り除くのだ。

と思いきや

https://docs.ruby-lang.org/ja/2.5.0/class/String.html#I_CHOMP

rs に空文字列 (“”) を指定した場合は「パラグラフモード」になり、 末尾の連続する改行コードをすべて取り除きます。

なんだって！？

pry(main)> "abc\r\n\r\n\n\n\r\n".chomp("")
=> "abc"

本当じゃないか…！

実行速度も速い。やはり正規表現を使うのが筋が悪かったんだ。ちゃんと用意されたメソッドを使うべきだったんだ。しかしなぜこんな引数でこんな挙動をするんだ。引数は改行文字の指定だとある。空文字列を改行文字とすると末尾の改行が全部消えるのか。空文字列が改行文字とはいったいどういうことなんだ。どうして指定していない文字が消えてしまうんだ。こんなんじゃコードレビューで読み違えたコメントがついても仕方ないんじゃないか？（※ちなみにこれはどうやら Perl 由来の機能らしい）

で、その辺のことはともかく目的からすれば chomp("") を使うべきだよねとなるはずだったのだが、これもまた地味にこれまでのものと挙動が異なり、 \r 単品を改行とはみなさないようなのだ。

pry(main)> "abc\r".chomp("")
=> "abc\r"
pry(main)> "abc\r\r".chomp("")
=> "abc\r\r"
pry(main)> "abc\r\n".chomp("")
=> "abc"
pry(main)> "abc\r\n\r".chomp("")
=> "abc\r\n\r"
pry(main)> "abc\r\n\r\n\n\n".chomp("")
=> "abc"
pry(main)> "abc\n\r\r\n\n\n".chomp("")
=> "abc\n\r"

\r (CR) を改行コードとしていた Mac も、 OS X からは \n (LF) となって久しいので、これが現実の問題になることは少なそうではある。ただ、本当に問題ないのかどうかは個別の状況を確認しておくべきだろう。

まとめ

一見簡単そうな問題が、対応方法によって挙動が微妙に異なったり、場合によっては致命的な問題に繋がる例を紹介した。特にパフォーマンス劣化を引き起こす件については、本質的には正規表現のバックトラックによるものであり、言語や対象文字列とは独立した問題だ。

実際に類似問題がセキュリティ上の問題として報告・修正されることもあり、例えば以下のようなものがある。

• https://bugs.python.org/issue32981 (CVE-2018-1060, CVE-2018-1061)
• https://github.com/django/django/commit/97b7dd59bb8d6163239061e2022153c3415d146d (CVE-2018-7537)

慣れないと気づきづらい問題である。正規表現を利用するときは気を付けたい。