スライド 1

Angelic Debugging
東京工業大学権藤研究室 10M38102 栗田剛
1
Angelic Debugging
目的: バクの可能性がある場所（修正候補）の特定
「 Angelic Debugging 」では修正候補を自動計算する



ここで自動計算するのは「構文」ではなく「値」



正しい構文を考えるのはコストが高い
（正しく動作するのに必要な）正しい値を計算する方が容易
テストが通る値が見つかった時、その式を修正候補とする

「式」は「値」を導出するため、「（エラーを起こす）式から導出される
値」の代わりに「正しい値」が分かれば、その式を直すべきとわかる
この手法の特徴・利点




2
プログラマの労力が減る: コンピュータの性能に任せる
テストに使う入力をそのまま活用している
手法を自動化し、大小のJavaプログラムでテストした
Angelic Debuggingの詳細
次の手順によりバグの修正を行う

1.
（プログラマが）バグが含まれそうな箇所を特定する

2.
（コンピュータが）その箇所を検証する


3.
修正すると別のテストが通らなくなるような修正候補を除外
（プログラマが）修正候補に対して最適な式を考える


3
スコープ内の式すべてを計算し、もっともらしい修正候補を抽出
修正候補の箇所と同時に、テストを通すことができる値が得られる
（コンピュータが）修正候補を絞り込む

4.
その箇所を「スコープ」とし、その中に含まれる式が以下の対象
式をコンピュータが検索するのは計算空間的に厳しい
しかし2で得られる値が最適な式を考えるヒントになる
例 – 三角形の判定プログラムのバグ
1. 左のソースコードのもとで下中央の表のテストを実施
1 public int classify
(int a, int b, int c) {
2. T8で失敗したのでT8にAngelic Debuggingを実施
2
int retval;
3
if (a >= b && b >= c) {
• すると右下表の修正候補（代替値）が得られる
4
if (a == c || b == c) {
5
if (a == b && a == c)
3. 修正候補のうち、他のテストを阻害するものを計算
6
retval = EQUILATERAL;
7
else
• 表中の「阻害」が（正しい出力を）阻害されるテスト
8
retval = ISOSCELES;
9
} else {
4. 代替値を元に具体的なソースコードを考える
10
if (a*a != b*b + c*c) {
11
if (a*a < b*b + c*c) {
• 1つ目は「a」を「c」にすることになるので不適切
12
retval = ACUTE;
13
} else {
• 2つ目は「c」を「b」にできる→正しいコードに
14
retval = OBTUSE;
15
}
T
a
b
c
想定値
16
} else {
←表1: テストの入力値と想定値
T1
2 12 27 ILLEGAL
17
retval = RIGHT;
18
}
T2
5
4
3 RIGHT
↓表2: 修正候補と代替値など
19
}
T3
26 14 14 ISOSCELES
20
} else {
21
retval = ILLEGAL;
T4
19 19 19 EQUILATERAL
行コード
代替値(T8) 阻害
22
}
T5
9
6
4 OBTUSE
4 if (a == c || b == c) {
7
23
return retval;
24 }
4 if (a == c || b == c) {
26
T6
24 23 21 ACUTE
4
T7
7
5
6
ILLEGAL
4
if (a == c || b == c) {
7
T3
T8
26
26
7
ISOSCELES
4
if (a == c || b == c) {
26
T3
「ACUTE」が出力↑
12
ISOSCELES
T6
retval = ACUTE;
Angelic Debuggingの評価
「Zunebug」（改）と「JTopas」に含まれるバグで実験


「Zunebug」… (参考: http://winjade.net/2009/01/lesson-on-infinite-loops/)


このバグそのものはステートメントの追加と削除という2つの修正が
必要だが、今回はツールが「ステートメントの追加」に対応していな
いため改変
「JTopas」…10のバグが含まれるVer0.4を対象とする
結果…


Zunebugでは4つの修正候補を示す


その中の1つが本当の修正候補だが、他は見てそうでないとわかる
JTopasでは（数分で）4つのバグに対し正しく修正候補を示す

残りは「1箇所修正すれば直る」ではないものか、ツールの性能的（リ
ソース的）問題で示せず
→ デバッグのスピードアップに役立つ手法の一つとして有用
5
Static Extraction of Program
Configuration Options
ICSE2011 勉強会
東京工業大学
権藤研究室修士2年
荻原渓太
2011/07/05
2011/7/5
6
背景と目的
設定オプション
キー値モデルの例
SERVER_ADDRESS=192.168.10.1 SERVER_PORT=80
キー値モデルで起こる問題
• 使用しないオプションがドキュメントに記述
• 使用するオプションがドキュメントに未記述
目的
キー値モデルの弱点を静的解析で補う
2011/7/5
7
貢献内容
OSSのキー値モデルの使用法を明らかに
 7つのOSSを調査（合計で百万行超）
• オプションの種類は少数
• ドキュメントとプログラムの不整合がある
２つの静的解析の提案と評価
 プログラムが使用するオプションリストを出力
 オプションの種類を推測
7つのOSSの規模とオプション数
2011/7/5
8
オプションの発見
前提
 points-to, コールグラフ
 オプション API の情報
Ariel .R, Randy. K, Static extraction of program configuration options,
In ICSE, 2011
ドキュメントのエラー
アプローチ
 オプション操作の場所の発見
 その場所でオプションを発見
評価
解析で見つからなかったオプション
 ドキュメント内容と比較
• 不一致時は手動で確認
 解析の方が正確
2011/7/5
9
オプションの分類
11種類のタイプを認識
前提
Ariel .R, Randy. K, Static extraction of program configuration options,
In ICSE, 2011
手動での分類結果（全16種類）
 points-to, コールグラフ
 前の解析結果
アプローチ
 オプション操作の返り値の型
 設定値が渡されるメソッド
解析結果
 比較される値
評価
 手動での分類と比較
 精度は82%
2011/7/5
10
An Empirical Study of Build
Maintenance Effort
S. McIntosh, B. Adams, T. H. D. Nguyen, Y. Kamei, A. E. Hassen
東京工業大学大学院情報理工学研究科
計算工学専攻権藤研究室
修士2年川村恒星
2011/7/5
11
概要
ビルドはソフトウェア開発の中で重要なプロセスだが、
その手間については殆ど文書化されていない。
• 目的：各種ソフトウェアプロジェクトを調査し、開発
者がビルド管理に費やしている労力を解析する。
• 貢献
– 製品コード変更時にビルドコード変更も行う確率を解析
– 開発メンバー間でのビルド作業分担方法を解析
• 手法：リポジトリ解析を半自動で解析
– Build Coupling
• 製品コードの変更により、ビルド管理が必要となる頻度
• リビジョンレベル、作業単位レベルでの解析
– Build Ownership
• ビルド管理作業の分担の様子
2011/7/5
12
解析結果：Build Coupling
• リビジョンレベル
– 製品コードの変更とビルド管理との間に密接な関
係無し。
– 製品コードとビルドファイルの変更は同時にコミッ
トされないから。
• 作業単位レベル
表1：ソース/テストコードを変更した作業単位のうち、ビルド管理を含むものの割合
Eclipse
Jazz
Mozilla
ソースコード
16%
4%
27%
テストコード
20%
8%
44%
– EclipseとJazzのプロジェクトはIDE（PDE）によるビル
ドコード自動生成機能が効果を発揮。
2011/7/5
13
解析結果：Build Ownership
表2：開発者の作業分担
Jazz
Git
Linux
ソース開発者のうちビルド設定を変更
79%
22%
25%
ビルド管理者のうちソース開発
87%
85%
93%
テスト開発者のうちビルド設定を変更
89%
24%
58%
ビルド管理者のうちテスト開発
44%
23%
6%
• LinuxとGitでは集中型、Jazzでは分散型
– Jazzの場合は、そもそもビルド管理の頻度が少ない。
• オープンソースの場合は集中型が適していると
推測
• テスト開発者の多くがビルド設定も行う。
2011/7/5
14
まとめ
• ソースコードの変更に対し、
– Javaのプロジェクトは4～16%
– Cのプロジェクトは27%
の確率でビルド管理を伴う。
• テストコードの変更に対し、
– Javaのプロジェクトは8～20%
– Cのプロジェクトは44%
の確率でビルド管理を伴う。
• 各種ソフトウェアプロジェクトを解析した結果、
– ビルド管理方法として集中型、分散型がある。
– テスト開発者の多くがビルド設定も行う。
– 開発者個人のビルド管理の負担は限定的。
2011/7/5
15

Download Report