大規模ソースコード集合を対象とした類似関数集合群の抽出大阪大学大学院情報科学研究科コンピュータサイエンス専攻 ○田中健介，肥後芳樹，楠本真二 1 研究概要 • 大規模ソースコードから関数単位のクローンセットを生成する手法を提案 – 類似した関数集合群の抽出 • 約2,000のソフトウェアに対して適用実験 – 再利用性の高い関数の検出 – メトリクスによる関数のフィルタリング 2 研究背景 • ソフトウェア開発の大規模化 – 開発コストの増大これまで作成したソースコードやオープンソース資源の再利用 • 問題点 – 再利用候補の発見多数存在する処理の把握処理の類似した部分を発見できないだろうか・・・ 3 コードクローンとは？ • ソースコード上に存在する類似したコード片 • 主にコピー＆ペーストによって発生コピー＆ペーストコピー＆ペースト処理が類似した部分を発見することができる！ 4 クローンペアとクローンセット • クローンペア – 互いに類似する２つのコード片 • クローンセット – 互いに類似するコード片の集合類似した処理の集合コードクローン clone A-1 クローンペア類似した処理を効率的に把握・再利用！ clone A-1 clone A-2 clone A-1 clone A-2 クローンセット clone A-3 clone B-1 clone B-1 clone A-1 clone A-3 clone A-2 5 既存のクローン検出ツールの問題点 • 一度に検出対象にできるソースコードの量に限界がある – 大規模ソースコードに適用不可能 • 大規模ソースコードを対象にしたクローンセットを生成する手法は提案されていない複数のクローン検出結果を組合わせてクローンセットを生成できないだろうか？ 6 クローンセット生成のアイデアコードクローンコードクローン結果を組合せた検出結果１クローンセット検出結果２ funcA { } funcC { funcE { } } 一回目の検出対象二回目の検出対象 funcB { funcD { funcF { } } } ソースコード１ソースコード２ソースコード３関数（機能）単位クローンを検出！ 7 関数クローンペアの検出 funcA { funcB { } } ソースコード１ソースコード２クローン行の割合が閾値を超えた場合互いに関数クローンペア 8 関数クローンセットの定義 • 関数 a i と関数クローンペアになる関数の集合が {b1 , b2 , b3 ,...bn }の場合、{ai , b1 , b2 , b3 ,...bn } を a i をもとにした関数クローンセット関数をもとにした関数クローンセット 9 関数クローンセットのマージ関数クローンペア関数クローンセットマージ 10 再利用性の高い関数 • 再利用性の高い関数とは？ – 複数回記述されている – 多くのソフトウェアに存在する – ソフトウェアの種類に関係なく利用されている – ある特定のソフトウェアで何度も記述されている関数クローンセットから特定するには・・・ •関数クローンセットの要素数 •関数クローンセットの要素の行数 •関数クローンセットの要素が存在するソフトウェアの数 •関数クローンセットの要素が存在するソフトウェアの偏り 11 関数クローンセットメトリクス (1/2) • ある関数クローンセットに対して関数の利用回数 – POP ( Population ) : 要素数 – LEN ( Length ) : 要素の平均行数関数の規模 – FOF ( Frequency of Functions ) : 要素がいくつのソフトウェアにあるか – DOS ( Dispersion of Software ) : 関数の汎用性要素がどの程度異なるソフトウェアに分散しているか DOS  ( FOF  1)  ( POP  1) [例] 要素数３の関数クローンセットが・・・・1つのソフトウェアから得られた → (1  1)  (3  1)  0 ・3つのソフトウェアから得られた → (3  1)  (3  1)  1 12 関数クローンセットメトリクス (2/2) • ある関数クローンセットに対して関数の汎用性 – GVOF ( General Versatility of Functions )：要素がいくつのドメインにあるか – DOD ( Dispersion of Domains )：要素がどの程度異なるドメインに分散しているか DOD  (GVOF  1)  ( POP  1) [例] 要素数３の関数クローンセットが・・・・1つのドメインから得られた → (1  1)  (3  1)  0 ・3つのドメインから得られた → (3  1)  (3  1)  1 ソフトウェアの種類による分類．dns，editors，ｆｔｐなど 13 関数クローンセットメトリクスの例関数クローンセット ①関数A，ドメインα，ソフトウェアⅠ POP = 7 ②関数B，ドメインα，ソフトウェアⅠ FOF = 5 ③関数C，ドメインα，ソフトウェアⅡ DOS = 4 / 6 = 0.67 ④関数D，ドメインα，ソフトウェアⅢ ⑤関数E，ドメインβ，ソフトウェアⅣ ⑥関数F，ドメインβ，ソフトウェアⅣ ⑦関数G，ドメインγ，ソフトウェアⅤ GVOF = 3 DOD = 2 / 6 = 0.33 14 実装 • 一台の計算機では計算時間が膨大 • 並列計算を利用 – 複数の計算機で関数クローンペアを検出 • 関数の位置情報の抽出（Ctags） • クローン検出ツールの実行（CCFinder） • 関数クローンペアの検出 – 検出結果を一台の計算機集め、関数クローンセットを生成計算時間の削減が可能！ 15 実験 • 実験で調査したいこと – 関数クローンと閾値との関係 – 関数クローンセットメトリクスと関数クローンとの関係 • 実験方法 – 実験対象から閾値別に関数クローンペア・セットを生成し，関数クローン数を確認 – メトリクス別に関数クローン数を確認 • 実験対象：FreeBSDソフトウェア集合ports（C言語）関数クローンペアを得る際，関数のクローン行の割合 16 ケース１～1つのドメインを対象とした場合～ • 対象：mailドメイン – ソフトウェア数：717 – 総行数：27,076,351 • 目的：同ドメインのソフトウェア間の関数クローンの調査 • クローン検出方法 – 完全一致検出 – 名前変更検出ソフトウェアの種類による分類．dns，editors，ｆｔｐなど 17 完全一致 / 名前変更検出コードクローンでないと判定完全一致検出名前変更検出コードクローンであると判定（完全一致に比べ多くのクローン） 18 閾値60%以上のほとんどが関数は修正されずに実験結果閾値が上がるにつれて減少閾値100%の関数クローン（セット）そのまま利用されることが多い～mailドメイン～ THRESHOLD (%) 60 70 80 90 100 ペア数（完全一致） 475,022 446,592 421,502 403,447 383,091 セット数（完全一致） 70,796 69,910 69,024 5%減 67,941 67,064 関数の数（完全一致） 255,050 252,275 249,466 1%減 246,275 242,868 ペア数（名前変更） 1,064,941 929,141 819,848 763,538 718,048 セット数（名前変更） 72,196 70,971 69,313 8%減 67,881 66,455 関数の数（名前変更） 269,463 265,787 261,757 6%減 257,541 253,455 THRESHOLD・・・関数クローンペアとなるクローン行の割合の閾値 19 617,713個の関数のうち253,455個を実験結果名前変更のほうが多くの関数クローンペア完全一致のほうが多い・・・？ 66,455種類に分類～mailドメイン～ THRESHOLD (%) ペア数（完全一致） 60 70 80 90 100 475,022 446,592 421,502 403,447 383,091 セット数（完全一致）使用されているソフトウェアに偏りがある関数 70,796 69,910 69,024 67,941 多くのソフトウェアに分散して使用されている関数関数の数 255,050 252,275 249,466 246,275 →FOF，DOS （完全一致） 67,064 242,868 パラメータ化により関数クローンセット同士が類似するためペア数 1,064,941 929,141 819,848 763,538 718,048 セット数（名前変更） 72,196 70,971 69,313 67,881 66,455 関数の数（名前変更） 269,463 265,787 261,757 257,541 253,455 （名前変更） THRESHOLD・・・関数クローンペアとなるクローン行の割合の閾値 20 メトリクス値と関数クローンセット数との関係ソフトウェア間の関数クローンのほうが多い同ドメイン内の関数クローンは分散傾向～mailドメイン～ほぼ全て lightning，thunderbird，enigmail-thunderbird，enigmail-seamonkey 間要素がある1つのソフトウェアにのみ存在する DOS 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 postfix，postfix23，postfix24，postfix-current間関数クローンセット数 ~0.1 ~0.2 ~0.3 ~0.4 ~0.5 ~0.6 ~0.7 ~0.8 ~0.9 ~1.0 FOF 1 2 3 mutt，mutt-lite，mutt-devel，mutt-devel-lite 間 3,405 0 0 0 0 0 0 0 0 bogofilter，bogofilter-qdbm，bogofilter-sqlite，bogofilter-tc間トータル 40 108 36 の関数クローンセット 307 252 0 0 0 0 3,405 ソースファイル単位のクローン 9,942 38 57 66 411 34 0 148 0 4 164 510 537 263 2,661 19 0 920 0 35,891 5 7 91 別バージョンや拡張機能 58 90 88 40 11 199 0 812 6 1 16 22 17トータル 36 3 2 0 15 53 7 0 13 4 1 63,050 8 3 2 0 15 53 8 0 1 30 9 0 5 17 10~ 0 4 79 多くのソフトウェアで分散して利用されている 4 5 0 4 0 0 1 （高FOF，高DOSの）関数は 1 1 0 0 0 1 4 どのような機能があるのか？ 0 2 0 1 1 10 13 要素が複数のソフトウェアに存在する FOF : 要素がいくつのソフトウェアに存在しているか関数クローンセット数 DOS : 要素がどの程度異なるソフトウェアに分散しているか 0 0 7,643 21 関数クローンの例 FOF，DOSを利用することにより～mailドメイン～ mailドメインにおいて再利用性の高い関数を得ることができた！ FOF : 26 DOS : 1.0 FOF 23，DOS 1.0： UINT4からunsigned charにエンコードする関数 MD5メッセージダイジェスト操作を終了する関数 FOF 21，DOS 1.0： unsigned charからUINT4にデコードする関数 MD5の基本的な変換を行う関数 FOF 19，DOS 1.0 文字列をコピーする関数など・・・文字列において指定した文字へのポインタを返す関数 22 ケース２～複数のドメインを対象とした場合～ • 対象：8ドメイン( accessibility, archivers, benchmarks, converters, finance, ftp, irc, misc ) – ソフトウェア数：1,306 – 総行数：18,339,890 • 目的：ドメイン間の関数クローンの調査 • クローン検出方法 – 完全一致検出 – 名前変更検出 23 421,008個の関数のうち88,918個を名前変更のほうが多くの関数クローンペア・セット実験結果閾値が上がるにつれて大きく減少 36,378種類に分類差が大きい～複数ドメイン～ THRESHOLD (%) 60 ペア数（完全一致）セット数（完全一致）関数の数（完全一致） 88,913 70 80,417 80 72,405 90 65,927 使用されているドメインに偏りがある関数 36,980 34,798 24%減 32,717 30,468 多くのドメインに分散して使用されている関数変更の加えられた関数クローンが多い！ 83,070 78,311 23%減 73,912 69,443 →GVOF，DOD 100 56,832 28,016 64,122 ペア数（名前変更） 407,860 335,802 259,790 221,538 201,565 セット数（名前変更） 49,290 45,966 41,818 26%減 38,941 36,378 関数の数（名前変更） 113,387 107,011 99,980 22%減 94,238 88,918 THRESHOLD・・・関数クローンペアとなるクローン行の割合の閾値 24 ドメイン間の関数クローンのほうが少ないメトリクス値と関数クローンセット数との関係 2つのドメイン間の関数クローンが多いソースファイル単位のクローン～複数ドメイン～ DOD GVOF 1 2 3 要素がある1つのドメインにのみ存在する 0.2 0.3 0.4 0.5 0.6 0.7 ~0.3 関数クローンセット数 ~0.4 ~0.5 ~0.6 ~0.7 ~0.8 0.0 ~0.1 0.1 ~0.2 0.8 ~0.9 0 0 0トータル 0 0 0 0 多くのドメインで分散して利用されているドメイン間の関数クローンは 268 220 （高GVOF，高DODの）関数は 67 91 31,923 1,198 0 0 0 特定のソフトウェア，ドメイン間での数の偏りはなかったどのような機能があるのか？ 31,923 0.9 ~1.0 0 0 0 1,263 55 129 143 129 86 0 103 0 0 206 4 0 13 36 50 33 25 0 26 0 2 5 0 40 20 24 11 1 4 2 0 0 6 190 4 2 6 0 0 0 0 0 7 0 3 0 0 0 0 0 0 5 トータル 0 4,455 0 GVOF : 要素がいくつのドメインに存在しているか要素が複数のドメインに存在する DOD : 要素がどの程度異なるドメインに分散しているか関数クローンセット数 25 関数クローンの例 GVOF，DODを利用することにより～複数ドメイン～ドメインによらず汎用的な機能の関数を得ることができた！ GVOF :7 DOD : 0.38 GVOF 7，DOD 0.15：文字列に対して指定した文字へのポインタを返す関数引数1つの関数を複数回呼び出す関数 GVOF 6，DOD 0.45：引数2つの関数を複数回呼び出す関数コマンドライン引数の要素を調べる関数カレントディレクトリのパス名を返す関数など・・・メモリ領域を解放する関数 26 まとめと今後の課題 • 大量のソースコードから関数クローンセットを生成する手法を提案 • 今後の課題 – クローン検出ツールによる比較実験 – 他のプログラミング言語を対象とした実験 – 関数の呼び出し回数に応じた評価方法 27