プログラム変更支援を目的としたコードクローン情報

プログラム変更支援を目的とした
コードクローン情報付加手法の提案と実装
井上研究室
佐々木亨
2004/2/26
特別研究報告会
1
研究の背景
 コードクローンとは
 ソースコード中に存在するコード片で、同形のコード片
が他に存在するもの
 コピー＆ペーストによるプログラム再利用などで生じる
 ソフトウェア保守を困難にする
 あるコード片にバグがあると、そのコードクローン全て
について修正の検討をしなければならない
 機能を追加する場合も同様のことが言える
2004/2/26
特別研究報告会
2
クローンクラス
 クローンクラス同形のコードクローンの集合
例
クローンクラス１
{C1,C4,C5}
C1
C2
C3
クローンクラス2
{C2,C3}
C4
C5
2004/2/26
特別研究報告会
3
コードクローン検出ツールCCFinder
 ソースコードを字句解析してトークンの列に分
解してから、トークン単位で直接比較すること
によりクローンを検出
 数百万行規模のシステムにも実用時間で解析
可能
 実用的に意味のないクローンを検出しない
 さまざまな企業のソフトウェアにも適用している
2004/2/26
特別研究報告会
4
CCFinderの出力
解析対象のファイル群の情報
ファイルのID・ファイル行数・
ファイルパスなどからなる
クローンクラス情報
クローンクラス
ID1のファイルの49行目から55行目
ID2のファイルの62行目から68行目
ID2のファイルの75行目から81行目
2004/2/26
#begin{file description}
0 1475 3429 /home/test/test1.c
1 3213 9669 /home/test/test2.c
2 3584 11420 /home/test/test3.c
:
#end{file description}
#begin{clone}
#begin{set}
0 1250,3,2811 1258,17,2853
0 1260,3,2861 1268,13,2903
1 2962,3,8913 2970,10,8955
#end{set}
#begin{set}
1
49,1,66 55,41,120
2
62,1,93
68,39,147
2
75,1,159 81,37,213
#end{set}
:
:
#end{clone}
特別研究報告会
5
クローン情報を用いてソースコードを修正
する際の問題点
 コードクローンに対する機能追加・修正中にク
ローン情報とソースコードで行番号のずれが
生じる
 対処法
 行番号のずれを意識しながら作業する
 効率が悪い
 修正箇所を間違える可能性
2004/2/26
特別研究報告会
6
研究の目的
 コードクローンに対する機能追加・修正中に行
番号のずれを意識せずに作業する
 コードクローンの位置情報を、コメントとして
ソースコードに埋め込む手法の提案とツール
の実装を行う
2004/2/26
特別研究報告会
7
コードクローン情報の追加（コメントの利用）
 基本方針
 クローンクラスごとに割り付けたIDを利用する
 クローンクラスに含まれる全行にコメントを追加する
 コメントの形式
 クローンクラスの先頭行は“//@$クローンクラスの
ID@”
 先頭行以外は“//@クローンクラスのID@”
 ある行が2つ以上のクローンクラスに属している場合は
コンマで区切る
2004/2/26
特別研究報告会
8
コメント追加例
クローンクラス1
#begin{set}
1
30,1,45
1
40,1,58
1
83,1,102
#end{set}
クローンクラス2
#begin{set}
1
30,1,45
1
83,1,102
#end{set}
2004/2/26
33,1,52
43,1,65
86,1,109
30: while(a>10){
31:
b=b+a;
32:
a=a+1;
33: }
34: sum = a;
//@$1@,@$2@
//@$1@
//@1@
//@1@,@2@
//@1@
//@1@,@2@
//@1@
//@1@,@2@
//@2@
34,1,55
87,1,112
40: while(c>10){
41:
d=d+c;
42:
c=c+1;
43: }
//@$1@
//@1@
//@1@
//@1@
83: while(e>10){
84:
f=f+e;
85:
e=e+1;
86: }
87: sum = e;
//@$1@,@$2@
//@$1@
//@1@
//@1@,@2@
//@1@
//@1@,@2@
//@1@
//@1@,@2@
//@2@
特別研究報告会
9
デバッグへの利用手順
１．あるバグを発見する
２．ソースコードにクローン情報の
コメントを付加する
３．バグを修正する
４．修正部分のコメントを調べる
５．コメント中のクローンクラスのID
を利用してクローンクラスの
先頭行を見つける
６．他の修正箇所を見つける
７．同様の修正を行う
８．不要になったコメントを除去する
2004/2/26
while文の条件が間
違っている
while(a <
> 10){ //@$1@,@$2@
b=b+a;
//@1@,@2@
a=a+1;
//@1@,@2@
}
//@1@,@2@
Sum = a;
//@2@
:
while(c <
> 10){ //@$1@
d=d+c;
//@1@
c=c+1;
//@1@
}
//@1@
:
while(e <
> 10){ //@$1@,@$2@
f=f+e;
//@1@,@2@
e=e+1;
//@1@,@2@
}
//@1@,@2@
Sum = e;
//@2@
特別研究報告会
10
ツールの機能
 コメント追加機能
 コメントにはクローンクラスのIDを利用
 コメントはクローンクラスに含まれる全行に追加
 追加はオリジナルファイルに行わず、編集用の一時的なファイルに行う
 クローンクラス検索機能
 クローンクラスを指定し、そのコメントがあるファイル情報等を検索・表示
 一時ファイル編集機能
 コメント追加後、ファイル編集のためにファイルを選択して開く
 コメント除去機能
 不要となったコメントを、クローンクラスのIDを指定して除去する
 すべてのコメントを一括して除去する
 一時ファイル書き戻し機能
 編集用の一時的なファイルの変更をオリジナルファイルに反映させる
2004/2/26
特別研究報告会
11
適用実験
 日本語入力システム「かんな」
(http://canna.sourceforge.jp)のバージョン3.6
と3.6p1の間でのセキュリティ問題の修正に対して擬
似的なデバッグを行うことで適用した
 ソースコードはC言語で記述、92ファイル、約9万行
 この修正は、バッファのオーバーフローを調べる処理の追
加で、全２０箇所にほぼ同じ修正を行っている
 具体的な追加コードは
if(Request.type7.datalen!=SIZEOFSHORT*3)
return (-1);
等
 実行環境 FreeBSD Pentium4 1.5GHz 512MB
2004/2/26
特別研究報告会
12
具体例（修正前の「かんな」ソースコード）
 下図の2405行目の直前にオーバーフローの検査処理を追加する
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
static
ProcWideReq7(buf)
BYTE *buf ;
{
ir_debug( Dmsg(10, "ProcWideReq7 start!!\n"));
buf += HEADER_SIZE; Request.type7.context = S2TOS(buf);
buf += SIZEOFSHORT; Request.type7.number = S2TOS(buf);
buf += SIZEOFSHORT; Request.type7.yomilen = (short)S2TOS(buf);
ir_debug( Dmsg(10, "req->context =%d\n", Request.type7.context));
ir_debug( Dmsg(10, "req->number =%d\n", Request.type7.number));
ir_debug( Dmsg(10, "req->yomilen =%d\n", Request.type7.yomilen));
return( 0 ) ;
}
2004/2/26
特別研究報告会
13
ツールを利用しない場合
- コードクローン位置情報のずれ
「かんな」バージョン3.6のコードクローン情報
#begin{set}
0.91
2367,1,7452
0.91
2383,1,7519
0.91
2399,1,7586
0.91
2415,1,7657
0.91
2433,1,7739
：
#end{set}
#begin{set}
0.91
2376,5,7488
0.91
2392,5,7555
0.91
2408,5,7626
0.91
2426,5,7708
0.91
2444,5,7790
：
#end{set}
#begin{set}
0.91
2399,1,7586
0.91
2587,1,8410
：
2004/2/26
#end{set}
2375,24,7483
2391,24,7550
2407,24,7617
2423,24,7688
2441,24,7770
2381,2,7518
2397,2,7585
2413,2,7656
2431,2,7738
2449,2,7820
この修正例において全部で20
2420行目に同様の2行分
箇所101行もの処理を追加
の修正を行ったとする
行番号の増減を意識しなが
赤い部分のずれは2行
ら作業するのは困難
2405行目に追加したため
青い部分のずれは4行
ソースコードとコードクローン
情報の間で行番号が2行ず
つずれている
2407,50,7619
2595,51,8443
特別研究報告会
14
コメント追加
ツールを利用する場合
コメント全消去
- コメント付加後に追加
約5秒
約3秒
一時ファイル書き戻し約3秒
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
クローンクラス検索
1秒未満
static //@$1311@,@$1318@
追加処理
ProcWideReq7(buf) //@1311@,@1318@
BYTE *buf ; //@1311@,@1318@
{ //@1311@,@1318@
ir_debug( Dmsg(10, "ProcWideReq7 start!!\n")); //@1311@,@1318@
//@1311@,@1318@
if(Request.type7.datalen!=SIZEOFSHORT*3)
return (-1);
buf += HEADER_SIZE; Request.type7.context = S2TOS(buf); //@1311@,@1318@
buf += SIZEOFSHORT; Request.type7.number = S2TOS(buf); //@1311@,@1318@
buf += SIZEOFSHORT; Request.type7.yomilen = (short)S2TOS(buf);
//@1311@,@1318@
ir_debug( Dmsg(10, "req->context =%d\n", Request.type7.context)); //@$1317@
ir_debug( Dmsg(10, “req->number =%d\n", Request.type7.number)); //@1317@
ir_debug( Dmsg(10, "req->yomilen =%d\n", Request.type7.yomilen)); //@1317@
//@1317@
return(
0 ) ; //@1317@
この部分のコメントを見ればクローンクラス1311と1318に関して同様の
} //@1317@
修正の検討をすればいいとわかる（実際に1311に対して修正を行っていた）
行番号のずれを意識することなく作業することができる
2004/2/26
特別研究報告会
15
まとめと今後の課題
 まとめ
 プログラム変更作業を支援するための、コードク
ローン情報付加手法の提案、ツールの試作をし、
「かんな」のバグ修正作業に適用した
 今後の課題
 実際のソフトウェア開発・保守現場での評価
2004/2/26
特別研究報告会
16
終わり
2004/2/26
特別研究報告会
17
これ以降は発表に入れないスライド
2004/2/26
特別研究報告会
18
定義
完全性
 修正が必要な箇所のうち実際に検出された割合
効率性
 検出されたうち実際に修正箇所である割合
検出された
 ある修正箇所を特定したときに、その箇所にあるコメン
ト内のクローンクラスIDをたどってたどり着ける箇所
2004/2/26
特別研究報告会
19
評価内容
 本ツールにおける「検出された
数」の定義
 修正箇所（関数単位）を節点と
して、同じクローンIDをもつ他
の節点に辺をつなぐ
 ある節点から到達することので
きる節点の総数
総修正箇所は4箇所
検出された箇所は5箇所
検出された修正箇所は3箇所
完全性 (4箇所中3箇所) 75%
効率性 (5箇所中3箇所) 60%
2004/2/26
特別研究報告会
//CL1
//CL1,2
//CL3
//CL2
//CL2,3
20
f値＝
評価結果
2  完全性  効率性
完全性  効率性
grep
本ツール
総修正箇所
20箇所
20箇所
検出された箇所
61箇所
15箇所
検出された箇所中
の修正箇所
19箇所
15箇所
完全性
95%
75%
効率性
34%
100%
f値
0.5
0.86
f値を見ると、本ツールはgrepより有効である
2004/2/26
特別研究報告会
21
補足実験
 CCFinderの最小一致トークン数を変化させた
トークン数
完全性
効率性
コメント数
50
13%
100%
0.5個
40
17%
100%
1.0個
30
75%
100%
4.2個
20
90%
100%
11個
10
100%
5%未満
30個
• コメント数：１修正箇所中のコメント数
2004/2/26
特別研究報告会
22
grepで検出されなかった唯一のクローン
・この部分を検索キーとすればgrepでも検出されるが、
static
ProcWideReq1(buf) これだと他にも数多く検出される
BYTE *buf ;
（135行一致する f値は0.26）
/* ARGSUSED */
{
ir_debug( Dmsg(10, "ProcWideReq1 start!!\n") );
return( 0 ) ;
}
このようにgrepなどのコード片を指定して
検索する場合は利用者の能力によって検
索結果に差が出る
しかし、
本ツールではその必要がないためその心
配がない
2004/2/26
特別研究報告会
23
1311は修正箇所で1318は修正しなくてよ
かったのはなぜ？
クローンクラス1311
クローンクラス1312
クローンクラス1318
実際には1312に対して修正が行われていた
つまり、1311に修正を行ったというより、
1312に対して修正を行っていた
2004/2/26
特別研究報告会
24
編集用の一時ファイルの作成方法
 対象のファイル群のパスの深さの最小値から、ディレクトリ
ファイル階層を実現する
1 /home/Canna36/cmd/wtoc/wtoc.c
2 /home/Canna36/dic/ideo/pubdic/pod.c
3 /home/Canna36/doc/man/guide/tex/cannaindex.c
4 /home/Canna36/misc/is.c
5 /home/Canna36/sample/sample.c
だと4と5が深さ4でパスが最も短い。深さ3番目からをこちらで新たに作った
ディレクトリAppend_Comment_Files中に再現する
1’ / Append_Comment_Files /cmd/wtoc/wtoc.c
2’ / Append_Comment_Files /dic/ideo/pubdic/pod.c
3’ / Append_Comment_Files /man/guide/tex/cannaindex.c
4’ / Append_Comment_Files /misc/is.c
5’ / Append_Comment_Files /sample/sample.c
となる。
2004/2/26
特別研究報告会
25
既存のコードクローン検出手法(1/2)
Bakerの手法
 行単位でソースコードを比較してコードクローンを検出
Baxterらの手法
 C言語のソースファイルを入力，構文解析して，解析木
(の部分木)を比較する
[Baker1995] B. S. Baker: “On finding Duplication and Near-Duplication in Large
Software
System,” Proc. Second IEEE Working Conf. Reverse Eng., pp. 8695, Tronto, Canada (Jul., 1995).
[Baxter1998] I. D. Baxter, A. Yahin, L. Moura, M. Sant’Anna, and L. Bier: “Clone
Detection Using Abstract Syntax Trees,” Proc. of ICSM ’98, pp. 368-377,
Bethesda, Maryland (Nov., 1998).
2004/2/26
特別研究報告会
26
既存のコードクローン検出手法(2/2)
Merloらの手法
 手続き（メソッドや関数）の特徴メトリクスを比較して，
計測値が似ていればコードクローンであると判定す
る
[Balazinska1999] M. Balazinska, E. Merlo, M. Dagenais, B. Lague, and K.A.
Kontogiannis, "Measuring Clone Based Reengineering Opportunities", Proc. 6th
IEEE Int'l Symposium on Software Metrics (METRICS '99), pp. 292-303, Boca
Raton, Florida, Nov. 1999.
2004/2/26
特別研究報告会
27
CCFinder：コードクローン検出ツール
ソースコードを字句解析してトークンの列に直
してからコードクローン検出を行う
 （浅い）文法知識に基づいたソースコード変形
 クラススコープや名前空間による複雑な名前の正規化
を行う
 初期化テーブルを取り除く
 モジュールの区切りを認識する
 言語依存部分を取り替えることで，さまざまなプログ
ラミング言語に対応
2004/2/26
特別研究報告会
28
コードクローン検出手順
(1)ソースコードを入力し，トークンの列にする
(2)変形ルールにより，トークン列を変形する
(3)パラメータ置換を行う
(4)マッチングアルゴリズムによりコードクローン
を検出する
(5)コードクローンの位置(ファイル，行, カラム)
を出力する
2004/2/26
特別研究報告会
29
例題ソースコード
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
2004/2/26
static void foo() throws RESyntaxException {
String a[] = new String [] { "123,400", "abc", "orange 100" };
org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+");
int sum = 0;
for (int i = 0; i < a.length; ++i)
if (pat.match(a[i]))
sum += Sample.parseNumber(pat.getParen(0));
System.out.println("sum = " + sum);
}
static void goo(String [] a) throws RESyntaxException {
RE exp = new RE("[0-9,]+");
int sum = 0;
for (int i = 0; i < a.length; ++i)
if (exp.match(a[i]))
sum += parseNumber(exp.getParen(0));
System.out.println("sum = " + sum);
}
特別研究報告会
30
4-6行目と
13-15行目，
8-10行目と
17-19行目
2004/2/26
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
static void foo() throws RESyntaxException {
String a[] = new String [] { "123,400", "abc", "orange 100" };
org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+");
int sum = 0;
for (int i = 0; i < a.length; ++i) {
if (pat.match(a[i]))
sum += Sample.parseNumber(pat.getParen(0));
}
System.out.println("sum = " + sum);
}
static void goo(String [] a) throws RESyntaxException {
RE exp = new RE("[0-9,]+");
int sum = 0;
for (int i = 0; i < a.length; ++i) {
if (exp.match(a[i]))
sum += parseNumber(exp.getParen(0));
}
System.out.println("sum = " + sum);
}
31
特別研究報告会
クローン
2004/2/26
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
static void foo() throws RESyntaxException {
String a[] = new String [] { "123,400", "abc", "orange 100" };
org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+");
int sum = 0;
for (int i = 0; i < a.length; ++i)
if (pat.match(a[i]))
sum += Sample.parseNumber(pat.getParen(0));
System.out.println("sum = " + sum);
}
static void goo(String [] a) throws RESyntaxException {
RE exp = new RE("[0-9,]+");
int sum = 0;
for (int i = 0; i < a.length; ++i)
if (exp.match(a[i]))
sum += parseNumber(exp.getParen(0));
System.out.println("sum = " + sum);
}
特別研究報告会
32
修正のたびにコードクローンの位置情報を
更新すると‥
検出されなくなる
クローンペア
修正する
クローンでなくなる
2004/2/26
特別研究報告会
33
実装
 Javaで実装
 動作環境 FreeBSD
メニューバー
ステータスバー
2004/2/26
特別研究報告会
34

Download Report