識別子の共起関係に基づく類似コード検索法の提案と

識別子の共起関係に基づく
類似コード検索法の提案と
欠陥検出への適用
大阪大学大学院情報科学研究科
服部剛之，吉田則裕，早瀬康裕，
肥後芳樹，松下誠，楠本真二，
井上克郎
Department of Computer Science,
Graduate School of Information Science & Technology,
Osaka University
1
概要

キーワードを自動的に抽出し，類似コードを検
索する手法を提案する
 grep等のキーワード検索では，適切なキーワードを
決めるために対象ソフトウェアの知識が必要
 ソースコードの一部を与えることで，キーワードを自
動的に抽出
 識別子の共起関係を利用

提案手法を欠陥検出に適用し，実験を行った
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
2
目次

研究の背景
 欠陥の修正
 類似コード検索
研究の目的とアプローチ
 提案手法の説明

 手法の概要
 作成したシステムの説明

適用実験
 欠陥検出への適用

まとめと今後の課題
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
3
欠陥の修正
ソフトウェア保守作業の効率化が重要な課題
 ソフトウェアには，コピーアンドペーストによって生成さ
れたソースコードが存在

 ソフトウェア保守の際に，複数箇所に同様の修正を加える必
要が生じることがある

同様の欠陥が存在する箇所を特定する方法が必要
ソースコードの一部が
類似した箇所が存在
同様の欠陥が存在
欠陥が存在
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
4
類似コード検索(1/2)

ソースコードの集合から，一致もしくは類似した
コード片(ソースコードの断片)を検索する
 クエリ(検索質問)を与えることで検索を行う
検索結果
ソースコードの集合
ユーザ
類似コード検索
クエリを指定
クエリ
一致もしくは類似したコード片
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
5
類似コード検索(2/2)

ソースコードの集合から，一致もしくは類似した
コード片(ソースコードの一部)を検索する
 クエリ(検索質問)を与えることで検索を行う

キーワードをクエリとして与える方法
例)grep

コード片をクエリとして与える方法
例)コードクローン検索ツール Libra[1]
[1] 泉田聡介，植田泰士，神谷年洋，楠本真二，井上克郎，
“ソフトウェア保守のための類似コード検査ツール”，
電子情報通信学会論文誌，Vol.J-86-D-I(No.12):pp.906–908，2003.
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
6
grepを用いた類似コード検索

手順
ユーザがコード片からキーワードを発見する
2. grepによって，キーワードが出現する箇所を検出する
3. 検出した箇所を基にキーワードを含むコード片を特定する
1.

利点
 名前などの識別子の情報が利用可能

問題点
 適切なキーワードを発見することが困難
 対象のソースコード集合に対する知識が必要
 同義語などのキーワードの変化形を検出することが困難
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
7
Libraを用いた類似コード検索

手順
1.
2.

利点



ユーザがコード片をクエリとして与える
コードクローン検出ツールCCFinder[2]を用いてクエリのコードクローン
を検出する
キーワードを考えなくても検索が可能
キーワードの変化形にも対応可能
問題点

クエリとコードクローンの関係にある類似コードしか検出できない

コード片の挿入，削除などの差異があると検出できない
[2] T. Kamiya, S. Kusumoto, and K. Inoue,
"CCFinder: A multi-linguistic token-based code clone detection system
for large scale source code", IEEE Transactions on Software Engineering,
Vol.28(No.7):pp.654–670, 2002.
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
8
研究の目的とアプローチ

目的
 キーワードの発見を自動的に行い，類似コードの検索を行う


キーワードの変化形も考慮する
アプローチ
 識別子の共起関係を利用することで，コード片からキーワー
ド，キーワードの変化形を自動的に抽出する
入力
ソースコードの集合
クエリとして与えるコード片
提案手法
出力
抽出部
キーワード等の抽出
照合部
類似コードの検索
クエリと類似した
コード片の集合
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
9
提案手法の概要(1/2)

抽出部
クエリとして与えられたコード片から，コード片を特徴付ける
識別子(特徴語)を求める
2. ソースコード集合から，クエリとして与えられたコード片と特
徴語が同じ，もしくは特徴語が類似したコード片を抽出する
1.
クエリとして与えられたコード片
特徴語
…
host = host_alloc( ... );
log ( ... );
if (!add_host(host)) {
// scan_host(host)
// is missing!
}
…
手法が抽出したコード片
…
node = node_alloc( ... );
if ( ... == 0){
return;
}
if (!add_node(node)) {
// scan_node(node)
// is missing!
}
…
特徴語
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
10
提案手法の概要(2/2)

照合部
クエリとして与えられたコード片と手法が抽出したコード片に
対して，特徴語を含む文の集合を比較する
2. 特徴語を含む文の構文情報が一致した場合，クエリとして与
えられたコード片と類似したコード片として検出する
1.
クエリとして与えられたコード片
手法が抽出したコード片
…
…
node = node_alloc( ... );
host = host_alloc( ... );
log ( ... );
構文情報が一致 if ( ... == 0){
return;
類似したコード片
if (!add_host(host)) {
}
// scan_host(host)
if (!add_node(node)) {
// is missing!
// scan_node(node)
}
// is missing!
…
}
…
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
11
作成したシステムの概略図
識別子情報の抽出
ソースコードの集合
抽出部
識別子の同義語の導出
クエリ
特徴的な箇所の抽出
構文情報の取得
照合部
ユーザ
ユーザが行単位で
コード片を選択
特徴的な箇所の構文の比較
ユーザが与えたコード片と類似した
コード片を持つモジュールのリスト
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
12
識別子情報の抽出

ソースコードの集合からモジュール単位で識別
子を抽出する
 予約語，型名を表す識別子は除外

モジュールごとに識別子の出現回数を計算する
 識別子情報
 識別子名
 対象モジュール
 出現回数
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
13
識別子の同義語の導出

識別子の共起関係に基づいて，識別子のクラス
タリングを行う
 識別子の共起回数の分布が類似している場合，同じ
クラスタに含まれる
 Jensen-Shannon

divergence[3]を用いて，類似度を表す
同じクラスタに属する識別子を同義語と定義する
例）識別子aと識別子bの共起回数の分布
識別子a 識別子b 識別子c 識別子d 識別子e
識別子a
a1
a2
a3
a4
識別子b
b1
b2
b3
b4
a2，a3，a4とb2，b3，b4が類似している場合，識別子aと識別子bを同義語とする
[3] I. Dagan, L. Lee, and F. C. N. Pereira,
"Similarity-based models of word cooccurrence probabilities",
Machine Learning, Vol.34(No.1-3):pp.43–69, 1999.
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
14
特徴的な箇所の抽出

モジュールごとに特徴語を求める
 モジュール単位で閾値を定める
 ソースコード集合固有の基準値をモジュールの規模に応
じて正規化する
 識別子の出現回数が閾値を上回る場合，そのモジ
ュールにおける特徴語と設定した

モジュール中の特徴語を含む行を特徴的な箇
所と設定した
 照合部で比較を行う対象として用いる
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
15
作成したシステムの概略図
識別子情報の抽出
ソースコードの集合
抽出部
識別子の同義語の導出
クエリ
特徴的な箇所の抽出
構文情報の取得
照合部
ユーザ
ユーザが行単位で
コード片を選択
特徴的な箇所の構文の比較
ユーザが与えたコード片と類似した
コード片を持つモジュールのリスト
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
16
構文情報の取得
入力コード片から特徴的な箇所を抽出する
 それぞれの特徴的な箇所において，構文情報
を取得する

 構文情報の設定
 出現している特徴語の集合
 文の種類
 変数宣言などの宣言文
 条件文，繰り返し文などの条件節
 break文，return文などの補助制御文
 それ以外の文
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
17
特徴的な箇所の構文の比較(1/2)

入力コード片と各モジュールについて，特徴的な箇所
の構文情報を比較する
 構文情報の対応付けを行う
同義語
 特徴語が一致もしくは同義語の関係にある {host_alloc, node_alloc}
{add_host, add_node}
 文の種類が一致する
特徴語が同義語の関係
比較対象
文の種類が一致
…
…
node = node_alloc( ... );
host = host_alloc( ... );
if ( ... == 0){
log ( ... );
return;
if (!add_host(host)) {
}
// scan_host(host)
if (!add_node(node)) {
// is missing!
// scan_node(node)
特徴語が同義語ではない
}
文の種類が一致しない // is missing!
…
}
…
入力コード片
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
18
特徴的な箇所の構文の比較(2/2)

構文情報の対応付けの状態によって，類似し
たコード片を含むモジュールを検出する
 入力コード片の特徴的な箇所の構文情報すべてが，
対応付け可能である場合
入力コード片
比較対象
…
…
node = node_alloc( ... );
host = host_alloc( ... );
log ( ... );
対応付け可能 if ( ... == 0){
return;
if (!add_host(host)) {
類似したコード片を含むモジュール
}
// scan_host(host)
if (!add_node(node)) {
// is missing!
// scan_node(node)
}
// is missing!
…
}
…
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
19
適用実験目次
実験概要
 実験対象

 日本語入力システム
かんな
 ソフトウェア部品検索システム SPARS-J

実験の設定
 クラスタリングの閾値
 入力コード片
評価基準
 実験結果
 考察

Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
20
実験概要
実験対象に存在している欠陥の箇所をクエリとする
 クエリと同じ欠陥を含むコード片がどの程度検出され
ているか調べる

コード片の1つを
クエリとして与える
同じ欠陥を含む
コード片の集合
提案手法
クエリ
検出できた数を調べる
クエリと類似したコード片を
持つモジュール
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
21
実験対象

日本語入力システムかんな
 Version3.6，Version3.6p1間でバッファのオーバー
フローを検出するコードが追加された
 コードが追加される箇所を欠陥の箇所とした

ソフトウェア部品検索システム SPARS-J
 複数の関数において型キャストの追加が行われた
 2004/5/27で同時に修正が行われている
 型キャストの追加が行われる箇所を欠陥の箇所とした
モジュールの単位を関数単位とした
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
22
実験の設定(クラスタリングの閾値)

同義語を求める際のクラスタリングの閾値を変化させて実験を
行った


クラスタリングの閾値を求める手順
1.
2.

共起回数の分布の差異をクラスタ間距離とする
初期状態のクラスタ間距離の最大値を求める
1の値のx%を閾値とする
Xを0%～100%まで10%刻みに変化させ実験を行った
例)初期状態のクラスタ間距離の分布
クラスタa クラスタb クラスタc クラスタd
1
クラスタa
2
4
3
5
クラスタb
クラスタc
クラスタd
-
割合を50%に設定した場合，
閾値は6×0.5=3となる
6
-
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
23
実験の設定(入力コード片)

後のバージョンで修正が行われる箇所とその
前後合わせて3行を入力のコード片とする
 入力コード片の総数
 かんな：21個
 SPARS-J：75個
修正前
修正後
修正箇所
key.data = package;
key.size = size + 1;
key.data = package;
key.size = (u_int32_t)(size + 1);
/* Acquire a cursor for the database. */
dbcp = get_cursor(&DBlist[PACKAGEDB]);
/* Acquire a cursor for the database. */
dbcp = get_cursor(&DBlist[PACKAGEDB]);
修正が行われる箇所の前後1行ずつを
追加して3行を入力コード片とする
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
24
評価基準

それぞれの入力コード片について，適合率，再
現率を求めた
 正解集合は実験対象で述べた欠陥を含むコード片
とした
× 100 (%)
適合率：システムが検出した正解集合のコード片を含む関数の数
システムが検出した関数の数
× 100 (%)
 再現率：システムが検出した正解集合のコード片を含む関数の数
正解集合のコード片を含む関数の総数

正解集合の関数
システムが検出した関数
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
25
実験結果
かんな
ＳＰＡＲＳ－Ｊ
入力コード片の
適合率の平均
入力コード片の
再現率の平均
0%
8.05%
0.36%
18.55%
10%
22.67%
18.28%
39.45%
81.95%
20%
7.01%
87.19%
30%
21.09%
100.00%
30%
7.33%
88.31%
40%
9.64%
100.00%
40%
7.33%
88.31%
50%
9.64%
100.00%
50%
7.33%
88.31%
60%
9.55%
100.00%
60%
7.23%
89.53%
70%
9.55%
100.00%
70%
7.23%
89.53%
80%
9.55%
100.00%
80%
7.23%
89.53%
90%
9.55%
100.00%
90%
7.23%
89.53%
100%
9.55%
100.00%
100%
7.23%
89.53%
閾値として
設定した割合
入力コード片の
適合率の平均
入力コード片の
再現率の平均
0%
17.03%
5.51%
10%
89.86%
20%
閾値として
設定した割合
適合率は低いが，20%以降高い再現率が得られた
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
26
結果と考察

入力コード片の再現率の平均が高い値となっていた
 欠陥を漏れなく検出することが要求される条件下では，提案
手法は有効

入力コード片の適合率の平均は低い値となっていた
 欠陥が含まれていなくても，同じ構文であれば欠陥を含むコ
ード片と判定されてしまう


欠陥と関係がないコード片を除外することが必要
閾値として設定した割合が，10%～20%の間で再現
率が大きく変化している
 閾値の基準となる値を設定できると期待される
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
27
まとめ

識別子の共起関係に基づいて類似コード片を
検索する手法を提案
 コード片から自動的にキーワードを発見
 同義語を用いて，キーワードの変化形にも対応

提案手法を欠陥検出に適用し，実験を行った
 実験対象はC言語のソフトウェア
 かんな
 SPARS-J
 適合率は低いが，再現率は高い結果
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
28
今後の課題

出力結果を分類して評価を行う必要がある



同じ欠陥を含むモジュール
処理内容が同じで欠陥を含まないモジュール
異なる処理内容のモジュール

他のプログラミング言語で開発されたソフトウェアを対象とした
実験を行う必要がある

特徴語検出における閾値の妥当性を評価する必要がある

構文情報の対応付けを行った効果について，評価する必要が
ある
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
29

Download Report