プログラム依存グラフの一貫性検査に基づく欠陥候補の検出手法

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 メソッド内で同時に出現することの多いメソッド呼び出し文の集合
関連研究 欠陥の自動検出に関連する2つの研究を紹介 PR-Miner [1] JADET [2] メソッド内で同時に出現することの多いメソッド呼び出し文の集合 オブジェクトの使い方を 表すグラフ イディオム 誤実装 イディオム 誤実装 open(c); read(c); f.close() close() open(c); : read(c); f.open(“?”); f.read(); g.close(); read() f.read() open() f.open() 誤実装 [1] Z. Li et al., PR-Miner: Automatically extracting implicit programming rules and detecting violations in large software code. In Proc. of ESEC/FSE 2005, 2005 [2]A. Wasylkowski et al., Detecting object usage anomalies. In Proc. of ESEC/FSE 2007, 2007

4 関連研究: PR-Miner イディオムの抽出 欠陥の検出 ソースコード中のメソッド内の文の集合にアイテムセットマイニングを適用
順序を持たない集合の集合から、頻出する部分集合を抽出する手法 欠陥の検出 抽出した頻出部分集合と、そのサブセットの出現数を比較 サブセットのみ出現するメソッドが少数であれば、欠陥の候補とする read(b); : open(a); close(a); read(a); : open(a); close(a); read(a); : open(a); close(a); open(a); : read(a); close(a); read(b); : open(b); close(a); open(a); : read(a); close(a); マイニング 出現比の計算 close() 右の図で順番を考慮してないってのを言及しておく open(a); : read(a); close(a); close(a); : open(a); read(a); read() open(d); : read(d); 4 4 4 4 open() 1

5 関連研究: JADET イディオムの抽出 欠陥の検出 1つのオブジェクトに着目し、その使い方をグラフ化 頻出する部分グラフがイディオム
頂点はラベルなし、辺のラベルが文 頻出する部分グラフがイディオム 欠陥の検出 頻出する部分グラフとほとんど同じであるが、一部が欠落しているものが少数であれば、欠陥の候補とする <enter> public Hoge getHoge(){ Hoge result = new Hoge(); for (int i=0; i<3; i++){ result.add(i); } return result; result<init> <exit> result.add(i)

6 プログラムの文の間に生じる関係を多く取得すれば、より高精度に欠陥を検出できるのではないか？
関連研究: 問題と解決方法 イディオムのモデル化の段階で情報を削る 制御構造 文の順序 データ依存関係 誤検出の割合が高くなる 検出できない欠陥が増える 精度の説明　適合率？再現率？ プログラムの文の間に生じる関係を多く取得すれば、より高精度に欠陥を検出できるのではないか？

7 提案手法 イディオムの抽出の対象はプログラム依存グラフ(Program Dependence Graph)
文間の依存関係を表現したグラフ イディオムはPDG上で頻出部分グラフとして現れる PDGを用いることで違反の原因を細かく特定できる ＰＤＧの構築 イディオムの抽出 違反の検出 ------ - -- --- -- - ------ --- --- - -- ------ ソースコード PDG さっきのスライドと対比して、網羅的にいえる プログラムのぶんかんのイゾンカンケイヲヒョウゲンシタグラフ 文館の関係

8 プログラム依存グラフ 1 2 3 4 5 プログラム依存グラフ(Program Dependence Graph)とは グラフの構成要素
プログラム中の文の間における関係を表現した有向グラフ グラフの構成要素 頂点: プログラムの文・条件式 辺: データ依存関係・制御依存関係 1 1: int i = 0; 2: i = method(); 3: if ( i > 0) 4: ..i = x; 5: y = i; 2 3 4 5

9 プログラム依存グラフ: 制御依存辺 1 2 3 4 5 ある文と、その文が実行されるか決定する文の間の関係
2つの文 S, T 間で2つの関係が成立 S が条件文 T が実行されるかどうかは、Ｓ の判定結果に依存 1 1: int i = 0; 2: i = method(); 3: if ( i > 0) 4: ..i = x; 5: y = i; 2 3 4 5

10 プログラム依存グラフ: データ依存辺 1 2 3 4 5 ある変数が参照される文と、その変数が定義された文の間の関係
2つの文 S, T 間で変数 v に関する3つの関係が成立 S で v が定義される T で v が参照される S から T へ途中で変数 v を再定義している文が存在しない経路が存在 1 1: int i = 0; 2: i = method(); 3: if ( i > 0) 4: ..i = x; 5: y = i; 文1の内容を変更 2 3 4 文2, 4どちらの値か 実行しないとわからない 5

11 イディオムの抽出 ソースコードからPDGを構築 PDGの集合から頻出部分グラフを抽出 頻出部分グラフをグラフパターンとよぶ
グラフパターンとみなす最小のノード数を設定 頻出部分グラフをグラフパターンとよぶ グラフパターンはソースコード上でイディオムに対応 --- - -- ------ ＰＤＧの構築 頻出部分グラフの抽出 --- - -- ------ --- - -- ------ ここなおす！！！タイトルおかしないか？ 流れの説明 このようの構築したPDGからうんたらかんたら 入力には閾値をむにゃむにゃ ソースコード PDG グラフパターン

12 欠陥候補の検出: グラフパターンの変種 あるグラフパターンに対し，その部分グラフをグラフパターンの変種(Variants)と呼ぶ
1つのグラフパターンに対し、複数の変種が存在し得る PDGにグラフパターンが出現するならば、その変種が必ず出現する その逆は真ではない PDGに変種が出現しても、そのグラフパターンが出現するとは限らない 部分グラフ

13 欠陥候補の検出: 欠陥の可能性が高い変種 多数のPDGで出現するグラフパターンについて
文が欠落 パターンが出現 = 変種も出現 緑のところもなんか適当に微妙に変えようぜ

14 欠陥候補の検出: パターン違反(1/2) C = 相関ルール(association rule)の確信度Cを用いる
相関ルール　P1⇒P2 グラフパターンP1, P2について, あるPDG中でP1が出現するとき，P2も出現するというルール 確信度C: P1が出現するとき，P2も出現する条件付確率 P1, P2ともに出現するPDGの数 C = P1の出現するPDGの数 パターンが出現 = 変種も出現

15 欠陥候補の検出: パターン違反(2/2) C = 確信度Cが1.0でなく，ある閾値以上であればパターン違反として検出
閾値は任意に設定 P1, P2ともに出現するPDGの数 C = P1の出現するPDGの数 P2 P1 P2が出現するPDGの集合 P1が出現するPDGの集合 P1が変種なんやから，1.0ちゅうことは変種の定義によりやな パターン違反

16 使用例 提案手法のツールを試作し、MASUを対象に実験 欠落
100574行, 4345メソッド, 最小ノード数: 5, 最小確信度: 0.9 パターン:893, 欠陥候補: 27 if (this.alreadyResolved()) { return this.getResolved(); } /* 省略 */ final int fromLine = getFromLine(); final int fromColumn = getFromColumn(); Class: UnresolvedBinominalOperationInfo Method: resolve() 欠落 MetricsToolSecurityManager.getInstance().checkAccess(); if ((null == usingClass) || (null == usingMethod) || (null == classInfoManager) || (null == methodInfoManager)) { throw new NullPointerException(); } if (this.alreadyResolved()) { return this.getResolved(); /* 省略 */ final int fromLine = getFromLine(); final int fromColumn = getFromColumn(); Class: UnresolvedCatchBlockInfo 他13箇所 Method: resolve()

17 評価実験計画(1/2) 手法の有効性を評価するため実験を行う 以下の2点で評価 オープンソース・プロジェクトのリポジトリを対象
欠陥が修正されたと考えられるリビジョン(revN)を検出 コミットログを参考 Bugzillaを利用 revNとその直前のリビジョンrevN-1に対し手法を適用 revN-1でのパターン違反がrevNでパターンになっているか調査 以下の2点で評価 修正された欠陥をどれだけ検出できるか(再現率) 欠陥候補に対する欠陥の割合(適合率) 丁寧に！井岡くんに説明した感じで！

18 評価実験計画(2/2) revN-1 revN 修正

19 まとめと今後の課題 まとめ 今後の課題 イディオムの誤実装をすることがある PDGをもとに欠陥の候補を自動的に検出する手法を提案した
ツールを試作し、ソフトウェアに適用したところ欠陥を発見できた 今後の課題 手法の評価 PDGの軽量化 PDGの計算コストは非常に高い 検出結果のランキング・フィルタリング手法 他の検出手法(ツール)との検出結果の比較 ashunotukurikata