蓄積されたオブジェクトの動作履歴を用いた 実行履歴削減手法の提案 博士前期課程 2年 コンピュータサイエンス専攻 井上研究室　脇阪 大輝

背景 プログラム利用者のもとで障害が発生したとき 障害の生じた実行についての情報を収集 障害をデバッグ環境で再現し，原因となる欠陥を修正 障害の再現のためには，実行履歴が用いられることもある 実行履歴 修正

実行履歴 実行履歴には様々な形式があるが，詳細なものには， 全てのメソッド呼出しやフィールドの読書きの発生が具体的な値とともに含まれる 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の実行開始 パラメータ情報 フィールドstackの読込み フィールドspの読込み stackへの書込み フィールドspへの書込み メソッドpushの実行終了 class Stack { public void push(int item){ stack[sp] = item; sp += 1; } public int pop(){ sp -= 1; return stack[sp]; メソッドpopの実行開始 パラメータ情報 フィールドspの読込み フィールドspへの書込み フィールドstackの読込み stack要素の読込み メソッドpopの実行終了

実行履歴を用いたデバッグ 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.

問題点 プログラムの詳細な実行履歴の量は膨大 プログラム実行環境のディスク容量を浪費する プログラム利用者のもとで， 膨大な量の実行履歴を保存することは好ましくない 実行履歴

アプローチ 障害に関係しそうにない処理の履歴を記録しないことで実行履歴の量を減らす テスト環境で事前に確認されている動作は障害に関係しない可能性が高い オブジェクトを入力として受け取る動作のテストでは， 　オブジェクトの取り得る状態を網羅することは困難[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.

提案手法 概要 事前にプログラムを実行しオブジェクトの動作を蓄積 提案手法　概要 事前にプログラムを実行しオブジェクトの動作を蓄積 後のプログラムの実行ではメソッドの実行ごとに観測されたことのない動作をしそうかを蓄積した記録を用いて判定 事前の実行とは一致しない動作をしているオブジェクトが入力となるメソッドの実行のみを詳細に記録 先の実行 オブジェクトごとの動作 比較 未知の振舞いと 考えられる 実行の履歴 プログラム 後の実行

オブジェクトの動作 オブジェクトの動作はオートマトンとして抽出する 入力はオブジェクトに対するメソッドの呼出し位置 同じメソッド呼出し位置を入力した後は全て同じ状態 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 isEmpty#6 pop#7 始めのループで pushが2回以上呼出されたとき 同じメソッド呼出し位置の繰り返しは ループとして表現される

実行履歴を記録する対象 メソッドの実行開始時に以下のオブジェクトの動作を比較する 事前の動作と一致しない動作をするオブジェクトがあればそのメソッドの実行を記録対象とする 事前の実行でメソッドの入力となったオブジェクトの動作 後の実行でメソッドの入力となっているオブジェクトの動作 動作比較 ？ method(parameter) method(parameter) 後の実行になって初めて 実行されたメソッドは無条件で記録対象とする

オブジェクトの動作の比較 プログラム実行中に出現したオブジェクトへのメソッド呼出しを比較対象のオートマトンへ入力する 状態遷移が可能な間はオートマトンと一致 状態遷移ができなかったあとは不一致 push#3 isEmpty#6 pop#7 1. push#3 2. push#3 3. isEmpty#6 一致している動作 1. isEmpty#6 事前の実行で得られたオブジェクトの動作を表すオートマトン 一致していない動作

実行履歴の削減例(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: 逆ポーランド記法で与えられた数式を スタックを用いて計算するプログラム

実行履歴の削減例(2/3) 事前の実行では数式として”1 2 + ”が与えられるとする 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) 後の実行では数式に”1 2 + 3 +”が与えられるとする “3+”の計算のaddは実行履歴記録対象になる × 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は実行履歴記録対象になる

実験1 目的 対象 手段 手法により実行履歴を削減できるかどうかを調査する DaCapoベンチマークのbatik，fop，luindex，pmd 様々なアプリケーションを実行できるベンチマークソフト オプションで実行の規模をsmall，default，largeから選択できる defaultは，イベント数にしてsmallの約4～80倍 手段 smallを事前の実行として用いオブジェクトの動作を蓄積する defaultの実行履歴をどの程度削減できるかを調べる

実験2 目的 手段 事前の実行とは異なる動作をしている部分の実行を，実行履歴の記録対象とできているかを調べる smallでは観測されず，defaultでのみ観測される実行経路をたどっているメソッド実行を，記録すべきメソッド実行とみなし，　それを実行履歴の記録対象にできているかを調査する

評価尺度 DEFAULT ・・・defaultの全メソッド実行 RECORDED・・・記録対象となったメソッド実行 DEAFULT RECORDED TARGET DEFAULT ・・・defaultの全メソッド実行 RECORDED・・・記録対象となったメソッド実行 TARGET ・・・記録すべきメソッド実行 評価尺度 意味 ①DEFAULTに含まれるRECORDEDの割合 値が小さいほど，実行履歴が少なくて済む ②RECORDEDに含まれるTARGETの割合 値が大きいほど，無駄な記録が少ない ③TARGETに含まれるRECORDEDの割合 値が大きいほど，取りこぼしが少ない

結果 (1/2) 約20～60%の記録量になる どのアプリでも必要のない記録対象が多い 記録すべきメソッド実行の多くを記録できるアプリもある batik fop luindex pmd ①DEFAULT中に含まれるRECORDEDの割合 26.3% 23.7% 58.6% 62.4% ②RECORDED中に含まれるTARGETの割合 約0% 0.5% 0.9% ③TARGET中に含まれるRECORDEDの割合 18.5% 5.1% 97.1% 92.2%

結果 (2/2) fopの取りこぼしたメソッド実行のほとんどが オブジェクトが入力とならないメソッドのもの オブジェクト以外の引数の値による振舞いの変化は， テストで事前に網羅することが容易 batik fop luindex pmd ①DEFAULT中に含まれるRECORDEDの割合 26.3% 23.7% 58.6% 62.4% ②RECORDED中に含まれるTARGETの割合 約0% 0.5% 0.9% ③TARGET中に含まれるRECORDEDの割合 18.5% 5.1% 97.1% 92.2%

まとめと今後の課題 まとめ 本研究では，事前に蓄積したオブジェクトの動作履歴を用いることによって，障害を再現するための実行履歴の量を削減する手法を提案し，評価実験を行った 実験では，実行履歴が2割～6割ほどの量になることを確認した 今後の課題 実行履歴が削減されないアプリケーションの特徴調査 手法によるオーバーヘッドの計測