プログラム依存グラフを用いた ソースコードのパターン違反検出法

Presentation on theme: "プログラム依存グラフを用いた ソースコードのパターン違反検出法"— Presentation transcript:

1 プログラム依存グラフを用いた ソースコードのパターン違反検出法
井上研究室 山田 吾郎

2 背景 パターン違反を検出したい パターン パターンの実装に誤り(パターン違反)が生じ得る
複数ヶ所に出現する特定の処理を実現するための実装[1] パターンの実装に誤り(パターン違反)が生じ得る 一部が欠落[2] 順序の誤り 識別子名の変更漏れ open(a); : read(a); close(a); open(b); : read(b); close(b); open(c); : read(c); close(c); open(d); : read(d); イディオムｊはややこしいから使わない！！」 パターン違反を検出したい [1]石尾 隆ら. シーケンシャルパターンマイニングを用いたコーディングパターン抽出. 情報処理学会論文誌, 2009 [2]A. Wasylkowski et al., Detecting object usage anomalies. In Proc. of ESEC/FSE 2007, 2007

3 既存手法と問題点 確信度: “パターン違反らしさ”を表す値 パターンの正しい実装と違反との出現比 モデル構築 パターン抽出 違反検出 ソート
ソースコード モデル パターン (頻出部分構造) パターン違反 モデル構築 パターン抽出 違反検出 ソート ------ - -- --- -- - ------ --- --- - -- ------ 確信度 確信度 モデルの簡略化 抽出可能なパターンが減少 高い確信度を用いた検出 検出漏れが増加 モデル作る 目標に沿った最適化 パターン抽出する 頻出する部分構造．例えばグラフなら… 違反検出する 確信度を使う．確信度の話を読み上げる． 問題点 抽出が重いからモデルを簡略化→とれないパターン→欠陥が 誤検出が多いから確信度を高く設定→少数出現する違反はとれない 確信度: “パターン違反らしさ”を表す値 パターンの正しい実装と違反との出現比 高ければ高いほど違反らしい

4 提案手法：概要 PDG PDG構築 パターン抽出 違反検出 ソート プログラム依存グラフ （PDG) 低い確信度での検出 複数のメトリクス
ソースコード PDG パターン パターン違反 PDG構築 パターン抽出 違反検出 ソート ------ - -- --- -- - ------ --- --- - -- ------ プログラム依存グラフ （PDG) 低い確信度での検出 複数のメトリクス 5つのメトリクスにより フィルタリング ソート 誤検出の低下 従来手法に比べ多くの情報を持つ 抽出可能なパターンが増加 出現数の少ない違反を検出可能 誤検出増加

5 提案手法：プログラム依存グラフ 1 2 3 4 5 抽象化が少なく多くの情報をもつ グラフの構成要素 頂点: プログラムの文・条件式
辺: データ依存関係・制御依存関係 1 1: int i = 0; 2: i = method(); 3: if ( i > 0) 4: ..i = x; 5: y = i; 2 3 4 5

6 提案手法：パターン抽出の例 パターン抽出 P1 P2 ＰＤＧの構築 ソースコード 2段目3段目キャプション入れる --- - --
------ ＰＤＧの構築 --- - -- ------ --- - -- ------ ソースコード パターン抽出 P1 2段目3段目キャプション入れる P2

7 提案手法：違反候補の検出 確信度: パターンP1が存在するPDG中でP2も出現する条件付き確率
頂点 の欠落によるパターン違反 P1 P1が変種なんやから，1.0ちゅうことは変種の定義によりやな P2

8 提案手法：メトリクス 5つのメトリクスを提案 リフト値 頂点欠落数 違反PDG数 頂点重複度 平均ギャップ長 頂点欠落数: 1
どれを説明してるかキャプション 頂点欠落数: 1 違反PDG数: 1

9 評価実験：概要 既存研究であるGrouMiner[1]と比較実験を行う 目的 実験方法 GrouMinerはPDGに近似したモデルを使用
誤検出を抑えながら，少数しか出現しない違反を検出できるか 実験方法 準備としてメトリクスの閾値を決定する実験を行う 本手法，GrouMinerともに上位15件を調査し分類 表現に一貫性がない [1]T.T. Nguyen et al., Graph-based mining of multiple object usage patterns. In Proc. of ESEC/FSE 2009, 2009

10 評価実験：閾値決定 違反検出 違反検出 それぞれのメトリクスの中で最悪値を閾値に 全てのメトリクスで上位50%に存在する候補に絞り込み
プロジェクト 違反候補 上位50% 違反検出 ------ --- 欠陥 閾値 違反検出 ------ --- それぞれのメトリクスの中で最悪値を閾値に 表現に一貫性がない 全てのメトリクスで上位50%に存在する候補に絞り込み 絞りこまれた全候補から欠陥を調査，列挙

11 評価実験：結果 プロジェクト名 GrouMiner 確信度0.9 本手法 欠陥数(上位15件) 確信度 0.9 0.6 確信度0.6 &フィルタリング Apache Ant 145 34 960 24 1 2 Apache log4J 32 8 143 11 AspectJ 244 26 368 14 Apache Axis 689 27 Columba 40 144 1343 50 jEdit 47 36 632 Jigsaw 115 41 723 Struts 33 5 137 3 合計6:5 誤検出を抑えながら検出できたか？ 向こうでとれてたのがとれてません＞＜ でも既存手法でとれなかったのがとれていますね＾ｑ＾

12 org.apache.axis.components.net.JSSESocketFactory
検出例 Apache Axisからの欠陥: 確信度0.67 public Socket create(...) throws Exception { if (port == -1) { port = 443;} : Socket sslSocket = null; org.apache.axis.components.net.JSSESocketFactory 欠落 org.apache.axis.components.net.SunJSSESocketFactory等2箇所 public Socket create(...) throws Exception { Socket sslSocket = null; if (sslFactory == null){ initFactory(); } if (port == -1) { port = 443;} :

13 まとめと今後の予定 まとめ 今後の課題 PDGをもとにパターン違反を検出する手法を提案 ツールを実装し，GrouMinerと比較実験
誤検出の増加を抑えながらパターン違反を検出 今後の課題 手法の高速化 フィルタリングの有効性を他の手法で確認

14 ご清聴ありがとうございました