Imo Judge を支える技術

2011年12月公開

Imo Judge を支える技術

オンラインジャッジとはプログラミングコンテストのために作られたプログラムの自動採点システムであり，選手が提出したソースコード (以下，ユーザプログラムと言う) をコンパイルして実行しその結果を元に採点を行います．プログラミングコンテストは公正にかつ問題を起こさずに粛々と行われなければなりません．送られてきた任意のソースコードを実行するという極めて危険な行為をせざるをえないオンラインジャッジでは，これらを満たすために様々な工夫が行われています．この記事では，私が作っている Imo Judge を例にとり様々な工夫を紹介します．

サーバの構成

選手 → Web サーバ → データベース ← ジャッジサーバ
図 1: 現在の Imo Judge の構成 (矢印は接続の方向を表す)
ICPC では PC2 という Java で書かれたジャッジシステムが使われています．また TopCoder も同様に Java で書かれたジャッジシステムが使われています．しかし，クライアント側でアプリケーションとして動かすと環境依存を避けることは (特にネットワーク周りについては) 難しく，仮に問題が起きた時にもデバッグが非常に困難なものとなります．特に例外を吐いて終了するような状況になってしまうと復旧が困難になるので，Imo Judge では環境依存をよく吸収するブラウザを通して選手とやり取りを行います．
Imo Judge では Web サーバとジャッジサーバを完全に分離しデータベースを間に置くことによりそれら 2 つの依存度を低くし，ジャッジサーバのスケーリングを可能にしました．結果としていずれのコンテストでもジャッジサーバを複数動かし選手の待ち時間を削減でき，また採点のやり直しが発生した時にも一時的にジャッジサーバの台数を増やすことによってスムーズに対処することができました．
コンテストの時間中はジャッジサーバは Amazon EC2 上で動いています．サーバの台数は手動ではありますが指示すれば数分でスケールすることができます．また，コストは 1 時間単位でつくため非常に安く，例えば 2011 年の京都大学プログラミングコンテストのジャッジサーバにかかった金額は，
の様な内訳となり，約 300 円と非常に低価格でコンテストを行うことができました．

ジャッジシステムの設計

実行方法の多様化

近年，情報オリンピックではバッチ方式 (入力が全て与えられ，出力を確認する形式) だけにはとらわれず様々な問題が提案されています．
バッチ方式 (スペシャルジャッジも含む)
決まった入力が最初にすべて与えられる最も典型的な方式です．多くのバッチ方式は出力が決まっていますが，浮動小数を扱う問題などで出力が不定な問題もあります．そのような問題を採点するには出力したデータを別のプログラムで解析する必要があります．
アウトプットオンリー方式
この方式は選手に予め入力データを与え，手元でプログラムを実行し出力ファイルを作って提出する方式です．NP 困難な問題などの解が定まらない問題で採用されており，実際に入力データや出力データを見ながら自分の手で編集したり使うプログラムが変更できるという点で非常に特徴的な方式です．
リアクティブ方式
バッチ方式が入力データを最初にすべて与える方式であるのに対してリアクティブ方式はユーザプログラムの出力に応じて入力を与える方式です．オンラインアルゴリズムを問う問題はもちろんのこと，三目並べのようなユーザプログラムの出力によって次の入力が変化する問題にも対処できます．2011 年の京都大学プログラミングコンテストではこの方式を用いて乱択アルゴリズムを問う問題を出題しました．
エンコーダー/デコーダー方式
近年現れた方式で，2 つのプログラムを書かせて通信させる方式です．通信路容量を問う問題などで使われています．

ジャッジシステムへの攻撃手法とその対処法

ジャッジシステムはいかなるプログラムをコンパイル・実行してもシステムダウンしてしまってはいけません．そこで，ユーザプログラムに対して監視を行い，システムに危険が及ぶような状況になった場合は実行を停止しなければなりません．近年の国際情報オリンピックで用いられているジャッジシステム MOE は ptrace を用いてユーザプログラムを監視します．しかし，ptrace を用いると各々のシステムコールに対してどのような動作をするか決定しなければならず，また介入を行う必要が発生するために速度の低下も招きます．Imo Judge では出来る限りユーザプログラムを通常の状態に近い状態で実行するため ptrace は用いず，カーネルレベルで処理を行う ulimit や cgroups を用いてユーザプログラムの制限を行います．

メモリを食いつぶす攻撃手法

ヒープメモリを多量に確保する攻撃手法です．多量のスワップが発生しそれらの影響でジャッジサーバの動作が不安定になることがあります．ulimit ではメモリの制限ができないため cgroups を用いてメモリの制限を行います．制限をかける対象は Virtual Memory ではなく Resident Memory である必要があります．特に Java を実行する場合は Virtual Memory に対して制限をかけた場合，起動さえしない場合があるので注意が必要です．

ディスクを食いつぶす攻撃手法

ディスク書き込みをし続けることによりディスクの残容量を少なくする攻撃手法です．ジャッジサーバで予期せぬエラーを発生させる場合があるので，ulimit を用いて制限を行います．

fork を用いた攻撃手法

Fork 爆弾 と呼ばれる攻撃手法です．ulimit を用いてプロセス数の制限を行います．Java は複数のプロセスを生成するため厳しいプロセス制限を行うと Java プログラムを実行することができません．また Fork 爆弾は 1 つずつプロセスを kill しても全て終了させることが (kill している間に次々と新しいプロセスが生成するため) 困難であるので，kill -1 を用いて一掃します．

コンパイルエラーを用いた攻撃手法

C++ の template は深さ制限がなければチューリング完全であるのでコンパイルが停止しないことがあります．それどころか Warning を履き続けるようなソースコードを作ることも可能であるので，適切にそのような状況があることを考えてコンパイル処理を書かなければなりません．具体的にはコンパイルに時間制限を設け，コンパイルエラーの出力は適切に切り落とす必要があります．

kill を用いた攻撃手法

ユーザプログラムを監視するプログラムがユーザプログラムと同じ権限で動いている場合，ユーザプログラムによって kill が成功してしまいます．その時はユーザプログラムによる攻撃なのか，ジャッジプログラムがバグによって終了したのかが判断できません．よって，ジャッジプログラムを別の権限で動かす必要があります．

/tmp, /var/tmp を用いた攻撃手法

/tmp, /var/tmp にプログラムを書き込むプログラムを送り，次にそれらのファイルを include するプログラムを書くと一見ショートコーディングにできます．初代 Imo Judge では /tmp のみの削除を行なっていたため，iwiwi 先生に /var/tmp に書きこまれ攻撃が成功してしまいました．

Imo Judge の今後

今後，Imo Judge は UI と API を用いて分離しシステムの安全性を保ちながら第三者が UI を作ることができるようにする予定です．また，テストケースを別々にジャッジキューに入れることによってジャッジ速度の向上を図ろうと考えています．