日時：2007年 3月 1日(木) 18:30 から
場所：東京工業大学 大岡山キャンパス 西8号館Ｗ棟10階1008号室 （地図）
話者：
岩崎 敏 (東京工業大学)
話題：
プログラム盗用発見システム Dr.Plag
概要：
他人のプログラムをそのまま写す、または簡単な偽装工作によって写すことをプ
ログラム盗用(Plagiarism)という。プログラム盗用は初等プログラミング教育の
現場において、プログラミング技術習得の大きな妨げとなる。学生の提出したプ
ログラムを人手で盗用したかどうかを判定するのは、学生が多人数になると困難
であるからである。既存の研究は大きく分けて２つに分類される。２つのプログ
ラムの字句構造を比較する手法と、プログラムの意味的構造を抽出し比較する手
法である。前者は、２つのプログラムを字句解析し抽出したトークン列の共通部
分を計算し、プログラム盗用を発見する。この手法は盗用発見に要する時間は速
いが、トークン列を変化させるような字面の変更に対応できないという欠点があ
る。後者の手法は２つのプログラムの意味構造を比較する。意味構造として、プ
ログラムの依存関係をグラフとして表現したプログラム依存グラフを用いる。そ
して共通部分グラフを計算することでプログラム盗用発見する。この手法は字句
構造を比較する手法と比較して、精度が高いが、計算コストがかかるという問題
がある。本研究の提案する手法は意味構造を比較する手法である。既存の手法を
異なる点はプログラム依存グラフではなく、オブジェクト指向言語の特徴をより
詳細に表現可能なグラフであるシステム依存グラフを用いることである。さらに
精度を向上させるために、システム依存グラフのノードをより細粒度なものにし
た。グラフを木に変換するヒューリスティックを用いることで、最大のネックで
ある計算コストを大幅に軽減した。グラフを木に変換する際にバックエッジな
どの欠落する情報は、ノードの属性としてノードに付加することにより精度の低
下を防ぐ。木の共通部分を求めるアルゴリズムは、基本的にはTop Down
Unordered Subtree Isomorphismを用いる。このアルゴリズムに加えて、無駄な
部分木対の比較を減らすために木の葉、枝に順序付けをし計算コストのより小さ
いTop Down Ordered Subtree Isomorphismを併用する。その他にも識別子の情報
も部分的に用いるヒューリスティクやノード数の大きい部分木を優先的に探索す
るなどのヒューリスティックを用いることにより計算コストを軽減させた。実験
では字句構造を比較する手法では発見できないプログラム盗用を、本システムで
は発見できることを実証した。また人手との比較では採点者が発見できなか
ったプログラム登用を発見することができた。計算コストの評価実験では実用
的な時間で計算可能なことを実証した。