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

ソースコードの類似性分析に基づく
ソフトウェア保守支援に関する研究
井上研究室吉田則裕
Department of Computer Science,
Graduate School of Information Science & Technology,
Osaka University
1
ソフトウェア保守

ソフトウェアの保守作業とは
 納入後，ソフトウェアに対して加えられる，欠陥の修
正，性能などの改善，変更された環境に適合させる
ための修正
長期にわたって運用される大規模ソフトウェア
が増加
保守作業の効率化が重要な課題として取り上
げられるようになった

Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
2
ソースコードの類似性


ソースファイル内やソースファイル間には，類似性の
高い部分が多く存在する
類似コード片とは
プログラム要素とは，トークンや構文など
ソースコードを構成する要素のこと
 ソースコード上のコード片のうち，等価なプログラム要素を
閾値以上の個数含むコード片を持つコード片
ソースファイルA
ソースファイルB
修正
コード片F
類似コード片SF1
修正の検討が
必要
類似コード片SF2
類似コード片は，ソフトウェアの保守作業にかかるコストを増大させる
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
3
類似コード片に対する保守作業

同時修正
ソースファイルB
ソースファイルA
修正
コード片CF0
類似コード片
コード片CF1
同時に修正
コード片CF2

集約（リファクタリング）
コード片CF0
コード片CF1
メソッドM（関数）
新規メソッド（関数）
呼び出し文
コード片CF2
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
コードクローン検出ツール

類似コード片の中でも，コードクローンを自動的に検出

類似コード片


コークローン


ソースコード上のコード片のうち，等価なプログラム要素を閾値以上の個
数含むコード片を持つコード片
ソースコード上のコード片のうち，等価なプログラム要素のみを含むコード
片を持つコード片
CCFinder

等価なトークン列のみを含むコード片を持つコード片を検出
コード片CF0のトークン列
A
B
C
D
E
コード片CF1のトークン列
J
×類似コード片
×コードクローン
コード片CF2のトークン
列A
D
B
F
E
○類似コード片
×コードクローン
F
G
H
I
コード片CF3のトークン
○類似コード片
○コードクローン
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
A
B
C
D
E
5
コードクローン検出ツールの問題点 (1/2)

コードクローンのリファクタリングを行う際の問題点
 クローンセット間の依存関係を検出しない

あるクローンセットをリファクタリングするためには，他のクローンセット
をリファクタリングする必要があるという関係を検出できない
ソースファイルA
クローンセット1
クローンセット2
集約作業先の
ソースファイルC
ソースファイルB
集約
コード片CFA1
コード片CFB1
呼出
呼出
コード片CFA2
コード片CFB2
コード片CF1
集約
呼出
コード片CF2
リファクタリングを行うためには，クローンセット間の依存関係を理解する必要がある
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
6
コードクローン検出ツールの問題点 (2/2)

同時修正を行う際の問題点
 等価なプログラム要素からなるコード片のみを検出
 同時修正を行う作業者は，できるだけ修正漏れを防ぎたい
コードクローン検出ツールが検出しない類似コード片を提示
する手法が必要
コード片F0のトークン列
A
B
C
D
コード片F1のトークン列
E
F
G
H
I
J
コード片F2のトークン列
A
B
F
D
E
類似コード片
E
類似コード片かつ
コードクローン 7
コード片F3のトークン列
A
B
C
D
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
7
本研究の目的と概要

目的
 類似コード片に対する保守作業を支援
 同時修正をおよび集約（リファクタリング）作業の支援

概要
 １章：はじめに
 ２章：コードクローン間の依存関係に基づくリファクタリング
支援


クローンセット間の依存関係を検出することで，集約支援を行う手法
文献[1-1, 1-2]
 ３章：類義語の特定に基づく類似コード片検索法
 識別子の類似性に基づいて，類似コード片の検索を行う手法
 文献[1-3, 2-3]
 ４章：むすびに
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
8
2章：コードクローン間の依存関係に
基づくリファクタリング支援
Department of Computer Science,
Graduate School of Information Science & Technology,
Osaka University
9
クローンセット間の依存関係 (1/2)

異なるクローンセットに含まれるコード片間に呼び出し関係が
存在すると，リファクタリングが困難な場合がある
親クラス
メソッド1
親クラス
集約
クラスA
クラスB
メソッドa1
メソッドb1
呼出
メソッドa2
呼出
メソッドb2
クラスA
クラスB
呼出できない
メソッドa2
メソッドb2
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
10
クローンセット間の依存関係(2/2)



呼出先の二つのメソッドもコードクローンであることを利用する
ことにより，まとめてリファクタリングを行うことが可能
リファクタリング技術に詳しく，かつコード片間の依存関係を把
握した技術者でなければ，適切にリファクタリングを行うことは
困難
リファクタリング支援が必要
親クラス
親クラス
メソッド1
クラスA
呼出
クラスB
メソッド2
メソッドb1
メソッドa1
呼出
メソッドa2
呼出
メソッドb2
クラスA
クラスB
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
11
研究の目的

クローンセット間の依存関係に基づくリファクタリング支援手
法を提案
依存関係を持つクローンセットの集合をチェーンドクローンセットと
して定義し，検出
 チェーンドクローンセットの特徴に応じて，適用可能なリファクタリ
ングパターンを提示する手法を提案

チェーンドクローンセット
コード片a1
コード片b1
コード片a2
コード片b2
リファクタリング
コード片1
コード片2
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
12
チェーンドクローンセットの定義
複数のクローンセットが与えられたとき，コード片を頂点，呼び出し関係
を有向辺とする有向グラフを作成し，連結成分（チェーン）毎に分割する
 このとき，2つの条件が成り立つなら，それらのチェーンは，チェーンドク
ローンセットであるという



各チェーンに含まれる頂点が，同一クローンセットに属するという関係で対
応をとれること
チェーン上で，有向辺 Ea =（a1, a2)があれば，その他のチェーン上で，a1
に対応するb1，a2に対応するb2からなる有向辺 Eb = （b1, b2）が存在す
る
チェーンドクローンセット
呼出
コード片b1
呼出
コード片a2
コード片b2
コード片a1
クローンセット1
クローンセット2
呼出
クローンセット3
呼出
コード片a3
コード片b3
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
13
チェーンドクローンセットに対する
リファクタリング支援

チェーンドクローンセットを，適用可能なリファクタリン
グパターンにより，4種類に分類する
分類1：Extract Method パターンが適用可能
分類2：Pull Up Method パターンが適用可能
分類3：Extract SuperClassパターンが適用可能
分類4：上記３つのリファクタリングパターンが適用不可能

チェーンドクローンセットを特徴に応じて自動的に分
類し，対応するリファクタリングパターンを提示する
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
14
チェーンドクローンセットの分類
分類 1 : Extract Method パターンが適用可能


特徴
 チェーンドクローンセットが一つのクラスに包含されている
集約方法
 同一のクラス内に全てのコードクローンを集約
リファクタリング後
リファクタリング前
クラスA
クラスA
チェーンドクローンセット
コード片a1
コード片b1
メソッド1
コード片a2
コード片b2
メソッド2
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
15
チェーンドクローンセットの分類
分類 2 : Pull Up Method パターンが適用可能


特徴
 各チェーンは，それぞれ一つのクラスに包含されている
 チェーンを含んでいる全てのクラスは，共通の親クラスを持つ
集約方法
 全てのコードクローンを共通の親クラスに引き上げる
リファクタリング後
親クラス
リファクタリング前
親クラス
メソッド1
クラスA
クラスB
チェーンドクローンセット
メソッド2
コード片a1
コード片b1
コード片a2
コード片b2
クラスA
クラスB
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
16
チェーンドクローンセットの自動分類手法


与えられたチェーンドクローンセットに，どのリファクタリングパターンを適用
できるかメトリクスを用いて判定
抽出すべき特徴
クローンセットに含まれるコード片間の関係
 チェーンに含まれるコード片間の関係


コード片間の関係を3種類に分けて考える

R1：各コード片は同一クラスに所属
 R2：各コード片が所属するクラスは同一ではないが，共通の親クラスを持つ
 R3：各コード片が所属するクラスは共通の親クラスを持たない
親クラス
クラスA
クラスB
コード片a1
コード片b1
コード片a2
コード片b2
Pull Up Methodパターンを
適用するためには，クロー
ンセットに含まれるコード片
間の関係がR2である必要
がある
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
17
メトリクスDCH
(the Dispersion of Class Hierarchy)
与えられたコード片群と，その共通の親クラスまでの距離の最
大値を表す[22]
R1：同一クラス
R2: 共通の親クラスを
持つ
R3: 共通の親クラスを
持たない
クラスP
クラスA
クラスB
クラスC
クラスD
クラスE
コード片a1 コード片a2
コード片b
コード片c
コード片d
コード片e
DCH = 0
DCHは1以上の整数
（この例では１）
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.
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
18
自動分類を目的としたメトリクスの定義


DCHS：クローンセットに含まれるコード片間の関係を表す
DCHD：チェーンに含まれるコード片間の関係を表す
各チェーンに含まれるコード片に対し，それぞれDCHを求め，
その最大値をDCHDとする
DCHD = max{DCH(C1), …, DCH(Cm)}
親クラス
クラスA
クラスB
C1
C2
コード片a1
コード片b1
S1
クローンセットに含まれるコード片
について，それぞれDCHを求め，
その最大値をDCHSとする
コード片a2
コード片b2
S2
DCHS = max{DCH(S1), …, DCH(Sn)}
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
19
メトリクスによるチェーンドクローンセットの分類
DCHD
0
(R1)
1以上の整数
(R2)
∞
(R3)
DCHS
0
(R1)
Extract Methodが
適用可能
1以上の整数
(R2)
Pull Up Methodが
適用可能
∞
(R3)
Extract
SuperClassが適用
可能
いずれのリファクタリングパターンも
適用不可能
DCHS：クローンセットに含まれるコード片間の関係を表す
DCHD：チェーンに含まれるコード片間の関係を表す
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
20
適用実験
概要
目的
 チェーンドクローンセットの数，規模の調査
 メトリクスを用いてチェーンドクローンセットを分類し，その分
類に対応したリファクタリングパターンを適用できるか確認
 対象
 ANTLR 2.7.4 （4.7万行，285クラス）



C++, Java, C#用コンパイラ・コンパイラ
チェーンドクローンセットに基づくリファクタリング支援ツールを
作成
 コードクローン検出ツールCCFinderを用いてクローンセット
を検出
 それらクローンセットに含まれるコード片間の依存関係を解
析し，チェーンドクローンセットを検出
 定義したメトリクスに基づき，リファクタリングパターンを提示
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
21
適用実験
チェーンドクローンセットの検出
分類
検出数
コード片数
最大




最小
Extract Method
6
11
4
Pull Up Method
8
120
6
Extract SuperClass
1
4
4
いずれも適用不可能
0
合計
15
全てリファクタリングパターンを適用可能なチェーンドクローンセットであった
提示されたリファクタリングパターンを用いて，全てのチェーンドクローンセッ
トをリファクタリングできた
含まれるコード片数が多いチェーンドクローンセットを検出できた
三つの言語（C++, C#, Java）に対応した部分の多くがコードクローンとなっ
ていたため
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
22
3章：類義語の特定に基づく
類似コード片検索法
Department of Computer Science,
Graduate School of Information Science & Technology,
Osaka University
23
類似コード片検索


ソースコード中から，クエリとして与えられたコード片の類似コー
ド片を特定する作業
類似コード片の同時修正を支援するためには，類似コード片検
索を自動的に行うツールが必要
入力コード片
（クエリ）
入力プログラム要素列
ei[0]
ei[1]
ei[ni]
類似要素列
欠陥を含むコード片を与える
対象ソース
ファイル
照合
各ソースファイルの
プログラム要素列
et1[0]
et1[1]
et1[nt1]
et2[0]
et2[1]
et2[nt2]
et2[0]
et2[1]
et2[nt2]
es1[0]
es1[ns1]
es2[0]
es2[ns2]
類似コード片
欠陥の有無を検査
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
24
提案手法の概要

識別子の類似性に基づいて，類似コード片を検索する
手法を提案
 識別子を語単位に分割し正規化
 “add_host”  “add”と”host”，”type1”  “type”
 自然言語解析を用いて，語の類義語を特定
 入力コード片に含まれる全ての語と一致する，もしくは類義語
である語を含む関数を検出する
入力コード片
語の抽出
検索
語の抽出
類義語の特定
類似コード片
（関数単位）
対象ソースファイル
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
25
類義語の特定手順 (1/4)

関数×語行列の作成
識別子
語
wc wa wd
we
wb
wc
wb
wc
wc
wd
関数 f0
wc
wd
関数 f1
wa wb
we
wc
we
関数 f2
wd
we
f0
f1
f2
関数×語行列
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
26
類義語の特定手順 (2/4)

関数×語行列を共起行列に変換
 2つの語が共起しているとは，それら語が同一関数内で出現
f0
f1
f2
していること言う
 2つの語がn回共起しているとは，それら語がn個の関数内で
共起していることを言う
wa wb wc wd we
wa wb wc wd we
wa
wb
wc
wd
we
関数×語行列
共起行列
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
27
類義語の特定手順 (3/4)

共起行列から語間の距離を算出
 自然言語処理[13]で用いられている
wa
wb
wc
wd
we
Jensen-Shannon
divergence[38] を用いる
 waとwbの距離は，分布 [1, 1, 0]と分布 [1, 0, 1]のdivergence
wa wb wc wd we
wa
wb wc wd we
wa
wb
wc
wd
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.
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
28
類義語の特定手順 (4/4)

語のクラスタリング

全ての語が独立したクラスタという状態から始めて，最も距離の小さいク
ラスタから順次結合していく


クラスタ間の距離は，語間の距離の平均（群平均法）
任意のクラスタ間の距離が，ユーザが指定した閾値以上になったら終了
Clustera
Wa
Clusterb
Wb
Merge
(distance: 0)
Clusterac
Clusterac
Wa W c
Wa W c
Clusterbd
Clusterb
Wb Wd
Wb
Clusterｃ
Merge
(distance: 0.17)
Wｃ
Clusterｄ
Wｄ
Clusterd
Wd
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
29
入力コード片との照合
1.
2.
入力コード片に含まれる各語について，対象関数中
に同一の語もしくは類義語が存在するか判定する
全ての語について，１．が成立すれば，対象関数を
類似コード片として提示
入力コード片に含まれる語の列
対象関数に含まれる語の列
host
node
alloc
add
alloc
add
host
node
語hostと語nodeが類義語である場合
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
30
適用実験の概要

欠陥検出に対する有効性を確認した

かんなの結果
のみを発表
日本語入力システムかんな 3.6
7.6KLOC, 203関数（＊.c ファイルのみ）
 18個の関数がバッファオーバーフローエラーを含んでいた


ソフトウェア部品検索システム SPARS-J
36KLOC，859関数（＊.c ファイルのみ）
 50個の関数が型キャスト忘れを含んでいた


CCFinderの結果
のみを発表
CCFinder，grepとの性能比較を行った
欠陥を含むコードを与える
欠陥を含む関数の割合を確認する
入力コード片
類似コード片（関数）
語の抽出
検索
語の抽出
類義語の特定
対象ソースファイル
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
31
入力コード片（かんな） (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]));
}
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
32
入力コード片（かんな） (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);
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
33
評価基準
各入力コード片について，適合率（Precision）,
再現率（Recall）, F値を計測した
 Ｄを欠陥を含む関数の集合，Rを検索された関
数の集合とすると，以下のように表される

検索結果に含まれた関数のうち，
欠陥を含む関数の割合
欠陥を含む関数のうち，
検索結果に含まれた関数の割合
適合率と再現率の
調和平均
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
34
実験結果(1/2)
語をクラスタリングする際の閾値thrを変化させたとき
の，各コード片の適合率，再現率，F値

コード片
提案手法（thr = 0.1）
適合率
再現率
CFA
0.50
0.72
CFB
0.19
CFC
1.00

提案手法（thr = 0.2）
適合率
再現率
0.59
0.18
1.00
0.33
0.25
0.18
0.06
0.11
0.33
F値
CCFinder
適合率
再現率
0.31
1.00
0.06
0.11
1.00
0.31
1.00
0.06
0.11
0.06
0.10
1.00
0.06
0.11
F値
F値
クラスタリングの閾値は，thrが与えられたときに，以
下の手順で求めることができる
1.
2.
対象ソースコードに含まれる任意の語の距離を求め，その
最大値をdmaxとする
dmaxとthrの積を閾値とする
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
35
実験結果(2/2)

語をクラスタリングする際の閾値を変化させたときの，
各コード片の適合率，再現率，F値
コード片
提案手法（thr = 0.1）
適合率
再現率
CFA
0.50
0.72
CFB
0.19
CFC
1.00
提案手法（thr = 0.2）
適合率
再現率
0.59
0.18
1.00
0.33
0.25
0.18
0.06
0.11
0.33
F値
適合率は良いが，
再現率は悪い
CCFinder
適合率
再現率
0.31
1.00
0.06
0.11
1.00
0.31
1.00
0.06
0.11
0.06
0.10
1.00
0.06
0.11
F値
適合率は悪いが，
再現率は良い
F値
コード片を含む関数
のみが提示された
各コード片に含まれる語が属するクラスタを分析した
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
36
コード片に含まれる語が属するクラスタ

thr = 0.1に設定したときのクラスタリング結果
コード片CFA
バッファを表すポインタの
クラスタ1
加算を表す文に頻出
buf, HEADER,SIZE,
SIZEOFINT, SIZEOFSHORT（他２）
コード片CFB
バッファからデータを
クラスタ2 読み出す文に頻出
context, dicname, kouho,
number, type, Request（他３７）
クラスタ3
プログラム全体に頻出
retval,free,len,malloc,i
バッファからデータを
クラスタ4 読み出す文に頻出
datalen, ushortstrlen,
yomi, yomilen（他８）
クラスタ３がコード片CFB
の結果を悪化
プログラム全体で頻出する
語を除去する必要
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
37
今後の研究方針

コードクローン間の依存関係に基づくリファクタリング
支援について
 リファクタリング間に存在する依存関係の検出

類義語の特定に基づく類似コード片検索法について
 関数単位ではなく，コード片単位で提示を行う手法への改善
 類似度による類似コード片の順位付け
 頻出する語をクラスタリングの対象から除去
 類似した機能が実装されているコード片の検索など他の用
途への適用
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University
38

Download Report