「スタックオーバーフロー」はどのようにして発生し、どのように防ぐのでしょうか?

https://stackoverflow.com/questions/26158

09-06-2019
|

質問

スタックオーバーフローはどのようにして発生するのでしょうか。スタックオーバーフローが発生しないようにする最善の方法は何ですか。特に Web サーバー上でスタックオーバーフローを防ぐ方法はありますか。他の例も興味深いでしょう。

解決

スタック

この文脈におけるスタックとは、プログラムの実行中にデータを配置する後入れ先出しバッファーのことです。後入れ先出し (LIFO) は、最後に入力したものが常に最初に取り出されるという意味です。スタック上の 2 つの項目 (「A」、次に「B」をプッシュした場合、最初にポップしたものがポップされます)スタックから取り出されるのは「B」で、その次は「A」になります。

コード内で関数を呼び出すと、関数呼び出し後の次の命令がスタックと、関数呼び出しによって上書きされる可能性のある記憶領域に格納されます。呼び出す関数は、独自のローカル変数のためにさらに多くのスタックを使用する可能性があります。それが完了すると、使用していたローカル変数のスタック領域が解放され、前の関数に戻ります。

スタックオーバーフロー

スタックオーバーフローは、プログラムが使用する予定よりも多くのメモリをスタックに使い果たした場合に発生します。組み込みシステムでは、スタックに 256 バイトしかない可能性があり、各関数が 32 バイトを占める場合、関数呼び出しは深さ 8 までしか行うことができません。つまり、関数 1 が関数 2 を呼び出し、その関数が関数 3 を呼び出し、その関数が関数 4 を呼び出します。関数 8 を呼び出す人関数 9 を呼び出す人。ただし、関数 9 はスタックの外側のメモリを上書きします。これにより、メモリやコードなどが上書きされる可能性があります。

多くのプログラマーは、関数 A を呼び出してから関数 B を呼び出し、さらに関数 C を呼び出し、さらに関数 A を呼び出すというこの間違いを犯します。ほとんどの場合は機能するかもしれませんが、一度だけ間違った入力をすると、スタックが過剰であることをコンピューターが認識するまで、永久にその循環を続けることになります。

再帰関数もこの原因になりますが、再帰的に記述している場合 (つまり、関数自体が呼び出される場合)、これに注意し、無限再帰を防ぐために静的/グローバル変数を使用する必要があります。

一般に、スタックは使用している OS とプログラミング言語によって管理され、ユーザーの手に負えません。コールグラフ (各関数が何を呼び出すかをメインから示すツリー構造) を調べて、関数呼び出しがどの程度深く行われているかを確認し、意図しないサイクルや再帰を検出する必要があります。意図的なサイクルと再帰は、相互に呼び出す回数が多すぎる場合にエラーが発生するように人為的にチェックする必要があります。

適切なプログラミングの実践、静的および動的テスト以外に、これらの高レベルのシステムでできることはあまりありません。

組み込みシステム

組み込みの世界、特に信頼性の高いコード (自動車、航空機、宇宙) では、広範なコードレビューとチェックが行われますが、さらに次のことも行われます。

再帰とサイクルを禁止します - ポリシーとテストによって強制されます
コードとスタックを遠く離れた場所に配置します (コードはフラッシュに、スタックは RAM に置き、両者が接触することはありません)。
スタックの周りにガードバンドを配置します。メモリの空き領域にマジックナンバー (通常はソフトウェア割り込み命令ですが、ここには多くのオプションがあります) を埋め込み、1 秒間に何百、何千回もガードバンドを確認して確認します。上書きされていません。
メモリ保護を使用する (つまり、スタック上で実行しない、スタックのすぐ外で読み取りまたは書き込みをしない)
割り込みは二次関数を呼び出しません。割り込みはフラグを設定し、データをコピーし、アプリケーションにその処理を任せます (そうしないと、関数呼び出しツリーの深さが 8 になり、割り込みが発生し、その後、内部でさらにいくつかの関数が実行される可能性があります)中断して爆発を引き起こします)。複数の呼び出しツリーがあります。1 つはメインプロセス用、もう 1 つは各割り込み用です。割り込みが互いに割り込むことができる場合...まあ、ドラゴンもいるけど…

高級言語とシステム

ただし、オペレーティングシステム上で実行される高級言語では次のようになります。

ローカル変数のストレージを減らします (ローカル変数はスタックに格納されますが、コンパイラはこれについて非常に賢く、呼び出しツリーが浅い場合には大きなローカル変数をヒープに置くことがあります)。
再帰を避けるか厳密に制限する
プログラムをより小さな関数に分割しすぎないでください。ローカル変数をカウントしなくても、各関数呼び出しはスタック上で 64 バイトも消費します (32 ビットプロセッサ、CPU レジスタ、フラグなどの半分を節約します)。
コールツリーを浅くする (上記のステートメントと同様)

Webサーバー

スタックを制御できるか、さらには表示できるかは、使用している「サンドボックス」によって異なります。Web サーバーを他の高級言語やオペレーティングシステムと同じように扱うことができる可能性は十分にあります。それはほとんどあなたの手に負えませんが、使用している言語とサーバースタックを確認してください。それはたとえば、SQL サーバー上のスタックを破壊する可能性があります。

-アダム

他のヒント

実際のコードではスタックオーバーフローが発生することはほとんどありません。この問題が発生するほとんどの状況は、終了が忘れられた再帰です。ただし、高度にネストされた構造ではまれに発生する可能性があります。特に大きな XML ドキュメント。ここでの唯一の本当の助けは、コールスタックの代わりに明示的なスタックオブジェクトを使用するようにコードをリファクタリングすることです。

ほとんどの人は、出口パスのない再帰でスタックオーバーフローが発生すると言うでしょう。ほとんどがその通りですが、十分な大きさのデータ構造を扱う場合、適切な再帰出口パスがあっても役に立ちません。

この場合のいくつかのオプション:

幅優先検索
末尾再帰, 、.Net 固有の素晴らしいブログ投稿 (ごめんなさい、32 ビット .Net)

無限再帰はスタックオーバーフローエラーを引き起こす一般的な方法です。これを防ぐには、常に出口パスがあることを確認してください。意思殴られる。:-)

(少なくとも C/C++ では) スタックオーバーフローを発生させるもう 1 つの方法は、スタック上で巨大な変数を宣言することです。

char hugeArray[100000000];

それで済むよ。

スタックオーバーフローは、Jeff と Joel が技術的な質問に対する答えを得るより良い場所を世界に提供したいと考えたときに発生します。このスタックオーバーフローを防ぐには遅すぎます。その「他のサイト」は、スカジーにならなければ、それを防ぐことができたかもしれません。;)

通常、スタックオーバーフローは、無限再帰呼び出しの結果として発生します (今日の標準的なコンピューターの通常のメモリ量を考慮すると)。

メソッド、関数、またはプロシージャを呼び出すときの「標準的な」方法、または呼び出しの実行は次のとおりです。

呼び出しの戻り方向をスタックにプッシュします (呼び出しの後の次の文です)。
通常、戻り値用のスペースはスタックに予約されます。
各パラメータをスタックにプッシュします (順序は異なり、各コンパイラによって異なります。また、パフォーマンス向上のために一部のパラメータが CPU レジスタに格納されることもあります)。
実際に電話をかける。

したがって、パラメータの数とタイプ、およびマシンのアーキテクチャに応じて、通常、これには数バイトかかります。

再帰呼び出しを開始すると、スタックが増加し始めることがわかります。現在、スタックは通常、ヒープとは逆方向に成長するような方法でメモリ内に予約されているため、「戻ってくる」ことなく大量の呼び出しが行われると、スタックがいっぱいになり始めます。

さて、昔は、利用可能なメモリをすべて使い果たしたという理由だけでスタックオーバーフローが発生することがありました。仮想メモリモデル (X86 システムでは最大 4GB) は対象外だったので、通常、スタックオーバーフローエラーが発生した場合は、無限再帰呼び出しを探します。

直接再帰から得られるスタックオーバーフローの形式とは別に (例: Fibonacci(1000000)）、私が何度も経験した、より微妙な形式は間接再帰です。つまり、関数が別の関数を呼び出し、その関数が別の関数を呼び出し、その後、それらの関数の 1 つが最初の関数を再度呼び出します。

これは一般に、イベントに応答して呼び出される関数内で発生しますが、関数自体が新しいイベントを生成する可能性があります。次に例を示します。

void WindowSizeChanged(Size& newsize) {
  // override window size to constrain width
    newSize.width=200;
    ResizeWindow(newSize);
}

この場合、次の呼び出しは ResizeWindow を引き起こす可能性があります WindowSizeChanged() 再度トリガーされるコールバック。 ResizeWindow スタックがなくなるまで繰り返します。このような状況では、多くの場合、スタックフレームが戻るまで、たとえばメッセージを投稿するなどして、イベントへの応答を延期する必要があります。

何？無限ループに陥った人たちを愛する人はいないのでしょうか？

do
{
  JeffAtwood.WritesCode();
} while(StackOverflow.MakingMadBank.Equals(false));

これが「ハッキング」でタグ付けされていることを考えると、彼が言及している「スタックオーバーフロー」は、ここでの他のほとんどの回答で参照されているような高レベルのスタックオーバーフローではなく、コールスタックオーバーフローではないかと思います。これは、Web アプリが通常作成される .NET、Java、Python、Perl、PHP などの管理または解釈された環境には実際には適用されません。そのため、唯一のリスクは、おそらく次の言語で記述されている Web サーバー自体です。 C または C++。

このスレッドをチェックしてください:

https://stackoverflow.com/questions/7308/what-is-a-good-starting-point-for-learning-buffer-overflow

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow

「スタック オーバーフロー」はどのようにして発生し、どのように防ぐのでしょうか?