正規表現とは何なのか、makenowjustが正規表現に興味を持ったきっかけ。深掘りRubyKaigi 2023 with spikeolaf & makenowjust 文字起こしレポート vol.1

2023年6月15日に『深掘りRubyKaigi 2023 with spikeolaf & makenowjust』を開催しました。イベントの内容をほぼ全文文字起こし形式でお届けします。この記事は第1部です。 hey.connpass.com

イベントのアーカイブはYouTubeでも公開しています。

www.youtube.com

登場人物

ゲスト

makenowjust/藤浪大弥さん
spikeolaf/金子雄一郎さん

STORES

fujimura/藤村大介
shyouhei/卜部昌平
hogelog/小室直

正規表現に興味を持ったきっかけ

fujimura：最初は藤浪さん、makenowjustさんに正規表現の発表について伺おうと思います。まずは改めてRubyKaigi 2023でどんなことを発表したかを紹介いただけないでしょうか？

makenowjust：Rubyの正規表現エンジンはOnigumoっていう名前なんですけど、この正規表現エンジンに対してReDoSというセキュリティ上の脆弱性が起きるのを防ぐような変更を行った話をしました。

まずReDoSがどういう脆弱性なのかというと、正規表現マッチングっていうのは正規表現と文字列の組み合わせによっては、マッチ時間がすごく長くなってしまうことがあります。例えば30文字ぐらいの入力文字列でマッチに1、2分かかってしまったりとか。Webアプリケーションの中にそういった正規表現があって、悪意ある人がそういう文字列を送ってくるとその間サーバの処理がそれに占有されてしまって問題が起こる、そういった脆弱性をReDoSといいます。

ReDoSを防ぐためには、マッチ時間がものすごく長くなってしまうマッチ時間の爆発を防がなければいけません。そのために今回は正規表現エンジンの中にメモ化による最適化を行いました。マッチ時間が爆発してしまうのは、マッチングの中で同じ状態の文字列が同じ位置に何度も到達していることが原因なので、ある位置に到達したということを一度記録してもう1回到達したときには即座に失敗とみなすような最適化を入れることで高速化しています。結果的にそういった最適化ができない場合は、まだReDoSが起こってしまう可能性はあるんですけど、最適化がうまくいく場合にはReDoSが起こらないことが保障できるようにRubyの正規表現エンジンを高速化しました、というような話です。

今後の展望としてRubyの正規表現エンジンをRubyで書いたものに置き換えられたらいいなぁというような願望みたいなものを語ったりしました。

rubykaigi.org

fujimura：ありがとうございます。いきなり事前に送った質問と違うことを聞きますが、そもそもなぜRubyの正規表現、ReDoS、Rubyに出会ったんですか？結果的にこうなった始まりはどこだったんですか？

makenowjust：自分はもともとプログラミング言語が好きで、いろんなプログラミング言語を試してみたり、自分で作ったりもしようとしてたんですけど。プログラミング言語を作る中で一番最初にパーサを書くんです。パーサを書くのが楽しくてずっと書き続けてて、パーサをもっと深掘って勉強してみようと思ったんですけど、文脈自由文法やパーサの理論って難しいなぁと思って。正規表現は勉強してみたら思ったよりわかるなぁとなったのが正規表現に興味を持ったきっかけですね。

fujimura：なるほど。

makenowjust：正規表現に興味を持っていて、昔サイボウズのインターンで、先読み、後読みがあるような正規表現をうまく線形時間でマッチできるようなエンジンを作っていて。その時に新屋先生という『正規表現技術入門』の著者に知り合って、そのつながりで2020年のセキュリティ・キャンプで講師をしようという話になりました。正規表現とセキュリティが絡む話題ってなんだろうという中でReDoSという話題が出てきて、ReDoSについて調べたら、意外と理論的なバックグラウンドがあって面白いなぁと思って、ReDoSに入れ込んでいきました。というのがReDoSに興味を持ったきっかけです。

Rubyの正規表現エンジンに関わることになったきっかけは、そういった話があった中で2022年あたりにRubyもReDoSの問題があるっていう相談が新屋さんにあって、新屋さんから僕に話がさらに来て何かやってみないかと言われて、その流れで遠藤さんたちがいたクックパッドでインターンをして正規表現エンジンの最適化を行いました。

fujimura：なるほど。本格的にRubyと関わるようになったのも正規表現がきっかけなんですね。

makenowjust：はい。

Rubyの正規表現エンジンは素朴

fujimura：他の正規表現エンジンももちろんご覧になったんじゃないかなと思うんですけど、Rubyのを見てどう思われたんですか？

makenowjust：Rubyの正規表現エンジンは素朴でいいなぁと、そこまで複雑じゃないのでまだ全然読めるなぁと。Chromiumに乗っているJavaScriptエンジン V8の正規表現エンジンがIrregexpっていうんですけど、めちゃくちゃすごい実装でJITとかが絡んでたり、バイト・コードレベルの最適化もピープホール最適化をやってたりして、正規表現エンジンの実装なのにコンパイラみたいな作りになってるんですよね。全然わからないなぁと思った記憶があるのでそれと比べると全然わかりやすいなって。

fujimura：ハックしやすかったというか。

makenowjust：はい、そうですね。Ruby全体が結構そういう感じなのかな、どうだろう。V8よりは簡単という認識です。

fujimura：登壇者の方で比較したことがある方がいたら聞いてみたいんですけど、卜部さんはどう見てるんですか？

shyouhei：僕も他のプログラミング言語の正規表現エンジンをそんなに真面目に読んだことがないので。言っちゃえばRubyの正規表現エンジンもそこまで読み込んではないというところもあるので、他と比べてどうですかと言われてもなかなか難しい。

fujimura：複数読んだことがある人もそんなにいないっていう。

shyouhei：ですね。

fujimura：そうですよね、正規表現エンジンソムリエみたいな状態に。コメントで「金子さんが首を傾げていた」とのことですか、何かコメントありますか？

spikeolaf：Ruby全体が読みやすいかというのは、まあ読みやすいところもあれば読みやすくないところもあるかなって。

fujimura：ありがとうございます。

大学での研究内容

fujimura：では、事前に用意してた質問からいこうと思うんですけど、卜部さんからお願いします。

shyouhei：今まだ大学に通われていると思うんですけど、普段大学ではどういったご研究をされているんですか？っていうのがまあ素朴な疑問としてあって。

makenowjust：大学での研究内容は、詳細は研究室の方針もあって触れられないんですけど、プログラム検証と絡めた情報セキュリティみたいなことをやっています。例えばプログラムを静的に検証してセキュリティ的なインシデントが起こらないということを保証できないか、そういう証明が作れないかみたいな研究をやっています。

shyouhei：全然正規表現と関係なかった。

makenowjust：いや、プログラム検証ってバックグラウンドにはオートマトン理論があることが多いので、意外と関わってくる部分なんじゃないかなと思います。僕はReDoSを防ぐだけじゃなくて、正規表現がReDoSを起こすかどうかのチェックも趣味でやってるんですけど、そういうのもプログラム検証っぽいなあって思っています。

shyouhei：なるほど、面白そうですね。

spikeolaf：僕は大学でコンピュータサイエンスの教育をそんなに受けていないんですけれど、伺っていると、ある時間で計算可能なものとかを研究していくと、当然ベースとしては正規表現というかオートマトンのような計算がすでにある程度読めるものとして帰着するイメージなのかなと思いました。

makenowjust：結局オートマトンってその性質がすごくいいので、解析に、解析の知識のバックグラウンドとして使いやすい。道具として優秀なんだと思います。

fujimura：ありがとうございます。卜部さんもうひとつ質問ありますよね？

shyouhei：先ほどの話とはジャンルが違うんですけど、自分が大学生だった頃を思い出して、他人の論文を読んでこれを実装してみようみたいな無茶振りを先生にされて超つらかった思い出があって。今回のやつだと特に自分が作ったわけでもない正規表現エンジンに自分が書いたわけでもない論文を実装するっていうハードモードの話じゃないですか。これ僕の経験から言うと超つらくって壊してるかもわからないし、正しいかもわからないし、五里霧中なんですけど、つらくなかったですか？

makenowjust：やっていて、なんかメモリ破壊になるときはつらいなぁと思った記憶はあります。ただやりたいことのアイディアはシンプルだと理解していたので、ちゃんとやればできることなんじゃないかな。そんなに難しいことをやろうとしてるわけじゃないっていう気持ちでやってました。

shyouhei：論文を読んでも抽象コードが書いてなくて、全部言葉でバーッと説明してるんですよね。読み下して理解をしないとなかなかしんどいなぁみたいな感じでしたね。

makenowjust：ぶっちゃけるとあの論文は結構怪しい。一応参考実装みたいなのもあるんで、そっちを見れば多少はわかるんですけど、論文に書いてあるメモ化のタイミングと実装のメモ化のタイミングが違うなぁとか。その辺に今も僕は振り回されているのでなかなか難しい。論文を読んで実装するっていうのだと、オートマトンだと数学的な記述が多いので、関数型言語を使って一回やると簡単だなぁと思うんですけど、今回の場合は別にそういう方向性でもなかったなぁっていう感じです。

shyouhei：お疲れ様です。

makenowjust：ありがとうございます。

プログラマになったきっかけ

fujimura：僕の質問なんですけど、なぜそもそもプログラマになったんですか？

makenowjust：なぜって言われると…

fujimura：どんなきっかけ？

makenowjust：中学生の頃に家にパソコンがあって、多分その当時ってInternet Explorer 8が出た頃だったんですけど、多分8ってインスペクターみたいなのがつき始めたぐらいで。それで色々と見れるようになって面白いなぁと思って。どうなってるんだろうって調べていってプログラミングに興味を持ったんだと思います。

fujimura：深掘りRubyKaigi 2022で話してもらったkateinoigakukunさんも同じようなことを言ってた。ブラウザからだったって言ってましたね。やっぱブラウザは偉大ですね。あのインスペクターって。

makenowjust：裏側に触れられてる感じがしてるのも面白くて。

fujimura：なるほどなぁ。

正規表現とは何なのか

fujimura：僕からは素人質問コーナーみたいな感じなんですけど、正規表現って今日来てくださっているみなさんも何かしら使ったことがあると思うんですけど、これは一体何者なんだろうというのが謎で、便利だからできたと思ったら結構違ったみたいな印象があったので、簡単にこいつは何なのかを教えてください。

shyouhei：一番難しい、本質を突かなければいけないやつ。

makenowjust：質問があらかじめ提示されていたので調べてきたことを話すんですけど、

fujimura：ありがたい。

makenowjust：ニューラルネットワークってあるじゃないですか。丸があって線でつながってるみたいなもの。そういうもので丸から次の丸に移動するためには、イベントが発火してこっちに移動する、次にこっちに移動するみたいなスタートとラストがある。でもこの最初から最後にいくためにはどういうのが連続で発火していかなきゃいけないんだろうっていう、要するにこれって有限状態オートマトンなんですけど、そういうのを考えた人がいて。

スタートからラストにいくまで単純に右から左に一直線につながっていれば簡単なんですけど、途中で戻っていくのがあるとどういう風になるのか。直感的な答えがありそうでなさそうというのに対して、数学的にどうやってそれを記述すればいいかというアイデアを1951年にスティーヴン・コール・クリーネさんが考えました。その方法が正規表現にある「*」、繰り返しがあるじゃないですか。ニューラルネットワークの有限状態オートマトンが表すどういうのが右から左にいけるかっていうのを書くための方法として、あれを導入することによってその集合の操作として和集合を取ったりとか。列限定なんですけど列をつなげるやつ以外にさらにその繰り返しをするやつっていうのを追加するとそれをうまく表せるっていうことを発見して、その書き方をレギュラーイベントって読んでいたんですが、歴史を経るにつれて結局数式なのでRegexpと呼ばれるようになりました。

fujimura：ありがとうございます。そんな背景があるって生活の中でプログラムを書いている人はそうなの？！みたいな感じでもあるような気がして驚きだなぁと僕も思いましたね。僕の素人質問の中に「オートマトンって何ですか？」というのがあったんですけど、一体あれは何なんでしょうね。あの理論は誰が何のために考えたんだろうな。

makenowjust：もともとは計算っていうものが何かっていうのを考えるために考えられたもの。チューリングだとかそういった過去の偉大な先人たちが考えたアイデアで、計算って1ステップごとにステップ1ステップ2みたいにやることを状態という考え方をして、そこは一つ進んでいったり、戻ったりするっていうのを考えるとうまくいくんじゃないかと考えたんじゃないかなと思います。

RE2をRubyにいれたらどうなる？

fujimura：これは藤浪さんに聞く質問じゃないかもしれないんですけど、例えば僕がGoを書いているとRE2ってGoogle が作った正規表現が使われているじゃないですか。あれを素朴にRubyもこれでいいんじゃないっていうふうにするとどんな困ったことが起きるんだろうなぁというのを聞いてみたかった。これは卜部さんにも聞いてみたい。

shyouhei：(Rubyで)RE2を使ってみようという話を実は前に言ってた人がいて、誰だっけな。Sam Saffronかなぁ。Sam SaffronはDiscourseを作っている人ですけど、ともかく正規表現が遅いのは困るから早くしてくれみたいな感じで、早い正規表現エンジンがここにあるじゃん、これ使えばいいじゃんみたいな話をして。それでさっき話が出ていた遠藤さんが実際ちょっとやってみようかなぁみたいな感じでちょっとだけ手を出して、生半可な気持ちでは手が出せませんねということが明らかになって撤退していった感じですね。

そもそもRE2とは何かというと、Googleに昔あったGoogle Code Searchを作るにあたって Googleの人たちが開発した正規表現エンジン。これの特徴はGoogleの検索窓のところに正規表現を突っ込めたんです、昔。

fujimura：ほおお。

shyouhei：なので外部の悪意やるユーザーからアタックされても、正規表現エンジンが死なないことを目標に、正規表現の言語の側をデザインして作っているんですね。できることがすごく限られていて、限られているんだけど実用上はそんなに困らないんですよ。落とし所として普段我々がやりたいことは大体できるみたいな感じのやつなんですけど、でもやっぱりRubyの今の正規表現とできることが違うので、その違う部分をどういう風にギャップを埋めていけばいいのかなっていうところが、ちょっと一筋縄ではいかなさそうな感じでした。っていう風に言ってたのを聞きました、僕がやったわけじゃないです。

makenowjust：という話を経て自分が呼ばれたので、そのあたりのことはよく知らないというのが正直なところです。

fujimura：なるほどなぁ。ありがとうございます。僕からもう1つ質問があって、最後の方でDFAで書き直すって話をされていたと思うんですけど、どの辺が難しそうみたいなのってもうあったりされるんですか？

makenowjust：実用上ちゃんと早く動くようにするっていう、その細かな最適化の部分が一番つらいんじゃないかなって思っています。実装自体はやればできるんじゃないかとは思っていて、Rubyのオブジェクト生成を減らすみたいな地道な最適化が最終的には大事になってくるんじゃないかなっていう。

fujimura：Ruby自体のボトルネックが見つかったりみたいな感じになるんですかね。

makenowjust：まあそういうイメージですね。

fujimura：なるほどなぁ。あとは本当にどうでもいい質問なんですけど、この正規表現エンジンが好きだなみたいなのありますか？

makenowjust：インテルが作ってるHyperscanっていう正規表現エンジンがあって、これはインテルが作っているだけあって、CPUの命令で追加された文字列の走査を早くする命令がふんだんに使われていて、すごい実装で、すごい速くて。何のために作ってるかっていうと、Deep Packet Inspection、パケットの解析に使うためにやっていて、数秒で数ギガとかをさばけなきゃいけないみたいなシチュエーションで使うようなやつで、その割にはいろんな機能が高機能なエンジンとして実装されてて面白いなぁって思った記憶があります。

fujimura：すごいニッチなところに向けている割にちゃんとできているっていうのがすごいみたいな。

makenowjust：意外と使おうと思えばどこでも使えるものではあるはずなんじゃないかなぁという。インテル謹製なのでインテルのCPUじゃないといまいちっていう。他のCPUで動くのかわからないみたいな。

fujimura：いや、すごいですね。面白いなぁ。

Rubyの中に複数の正規表現エンジンを入れられるのか？

hogelog：話を聞いていた中で気になったことがあって、PHPはPerl由来の正規表現エンジンが入っているかと思うんですが、Rubyだと正規表現エンジンって言語にがっつり絡み合ってるじゃないですか。複数入れるのが難しいのか、それとも別に入れられるのか、どうなんですか？

makenowjust：入れれば入るんじゃないんですか？僕よりもその辺は卜部さんの方が話せそう。

shyouhei：さっき話したRE2にはgemがありますよ。

spikeolaf：その議論って2つ意味があると思っていて、普通にオブジェクトとしてRe2.newみたいにエンジンとして入れられるかっていう問いと、あとRubyの文法parse.yの中に明らかにOnig系のインターフェースを期待している場所って何箇所かあるんですよね。あの辺に組み込みたいか、組み込めるかって問いはあると思ってます。

shyouhei：PHPのmb_eregだって別にリテラルじゃないわけじゃないですか。あれと似たような感じには多分できると思う。

spikeolaf：それはできると思います。

shyouhei：Rubyの言語の処理系の中から今のRubyの正規表現エンジンを抜くっていう話になると、多言語対応（M17N）が超大変。Rubyの成立過程として先に正規表現の方が多言語対応して、そこに後からRuby本体が乗ったので、正規表現の方だけ抜こうと思うとちょっとテクニカルに大変ですね。

spikeolaf：僕が思っていたのは、変数を束縛する箇所があるので、あれをなくせないのでどうしようかなっていうのありますね。

makenowjust：そこはキャプチャの数を数えられるとかあればいいんじゃないですかね。

shyouhei：named captureは正規表現で書くとマッチした瞬間にローカル変数になるんですよ。

makenowjust：そうなんだ。

spikeolaf：キャプチャを書いた場合のローカル変数として組み込んで、それが他に影響するんですよ、あのパーサは。

fujimura：悪いことをするのが好きな人が大好きな機能ですよね。

shyouhei：その機能を作った人が、できるからやったけどやりすぎだって言ってました。

spikeolaf：誰が作ったんですか？

shyouhei：たなかさんっていう人が作りました。

spikeolaf：ああ、なるほどね。わかりました。

hogelog：便利だなぁって思って。なくなるとショックを受ける人は多いだろうなって思いますね。もともと正規表現エンジンは自分でも色々書いたりしてるんですか？

makenowjust：ちゃんとした実用上使えるものは作ったことはないんですけど、勉強のためだったりとか、面白いことできないかなと思って書いてみたりは色々やったことがあります。さっき話したReDoSが起こるかどうかをチェックするツールの中で、動的な解析正規表現マッチングを実際に行ってみて爆発するのがないかを遺伝的アルゴリズムで探すみたいなことをやってるんですけど、そこでは当然実際にマッチングをやらなきゃいけないので正規表現エンジンを実装しています。

hogelog：ReCheckでしたっけ？

makenowjust：です。

hogelog：なるほど、ありがとうございます。

fujimura：参加者のみなさんの質問でも拾おうかと思います。

spikeolaf：いつものみなさんが解説を加えてくれている。

fujimura：ありがたい。

金子さんの発表の感想

fujimura：もし質問がなかったら聞いてみたかったのとしては藤浪さんは金子さんの発表をどう見ていたかってのは聞いてみたかったです。

makenowjust：僕は冒頭で話したようにパーサに興味があったんですけど、割と挫折した感があったので。それを真剣にやってる人がいて、すごいなというか憧れました。今の時代にBisonを置き換えるものを作ろうっていう発想になるんだっていうのが衝撃でしたね。

spikeolaf：それはどういう意味で言ってます？

makenowjust：Bisonって枯れたソフトウェアで、わざわざ置き換えるようなものではないんじゃないかと。

spikeolaf：なるほど、わかりました。

makenowjust：と思いつつRubyのパーサについて多少見たことがあったので、何かできるならやったほうがいいんだろうなって。モチベーションがあるのはイメージできましたね。

卒業したらやりたいこと

shyouhei：ご質問いただきましたね。「卒業したら何をやりたいですか？」

makenowjust：卒業したら…うーん。未だにアカデミックでやっていくか、社会に出ていくか方向性が定まっていなくて、どうしようかなって思っています。自分はReDoSの研究が好きでやっているけど、これ一本でアカデミアでやっていけるんだろうかという不安があるので、その部分を残りの大学院、あと3、4年やっていく中で埋めていけたらなって考えています。

shyouhei：ReDoSで外部予算を獲得していただいて。

fujimura：インターネットジャイアントの人とかはサポートしそうですけどね。みんな困ってるだろうし。

makenowjust：ただその困ってる部分とアカデミックをどうやって結びつけるかっていう部分はセンスみたいな感じがしていて。割とそういうことをやっている研究室ではあるので教授の背中を見て上手くやっていけたらなって思っています。

DFAの新しいアルゴリズムのすごさ

fujimura：ちょうど時間がきたんですけど、もう一個聞きたいことがあります。DFAで新しいアルゴリズムがあってそれをRubyで実装してみるという話を最後にされてたと思うんですけど、いわゆる普通のDFAの正規表現エンジンを使うのに比べると、どういうところが新しいんですか？

makenowjust：Microsoftのあの論文の新しいところは、最近の正規表現っていうか .NET（ドットネット）の正規表現のほとんどの範囲をちゃんとサポートしつつ、理論的にちゃんと意味を与えて効率的な実装を作ったところが意義深いんじゃないかと思います。ああいう方針で正規表現を実装するっていう研究自体はいくつかあるんですけど、実用レベルで使われているのはほとんどない。多分実際なくて、それを現実に使われる .NETの標準ライブラリに組み込まれるようなレベルの実装として作ったのがすごい。

fujimura：世界で動いてるっていうことなのかな？

makenowjust：動いてるんじゃないんですかね。.NETがどれくらい使われているのか計り知れない。そこは僕もわかんないんですけど。藤村さんが着ているのはMicrosoft Tシャツじゃないですか。

fujimura：Tシャツはメルカリで買いました。なるほど、ありがとうございます。ということでお時間なので、藤浪さんのパートを終わりにしようと思います。改めてありがとうございました。

第2部に続きます。