プログラムスライシング

コンピュータ プログラミングにおいて、プログラム スライシングとは、スライシング基準と呼ばれる、ある関心のあるポイントの値に影響を与える可能性のあるプログラム ステートメントのセット (プログラムスライス) を計算することです。プログラム スライシングは、デバッグでエラーの原因をより簡単に特定するために使用できます。スライシングの他の用途には、ソフトウェアのメンテナンス、最適化、プログラム分析、情報フロー制御などがあります。

スライシング技術は、マーク・ワイザーによる最初の定義以来、急速な発展を遂げてきました。当初、スライシングは静的なものであり、ソースコード以外の情報なしでソースコードに適用されていました。ボグダン・コレルとヤヌシュ・ラスキは、プログラムの特定の実行（特定の実行トレース）で機能する動的スライシングを導入しました。 ^[1]パススライシングなど、他の形式のスライシングも存在します。^[2]

^{Weiser の元の定義[3]}に基づき、非公式には、静的プログラム スライス S は、ステートメント x の変数 v の値に影響を与える可能性のあるプログラム P のすべてのステートメントで構成されます。スライスは、スライス基準 C=(x,v) に対して定義されます。ここで、x はプログラム P のステートメントで、v は x の変数です。静的スライスには、ステートメント x で、考えられるすべての入力に対して変数 v の値に影響を与える可能性のあるすべてのステートメントが含まれます。静的スライスは、ステートメント間の依存関係をバックトラックすることによって計算されます。具体的には、(x,v) の静的スライスを計算するには、まず、ステートメント x に遭遇する前に v の値に直接影響を与える可能性のあるすべてのステートメントを見つけます。再帰的に、ステートメント x の v の値に影響を与える可能性のある各ステートメント y について、v の値に影響を与える y のすべての変数 z のスライスを計算します。

たとえば、以下の C プログラムについて考えてみましょう。スライス ( write(sum), sum ) を計算してみましょう。 sum の値は、N>1 の場合は「sum = sum + i + w」ステートメント、N <= 1 の場合は「int sum = 0」ステートメントによって直接影響を受けます。したがって、slice( write(sum), sum) は、3 つのスライスと依存関係のない「int sum = 0」ステートメントの結合です。

1. スライス(合計 = 合計 + i + w, 合計),
2. スライス(合計 = 合計 + i + w, i),
3. スライス(合計 = 合計 + i + w, w)、および
4. { int 合計 = 0 }。

slice( sum = sum + i + w, sum) が "sum = sum + i + w" と "int sum = 0" で構成されていることは簡単にわかります。これは、これらが "sum = sum + i + w" での sum の値に影響を与えることができる唯一の 2 つの先行ステートメントだからです。同様に、slice( sum = sum + i + w, i) には "for(i = 1; i < N; ++i) {" のみが含まれ、slice( sum = sum + i + w, w) には "int w = 7" ステートメントのみが含まれます。

これらのステートメントをすべて結合すると、実行可能なコードがなくなるため、スライスを実行可能なスライスにするには、for ループの終了中括弧と i の宣言を追加するだけです。結果として得られる静的実行可能スライスは、以下の元のコードの下に示されています。

int i ; int sum = 0 ; int product = 1 ; int w = 7 ; for ( i = 1 ; i < N ; ++ i ) { sum = sum + i + w ; product = product * i ; } write ( sum ); write ( product ); 
   
   
   
       
        
      

基準 ( 、合計) の静的実行可能スライスは、write(sum)以下に示す新しいプログラムです。

int i ; int sum = 0 ; int w = 7 ; for ( i = 1 ; i < N ; ++ i ) { sum = sum + i + w ; 
   
   
       
        

}
書き込み(合計);

実際、Weiser 自身の手法を含むほとんどの静的スライス手法では、write(sum)ステートメントも削除されます。ステートメント ではwrite(sum)、 の値はsumステートメント自体に依存しないためです。特定のステートメント x のスライスには、複数の変数が含まれることがよくあります。ステートメント x 内の変数の集合が V である場合、(x, V) のスライスは、条件 (x, v) を持つすべてのスライスの和集合です。ここで、v は集合 V 内の変数です。

非常に高速でスケーラブルですが、精度はやや劣るスライシング アプローチは、いくつかの理由から非常に便利です。開発者は、数日ではなく数分で変更の影響を見積もるための非常に低コストで実用的な手段を手にします。これは、新機能の実装を計画し、変更がシステムの他の部分とどのように関連しているかを理解するために非常に重要です。また、システムの完全でより高価な分析が必要かどうかを判断するための安価なテストも提供します。高速スライシング アプローチは、スライシングに基づくメトリックと履歴のマイニングに関する新しい研究の道を開きます。つまり、非常に大規模なシステムとバージョン履歴全体に対して、非常に実用的な時間枠でスライシングを実行できるようになりました。これにより、以前はコストがかかりすぎて実行できなかった多くの実験と実証的調査への扉が開かれます。^[4]

動的スライスは、プログラムの特定の実行に関する情報を利用します。動的スライスには、プログラムの任意の実行のプログラム ポイントで変数の値に影響を与えた可能性のあるすべてのステートメントではなく、プログラムの特定の実行のプログラム ポイントで変数の値に実際に影響を与えるすべてのステートメントが含まれます。

静的スライスと動的スライスの違いを明確にする例です。if-else ブロックを含む反復ブロックがあるプログラム ユニットの小さな部分について考えてみましょう。 ブロックifとelseブロックの両方に、変数に影響を与えるステートメントがいくつかあります。 静的スライスの場合、プログラムの特定の実行に関係なくプログラム ユニット全体が調べられるため、両方のブロックの影響を受けるステートメントがスライスに含まれます。 しかし、動的スライスの場合は、プログラムの特定の実行を考慮します。その場合、ブロックはif実行されますが、ブロック内の影響を受けるステートメントはelse実行されません。 そのため、この特定の実行ケースでは、動的スライスにはブロック内のステートメントのみが含まれますif。

• ソフトウェアメンテナンス
• 依存分析
• 定義に到達する
• データ依存性
• Frama-C は、C プログラムにスライス アルゴリズムを実装するツールです。
• 部分的なデッドコードの除去

• Mark Weiser . 「プログラム スライシング」。第 5 回国際ソフトウェア エンジニアリング会議の議事録、439 ～ 449 ページ、IEEE Computer Society Press、1981 年 3 月。
• Mark Weiser . 「プログラム スライシング」。IEEE Transactions on Software Engineering、第 10 巻、第 4 号、352 ～ 357 ページ、IEEE Computer Society Press、1984 年 7 月。
• Susan Horwitz、Thomas Reps、David Binkley、「依存グラフを使用したプロシージャ間スライシング」、ACM Transactions on Programming Languages and Systems、第 12 巻、第 1 号、26-60 ページ、1990 年 1 月。
• Frank Tip. 「プログラム スライシング テクニックの調査」。Journal of Programming Languages、第 3 巻、第 3 号、121 ～ 189 ページ、1995 年 9 月。
• David Binkley および Keith Brian Gallagher。「プログラム スライシング」。Advances in Computers、第 43 巻、1 ～ 50 ページ、Academic Press、1996 年。
• Andrea de Lucia、「プログラム スライシング: 方法とアプリケーション」、ソース コード分析および操作に関する国際ワークショップ、142 ～ 149 ページ、2001 年、IEEE Computer Society Press。
• Mark Harman および Robert Hierons。「プログラム スライシングの概要」、Software Focus、第 2 巻、第 3 号、85 ～ 92 ページ、2001 年 1 月。
• David Binkley および Mark Harman。「プログラム スライシングに関する実証的結果の調査」、Advances in Computers、第 62 巻、105 ～ 178 ページ、Academic Press、2004 年。
• Jens Krinke、「プログラム スライシング」、ソフトウェア エンジニアリングと知識エンジニアリングのハンドブック、第 3 巻: 最近の進歩。World Scientific Publishing、2005 年
• シルバ、ジョセップ。「プログラム スライシング ベースのテクニックの語彙」、ACM コンピューティング調査、第 44 巻、第 3 号、Association for Computing Machinery、2012 年 6 月
• Alomari HW 他「srcSlice: 非常に効率的でスケーラブルなフォワード静的スライシング」。Wiley Journal of Software: Evolution and Process ( JSEP )、DOI: 10.1002/smr.1651、Vol. 26、No. 11、pp. 931-961、2014 年。

• VALSOFT/ジョアナプロジェクト
• インダス プロジェクト (バンデラ チェッカーの一部)
• ウィスコンシンプログラムスライシングプロジェクト