ソフトウェアにおける構造的な変更の細粒度解析 Fine-Grained Structural Change Analysis of Software Artifacts

thumb image

ソフトウェアはそのライフサイクルにおいて、様々な要求に応えるために様々な変更を受け、それが積み重なることで、生物さながら進化してゆくように見えます。生物におけるDNAに相当するとも言えるソースコードに対する変更の詳細情報を蓄積することで、時間の概念を含んだような高度な分析がソフトウェアに対して可能となります。例えば、類似度の高いコード片がそれぞれどのように変化してゆくかを追跡することで、不具合の修正漏れを発見することができます。

ソースコードはプログラミング言語の文法規則に従った階層構造を持っており、その規模が大きくなるにつれ、それに対する変更の解析が困難となりますが、新しい近似アルゴリズムを開発することでその困難を克服しました。このアルゴリズムはソースコードだけでなく、様々な階層構造に適用可能です。例えば、バイナリ解析技術を利用し制御構造を反映した階層構造に変換することで、ソースコードが入手できないようなマルウェアに対しても適用することができます。

このプロジェクトでは、以下のような課題に取り組んでいます。

  1. 大規模階層構造の細粒度差分計算アルゴリズムの開発
  2. ソフトウェアの系統分析
    1. マルウェアの系統分析
    2. 相同コードの同定とその追跡による、一貫性の無い変更の検出
  3. ソースコード変更履歴からの横断的関心事の抽出
  4. 大規模ソフトウェアにおける複合的な変更パターンの同定※
  5. ソフトウェアプロダクトラインのためのフィーチャモデルの抽出
  6. 故障を引き起こす変更の自動特定※

科研費(基盤B)の助成を受けました。

論文

This project focuses on fine-grained analyses 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, Fortran, C and C++ projects. We have presented several applications including phylogenetic analyses on widely known open source software projects and automated phylogenetic malware classification based on control flows.

Papers

2017.07.08

Members