はじめに

このエントリは全5回を予定する19卒新人ブログリレーの第1回目です。

はじめまして、リクルートテクノロジーズ新卒二年目の藤原 巧と申します。

私は、競技プログラミングを強みとして入社し、現在はプラットフォームセキュリティグループという部署でセキュリティエンジニアとして活動しています。
競技プログラミングといえば、プログラムの高速化が得意といった、セキュリティとはあまり縁のないイメージを持つ方も多いと思います。

ここでは、そんな競技プログラマーの藤原がセキュリティエンジニアとして働く上で、競技プログラミングの経験がどう活きているのかについてご紹介したいと思います。

想定読者

この記事は、

• 競技プログラマーだけど将来のキャリアに悩んでいて、その一例を知りたい人
• 競技プログラマーがどんな人なのか、その一例を知りたい人

を対象に書いています。 そんな方々の参考になれば幸いです。

競技プログラミングについて

この記事では、与えられた問題に対して制限時間内に実行が完了するようなコードを、早く正確に提出する競技プログラミング（通称アルゴ）にスコープを当てて説明します。
このアルゴでは、おおよそ2時間で4問から6問程度の課題を解きます。

アルゴでの「制限時間内に実行が完了するようなコード」に関して、例を挙げて説明します。
「Nが与えられて1からNまでの和を2秒以内に求めるプログラムを作る問題」であれば、2秒以内の部分が「制限時間」に該当します。
Nが10000程度の制約条件であれば1からNまでループを回せば解くこともできますが、
Nが10^12などの厳しい制約条件では間に合わせることが難しいため、等差数列の和の公式を用いて変形しなければなりません。

アルゴでは、このように、実行が制限時間内に収まるようにアルゴリズム的な工夫や式変形など、様々な工程が必要です。
特に2時間以内で6問と、短時間で実装する必要があるため、

• コードが簡単でバグが入り込みにくい
• 「実行時間が制限時間内」に収まる

そのようなプログラムを、うまく問題を変形して考える必要があります。

そんな競技プログラミングですが、「アルゴリズムを考える」以外にも様々なことを考慮する必要があり、また他にも様々な遊び方があります。
この記事では、「アルゴリズムを考える」以外の様々な遊び部分も含めて、どのように競技プログラミングの経験が業務の経験で活きているかについて、ご紹介しようと思います！

競技プログラミングのHack と セキュリティ

競技プログラミングの「アルゴ」には、大きく分けて以下のような2つのコンテストが存在しています。

1.コンテスト中にソースコードを提出し、Acceptedと表示されればその時点で点数が確定する「full-feedback」と呼ばれる形式

2.コンテスト中に提出しても簡単なプレテスト(preteset)しか行われず、コンテスト終了後に行われる本格的なテストで初めて点数が確定する「pretest」と呼ばれる形式

「pretest」と呼ばれる形式では、自分のコードの提出後、他人のコードを閲覧してバグをつく「Hack」と呼ばれる機能があります。
このHackでは、入力される値の種類を意識していないコードに対してコーナーケースを指摘する必要があり、そのようなケースを考える力がセキュリティで活きていると感じています。

競技プログラミングのコーナーケース探しでは、入力可能な範囲内で実行時間が長くなるようなものや、間違った出力をするものなど、悪意のある入力を探すことが多いのですが、
セキュリティのテストでも同様に「どのような値がその関数に入って来うるか想像して、バグの起こりそうな入力を探す」ということが多くなります。

私の好きなとある脆弱性では、入力値がアルファベットの「小文字→大文字→小文字」と変換されることで、元の文字とは別の小文字に変わるという不思議な文字が悪用されていました。
もし手元で大文字と小文字を変換できる環境があれば、ドイツ語の「ß」（エスツェット）という文字を「大文字変換(upper)→小文字変換(lower)」と変換してみてください。別の文字に変わると思います（しかも文字数も増えます！）。
昨今広く使われているUnicodeでは世界中の様々な文字を表現できるため、このような特殊な文字も入力値として考えなければならない場合があります。
もし一部では元の文字のまま処理を行い、別の場所では大文字や小文字に変換した文字列を使用していたらどうなるでしょうか？
その些細な違いが、「GitHubのパスワードリセットのメールが他人に送信される」という脆弱性になりえるのです。
興味がある方は、以下のページをご覧ください！

10^9+7 のあまり と セキュリティ

競技プログラミングではしばしば、答えを10^9+7で割ったあまりを求める問題が登場します。
例えば、「1~Nの数字が書かれたボールがあります。ボールを1列に並べる時、数字の順列の総数はいくつになりますか？ただし答えが大きくなるので、10^9+7 で割ったあまりを求めてください」
というような問題ですね。

この10^9+7 という数は、実は素数であり、正の整数を素数で割ったあまりの集合は「有限体」になることが知られています。
他にも、「セグメント木」に「モノイド」を乗せることであったり、競技プログラミングでは群・環・体の知識が役に立つことがあります。

このような知識は、暗号周りの脆弱性の調査で役に立ちます。
我々プラットフォームセキュリティグループでは、毎日世の中に公表された脆弱性の影響を調査する「早期警戒」という業務があります。
先日報告されたWindows の Crypto APIにおける楕円曲線暗号の証明書検証不備の脆弱性では、
影響の解析に群論の知識が役立ちました。

もし、10^9+7で割ったあまりに関して、より深く知識を掘り下げたい方は暗号理論を勉強すると楽しいかもしれませんね！

計算量の見積もり と セキュリティ

競技プログラミングのアルゴでは、1秒あたりおおよそ10^9回程度計算できるとして、与えられた時間以内に計算が完了するかどうか、計算量の確認をする必要があります。
例えば、N個の（重さ、価値）を持つ商品があり、それらの商品をいくつか選んで、重さX以下で価値を最大化する問題を考えてみましょう（一つの商品を2個以上選べないものとします）。
Nが10程度であれば、2^N をすべて列挙できるので、計算が容易にできますが、Nが1000になったとたんに計算量が大きくなり、計算が間に合わなくなるので、工夫が必要になってきます。

脆弱性が発生した場合も、セキュリティリスクを調べる上で、計算量を見積もり定量的に判断することが重要になるケースがあります。
例えば、一部の脆弱性の攻撃方法として、HTTPリクエストなどの試行を何度も繰り返すことでエラーメッセージなどから機密情報を少しずつ漏洩させるというものがあります。
一定量の試行回数が攻撃手法となる例としては、POODLE Attackや、ROBOT Attack が挙げられます。

これらのアルゴリズムを調査する上では、アルゴリズムの内容を把握し、そのステップごとに計算量を明確化し、人に伝える必要があります。
ここは、競技プログラミングでの計算量を求める経験が活きた部分だと感じました。

最後に

この記事では、藤原がセキュリティエンジニアとして働いていて、競技プログラミングの経験がどこで活きていると感じたかをまとめました。
競技プログラミングも、問題を解くプロセスや楽しみ方も人それぞれなので必ずしもこのような経験をするわけではありませんが、その一例として参考になれば幸いです。
もし、競技プログラマで競技プログラミング以外の趣味を探している方は、セキュリティ領域に足を踏み入れてみてはいかがでしょうか？