2009年10月30日金曜日

[Goose] プログラム解析技術 - 動的解析

前回のエントリでは、Gooseが解答を添削する際に利用していた技術として、プログラムの静的解析技術を紹介しました。

しかし、Javaなどの手続型プログラミング言語において、プログラムの静的解析だけでその挙動を完全に把握するのは非常に困難です。このため、Gooseでは静的解析が完了した後に、プログラム全体を実際に実行して動作を確認します。

空欄を含むプログラムと、空欄の内容については静的解析の段階で合成されますので、その結果をもとにオンラインでプログラムをコンパイルし、標準的なJavaの単体テストフレームワーク (JUnitなど) を利用したテストを実行できます。特殊な静的解析が必要でない場合、出題者は通常のプログラムと単体テストプログラムを用意し、通常のプログラムのいくつかに空欄を作成するだけで、新しい問題を作成できます。

なお、Gooseはクラウド上でも稼働することを前提に作成されています。このような場合、受講者が不正なプログラムを作成した際に、それを実行するとサーバに損害を与えることも可能となってしまいます。このような損害を回避するため、受講者の作成したプログラムに対して、実行時にいくつかの制限をかけられるようになっています。

サンドボックス実行環境

サンドボックス実行環境は、解答されたプログラムをGooseが実行(動的解析)する際に利用する環境です。この環境ではプログラムが特定の機能を利用しようとした際に、その利用を制限したり別の処理を実行させたりすることができます。受講者が環境に損害を与えるプログラムを作成した際に、プログラムの実行を停止 したり、無害な処理に書き換えて実行したりすることができます。

サンドボックス実行環境のイメージ。解答されたプログラムから利用可能な機能を制限している。

また、このサンドボックスは問題ごとに個別の設定を行えます。このため、一部のプログラムで特定のネットワークへの接続を許したり、コンソールへの出力を記録してそれをテストの対象としたりする、などといった使い方も可能です。

無限ループ解析

Gooseは解答されたプログラムを実際に実行しますが、そのプログラムの中に無限ループや非常に時間を要する処理が含まれていると、サービスを正常に稼働させられなくなってしまいます。このような処理は静的解析で検出するのが非常に困難で、Gooseでは動的解析の一環として無限ループの検出を行っています。

解答されたプログラムがコンパイルされる際、Gooseはクラスファイルに対して「チェックポイント処理」というものをプログラムの様々な個所に挿入します。このプログラムを実行すると、チェックポイント処理が何度も実行されることになり、Gooseはこの処理が行われた回数や最初のチェックポイント処理からの経過時間をもとに、サービスに損害を与えそうなプログラムを検出します。

サービスに損害を与えそうだと判断されたプログラムは、その場で実行が強制的に停止されます。そしてその解答は「時間内に動作が完了しなかった」という理由で不正解という扱いになります。Gooseでは、このような方法でサービスの可用性を向上しています。

0 件のコメント:

コメントを投稿