ソードコードの編集に基づいた

TF-IDF法とLSHアルゴリズムを用いた
関数単位のコードクローン検出法
井上研究室
山中裕樹
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
コードクローン
 ソースコード中に同一・類似した部分を持つコード片
►ソースコードのコピーアンドペーストなどによって発生
►本研究では関数単位のコードクローンが対象
関数C
関数A
関数B
クローンペア
2
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
コードクローンの定義 [1]
種類
意味
タイプ1 レイアウト・空白・コメントの違いを除き完全に一致している
タイプ2 タイプ1に加え変数名・型の違いを除き構文的に一致している
タイプ3 タイプ2に加え文が挿入・削除・変更されている
タイプ4 構文上異なる実装だが，類似処理を実行している
[1]C. K. Roy, J. R. Cordy, R. Koschke. Comparison and evaluation of code clone
detection techniques and tools: a qualitative approach. Science of Computer
Programming, Vol. 74, No. 7, pp. 470–495, 2009.
3
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
コードクローン：タイプ1
種類
意味
タイプ1 レイアウト・空白・コメントの違いを除き完全に一致している
タイプ2 タイプ1に加え変数名・型の違いを除き構文的に一致している
タイプ3 タイプ2に加え文が挿入・削除・変更されている
タイプ4 構文上異なる実装だが，類似処理を実行している
int sum(int[] data){
int sum = 0;
for(int i=0; i<data.length; i++){
sum = sum + data[i];
}
return sum;
}
関数A
int sum(int[] data){
int sum = 0;
for(int i=0; i<data.length; i++){
sum = sum + data[i];
}
return sum;
}
関数B
4
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
コードクローン：タイプ2
種類
意味
タイプ1 レイアウト・空白・コメントの違いを除き完全に一致している
タイプ2 タイプ1に加え変数名・型の違いを除き構文的に一致している
タイプ3 タイプ2に加え文の挿入・削除・変更されている
タイプ4 構文上異なる実装だが，類似処理を実行している
int sum(int[] data){
int sum = 0;
for(int i=0; i<data.length; i++){
sum = sum + data[i];
}
return sum;
}
関数A
double sum(double[] data){
double sum = 0;
for(int j=0; j<data.length; j++){
sum = sum + data[j];
}
return sum;
}
関数B
5
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
コードクローン：タイプ3
種類
意味
タイプ1 レイアウト・空白・コメントの違いを除き完全に一致している
タイプ2 タイプ1に加え変数名・型の違いを除き構文的に一致している
タイプ3 タイプ2に加え文が挿入・削除・変更されている
タイプ4 構文上異なる実装だが，類似処理を実行している
int sum(int[] data){
int sum = 0;
for(int i=0; i<data.length; i++){
sum = sum + data[i];
}
return sum;
}
関数A
int sum(int[] data){
int sum = 0;
for(int i=0; i<data.length; i++){
sum += data[i];
}
return sum;
}
関数B
6
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
コードクローン：タイプ4
種類
意味
タイプ1 レイアウト・空白・コメントの違いを除き完全に一致している
タイプ2 タイプ1に加え変数名・型の違いを除き構文的に一致している
タイプ3 タイプ2に加え文が挿入・削除・変更されている
タイプ4 構文上異なる実装だが，類似処理を実行している
int sum(int[] data){
int sum = 0;
for(int i=0; i<data.length; i++){
sum = sum + data[i];
}
return sum;
}
関数A
int sum(int[] data){
int sum = 0, i=0;
while(i<data.length){
sum += data[i]; i++;
}
return sum;
}
関数B
7
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
コードクローン検出の目的
 リファクタリング支援
Class S
Class A
Class B
hoge()
hoge()
メソッド
の引上げ
hoge()
Class A
Class B
クローンペア
 一貫した修正漏れによるバグの検出（タイプ3,4）
int sum(int[] data){
if ( data == null)
return null;
・・・
}
例外処理の
追加漏れ
int sum(int[] data){
//例外処理漏れ
・・・
}
8
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
既存のコードクローン検出手法
 構文的な類似性に着目した手法
►CCFinder[2] など
►メリット：タイプ1,2のコードクローンを高速に検出可能
►デメリット：タイプ3,タイプ4のコードクローンの検出が困難
 処理の意味的な類似性に着目した手法
►MeCC[3] など
►メリット：タイプ1- タイプ4のコードクローンを検出可能
►デメリット：検出時間に膨大な時間がかかる
[2] T. Kamiya, S. Kusumoto, K. Inoue. CCFinder: a multilinguistic token-based code clone detection system for large scale
source code. IEEE Trans. Softw. Eng., Vol. 28, No. 7, pp. 654–670, 2002.
[3] H. Kim, Y. Jung, S. Kim, K. Yi. MeCC: memory comparison-based clone detector. In Proc. of ICSE ’11, pp. 301–310, 2011.
9
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
提案手法の概要
 関数中のワードに重み付けを行い特徴ベクトルを計算
►識別子名を構成する単語（関数名，変数名）
►予約語に含まれる単語（ if, while ）
 近似アルゴリズムを用いて特徴ベクトルをクラスタリング
全タイプの関数単位のコードクローンを高速に検出
10
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
検出アルゴリズム
STEP1：各関数からワードの抽出
STEP2: TF-IDF法を用いて関数を特徴ベクトルに変換
STEP3: LSHアルゴリズムを用いて特徴ベクトルをクラスタリング
STEP4: クラスタ中の特徴ベクトル間の類似度を計算
STEP1
STEP2
STEP3
STEP4
Function A
ワード回数
xxx
3
yyy
2
・・・・・・
Function B
ソースコード
ワード回数
xxx
2
yyy
4
・・・
Function A
{a1 , a2 , a3 , }
Function B
{b1 , b2 , b3 , }
0.95
Function A
Function B
特徴ベクトル
0.70
0.70
Function C
Function D
Function E
・・・
ワードリスト
類似度
クラスタ
0.90
・・・
関数対クローン
Function A
✓
Function B
Function C
Function D
Function C
Function E
Function D
✓
Function E
・・・
・・・
クローンペアリスト
11
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
STEP1：ワードの抽出
 各関数から識別子名・予約語を抽出
► 2文字以下の識別子は全て同一のワード（メタワード）として扱う
► 複数の単語の場合，区切り文字や大文字で分割
 例：dataSize
⇒ data + size
関数 Aのワードリスト
関数 Aのソースコード
int sum(int[] data, int dataSize){
int sum = 0;
for(int i=0; i<dataSize; i++)
sum += data[i];
return sum;
}
予約語
分割した
識別子名
ワード出現回数
int
4
for
1
return
1
data
4
sum
4
size
2
メタワード
4
12
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
STEP2：特徴ベクトルの計算
 TF-IDF法を利用
►文書中の単語に関する重み付けの手法
►TF値とIDF値の積で表される
TF値
IDF値
関数中の
ワードの出現頻度
ソースコード全体の
ワードの希少さ
×
各ワードの重みを特徴量として
各関数を特徴ベクトルに変換
13
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
STEP3：特徴ベクトルのクラスタリング
 LSH(Locality-Sensitive Hashing)[4]を利用
►近似最近傍探索アルゴリズムの一つ
 ハッシュ関数を用いて高速にクラスタリング可能
►クローンペアと成りうる候補を絞ることが目的
関数名
特徴ベクトル
Function A
(5,4,2,1,・・・ )
Function B
(0,0,2,2,・・・ )
Function C
(0,0,2,2,・・・ )
Function D
(3,4,2,1,・・・ )
Function E
(5,4,2,3,・・・ )
Function F
(0,1,2,2,・・・ )
・・・
・・・
各関数の特徴ベクトル
Function A
Function D
Function F
クラスタリング
Function B
Function C
Function E
関数のクラスタ
[4] P. Indyk, R. Motwani. Approximate nearest neighbors: towards removing the
curse of dimensionality. In Proc. of STOC ’98, pp. 604-613, 1998.
14
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
STEP4: ベクトル間の類似度計算
 各クラスタ内で特徴ベクトル間の類似度を計算
►コサイン類似度を利用
 
 
►特徴ベクトル a , b 間の類似度の計算方法
閾値（0.9）以上であればクローンペアとして検出
15
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
評価実験
 実験1：ベンチマークを用いた検出性の評価
►本手法でコードクローンを検出することができるか
 実験2：既存手法との比較実験
►検出時間と検出精度の比較
 実験3：検出したコードクローンの調査
►本手法でどのようなタイプ4のコードクローンを検出できたか
16
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
実験1：検出性の評価
 Royらのベンチマーク[5]を利用
►タイプ1-タイプ4の16個のクローンペアが用意
ベンチマーク
検出結果
タイプ1
3
3
タイプ2
4
2
タイプ3
5
5
タイプ4
4
4
全タイプのコードクローンを検出することを確認
[5] C. K. Roy, J. R. Cordy, R. Koschke. Comparison and evaluation of code clone detection techniques and
tools: a qualitative approach. Science of Computer Programming, Vol. 74, No. 7, pp.470-495, 2009.
17
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
実験2：既存手法との比較
 メモリベースの検出ツールMeCCと比較
►タイプ1-タイプ4の関数単位のコードクローン検出
 MeCCの評価実験で利用されたOSSに適用
►検出精度・検出時間を比較
プロジェクト名
ApacheHTTPD
Python
PostgreSQL
言語
C
C
C
サイズ
バージョン
343KLOC 2.2.14
435KLOC
2.5.1
937KLOC
8.5.1
18
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
検出精度の比較結果
 適合率と各タイプの正解検出数を比較
プロジェクト名
ApacheHTTPD
Python
本手法
PostgreSQL
合計
ApacheHTTPD
Python
MeCC
PostgreSQL
合計
適合率
95.4%
94.5%
94.7%
94.6%
87.5%
85.3%
83.1%
85.0%
タイプ1
71
19
57
147
2
3
9
14
検出クローン
タイプ2 タイプ3 タイプ4
100
190
11
103
159
21
230
341
17
433
690
49
84
71
10
127
82
13
120
88
14
331
241
37
• MeCCよりも高い適合率で検出可能である
• 各タイプの検出数もMeCCを上回っている
19
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
検出時間の比較結果
 MeCCの実行環境と同一のものを利用
► Ubuntu 64-bit ( RAM: 8.0GB, CPU: Intel Xeon 2.4GHz)
ApacheHTTPD
Python
PostgreSQL
本手法
1m43s
2m13s
4m39s
MeCC
310m34s
65m26s
428m32s
MeCCよりも高速な検出を行うことが可能
20
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
実験3：コードクローンの実例(1/2)
 繰り返し処理の置き換え
static const XML_Char *
poolCopyStringN(STRING_POOL *pool, const
XML_Char *s, int n)
{
if (!pool->ptr && !poolGrow(pool))
return NULL;
for (; n > 0; --n, s++) {
if (!poolAppendChar(pool, *s))
return NULL;
}
s = pool->start;
poolFinish(pool);
return s;
}
for文を用いた繰り返し
static const XML_Char * FASTCALL
poolCopyString(STRING_POOL *pool, const
XML_Char *s)
{
// 例外処理漏れの可能性がある!
do {
if (!poolAppendChar(pool, *s))
return NULL;
}while (*s++);
s = pool->start;
poolFinish(pool);
return s;
}
do-while文を用いた繰り返し
21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
実験3：コードクローンの実例(2/2)
 文の並び替え
static PyObject *
static PyObject *
dequeiter_next(dequeiterobject *it)
dequereviter_next(dequeiterobject *it)
{
{
PyObject *item;
PyObject *item;
if (it->deque->state != it->state) {
if (it->counter == 0)
it->counter = 0;
return NULL;
PyErr_SetString(PyExc_RuntimeError,
if (it->deque->state != it->state) {
"deque mutated during iteration");
it->counter = 0;
return NULL;
PyErr_SetString(PyExc_RuntimeError,
}
"deque mutated during iteration");
if (it->counter == 0)
return NULL;
return NULL;
}
assert (!(it->b == it->deque->rightblock &&
assert (!(it->b == it->deque->leftblock &&
it->index > it->deque->rightindex));
it->index < it->deque->leftindex));
・
・
・
・
例外処理の
・
・
位置が異なる
}
}
22
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
まとめと今後の課題
 まとめ
►全タイプの関数単位のコードクローン検出法を提案
 TF-IDF法を利用して関数を特徴ベクトルに変換
 LSHアルゴリズムを用いて特徴ベクトルをクラスタリング
►既存手法と比較して高精度・高速な検出を実現
 今後の課題
►LSI（Latent Semantic Indexing）などの手法との比較
►様々なプログラミング言語に対応
►他のコードクローン検出ツールとの比較
23
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
ご清聴ありがとうございました
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Download Report