【論文メモ】＜2007＞DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones

 

原論文

deckard.pdf (purdue.edu)



Abstract

コードクローンの検出には多くのソフトウェアエンジニアリングの応用があります。既存のアプローチは、大規模なコードベースにスケーリングされていないか、微細なコードの変更に対して堅牢ではありません。本論文では、類似した部分木を識別する効率的なアルゴリズムを提案し、それをソースコードの木構造表現に適用します。当該アルゴリズムは、数値ベクトルによる部分木の新しい特性と、ユークリッド空間R^n内の数値ベクトルに対するユークリッド距離メトリックに基づいた効率的なアルゴリズムに基づいています。1つのクラスタ内のベクトルを持つ部分木は類似と見なされます。私たちは、DECKARDというクローン検出ツールとして私たちの木構造類似性アルゴリズムを実装し、LinuxカーネルやJDKを含むCおよびJavaで書かれた大規模なコードベースで評価しました。実験の結果、DECKARDはスケーラブルで正確であることが示されました。また、言語に依存せず、形式的に指定された文法を持つ任意の言語に適用可能です。

Introduction

多くのソフトウェアエンジニアリングのタスク、例えばリファクタリング、コード品質の理解、バグの検出などは、構文的または意味的に類似したコードフラグメント（一般的に「クローン」と呼ばれる）を抽出する必要があります。さまざまな研究によると、大規模なコードベースには多くの重複したコードが存在することが示されています。多くの重複は、プログラマーが機能を素早く複製するためにコードをコピー＆ペーストすることに起因することが多いです。この傾向は、メンテナンスが困難なコードを生み出すだけでなく、微妙なエラーを導入する可能性もあります。

文献にはクローン検出のための異なるアプローチが提案されています。ほとんどのアプローチは、意味的な類似性のチェックが非常に難しい（一般的には決定不能である）ため、コードの構文的な類似性を検出することに焦点を当てています。大まかに言えば、これらの技術は以下の4つのカテゴリに分類されます。

文字列ベース：プログラムはまず文字列（通常は行）に分割されます。各コードフラグメントは、連続する文字列のシーケンスで構成されます。2つのコードフラグメントが類似していると見なされる条件は、それぞれの構成文字列が一致する場合です。代表的な作品は、Bakerの「パラメータ化」マッチングアルゴリズムです。ここでは、識別子とリテラルがグローバル定数で置き換えられます。

トークンベース：プログラムはトークンシーケンスにレクシカルに解析され、ポテンシャルなコードクローンを示す重複したトークン部分列がスキャンされます。文字列ベースのアプローチと比較して、トークンベースのアプローチは、フォーマットやスペーシングなどのコードの変更に対して通常よりも堅牢です。CCFinderとCP-Minerは、トークンベースのテクニックの中で最もよく知られています。

ツリーベース：プログラムは解析され、ソースプログラムの解析木または抽象構文木（AST）表現が生成されます。生成された解析木またはAST内の部分木を比較することで、正確または近いマッチを識別できます。代わりに、異なるメトリクスを使用して部分木をフィンガープリント化し、似たようなフィンガープリントを持つ部分木を可能な重複として報告することもできます。

意味ベース：意味を考慮したアプローチも提案されています。KomondoorとHorwitzは、プログラム依存グラフ（PDG）とプログラムスライシングを使用して、コードクローンを特定するためにPDGの同型部分グラフを見つけることを提案しています。彼らはまた、特定されたクローンをグループ化し、ソフトウェアリファクタリングをサポートするための自動手順抽出のために元のコードの意味を維持するアプローチも提案しています。しかし、このような技術は大規模なコードベースにはスケーリングしていません。

既存の技術の中で、CCFinder [10]、CP-Miner [17]、およびCloneDR [4, 5] が最先端を代表しています。しかし、それらはいずれもスケーラビリティに限界があるか、コードの変更に対して堅牢ではありません。私たちの目標は、スケーラブルであり、コードの変更に対して堅牢な実用的な検出アルゴリズムを開発することです。

本論文では、類似した木を検出するための新しいアルゴリズムと、コードクローンを検出するための実用的な実装であるDECKARDを紹介します。アルゴリズムの主なアイデアは、AST内の構造情報を近似するための特定の特徴ベクトルを計算し、それから類似したベクトル（およびコードクローン）を効率的にクラスタリングするために、局所的に敏感なハッシュ（LSH）[7] を適応させることです。

図1は、DECKARDのハイレベルなアーキテクチャを示しています：
（1）形式的な構文規則から自動的に生成されたパーサー；
（2）パーサーはソースファイルを解析木に変換します；
（3）解析木は、解析木の構文情報を捉えた固定次元のベクトルのセットに変換されます；
（4）ベクトルはユークリッド距離に関してクラスタリングされます；
（5）追加の事後処理ヒューリスティックがクローンレポートを生成するために使用されます。

私たちは、DECKARDをJDKやLinuxカーネルを含む大規模なソフトウェア上で広範な経験的評価を行い、CloneDRやCP-Minerと比較しました。結果は、DECKARDがスケーラブルであり、正確であることを示しています：DECKARDは、大規模なコードベースでより多くのクローンを検出します。CloneDRやCP-Minerよりもスケーラブルであり、また、木ベースのCloneDRと同様にスケーラブルです。
論文の残りの部分は次のように構成されています。まず、アルゴリズムの詳細な概要を説明し、例を挙げます（セクション2）。次に、検出アルゴリズムの詳細を示します（セクション3）。次に、DECKARDの実装と評価について議論します（セクション4）。最後に、関連する研究を調査し（セクション5）、今後の研究について議論します（セクション6）。


Conclusion

本論文では、類似した部分木を特定するための実用的なアルゴリズムを提案し、コードクローンの検出に適用しました。このアルゴリズムは、木をR^nのベクトルとして新しい特性で表現し、効果的に木の構造情報を捉えるものであり、数値ベクトルの効率的なハッシュ化および近傍クエリングアルゴリズムに基づいています。私たちはこのアルゴリズムをDECKARDというツールで実装しました。DECKARDは言語に依存せず、高度に設定可能です。私たちはLinuxカーネルやJDKなどの大規模なコードベースでDECKARDを評価しました。DECKARDは数百万行のコードに簡単にスケールし、既存のツールよりも多くのクローンを特定しました。私たちのアルゴリズムは一般的であり、グラフなどの他のデータ構造での利用も可能です。また、バグ検出、コードリファクタリング、プログラミングパターンの発見など、他の多くの潜在的な応用があります。将来の研究では、このアルゴリズムをこれらの問題領域に適用する予定です。

コメント

コメントを投稿

このブログの人気の投稿

【論文】2023 Large Language Models for Software Engineering: Survey and Open Problems

  [2310.03533] Large Language Models for Software Engineering: Survey and Open Problems 要旨 本論文は、ソフトウェアエンジニアリング（SE）分野における大規模言語モデル（LLM）の新たな応用領域に関する調査を提供します。また、ソフトウェアエンジニアが直面する技術的課題にLLMを適用するための今後の研究課題も提示します。LLMの新たに生じた特性は、コーディング、設計、要求仕様、修復、リファクタリング、パフォーマンス改善、ドキュメント作成、および分析など、ソフトウェアエンジニアリング活動全体にわたり、斬新で創造的な応用可能性をもたらします。しかし、これらの特性は同時に大きな技術的課題も伴い、ハルシネーションのような誤った解答を排除するための信頼性ある手法が求められています。我々の調査は、信頼性が高く効率的で効果的なLLMベースのSEシステムを開発・導入する上で、従来のSEとLLMを組み合わせたハイブリッド技術が重要な役割を果たすことを明らかにしています。 Introduction 本論文は、大規模言語モデル（LLM）をソフトウェアエンジニアリング（SE）に応用する分野における最新の進展、技術的な進歩、および実証的な結果を調査したものです。この調査を通じて、急速に発展しているものの、まだ初期段階にあるこの研究分野における空白を浮き彫りにしています。また、文献におけるギャップや技術的な機会に基づき、ソフトウェアエンジニアリング研究コミュニティにとっての未解決の問題や課題も特定しています。 この急速に拡大する分野を網羅することは難しいものの、本調査がSEにおける新たなLLMベースの分野の初期段階の全体像を把握するのに役立つことを期待しています。この分野の科学的・技術的な構造はまだ形成されつつありますが、既に今後の研究の方向性や取り組むべき技術的な課題、また、将来に向けた有望な研究の道筋を確認することが可能です。 特に、ソフトウェアエンジニアリングの既存のトレンドや確立されたアプローチ、サブディシプリン（分野）との関連性や共鳴が見受けられます。また、技術的な課題も多く存在する一方で、この分野の未来には楽観的な要素も少なくありません。多くの研究者が科学的にも、また経験則としても指摘して...
続きを読む

【論文】ChatGPT Prompt Patterns for Improving Code Quality, Refactoring, Requirements Elicitation, and Software Design

2303.07839   論文概要 ソフトウェアエンジニアリングにおけるプロンプト設計技術を、パターンの形式で紹介。 大規模言語モデル（LLM）、例えば ChatGPT を使用して一般的なソフトウェアエンジニアリングの活動を自動化する際に生じる、一般的な問題を解決する方法を提案。例えば、コードをサードパーティライブラリから分離することや、要件リストから API 仕様を作成することなどが含まれる。 ソフトウェアエンジニアリングにおける LLM の活用に関する研究に対する論文の貢献： ソフトウェアエンジニアリング向けのパターンのカタログを提供し、それらを解決する問題の種類ごとに分類する。 要件抽出、迅速なプロトタイピング、コード品質の向上、デプロイメント、およびテストの改善に適用された複数のプロンプトパターンを探求する。 はじめに ソフトウェアエンジニアリングタスクの自動化におけるLLMとプロンプトの概要 一般的に、LLMとの対話は「プロンプト」を入力することで行われる。プロンプトとは、LLMにコンテキストを提供し、テキストの生成を誘導するための自然言語による指示のことである。 チャットベースの環境では、プロンプトはユーザーが ChatGPT などのLLMに送信するチャットメッセージとして機能する。本論文では、ChatGPT を活用したチャット対応のLLMに焦点を当てて議論を進める。 プロンプトの使い方には大きく分けて二つの方法がある。本論文では、これら二種類のプロンプトパターンについて詳しく扱う。 LLMに直接情報を求めたり、コードを生成させたりする方法。 LLMに特定のルールを指示し、それに従わせる方法（例：特定のコーディング規約に準拠させる）。 ソフトウェアエンジニアリングタスク向けのプロンプトパターンの概要 本論文は、以前の研究で提案した プロンプトパターン の概念 [9] に基づいている。プロンプトパターンとは、LLMとの対話における問題を解決するための再利用可能なプロンプト設計である。 プロンプトパターンは、ソフトウェアパターン [10], [11] と同様に、優れた設計経験を形式化したものであり、プログラムが特定の設計原則やセキュアコーディングガイドライン に準拠することを保証するなど、LLMとの対話における一般的な問題に対する再利用可能な解決策を...
続きを読む

参考論文：コードクローン検出において比較する候補の絞り方

  軽量な類似度計算によるプロジェクト間のソースファイル集合の再利用検出.pdf ソースコードから作成した木構造の断片について、LSHを用いてクラスタリングすることで高速にコードクローンを検出[13]。 DECKARD: Scalable and accurate tree-based detection of code clones (smu.edu.sg) ソースコードから作成したTF-IDFベクトルについて、cross-polytope LSHを用いてクラスタリングし、コードブロック単位でのコードクローンを検出[14]。 _pdf (jst.go.jp) 転置インデックスを使って比較するべき候補を絞ることで、効率的にコードクローンを検出[15]。 1512.06448 (arxiv.org)
続きを読む