大規模ソースコード集合を対象とした 類似関数集合群の抽出

Presentation on theme: "大規模ソースコード集合を対象とした 類似関数集合群の抽出"— Presentation transcript:

1 大規模ソースコード集合を対象とした 類似関数集合群の抽出
大阪大学大学院情報科学研究科 コンピュータサイエンス専攻 ○田中 健介，肥後 芳樹，楠本 真二

2 研究概要 大規模ソースコードから関数単位のクローンセットを生成する手法を提案 約2,000のソフトウェアに対して適用実験
類似した関数集合群の抽出 約2,000のソフトウェアに対して適用実験 再利用性の高い関数の検出 メトリクスによる関数のフィルタリング

3 研究背景 ソフトウェア開発の大規模化 問題点 開発コストの増大 これまで作成したソースコードやオープンソース 再利用候補の発見 資源の再利用
多数存在する処理の把握 [前回の指摘] 次ページでいきなりコードクローンの説明は飛躍がある．なぜコードクローンを使うのか．処理が類似した部分を見つければ再利用候補にもコード理解にも便利という繋ぎがほしい． 処理の類似した部分を発見できないだろうか・・・

4 処理が類似した部分を発見することができる！
コードクローンとは？ ソースコード上に存在する類似したコード片 主にコピー＆ペーストによって発生 コピー＆ペースト コピー＆ペースト 処理が類似した部分を発見することができる！

5 クローンペアとクローンセット クローンペア クローンセット 類似した処理の集合 類似した処理を効率的に把握・再利用！
互いに類似する２つのコード片 クローンセット 互いに類似するコード片の集合 コードクローン clone A-1 類似した処理の集合 クローンペア 類似した処理を効率的に把握・再利用！ clone A-1 clone A-2 clone A-1 clone A-2 クローンセット clone A-3 clone A-1 clone A-2 clone B-1 clone B-1 clone A-3

6 既存のクローン検出ツールの問題点 一度に検出対象にできるソースコードの量に限界がある
大規模ソースコードに適用不可能 大規模ソースコードを対象にしたクローンセットを生成する手法は提案されていない 複数のクローン検出結果を組合わせて クローンセットを生成できないだろうか？

7 クローンセット生成のアイデア 一回目の検出対象 二回目の検出対象 関数（機能）単位クローンを検出！ コードクローン 検出結果１
結果を組合せた クローンセット 二回目の検出対象 コードクローン 検出結果２ funcA { } funcB { funcC { } funcD { funcE { } funcF { 関数（機能）単位クローンを検出！ ソースコード１ ソースコード２ ソースコード３

8 関数クローンペアの検出 クローン行の割合が閾値を超えた場合 互いに関数クローンペア ソースコード１ ソースコード２ funcA {
} funcB { } [前回の指摘] 展開がはやい，閾値をこえたら関数クローンというのがわかり辛い ソースコード１ ソースコード２ クローン行の割合が閾値を超えた場合 互いに関数クローンペア 8

9 関数クローンセットの定義 関数 と関数クローンペアになる関数の集合 が の場合、 を をもとにした関数クローンセット
関数　　と関数クローンペアになる関数の集合 が　　　　　　　　　　 の場合、 を　　をもとにした関数クローンセット 関数　　をもとにした 関数クローンセット

10 関数クローンセットのマージ 関数クローンペア 関数クローンセット マージ

11 関数クローンセットから特定するには・・・
再利用性の高い関数 再利用性の高い関数とは？ 複数回記述されている 多くのソフトウェアに存在する ソフトウェアの種類に関係なく利用されている ある特定のソフトウェアで何度も記述されている 関数クローンセットの要素数 関数クローンセットの要素の行数 関数クローンセットの要素が存在するソフトウェアの数 関数クローンセットの要素が存在するソフトウェアの偏り 関数クローンセットから特定するには・・・ [前回の指摘] メトリクスの説明の前にメトリクスが必要な理由？メトリクス利用に至る事情？のようなのがほしい．

12 関数クローンセットメトリクス (1/2) ある関数クローンセットに対して POP ( Population ) : 要素数
LEN ( Length ) : 要素の平均行数 FOF ( Frequency of Functions ) : 要素がいくつのソフトウェアにあるか DOS ( Dispersion of Software ) : 要素がどの程度異なるソフトウェアに分散しているか 関数の利用回数 関数の規模 関数の 汎用性 [前回の指摘] メトリクスの印象が薄い． 語源を乗せると印象にのこるかも． DOSの例をのせるとよい． 「３つの要素からなる関数クローンセットがありました．この場合は～，この場合は～．」 [例] 要素数３の関数クローンセットが・・・ ・1つのソフトウェアから得られた → ・3つのソフトウェアから得られた → 　　 1

13 関数クローンセットメトリクス (2/2) ある関数クローンセットに対して 関数の汎用性
GVOF ( General Versatility of Functions )： 　要素がいくつのドメインにあるか DOD ( Dispersion of Domains )： 　要素がどの程度異なるドメインに分散しているか 関数の汎用性 [例] 要素数３の関数クローンセットが・・・ ・1つのドメインから得られた → ・3つのドメインから得られた → 　　 1 ソフトウェアの種類による分類．dns，editors，ｆｔｐなど

14 関数クローンセットメトリクスの例 関数クローンセット POP = 7 ①関数A，ドメインα，ソフトウェアⅠ FOF = 5
②関数B，ドメインα，ソフトウェアⅠ ③関数C，ドメインα，ソフトウェアⅡ DOS = 4 / 6 = 0.67 ④関数D，ドメインα，ソフトウェアⅢ GVOF = 3 ⑤関数E，ドメインβ，ソフトウェアⅣ DOD = 2 / 6 = 0.33 ⑥関数F，ドメインβ，ソフトウェアⅣ ⑦関数G，ドメインγ，ソフトウェアⅤ

15 実装 一台の計算機では計算時間が膨大 並列計算を利用 計算時間の削減が可能！ 複数の計算機で関数クローンペアを検出
関数の位置情報の抽出（Ctags） クローン検出ツールの実行（CCFinder） 関数クローンペアの検出 検出結果を一台の計算機集め、関数クローンセットを生成 計算時間の削減が可能！

16 実験 実験で調査したいこと 実験方法 実験対象：FreeBSDソフトウェア集合ports（C言語） 関数クローンと閾値との関係
関数クローンセットメトリクスと関数クローンとの関係 実験方法 実験対象から閾値別に関数クローンペア・セットを生成し，関数クローン数を確認 メトリクス別に関数クローン数を確認 実験対象：FreeBSDソフトウェア集合ports（C言語） 関数クローンペアを得る際，関数のクローン行の割合

17 ケース１ ～1つのドメインを対象とした場合～ 対象：mailドメイン 目的： クローン検出方法 ソフトウェア数：717
総行数：27,076,351 目的： 　同ドメインのソフトウェア間の関数クローンの調査 クローン検出方法 完全一致検出 名前変更検出 ソフトウェアの種類による分類．dns，editors，ｆｔｐなど

18 完全一致 / 名前変更 検出 コードクローンでないと判定 完全一致検出 名前変更検出
コードクローンであると判定（完全一致に比べ多くのクローン） コードクローンでないと判定 完全一致検出 名前変更検出

19 実験結果 ～mailドメイン～ 閾値60%以上のほとんどが 閾値100%の関数クローン（セット）
閾値が上がるにつれて減少 関数は修正されずに そのまま利用されることが多い THRESHOLD (%) 60 70 80 90 100 ペア数 （完全一致） 475,022 446,592 421,502 403,447 383,091 セット数 （完全一致） 70,796 69,910 69,024 67,941 67,064 関数の数 （完全一致） 255,050 252,275 249,466 246,275 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 5%減 1%減 8%減 6%減 関数クローンペア閾値が上昇するにつれてそれぞれの数でゃ減少しているが，その減少幅は少ない．閾値60%の関数クローンセット，ユニークな関数の数はほぼ閾値100%となっている．67%，92%，94%． 閾値100%の関数クローンセット群を選択した場合，617,713個の関数のうち253,455個を66,455個に分類した． THRESHOLD・・・関数クローンペアとなるクローン行の割合の閾値

20 実験結果 ～mailドメイン～ 617,713個の関数のうち253,455個を 66,455種類に分類
名前変更のほうが多くの関数クローンペア 完全一致のほうが多い・・・？ THRESHOLD (%) 60 70 80 90 100 ペア数 （完全一致） 475,022 446,592 421,502 403,447 383,091 セット数 （完全一致） 70,796 69,910 69,024 67,941 67,064 関数の数 （完全一致） 255,050 252,275 249,466 246,275 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 使用されているソフトウェアに偏りがある関数 多くのソフトウェアに分散して使用されている関数 →FOF，DOS パラメータ化により関数クローンセット同士が類似するため 関数クローンペア閾値が上昇するにつれてそれぞれの数でゃ減少しているが，その減少幅は少ない．閾値60%の関数クローンセット，ユニークな関数の数はほぼ閾値100%となっている．67%，92%，94%． 閾値100%の関数クローンセット群を選択した場合，617,713個の関数のうち253,455個を66,455個に分類した． THRESHOLD・・・関数クローンペアとなるクローン行の割合の閾値

21 メトリクス値と関数クローンセット数との関係 ～mailドメイン～
ソフトウェア間の関数クローンのほうが多い 同ドメイン内の関数クローンは分散傾向 ほぼ全て lightning，thunderbird，enigmail-thunderbird，enigmail-seamonkey 間 postfix，postfix23，postfix24，postfix-current間 mutt，mutt-lite，mutt-devel，mutt-devel-lite 間 bogofilter，bogofilter-qdbm，bogofilter-sqlite，bogofilter-tc間 の関数クローンセット ソースファイル単位のクローン 要素がある1つのソフトウェアにのみ存在する 関数クローンセット数 要素が複数のソフトウェアに存在する 0.0 ~0.1 0.1 ~0.2 0.2 ~0.3 0.3 ~0.4 0.4 ~0.5 0.5 ~0.6 0.6 ~0.7 0.7 ~0.8 0.8 ~0.9 0.9 ~1.0 1 3,405 2 40 108 36 307 252 9,942 3 38 57 66 411 34 148 7,643 4 164 510 537 263 2,661 19 920 35,891 5 7 91 58 90 88 11 199 812 6 16 22 17 15 53 13 8 30 9 10~ 10 79 DOS FOF トータル 63,050 トータル 3,405 別バージョンや拡張機能 多くのソフトウェアで分散して利用されている （高FOF，高DOSの）関数は どのような機能があるのか？ [前回の指摘] 「FOFとDOSでこういうものを抽出したいので，この分布を示す」みたいなのがほしい．いきなりこの表を出しても意図がわからない． 表はちゃんと作る． FOF : 要素がいくつのソフトウェアに存在しているか DOS : 要素がどの程度異なるソフトウェアに分散しているか

22 mailドメインにおいて 再利用性の高い関数を得ることができた！
FOF，DOSを利用することにより 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 　　 文字列をコピーする関数 など・・・ [前回の指摘] 何を意図してFOFとDOSを基準にしてフィルタリングをしたのか． FOF，DOSの具体値． その他にもこんなものがありました． この汎用的であることを言う． これを紹介した理由． 文字列において指定した文字へのポインタを返す関数

23 ケース２ ～複数のドメインを対象とした場合～
対象：8ドメイン( accessibility, archivers, benchmarks, converters, finance, ftp, irc, misc ) ソフトウェア数：1,306 総行数：18,339,890 目的： 　ドメイン間の関数クローンの調査 クローン検出方法 完全一致検出 名前変更検出

24 実験結果 ～複数ドメイン～ 421,008個の関数のうち88,918個を 36,378種類に分類
閾値が上がるにつれて大きく減少 名前変更のほうが多くの関数クローンペア・セット 差が大きい THRESHOLD (%) 60 70 80 90 100 ペア数 （完全一致） 88,913 80,417 72,405 65,927 56,832 セット数 （完全一致） 36,980 34,798 32,717 30,468 28,016 関数の数 （完全一致） 83,070 78,311 73,912 69,443 64,122 ペア数 （名前変更） 407,860 335,802 259,790 221,538 201,565 セット数 （名前変更） 49,290 45,966 41,818 38,941 36,378 関数の数 113,387 107,011 99,980 94,238 88,918 使用されているドメインに偏りがある関数 多くのドメインに分散して使用されている関数 →GVOF，DOD 24%減 23%減 26%減 22%減 変更の加えられた関数クローンが多い！ THRESHOLD・・・関数クローンペアとなるクローン行の割合の閾値

25 メトリクス値と関数クローンセット数との関係 ～複数ドメイン～
ドメイン間の関数クローンのほうが少ない メトリクス値と関数クローンセット数との関係 ～複数ドメイン～ 2つのドメイン間の関数クローンが多い ソースファイル単位のクローン 要素がある1つのドメインにのみ存在する 関数クローンセット数 要素が複数のドメインに存在する 0.0 ~0.1 0.1 ~0.2 0.2 ~0.3 0.3 ~0.4 0.4 ~0.5 0.5 ~0.6 0.6 ~0.7 0.7 ~0.8 0.8 ~0.9 0.9 ~1.0 1 31,923 2 268 220 67 91 1,198 1,263 3 55 129 143 86 103 206 4 13 36 50 33 25 26 5 40 20 24 11 6 190 7 DOD GVOF ドメイン間の関数クローンは 特定のソフトウェア，ドメイン間での数の偏りはなかった 多くのドメインで分散して利用されている （高GVOF，高DODの）関数は どのような機能があるのか？ トータル 4,455 トータル 31,923 GVOF : 要素がいくつのドメインに存在しているか DOD : 要素がどの程度異なるドメインに分散しているか

26 ドメインによらず 汎用的な機能の関数を得ることができた！
関数クローンの例 ～複数ドメイン～ GVOF，DODを利用することにより ドメインによらず 汎用的な機能の関数を得ることができた！ GVOF :7 DOD : 0.38 GVOF 7，DOD 0.15： 　　文字列に対して指定した文字へのポインタを返す関数 　　引数1つの関数を複数回呼び出す関数 GVOF 6，DOD 0.45： 　　引数2つの関数を複数回呼び出す関数 　　コマンドライン引数の要素を調べる関数 　　カレントディレクトリのパス名を返す関数 など・・・ メモリ領域を解放する関数

27 まとめと今後の課題 大量のソースコードから関数クローンセットを生成する手法を提案 今後の課題 クローン検出ツールによる比較実験
他のプログラミング言語を対象とした実験 関数の呼び出し回数に応じた評価方法