ギャップを含むクローンセットの検出と評価

これまでに多数のクローン検出手法が提案されている．検出手法には互いに類似するコード片のペアであるクローンペア形式で出力する手法と互いに類似するコード片の集合であるクローンセット形式で出力する手法がある．どちらの形式で出力すべきかはクローン情報の用途によって異なるため，クローンの検出は両方の形式で出力できることが好ましい．しかし多くの既存検出手法では文の挿入や削除といったギャップを含むクローンはクローンペアの形式でしか出力できない．さらにクローンセットを検出できる手法は検出の精度やスケーラビリティの面で課題が残る．本研究では極大クリーク列挙アルゴリズムを利用してクローンペア形式で表されたクローンの情報からクローンセットを検出する手法を提案する．提案手法ではコード片を頂点，2つのコード片がクローンペアであることを辺と見なしたグラフを作成したときに極大クリークを1つのクローンセットと見なす．実験では提案手法を実装したツールを5つのオープンソースソフトウェアに対して適用した．提案手法と検出の精度に課題がある既存手法に対して同じクローンペア情報を与えたところ，すべての対象ソフトウェアに対して提案手法の方が多くのクローンセットを検出しており，既存手法で検出されるクローンセットが提案手法では細かく分割されていることが確認できた．また，提案手法はクローンペア情報から数秒でクローンセットを高速に検出できた．

Many clone detection techniques have been proposed before now. There are two output formats of clone detection results. One is the clone pair format, which is a pair of code fragments that are similar to each other. The other is the clone set format, which is a set of code fragments that are similar to one another. The clone pair format is better in some situations while the clone set format is better in other situations. Hence, clone detection techniques should be able to output in both formats. However, most of the existing clone detection techniques that are capable of detecting gapped clones, which contains some gaps such as insertions and/or deletions of statements, can detect only clone pairs. In addition, in the case of the techniques that can detect clone sets, there is another problem that their detection accuracy is low and their scalability is poor. In this paper, we propose a new approach to obtain clone sets from detected clone pairs by using the maximum clique enumeration algorithm. Our proposed approach constructs a graph whose vertices are code fragments of the clone pairs and whose edges are clone pair relationships. Thereafter, maximal cliques in the graph are detected as clone sets. We applied our proposed approach to five open source software. We gave the same clone pairs to the proposed approach and an existing one, which has an issue in detection accuracy. The proposed approach detected more clone sets for all the target software, which means that the clone sets detected by the existing approach were finely devided by the proposed approach. In addition, our proposed approach could detect clone sets from clone pairs for each project in several seconds.