Paper - 京都産業大学

SCIS 2015
The 32nd Symposium on
Cryptography and Information Security
Kokura, Japan, Jan. 20 - 23, 2015
The Institute of Electronics,
Information and Communication Engineers
c
Copyright ⃝2015
The Institute of Electronics,
Information and Communication Engineers
コーディングスタイルの特徴量を用いた
初心者プログラマーを対象にした著者解析
The authorship analysis for the novice programmers from characteristics of coding style
北川裕基 ∗
Yuki Kitagawa
福本大 †
Dai Fukumoto
玉田春昭 ‡
Haruaki Tamada
あらまし学生のプログラミング習得を目的とした課題で，他人の書いたコードをコピーする盗作と
いった問題が多発している．本稿の目的は，学生のプログラミング演習課題における簡易なプログラム
を対象に，著者解析を行うことである. 著者解析は誰がそのコードを書いたかを明らかにする．従来は，
コピー関係にあるソースコードを発見することに注力されていた．本稿においては, そこから一歩踏み込
んで，オリジナルがどれかを特定しようと試みる．そのために，各プログラムの作成者が誰であるのか
を著者解析により判定する．本論文では，プログラムから 56 個の表層的特徴量を取り出し，クラスタリ
ングを行う. 表層的特徴とは，ソースコードの長さや名前の付け方などプログラムの見た目の特徴である．
クラスタリングは，教師なし機械学習を用いて，分類分けする．クラスタリングの結果，指定したソー
スコードと同じ作成者のソースコードを絞り込むことができた．
キーワード著者解析，コーディングスタイルの特徴量，クラスタリング，k-means
1
背景と目的
師なし機械学習を用いる. 教師なし学習により，盗用検
出の精度を上げるだけでなく，プログラマの特徴をジャ
学生のプログラミング習得を目的とした科目プログラ
ンル分けすることが期待できる．
ミング演習において，受講している学生が演習課題に対
し，他人の書いたソースコードをコピー&ペーストなど
2
により盗用するといった問題がある．このような盗用に
関連研究
より, 教員が正しく成績評価できない，受講生の習熟度を
武田らは，初心者プログラマーを対象に，コーディン
把握できないといった問題が発生する．この問題に対し
グスタイルの特徴から盗用検出を行った [3]．学生の演習
て，受講生本人が作成したソースコードか確認しなけれ
課題のような小規模なソースコードを対象とした盗用の
ばならない．したがって，提出された課題のソースコー
検出が目的である．インデント，演算子などのコーディ
ドを誰が作成したものかを調べる必要がある．
ングスタイルに着目し，56 項目の特徴量として抽出し，
本稿では，プログラミング演習課題における簡易なプ
盗用の発見に用いた．今回は，コーディングスタイルの
ログラムを対象に制作者を特定する著者解析を行う．し
特徴量を利用するが，目的が盗用検出ではなく個人を特
かし，課題で提出されたプログラムはアルゴリズムの自
定する著者解析である．
永井らは，C や C++の大量のプログラムコードを対
由度が低く，アルゴリズムから個人を特定するのは困難
象に，ソースコードの見た目の特徴を抽出し，機械学習
である．
今回は，インデントや演算子などの特徴量を著者解析
でプログラムコードの分類を行った [2]．変数の命名規
に用いる．また，盗用検出の精度を上げるため，前回の
則やコーディングスタイルなど，見た目によって表す特
課題での特徴量を機械学習に適応させる．機械学習は教
徴量を大量のプログラムコードから抽出し，機械学習を
∗
†
‡
用いて分類分けを行った．また，見た目に基づいて分類
京都産業大学コンピュータ理工学部，京都市北区上賀茂本山, Motoyama, Kamigamo, Kita-ku, Kyoto-shi, Kyoto
京都産業大学コンピュータ理工学部，京都市北区上賀茂本山， Motoyama, Kamigamo, Kita-ku, Kyoto-shi, Kyoto
京都産業大学コンピュータ理工学部，京都市北区上賀茂本山，Motoyama, Kamigamo, Kita-ku, Kyoto-shi, Kyoto
する際に見た目のどのような特徴が効いているのかを調
べる実験を行った．その結果，見た目の特徴によって 9
割程度の認識度でプログラムの著者解析を行えることを
1
確認した．今回は，プログラミングを習い始めた初心者
である．例えば，括弧前後に空白や改行があるか
が対象なので使えない．
どうかである．括弧前後の書き方に特徴が現れる
ことが多い．
提案手法
3
コメントコメントのバイト数や行数の特徴量である．プ
3.1
概要
ログラムの内容へのコメント以外にも，作成時に
本研究の目的は，ソースコードの作成者を明らかにす
工夫した点などがある．
る著者解析であり，作成者ごとにソースコードを分類す
名前関数名やクラスの名前の特徴量である．例えば，名
ることである．つまり，複数のソースコードを入力とし
前に大文字，小文字，混在の割合や数字，アンダー
て受け取り，作成者ごとに分類されたソースコードを出
スコアの含まれる割合などである．関数名やクラ
力することが目的である．この目的を達成するために，
スの名前の命名には著者の嗜好が強く反映される
分類のための情報と，分類法を定義しなければならない．
と考えられる．
ここでは，分類のための情報として，武田らが用いた特
徴量を用い，分類法は分割最適化クラスタリング手法を
演算子演算子の前後にある空白などの特徴量である．演
利用する．
算子の周りに空白をおくかどうかなどは書き手の
本研究の対象は，プログラミングを学習し始めた初学
癖を表すと考えられる．
者であり，学習者らが提出した課題のプログラムである．
3.3
そのため，アルゴリズムでの区別は困難である．武田ら
著者解析手法
本稿では，ソースコード中の特徴量を基に著者を特定
が用いた特徴量は，インデント量や名前のつけ方など，
表層的な特徴であるため，初学者であっても違いが生じ
する方法を提案する．手順を大きく前半と後半に分ける．
得る．
前半では著者解析を行うため，クラスタリングを行う．
一方，分類法として，教師なし学習の一つであるクラ
この方法を図 1 に示す．後半では，得られたクラスタリ
スタリングを用いる [1]．これは，学習者ごとにソース
ング結果から著者解析を行う方法を示す．この方法を図
コードを分類するという目的から，訓練データが存在
2 に示す．
しないためである．また，クラスタリングには，階層的
前半ではクラスタリングを行う方法について，図 1 に
手法と分割最適化手法の２種類に大別される．階層的手
従って説明する．ここでは，調査対象となるソースコー
法は，最初に１つの要素のみを含むクラスタを作ってお
ドの集合を S とし，その要素を sk ∈ S(0 ≤ k ≤ l)
き，クラスタを統合していく手法である．分割最適化手
とする．そして，sk 中の何らかの特徴 mi ∈ Mall (0 ≤
法は，全ての要素を含むクラスタを，決められた評価関
i ≤ n) を規定の方法 fi により取り出す (mi = fi (s))．
数に従って分割していく方法である．本研究では，代表
また，得られた特徴 mi を何らかの意味で分類し，特徴
的な分割最適化手法である k-means を用いる．この方法
量群 Mj (0 ≤ j ≤ m) を得る．Mj は mi を要素とする
は，クラスタの平均から，与えられたクラスタ k 個に分
集合である．そして，mi は唯一の Mj に所属し，複数
類する方法である．また，最終的なクラスタ数はギャッ
の特徴量群に所属することはない．提案手法では，ま
プ統計量により求める．
ず，mi ∈ Mall に所属する特徴量でクラスタリングす
3.2
る．その結果を Call = {call1 , call2 , ..., callg } とする．次
武田手法
に，mi ∈ Mj に所属する特徴量で分類する．その結果を
本稿では，武田らのコーディングスタイルの特徴量 [3]
Cj = {cj1 , cj2 , ..., cjg } とする．このとき，m + 1 のクラ
スタリング結果が得られ，それぞれのクラスタの数は g
である．
を用いる．抽出される 56 種類の特徴量は，5 つの特徴量
群に分類される．それら５つを次に示す．
次に，後半のクラスタリング結果から著者を解析する
インデント量と深さファイル全体の見た目を表す特徴
方法を次の通り説明する．
量である．多くのプログラムはスコープレベルが
増えるごとにインデントの深さが大きくなる．そ
1. 調査したいソースコード st を一つ選択する．
のため，スコープとインデントをとることにより，
2. st が所属するクラスタ ct を Call から選択する（st ∈
一貫したスコープレベルとインデントの数の関係
ct ）．
性を調べる．
3. st が所属するクラスタを C0 , C1 , ..., Cm からそれぞ
れ選択し，その結果の集合を C t = {c0a , c1b , ..., cmx }
括弧前後の書き方クラスや関数の開始や終了，条件な
どのブロックを区別する要素である括弧の特徴量
(0 ≤ a, b, ..., x ≤ g) とする．
2
4. {sk |sk ∈ ct ∧ sk ̸= st } について次の調査を行う．
ただし，誤判定はネガティブな評価を不当に与えること
になるため，避けるべきである．以上のことから，再現
(a) sk が所属するクラスタを C0 , C1 , ..., Cm から
それぞれ選択し，結果となる集合を C k とす
率を犠牲にしても，適合率を上げることを目指す．
る．
4
(b) C t と C k で一致するクラスタを調べ，その数
を α とする．このとき，一致率を
α
m
ケーススタディ
ここでは，大学の演習で提出されたソースコードから
とする．
著者を特定できるかを実際に確認する．対象は，京都産
(c) 一致率が閾値以上であれば，st と sk は同じ
著者が書いたものであると判定する．
業大学で開講されている Java のプログラミング演習で
課された 21 の課題である．これらのソースコードを対
象に，それぞれの課題で，誰がそのソースコードを提出
著者解析では，全ての特徴量を用いた場合と，それぞ
したのかを判定する．
れの特徴量群を用いた場合ごとにクラスタリングして
なお，提出数は図 3 に示す通りである．横軸が課題，
おく（Call と Cj (0 ≤ j ≤ m)）．図 2 の Call が全ての
特徴量を用いたクラスタリング結果を表しており，C0 ，
縦軸が提出数である．この図からわかるように，授業の
C1 がある特徴量群を用いた場合のクラスタリング結果
進度に従って提出数が下がっている．最後の課題の提出
を示している．そして，Call において，着目すべきソー
率が上がっているのは，当該課題が最終課題であり，成
スコード st と同じクラスタに所属するソースコードが，
績に大きく影響する課題であるためである．
どの程度 Cj において一致するかの確率で著者解析を行
このケーススタディでは，全課題の提出率が 80%を超
う．図 2 において，sc に着目したとする．この場合，sa
える学生だけを対象に提案手法を適用して，提案手法の
は，C0 , C1 ともに同じクラスタに所属する．そのため，
有効性を調査する．クラスタ数はギャップ統計量より 7
sa の一致率は 1.0 となる．また，sd は C0 のクラスタに
は存在せず，C1 のクラスタに存在する．そのため，一
とする．なお，このケーススタディでは，誰がそのソー
致率は 0.5 となる．
特定を試みる．なお，対象となる人数は，10 人，ソース
スコードを書いたのかわからないという前提で，著者の
コード数は 223 である．
なお，閾値は与えられるものとし，ドメインやソース
このケーススタディでは，Mall を武田らが用いた 56
コードの数，特徴量の数により変動して決める必要が
個のコーディングスタイルの特徴量を用いる．また，特
ある．
徴量の分類 Mj も武田らの定義に従うものとする．その
3.4
著者解析の評価尺度
ため，0 ≤ j ≤ 5 となる．
ここでは，著者解析の評価尺度について考える．一般
対象のソースコードの中からランダムに st を選択す
的に，予測結果の評価尺度は，適合率 (precision) と再
る．そして，Call でのクラスタリング結果で分けられた
現率 (recall)，F 値 (F-value) で行われる．適合率は正
一つのクラスタ内から st と同じ著者であるソースコード
しいと予測した結果のうち，実際に正しいものの割合
を絞り込む．これを２つのソースコードに対して施行し
を表し，再現率は正解集合のなかから正しいと予測され
た．それぞれ，s1 ，s2 とする．なお，閾値は 0.25, 0.50,
た割合を表す．この評価には，著者 A であると判定し
0.75, 1.00 とした．結果となる適合率，再現率，F 値を
た結果が正しい場合（true positive）と正しくない場合
表 1 に示す．空欄となっているセルは，計算結果が不定
となることを示している．
（false positive），そして，著者 A でないと判定した結果
が正しい場合（true negative）と正しくない場合（false
s2 を見ると，閾値が小さい場合は適合率が多いもの
negative）の４つの分類から求められる．
ここでは，適合率をできるだけ向上させることを目指
の，閾値を挙げていくことで，適合率が上がっていく．
す．適合率を向上させるには，誤判定をできるだけ減ら
されるソースコードは少なくなるものの，誤検出 (false
すことが必要である．また，適合率のみを向上させると，
positive) も少なくなるため，結果として適合率が増加し
ていくと考えられる．
閾値が上がれば，それに伴い，同一著者であると判定
予測できないものがあるものの，著者解析の結果がほぼ
しかし，一方で，s1 のように閾値を上げていくことで，
正しいということになる．
同一著者であると予測される集合が少なくなっている．
現実的な問題として，演習課題のプログラムに提案手
法を適用する場合を考える．もし，提出課題の中にコピー
そして，最終的に閾値を 1 としたとき，予測集合が空集
が見つかったとき，従来は，著者が誰かを見つける方法
合となるため，適合率が不定となる．
はなかった．そこで，提出課題や，以前の提出課題を対
このように，２つのケースの調査では，最適な閾値を
象に提案手法を適用し，もし，著者が特定できれば，流
求められないため，今後，より多くのケーススタディを
出元が特定でき，より正確な指導が行えるようになる．
試行していく必要がある．
3
表 1: ケーススタディ1 の著者解析結果
s1
s2
5
適合率
0.222
0.222
0.25
再現率
0.400
0.400
F値
0.286
0.286
適合率
0.000
0.500
0.5
再現率
0.000
0.400
F値
0.444
適合率
0.000
0.500
0.75
再現率
0.000
0.200
F値
適合率
0.286
1.000
1.00
再現率
0.000
0.200
F値
0.333
まとめ
本稿では，初心者プログラマーを対象にコーディング
スタイルの特徴量をクラスタリングすることにより，著
者解析を行った．提案手法は，指定したソースコードと
同じ著者のソースコードを他のソースコードの中から絞
り込むのに役立つ．しかし，対象が初心者かつ，課題の
ソースコードであるため，課題に左右される場合がある．
今後の課題として，より大規模なケーススタディや，
提案手法の評価，対象のソースコード集合を変更しての
調査などが挙げられる．
参考文献
[1] Toby Segaran: 集合知プログラミング, オーム社
(2008).
図 1: クラスタリング結果を求める手順
[2] 永井洋一, シムウォンボ, 三輪誠, 近山隆: 機械学習
を用いたプログラムの表層的特徴による分類, 第 9 回
プログラミングおよび応用のシステムに関するワー
クショップ (2010).
[3] 武田隆之, 牛窓朋義, 山内寛巳, 門田暁人, 松本健一:
Call!
s a!
sb!
sc!
C0!
s a!
sb!
sc!
C1!
s a!
sb!
sd!
se!
sf!
s g!
sh!
!!
sd!
!!
コーディングスタイルの特徴量とソースコード盗用
図 2: クラスタリング結果からの著者解析
との関係の分析, 情報処理学会 (IPSJ SIG Technical
Report 2010)(講演番号 2010-SE-167(8)) (2010).
図 3: 課題ごとの提出数
4
!!

Download Report