スタック容量の消費を分解する
ここで扱うスタックオーバーフローは、呼出しや局所データによって実行スタックの容量を使い切る現象です。スタック上の配列の範囲を越えるバッファオーバーフローとは、対象が同じ場所でも原因が違います。深い再帰だけでなく、大きな局所配列、一時領域、処理系が作るフレームも消費へ関わります。症状は言語や実行環境により、再帰制限の例外、保護領域へのアクセス、プロセス終了などになります。どの環境でも同じ例外を捕まえられるとは考えず、スタックトレースと入力、スレッドごとの条件を記録します。
深さとフレームサイズの模式計算
説明用に1フレームが約1KiBで、使える容量を1MiBと仮定すると、千回程度の呼出しで容量へ近づく計算になります。ただし実際には既存のフレーム、整列、一時領域、保護ページがあり、この割り算は安全な再帰回数を保証しません。同じソースでも最適化や版、ABIで消費が変わります。末尾再帰の最適化も全ての言語や設定で保証されません。数値は機構を説明する仮定で実測値ではないため、これをそのまま入力上限へ採用しません。言語の再帰制限とOSやスレッドのスタック容量も、別の上限として確認します。
再帰の終了条件と入力構造を確認する
再帰関数が停止する条件と、各呼出しで入力がどれだけ小さくなるかを調べます。木を読む処理で、要素数が多くなくても一直線の構造なら深さが大きくなる場合があります。循環を持つグラフを木として扱うと、訪問済みの確認がないため同じ場所を再びたどることもあります。クラッシュ直前の同じ関数が並ぶトレースは手掛かりですが、単に再帰があること自体がバグとは言えません。外部から受け取る入れ子データでは、総バイト数の制限だけで深さの制限を代用しないようにします。入力の形と深さを独立に保存して再現条件を作ります。
反復化と上限の設計を選ぶ
反復処理へ変える場合は、明示的な作業スタックやキューを使い、順序と終了条件を維持します。呼出しスタックをヒープへ移すだけなら、必要なメモリや仕事量がなくなるわけではありません。明示構造の件数、深さ、時間にも上限や拒否条件を設けます。スタック容量を増やす方法は有限の深さが必要な場合の選択肢ですが、終了しない再帰を直す代わりにはなりません。Pythonのsetrecursionlimitのような処理系の設定も、無制限に上げれば安全になるという意味ではありません。処理系の保護と実際のCスタック等の制約を合わせて検討します。
回復と試験の限界を確かめる
試験では空構造、浅い構造、深く片寄った構造、許容境界の直前と直後、循環が混入した入力を分けます。実験は専用の小さなプロセスで行い、共有サービスを意図的に落として確認する必要はありません。スタックが尽きた後のログや例外処理にも領域が必要なため、障害後に常に完全な診断が残るとは限りません。入力を処理前に制限する設計と、失敗時に仕事を中断する方針を用意します。修正後は正当な入力の走査順や出力が変わっていないことも比較し、深さ制限を加えただけで処理の意味を失っていないかを確認します。