コードクローンに対する一貫性のない変更に起因する欠陥の検出 井上研究室 博士前期課程２年 Yii Yong Lee 井上研究室の Yii Yong Leeです。 では、「コードクローンに対する一貫性のない変更に起因する欠陥の検出」というタイトルで発表します。

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

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

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

欠陥の作り込み例 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に変更すべき 修士論文発表会 2008/02/15

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

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

字句解析 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 ; 修士論文発表会 2008/02/15

マッピング解析 一貫性のない修正 ＝ 不整合 一貫性のある修正 識別子変更テーブル コード片１ コード片２ 回数 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つの識別子が複数の識別子と対応する場合は、一貫性のない修正と言い、修正の不整合が発生します。 一貫性のある修正は次の手順の対象外ですので、ここで取り除きます。 一貫性のある修正 修士論文発表会 2008/02/15

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

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

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となります。 修士論文発表会 2008/02/15

Conflict 元の識別子と異なる複数の識別子に対応する場合: 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となり、欠陥の候補から取り除かれます。 修士論文発表会 2008/02/15

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

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

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

適用実験 目的：識別子の修正不整合による欠陥を検出できているかを確認 対象：Linux kernel 2.6.6 実験設定 ファイル数: 6,491 LOC: 約400万 実験設定 クローンの最小トークン数：30 UnchangedRatioの閾値：0.4 提案手法が実際に識別子の修正不整合による欠陥を検出できることを確認するために、適用実験を行いました。 実験対象はLinux kernel 2.6.6としました。 実験では、クローンの最小トークン数を３０とし、 UnchangedRatio が0.4以下の候補のみを調査しました。 修士論文発表会 2008/02/15

欠陥候補の検出 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％未満でした。 修士論文発表会 2008/02/15

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

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