形状分析（プログラム分析）

プログラム分析において、シェイプ分析は、（通常は命令型の）コンピュータ プログラム内のリンクされ、動的に割り当てられたデータ構造の特性を発見して検証する静的コード分析手法です。これは通常、コンパイル時にソフトウェアのバグを見つけたり、プログラムの高レベルの正確性特性を検証したりするために使用されます。Java プログラムでは、ソート メソッドがリストを正しくソートすることを確認するために使用できます。C プログラムでは、メモリ ブロックが適切に解放されていない場所を探す場合があります。

形状解析はさまざまな問題に適用されてきました。

• メモリの安全性:メモリリーク、ダングリングポインタの逆参照、メモリブロックが複数回解放されるケースの検出。^{[1] [2]}
• 配列の範囲外エラーの検出^{[引用が必要]}
• 型と状態のプロパティを確認する（たとえば、ファイルがopen()である前に であることを確認するread()）^{[引用が必要]}
• リンクリストを逆にする方法がリストに循環を導入しないことを保証する^[2]
• ソートメソッドがソートされた順序で結果を返すことを確認する^{[引用が必要]}

シェイプ解析はポインタ解析の一種ですが、一般的なポインタ解析よりも正確です。ポインタ解析は、ポインタが指すことができるオブジェクトのセット (ポインタのポイント先セットと呼ばれる) を決定しようとします。残念ながら、これらの解析は必然的に近似値になります (完全に正確な静的解析では停止問題を解決できるため)。シェイプ解析では、より小さい (より正確な) ポイント先セットを決定できます。

次の単純な C++ プログラムを考えてみましょう。

Item * items [ 10 ]; for ( int i = 0 ; i < 10 ; ++ i ) { items [ i ] = new Item (...); // 行 [1] } process_items ( items ); // 行 [2] for ( int i = 0 ; i < 10 ; ++ i ) { delete items [ i ]; // 行 [3] } 
         
        

 
         
      

このプログラムは、オブジェクトの配列を構築し、それらを任意の方法で処理してから削除します。関数にprocess_itemsエラーがないと仮定すると、プログラムが安全であることは明らかです。解放されたメモリを参照することはなく、構築したすべてのオブジェクトを削除します。

残念ながら、ほとんどのポインタ解析では、このプログラムを正確に解析することは困難です。ポイント先セットを決定するために、ポインタ解析はプログラムのオブジェクトに名前を付けることができなければなりません。一般に、プログラムは無制限の数のオブジェクトを割り当てることができますが、終了するために、ポインタ解析は有限の名前セットしか使用できません。一般的な近似は、プログラムの特定の行に割り当てられたすべてのオブジェクトに同じ名前を付けることです。上記の例では、行 [1] で構築されたすべてのオブジェクトは同じ名前になります。したがって、ステートメントdeleteが初めて解析されるとき、解析は [1] という名前のオブジェクトの 1 つが削除されていると判断します。ステートメントが 2 回目に解析されると (ループ内にあるため)、解析はエラーの可能性を警告します。配列内のオブジェクトを区別できないため、2 番目はdelete1 番目と同じオブジェクトを削除している可能性がありますdelete。この警告は偽物であり、シェイプ解析の目的はこのような警告を回避することです。

シェイプ分析は、より柔軟なオブジェクト命名システムを使用することで、ポインター分析の問題を克服します。プログラム全体でオブジェクトに同じ名前を付けるのではなく、プログラムの動作に応じてオブジェクトの名前を変更できます。場合によっては、異なる名前を持つ複数の異なるオブジェクトを要約またはマージして、同じ名前にすることができます。次に、要約されたオブジェクトがプログラムで使用されるときに、それを具体化できます。つまり、要約されたオブジェクトは、異なる名前を持つ 2 つのオブジェクトに分割され、1 つは単一のオブジェクトを表し、もう 1 つは残りの要約されたオブジェクトを表します。シェイプ分析の基本的なヒューリスティックは、プログラムによって使用されているオブジェクトは一意の具体化されたオブジェクトを使用して表され、使用されていないオブジェクトは要約されるというものです。

上記の例のオブジェクトの配列は、[1]、[2]、[3] 行で別々の方法で要約されています。[1] 行では、配列は部分的にしか構築されていません。配列要素 0..i-1 には構築されたオブジェクトが含まれています。配列要素 i は構築される予定であり、後続の要素は初期化されていません。シェイプ分析では、次のように、最初の要素セットの要約、要素 i の具体化されたメモリ位置、および残りの初期化されていない位置の要約を使用して、この状況を近似できます。

ループが終了した後、[2]行目で何もマテリアライズドしておく必要はありません。形状分析により、この時点ですべての配列要素が初期化されたことが判断されます。

ただし、行 [3] では、配列要素iが再び使用されています。そのため、解析では行 [1] のように配列を 3 つのセグメントに分割します。ただし、今回は、最初のセグメントがi削除されており、残りの要素はまだ有効です (deleteステートメントがまだ実行されていないと仮定)。

この場合、分析ではインデックスのポインタiがまだ削除されていないことが認識されることに注意してください。したがって、二重削除の警告は表示されません。

• エイリアス分析
• 脱出分析

• Neil D. Jones、Steven S. Muchnick (1982)。「インタープロシージャ データ フロー分析と再帰データ構造を持つプログラムへの柔軟なアプローチ」。プログラミング言語の原則に関する第 9 回 ACM SIGPLAN-SIGACT シンポジウム議事録 - POPL '82 。ACM。pp . 66–74。doi :10.1145/ 582153.582161。ISBN 0897910656. S2CID  13266723。{{cite book}}: CS1 メンテナンス: 日付と年 (リンク)

• Mooly Sagiv ; Thomas Reps ; Reinhard Wilhelm (2002年5 月) 。「3 値ロジックによるパラメトリック形状解析」(PDF)。ACM Transactions on Programming Languages and Systems。24 ( 3 ) 。ACM: 217–298。CiteSeerX 10.1.1.147.2132。doi : 10.1145 /292540.292552。S2CID 101653  。 

• Wilhelm, Reinhard、Sagiv, Mooly、Reps, Thomas (2007)。「第 12 章: 形状分析とアプリケーション」。Srikant, YN、Shankar, Priti (編)。コンパイラ設計ハンドブック: 最適化とマシン コード生成、第 2 版。CRC プレス。pp. 12–1–12–44。ISBN 978-1-4200-4382-2。