MapReduce 型の並列処理によるコードクローン検出アルゴリズムと試験的な実装

MapReduce 型の並列処理によるコードクローン検出アルゴリズムと試験的な実装神谷年洋†, 崔恩瀞‡ †島根大学学術研究院理工学系 ‡京都工芸繊維大学

2 コードクローンとは • ソースコード中の重複したコード断片をコードクローンと呼ぶ – 典型的には、開発者がソースコードをコピペすることで作られる • コードクローンによりソースコード修正の手間が増大する（と言われている） –
コードクローンにバグが見つかる→全部修正する必要修正したつもりが修正できていない – 大規模なソースコードだとコードクローンを把握することすら難しい

3 コードクローン検出手法 • コードクローンを（特に大規模なソースコードから）検出するための手法 – 精度: コード断片がコピペされたあと修正されるような状況も検出できるか – スケーラビリティ: どのくらいの規模のソースコードに（実用的な処理時間
で）適用できるか • 検出手法が利用するデータ表現・アルゴリズムの違い – トークンの列、AST, PDG, etc – N-gram, 接尾辞配列、同型グラフマイニング、等 • コードクローン検出手法の応用 – リファクタリング、ソースコード修正前のチェック、ソースコードの状態の可視化、等

4 コードクローンのタイプコードクローン検出手法を分類するために提唱されたタイプ 1 ソースコード中の空白文字やインデントの違いを除けば同じ文字列となるコード断片→コピペしただけタイプ 2 タイプ
1 での変更に加えて、識別子(変数や関数の名前)を変更したコード断片→コピペして変数や関数名がぶつからないように修正タイプ 3 タイプ 1 および 2 での変更に加えて、ある程度の挿入や削除が行われたコード断片→コピペ後に修正タイプ 4 何らかの意味論を与えられたときに、その意味論で等価であるとみなされるコード断片

5 提案手法 MapReduce型並列処理で実行できるコードクローン検出手法 • MapReduce型並列処理として実装された頻出アイテム集合検出アルゴリズムを利用 – コード断片を含まれているトークンの種類（集合）で表現 – 含まれているトークンの種類が似ているコード断片をコー
ドクローンとする • トークンの出現順序は無視 • 式や文が並べ替えられていても検出する→タイプ3 次ページで後述

6 インデックス MapReduce型並列処理 • もともとGoogleで大量のwebページからインデックスを作成するために利用された並列処理手法 • 大規模なデータをマップ、シャッフル、リデュースという3種類の操作の組み合わせにより、計算機クラスタ上で分散処理 •
Apache Spark等のフレームワークが利用可能ページに含まれる単語とURLのタプルを作成 (単語,URL) 単語からそれを含むページのリスト求めるインデックスを作成 (w, u) (w, u) (w, u) (w, u) (w, u) (単語, [URL, ...]) 単語で分類ページのデータを分配

7 検出手法コード断片をトークンの集合として表現 → コードクローン検出頻出アイテム ≒ 集合の特定検出手法のステップステップ
(1) 手続きの定義であるコード断片からトークンを要素とするアイテム集合を求めるステップ (2) 共通の要素を持つアイテム集合の部分集合(クローンセット)を特定ステップ (3) 各クローンセットについて、トークンの分布による後処理 int max(int a, int b) { if (a >= b) return a; else return b; } $P:{ $P:} $P:( $P:) $P:; $K:else $K:if $K:return $O:> $O:= $I:a $I:b トークンの集合として表現

8 マップ#1: コード断片f = { t1, t2, … }から、各トークンをキー、それを含むコード断片f を値とするタプル(t1,
f), (t2, f), ...を作成シャッフル#1: トークンによりタプルを分類リデュース#1: トークンtを含むコード断片の集合F = {f1, f2, … }を求め、Fをキー、トークンtを値とするタプル(F, t)を作成シャッフル#2: Fによりタプルを分類リデュース#2: F = {f1, f2, … }をクローンセットとする • 類似部分として、クローンセットのコード断片が共有するトークンも求めるステップ2のアルゴリズム {ab} {ac} (a, {ab}) (b, {ab}) (a, {ac}) (c, {ac}) (a, {ab}) (a, {ac}) ({{ab}{ac}}, a) ({{ab}{ac}}, a) s: {a} f: {ab}, {ac} マップ#1 シャッフル#1 リデュース#1 シャッフル#2 リデュース#2 この例では、タプルの値が共有するトークンになっているが一般には異なる

14 少し大きな例 {ab} {ac} {abc} {ef} (a, {ab}) (b, {ab})
(a, {ac}) (c, {ac}) (a, {abc}) (b, {abc}) (c, {abc}) (e, {ef}) (f, {ef}) (a, {ab}) (b, {ab}) (a, {ac}) (c, {ac}) (a, {abc}) (b, {abc}) (c, {abc}) (e, {ef}) (f, {ef}) ({{ab}{abc}{ac}}, a) ({{ab}{abc}}, b) ({{abc}{ac}}, c) ({{ef}}, e) ({{ef}}, f) ({{ab}{abc}{ac}}, a) ({{ab}{abc}}, b) ({{abc}{ac}}, c) ({{ef}}, e) ({{ef}}, f) s: {a} f: {ab}, {abc}, {ac} s: {ab} f: {ab}, {abc} s: {ac} f: {abc}, {ac} s: {ef} f: {ef} マップ#1 シャッフル#1 リデュース#1 シャッフル#2 リデュース#2 リデュース#2でコード断片が共有するトークンがタプルの値と異なる例リデュース#2で2つ以上のタプルがマージされる例

15 中間データが膨れ上がるケースと対策 • 極端に「長い」コード断片 – トークンの種類の2乗に比例する中間データが生成される – →
「長い」コード断片は除去する • 「頻出」トークン – → ストップワード扱い (t 1 , {t 1 t 2 ... t N }) マップ#1 {t 1 t 2 ... t N } (t 2 , {t 1 t 2 ... t N }) (t N , {t 1 t 2 ... t N }) ... N N2 最初の実験では、中間データが膨れ上がり、マップ#1・リデュース#1で処理が止まった → 対策を講じた

16 実験: セットアップ適用対象 Ubuntu 19.10のパッケージをapt sourceコマンドで取得

17 実験: 検出パラメーター • コード断片の最大サイズ: 60 – 「長い」コード断片対策 • トークンの最大頻度:
1000 – ストップワード • 類似部分の最小サイズ: 5 • ギャップの割合の最大: 0.3 – クローンセットの各コード断片のトークン列中から、共有されるトークンをすべて含み、かつ、それ以外のトークンの個数が最小の部分列を探す – その部分列が含む「それ以外」のトークンの割合がこの値より多ければ、検出結果からそのコード断片を取り除く

18 実験: 結果メモリ利用量のピーク: 128GiB+53GiB

19 検出されたコードクローンの例連続して一致しているのは1行だけだが、提案手法では網掛けの部分をコードクローンとして検出した

20 まとめと課題まとめ • 大規模なソースコードに適用可能な、タイプ3コードクローン検出手法を提案 • 実装したツールを4億行のソースコードに適用課題 •
テストコードや自動生成コード等を除外して実験し直す • 実装上の都合で候補から取り除いた「長い」コード断片を扱えるように工夫する • ベンチマークなどにより他の手法と比較する

より詳しい内容については次を参照ください • 神谷年洋, 崔恩瀞, "MapReduce型の並列処理によるコードクローン検出アルゴリズムと試験的な実装", 電子情報通信学会技術研究報告,
Vol. 116, No. 362, pp. 43-48 (2020- 01-14).

MapReduce 型の並列処理によるコードクローン検出アルゴリズムと試験的な実装

MapReduce 型の並列処理によるコードクローン検出アルゴリズムと試験的な実装

Toshihiro Kamiya

More Decks by Toshihiro Kamiya

Other Decks in Research

Featured

Transcript