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

Slides:



Advertisements
Similar presentations
シーケンス図の生成のための実行履歴圧縮手法
Advertisements

XHTML構文検証手法における スクリプト要素の静的解析アルゴリズム
シーケンシャルパターンマイニングに基づくオブジェクト指向プログラムのための 欠陥検出手法
メソッド周辺の識別子と メソッド本体のAPI利用実績に基づいたAPI集合推薦手法
Myoungkyu Song and Eli Tilevich 発表者: 石尾 隆(大阪大学)
情報伝播によるオブジェクト指向プログラム理解支援の提案
変数間データフローグラフを用いた ソースコード間の移動支援
プログラムの動作を理解するための技術として
リファクタリングのための 変更波及解析を利用した テスト支援ツールの提案
メソッド名とその周辺の識別子の 相関ルールに基づくメソッド名変更支援手法
動的スライスを用いたバグ修正前後の実行系列の差分検出手法の提案
分散処理を用いた大規模ソフトウェアに対するコーディングパターン検出ツール
Java ソフトウェア部品検索システム SPARS-J のための リポジトリ自動更新機能の実現
ソースコードに対する適用可能な修正手順を 可視化するリファクタリング支援手法の提案
ソースコードの変更履歴における メトリクス値の変化を用いた ソフトウェアの特性分析
静的情報と動的情報を用いた プログラムスライス計算法
ギャップを含むコードクローンの フィルタリング手法の提案
Javaクラスの利用関係を用いた ソフトウェア部品のカテゴリ階層構築法
プログラム依存グラフを利用した 情報漏洩解析手法の提案と実現
コードクローンに含まれるメソッド呼び出しの 変更度合の分析
コードクローンに含まれるメソッド呼び出しの 変更度合の調査
識別子の共起関係に基づく類似コード検索法の提案と 欠陥検出への適用
動的スライスを用いた バグ修正前後の実行系列の比較
動的依存グラフの3-gramを用いた 実行トレースの比較手法
オブジェクト指向プログラムにおける エイリアス解析手法の提案と実現
動的スライスを用いたバグ修正前後の実行系列の差分検出手法
限られた保存領域を使用する Javaプログラムの実行トレース記録手法の 提案と評価
Javaプログラムの変更を支援する 影響波及解析システム
コードクローン検出ツールを用いた ソースコード分析システムの試作と プログラミング演習への適用
リファクタリング支援のための コードクローンに含まれる識別子の対応関係分析
動的データ依存関係解析を用いた Javaプログラムスライス手法
ソースコードの特徴量を用いた機械学習による メソッド抽出リファクタリング推薦手法
コードクローンの動作を比較するためのコードクローン周辺コードの解析
UMLモデルを対象とした リファクタリング候補検出の試み
Javaバイトコードの 動的依存解析情報を用いた スライシングシステムの実現
コードクローン検出に基づくデザイン パターン適用支援手法の提案と実現
バイトコードを単位とするJavaスライスシステムの試作
コードクローン編集者数に着目した開発履歴の分析
○ 後藤 祥1,吉田 則裕2 ,井岡 正和1 ,井上 克郎1 1大阪大学 2奈良先端科学技術大学院大学
パターンマイニング技術を 用いた実時間プログラムの コーディングパターン検出
コードクローンの理解支援を目的としたコードクローン周辺コードの解析
コードクローン分類の詳細化に基づく 集約パターンの提案と評価
Javaバーチャルマシンを利用した 動的依存関係解析手法の提案
コーディングパターンの あいまい検索の提案と実装
JAVAバイトコードにおける データ依存解析手法の提案と実装
JavaScriptを含んだHTML文書に対する データフロー解析を用いた構文検証手法の提案
コードクローン間の依存関係に基づく リファクタリング支援環境の実装
ソフトウェアプロダクト集合に対する 派生関係木の構築
オブジェクトの協調動作を用いた オブジェクト指向プログラム実行履歴分割手法
静的情報と動的情報を用いた Javaプログラムスライス計算法
プログラムスライスを用いた凝集度メトリクスに基づく 類似メソッド集約候補の順位付け手法
設計情報の再利用を目的とした UML図の自動推薦ツール
保守請負時を対象とした 労力見積のためのメトリクスの提案
dcNavi:デバッグ支援のための グラフベース推薦システム
オープンソースソフトウェアに対する コーディングパターン分析の適用
メソッドの同時更新履歴を用いたクラスの機能別分類法
分散処理を用いたコーディングパターン検出ツールの実装
蓄積されたオブジェクトの動作履歴を用いた 実行履歴削減手法の提案
欠陥検出を目的とした類似コード検索法 吉田則裕,石尾隆,松下誠,井上克郎 大阪大学 大学院情報科学研究科
エイリアス関係を考慮した Javaプログラム用静的スライシングツール
動的スライスを用いたバグ修正前後の実行系列の差分検出手法の提案
動的スライスを用いたバグ修正前後の実行系列の差分検出手法の提案
コードクローン解析に基づく デザインパターン適用候補の検出手法
回帰テストにおける実行系列の差分の効率的な検出手法
メソッド抽出リファクタリングが 行われるメソッドの特徴調査
オブジェクト指向言語における セキュリティ解析アルゴリズムの提案と実現
識別子の読解を目的とした名詞辞書の作成方法の一試案
プログラム依存グラフを用いた ソースコードのパターン違反検出法
Detecting Software Modularity Violations
Presentation transcript:

プログラム依存グラフの一貫性検査に基づく欠陥候補の検出手法 ○山田 吾郎(阪大), 吉田 則裕(奈良先端大), 井上 克郎(阪大)

背景 イディオムの違反を自動で検出したい イディオム イディオムの実装に誤り(違反)が生じ得る 特定の処理を実現するための実装のパターン[1] イディオムの実装に誤り(違反)が生じ得る 一部が欠落[2] 順序の誤り 識別子名の変更漏れ open(a); : read(a); close(a); open(b); : read(b); close(b); open(c); : read(c); close(c); open(d); : read(d); 開発者がプログラムを実装するにあたり、特定の操作を行いたいがために何度も同じ処理を記述します。たとえば図に挙げたファイル操作があります。 ふぃあるひらいてょげhごえほげ このような実装のパターンをイディオムと呼びます 熟練していないプログラマ 熟練したプログラマ イディオムの違反を自動で検出したい [1]石尾 隆ら. シーケンシャルパターンマイニングを用いたコーディングパターン抽出. 情報処理学会論文誌, 2009 [2]A. Wasylkowski et al., Detecting object usage anomalies. In Proc. of ESEC/FSE 2007, 2007

メソッド内で同時に出現することの多いメソッド呼び出し文の集合 関連研究 欠陥の自動検出に関連する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

関連研究: 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

関連研究: 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)

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

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

プログラム依存グラフ 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

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

プログラム依存グラフ: データ依存辺 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

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

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

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

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

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

使用例 提案手法のツールを試作し、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()

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

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

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