Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 情報検索技術に基づく 関数クローン検出を用いた.

Presentation on theme: "Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 情報検索技術に基づく 関数クローン検出を用いた."— Presentation transcript:

1 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 情報検索技術に基づく 関数クローン検出を用いた 変更管理システムの開発 佐野 真夢 1, 吉田 則裕 2, 春名 修介 1, 井上 克郎 1 1 大阪大学 2 名古屋大学

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

3 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 構文上は異なる実装だが, 同一処理を実行している 各タイプに応じたクローン検出ツールが存在している

4 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University クローンの分類（タイプ 3 ） 4 種類意味 タイプ 1 空白, コメント等のコーディングスタイルを除いて完全に一致している タイプ 2 タイプ 1 に加え, ユーザ定義名や型の違いを除いて構文上一致している タイプ 3 タイプ 2 に加え, 文が挿入・変更・削除されている タイプ 4 構文上は異なる実装だが, 同一処理を実行している int sum(int[] data){ int sum = 0; for(int i=0;i<data.length;i++){ sum = sum + data[i]; } return sum; } int sum(int[] data){ int sum = 0; for(int i=0;i<data.length;i++){ sum += data[i]; } return sum; } 4 行目の文が異なる

5 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University クローンの分類（タイプ 4 ） 5 種類意味 タイプ 1 空白, コメント等のコーディングスタイルを除いて完全に一致している タイプ 2 タイプ 1 に加え, ユーザ定義名や型の違いを除いて構文上一致している タイプ 3 タイプ 2 に加え, 文が挿入・変更・削除されている タイプ 4 構文上は異なる実装だが, 同一処理を実行している int sum(int[] data){ int sum = 0; for(int i=0;i<data.length;i++){ sum = sum + data[i]; } return sum; } int sum(int[] data){ int sum = 0,i=0; while(i<data.length){ sum += data[i]; i++; } return sum; } for 文と while 文で実装が異なる

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

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

8 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 問題点 CloneNotifier はタイプ 3, 4 のクローンを検出できな い – 文の挿入, 削除, 変更が行われたクローン – 構文上の実装は異なるが, 処理が同じクローン 同時修正の際には, これらも確認すべき 8 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

9 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 000 山中らのクローン検出ツール [3] テキストマイニング技術を利用したクローン検出ツール 関数単位でクローンを検出する タイプ 1 ～ 4 の全てのクローンを高速に検出可能 9 [3] 山中ら, 情報検索技術に基づく高速な関数クローン検出, 情報処理学会論文誌, 2014. ワード回数 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 ・・・ クローン検出

10 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 研究概要 山中らのクローン検出ツールを利用し, 新し い クローン変更管理システムを開発 – 従来の CloneNotifier を改変する形で実装 クローン検出ツール CCFinder を山中らのクローン検 出ツールに置換 クローン（関数）の位置特定処理の追加 – 山中らの検出ツールがクローンの位置情報を出力しないた め 開発したシステムの評価実験 10

11 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 評価実験 新 CloneNotifier が, 従来の CloneNotifier では 検出できない事例を実際に検出できるか調査 – 新 CloneNotifier ： 山中らの検出ツールを使用（タイプ 1 ～ 4 ） – 従来の CloneNotifier ： CCFinder を使用（タイプ 1 ～ 2 ） 調査対象 –PostgreSQL [4] OSS のデータベース管理システム（ C 言語） 2005/01/01 ～ 2005/06/30 の 6 ヶ月間 1 週間単位で区切り 11 [4] http://www.postgresql.org/

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

13 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 評価結果 (1/2) 13 従来 CloneNotifier で は 検出不可 従来 CloneNotifier で も 検出可能 合計 126219345 新 CloneNotifier で検出されたクローンセット修正事例の数 約 1/3 が従来の CloneNotifier では検出できない 事例であった

14 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 評価結果 (2/2) 14 一貫し た 修正 非一貫し た 修正 他に適用 不能な修 正 整形 コメントの み 合計 7316325126 従来の CloneNotifer で検出できない有用な修正事例の数 一貫した修正 = クローンセットの全クローンが対象の場合のみ 非一貫した修正 = 1 つでも一貫修正がなく, かつ一部でも適用可能な修正があれば 他に適用不能 = 明らかに適用できない or する必要が無い 従来の CloneNotifier で検出できない 89 件の 有用なクローン修正事例を検出できた 従来の CloneNotifier で検出できない 89 件の 有用なクローン修正事例を検出できた

15 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 有用な事例（一貫した修正 1 ） 15 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

16 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 有用な事例（一貫した修正 1 ） 16 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 チェックの 方法を変更 変数・関数 呼出しの追加 参照先の変更 タイプ 3 2005/03/12 → 2005/03/18

17 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 有用な事例（一貫した修正 2 ） 17 src/backend/utils/adt/nabstime.ctimepl src/backend/utils/adt/nabstime.ctimemi 修正前 Changed Cloneset 2005/05/21 → 2005/05/27 timepl(PG_FUNCTION_ARGS) {... if(AbsoluteTimeIsReal(t1) && RelativeTimeIsValid(t2) && ((t2 > 0) ? (t1 < NOEND_ABSTIME - t2) : (t1 > NOSTART_ABSTIME - t2)))... } timemi(PG_FUNCTION_ARGS) {... if(AbsoluteTimeIsReal(t1) && RelativeTimeIsValid(t2) && ((t2 > 0) ? (t1 > NOSTART_ABSTIME + t2) : (t1 < NOEND_ABSTIME + t2)))... } 比較の向き が異なる 比較の向き が異なる タイプ 3 演算子が異なる

18 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 有用な事例（一貫した修正 2 ） 18 src/backend/utils/adt/nabstime.ctimepl src/backend/utils/adt/nabstime.ctimemi 修正後 Changed Cloneset 2005/05/21 → 2005/05/27 timepl(PG_FUNCTION_ARGS) {... if(AbsoluteTimeIsReal(t1) && RelativeTimeIsValid(t2) && ((t2 > 0 && t1 < NOEND_ABSTIME - t2) || (t2 NOSTART_ABSTIME - t2)))... } timemi(PG_FUNCTION_ARGS) {... if(AbsoluteTimeIsReal(t1) && RelativeTimeIsValid(t2) && ((t2 > 0 && t1 > NOSTART_ABSTIME + t2) || (t2 <= 0 && t1 < NOEND_ABSTIME + t2)))... } 三項演算子を解消し, and/or のみの表現に変更 タイプ 3

19 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 有用な事例（一貫しない修正 1 ） 19 src/backend/utils/adt/numeric.cint2_sum src/backend/utils/adt/numeric.cint4_sum src/backend/utils/adt/numeric.cint8_sum 修正前 Changed Cloneset 2005/04/02 → 2005/04/08 int4_sum(...) { int64 oldsum;... oldsum = PG_GETARG_INT64(0); if(PG_ARGISNULL(1)) PG_RETURN_INT64(oldsum); newval = oldsum + (int64) PG_GETARG_INT32(1); PG_RETURN_INT64(newval); } int8_sum(...) { Numeric oldsum;... oldsum = PG_GETARG_NUMERIC(0); if(PG_ARGISNULL(1)) PG_RETURN_NUMERIC(oldsum); newval = DirectFunctionCall1(...); PG_RETURN_DATUM(DirectFunctionCall2(..)); } ※ int2_sum と int4_sum は一貫した修正. タイプ 3 代入する式の違い 引数となる式の違い

20 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 有用な事例（一貫しない修正 1 ） 20 src/backend/utils/adt/numeric.cint2_sum src/backend/utils/adt/numeric.cint4_sum src/backend/utils/adt/numeric.cint8_sum 修正後 Changed Cloneset 2005/04/02 → 2005/04/08 int4_sum(...) {... if(fcinfo->context && IsA(...)) { int64 *oldsum = (int64*) PG_GETARG_POINTER(0); if(!PG_ARGISNULL(1)) *oldsum = *oldsum+(int64) PG_GETARG_INT32(1); PG_RETURN_POINTER(oldsum); } else { int64 oldsum = PG_GETARG_INT64(0); if(PG_ARGISNULL(1)) PG_RETURN_INT64(oldsum); newval = oldsum + (int64) PG_GETARG_INT32(1); PG_RETURN_INT64(newval); } int8_sum(...) {... oldsum = PG_GETARG_NUMERIC(0); if(PG_ARGISNULL(1)) PG_RETURN_NUMERIC(oldsum); newval = DirectFunctionCall1(...); PG_RETURN_DATUM(DirectFunctionCall2(..)); } ※ int2_sum と int4_sum は一貫した修正. 分岐処理の追加 追加は無いが, 外見上は適用できる可能性 が 考えられる 追加は無いが, 外見上は適用できる可能性 が 考えられる タイプ 3

21 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 有用な事例（一貫しない修正 2 ） 21 src/bin/pg_ctl/pg_ctl.cdo_stop src/bin/pg_ctl/pg_ctl.cdo_restart 修正前 Deleted Cloneset 2005/04/30 → 2005/05/06 do_stop(void) {... else if(pid < 0) { pid = -pid; writestderr(_("..."), progname, pid); exit(1); } if(kill((...) != 0) {... } if(!do_wait) {... } else { print_msg(...);... } do_restart(void) {... else if(pid < 0) { pid = -pid; writestderr(_("..."), progname, pid); writestderr(...); exit(1); } if(kill((...) != 0) {... } print_msg(...);... } タイプ 3 関数呼出しが多い if 分岐がある

22 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 有用な事例（一貫しない修正 2 ） 22 src/bin/pg_ctl/pg_ctl.cdo_stop src/bin/pg_ctl/pg_ctl.cdo_restart 修正後 Deleted Cloneset 2005/04/30 → 2005/05/06 do_stop(void) {... else if(pid < 0) { pid = -pid; writestderr(_("..."), progname, pid); exit(1); } if(kill((...) != 0) {... } if(!do_wait) {... } else { print_msg(...);... } do_restart(void) {... else if(pid < 0) { pid = -pid; if(postmaster_is_alived(pid) { writestderr(_("..."), progname, pid); writestderr(...); exit(1); } if(postmaster_is_alived(pid) { if(kill((...) != 0) {... } print_msg(...);... } else {... } } 適用すべきか検討は必 要 プロセス生存チェック の追加 タイプ 3

23 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University まとめと今後の課題 新しいクローン変更管理システムの開発 開発したシステムの有用性評価 今後の課題 – 従来の CloneNotifier との比較 従来版のみが検出できるクローンの調査 両システムで検出できるクローンの調査 – 対象プロジェクトの追加 23

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

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

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

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

28 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 評価 2 方法案（ 1/2 ） 1. 従来の CloneNotifer と新システムの各々 を適用して結果を得る 2. 同一の変更クローンセットをまとめる – 対応するファイルセットが同じ変更クローン セットがあれば, 変更箇所の一致をチェック –2 つのシステムが検出した変更の和集合を得 る 28

29 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 評価 2 方法案（ 2/2 ） 3. 変更集合から X 個の変更をランダムに抽 出し, 以下を数える（これを有用な事例 とする） – 一貫した修正が行われている – 一貫した修正はないが, 適用が可能 – 手作業なので X = 100 程度の予定 4. 各々のシステムが検出した有用な変更が どのくらいあるかを調べる 29