プログラム変更支援を目的とした コードクローン情報付加手法の提案と実装 井上研究室 佐々木 亨 2004/2/26 特別研究報告会

研究の背景 コードクローンとは ソフトウェア保守を困難にする ソースコード中に存在するコード片で、同形のコード片が他に存在するもの 研究の背景　 コードクローンとは ソースコード中に存在するコード片で、同形のコード片が他に存在するもの コピー＆ペーストによるプログラム再利用などで生じる ソフトウェア保守を困難にする あるコード片にバグがあると、そのコードクローン全てについて修正の検討をしなければならない 機能を追加する場合も同様のことが言える 2004/2/26 特別研究報告会

クローンクラス クローンクラス 同形のコードクローンの集合 例 クローンクラス１ {C1,C4,C5} クローンクラス2 {C2,C3} クローンクラス　同形のコードクローンの集合 例 C1 C5 C4 C3 C2 クローンクラス１ {C1,C4,C5} クローンクラス2 {C2,C3} 2004/2/26 特別研究報告会

コードクローン検出ツールCCFinder ソースコードを字句解析してトークンの列に分解してから、トークン単位で直接比較することによりクローンを検出 数百万行規模のシステムにも実用時間で解析可能 実用的に意味のないクローンを検出しない さまざまな企業のソフトウェアにも適用している 2004/2/26 特別研究報告会

CCFinderの出力 #begin{file description} 0 1475 3429 /home/test/test1.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} 1 49,1,66 55,41,120 2 62,1,93 68,39,147 2 75,1,159　 81,37,213 : #end{clone} 解析対象のファイル群の情報 ファイルのID・ファイル行数・ ファイルパスなどからなる クローンクラス情報 クローンクラス ID1のファイルの49行目から55行目 ID2のファイルの62行目から68行目 ID2のファイルの75行目から81行目 2004/2/26 特別研究報告会

クローン情報を用いてソースコードを修正する際の問題点 コードクローンに対する機能追加・修正中にクローン情報とソースコードで行番号のずれが生じる 対処法 行番号のずれを意識しながら作業する 効率が悪い 修正箇所を間違える可能性 2004/2/26 特別研究報告会

研究の目的 コードクローンに対する機能追加・修正中に行番号のずれを意識せずに作業する コードクローンの位置情報を、コメントとしてソースコードに埋め込む手法の提案とツールの実装を行う 2004/2/26 特別研究報告会

コードクローン情報の追加（コメントの利用） 基本方針 クローンクラスごとに割り付けたIDを利用する クローンクラスに含まれる全行にコメントを追加する コメントの形式 クローンクラスの先頭行は“//@$クローンクラスのID@” 先頭行以外は“//@クローンクラスのID@” ある行が2つ以上のクローンクラスに属している場合はコンマで区切る 2004/2/26 特別研究報告会

コメント追加例 30: while(a>10){ 31: b=b+a; 32: a=a+1; 33: } 34: sum = a; 33: } 34: sum = a; 40: while(c>10){ 41: d=d+c; 42: c=c+1; 43: } 83: while(e>10){ 84: f=f+e; 85: e=e+1; 86: } 87: sum = e; //@$1@ //@1@ //@$1@,@$2@ //@1@,@2@ //@2@ //@$1@ //@1@ クローンクラス1 #begin{set} 1　　　30,1,45　　　33,1,52 1　　　40,1,58　　　43,1,65 1　　　83,1,102　　86,1,109 #end{set} クローンクラス2 1　　　30,1,45　　　34,1,55 1　　　83,1,102　　87,1,112 2004/2/26 特別研究報告会

デバッグへの利用手順 while文の条件が間違っている １．あるバグを発見する ２．ソースコードにクローン情報の コメントを付加する //@$1@,@$2@ //@1@,@2@ //@2@ //@$1@ //@1@ while(a < 10){ b=b+a; a=a+1; } Sum = a; : while(c > 10){ d=d+c; c=c+1; while(e > 10){ f=f+e; e=e+1; Sum = e; //@$1@,@$2@ //@1@,@2@ //@2@ //@$1@ //@1@ while(a < 10){ b=b+a; a=a+1; } Sum = a; : while(c < 10){ d=d+c; c=c+1; while(e < 10){ f=f+e; e=e+1; Sum = e; //@$1@,@$2@ //@1@,@2@ //@2@ //@$1@ //@1@ while(a < 10){ b=b+a; a=a+1; } Sum = a; : while(c < 10){ d=d+c; c=c+1; while(e < 10){ f=f+e; e=e+1; Sum = e; while(a > 10){ b=b+a; a=a+1; } Sum = a; : while(c > 10){ d=d+c; c=c+1; while(e > 10){ f=f+e; e=e+1; Sum = e; １．あるバグを発見する ２．ソースコードにクローン情報の コメントを付加する ３．バグを修正する ４．修正部分のコメントを調べる ５．コメント中のクローンクラスのID を利用してクローンクラスの 先頭行を見つける ６．他の修正箇所を見つける ７．同様の修正を行う ８．不要になったコメントを除去する 2004/2/26 特別研究報告会

ツールの機能 コメント追加機能 クローンクラス検索機能 一時ファイル編集機能 コメント除去機能 一時ファイル書き戻し機能 コメントにはクローンクラスのIDを利用 コメントはクローンクラスに含まれる全行に追加 追加はオリジナルファイルに行わず、編集用の一時的なファイルに行う クローンクラス検索機能 クローンクラスを指定し、そのコメントがあるファイル情報等を検索・表示 一時ファイル編集機能 コメント追加後、ファイル編集のためにファイルを選択して開く コメント除去機能 不要となったコメントを、クローンクラスのIDを指定して除去する すべてのコメントを一括して除去する 一時ファイル書き戻し機能 編集用の一時的なファイルの変更をオリジナルファイルに反映させる 2004/2/26 特別研究報告会

適用実験 日本語入力システム「かんな」(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 特別研究報告会

具体例（修正前の「かんな」ソースコード） 下図の2405行目の直前にオーバーフローの検査処理を追加する 2399 static 2400 ProcWideReq7(buf) 2401 BYTE *buf ; 2402 { 2403 ir_debug( Dmsg(10, "ProcWideReq7 start!!\n")); 2404 　 2405 buf += HEADER_SIZE; Request.type7.context = S2TOS(buf); 2406 buf += SIZEOFSHORT; Request.type7.number = S2TOS(buf); 2407 buf += SIZEOFSHORT; Request.type7.yomilen = (short)S2TOS(buf); 2408 ir_debug( Dmsg(10, "req->context =%d\n", Request.type7.context)); 2409 ir_debug( Dmsg(10, "req->number =%d\n", Request.type7.number)); 2410 ir_debug( Dmsg(10, "req->yomilen =%d\n", Request.type7.yomilen)); 2411 　 2412 return( 0 ) ; 2413 　} 2004/2/26 特別研究報告会

ツールを利用しない場合 - コードクローン位置情報のずれ ツールを利用しない場合 　- コードクローン位置情報のずれ 「かんな」バージョン3.6のコードクローン情報 #begin{set} 0.91　　　2367,1,7452　　　2375,24,7483 0.91　　　2383,1,7519　　　2391,24,7550 0.91　　　2399,1,7586　　　2407,24,7617 0.91　　　2415,1,7657　　　2423,24,7688 0.91　　　2433,1,7739　　　2441,24,7770　　 　　　　　　： #end{set} 0.91　　　2376,5,7488　　　2381,2,7518 0.91　　　2392,5,7555　　　2397,2,7585 0.91　　　2408,5,7626　　　2413,2,7656 0.91　　　2426,5,7708　　　2431,2,7738 0.91　　　2444,5,7790　　　2449,2,7820 0.91　　　2399,1,7586　　　2407,50,7619 0.91　　　2587,1,8410　　　2595,51,8443 #begin{set} 0.91　　　2367,1,7452　　　2375,24,7483 0.91　　　2383,1,7519　　　2391,24,7550 0.91　　　2399,1,7586　　　2407,24,7617 0.91　　　2415,1,7657　　　2423,24,7688 0.91　　　2433,1,7739　　　2441,24,7770　　 　　　　　　： #end{set} 0.91　　　2376,5,7488　　　2381,2,7518 0.91　　　2392,5,7555　　　2397,2,7585 0.91　　　2408,5,7626　　　2413,2,7656 0.91　　　2426,5,7708　　　2431,2,7738 0.91　　　2444,5,7790　　　2449,2,7820 0.91　　　2399,1,7586　　　2407,50,7619 0.91　　　2587,1,8410　　　2595,51,8443 #begin{set} 0.91　　　2367,1,7452　　　2375,24,7483 0.91　　　2383,1,7519　　　2391,24,7550 0.91　　　2399,1,7586　　　2407,24,7617 0.91　　　2415,1,7657　　　2423,24,7688 0.91　　　2433,1,7739　　　2441,24,7770　　 　　　　　　： #end{set} 0.91　　　2376,5,7488　　　2381,2,7518 0.91　　　2392,5,7555　　　2397,2,7585 0.91　　　2408,5,7626　　　2413,2,7656 0.91　　　2426,5,7708　　　2431,2,7738 0.91　　　2444,5,7790　　　2449,2,7820 0.91　　　2399,1,7586　　　2407,50,7619 0.91　　　2587,1,8410　　　2595,51,8443 この修正例において全部で20箇所101行もの処理を追加 2420行目に同様の2行分の修正を行ったとする 行番号の増減を意識しながら作業するのは困難 赤い部分のずれは2行 青い部分のずれは4行 2405行目に追加したため ソースコードとコードクローン情報の間で行番号が2行ずつずれている 2004/2/26 特別研究報告会

ツールを利用する場合 - コメント付加後に追加 ツールを利用する場合 - コメント付加後に追加 コメント追加 約5秒 コメント全消去 約3秒 一時ファイル書き戻し クローンクラス検索 1秒未満 2399 static //@$1311@,@$1318@ 2400 ProcWideReq7(buf) //@1311@,@1318@ 2401 BYTE *buf ; //@1311@,@1318@ 2402 { //@1311@,@1318@ 2403 　 ir_debug( Dmsg(10, "ProcWideReq7 start!!\n")); //@1311@,@1318@ 2404 //@1311@,@1318@ 2405 if(Request.type7.datalen!=SIZEOFSHORT*3) 2406 return (-1); 2407 buf += HEADER_SIZE; Request.type7.context = S2TOS(buf); //@1311@,@1318@ 2408 buf += SIZEOFSHORT; Request.type7.number = S2TOS(buf); //@1311@,@1318@ 2409 buf += SIZEOFSHORT; Request.type7.yomilen = (short)S2TOS(buf); //@1311@,@1318@ 2410 　ir_debug( Dmsg(10, "req->context =%d\n", Request.type7.context)); //@$1317@ 2411 ir_debug( Dmsg(10, “req->number =%d\n", Request.type7.number)); //@1317@ 2412 ir_debug( Dmsg(10, "req->yomilen =%d\n", Request.type7.yomilen)); //@1317@ 2413 　//@1317@ 2414 　 return( 0 ) ; //@1317@ 2415 } //@1317@ 追加処理 この部分のコメントを見ればクローンクラス1311と1318に関して同様の 修正の検討をすればいいとわかる（実際に1311に対して修正を行っていた） 行番号のずれを意識することなく作業することができる 2004/2/26 特別研究報告会

まとめと今後の課題 まとめ プログラム変更作業を支援するための、コードクローン情報付加手法の提案、ツールの試作をし、「かんな」のバグ修正作業に適用した 今後の課題 実際のソフトウェア開発・保守現場での評価 2004/2/26 特別研究報告会

終わり 2004/2/26 特別研究報告会

これ以降は発表に入れないスライド 2004/2/26 特別研究報告会

定義 完全性 効率性 検出された 修正が必要な箇所のうち実際に検出された割合 検出されたうち実際に修正箇所である割合 ある修正箇所を特定したときに、その箇所にあるコメント内のクローンクラスIDをたどってたどり着ける箇所 2004/2/26 特別研究報告会

評価内容 本ツールにおける「検出された数」の定義 //CL1 修正箇所（関数単位）を節点として、同じクローンIDをもつ他の節点に辺をつなぐ ある節点から到達することのできる節点の総数 //CL1 //CL1,2 //CL3 //CL2 総修正箇所は4箇所 検出された箇所は5箇所 検出された修正箇所は3箇所 完全性　(4箇所中3箇所)　75% 効率性　(5箇所中3箇所)　60% //CL2,3 2004/2/26 特別研究報告会

評価結果 grep 本ツール 総修正箇所 20箇所 検出された箇所 61箇所 15箇所 検出された箇所中の修正箇所 19箇所 完全性 95% 75% 効率性 34% 100% f値 0.5 0.86 f値を見ると、本ツールはgrepより有効である 2004/2/26 特別研究報告会

補足実験 CCFinderの最小一致トークン数を変化させた トークン数 完全性 効率性 コメント数 50 13% 100% 0.5個 40 17% 1.0個 30 75% 4.2個 20 90% 11個 10 5%未満 30個 　コメント数　：　１修正箇所中のコメント数 2004/2/26 特別研究報告会

grepで検出されなかった唯一のクローン （135行一致する　f値は0.26） static ProcWideReq1(buf) BYTE *buf ; /* ARGSUSED */ { ir_debug( Dmsg(10, "ProcWideReq1 start!!\n") ); return( 0 ) ; } このようにgrepなどのコード片を指定して検索する場合は利用者の能力によって検索結果に差が出る しかし、 本ツールではその必要がないためその心配がない 2004/2/26 特別研究報告会

1311は修正箇所で1318は修正しなくてよかったのはなぜ？ クローンクラス1311 クローンクラス1312 クローンクラス1318 実際には1312に対して修正が行われていた つまり、1311に修正を行ったというより、 1312に対して修正を行っていた 2004/2/26 特別研究報告会

編集用の一時ファイルの作成方法 対象のファイル群のパスの深さの最小値から、ディレクトリファイル階層を実現する 　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 特別研究報告会

既存のコードクローン検出手法(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. 86-95, 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 特別研究報告会

既存のコードクローン検出手法(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 特別研究報告会

CCFinder： コードクローン検出ツール ソースコードを字句解析してトークンの列に直してからコードクローン検出を行う （浅い）文法知識に基づいたソースコード変形 クラススコープや名前空間による複雑な名前の正規化を行う 初期化テーブルを取り除く モジュールの区切りを認識する 言語依存部分を取り替えることで，さまざまなプログラミング言語に対応 2004/2/26 特別研究報告会

コードクローン検出手順 (1)ソースコードを入力し，トークンの列にする (2)変形ルールにより，トークン列を変形する (3)パラメータ置換を行う (4)マッチングアルゴリズムによりコードクローンを検出する (5)コードクローンの位置(ファイル，行, カラム)を出力する 2004/2/26 特別研究報告会

例題ソースコード 1. static void foo() throws RESyntaxException { 2. String a[] = new String [] { "123,400", "abc", "orange 100" }; 3. org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+"); 4. int sum = 0; 5. for (int i = 0; i < a.length; ++i) 6. if (pat.match(a[i])) 7. sum += Sample.parseNumber(pat.getParen(0)); 8. System.out.println("sum = " + sum); 9. } 10. static void goo(String [] a) throws RESyntaxException { 11. RE exp = new RE("[0-9,]+"); 12. int sum = 0; 13. for (int i = 0; i < a.length; ++i) 14. if (exp.match(a[i])) 15. sum += parseNumber(exp.getParen(0)); 16. System.out.println("sum = " + sum); 17. } 2004/2/26 特別研究報告会

4-6行目と 13-15行目， 8-10行目と 17-19行目 1. static void foo() throws RESyntaxException { 2. String a[] = new String [] { "123,400", "abc", "orange 100" }; 3. org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+"); 4. int sum = 0; 5. for (int i = 0; i < a.length; ++i) { 6. if (pat.match(a[i])) 7. sum += Sample.parseNumber(pat.getParen(0)); 8. } 9. System.out.println("sum = " + sum); 10. } 11. static void goo(String [] a) throws RESyntaxException { 12. RE exp = new RE("[0-9,]+"); 13. int sum = 0; 14. for (int i = 0; i < a.length; ++i) { 15. if (exp.match(a[i])) 16. sum += parseNumber(exp.getParen(0)); 17. } 18. System.out.println("sum = " + sum); 19. } 2004/2/26 特別研究報告会

1. static void foo() throws RESyntaxException { 2. String a[] = new String [] { "123,400", "abc", "orange 100" }; 3. org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+"); 4. int sum = 0; 5. for (int i = 0; i < a.length; ++i) 6. if (pat.match(a[i])) 7. sum += Sample.parseNumber(pat.getParen(0)); 8. System.out.println("sum = " + sum); 9. } 10. static void goo(String [] a) throws RESyntaxException { 11. RE exp = new RE("[0-9,]+"); 12. int sum = 0; 13. for (int i = 0; i < a.length; ++i) 14. if (exp.match(a[i])) 15. sum += parseNumber(exp.getParen(0)); 16. System.out.println("sum = " + sum); 17. } 2004/2/26 特別研究報告会

修正のたびにコードクローンの位置情報を更新すると‥ 検出されなくなる クローンペア 修正する クローンでなくなる 2004/2/26 特別研究報告会

実装 Javaで実装 動作環境　FreeBSD メニューバー ステータスバー 2004/2/26 特別研究報告会