Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 関数クローン変更管理システ ムの開発と評価 井上研究室 佐野 真夢

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University コードクローン 同一または類似した部分を持つコード片の こと – ソースコードのコピーアンドペーストなどによ り生じる ソフトウェアの保守コストを大きくする要 因 2 クローン セット 他のコードクローンにも バグがあるかもしれない あるコード片に バグがあれば あるコード片に バグがあれば コードク ローン 調査の手間

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University クローンの分類 [1] 3 [1] Roy et, al., Comparison and Evaluation of Code Clone Detection Techniques and Tools: A Qualitative Approach, Science of Computer Programming, 2009 分類定義 タイプ 1 空白, コメント等のコーディングスタイルを除いて完 全に 一致している タイプ 2 タイプ 1 に加え, ユーザ定義名や型の違いを除いて構 文上 一致している タイプ 3 タイプ 2 に加え, 文が挿入・変更・削除されている タイプ 4 構文上は異なる実装だが, 類似処理を実行している （ while 文と for 文など） 各タイプに応じたクローン検出ツールが存在している

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University クローンの変更管理の必要性 クローンを修正する場合, 他クローンの同時 修正を検討する必要がある 大規模なソフトウェアほど多くのクローン を含む – 修正の度に, クローンを検出し, 手作業で修正さ れたかどうか調査するのは非効率 4 コードクローン変更を自動管理するシステムが必要

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University ※タイプ 1, 2 CloneNotifier [2] クローンの同時修正を支援するための変更管理シス テム 5 版管理システ ム ソースコードの 取得 コードクローンの 変更を調査 コードクローンの 変更を調査 コードクローンの検 出 コードクローン 変更管理システム クローン検出ツー ル CCFinder 開発者 コードクローン の変更情報の提 示 [2] 山中ら, コードクローン変更管理システムの開発と実プロジェクトへの適用, 情報処理学会論文誌, 変更された コードクローンを把 握 変更された コードクローンを把 握

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 問題点 CloneNotifier はタイプ 3, 4 のクローンを検出できない – 文が挿入・変更・削除されたクローン – 構文上の実装が異なるが, 処理は同じクローン 検出粒度が小さい分, 重要度の低い結果も多く検出 される 6 void AscendingSort(int list[]) { for(i = 0; i < n-1; i++) for(j = n-1; j > i; j--) if(list[j+1] > list[j]) { temp = list[j]; list[j] = list[j-1]; list[j-1] = temp; } 修正 : if(list[j-1] > list[j]) { void DescendingSort(int list[]) { for(i = 0; i < n-1; i++) for(j = n-1; j > i; j--) if(list[j+1] < list[j]) { temp = list[j]; list[j] = list[j-1]; list[j-1] = temp; } 修正 : if(list[j-1] < list[j]) { 検出できない同時修正の例（タイプ 3 ） 比較対象のミス × j+1 → ○ j-1 比較演算子が異なる → タイプ 3

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 000 山中らのクローン検出ツール [3] テキストマイニング技術を利用したクローン検出ツール 関数単位でクローンを検出する タイプ 1 ～ 4 の全てのクローンを高速に検出可能 7 [3] 山中ら, 情報検索技術に基づく高速な関数クローン検出, 情報処理学会論文誌, ワード回数 xxx2 yyy4 ・・・ ワード回数 xxx3 yyy2 ・・・ Function A Function B ソースコード 入力 ワード抽出 特徴ベクトル 計算 クラスタリング Function A Function B Function A Function B Function A Function B Function C Function D Function E Function C Function D Function E 類似度関数対クローン 0.95 Function A Function B 0.70 Function C Function D 0.70 Function C Function E 0.90 Function D Function E ・・・ クローン検出

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 研究概要 山中らのクローン検出ツールを利用し, 新た な 関数クローン変更管理システムを開発 –CloneNotifier を改変する形で実装する 開発したシステムの評価 8

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 関数クローン変更管理システム 9 ※全タイプ 版管理システ ム ソースコードの 取得 コードクローンの検 出 関数クローン 変更管理システム 山中らの クローン検出ツー ル 開発者 コードクローン の変更情報の提 示 変更された コードクローンを把 握 変更された コードクローンを把 握 クローン位置情 報 の特定 クローン位置情 報 の特定 コードクローンの 変更を調査 コードクローンの 変更を調査 入出力仕様の 違いに対応 入出力仕様の 違いに対応 出力仕様の違いによる. 変更されたかの判断に必 要 出力仕様の違いによる. 変更されたかの判断に必 要 出力に関数名の 情報を追加 出力に関数名の 情報を追加

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 提案システムの出力の例 10 新たに増えたクローン クローンセット ID:0 ID 分類ファイル名位置メソッド名 0.0ADDEDsrc\backend\parser\parse_expr.c transformAExprAnd 0.1ADDEDsrc\backend\parser\parse_expr.c transfomrAExprOr 0.2ADDEDsrc\backend\parser\parse_expr.c transformAExprDistinct New Clone Set クローンセット ID:1 ID 分類ファイル名位置メソッド名 1.0MODIFIEDsrc\backend\access\rtree\rtscan.c rtmarkpos 1.1MODIFIEDsrc\backend\access\rtree\rtscan.c rtrestpos Changed Clone Set 変更されたクローン Deleted Clone Set クローンセット ID:4 ID 分類ファイル名位置メソッド名 4.0DELETEDsrc\backend\access\gist\gistget.c gistnext 4.1DELETEDsrc\backend\access\rtree\rtget.c rtnext 消滅したクローン

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 評価実験 CloneNotifier と提案システムの比較評価 – 評価 A. 提案システムのみが検出可能なクローンはど れくらいあるかの調査 CloneNotifier でほとんどの修正クローンが検出可能なら, 提 案システムの有用性が示せない – 評価 B. クローン変更管理システムとしての性能の評 価 評価対象 –PostgreSQL [4] OSS のデータベース管理システム（ C 言語） 2005/01/01 ～ 2005/06/30 の 6 ヶ月間 1 週間単位で区切り 11 [4]

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 評価 A. 概略 評価対象に提案システムを適用し, 検出結 果のタイプ 3, 4 クローン修正の数を調べる 12 タイプ 3, 4 タイプ 1, 2 合計 一貫し た 修正 非一貫し た 修正 他に適用 不能な修 正 整形 コメントの み 合計 CloneNotifier で検出できない 89 件の 有用なクローン修正事例を検出できた CloneNotifier で検出できない 89 件の 有用なクローン修正事例を検出できた

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 評価 B. 手順 1. 各システムで, 評価対象（ PostgreSQL の全 26 期 間の変更）における変更クローンセットの集合 を 検出する 2. 各システム, 集合から 50 件ずつ結果をランダム に選択する – 手作業が入るため, 現実的に調査可能な数 – 母集団の数が 4 倍近く異なるため合わせる 3.2 つの評価尺度（後述）に基づき, 有用な修正 クローンセットの割合を求める – 有用 / 不要の判断ができないものは分母から除外する 13

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 評価 B. 評価尺度 尺度 1. 一貫した修正が行われた, または, 必要な可能性のあるクローンセットか 14 clone1 cloneset.A clone2 同様の修正が行われた clone1 cloneset.B clone2 同様の修正を適用できる 可能性がある clone1 cloneset.C clone2 同様の修正を適用不可修正が無い （クローンの構成が変わった） clone1 cloneset.D clone2clone3 削除追加 尺度 2. 変更後も同じクローンセットとして追跡できてい るか 有用 有用でない 除外 clone1 cloneset.A clone2clone1 cloneset.A clone2 修正前 修正後 有用 clone1 not clone clone2clone1 cloneset.B clone2 有用でない clone1 cloneset.C clone2 除外 clone1 cloneset.D clone2 clone1 not clone 削除コード clone1clone2 not clone 追加コード 除外

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 評価 B. 結果（尺度 1 ） 15 提案システムの方が有用なクローンセットの割 合が高い – 提案システムの方が精度は高い – ただし, 母集団は排他的で, 完全に同じ修正箇所を検 出している事例は存在しなかった 一貫した修正が行われた, または, 必要な可能性のある クローンセットをどれくらい検出できているか 有用有用でない合計数除外数 CloneNotifier56.4 % （ 22 ） 43.6 % （ 17 ） 3911 提案システム 71.4 % （ 25 ） 28.6 % （ 10 ） 3515

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 評価 B. 結果（尺度 2 ） 有用有用でない合計数除外数 CloneNotifier47.1 % （ 16 ） 52.9 % （ 18 ） 3416 提案システム 71.4 % （ 30 ） 28.6 % （ 12 ） 提案システムの方が追跡を継続している割合が高 い – 提案システムの方が, クローンを継続して変更管理でき る – 一貫しない変更が起きても, タイプ 3 クローンとして追 跡できたため 変更後も同じクローンセットとして追跡できているか

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University まとめと今後の課題 新たな関数クローン変更管理システムの開発 開発したシステムの有用性評価 –CloneNotifier では検出できない多くの事例を検出した –CloneNotifier と比較し, 精度は高かった – ただし, 結果が排他的のため, 組み合わせて使う方が 望ましい 今後の課題 – より多くのプロジェクトに対する評価 – ユーザ調査, インタフェース等の改良 – 両システムを統合した場合の評価 17

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 18

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 追跡不能クローンの例 19 ri_InitHashTables(void) { HASHCTLctl; memset(&ctl, 0, sizeof(ctl)); ctl.keysize = sizeof(RI_QueryKey); ctl.entrysize = sizeof(RI_QueryHashEntry); ctl.hash = tag_hash; ri_query_cache = hash_create(“RI query cache”, RI_INIT_QUERYHASHSIZE, &ctl, HASH_ELEM | HASH_FUNCTION); } plpgsql_HashTableInit(void) { HASHCTLctl; Assert(plpgsql_HashTable == NULL) memset(&ctl, 0, sizeof(ctl)); ctl.keysize = sizeof(PLpgSQL_func_hashkey); ctl.entrysize = sizeof(plpgsql_HashEnt); ctl.hash = tag_hash; plpgsql_HashTable = hash_create(“PLpgSQL function cache”, FUNCS_PER_USER, &ctl, HASH_ELEM | HASH_FUNCTION); }

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 評価 1 （手順） 1. 各期間内の新・旧プロジェクトを取得し, 提案システム を 適用した結果を得る – 得られる結果は変更があったクローンセットの集合 – 旧 : 各期間内の一番古い状態, 新 : 各期間内での最新状態 2. 結果から実際にコードに対する修正が行われた事例のみ を抽出する（手動） – クローン自体の追加・削除・移動を除外 3. さらに, CloneNotifier で検出できない事例（タイプ 3, 4 へ の修正）を抽出し, 一貫した修正か否かを分類する 20 提案システムが, CloneNotifier では検出できないクローンを どのくらい検出するか 提案システムが, CloneNotifier では検出できないクローンを どのくらい検出するか

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 実装の詳細 検出ツール呼出し部分の置換 – プロセスに与える実行コマンドを変更 – 検出結果読み込み部の修正 クローン位置情報の特定処理の追加 – 各関数クローンの開始・終了行列を求める メトリクス情報の出力部分を除去 –CCFinder の出力結果を利用していたため 等価なクローンセットの定義を変更 – 従来版は CCFinder での内部 ID で判断できた – 新版はリスト先頭に来るクローンが等価な関数かで 判断 21

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 有用な事例（一貫した修正 1 ） 22 src/backend/access/common/printtup.cprinttup src/backend/access/common/printtup.cprinttup_internal_20 printtup(HeapTuple tuple, TupleDesc typeinfo,...) {... heap_deformtuple(...)... for(i=0;i<natts;++i) {... Datum origattr = myState->values[i], attr; if(myState->nulls[i] == 'n') { pq_sendint(&buf,-1,4); continue; }... } printtup_internal_20(HeapTuple tuple, TupleDesc typeinfo,...) {... heap_deformtuple(...)... for(i=0;i<natts;++i) { if(myState->nulls[i] != 'n') j |= k;... }... for(i=0;i<natts;++i) {... Datum origattr = myState->values[i], attr; bytea *outputbytes; if(myState->nulls[i] == 'n') continue; }... } 修正前 Changed Cloneset 2005/03/12 → 2005/03/18 for ブロックの 有無 局所変数が多い 呼出し関数 がある 呼出し関数 がある タイプ 3

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 有用な事例（一貫した修正 1 ） 23 src/backend/access/common/printtup.cprinttup src/backend/access/common/printtup.cprinttup_internal_20 printtup(TupleTableSlot *slot,...) { TupleDesc typeinfo =...;... slot_getallattrs(slot);... for(i=0;i<natts;++i) {... Datum origattr = slot->tts_values[i], attr; if(slot->tts_isnull[i]) { pq_sendint(&buf,-1,4); continue; }... } printtup_internal_20(TupleTableSlot *slot,...) { TupleDesc typeinfo =...;... slot_getallattrs(slot);... for(i=0;i<natts;++i) { if(slot->tts_isnull[i]) j |= k;... }... for(i=0;i<natts;++i) {... Datum origattr = slot->tts_values[i], attr; bytea *outputbytes; if(slot->tts_isnull[i]) continue; }... } 修正後 Changed Cloneset 引数の変更 null チェックの 方法を変更 変数・関数 呼出しの追加 参照先の変更 タイプ /03/12 → 2005/03/18

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 山中らのツールを選んだ理由 (1) 全タイプ対応の他の検出ツールより高精度 24 プロジェクト 名 適合率 (%) 検出クローン数 タイプ 1 タイプ 2 タイプ 3 タイプ 4 山中らのツー ル Python ApacheHTTPD PostgreSQL 合計 MeCC Python ApacheHTTPD PostgreSQL 合計 [5] Kim et. al., MeCC: memory comparison-based clone detector, Proc. of ICSE, ※ MeCC はメモリベースの関数クローン検出ツール. 他の検出ツールより高い精度を持つことが報告されている [5].

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 山中らのツールを選んだ理由 (2) 全タイプ対応の他の検出ツールより高速 25 ApacheHTTPDPythonPostgreSQL 山中らのツー ル 1m43s2m13s4m39s MeCC310m34s65m26s428m32s

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 本研究でのタイプ定義 タイプ 3 – 基本的に, 変更・挿入・削除の文数は無制限 総入れ替えレベルだと例外だが, 無かった タイプ 4 – 以下の内容を含むならクローンとして判定 ループ実装の違い（ while/for ） 条件分岐実装の違い（三項演算子 /if ） 実行順序の入れ替え 中間媒介変数の有無 26

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 修正クローンセットの等価判定 1. 各クローンを含むファイルセットが等価 2. 各クローンが同じ関数に含まれる（複数 の関数で 1 つの関数になっているのは非 等価） 3. クローン範囲に含まれる修正箇所が同じ – 一方が関数単位なので, 実質, 関数中の全て の修正を含む場合 27