この論文では、プログラムの構造的変更を細粒度解析するのためのツールについて報告しています。Diff/TSと呼ばれるこのツールは、あるリビジョンのプログラムを別のリビジョンに変更する際に要する、移動（move）を含む編集操作（edit operation）の列を計算し、可視化し、分類することができます。

Abstract

This paper reports on a tool for fine-grained analysis of structural changes made between revisions of programs.  The tool, called Diff/TS, calculates, visualizes and classifies edit operations including moves that will change one revision into another by means of detailed tree structural analysis on source code.  Such analysis tends to be time consuming and inflexible.  We have  extended a general tree comparison algorithm with heuristics driven control configurable for multiple programming languages and have achieved both processing speed and analysis precision needed for investigating large-scale software projects.  The tool is capable of processing Python, Java, C and C++ projects.  We present several applications including software archaeology on a widely known open source software project and automated phylogenetic malware classification based on control flows.  These examples suggest that tree differencing is useful for measuring distance or dissimilarity between tree structured artifacts, and offer good precision tests of the method.

Reference

Masatomo Hashimoto and Akira Mori. Diff/TS: A Tool for Fine-Grained Structural Change Analysis. In Proceedings of the 15th Working Conference on Reverse Engineering (WCRE ’08). IEEE Computer Society, Washington, DC, USA, pp. 279-288, 2008. DOI: 10.1109/WCRE.2008.44

ダウンロード(PDF)

実装

AST (abstract syntax trees) の比較に特化した実装がこちらにあります。

解析結果サンプル

Diff/TSによる解析結果のサンプルはこちらにあります。