プログラム理解におけるThin sliceの 統計的調査による有用性評価

Presentation on theme: "プログラム理解におけるThin sliceの 統計的調査による有用性評価"— Presentation transcript:

1 プログラム理解におけるThin sliceの 統計的調査による有用性評価
井上研究室 秦野 智臣　 それでは，プログラム理解におけるThin sliceの統計的調査による有用性評価というテーマで発表します． 井上研，秦野です．

2 背景 ソフトウェアの保守作業において，開発者はプログラム理解に多くの時間を費やしている
変数の値を調べる メソッドの呼び出し関係を調べる プログラム理解の時間を減らすための技術として，プログラムスライシングがある まず，本研究の背景について説明します． ソフトウェアの保守作業において，開発者はプログラム理解に多くの時間を費やしていると言われています． プログラム理解は，変数の値を調べたり，メソッドの呼び出し関係を調べたりすることが主な作業です． このプログラム理解の時間を減らすための技術として，プログラムスライシングという手法が存在します． このプログラムスライシングについて簡単に説明します．

3 プログラムスライシング プログラム内のある文に影響を与える可能性のあるすべての文を抽出する技術 ソースコード 1 void main() {
2 int sum = 0; 3 int i = 1; 4 while (i <= 10) { sum = sum + i; i = i + 1; 7 } 8 print(i); 　　9 } プログラムスライス 1 void main() { 3 int i = 1; 4 while (i <= 10) { i = i + 1; 7 } 8 print(i); 　　9 } スライシング プログラムスライシングは，プログラム内のある文に影響を与える可能性のあるすべての文を抽出する技術です． 例えば，このようなソースコードがある場合に，8行目の文print(i)の変数iの値に影響を与える可能性のある文を抽出すると，このようになります（アニメーション）． この抽出された文の集合をプログラムスライスといいます．そして，この8行目の変数iのように，プログラムスライシングの基点となる文のことをスライシング基準といいます． このように，例えば8行目で使用する変数iの値について調べたい場合にプログラムスライシングを利用すると，開発者が読む必要のあるコードを減らすことができます． また，開発者の負担を減らすため，プログラムスライスはできるだけ少ないほうが良いことになります． 8行目の変数iの値を知りたい場合 に開発者の読むコードが減少 スライシング基準

4 プログラムスライスの平均値 プログラムスライスのサイズの平均値は，プログラム内のすべての文の約３０％である[1]
100万行のプログラムのある文について，プログラムスライシングを実行しても，平均約30万行は残る 大規模プログラムではスライスサイズが大きくなってしまう このプログラムスライシングで，どのくらいの文が平均して抽出されるのかを調査した研究があります． この研究では，プログラムスライスのサイズの平均値はプログラム内のすべての文の約３０％であることを示しています． これは，例えば，100万行あるプログラムのある文について，プログラムスライシングを利用しても，平均で約３０万行は残ってしまうということです． このように，大規模プログラムではスライスサイズが大きくなってしまうため，プログラム理解に有用であるとは言い難い状況となっています．そこで， --メモ スライスサイズ プログラム理解に有用であるとは言い難い [1] D. Binkley, N. Gold, and M. Harman. An empirical study of static program slice size. ACM Trans. Softw. Eng. Methodol., Vol. 16, No. 2, pp. 1-32,

5 Thin slicing[2] プログラム内のある文で使用しているデータについて，そのデータを生成した文のみを抽出する技術
変数の値を計算したり，コピーしている文 変数の値に着目し抽出される文を少なくする プログラム理解に対する効果が期待できる Thin slicingを利用して，プログラム理解の時間が大きく減少した例が22個示されている[2] この問題を解決するために，Thin slicingが提案されています． Thin slicingは，ある文で使用しているデータについて，そのデータを生成した文のみを抽出するスライシング技術です． データを生成した文とは，変数の値を計算したり，コピーしている文のことを指します． Thin slicingは変数の値に注目して抽出される文を減らすため，プログラム理解に対する効果が期待できます． 実際に，Thin slicingを利用することによって，プログラム理解の時間が大きく減少した例が22個，提案元の論文にて示されています． [2]M. Sridharan, S. J. Fink, and R. Bodik. Thin slicing. In Proceedings of the 2007 ACM SIGPLAN Conference on PLDI, pp. 112–122., 2007.

6 Thin sliceの効果が高い例 1 package sample; 2 public class Main {
3 public static void main(String[] args) { A a = new A(); int id; if (args.length > 0) id = 1; else id = 0; a.addData( ); System.out.println( ); 12 } 13 } 14 class A { 15 B b = new B(); 16 void addData(int id) { b.addData( ); 18 } 19 } 20 class B { 21 int max = 4; 22 X x = new X(); 23 void addData(int id) { if (id >= 0 && id <= max) x.addData( ); 26 } 27 } 28 class Data { 29 int[] idList = new int[16]; 30 int count = 0; 31 void addData(int id) { idList[count++] = ; 33 } 34 } id id a id Thin slicingの効果が高い例について説明します．この例の32行目で使用する変数idの値について調べたい場合に，ここを基準に，まず，通常のスライシングを利用すると このようになります（フェードアウト）．このように，抽出される文が多いため，変数idの値が何なのかはすぐに分かりません． id Thin sliceの効果が高い例 メソッドの呼び出し関係 Main#main⇒A#addData⇒B#addData⇒Data#addData

7 この部分だけを見れば変数idの値が分かる
1 package sample; 2 public class Main { 3 public static void main(String[] args) { A a = new A(); int id; if (args.length > 0) id = 1; else id = 0; a.addData( ); System.out.println( ); 12 } 13 } 14 class A { 15 B b = new B(); 16 void addData(int id) { b.addData( ); 18 } 19 } 20 class B { 21 int max = 4; 22 X x = new X(); 23 void addData(int id) { if (id >= 0 && id <= max) x.addData( ); 26 } 27 } 28 class Data { 29 int[] idList = new int[16]; 30 int count = 0; 31 void addData(int id) { idList[count++] = ; 33 } 34 } id id a この部分だけを見れば変数idの値が分かる id 次に，Thin slicingの場合は，この変数idの値を生成している文のみを抽出するので，抽出される文はこのようになります（フェードアウト）． 通常のスライシングの場合と比べて，抽出される文が大幅に減っていることが分かります．さらに，Thin sliceの計算のようすをグラフで表すとこのようになります． このグラフの頂点は，プログラムの各文に対応していて，この数字はその行番号を表しています．また，この有向辺はデータの流れを表していて，たとえばこの場合は，25行目の文から32行目の文にデータが渡されることを意味しています．Thin sliceは，スライシング基準に相当する頂点から有向辺を後ろ向きに たどることによって計算します．このとき，グラフをたどった先のこの部分だけを見れば， 32行目で使用する値が0あるいは1であるということが分かります．このように使用している変数の値に注目したい場合に，Thin slicingの効果は高いと考えられます．しかし， 7 id 10 17 25 32 データの生成元 9 文を頂点としたグラフで Thin sliceを計算する

8 Thin sliceの効果が低い例 1 package sample; 2 public class Main {
3 public static void main(String[] args) { A a = new A(); int id; if (args.length > 0) id = 1; else id = 0; a.addData( ); System.out.println( ); 12 } 13 } 14 class A { 15 B b = new B(); 16 void addData(int id) { b.addData( ); 18 } 19 } 20 class B { 21 int max = 4; 22 X x = new X(); 23 void addData(int id) { if (id >= 0 && id <= max) x.addData( ); 26 } 27 } 28 class Data { 29 int[] idList = new int[16]; 30 int count = 0; 31 void addData(int id) { idList[count++] = ; 33 } 34 } id 同じメソッド内で使用 id a id この同じサンプルの11行目の変数aの値を調べたい場合は，Thin slicingを利用しなくても，ソースコードを見れば4行目で生成した値を使用していることがすぐに分かるため，Thin slicingの効果は低いと考えられます． このように，Thin slicingの効果が高い例と低い例が考えられますが，Thin slicingの提案元の論文では，効果が高い少数の例が紹介されているだけとなっています．そのため， Thin sliceの効果が低い例 id メソッドの呼び出し関係 Main#main⇒A#addData⇒B#addData⇒Data#addData

9 研究目的と方法 目的 方法 プログラム理解におけるThin slicingの有用性を評価する
Thin sliceのサイズは平均的に十分小さくなるか Thin sliceはプログラム理解において，どれくらい効果の高いものであるか 方法 Javaを対象としたThin slicingを実装し，7個のプログラムでThin sliceに関する指標を計測する 本研究では，プログラム理解におけるThin slicingの有用性を評価します． 有用性は，この2つのことを調査することによって評価します． 1つ目は，Thin sliceのサイズが平均的に十分小さくなるかどうかを調査します，（これは通常のスライスサイズの平均が全体の約30％であるのに対して，Thin sliceの場合はどうなるのかを調査します．） 2つ目は，Thin sliceはプログラム理解において，どれくらい効果の高いものであるかを調査します． このような調査を行うために，Javaプログラムを対象としたThin slicingを実装し，7個のプログラムに適用します．そして，Thin sliceに関する指標を計測します．

10 実験対象 DaCapo benchmark 多数のJavaプログラムが含まれている プログラム名 クラス数 メソッド数 頂点数
スライシング基準数 tomcat 261 2,389 54,468 12,120 luindex 560 4,180 123,191 23,554 sunflow 657 4,609 190,526 32,996 avrora 1,838 9,304 211,343 36,325 pmd 2,369 16,439 448,722 86,904 xalan 2,805 22,377 815,861 124,232 batik 4,417 28,818 968,470 149,169 実験対象は，多数のJavaプログラムが含まれているDaCapo benchmarkです．今回対象とする各プログラムの規模は，この表のようになっています．このように，大規模プログラムの多くのスライシング基準についてThin sliceを計算します．

11 計測する指標 Thin sliceのサイズを計算するため Thin sliceのプログラム理解に対する効果を調査するため
値が小さい⇒抽出される文が少ない Thin sliceのプログラム理解に対する効果を調査するため Thin sliceがまたがるメソッド数 値が大きい⇒データが多くのメソッドを経由する Thin sliceのうちデータの生成元に相当する頂点数 値が小さい⇒データの生成元の数が少ない 本実験で計測する指標はこの3つです． 1つ目は，Thin sliceに含まれる頂点数です．これは，Thin sliceのサイズを計算するための指標です． 2つ目は，Thin sliceのうち，データの生成元に相当する頂点数です． 3つ目は，Thin sliceがまたがるメソッド数です．（この2つの指標はメソッド呼び出しにおけるThin sliceのプログラム理解に対する効果を調査するための指標です．） この２つの指標を計測するのは，先ほど紹介したThin sliceの効果が高い例のように，Thin sliceは多くのメソッドにまたがる場合に効果が高いと考えられるためです． また，Thin sliceが多くのメソッドにまたがる場合にデータの生成元が少数に特定できれば，Thin sliceはより効果が高いと考えられます． これらの指標を，データを使用しているすべての 頂点をスライシング基準として計測する

12 実験結果(1/3) Thin sliceの頂点数の平均は，プログラム全体の約1％

13 実験結果(2/3) ・データの生成元の数がその最大値手前である Thin sliceが約10～20％
・残りの80％以上はデータの生成元の数が 少ない範囲に分布（この範囲内に着目） 最大値

14 実験結果(3/3) 全Thin sliceの約半分について，データの生成元の数が6以下である
さらに，データの生成元が6以下のThin sliceが全スライスの約50％を占めており，そのうち，Thin sliceが複数のメソッドにまたがるものが全スライスの約30％であることが分かりました．

15 考察 Thin sliceのサイズは平均的に十分小さいと言える
データを使用している場所のうち約30％で，メソッド呼び出しをたどってデータの生成元を探す作業の簡略化が期待できる 全Thin sliceの約半分でデータの生成元の数が少なく，うち約60％が複数のメソッドにまたがる この結果からThin sliceについて考えられることは，まず，Thin sliceのサイズは平均的に十分小さくなるということです． これは，通常のスライスの平均サイズが約30％であるのに対して，Thin sliceの平均サイズは約1％であることから考えれます． また，データを使用している場所のうち約30％で，メソッドの呼び出し関係をたどってデータの生成元を探す作業の簡略化が期待できます． これは，約30％のThin sliceが複数のメソッドにまたがり，かつデータの生成元も少ないことから考えられます．

16 まとめ Thin sliceに関する指標を計測し，プログラム理解における有用性を評価した 今後の応用
データの使用場所の約30％で，データの生成元をたどる作業の簡略化が期待できる 今後の応用 Thin sliceを利用したプログラム理解支援ツールの作成 実際のソフトウェア開発でThin sliceを利用する 本研究では，Thin sliceに関する指標を計測し，プログラム理解における有用性を評価しました． その結果，Thin sliceのサイズは平均的に十分小さくなることを確認しました． また，約30％の場面で，メソッドの呼び出し関係をたどってデータの生成元を調査する作業を簡略化でき，プログラム理解に利用することが期待できます． 今後の応用としては，Thin sliceを利用したプログラム理解の支援ツールを作成し，ソフトウェア開発において実際にThin slicingを利用することが考えられます．