【Z-III】seccampに参加したい人のための、参加課題の解き方【ReDoS対策/Linter編】

seccamp'20 と今回の記事の関係について

seccamp'20オンラインでは、グループで続けるというテーマのもと、グループワークが行われています。
今回の記事は、そのグループの1つ「電源50Hz」メンバーが週替りで
- 参加課題をどう解いたのか
- どうやって解答を作ったのか
- 普段どんな(勉強|実装|活動)をしているのか
などを記事として書き、
「今後のseccampに参加したいけど、課題難しくて自分じゃ無理そう……」
「seccampの課題どう解いてるのか分からないし、出てくる解答は凄すぎて手が届かなそう……」
と参加を諦めている人を、seccamp参加に繋げられるような情報発信を行っていきます。

なお課題は一部のみ引用していますので、全文は
https://www.ipa.go.jp/jinzai/camp/2020/zenkoku2020_vote.html#kadai
をご覧ください。

seccampの提出課題について

今回は集中開発コース、Z-IIIトラックに参加した自分が、どうやって課題を解いたのかを中心に書きます。
さてまず、Z-IIIトラックはどういったことをするのかの説明から参りましょう。

Zトラックは「プラットフォームセキュリティトラック」というトラックで、

Zトラックは、いわゆるインフラ（OS、VM、ネットワーク、アンチウィルス、Webセキュリティ）に興味があり、かつソフトウェア開発にもモチベーションがあり、加えて情報セキュリティにも取り組みたい、という3つの興味を満たし、それぞれの実力を育ててもらうことを目標としています。

と公式の説明にもある通り、幅広く深い専門知識を求められる傾向にあります。

その中で、今年のZ-IIIトラックの課題は「正規表現」と「静的解析」についての知識を問う内容でした。これだけ聞くと、難しそう……と思われるかもしれません。
勿論簡単ではなかったのですが、他のトラックの難易度から見ればそこまで高難易度の問題ではなく、ヒントとして資料も提示されているなど、課題提出者に優しいトラックでもありました。

特定の専門分野に特化していないと、問題が何を書いてるかも分からない他のトラックに比べて、解答の道筋は立てやすいものだったと思います。

大問1

小問1

この問題はある正規表現にマッチする文字列を3つ見つけ、どんな文字列がマッチするか説明せよ、という問題です。

実はこの課題、ただマッチする文字列を3つ出すだけであればそこまで難しくありません。"b", "bb", "bbb" でも正解ではあります。
ただし、「説明せよ」とあるということは、「どこまでその正規表現を理解しているか」を問われているように思えます。ということは3つ正規表現はあまり共通点のないものが望ましいと考え、""(空行)、"b"、"aa"という３つで提出しました。また法則性として、

この正規表現は全ての文字列についてがかかっており、bと(abab*)どちらも0個以上あれば条件を満たす。すなわち、""でもマッチする。同じように"b"でもマッチする。このbはいくら続いてもマッチする。
(abab)だけで考えると、"aa"や"abbbbbabbbaaa"などで満たせる。この正規表現は、aで始まること、aが偶数個存在することの2つを満たせば、どこにどれだけbが入っていてもマッチする。

という法則を見つけて、正規表現全体がこういった文字列にマッチする、という内容をなるべく漏れがないように説明しました。

小問2,3

この問題は、今回受講生として実装を行うReDoSに極めて深く関わる内容です。内容が続いているので両方一緒に考えることにしました。

実はseccampの講義で、グラフ理論やアルゴリズムを含めたより一般的な詳しい説明を受けています。
しかし今回は「seccamp参加を目指す」人向けの説明ですので、あえて提出した内容そのままで、どうやって解答を作ったかを書きます。

まず、私は情報工学専攻でないので、正規表現は少し使ったことがある程度で、詳しい理論については何一つ知らない状態からのスタートでした¹。つまりグラフ理論もアルゴリズムも分からない、そもそも数学的に解けることすら知らない状態です。

とりあえず課題にある正規表現をpythonで動かしてみると、確かにa50を入れると正規表現のマッチが終わりません。なのに何故かa100になるとすぐにマッチします。そしてa*49ではマッチしません。この時点で、

"a"*k(kは整数)で、50<=k && k<=100 のときマッチする

という予想をたてました。²

文字列が増えると処理も増えそうなのに、何故か文字列が少ない方が処理時間が長い……？というところで、恐らく括弧の中にある?演算子が何かしていそう、という予想を更に立てました。

ここからヒントを読もうとして、すぐに諦めました。
流石に前提知識がない専門的な話を英語で読めるような、素晴らしい英語力には持ち合わせがありません。とりあえずそれらしいことを日本語で探します。DeepLでどうにか解決できそうな気もしますが、日本語の解説を読むほうが分かりやすいでしょう。

すると運の良いことに、課題提出期限の1ヶ月前に書かれたReDoSの記事を見つけました。
https://gigazine.net/news/20200701-redos-cheet-sheet/

しかも丁寧にアルゴリズムの簡単な解説付き！これはしめたものです。雰囲気で理解し、それっぽく解答を書きました。

一般的な正規表現は、正規表現を前から順に評価していき、文字列とマッチしない場合評価する正規表現が1つずつ前に戻って再度評価し、文字列がすべてマッチした時点で終わるという仕組みになっている。つまり、文字列が連続でマッチしないど何文字も前から順に評価を行わなければならない。
ここで、正規表現の?は最短一致でマッチするものを選ぶ仕組みとなっているが、今回の場合k==50に近くなると、(a?){50}を"a"*50から"a"*1まで何度も繰り返して評価する必要が出てくる。
逆にaが100に近くなると、(a?){50}がより"a"*50に近づくため、kが小さい場合の評価がなくなり、時間が短くなる。
ちなみに、101<=kの時は文字列が全てマッチするまで正規表現が終わらないので、"a"*50以上に膨大な時間がかかる。

こんな感じでそれっぽい説明と、意味があるか分からないおまけを書くことで、ちゃんと理解してますよ！と猛アピールをしておきます。
意味があるかはわかりませんが、おまけが間違ってても減点はされないだろう、あわよく加点されれば尚良し！という期待を込めて大問1を提出しました。点数制かどうかは分かりません。

大問2

小問a

大問2はLinterや静的解析について問われました。まずはJavascriptのeval関数の危険性についての説明です。
これはなんと日本語ヒント付きです！ ということで、自分の合ってるかどうか分からない微妙な解答を見るより、ヒントでもある
https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/eval
を読むべきだと思います。

任意の文字列をコードとしてそのまま動かすと、入力元が信頼できない場合何されてもおかしくない

みたいなことを書きました。

小問b

恐らくこれが最も参考にならない解答です。こんな奴でも参加できるのか…と思ってください。

関数を検出するという時点で、というかこのトラックが何をするトラックか知っていれば、何をするかはもうお分かりかと思います。³

Javascript、Linterのトラックと言えば、ES-Lintの出番ですね。

木構造になったコードから、eval関数を検出して警告する、というのが詳しく書けていればOKだと思います。Lintに詳しいなら、更にコードを書いて説明すると完璧です。

間違っても正規表現で解決などという愚かな真似はしないでください。

最後に

さて、これを読んで皆さんはどう思ったでしょうか。
「自分には難しすぎて無理！」という気持ちが少しでも無くなれば嬉しいです。

今年は例年と違いオンラインということで、課題の難易度が少し変わった可能性はあります。
ですが知識不足でもググりながら課題を頑張れば、結果の保証はできませんが、講師の方は絶対に評価してくれます。

「こんな奴より自分の方がずっとできる！」と思って応募する方がいれば、私個人のグループワークの目標は達成できたかなと思っています。^{4 5}

とりあえずの軽い気持ちで課題をやって提出するだけでも、今まで知らなかった知識に触れられます。

私自身は年齢の問題で今後は全国大会に受講者として出ることはもうできませんが、seccampへの関わりは今後も続けていきます。

もし何かの機会でお会いできたら、その時はよろしくお願いします。

1. 受講生には非情報系出身者や高校生の方います。全国(世界)から年齢/性別/得意分野などが多種多様な人達が集まります。 ↩

2. ついでにささやかながらプログラムっぽく書いて、自分プログラム書いてますよアピールをしました。多分評価には入ってないので真似しなくて良いです。 ↩

3. まさかコードが"eval(.*"という正規表現にマッチするか調べる、なんて考えて提出してしまった人はいませんよね…？ ↩

4. 私自身はseccampを5年ほど前に知り、その時はとあるブログでの提出課題内容に圧倒されて、自分には辿り着けない世界だと思った記憶があります。同じような理由で諦めてしまう人が少しでも減るように、このグループワークを提案しました。 ↩

5. 特に地方の学生には是非参加してもらいたいです。自分は北海道の大学生ですが、seccampに出なければこんなに凄い受講生や講師の方々と学生のうちに話す機会は、もう手に入らなかったと思います。 ↩