ソースコードの類似性分析に基づく ソフトウェア保守支援に関する研究

Presentation on theme: "ソースコードの類似性分析に基づく ソフトウェア保守支援に関する研究"— Presentation transcript:

1 ソースコードの類似性分析に基づく ソフトウェア保守支援に関する研究
井上研究室 吉田 則裕

2 ソフトウェア保守 ソフトウェアの保守作業とは 長期にわたって運用される大規模ソフトウェアが増加
納入後，ソフトウェアに対して加えられる，欠陥の修正，性能などの改善，変更された環境に適合させるための修正 長期にわたって運用される大規模ソフトウェアが増加 保守作業の効率化が重要な課題として取り上げられるようになった

3 プログラム要素とは，トークンや構文などソースコードを構成する要素のこと
ソースコードの類似性 ソースファイル内やソースファイル間には，類似性の高い部分が多く存在する 類似コード片とは ソースコード上のコード片のうち，等価なプログラム要素を閾値以上の個数含むコード片を持つコード片 プログラム要素とは，トークンや構文などソースコードを構成する要素のこと ソースファイルA ソースファイルB 修正 類似コード片SF1 類似コード片SF2 修正の検討が必要 コード片F 類似コード片は，ソフトウェアの保守作業にかかるコストを増大させる

4 類似コード片に対する保守作業 同時修正 集約（リファクタリング） 類似コード片 新規メソッド（関数） コード片CF0 呼び出し文
ソースファイルA ソースファイルB 修正 コード片CF1 コード片CF2 類似コード片 コード片CF0 同時に修正 コード片CF0 新規メソッド（関数） メソッドM（関数） 呼び出し文 コード片CF1 コード片CF2

5 コードクローン検出ツール 類似コード片の中でも，コードクローンを自動的に検出 CCFinder 類似コード片 コークローン
ソースコード上のコード片のうち，等価なプログラム要素を閾値以上の個数含むコード片を持つコード片 コークローン ソースコード上のコード片のうち，等価なプログラム要素のみを含むコード片を持つコード片 CCFinder 等価なトークン列のみを含むコード片を持つコード片を検出 コード片CF0のトークン列 コード片CF1のトークン列 ×類似コード片 ×コードクローン A B C D E F G H I J コード片CF2のトークン列 ○類似コード片 ×コードクローン A B F D E コード片CF3のトークン ○類似コード片 ○コードクローン A B C D E 5 5

6 リファクタリングを行うためには，クローンセット間の依存関係を理解する必要がある
コードクローン検出ツールの問題点 (1/2) コードクローンのリファクタリングを行う際の問題点 クローンセット間の依存関係を検出しない あるクローンセットをリファクタリングするためには，他のクローンセットをリファクタリングする必要があるという関係を検出できない 集約作業先の ソースファイルC ソースファイルA ソースファイルB 集約 クローンセット1 コード片CFA1 コード片CFB1 コード片CF1 呼出 呼出 呼出 集約 コード片CF2 クローンセット2 コード片CFA2 コード片CFB2 リファクタリングを行うためには，クローンセット間の依存関係を理解する必要がある

7 コードクローン検出ツールの問題点 (2/2) 同時修正を行う際の問題点 等価なプログラム要素からなるコード片のみを検出
同時修正を行う作業者は，できるだけ修正漏れを防ぎたい コードクローン検出ツールが検出しない類似コード片を提示する手法が必要 コード片F0のトークン列 コード片F1のトークン列 A B C D E F G H I J コード片F2のトークン列 類似コード片 A B F D E コード片F3のトークン列 類似コード片かつ コードクローン A B C D E 7

8 本研究の目的と概要 目的 概要 類似コード片に対する保守作業を支援 １章：はじめに
同時修正をおよび集約（リファクタリング）作業の支援 概要 １章：はじめに ２章：コードクローン間の依存関係に基づくリファクタリング支援 クローンセット間の依存関係を検出することで，集約支援を行う手法 文献[1-1, 1-2] ３章：類義語の特定に基づく類似コード片検索法 識別子の類似性に基づいて，類似コード片の検索を行う手法 文献[1-3, 2-3] ４章：むすびに

9 2章：コードクローン間の依存関係に基づくリファクタリング支援

10 クローンセット間の依存関係 (1/2) 異なるクローンセットに含まれるコード片間に呼び出し関係が存在すると，リファクタリングが困難な場合がある 親クラス メソッド1 親クラス 集約 クラスA クラスB クラスA クラスB メソッドa1 メソッドb1 呼出できない それでは、本研究の動機について説明します。 ソフトウェア中には、複数のクローンセットをまとめて扱うことにより、効率的なリファクタリングを実現できる場合があります。 この図では、クラスAとクラスBに共通の親クラスが存在し、クラスA中のメソッドa1、クラスB中のメソッドb1がコードクローンとなっており、さらに、メソッドa1から呼び出されるメソッドa2、メソッドb1から呼び出されるメソッドb2もコードクローンとなっています。 このとき、メソッドa1とメソッドb1を親クラスに作成したメソッドに集約しますと、親クラスのメソッドから、メソッドa2もしくは、メソッドb2を呼び出すことができません。 呼出 呼出 メソッドa2 メソッドb2 メソッドa2 メソッドb2

11 クローンセット間の依存関係(2/2) 呼出先の二つのメソッドもコードクローンであることを利用することにより，まとめてリファクタリングを行うことが可能 リファクタリング技術に詳しく，かつコード片間の依存関係を把握した技術者でなければ，適切にリファクタリングを行うことは困難 リファクタリング支援が必要 親クラス 親クラス メソッド1 呼出 クラスA クラスB しかし、呼び出し先の二つのメソッドもコードクローンですので、それらメソッドも親クラスに集約すると、先ほどの親クラスからサブクラスのメソッドを呼び出せないという問題を解決することができます。 メソッド2 メソッドa1 メソッドb1 呼出 呼出 クラスA クラスB メソッドa2 メソッドb2

12 研究の目的 クローンセット間の依存関係に基づくリファクタリング支援手法を提案
依存関係を持つクローンセットの集合をチェーンドクローンセット として定義し，検出 チェーンドクローンセットの特徴に応じて，適用可能なリファクタリングパターンを提示する手法を提案 チェーンドクローンセット コード片a1 コード片b1 コード片1 リファクタリング コード片a2 コード片b2 コード片2

13 チェーンドクローンセットの定義 複数のクローンセットが与えられたとき，コード片を頂点，呼び出し関係を有向辺とする有向グラフを作成し，連結成分（チェーン）毎に分割する このとき，2つの条件が成り立つなら，それらのチェーンは，チェーンドクローンセットであるという 各チェーンに含まれる頂点が，同一クローンセットに属するという関係で対応をとれること チェーン上で，有向辺 Ea =（a1, a2)があれば，その他のチェーン上で，a1に対応するb1，a2に対応するb2からなる有向辺 Eb = （b1, b2）が存在する チェーンドクローンセット クローンセット1 コード片a1 コード片b1 呼出 呼出 クローンセット2 コード片a2 コード片b2 呼出 呼出 クローンセット3 コード片a3 コード片b3

14 チェーンドクローンセットに対する リファクタリング支援
チェーンドクローンセットを，適用可能なリファクタリングパターンにより，4種類に分類する 分類1：Extract Method パターンが適用可能 分類2：Pull Up Method パターンが適用可能 分類3：Extract SuperClassパターンが適用可能 分類4：上記３つのリファクタリングパターンが適用不可能 チェーンドクローンセットを特徴に応じて自動的に分類し，対応するリファクタリングパターンを提示する それでは，チェーンドクローンセットに対するリファクタリングについて説明したいと思います． チェーンドクローンセットを集約するリファクタリングパターンとしてPull Up Method, Extract Method, Extract Super Class利用します． チェーンドクローンセットの特徴に応じて，5種類に分類し，適切なリファクタリングパターンを適用します． この5種類の分類を，分類 1から分類 5と名づけているのですが，時間の都合上，C1とC3の説明のみにさせていただきます．

15 チェーンドクローンセットの分類 分類 1 : Extract Method パターンが適用可能
特徴 チェーンドクローンセットが一つのクラスに包含されている 集約方法 同一のクラス内に全てのコードクローンを集約 リファクタリング前 リファクタリング後 クラスA クラスA チェーンドクローンセット コード片a1 コード片b1 メソッド1 まず，分類 1ですが，これはチェーンドクローンセットが同一のクラスに含まれている場合です． この図のように，チェーンドクローンセット内に含まれる全てのメソッドが同一のクラスに存在する場合，同一のクラス内に，互いにクローンとなっているメソッドを集約します．この図では，互いにクローンとなっているメソッドa11とa12を集約しメソッド a1とし，同じくクローンとなっているメソッドa21とメソッドa22をメソッドa2に集約します． これは，Extract Method パターンの適用ともいえます． コード片a2 コード片b2 メソッド2

16 チェーンドクローンセットの分類 分類 2 : Pull Up Method パターンが適用可能
特徴 各チェーンは，それぞれ一つのクラスに包含されている チェーンを含んでいる全てのクラスは，共通の親クラスを持つ 集約方法 全てのコードクローンを共通の親クラスに引き上げる リファクタリング前 リファクタリング後 親クラス 親クラス メソッド1 クラスA クラスB チェーンドクローンセット メソッド2 コード片a1 コード片b1 コード片a2 コード片b2 クラスA クラスB

17 チェーンドクローンセットの自動分類手法 与えられたチェーンドクローンセットに，どのリファクタリングパターンを適用できるかメトリクスを用いて判定 抽出すべき特徴 クローンセットに含まれるコード片間の関係 チェーンに含まれるコード片間の関係 コード片間の関係を3種類に分けて考える R1：各コード片は同一クラスに所属 R2：各コード片が所属するクラスは同一ではないが，共通の親クラスを持つ R3：各コード片が所属するクラスは共通の親クラスを持たない 親クラス Pull Up Methodパターンを適用するためには，クローンセットに含まれるコード片間の関係がR2である必要がある クラスA クラスB コード片a1 コード片b1 コード片a2 コード片b2

18 メトリクスDCH (the Dispersion of Class Hierarchy)
与えられたコード片群と，その共通の親クラスまでの距離の最大値を表す[22] R1：同一クラス R2: 共通の親クラスを 　持つ R3: 共通の親クラスを持たない クラスP クラスA クラスB クラスC クラスD クラスE コード片a1 コード片a2 コード片b コード片c コード片d コード片e DCHは1以上の整数 （この例では１） 共通の親クラスに注目して、説明 最大値の距離を赤で示す 例を用いて説明します． まず，左側の例から説明します． これは，クラスA，Bに１つずつメソッドが所属しており，またクラスA，Bには共通の親クラスが存在しているという例です． この場合，DCHは１となります． 次に，右側の例を説明します． これは，クラスA，B，Ｃに１つずつメソッドが所属しており， またクラスA，Bには共通の親クラスS2，クラスS2，クラスCには共通の親クラスS3が存在しているという例です． この場合，DCHは２となります． DCH = 0 DCH = ∞ [22] Y. Higo, et al. A metric-based approach to identifying refactoring opportunities for merging code clones in a java software system. Journal of Software Maintenance and Evolution: Research and Pracctice, 20(6), 2008.

19 DCHD = max{DCH(C1), …, DCH(Cm)}
自動分類を目的としたメトリクスの定義 DCHS：クローンセットに含まれるコード片間の関係を表す DCHD：チェーンに含まれるコード片間の関係を表す 各チェーンに含まれるコード片に対し，それぞれDCHを求め，その最大値をDCHDとする DCHD = max{DCH(C1), …, DCH(Cm)} 親クラス クラスA クラスB C1 C2 テーブルを作る メトリクスの分類 チェーンドクローンセットがC1～C5のいずれに該当するか決定をするために必要な情報は２つあります． 1つ目は，互いにクローンとなっているメソッドのDCHです． これにより，互いにクローンとなるメソッドの間に共通の親クラスが （２）含まれるフラグメントチェーンのDCH コード片a1 コード片b1 S1 クローンセットに含まれるコード片について，それぞれDCHを求め，その最大値をDCHSとする コード片a2 コード片b2 S2 DCHS = max{DCH(S1), …, DCH(Sn)}

20 メトリクスによるチェーンドクローンセットの分類
DCHD DCHS (R1) 1以上の整数 (R2) ∞ (R3) Extract Methodが 適用可能 いずれのリファクタリングパターンも 適用不可能 Pull Up Methodが Extract SuperClassが適用可能 Using the two metrics, we classify チェーンドクローンセットs into 9 categories DCHS：クローンセットに含まれるコード片間の関係を表す DCHD：チェーンに含まれるコード片間の関係を表す

21 適用実験 概要 目的 チェーンドクローンセットの数，規模の調査
適用実験 概要 目的 チェーンドクローンセットの数，規模の調査 メトリクスを用いてチェーンドクローンセットを分類し，その分類に対応したリファクタリングパターンを適用できるか確認 対象 ANTLR （4.7万行，285クラス） C++, Java, C#用コンパイラ・コンパイラ チェーンドクローンセットに基づくリファクタリング支援ツールを作成 コードクローン検出ツールCCFinderを用いてクローンセットを検出 それらクローンセットに含まれるコード片間の依存関係を解析し，チェーンドクローンセットを検出 定義したメトリクスに基づき，リファクタリングパターンを提示

22 適用実験 チェーンドクローンセットの検出 分類 検出数 コード片数 最大 最小 Extract Method 6 11 4
Pull Up Method 8 120 Extract SuperClass 1 いずれも適用不可能 合計 15 全てリファクタリングパターンを適用可能なチェーンドクローンセットであった 提示されたリファクタリングパターンを用いて，全てのチェーンドクローンセットをリファクタリングできた 含まれるコード片数が多いチェーンドクローンセットを検出できた 三つの言語（C++, C#, Java）に対応した部分の多くがコードクローンとなっていたため 合計を先にいう 特徴を言う C5消す

23 3章：類義語の特定に基づく類似コード片検索法

24 類似コード片検索 ソースコード中から，クエリとして与えられたコード片の類似コード片を特定する作業
類似コード片の同時修正を支援するためには，類似コード片検索を自動的に行うツールが必要 入力コード片 （クエリ） 入力プログラム要素列 ei[0] ei[ni] ei[1] 類似コード片 類似要素列 欠陥を含むコード片を与える es1[0] es1[ns1] es2[0] es2[ns2] 照合 対象ソースファイル 各ソースファイルのプログラム要素列 欠陥の有無を検査 et1[0] et1[nt1] et1[1] et2[0] et2[nt2] et2[1]

25 提案手法の概要 識別子の類似性に基づいて，類似コード片を検索する手法を提案 識別子を語単位に分割し正規化
“add_host”  “add”と”host”，”type1”  “type” 自然言語解析を用いて，語の類義語を特定 入力コード片に含まれる全ての語と一致する，もしくは類義語である語を含む関数を検出する 入力コード片 類似コード片（関数単位） 語の抽出 検索 対象ソースファイル 語の抽出 類義語の特定

26 類義語の特定手順 (1/4) 関数×語行列の作成 wa wb wc wd we f0 f1 f2 wc wa wd wc we we wb
識別子 wc wa wd wc we we wb wc wc wb wc we wd wd 関数 f0 関数 f1 関数 f2 wa wb wc wd we f0 f1 f2 関数×語行列

27 類義語の特定手順 (2/4) 関数×語行列を共起行列に変換 2つの語が共起しているとは，それら語が同一関数内で出現していること言う
2つの語がn回共起しているとは，それら語がn個の関数内で共起していることを言う wa wb wc wd we wa wb wc wd we wa f0 wb wc f1 wd f2 we 関数×語行列 共起行列

28 類義語の特定手順 (3/4) 共起行列から語間の距離を算出
自然言語処理[13]で用いられている Jensen-Shannon divergence[38] を用いる waとwbの距離は，分布 [1, 1, 0]と分布 [1, 0, 1]のdivergence wa wb wc wd we wa wb wc wd we wa wa wb wb wc wc wd wd we we 語間の距離を表す行列 共起行列 [13] I. Dagan, et al.,Similarity-based models of word cooccurrence probabilities, Machine Learning, 34(1-3),1999. [38] J. Lin. Divergence measures based on the shannon entropy. IEEE Trans. Inf. Theory, 37(1),1991.

29 類義語の特定手順 (4/4) 語のクラスタリング
全ての語が独立したクラスタという状態から始めて，最も距離の小さいクラスタから順次結合していく クラスタ間の距離は，語間の距離の平均 （群平均法） 任意のクラスタ間の距離が，ユーザが指定した閾値以上になったら終了 Clustera Clusterac Clusterac Wa Wa Wc Wa Wc Clusterbd Clusterb Clusterb Merge (distance: 0) Wb Wd Wb Wb Clusterｃ Merge (distance: 0.17) Wｃ Clusterｄ Clusterd Wｄ Wd

30 入力コード片との照合 入力コード片に含まれる各語について，対象関数中に同一の語もしくは類義語が存在するか判定する
全ての語について，１．が成立すれば，対象関数を類似コード片として提示 入力コード片に含まれる語の列 host alloc add host node alloc add node 対象関数に含まれる語の列 語hostと語nodeが類義語である場合

31 適用実験の概要 欠陥検出に対する有効性を確認した CCFinder，grepとの性能比較を行った 日本語入力システム かんな 3.6
日本語入力システム　かんな 3.6 7.6KLOC, 203関数 （＊.c ファイルのみ） 18個の関数がバッファオーバーフローエラーを含んでいた ソフトウェア部品検索システム SPARS-J 36KLOC，859関数　 （＊.c ファイルのみ） 50個の関数が型キャスト忘れを含んでいた CCFinder，grepとの性能比較を行った かんなの結果のみを発表 CCFinderの結果のみを発表 欠陥を含むコードを与える 欠陥を含む関数の割合を確認する 入力コード片 類似コード片（関数） 語の抽出 検索 対象ソースファイル 語の抽出 類義語の特定

32 入力コード片（かんな） (1/2) バッファーオーバフローエラーを含むコード片CFA，CFB，CFCを入力 バッファを指すポインタを加算
バッファからの読み込み処理 コード片CFA buf += HEADER_SIZE; Request.type7.context = S2TOS(buf); buf += SIZEOFSHORT; Request.type7.number = S2TOS(buf); buf += SIZEOFSHORT; Request.type7.yomilen = (short)S2TOS(buf); バッファを指すポインタを加算 バッファからの読み込み処理 コード片CFB buf += SIZEOFINT; Request.type10.kouho = (short *)buf; for (i = 0; i < Request.type10.number; i++) { Request.type10.kouho[i] = S2TOS(buf); buf += SIZEOFSHORT; ir_debug(Dmsg(10, "req->kouho =%d\n", Request.type10.kouho[i])); }

33 入力コード片（かんな） (2/2) バッファを指すポインタを加算 バッファからの読み込み処理 コード片CFC
buf += HEADER_SIZE; Request.type13.context = S2TOS(buf); len = SIZEOFSHORT ; buf += len; Request.type13.dicname = (char *)buf; len = strlen( (char *)buf ) + 1; buf += len; Request.type13.yomi = (Ushort *)buf; len = ((int)Request.type13.datalen - len - SIZEOFSHORT * 4) / SIZEOFSHORT; for( data = Request.type13.yomi, i = 0; i < len; i++, data++) *data = ntohs( *data ); buf += (ushortstrlen((Ushort *)buf) + 1) * SIZEOFSHORT; Request.type13.yomilen = S2TOS(buf); buf += SIZEOFSHORT; Request.type13.kouhosize = S2TOS(buf); buf += SIZEOFSHORT; Request.type13.hinshisize = S2TOS(buf);

34 検索結果に含まれた関数のうち，欠陥を含む関数の割合
評価基準 各入力コード片について，適合率（Precision）, 再現率（Recall）, F値を計測した Ｄを欠陥を含む関数の集合，Rを検索された関数の集合とすると，以下のように表される 検索結果に含まれた関数のうち，欠陥を含む関数の割合 欠陥を含む関数のうち， 検索結果に含まれた関数の割合 適合率と再現率の調和平均

35 実験結果(1/2) 語をクラスタリングする際の閾値thrを変化させたときの，各コード片の適合率，再現率，F値
CCFinder 適合率 再現率 F値 CFA 0.50 0.72 0.59 0.18 1.00 0.31 0.06 0.11 CFB 0.19 0.33 0.25 CFC 0.10 クラスタリングの閾値は，thrが与えられたときに，以下の手順で求めることができる 対象ソースコードに含まれる任意の語の距離を求め，その最大値をdmaxとする dmaxとthrの積を閾値とする　

36 各コード片に含まれる語が属するクラスタを分析した
実験結果(2/2) 語をクラスタリングする際の閾値を変化させたときの，各コード片の適合率，再現率，F値 コード片 提案手法（thr = 0.1） 提案手法（thr = 0.2） CCFinder 適合率 再現率 F値 CFA 0.50 0.72 0.59 0.18 1.00 0.31 0.06 0.11 CFB 0.19 0.33 0.25 CFC 0.10 適合率は良いが，再現率は悪い 適合率は悪いが， 再現率は良い コード片を含む関数のみが提示された 各コード片に含まれる語が属するクラスタを分析した

37 コード片に含まれる語が属するクラスタ thr = 0.1に設定したときのクラスタリング結果 バッファを表すポインタの加算を表す文に頻出
クラスタ1 buf, HEADER,SIZE, SIZEOFINT, SIZEOFSHORT（他２） コード片CFA クラスタ３がコード片CFB の結果を悪化 バッファからデータを読み出す文に頻出 クラスタ2 コード片CFB context, dicname, kouho, number, type, Request（他３７） プログラム全体で頻出する 語を除去する必要 クラスタ3 プログラム全体に頻出 retval,free,len,malloc,i バッファからデータを読み出す文に頻出 クラスタ4 datalen, ushortstrlen, yomi, yomilen（他８）

38 今後の研究方針 コードクローン間の依存関係に基づくリファクタリング支援について 類義語の特定に基づく類似コード片検索法について
リファクタリング間に存在する依存関係の検出 類義語の特定に基づく類似コード片検索法について 関数単位ではなく，コード片単位で提示を行う手法への改善 類似度による類似コード片の順位付け 頻出する語をクラスタリングの対象から除去 類似した機能が実装されているコード片の検索など他の用途への適用