オブジェクトの動作の比較を用いた実行履歴削減手法

蓄積されたオブジェクトの動作履歴を用いた
実行履歴削減手法の提案
博士前期課程 2年
コンピュータサイエンス専攻
井上研究室脇阪大輝
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
背景
プログラム利用者のもとで障害が発生したとき
障害の生じた実行についての情報を収集
障害をデバッグ環境で再現し，原因となる欠陥を修正
障害の再現のためには，実行履歴が用いられることもある
実行履歴
修正
2
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
実行履歴
実行履歴には様々な形式があるが，詳細なものには，
全てのメソッド呼出しやフィールドの読書きの発生が具体的な値とともに含まれる
EventId=12,EventType=8,ThreadId=1,LocationId=240
EventId=13,EventType=9,ThreadId=1,LocationId=240,dataTypeId=12,paramIndex=0,value=2
EventId=14,EventType=1,ThreadId=1,LocationId=232
EventId=15,EventType=2,ThreadId=1,LocationId=232,dataTypeId=12,paramIndex=0,value=2
EventId=16,EventType=17,ThreadId=1,LocationId=233,dataTypeId=12,value=2
EventId=17,EventType=19,ThreadId=1,LocationId=233,dataType=int,value=0
EventId=18,EventType=3,ThreadId=1,LocationId=234,dataType=int,value=1
EventId=19,EventType=11,ThreadId=1,LocationId=240,dataType=boolean,value=true
EventId=20,EventType=8,ThreadId=1,LocationId=241
EventId=21,EventType=9,ThreadId=1,LocationId=241,dataTypeId=12,paramIndex=0,value=2
EventId=22,EventType=9,ThreadId=1,LocationId=241,dataType=int,paramIndex=1,value=1
EventId=23,EventType=1,ThreadId=1,LocationId=216
EventId=24,EventType=2,ThreadId=1,LocationId=216,dataTypeId=12,paramIndex=0,value=2
EventId=25,EventType=2,ThreadId=1,LocationId=216,dataType=int,paramIndex=1,value=1
EventId=26,EventType=17,ThreadId=1,LocationId=217,dataTypeId=12,value=2
EventId=27,EventType=19,ThreadId=1,LocationId=217,dataTypeId=13,value=3
EventId=28,EventType=17,ThreadId=1,LocationId=218,dataTypeId=12,value=2
EventId=29,EventType=19,ThreadId=1,LocationId=218,dataType=int,value=0
EventId=30,EventType=25,ThreadId=1,LocationId=219,dataType=int,paramIndex=0,objectId=3,value=1
EventId=31,EventType=17,ThreadId=1,LocationId=220,dataTypeId=12,value=2
EventId=32,EventType=19,ThreadId=1,LocationId=220,dataType=int,value=0
EventId=33,EventType=20,ThreadId=1,LocationId=221,dataType=int,objectId=2,value=1
EventId=34,EventType=3,ThreadId=1,LocationId=222,dataType=void,value=void
EventId=35,EventType=11,ThreadId=1,LocationId=241,dataType=null,value=null
EventId=36,EventType=18,ThreadId=1,LocationId=242
EventId=37,EventType=19,ThreadId=1,LocationId=242,dataTypeId=14,value=4
EventId=38,EventType=8,ThreadId=1,LocationId=243
EventId=39,EventType=9,ThreadId=1,LocationId=243,dataTypeId=12,paramIndex=0,value=2
EventId=40,EventType=1,ThreadId=1,LocationId=224
EventId=41,EventType=2,ThreadId=1,LocationId=224,dataTypeId=12,paramIndex=0,value=2
EventId=42,EventType=17,ThreadId=1,LocationId=225,dataTypeId=12,value=2
EventId=43,EventType=19,ThreadId=1,LocationId=225,dataType=int,value=1
EventId=44,EventType=20,ThreadId=1,LocationId=226,dataType=int,objectId=2,value=0
EventId=45,EventType=17,ThreadId=1,LocationId=227,dataTypeId=12,value=2
EventId=46,EventType=19,ThreadId=1,LocationId=227,dataTypeId=13,value=3
EventId=47,EventType=17,ThreadId=1,LocationId=228,dataTypeId=12,value=2
EventId=48,EventType=19,ThreadId=1,LocationId=228,dataType=int,value=0
EventId=49,EventType=23,ThreadId=1,LocationId=229,paramIndex=0,objectId=3
EventId=50,EventType=24,ThreadId=1,LocationId=229,dataType=int,value=1
EventId=51,EventType=3,ThreadId=1,LocationId=230,dataType=int,value=1
EventId=52,EventType=11,ThreadId=1,LocationId=243,dataType=int,value=1
EventId=53,EventType=8,ThreadId=1,LocationId=244
EventId=54,EventType=9,ThreadId=1,LocationId=244,dataTypeId=14,paramIndex=0,value=4
EventId=55,EventType=9,ThreadId=1,LocationId=244,dataType=int,paramIndex=1,value=1
EventId=56,EventType=11,ThreadId=1,LocationId=244,dataType=null,value=null
EventId=57,EventType=3,ThreadId=1,LocationId=245,dataType=void,value=void
メソッドpushの実行開始
class Stack {
パラメータ情報
public void push(int item){ フィールドstackの読込み
フィールドspの読込み
stack[sp] = item;
stackへの書込み
sp += 1;
フィールドspの読込み
フィールドspへの書込み
}
メソッドpushの実行終了
public int pop(){
sp -= 1;
return stack[sp];
}
}
メソッドpopの実行開始
パラメータ情報
フィールドspの読込み
フィールドspへの書込み
フィールドstackの読込み
stack要素の読込み
メソッドpopの実行終了
3
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
実行履歴を用いたデバッグ
Omniscient Debugging[1]
詳細な実行履歴を用いて，プログラムの実行における，
任意の時点での状態を再現する
開発者は実行履歴を用いてデバッグを行う
障害が生じたときのプログラムの実行を詳細に調査可能
障害の原因となった欠陥の特定を効率良く行える
[1]Bil Lewis. Debugging backwards in time.
In Proceedings of the 5th International Workshop on Automated Debugging(AADEBUG2003), pp.225-235 2003.
4
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
問題点
プログラムの詳細な実行履歴の量は膨大
プログラム実行環境のディスク容量を浪費する
プログラム利用者のもとで，
膨大な量の実行履歴を保存することは好ましくない
実行履歴
5
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
アプローチ
障害に関係しそうにない処理の履歴を記録しないこ
とで実行履歴の量を減らす
テスト環境で事前に確認されている動作は障害に関係
しない可能性が高い
オブジェクトを入力として受け取る動作のテストでは，
オブジェクトの取り得る状態を網羅することは困難[2]
事前の実行で確認されていない動作をしたオブジェクトが
入力として使用されている動作の実行履歴を記録する
[2]Hojun Jaygarl, Sunghun Kim, Tao Xie, and Carl K. Chang. Ocat: Object capturebased
automated testing. In Proceedings of the 19th International Symposium on
Software Testing and Analysis, ISSTA 2010, pp. 159–170, 2010.
6
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
提案手法概要
1. 事前にプログラムを実行しオブジェクトの動作を蓄積
2. 後のプログラムの実行ではメソッドの実行ごとに観測された
ことのない動作をしそうかを蓄積した記録を用いて判定
3. 事前の実行とは一致しない動作をしているオブジェクトが入
力となるメソッドの実行のみを詳細に記録
先の実行
オブジェクトごとの動作
比較
プログラム
後の実行
未知の振舞いと
考えられる
実行の履歴
7
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
オブジェクトの動作
オブジェクトの動作はオートマトンとして抽出する
入力はオブジェクトに対するメソッドの呼出し位置
同じメソッド呼出し位置を入力した後は全て同じ状態
1:Stack s;
2:while((i = read())!=null){
3: s.push(i);
4:}
5:
6:while(!s.isEmpty()){
7: sum += s.pop();
8:}
push#3
始めのループで
pushが2回以上呼出されたとき
isEmpty#6
push#3
pop#7
isEmpty#6
同じメソッド呼出し位置の繰り返しは
ループとして表現される
8
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
実行履歴を記録する対象
メソッドの実行開始時に以下のオブジェクトの動作を
比較する
事前の実行でメソッドの入力となったオブジェクトの動作
後の実行でメソッドの入力となっているオブジェクトの動作
動作比較
method(parameter)
method(parameter)
事前の動作と一致しない動作をするオブジェクトがあ
ればそのメソッドの実行を記録対象とする
後の実行になって初めて実行されたメソッドは無条件で記録対象とする
9
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
オブジェクトの動作の比較
プログラム実行中に出現したオブジェクトへのメソッド
呼出しを比較対象のオートマトンへ入力する
状態遷移が可能な間はオートマトンと一致
状態遷移ができなかったあとは不一致
push#3
isEmpty#6
push#3
pop#7
1. push#3
2. push#3
3. isEmpty#6
一致している動作
1. isEmpty#6
isEmpty#6
事前の実行で得られたオブジェクトの動作を表すオートマトン
一致していない動作
10
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
実行履歴の削減例(1/3)
1:String exp = argv[0];
2:Stack stack = new Stack();
3:for(int i=0;i<exp.length();i++){
4: char c = exp.charAt(i);
5: if(c==‘+’){
6: add(stack);
7: }else{
8: stack.push(Character.digit(c, 10));
9: }
10:}
11:System.out.println(stack.pop());
14:static private void add(Stack stack){
15: int a = stack.pop();
16: int b = stack.pop();
17: stack.push(b+a);
18:}
19:
逆ポーランド記法で与えられた数式を
スタックを用いて計算するプログラム
11
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
実行履歴の削減例(2/3)
1:String exp = argv[0];
2:Stack stack = new Stack();
3:for(int i=0;i<exp.length();i++){
4: char c = exp.charAt(i);
5: if(c==‘+’){
6: add(stack);
7: }else{
8: stack.push(Character.digit(c, 10));
9: }
10:}
11:System.out.println(stack.pop());
14:static private void add(Stack stack){
15: int a = stack.pop();
16: int b = stack.pop();
17: stack.push(b+a);
18:}
19:
push#8
pop#15
pop#16
push#17
push#8
pop#11
事前の実行では数式として”1 2 + ”が与えられるとする
12
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
実行履歴の削減例(3/3)
1:String exp = argv[0];
2:Stack stack = new Stack();
3:for(int i=0;i<exp.length();i++){
4: char c = exp.charAt(i);
5: if(c==‘+’){
6: add(stack);
7: }else{
8: stack.push(Character.digit(c, 10));
9: }
10:}
11:System.out.println(stack.pop());
14:static private void add(Stack stack){
15: int a = stack.pop();
16: int b = stack.pop();
17: stack.push(b+a);
18:}
19:
push#8
pop#15
pop#16
push#17
×
push#8
pop#11
後の実行では数式に”1 2 + 3 +”が与えられるとする
“3+”の計算のaddは実行履歴記録対象になる
13
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
実験1
目的
手法により実行履歴を削減できるかどうかを調査する
対象
DaCapoベンチマークのbatik，fop，luindex，pmd
– 様々なアプリケーションを実行できるベンチマークソフト
– オプションで実行の規模をsmall，default，largeから選択できる
» defaultは，イベント数にしてsmallの約4～80倍
手段
1. smallを事前の実行として用いオブジェクトの動作を蓄積する
2. defaultの実行履歴をどの程度削減できるかを調べる
14
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
実験2
目的
事前の実行とは異なる動作をしている部分の実行を，実行履
歴の記録対象とできているかを調べる
手段
smallでは観測されず，defaultでのみ観測される実行経路を
たどっているメソッド実行を，記録すべきメソッド実行とみなし，
それを実行履歴の記録対象にできているかを調査する
15
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
評価尺度
DEFAULT
DEAFULT
・・・defaultの全メソッド実行
RECORDED・・・記録対象となったメソッド実行
RECORDED
TARGET
TARGET
・・・記録すべきメソッド実行
評価尺度
意味
①DEFAULTに含まれるRECORDEDの割合
値が小さいほど，実行履歴が少なくて済む
②RECORDEDに含まれるTARGETの割合
値が大きいほど，無駄な記録が少ない
③TARGETに含まれるRECORDEDの割合
値が大きいほど，取りこぼしが少ない
16
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
結果 (1/2)
約20～60%の記録量になる
どのアプリでも必要のない記録対象が多い
記録すべきメソッド実行の多くを記録できるアプリもあ
る
batik
fop
luindex
pmd
①DEFAULT中に含まれる
RECORDEDの割合
26.3%
23.7%
58.6%
62.4%
②RECORDED中に含ま
れるTARGETの割合
約0%
約0%
0.5%
0.9%
③TARGET中に含まれる
RECORDEDの割合
18.5%
5.1%
97.1%
92.2%
17
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
結果 (2/2)
fopの取りこぼしたメソッド実行のほとんどが
オブジェクトが入力とならないメソッドのもの
オブジェクト以外の引数の値による振舞いの変化は，
テストで事前に網羅することが容易
batik
fop
luindex
pmd
①DEFAULT中に含まれる
RECORDEDの割合
26.3%
23.7%
58.6%
62.4%
②RECORDED中に含ま
れるTARGETの割合
約0%
約0%
0.5%
0.9%
③TARGET中に含まれる
RECORDEDの割合
18.5%
5.1%
97.1%
92.2%
18
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
まとめと今後の課題
まとめ
本研究では，事前に蓄積したオブジェクトの動作履歴を
用いることによって，障害を再現するための実行履歴の
量を削減する手法を提案し，評価実験を行った
実験では，実行履歴が2割～6割ほどの量になることを
確認した
今後の課題
実行履歴が削減されないアプリケーションの特徴調査
手法によるオーバーヘッドの計測
19
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Download Report