Token Comparison Approach to Detect Code Clone-related Bugs YongLee Yii Yasuhiro Hayase Makoto Matsushita Katsuro Inoue 大阪大学の Yii Yong Leeです。 「Token Comparison Approach to Detect Code Clone-related Bugs」というタイトルで発表させていただきます。

概要 複製されたソースコード片の間で識別子の変更による不整合を検出し、欠陥の候補として提示する手法を提案 発表構成 研究背景 研究動機と目的 提案手法 評価実験 まとめと今後の課題 本発表では、複製されたソースコード片の間で識別子の変更による不整合を検出し、欠陥の候補として提示する手法の提案を行います。 発表の構成は、研究背景、研究動機と目的、提案手法、評価実験と考察、まとめと今後の課題という流れになります。 SIGSS 3月研究会 2008/03/03

コードクローン ソースコード中に存在する、同一または類似したコード片を持つコード片 コードの再利用のために、コピーアンドペーストにより生成 クローンペア コード片 ソースファイル まず，背景としまして，コードクローンについて説明します。 コードクローンとは、ソースコード中に存在する、同一または類似したコード片を持つコード片のことです。 この図では、みどりの部分がコードクローンを表しています。コードクローンの対をクローンペアと呼びます。 コードクローンは様々な理由により生成されます。最も多い事例としては、プログラミングの労力を減らすために、ソースコードをコピーアンドペーストして再利用することが挙げられます。 SIGSS 3月研究会 2008/03/03

再利用の際に発生する不整合 コピーアンドペーストによる再利用の手順 修正の不整合による欠陥を招く 原因となる 実装したい機能と似ているコードを複製する そのコードを編集する 修正の不整合による欠陥を招く 原因となる コードクローンとなっているコード片に識別子の名称の修正を行う 修正漏れにより不整合が発生 再利用の際に、多くの場合は、実装したい機能と似ているコードをコピーアンドペースによって複製し、そのコードを編集します。 しかし、これは修正の不整合による欠陥を招く原因となります。 例えば、コードクローンとなっているコード片に識別子の名称を修正する際に、修正漏れによって不整合が発生し、欠陥を作り込んでしまいます。 次のスライドで、このような欠陥の例を示します。 SIGSS 3月研究会 2008/03/03

欠陥の作り込み例 File: Linux-2.6.6/drivers/pci/hotplug/shpchp_ctrl.c 1497: rc = p_slot->hpc_ops->check_cmd_status(ctrl); 1498: if (rc) { 1499: err("%s: Failed to enable slot, error 　　　　　　　　　 code(%d)\n", __FUNCTION__, rc); ..... 1501: up(&ctrl->crit_sect); 1502: return rc; 1503: } ...... 1573: retval= p_slot->hpc_ops->check_cmd_status(ctrl); 1574: if (retval) { 1575: err("%s: Failed to disable slot, error 　　　　　　　　　code(%d)\n", __FUNCTION__, rc); 1576: 1577: up(&ctrl->crit_sect); 1578: return retval; 1579: } コード片1 この例は実際に Linux の Kernel で見つけた欠陥です。 コード片１とコード片２はクローンペアとして検出されました。このクローンペアはコピーアンドペーストにより生成された可能性が高いと考えられます。 コード片１で rc であった識別子は、コード片２では全てretvalに変更される必要がありますが、 ここに一つ修正漏れがあります。 この欠陥により、システムは間違ったエラーコードを表示します。 コード片2 Retvalに変更すべき SIGSS 3月研究会 2008/03/03

研究動機と目的 大規模ソフトウェアにはコードクローンが多く存在する 修正漏れによる欠陥は実際のシステムに多く存在している Linuxファイルシステムを実装したコードの１２％はクローンとなっている 修正漏れによる欠陥は実際のシステムに多く存在している 大量のソースコードを精査するには労力がかかる 一貫性のない識別子の修正による欠陥を検出 特定の範囲のみコードを精査 大規模ソフトウェアに適用できる 過去の研究によると、大規模ソフトウェアにコードクローンが多く存在します。 実際のシステムには、先程述べたような修正漏れによる欠陥も多く存在しています。 このような欠陥を取り除くためには、大量のソースコードを精査する必要がありますが、これは大きな労力がかかります。 本研究では、大規模ソフトウェアに潜在する一貫性のない識別子の修正による欠陥を、特定の範囲のコードを精査することにより効率的に検出することを目的としています。 SIGSS 3月研究会 2008/03/03

提案手法 検出されたコードクローンをトークンに分割 不整合が検出された識別子を欠陥候補として出力 ソースファイル 欠陥候補の絞り込み メトリクス計算 不整合のフィルタリング マッピング解析 クローン検出ツール 字句解析 クローン位置情報ファイル クローンペアのトークン列 修正の不整合 欠陥候補 提案手法の流れはこのようになっています。 まず、クローン検出ツールにより、ソースファイルに存在するコードクローンを検出し、クローン位置情報ファイルを出力します。 次に、字句解析部が、クローンの位置情報を用いて、コードクローンをトークン単位に分割します。 そして、クローンペアの間で対応する識別子のマッピングを行い、識別子間の不整合を検出します。 さらに、メトリクスを用いて欠陥の可能性が低い不整合を取り除きます。 最後に、不整合が検出された識別子を欠陥候補として提示します。 ここから、各手順の詳細を説明します。 検出されたコードクローンをトークンに分割 不整合が検出された識別子を欠陥候補として出力 クローン検出ツールを用いてソースファイルに存在するコードクローンを検出 メトリクスを用いて欠陥の可能性が低い不整合を取り除く クローンペア間で対応する識別子のマッピングを行い、識別子間の不整合を検出 SIGSS 3月研究会 2008/03/03

字句解析 o_count 127: o_count = v_count; 128: o_var = variables; 129: 130: v_count += STORE_INCR; 131: variables = (char **) malloc (v_count*sizeof(char *)); 132: 133: for (indx = 3; indx < o_count; indx++) 134: variables[indx] = o_var[indx]; 135: 136: for (; indx < v_count; indx++) 137: variables[indx] = NULL; 　　　...... 161: o_count = a_count; 162: o_ary = arrays; 163: 164: a_count += STORE_INCR; 165: arrays = (char **) malloc (a_count*sizeof(char *)); 166: 167: for (indx = 1; indx < o_count; indx++) 168: variables[indx] = o_ary[indx]; 169: 170: for (; indx < v_count; indx++) 171: lists[indx] = NULL; = v_count ; o_var = varse ; v_count += STORE_INCR varse = ( char ** ) malloc ( v_count * sizeof ( char * ) ) ; for ( indx = 1 ; indx < o_count ; indx ++ ) varse [ indx ] = o_var [ indx ] ; for ( ; indx < v_count ; indx ++ ) varse [ indx ] = NULL ; o_count = a_count ; o_ary = arrays ; a_count += STORE_INCR 字句解析は、検出されたクローンペアをプログラミング言語の字句規則に基づいてトークン単位に分割します。 コード片ごとにそれぞれ１つのトークン列が作られます。 そして、トークン列から識別子を特定します。 arrays = ( char ** ) malloc ( a_count * sizeof ( char * ) ) ; for ( indx = 1 ; indx < o_count ; indx ++ ) varse [ indx ] = o_ary [ indx ] ; for ( ; indx < v_count ; indx ++ ) lists [ indx ] = NULL ; SIGSS 3月研究会 2008/03/03

マッピング解析 一貫性のない修正 ＝ 不整合 一貫性のある修正 識別子変更テーブル コード片１ コード片２ 回数 varse arrays ; o_var varse = o_count v_count += STORE_INCR ( char ) ** ・・・・・・ コード片２ ; o_ary arrays = o_count a_count += STORE_INCR ( char ) ** ・・・・・・ 識別子変更テーブル コード片１ コード片２ 回数 varse arrays 2 lists 1 v_count a_count 4 o_count o_var o_ary 一貫性のない修正　＝　不整合 次の手順であるマッピング解析では、クローンペア間に対応する識別子に対してマッピングを行い、その結果を識別子変更テーブルにまとめます。 コード片１にある識別子が常にコード片２にある同じ識別子と対応する場合、一貫性のある修正といいます。逆に、1つの識別子が複数の識別子と対応する場合は、一貫性のない修正と言い、修正の不整合が発生します。 一貫性のある修正、または変更されていない識別子は欠陥になりませんので、ここで取り除きます。 一貫性のある修正 SIGSS 3月研究会 2008/03/03

欠陥候補の絞り込み 全ての不整合は必ずしも欠陥ではない 2つの可能性がある メトリクスを用いて修正漏れによる欠陥の可能性の度合を数値化する 修正漏れによる欠陥である場合 意図的に変更されていない場合 メトリクスを用いて修正漏れによる欠陥の可能性の度合を数値化する UnchangedRatio Conflict しかし、全ての不整合は必ずしも欠陥ではありません。 ここで、不整合には2つの可能性があります。1つ目は、修正漏れによる欠陥である場合、2つ目は、意図的に変更されていない場合です。 そこで、修正漏れによる欠陥のみを抽出するために、メトリクスを用いて修正漏れによる欠陥の可能性の度合を数値化します。 本研究では、２つのメトリクスを用いました。 これから、この2つのメトリクスを説明します。 SIGSS 3月研究会 2008/03/03

UnchangedRatio 識別子がほとんどの箇所で変えられて、数箇所だけで変えられていない場合、欠陥の可能性が高い NumOfUnchangedID UnchangedRatio = TotalNumOfID クローンとなっているコード片にある識別子の変更されていない比率 UnchangedRatioが０に近い場合、変更されていない識別子は欠陥の有力な候補となる 変更漏れの可能性が高い UnchangedRatioが０、または１の場合、不整合が発生しないことを示す UnchangedRatio=0の時、全ての識別子が変更されている UnchangedRatio=1の時、全ての識別子が変更されていない 1つ目のメトリクスはUnchangedRatioです。 このメトリクスは、識別子がほとんどの箇所で変えられて、数箇所だけで変えられていない場合、欠陥の可能性が高いことを仮定します。 この仮定を踏まえてUnchangedRatioをこのように定義され、クローンとなっているコード片にある識別子の変更されていない比率を計算します。 UnchangedRatioが０に近い場合、変更されていない識別子は欠陥の有力な候補となります。つまり、変更漏れの可能性が高いです。 UnchangedRatio=0の時、全ての識別子が変更されています。一方、 UnchangedRatio=1の時、全ての識別子が変更されていません。したがって、UnchangedRatioが０、または１の場合、不整合が発生しないことを表します。 次に UnchangedRatio の計算例を示します。 SIGSS 3月研究会 2008/03/03

UnchangedRatioの計算例 v_countのUnchangedRatioは0.20となる この変数名は5回出現している コード片１ コード片２ 回数 UnchangedRatio v_count a_count 4 0.20 1 varse arrays 2 0.25 lists v_countのUnchangedRatioは0.20となる この変数名は5回出現している コード片２で１回変更されていない この識別子変更テーブルには、コード片１にある識別子とコード片２で対応する識別子の名前が記録されています。 例えば、v_countはコード片１で５回出現しており、コード片2では5回のうち、一回変更されていないため、 UnchangedRatioは0.2となります。 SIGSS 3月研究会 2008/03/03

Conflict このような場合は、Conflict = trueと設定 欠陥の候補から取り除く コード片１にある識別子がコード片２で元の識別子と異なる複数の識別子に対応する場合は、機能を実装するために、意図的に複数の識別子の名称に変更した可能性が高い このような場合は、Conflict = trueと設定 欠陥の候補から取り除く コード片１　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 コード片２ 回数 UnchangedRatio Conflict v_count a_count 4 0.20 False 1 varse arrays 2 0.25 True lists 2つ目のメトリクスは Conflict です。 コード片１にある識別子がコード片２で元の識別子と異なる複数の識別子に対応する場合は、機能を実装するなどのために、意図的に複数の識別子の名称に変更した可能性が高いと考えられます。 このような場合は、 Conflict を true とし、欠陥の候補から取り除きます。 このテーブルでは、varseは 複数の異なる識別子である arraysとlistsに対応しますので、conflict = trueとなり、欠陥の候補から取り除かれます。 SIGSS 3月研究会 2008/03/03

出力される欠陥候補 コード片１ コード片２ 回数 UnchangedRatio Conflict v_count a_count 4 0.20 False 1 コピー元のコード片 コピー先のコード片 識別子 UnchangedRatio コード片１ コード片２ v_count 0.20 最後に、メトリクスを用いて修正の不整合を絞り込んだ結果を出力します。 欠陥の候補は、コピー元のコード片、コピー先のコード片、不整合を起こした識別子、そして UnchangedRatio の値から成ります。 SIGSS 3月研究会 2008/03/03

提案手法の実装 対象言語：ＣとJava ツールの記述言語： Java クローン検出部には既存のコードクローン検出ツールCCFinderを利用 字句解析部は字句解析器生成ツールJFLEXを用いて構築 検出された欠陥候補を可視化するために、GUIで提示 提案手法を実装した欠陥検出ツールを試作しました。 現在のところ、対象言語はＣとJavaになっています。 クローン検出部には、既存のコードクローン検出ツールであるCCFinderを用いました。 また、字句解析部は字句解析器生成ツールJFLEXを用いて構築しました。 ユーザはＧＵＩを通じて、欠陥候補のインスペクションを行うことができます。 SIGSS 3月研究会 2008/03/03

ツールのＧＵＩ 欠陥候補リスト ソースコードビュー 識別子変更テーブル これは、ツールのスナップショットです。 この部分は欠陥候補リストと呼ばれるもので、欠陥候補の一覧を表示します。識別子のUnchangedRatioに基づいて一覧を昇順、降順にソートすることができます。 欠陥候補リストで候補を選択すると、その候補を含む識別子変更テーブルが表示されます。 また、ソースコードビューでは、選択された欠陥候補のコード片と、周辺のソースコードも表示されます。 SIGSS 3月研究会 2008/03/03

適用実験 目的： 対象：Linux kernel 2.6.6 実験設定 識別子の修正不整合による欠陥を検出できているかを確認 Conflictの有効性を評価 対象：Linux kernel 2.6.6 ファイル数: 6,491 LOC: 約400万 実験設定 クローンの最小トークン数：30 UnchangedRatioの閾値：0.4 提案手法が実際に識別子の修正不整合による欠陥を検出できることを確認するために、適用実験を行いました。 また、実験を通じて本研究で定義したメトリクスであるConflictの有効性も評価します。 実験対象はLinux kernel 2.6.6としました。 実験では、クローンの最小トークン数を３０とし、 UnchangedRatio が0.4以下の候補のみを調査しました。 SIGSS 3月研究会 2008/03/03

欠陥候補の検出 archモジュールでは87個、driversモジュールでは120個の欠陥候補が検出された ファイル数 総行数 欠陥候補数 欠陥候補を含むクローンの総行数 Linux-2.6.6/arch 2,355 724,858 87 1,615 Linux-2.6.6/drivers 2,323 2,344,594 120 3,637 archモジュールでは87個、driversモジュールでは120個の欠陥候補が検出された 欠陥候補を含むクローンの総行数はモジュールの総行数の0.25％未満 提案手法を実行したところ、archモジュールでは87個、driversモジュールでは120個の欠陥候補が検出されました。 欠陥候補を含むクローンの総行数はモジュールの総行数の0.25％未満でした。 SIGSS 3月研究会 2008/03/03

欠陥候補の検証 検証方法：Linuxの変更記録やLinux-2.6.6以降のバージョンと確認 修正された欠陥は3件 モジュール 証明された欠陥数 可能性の高い欠陥数 欠陥以外個数 合計 arch 3 5 79 87 検証方法：Linuxの変更記録やLinux-2.6.6以降のバージョンと確認 修正された欠陥は3件 欠陥の可能性が高い候補は5件 僅かなコードを調べることで 8 件もの欠陥を検出できた 検出された欠陥候補を確認したところ、実際に欠陥だと考えられる候補が 8 件見つかりました。 Linux の変更記録や Linux 2.6.6 以降のバージョンを調べたところ、このうち3件は未来のバージョンで修正されていました。 僅かなコードを調べることで 8 件もの欠陥を検出できたことから、本手法の有効性が示されました。 SIGSS 3月研究会 2008/03/03

Conflictの効果（候補の数） Conflictを無効とする時と比べて欠陥候補数を29%減らした モジュール Conflictフィルタリング無効 Conflictフィルタリング有効 証明された欠陥数 可能性の高い欠陥数 合計 arch 3 5 123 87 ２９%減 Conflictを無効とする時と比べて欠陥候補数を29%減らした 取り除いた欠陥候補には実際の欠陥が含まれていない 続いて、Conflictの効果の評価ですが、Conflictフィルタリングを無効とするときに、欠陥候補は123件が検出されました。 一方、Conflictフィルタリングを有効とするときに、欠陥候補は87件が検出されました。つまり、欠陥候補数を29%減らしました。 また、取り除いた欠陥候補のうちに実際の欠陥が含まれていないことから、Conflictの有効性が示されました。 SIGSS 3月研究会 2008/03/03

Conflictの効果（発見された欠陥数） 32%減 42 62 このグラフは、archモジュールに潜在する欠陥を検査する際に、Conflictフィルタリングがどのくらい有効に働くかを評価したものです。x軸は調査した欠陥数を表し、y軸は累積した欠陥数を表します。 Conflictフィルタリングを無効としたときには、 8件目の欠陥を見つかるためには、62個目までの欠陥候補を調査することが必要でした。 一方、 Conflictフィルタリングを有効としたときには、42個目までの欠陥候補を調査することで、8件の欠陥を見つけることができました。 つまり、Conflictフィルタリングにより、調査すべき欠陥候補数を32%減らすことが出来ました。 この結果から、Conflictフィルタリングによって、より少ない数の候補を調査することで欠陥を見つけられることがわかりました。 Conflictフィルタリングの有無に対し、archモジュールに潜在する8件の欠陥を見つかるために調査すべき欠陥候補の数を示す SIGSS 3月研究会 2008/03/03

まとめと今後の課題 まとめ 今後の課題 ソフトウェアに多く存在しているコードクローンに着目 クローンとなっているコード片の間で識別子に対する修正の不整合を検出する手法を提案 修正の不整合を絞り込み、欠陥候補を提示 今後の課題 他の種類のクローンに適用 他の手法との比較 では，まとめと今後の課題について述べます。 本研究では，ソフトウェアに多く存在しているコードクローンに着目し、クローンとなっているコード片の間で識別子に対する修正の不整合を検出する手法を提案しました。検出された修正の不整合を絞り込んで、欠陥の候補として提示します。 今後は、実装したツールを改善し、他の種類のクローンに適応できるようにしたいと考えています。 また、他の手法との比較が考えられます。 SIGSS 3月研究会 2008/03/03