シェープ解析

シェープ解析（シェープかいせき、英: Shape analysis）は、静的コード解析の技法のひとつであり、(通常は命令型の)コンピュータプログラムの中で相互にリンクしている動的に割り当てられたデータの特性を解析・検証する技術である。通常はコンパイル時にソフトウェアのバグを発見したり、プログラムの特性の高レベルな妥当性を検証するために用いられる。

シェープ解析は、例えば Java プログラムではソートするメソッドが正しくソートを行えることを保証するために用いたり、C のプログラムでは、適切に開放されないようなメモリのブロックの箇所を見つけ出したりすることができる。シェープ解析は非常に強力ではあるが、実行に非常に時間がかかるのが通例である。このため、大学や研究機関（実験的にのみ使用）以外ではあまり広く用いられていない。

シェープ解析の応用

シェープ解析は、多くの問題に適用することができる。

メモリリークの発見。Java 的なリーク(不要のオブジェクトに対するポインタがヌルクリアされていないために発生する)を含む
メモリブロックが複数回解放されるような場合の発見(C)
"dangling pointer" (Cでは解放されたメモリに対するポインタ)の解放の検知
配列の境界違反の発見
type-state properties の確認(例えば、ファイルが read() されるより前に open()されることを保証する)
リンクリストを逆方向にたどるメソッドが、循環しないことを検証する
ソートするメソッドが正しくソートされた結果を返すことを検証する

例

シェープ解析は通常のポインタ解析より強力だが、ポインタ解析の形態のひとつである。ポインタ解析ではポインタが示す可能性があるオブジェクト群（ポインタの指し示す集合）を特定する。しかし、こうした解析は必然的に推測であり、決定論的ではない（完全に正確な静的解析は停止性問題を解くことができないため）。シェープ解析では、ポインタの指す集合を狭い範囲に（より正確に）特定することができる。

下のような単純な C++ のプログラムを考える。

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

このプログラムはオブジェクトの配列を構築し、任意の方法でこれらを処理し、その後解放する。process_items 関数に問題がなければこのプログラムは安全であり、解放されたメモリを参照することはなく、きちんと初期化されたオブジェクトを削除する。

なお、大半のポインタ解析手法はこのプログラムを正確に解析することが困難である。ポインタの指し示す集合を特定するためには、ポインタ解析によってプログラムのオブジェクトに名前をつけることが可能でなければならない。一般的には、プログラムは数に制限なくオブジェクトを生成することができる。しかし、解析が完了するためには、ポインタ解析は有限の名前しか用いることができない。典型的な方法では、プログラムの特定の行で割り当てられたオブジェクトに同じ名前を与える。上記の例では、行[1]で作成されたオブジェクトはすべて同じ名前を持つ。このため、delete 文が初めて解析されると、解析処理は [1] と名前のついたオブジェクトの一つが解放されるようとしていると判断する。delete 文が（ループ処理により）二度目に解析されると、解析プログラムは配列内のオブジェクトを区別できないため、二度目のdelete が最初の delete と同じオブジェクトを解放しているかも知れないと判断し、プログラムに問題がある可能性を警告する。この警告は偽のものである。シェープ解析の目標は、こうした警告を生じさせないことである。

要約と実体化

シェープ解析ではより柔軟にオブジェクトに名前をつけることによって、ポインタ解析の問題点を克服している。プログラム全体を通してオブジェクトに同じ名前を与える替わりに、プログラムの動作によって名前を変えることができる。異なる名前のオブジェクトのいくつかは「要約 (summarize)」して同じ名前を持つようにすることができる。「要約された」オブジェクトが実際にプログラムによって使用されるとき、これを「実体化(materialize)」、すなわち要約化されたオブジェクトを、一つのオブジェクトと残りの要約されたオブジェクトの二つに分割し、識別できるような異なる名前をつける。シェープ解析の基本的な方法では、プログラムが使用しているオブジェクトは一意の実体化されたオブジェクトとして表現し、使用していないものは要約された形で表現する。

上記の例で、オブジェクトの配列は行 [1], [2], [3] で別々の方法で要約化される。行 [1] では、配列の要素は部分的にのみ初期化されている。配列の要素 0..i-1 は初期化されたオブジェクトを格納している。配列の要素 i が初期化されるようとしているとき、後続の要素は初期化されていない。シェープ解析ではこうした状況を要素の最初の、すなわち要素 i の実体化されたメモリ上の位置、および残りの未初期化されていないメモリ位置に対する要約を用いて、以下のように推測することができる。

0 .. i-1	i	i+1 .. 9
初期化済み (要約)	未初期化	未初期化 (要約)

行 [2] でループ処理が完了すると、オブジェクトを実体化したままにしておく必要はなくなる。シェープ解析では、この時点ですべての配列要素が初期化済みであると判断する。

0 .. 9

初期化済みオブジェクトへのポインタ (要約)

しかし、行 [3] では、配列の要素 i が再び使用される。そのため、解析では行 [1] で行ったように、配列を 3 つの領域に分割する。今回は、i 以前の領域は解放済みであり、残りの要素はまだ生存している(delete 文が実行されていなければ)。

0 .. i-1	i	i+1 .. 9
解放済み (要約)	初期化済みオブジェクトへのポインタ	初期化済みオブジェクトへのポインタ(要約)

この場合、インデックスi のポインタがまだ解放されていないことを認識できる。このため、二重解放の警告を出すことはない。

参考文献

en:Template:Cite journal