グラフマイニングアルゴリズムを用いた
ギャップを含むクローン抽出手法の提案
井上研究室
藤野陽平
2007/2/27
1
コードクローン
ソースコード中に存在する同一，もしくは類似したコード片
を同一システム中に持つコード片 (以降単にクローンと呼
ぶ)
コピー&ペースト等により生成される
ソフトウェア保守を困難にする
バグ修正などコード変更をする際、全てのクローンに対して変
更が必要
保守作業の手間が増大
クローンセット
2007/2/27
2
コードクローン検出ツール
CCFinder
クローンを対象とした保守支援ツール
検出ツール: CCFinder[1]
国内外の個人・組織に配布
配布先からのフィードバックを得ている
[1] 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, 28(7):654-670, 2002.
2007/2/27
3
CCFinderの問題点
問題点・・ギャップを含むクローンが抽出できないの
で、効率的に分析ができない
そうなるべきところが別々の短いクローンとして抽出される
目的・・CCFinderの出力を元に、ギャップを含むク
ローンを抽出する これらを１つのクローン
として抽出したい
ギャップ
2007/2/27
4
提案手法
ギャップを含むクローンを抽出する
2007/2/27
CCFinderが見つけたコード片をグラフのノードとする
グラフマイニングアルゴリズムを用いて、多頻度グラ
フパターン（ギャップを含むクローン）を抽出する
5
AGM(Apriori-based Graph
Mining)アルゴリズムの概要
グラフ１
グラフ２
１
１
３
２
４
１
２
３
５
４
頂点の数が1の多頻度グラフパターンを見つける
[2]猪口明博,鷲尾隆,元田浩:多頻度グラフマイニング手法の一般化.人工知能学会論文誌,vol19,No.5,pp. 368-378, 2004.
2007/2/27
6
AGM(Apriori-based Graph
Mining)アルゴリズムの概要
１
３
１
１
１
１
２
・・・・・
２
４
１
２
３
４
１
見つかった多頻度グラフパターンを組み合わせて、頂
点の数が1つ多い多頻度グラフパターンの候補を生成
する
[2]猪口明博,鷲尾隆,元田浩:多頻度グラフマイニング手法の一般化.人工知能学会論文誌,vol19,No.5,pp. 368-378, 2004.
2007/2/27
7
AGM(Apriori-based Graph
Mining)アルゴリズムの概要
グラフ1
グラフ2
１
１
３
２
４
１
２
３
５
４
生成した候補が多頻度グラフパターンかを確認する
[2]猪口明博,鷲尾隆,元田浩:多頻度グラフマイニング手法の一般化.人工知能学会論文誌,vol19,No.5,pp. 368-378, 2004.
2007/2/27
8
AGM(Apriori-based Graph
Mining)アルゴリズムの概要
グラフ1
グラフ2
１
１
３
２
４
１
２
３
５
４
これまでの操作を繰り返し、全ての多頻度グラフパターンを抽出する
[2]猪口明博,鷲尾隆,元田浩:多頻度グラフマイニング手法の一般化.人工知能学会論文誌,vol19,No.5,pp. 368-378, 2004.
2007/2/27
9
ギャップを含むクローン抽出手順
1.
2.
3.
2007/2/27
CCFinderが出力するクローンの位置情報を元
に、各クローンのコード片をノードとするグラフ
を作成する
作成したグラフ集合に対して、AGMアルゴリズ
ムを適用して多頻度グラフパターンを抽出し、
それをギャップを含むクローンとする
ギャップを含むクローンの位置情報を出力する
10
CCFinderが出力するクローンの
位置情報からグラフを作成する
ファイル１
１
ファイル２
１
２
３
２
※図に書かれている数字は、何番目のクローンセットに含まれ
るコードクローンかを表す．
オーバーラップしている
2007/2/27
11
CCFinderが出力するクローンの
位置情報からグラフを作成する
ファイル１
１
ファイル２
１
ファイル1に
対するグラフ
１
２
３
２
※図に書かれている数字は、何番目のクローンセットに 含ま
れるコードクローンかを表す．
2007/2/27
12
CCFinderが出力するクローンの
位置情報からグラフを作成する
ファイル１
１
ファイル２
１
ファイル1に
対するグラフ
１
ファイル2に
対するグラフ
１
２
３
２
※ノードに書かれている数字は、何番目のクローンセットに
含まれるコードクローンかを表す．
2007/2/27
13
CCFinderが出力するクローンの
位置情報からグラフを作成する
ファイル１
１
ファイル２
１
２
３
ファイル1に
対するグラフ
１
ファイル2に
対するグラフ
１
２
２
※ノードに書かれている数字は、何番目のクローンセットに
含まれるコードクローンかを表す．
2007/2/27
14
CCFinderが出力するクローンの
位置情報からグラフを作成する
ファイル１
１
ファイル２
１
２
３
ファイル1に
対するグラフ
１
２
ファイル2に
対するグラフ
１
２
２
※ノードに書かれている数字は、何番目のクローンセットに
含まれるコードクローンかを表す．
2007/2/27
15
CCFinderが出力するクローンの
位置情報からグラフを作成する
ファイル１
１
ファイル２
１
２
３
ファイル1に
対するグラフ
３
１
２
ファイル2に
対するグラフ
１
２
２
※２と３はオーバーラップしているのでエッジを引かない
※ノードに書かれている数字は、何番目のクローンセットに
含まれるコードクローンかを表す．
2007/2/27
16
多頻度グラフパターンを抽出し、そ
れをギャップを含むクローンとする
ファイル1に
対するグラフ
１
３
２
３
ファイル2に
対するグラフ
１
２
２
５
３
囲んだ部分がギャップを含むクローン
2007/2/27
17
抽出したギャップを含むクローンの
位置情報を出力する
ファイル1に
対するグラフ
ファイル2に
対するグラフ
１
１
２
２
３
３
ファイル１
ファイル２
濃いオレンジの部分がギャップ
2007/2/27
18
ギャップを含むクローン抽出手順
（まとめ）
入力:ギャップを含まないクローンの位置情報
ファイル１
１
ファイル２
出力：ギャップを含むクローンの位置情報
ファイル１
ファイル２
１
２
３
２
2007/2/27
19
実験
目的: どのようなギャップを含むクローンが抽出されるか調査
する
対象:Java，C言語で記述されたオープンソースソフトウェア
EJE,jasmin,javadjvu
f2j
CCFinderは30トークン以上のコードクローンを検出
グラフを構築するときに、メトリクスRNR[3]を用いる
Java:
C :
検出する必要がないクローンのフィルタリングが可能
例：連続した変数宣言、switch文のcaseエントリなど
閾値として0.5を用いる
挿入・削除・変更といった編集が加えられているクローンとそ
うでないクローンに分類
[3]肥後芳樹,吉田則裕,楠本真二,井上克郎:産学連携に基づいたコードクローン可視化手法の改良と実装,情報処理学会論
文誌,vol48,No.2,pp. 811-822, 2007.
2007/2/27
20
実験結果
EJE
f2j
jasmin
javadjvu
4
7
7
4
挿入・削除
2
7
7
4
変更
3
4
3
1
編集が加えられていないクローンセッ
ト数
1
26
10
9
編集が加えられたクローンセット数の
割合
80%
21%
41%
31%
編集が加えられたクローンセット数
内訳
ソフトウェアによって編集が加えられたクローンセット数の割合の違い
が大きい
編集が加えられていないクローンセットをフィルタリング出来るように
するなど改良の余地がある
2007/2/27
21
編集が加えられたクローンの例
クローンセット
CodeAttr init = new CodeAttr();
init.addInsn(new Insn(opc_aload_0));
init.addInsn(new Insn(opc_invokenonvirtual,
new MethodCP("java/lang/Object", "<init>", "()V")));
init.addInsn(new Insn(opc_return));
// Actual code to print string
CodeAttr doit = new CodeAttr();
// store refs in local variables
文が挿入さ
doit.addInsn(new Insn(opc_getstatic,
れている
new FieldCP("java/lang/System",
"out",
"Ljava/io/PrintStream;")));
doit.addInsn(new Insn(opc_astore_1));
doit.addInsn(new Insn(opc_ldc,
new StringCP(“Hello World”)));
doit.addInsn(new Insn(opc_astore_2));
// Loop index in var reg 3
doit.addInsn(new Insn(opc_bipush, 5));
2007/2/27
クローンセット
緑太字：コードが変更された箇所
CodeAttr code = new CodeAttr();
// No operands
code.addInsn(new Insn(opc_return));
// one arg operands
code.addInsn(new Insn(opc_astore, 5));
// one arg arguments with wide operand
code.addInsn(new Insn(opc_dstore, 256));
code.addInsn(new Insn(opc_istore, 2576));
// Add a label
code.addInsn(new Label("First label"));
// refer back to it
code.addInsn(new Insn(opc_jsr,
new Label("First label")));
// add another label
code.addInsn(new Label("second_label"));
// insn with CP argument
code.addInsn(new Insn(opc_ldc_w, new
StringCP("sdfsdf")));
黒太字：コードが挿入された箇所
22
編集が加えられていない
クローンの例
ギャップを含む
クローン
2007/2/27
public void reload( ) {
Iterator iterator = reloadables.iterator();
while (iterator.hasNext()) {
Reloadable reloadable = (Reloadable)
iterator.next();
reloadable.reload();
}
}
public void store( ) {
Iterator iterator = storers.iterator();
while (iterator.hasNext()) {
Storer storer = (Storer) iterator.next();
storer.store();
}
}
public void addReloadable(Reloadable reloadable) {
reloadables.addElement(reloadable);
}
public void removeReloadable(Reloadable reloadable)
{
reloadables.removeElement(reloadable);
}
2つのクローンが
オーバラップして
いる
ギャップを含む
クローン
23
まとめと今後の課題
まとめ
グラフマイニングアルゴリズムを用いたギャップを含
むクローン抽出手法を提案し、ツールを実装した
オープンソースソフトウェアに対してどのようなギャッ
プを含むクローンが抽出されるか調査した
今後の課題
2007/2/27
編集されていないクローンのフィルタリング
バグ検出手法としての有益性評価
24
2007/2/27
25
2007/2/27
26
コピー＆ペーストによる再利用の
流れ
if(a = b){
a = a + 1;
b = b*3;}
コピー＆ペーストによる
再利用
識別子名の変更
if(a = b){
if(i = j){
a = a + 1;
i = i + 1;
b = b*3;}
j = j*3;}
Exact
クローン
Parameterized
クローン
挿入
if(a = b){
削除
変更
if(a = b){
if(a = b){
b = b – 2;
a = a + 1;
a = a ++;
b = b*3;}
b = b*3;}
b = b*3;}
2007/2/27
Gappedクローン
27
コピー＆ペーストによる再利用の
流れ
Exactクローン
Parameterizedクローン
完全に一致したコード片。ただし空白、改行、コメント
などの違いは考慮しない
変数名、クラス名などのユーザ定義名の違いを除き
一致しているコード片
Gappedクローン
2007/2/27
構文的に一致しない不一致コード（ギャップ（Gap））を
部分的に含むコード片
28
実験１：結果
EJE
f2j
jasmin
javadjvu
ファイル
数
57
15
104
66
クローン
セット数
82
90
149
215
Gapped
クローン
セット数
42
63
102
45
94.165
1518.60
実行時間
（s）
2007/2/27
3.995 16.73
29
実験１：考察
クローンセット数が少なくても、ファイル数が多け
れば実行時間がかかっている
AGMアルゴリズムでは各ファイルごとにグラフを作成
するため
1つのファイルにクローンが集中していると、実
行時間が格段にかかってしまう
2007/2/27
グラフのサイズが大きくなると、頻度計算などで時間
がかかってしまうため
30
実験２
抽出されたGappedクローンが有益かどうかを判
断するために、抽出されたものに挿入・削除・変
更といった編集が加えられているかどうかを人
手で判定
メトリクス値RNRでフィルタリングして実験
2007/2/27
値が小さいほど、繰り返し要素を多く含むクローン
連続した変数宣言などのクローンをフィルタリングす
ることで、より効率的に分析作業が可能
閾値として0.5を用いる
31
RNR: クローン内の重複した処理の
少なさの度合い
∑ Tokensrepeated(C)
RNR = 1 -
C∈S
∑ Tokensall(C)
C∈S
S: クローンセット
C: クローンセットの要素
Tokensall(C) : クローンC中の総トークン数
Tokensrepeated(C) : クローンC中の繰り返し部分のトークン数
8トークン
X A B A B A B Y
4トークン
直前の繰り返し
2007/2/27
Tokensall = 8
Tokensrepeated = 4
32
クローン位置情報のフォーマット
フォーマット
グループID.ファイルID 開始行,開始カラム,開始トークン 終了行,終了カラム,終了トークン 繰り返し処理でないトークン数
0
.
1
73 ,
3
,
128
82 , 59
,
172
12
#begin{set}（１番目のクローンセット）
0.1
73,3,128 82,59,172 12
0.1
84,3,180 92,24,222 24
0.2
90,12,178 99,4,210 23
#end{set}
#begin{set}（２番目のクローンセット）
0.2
101,3,215 122,14,252 24
0.3
71,3,114 87,29,167 20
#end{set}
#begin{set}（３番目のクローンセット）
0.1
89,5,194 101,26,252 45
0.2
112,7,243 142,29,289 22
#end{set}
・・・・・・
2007/2/27
33
オーダー
AGMアルゴリズム
グラフの平均ノード数が増えると指数関数的に増加
グラフ構築
2007/2/27
O(n^2)
34
CP-Miner[1]
コピー＆ペーストによって生成されたコードの検
出を目的として開発されたツール
Clospan[2]と呼ばれるマイニングアルゴリズムを用い
る
コピー＆ペーストの後、数行の挿入や削除といった修
正が加えられたコードも検出可能
検出対象言語はC,C++
[1] Zhen Li, Shan Lu, Suvda Myagmar, Yuanyuan Zhou , “CP-Miner: Finding Copy-Paste and Related Bugs in
Large-Scale Software Code” , IEEE TSE, Vol.32, No.3 MARCH 2006 .
[2] X. Yan, J. Han, and R. Afshar, “CloSpan: Mining Closed Sequential Patterns in Laegr Datasets”, Proc.SIAM
Int’l Conf.Data Mining, May 2003.
2007/2/27
35
© Copyright 2025 ExpyDoc
