プログラム依存グラフの一貫性検査に
基づく欠陥候補の検出手法
○山田 吾郎(阪大), 吉田 則裕(奈良先端大),
井上 克郎(阪大)
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
関連研究
欠陥の自動検出に関連する2つの研究を紹介
PR-Miner
[1]
メソッド内で同時に出現することの多い
メソッド呼び出し文の集合
イディオム
close()
read()
open()
誤実装
open(c);
open(c);
read(c);
:
read(c);
誤実装
JADET
[2]
オブジェクトの使い方を
表すグラフ
イディオム
f.close()
f.read()
誤実装
f.open(“?”);
f.read();
g.close();
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
3
関連研究: PR-Miner
イディオムの抽出
ソースコード中のメソッド内の文の集合にアイテムセットマイニ
ングを適用
順序を持たない集合の集合から、頻出する部分集合を抽出する手法
欠陥の検出
抽出した頻出部分集合と、そのサブセットの出現数を比較
サブセットのみ出現するメソッドが少数であれば、欠陥の候補
とする
read(b);
read(a);
read(a);
open(a);
read(b);
open(a); :
open(b);
:
open(a);:
read(a);
close(a);
:
close(a);
:
:
read(a);
close(a); open(a);
:
:
close(a);
read(a);
マ
イ
ニ
ン
グ
close()
read()
open()
出
現
比
の
計
算
:
:
:
:
open(a);
open(a);
open(a);
read(a);
:
:
:
:
close(a);
close(a);
close(a);
close(a);
open(d);
:
read(d);
4
1
4
関連研究: JADET
イディオムの抽出
1つのオブジェクトに着目し、その使い方をグラフ化
頂点はラベルなし、辺のラベルが文
頻出する部分グラフがイディオム
欠陥の検出
頻出する部分グラフとほとんど同じであるが、一部が欠落し
ているものが少数であれば、欠陥の候補とする
public Hoge getHoge(){
Hoge result = new Hoge();
for (int i=0; i<3; i++){
result.add(i);
}
return result;
}
<enter>
result<init>
<exit>
result.add(i)
5
関連研究: 問題と解決方法
イディオムのモデル化の段階で情報を削る
制御構造
文の順序
データ依存関係
誤検出の割合が高くなる
検出できない欠陥が増える
プログラムの文の間に生じる関係を多く取得すれば、より高精度に
欠陥を検出できるのではないか？
6
提案手法
---------- -- -------------------------------------------------------
ソースコード
イ
デ
ィ
オ
ム
の
抽
出
Ｐ
Ｄ
Ｇ
の
構
築
違
反
の
検
出
PDG
イディオムの抽出の対象はプログラム依存グラフ
(Program Dependence Graph)
文間の依存関係を表現したグラフ
イディオムはPDG上で頻出部分グラフとして現れる
PDGを用いることで違反の原因を細かく特定できる
7
プログラム依存グラフ
プログラム依存グラフ(Program Dependence Graph)とは
プログラム中の文の間における関係を表現した有向グラフ
グラフの構成要素
頂点: プログラムの文・条件式
辺: データ依存関係・制御依存関係
1:
2:
3:
4:
5:
int i = 0;
i = method();
if ( i > 0)
..i = x;
y = i;
1
2
3
4
5
8
プログラム依存グラフ: 制御依存辺
ある文と、その文が実行されるか決定する文の間の関
係
2つの文 S, T 間で2つの関係が成立
S が条件文
T が実行されるかどうかは、Ｓ の判定結果に依存
1:
2:
3:
4:
5:
int i = 0;
i = method();
if ( i > 0)
..i = x;
y = i;
1
2
3
4
5
9
プログラム依存グラフ: データ依存辺
ある変数が参照される文と、その変数が定義された文の
間の関係
2つの文 S, T 間で変数 v に関する3つの関係が成立
S で v が定義される
T で v が参照される
S から T へ途中で変数 v を再定義している文が存在しない経
路が存在
1:
2:
3:
4:
5:
int i = 0;
i = method();
if ( i > 0)
..i = x;
y = i;
文2, 4どちらの値か
実行しないとわからない
文1の内容を変更
1
2
3
4
5
10
イディオムの抽出
ソースコードからPDGを構築
PDGの集合から頻出部分グラフを抽出
グラフパターンとみなす最小のノード数を設定
頻出部分グラフをグラフパターンとよぶ
グラフパターンはソースコード上でイディオムに対応
----------- -------- ------- ------------------------------------------
ソースコード
Ｐ
Ｄ
Ｇ
の
構
築
PDG
頻
出
部
分
グ
ラ
フ
の
抽
出
グラフパターン
欠陥候補の検出: グラフパターンの変種
あるグラフパターンに対し，その部分グラフをグラフパ
ターンの変種(Variants)と呼ぶ
1つのグラフパターンに対し、複数の変種が存在し得る
部分グラフ
PDGにグラフパターンが出現するならば、その変種が
必ず出現する
その逆は真ではない
PDGに変種が出現しても、そのグラフパターンが出現するとは限らな
い
12
欠陥候補の検出: 欠陥の可能性が高い変種
多数のPDGで出現するグラフパターンについて
変種のみ出現するPDGが少数の場合，欠陥の可能性
が高い
文が欠落
パターンが出現 = 変種も出現
13
欠陥候補の検出: パターン違反(1/2)
相関ルール(association rule)の確信度Cを用いる
相関ルール P1⇒P2
グラフパターンP1, P2について, あるPDG中でP1が出現するとき，P2
も出現するというルール
確信度C: P1が出現するとき，P2も出現する条件付確率
C=
P1, P2ともに出現するPDGの数
P1の出現するPDGの数
パターンが出現 = 変種も出現
14
欠陥候補の検出: パターン違反(2/2)
確信度Cが1.0でなく，ある閾値以上であればパターン
違反として検出
閾値は任意に設定
C=
P1, P2ともに出現するPDGの数
P1の出現するPDGの数
P1が出現する
PDGの集合
P1
P2
P2が出現する
PDGの集合
パターン違反
15
使用例
提案手法のツールを試作し、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()) {
Class:
return this.getResolved();
UnresolvedCatchBlockInfo 他13箇所
}
/* 省略 */
final int fromLine = getFromLine();
Method:
final int fromColumn = getFromColumn(); resolve()
16
評価実験計画(1/2)
手法の有効性を評価するため実験を行う
オープンソース・プロジェクトのリポジトリを対象
欠陥が修正されたと考えられるリビジョン(revN)を検出
コミットログを参考
Bugzillaを利用
revNとその直前のリビジョンrevN-1に対し手法を適用
revN-1でのパターン違反がrevNでパターンになっているか調
査
以下の2点で評価
修正された欠陥をどれだけ検出できるか(再現率)
欠陥候補に対する欠陥の割合(適合率)
17
評価実験計画(2/2)
revN-1
修正
revN
18
まとめと今後の課題
まとめ
イディオムの誤実装をすることがある
PDGをもとに欠陥の候補を自動的に検出する手法を提案し
た
ツールを試作し、ソフトウェアに適用したところ欠陥を発見で
きた
今後の課題
手法の評価
PDGの軽量化
PDGの計算コストは非常に高い
検出結果のランキング・フィルタリング手法
他の検出手法(ツール)との検出結果の比較
19
© Copyright 2024 ExpyDoc
