スタックオーバーフロー

スタックオーバーフロー (英: stack overflow) は、コンピュータプログラムにおいて、コールスタック領域の限界を超えたデータプッシュにより発生する、バッファオーバーフローの一種である。スタックバッファオーバーフロー (英: stack buffer overflow) とは別の概念である。

概要

プログラムにおいて、サブルーチン（関数／プロシージャ）呼び出しに関する情報を格納するためのスタックメモリ領域（コールスタック）が確保される。サブルーチン呼び出しのたびにデータがスタックに積まれ（プッシュ）、サブルーチンが終わって制御フローが呼び出し元に戻るとスタックからデータが降ろされる（ポップ）。オペレーティングシステムや実行オプションにもよるが、コールスタックに格納できる情報量には上限がある。コールスタックに蓄積されるデータ量が限界を超えるとスタックは「オーバーフロー」し、未定義動作を引き起こす。オペレーティングシステムにもよるが、プログラム側で対策をとっていなければ通常はプロセスがクラッシュしてしまう。ただし、スタックオーバーフローの原因となりうるコードパターンは比較的限定されている。

スタックオーバーフローの発生原因のうち、最も多いのはサブルーチンの再帰呼び出しによる無限ループ（無限再帰）である。また、ソースコードの設計上は無限再帰ではなく、終了条件を決めて有限回数で打ち切るような有限再帰になっていたとしても、再帰呼び出しの階層数が深すぎると実行環境におけるコールスタックの上限を超えてしまい、スタックオーバーフローとなってしまう場合もある。ただし、末尾最適化を実装したプログラミング言語では、末尾再帰の形で書かれたサブルーチンをループへ展開することができ、スタックオーバーフローは起こらなくなる。フラットなループ処理に変換されることで、再帰呼び出しによりスタックを消費することが無くなるからである。なお、再帰ではないサブルーチン呼び出しであっても、呼び出し階層数が深すぎる場合には、やはりスタックオーバーフローが起こりうる。

次によくある原因としては、スタック上に巨大な配列を確保しようとすることである。コールスタックに格納できる情報量には上限があるため、巨大なサイズのローカル変数を定義するのではなく、ヒープ領域などを明示的に利用すべきである。

C/C++ での例

再帰による無限ループ

/* 関数の戻り値が int の場合、C言語では前方宣言や前方定義がなくてもコンパイル可能だが、C++では前方宣言あるいは前方定義が必要。 */
int g(void);

int f(void) {
    return g();
}

int g(void) {
    return f();
}

関数 f() は関数 g() を呼び出しているが、g() もやはり f() を呼び出している。交互の呼び出しは終わることがなく、最終的にはスタックオーバーフローが発生する。以下のような終了条件のない自己再帰も無限再帰となる。

int foo(void) {
    return foo();
}

巨大な配列をスタックに配置した場合

システムに実装されているメインメモリの容量にかかわらず、各プログラムのスタック領域のサイズは既定でせいぜい数MiB程度^[1]^[2]^[3]^[4]^[5]であり、大容量の配列を確保するのには向いていない。

#include <stdio.h>
int main(void) {
    int ary[1000 * 1000 * 1000]; /* 配列が大きすぎる */
    printf("Hello!\n"); /* &"Hello!\n" のプッシュがスタックオーバーフローとなる */
}

この場合は、

#include <stdio.h>
int ary[1000 * 1000 * 1000];
int main(void) {
    printf("Hello!\n");
}

または

#include <stdio.h>
int main(void) {
    static int ary[1000 * 1000 * 1000];
    printf("Hello!\n");
}

のように配列を静的領域に移動するか、あるいは malloc などを使ってヒープ領域に動的確保すればスタックオーバーフローは回避できる。通例、システムが利用できる空きメモリの量は必ずしも定かではないので、実行時の動的メモリ確保と成否チェックを行なうことが望ましい。

#include <stdio.h>
#include <stdlib.h>
int main(void) {
    int *ary = (int *)malloc(sizeof(int) * 1000 * 1000 * 1000);
    printf("Hello!\n");
    free(ary);
}

スタックオーバーフロー

概要

C/C++ での例

再帰による無限ループ

巨大な配列をスタックに配置した場合

脚注

関連項目