プログラム依存グラフを用いたソースコードのパターン違反検出法井上研究室山田吾郎 1 背景パターン複数ヶ所に出現する特定の処理を実現するための実装[1] open(a); : read(a); : close(a); open(b); : read(b); : close(b); open(c); : read(c); : close(c); open(d); : read(d); : : パターンの実装に誤り(パターン違反)が生じ得る一部が欠落[2] 順序の誤り識別子名の変更漏れパターン違反を検出したい [1]石尾隆ら. シーケンシャルパターンマイニングを用いたコーディングパターン抽出. 情報処理学会論文誌, 2009 [2]A. Wasylkowski et al., Detecting object usage anomalies. In Proc. of ESEC/FSE 2007, 2007 2 既存手法と問題点ソースコード ---------- ------------------------------------------------------ パターンモデルモデル構築パターン抽出パターン違反 (頻出部分構造) 違反検出ソート確信度モデルの簡略化抽出可能なパターンが減少高い確信度を用いた検出検出漏れが増加確信度: “パターン違反らしさ”を表す値パターンの正しい実装と違反との出現比高ければ高いほど違反らしい 3 提案手法：概要ソースコード PDG ---------- ------------------------------------------------------ パターン PDG 構築プログラム依存グラフ（PDG) • 従来手法に比べ多くの情報を持つ 抽出可能なパターンが増加パターン抽出パターン違反違反検出低い確信度での検出 • 出現数の少ない違反を検出可能 • 誤検出増加ソート複数のメトリクス複数のメトリクス 5つのメトリクスにより • フィルタリング • ソート 誤検出の低下 4 提案手法：プログラム依存グラフ抽象化が少なく多くの情報をもつグラフの構成要素頂点: プログラムの文・条件式辺: データ依存関係・制御依存関係 1: 2: 3: 4: 5: int i = 0; i = method(); if ( i > 0) ..i = x; y = i; 1 2 3 4 5 5 提案手法：パターン抽出の例 ---------- -------- ------- ------------------------------------------ ソースコードＰＤＧの構築パターン抽出 P1 P2 6 提案手法：違反候補の検出確信度: パターンP1が存在するPDG中でP2も出現する条件付き確率確信度が1ではなく，かつ利用者が定めた閾値より大きい時，P1のみが出現するPDGがパターン違反頂点の欠落によるパターン違反 P1 P2 7 提案手法：メトリクス 5つのメトリクスを提案リフト値頂点欠落数違反PDG数頂点欠落数: 1 頂点重複度平均ギャップ長違反PDG数: 1 8 評価実験：概要既存研究であるGrouMiner[1]と比較実験を行う GrouMinerはPDGに近似したモデルを使用目的パターン抽出に用いるデータ増加によりGrouMinerで検出できなかったパターンを抽出できるか誤検出を抑えながら，少数しか出現しない違反を検出できるか実験方法準備としてメトリクスの閾値を決定する実験を行う本手法，GrouMinerともに上位15件を調査し分類 [1]T.T. Nguyen et al., Graph-based mining of multiple object usage patterns. In Proc. of ESEC/FSE 2009, 2009 9 評価実験：閾値決定違反候補プロジェクト --------------------------------- 違反検出上位50% 欠陥閾値 --------------------------------- 違反検出それぞれのメトリクスの中で最悪値を閾値に全てのメトリクスで上位50%に存在する候補に絞り込み絞りこまれた全候補から欠陥を調査，列挙 10 評価実験：結果プロジェクト名 Apache Ant GrouMin er 確信度 0.9 欠陥数(上位15件) 本手法確信度 0.9 確信度 0.6 確信度0.6 & GrouMiner 本手法フィルタリング 145 34 960 24 1 2 32 8 143 11 0 0 AspectJ 244 26 368 14 1 0 Apache Axis 145 32 689 27 0 1 Columba 40 144 1343 50 1 0 jEdit 47 36 632 11 1 1 Jigsaw 115 41 723 26 1 2 Struts 33 5 137 3 0 0 Apache log4J 11 検出例 Apache Axisからの欠陥: 確信度0.67 org.apache.axis.components.net.JSSESocketFactory public Socket create(...) throws Exception { if (port == -1) { port = 443;} : Socket sslSocket = null; : 欠落 org.apache.axis.components.net.SunJSSESocketFactory等2箇所 public Socket create(...) throws Exception { Socket sslSocket = null; if (sslFactory == null){ initFactory(); } if (port == -1) { port = 443;} : 12 まとめと今後の予定まとめ PDGをもとにパターン違反を検出する手法を提案ツールを実装し，GrouMinerと比較実験誤検出の増加を抑えながらパターン違反を検出今後の課題手法の高速化フィルタリングの有効性を他の手法で確認 13 ご清聴ありがとうございました 14