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 3
ソースコードの類似性
ソースファイル内やソースファイル間には，類似
性の高い部分が多く存在する
類似コード片とは
ソースコード上のコード片のうち，等価な
プログラム要
素
を閾値以上の個数含むコード片を持つコード片
ソースファイル B
修正の検討が
必要
類似コード片
SF
1類似コード片
SF
2ソースファイル A
コード片 F
修正
類似コード片は，ソフトウェアの保守作業にかかるコストを増大さ
せる
プログラム要素とは，トークンや構
文などソースコードを構成する要素
のこと
類似コード片に対する保守作業
同時修正
集約（リファクタリング）
ソースファイル B
同時に修正
コード片 CF
1コード片 CF
2ソースファイル A
コード片 CF
0修正
新規メソッド（関数）
呼び出し文
コード片
CF
0
コード片
CF
1
コード片
メソッド
M
（関数）
類似コード片
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 55
コードクローン検出ツール
類似コード片の中でも，コードクローンを自動的に検出
類似コード片
ソースコード上のコード片のうち，
等価なプログラム要素を閾値以上の個数
含む
コード片を持つコード片
コークローン
ソースコード上のコード片のうち，
等価なプログラム要素のみを含む
コード
片を持つコード片
CCFinder
等価なトークン列のみを含むコード片を持つコード片を検出
コード片 CF
1のトークン
列
コード片 CF
0のトークン列
コード片 CF
3のトー
クン
コード片 CF
2のトーク
ン列
○ 類似コード片
×
コードクロー
ン
○ 類似コード片
○ コードクローン
A
B
C
D
E
F
G
H
I
J
A
B
F
D
E
A
B
C
D
E
×
類似コード片
×
コードクロー
ン
コードクローン検出ツールの問題点
(1/2)
コードクローンのリファクタリングを行う際の問題点
クローンセット間の依存関係を検出しない
あるクローンセットをリファクタリングするためには，他のクローン
セットをリファクタリングする必要があるという関係を検出できない
クローンセット 1
ソースファイル B
ソースファイル A
コード片
CF
B1コード片
CF
B2コード片
CF
A1コード片
CF
A2呼出
呼出
集約作業先の
ソースファイル
C
コード片
CF
1コード片
CF
2呼出
クローンセット 2
リファクタリングを行うためには，クローンセット間の依存関係を理解する必要
集約
集約
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 7
コードクローン検出ツールの問題点
(2/2)
同時修正を行う際の問題点
等価なプログラム要素からなるコード片のみを検出
同時修正を行う作業者は，できるだけ修正漏れを防ぎたい
コードクローン検出ツールが検出しない類似コード片を提
示する手法が必要
7コード片 F
1のトークン列
コード片 F
0のトークン列
コード片 F
3のトーク
ン列
コード片 F
2のトーク
ン列
類似コード片
類似コード片かつ
コードクローン
A
B
C
D
E
A
B
F
D
E
A
B
C
D
E
F
G
H
I
J
本研究の目的と概要
目的
類似コード片に対する保守作業を支援
同時修正をおよび集約（リファクタリング）作業の支援
概要
１章：はじめに
２章：コードクローン間の依存関係に基づくリファクタリン
グ支援
クローンセット間の依存関係を検出することで，集約支援を行う手法
文献 [1-1, 1-2]
３章：類義語の特定に基づく類似コード片検索法
識別子の類似性に基づいて，類似コード片の検索を行う手法
文献 [1-3, 2-3]
４章：むすびに
Department of Computer Science,
Graduate School of Information Science & Technology,
Osaka University
9
2
章：コードクローン間の依存関
クローンセット間の依存関係 (1/2)
異なるクローンセットに含まれるコード片間に呼び出し関
係が存在すると，リファクタリングが困難な場合がある
メソッド a1
メソッド a2
メソッド
b1
メソッド
b2
クラス A
クラス B
親クラス
呼出
呼出
メソッド a2
メソッド
b2
クラス A
クラス B
親クラス
メソッド 1
呼出できない
集約
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 11
クローンセット間の依存関係 (2/2)
呼出先の二つのメソッドもコードクローンであることを利用するこ
とにより，まとめてリファクタリングを行うことが可能
リファクタリング技術に詳しく，かつコード片間の依存関係を把握
した技術者でなければ，適切にリファクタリングを行うことは困難
リファクタリング支援が必要
メソッド a2
メソッド
b2
クラス A
クラス B
親クラス
クラス A
クラス B
親クラス
メソッド 1
メソッド 2
呼出
メソッド a1
メソッド
b1
呼出
呼出
研究の目的
クローンセット間の依存関係に基づくリファクタリング
支援手法を提案
依存関係を持つクローンセットの集合を
チェーンドクローン
セット
として定義し，検出
チェーンドクローンセットの特徴に応じて，適用可能なリ
ファクタリングパターンを提示する手法を提案
コード片 a1
コード片 a2
コード片
b1
コード片
b2
リファクタリン
グ
コード片 1
コード片 2
チェーンドクローンセット
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 13
チェーンドクローンセットの定義
複数のクローンセットが与えられたとき，コード片を頂点，呼び出し関係を有
向辺とする有向グラフを作成し，連結成分（チェーン）毎に分割する
このとき， 2 つの条件が成り立つなら，それらのチェーンは，チェーンドク
ローンセットであるという
各チェーンに含まれる頂点が，同一クローンセットに属するという関係で対応をと
れること
チェーン上で，有向辺 Ea = （ a1, a2) があれば，その他のチェーン上で， a1 に対
応する b1 ， a2 に対応する b2 からなる有向辺 Eb = （ b1, b2 ）が存在する
クローンセット
1
クローンセット
2
クローンセット
3
呼出
コード片 a1
コード片 b1
コード片 a2
コード片 b2
コード片 a3
コード片 b3
呼出
呼出
呼出
チェーンドクローンセット
チェーンドクローンセットに対する
リファクタリング支援
チェーンドクローンセットを，適用可能なリファ
クタリングパターンにより， 4 種類に分類する
分類 1 ：
Extract Method
パターンが適用可能
分類 2 ：
Pull Up Method
パターンが適用可能
分類 3 ：
Extract SuperClass
パターンが適用可能
分類 4 ：上記３つのリファクタリングパターンが適用不可
能
チェーンドクローンセットを特徴に応じて自動的
に分類し，対応するリファクタリングパターンを
提示する
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 15
クラス A
コード片 a1
コード片 b2
コード片 a2
コード片 b1
チェーンドクローンセット
リファクタリング前
クラス A
メソッド 1
メソッド 2
リファクタリング後
チェーンドクローンセットの分類
分類 1 : Extract Method パターンが適用可能
特徴
チェーンドクローンセットが一つのクラスに包含されている
集約方法
同一のクラス内に全てのコードクローンを集約
クラス A
コード片 a1
コード片 b2
コード片 a2
クラス B
コード片 b1
親クラス
チェーンドクローンセッ
ト
メソッド 1
メソッド 2
親クラス
リファクタリング前
リファクタリング後
チェーンドクローンセットの分類
分類 2 : Pull Up Method パターンが適用可能
特徴
各チェーンは，それぞれ一つのクラスに包含されている
チェーンを含んでいる全てのクラスは，共通の親クラスを持つ
集約方法
全てのコードクローンを共通の親クラスに引き上げる
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 17
与えられたチェーンドクローンセットに，どのリファクタリングパ
ターンを適用できるかメトリクスを用いて判定
抽出すべき特徴
クローンセットに含まれるコード片間の関係
チェーンに含まれるコード片間の関係
コード片間の関係を 3 種類に分けて考える
R1
：各コード片は同一クラスに所属
R2
：各コード片が所属するクラスは同一ではないが，共通の親クラスを
持つ
R3
：各コード片が所属するクラスは共通の親クラスを持たない
チェーンドクローンセットの自動分類手
法
クラス A
コード片 a1
コード片 b2
コード片 a2
クラス B
コード片 b1
親クラス
Pull Up Method
パター
ンを適用するためには，
クローンセットに含まれ
るコード片間の関係が
R2
である必要がある
メトリクス DCH
(the Dispersion of Class Hierarchy)
R1
：同一クラス
[22] Y. Higo, et al. A metric-based approach to identifying refactoring opportunities for merging code clones in a
R2:
共通の親クラス
を 持つ
与えられたコード片群と，その共通の親クラスまでの距離
の最大値を表す [22]
クラス A
コード片
a1
コード片
a2
クラス D
コード片
d
クラス E
コード片
e
クラス B
コード片
b
クラス C
コード片
c
クラス P
R3:
共通の親クラス
を持たない
DCH = 0
DCH
は 1 以上の整
数
（この例では１）
DCH = ∞
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 19
自動分類を目的としたメトリクスの
定義
DCHS
：クローンセットに含まれるコード片間の関係を表す
DCHD
：チェーンに含まれるコード片間の関係を表す
各チェーンに含まれるコード片に対し，それぞれ DCH を
求め，その最大値を DCHD とする
クローンセットに含まれるコー
ド片について，それぞれ DCH
を求め，その最大値を DCHS と
する
DCHD = max{DCH(C
1
), …, DCH(C
m
)}
DCHS = max{DCH(S
1
), …, DCH(S
n
)}
C
1
C
2
S
1
S
2
コード片 a1
コード片 a2
コード片
b1
コード片
b2
クラス A
クラス B
親クラス
メトリクスによるチェーンドクローンセットの
分類
DCHD
DCHS
0
(R1)
1
以上の整数
(R2)
∞
(R3)
0
(R1)
Extract Method
が
適用可能
いずれのリファクタリングパターンも
適用不可能
1
以上の整数
(R2)
Pull Up Method
が
適用可能
∞
(R3)
Extract
SuperClass
が適用
可能
DCHS
：クローンセットに含まれるコード片間の関係を表
す
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 21
適用実験
概要
目的
チェーンドクローンセットの数，規模の調査
メトリクスを用いてチェーンドクローンセットを分類し，その
分類に対応したリファクタリングパターンを適用できるか確認
対象
ANTLR 2.7.4
（ 4.7 万行， 285 クラス）
C++, Java, C#
用コンパイラ・コンパイラ
チェーンドクローンセットに基づくリファクタリング支援ツール
を作成
コードクローン検出ツール CCFinder を用いてクローンセット
を検出
それらクローンセットに含まれるコード片間の依存関係を解析
し，チェーンドクローンセットを検出
定義したメトリクスに基づき，リファクタリングパターンを提
示
適用実験
チェーンドクローンセットの検出
全てリファクタリングパターンを適用可能なチェーンドクローンセットであっ
た
提示されたリファクタリングパターンを用いて，全てのチェーンドクローン
セットをリファクタリングできた
含まれるコード片数が多いチェーンドクローンセットを検出できた
三つの言語（ C++, C#, Java ）に対応した部分の多くがコードクローンとなっ
分類
検出数
コード片数
最大
最小
Extract Method
6
11
4
Pull Up Method
8
120
6
Extract SuperClass
1
4
4
いずれも適用不可能
0
合計
15
Department of Computer Science,
Graduate School of Information Science & Technology,
Osaka University
23
3
章：類義語の特定に基づ
類似コード片検索
ソースコード中から，クエリとして与えられたコード片の類似コード片を
特定する作業
類似コード片の同時修正を支援するためには，類似コード片検索を自動的
に行うツールが必要
入力コード片
（クエリ）
対象ソース
ファイル
e
i[0]
e
i[1]
e
i[n
i]
e
t1[0]
e
t1[1]
e
t1[n
t1]
e
t2[0]
e
t2[1]
e
t2[n
t2]
e
t2[0]
e
t2[1]
e
t2[n
t2]
入力プログラム要素
列
各ソースファイル
のプログラム要素
列
照合
類似コード
片
類似要素列
e
s1[0]
e
s1[n
s1]
e
s2[0]
e
s2[n
s2]
欠陥を含むコード片を与え
る
欠陥の有無を検
査
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 25
提案手法の概要
識別子の類似性に基づいて，類似コード片を検索す
る手法を提案
識別子を語単位に分割し正規化
“add_host” “add”
と” host” ，” type1” “type”
自然言語解析を用いて，語の類義語を特定
入力コード片に含まれる全ての語と一致する，もしくは類
義語である語を含む関数を検出する
類似コード片
（関数単位）
入力コード片
検索
語の抽出
対象ソースファイル
類義語の特定
語の抽出
類義語の特定手順 (1/4)
w
b
w
b
w
c
w
a
w
d
w
c
w
c
w
d
w
d
w
e
w
e
w
c
w
c
関数 × 語行列の作成
関数 f
0関数 f
1関数 f
2識別子
語
w
a
w
b
w
c
w
d
w
e
f
0
f
1
f
w
e
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 27
類義語の特定手順 (2/4)
関数 × 語行列を共起行列に変換
2
つの語が共起しているとは，それら語が同一関数内で
出現していること言う
2
つの語が n 回共起しているとは，それら語が n 個の関
数内で共起していることを言う
関数 × 語行列
w
a
w
b
w
c
w
d
w
e
f
0
f
1
f
2
共起行列
w
a
w
b
w
c
w
d
w
e
w
a
w
b
w
c
w
d
w
e
類義語の特定手順 (3/4)
共起行列から語間の距離を算出
自然言語処理 [13] で用いられている Jensen-Shannon divergence[38]
を用いる
w
a
と w
b
の距離は，分布 [1, 1, 0] と分布 [1, 0, 1] の divergence
共起行列
語間の距離を表す行列
w
a
w
b
w
c
w
d
w
e
w
a
w
b
w
c
w
d
w
e
w
a
w
b
w
c
w
d
w
e
w
a
w
b
w
c
w
d
w
e
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 29
類義語の特定手順 (4/4)
W
bCluster
bW
aCluster
aW
ｃCluster
ｃW
ｄCluster
ｄMerge
(distance: 0)
Merge
(distance: 0.17)
W
bCluster
bW
aCluster
acW
dCluster
dW
cW
bCluster
bdW
aCluster
acW
dW
c
語のクラスタリング
全ての語が独立したクラスタという状態から始めて，最も距離の小さい
クラスタから順次結合していく
クラスタ間の距離は，語間の距離の平均 （群平均法）
任意のクラスタ間の距離が，ユーザが指定した閾値以上になったら終了
入力コード片との照合
1.
入力コード片に含まれる各語について，対象関数中
に同一の語もしくは類義語が存在するか判定する
2.
全ての語について，１．が成立すれば，対象関数を
類似コード片として提示
node
node
alloc
add
入力コード片に含まれる語の列
host
alloc
add
host
対象関数に含まれる語の列
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 31
適用実験の概要
欠陥検出に対する有効性を確認した
日本語入力システム かんな 3.6
7.6KLOC, 203
関数 （＊ .c ファイルのみ）
18
個の関数がバッファオーバーフローエラーを含んでいた
ソフトウェア部品検索システム SPARS-J
36KLOC
， 859 関数 （＊ .c ファイルのみ）
50
個の関数が型キャスト忘れを含んでいた
CCFinder
， grep との性能比較を行った
かんなの結果
のみを発表
CCFinder
の結果
のみを発表
欠陥を含むコードを与える
欠陥を含む関数の割合を確認する
類似コード片（関
数）
入力コード片
検索
語の抽出
対象ソースファイル
類義語の特定
語の抽出
入力コード片（かんな） (1/2)
buf += HEADER_SIZE;
Request.type7.context = S2TOS(buf);
buf += SIZEOFSHORT;
Request.type7.number = S2TOS(buf);
buf += SIZEOFSHORT;
Request.type7.yomilen =
(short)S2TOS(buf);
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",
コード片 CF
Aコード片 CF
Bバッファを指すポインタを
加算
バッファを指すポインタを
加算
バッファからの読み込み処
理
バッファからの読み込み処
理
バッファーオーバフローエラーを含む
コード片 CF
A
， CF
B
， CF
C
を入力
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 33
入力コード片（かんな） (2/2)
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);
コード片 CF
Cバッファを指すポインタを
評価基準
各入力コード片について，適合率（ Precisio
n
） , 再現率（ Recall ） , F 値を計測した
Ｄを欠陥を含む関数の集合， R を検索された
関数の集合とすると，以下のように表される
検索結果に含まれた関数のう
ち，欠陥を含む関数の割合
欠陥を含む関数のうち，
検索結果に含まれた関数の割合
適合率と再現率の
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 35
実験結果 (1/2)
語をクラスタリングする際の閾値 thr
を変化させたとき
の，各コード片の適合率，再現率， F 値
クラスタリングの閾値は， th
r
が与えられたとき
に，以下の手順で求めることができる
1.
対象ソースコードに含まれる任意の語の距離を求め，
その最大値を d
max
とする
2.
d
max
と th
r
の積を閾値とする
コード
片
提案手法（ th
r= 0.1
）
提案手法（ th
r= 0.2
）
CCFinder
適合率 再現率
F
値
適合率 再現率
F
値
適合率 再現率
F
値
CF
A0.50
0.72
0.59
0.18
1.00
0.31
1.00
0.06
0.11
CF
B0.19
0.33
0.25
0.18
1.00
0.31
1.00
0.06
0.11
CF
C1.00
0.06
0.11
0.33
0.06
0.10
1.00
0.06
0.11
実験結果 (2/2)
語をクラスタリングする際の閾値を変化させたとき
の，各コード片の適合率，再現率， F 値
適合率は良いが
，再現率は悪い
適合率は悪いが，
再現率は良い
各コード片に含まれる語が属するクラスタを分析し
た
コード
片
提案手法（ th
r= 0.1
）
提案手法（ th
r= 0.2
）
CCFinder
適合率 再現率
F
値
適合率 再現率
F
値
適合率 再現率
F
値
CF
A0.50
0.72
0.59
0.18
1.00
0.31
1.00
0.06
0.11
CF
B0.19
0.33
0.25
0.18
1.00
0.31
1.00
0.06
0.11
CF
C1.00
0.06
0.11
0.33
0.06
0.10
1.00
0.06
0.11
コード片を含む関
数のみが提示され
た
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 37
