保証の観点：スタック安全性

小さなプログラムを堅牢化することで、スタックメモリと静的メモリについて学びます。最初のバージョンには脆弱性があります。攻撃者は特定の入力を与えることでシステムメモリを使い尽くし、アプリケーションをクラッシュさせることができます（「サービス拒否」または DoS）。修正後のバージョンは MISRA Rule 17.2（本質的には第 3 章で紹介した「再帰なし」）に準拠します。

[RR, Rule 17.2] 関数は（直接または間接的に）再帰的に自分自身を呼び出してはならない¹

これにより脆弱性が修復され、可用性が向上します。また、このルール/パターンは、再帰をサポートするあらゆるプログラミング言語に関係します！このルールは Python、Java、Go、Swift、TypeScript などにすぐに適用できます。

より一般的には、特定の関数のスタック安全性を高めるための、プラットフォーム非依存かつ言語非依存のパターンを探ります。

再帰と静的コールグラフ

付録の「理論：手続き間 CFG」セクションでは、多くの静的解析ツールが依拠するグラフの文脈で、再帰について簡単に検討しています。このセクションを読み終えた後、興味のある方におすすめする短い任意の余談です。

スタック

スタックメモリは、プログラミングにおける最も基本的な抽象化の 1 つである関数（別名、プロシージャ、メソッド、サブルーチン）を支えます。関数はパラメータとともに呼び出され、何らかの計算を行い、必要に応じて結果を返します。したがって、ハードウェアには次のことを行う仕組みが必要です²。

制御を渡す - 命令ポインタ（IP）を呼び出された関数のアドレスに設定し、完了したら呼び出しに続く文に戻す。
データを渡す - 入力としてパラメータを提供し、結果を返す。新しい値として返す場合もあれば、入力の mut 化として返す場合もある。
作業メモリを割り当て、解放する - 呼び出された関数は、開始時にローカル変数用の領域を取得し、戻るときにその領域を解放する必要がある。

機械的には、スタックメモリは push と pop という 2 つの単純な操作だけで、これら 3 つの要件すべてを支えます。これは同名の Last In First Out（LIFO）データ構造と同じように機能します。項目（アドレス、変数など）や関数全体の作業メモリブロック（「フレーム」と呼ばれます）をスタックへ push でき、pop できるのは最上部（最も最近 push された項目/フレーム）からだけです。

スタックメモリの目的は、サイズが固定されている（コンパイル時に既知である）データに対して、実行時の割り当てと解放を高速に支えることです。つまり：

スタックフレームは、単一の関数の実行に必要なメモリ上の「作業領域」の塊です。フレームには、その関数で使用される固定サイズのローカル変数がすべて含まれます。
push 操作（割り当て）は関数呼び出しに対応します。プログラム内で名前付き関数を呼び出すたびに、新しいフレームがスタックへ push されます³。呼び出された関数（例：callee）は、そのローカル変数用の作業メモリを得ます。これはcaller のフレーム（スタック上でその下に位置します）とは別です。ランタイムスタックは低いアドレスに向かって下方向に伸びます。
pop 操作（解放）は関数の戻りに対応します。関数が終了すると（制御が return キーワードに到達するか、関数スコープの終端に到達するため）、そのフレームは破棄されます。時間を節約するため、プログラマが C の memset⁴ のような関数を明示的に呼び出すか、Rust の zeroize⁵ のようなクレートを使用しない限り、データはクリア/消去されません。速度のために、代わりに SP が単にインクリメントされます。古い（低いアドレスの）データへのアクセスは、それを含むフレームが pop された時点でもはや合法ではありません。

なぜスタックは高速なのか？

ヒープメモリとは異なり、スタックメモリの仕組みはハードウェアで直接サポートされており、コンパイル時に決定できます。

思い出してください。「スタックポインタ」は CPU レジスタ（SP）です。最適化されたハードウェアは、現在のスタック先頭がどこにあるかを追跡します。コンパイラは、スタックへ効率的に push し、スタックから効率的に pop するための専用 CPU 命令を生成します。これらの命令については、後ほどアセンブリのスニペットで少し見ます。

push/pop の説明をより具体的にするために、コードスニペットがスタックをどのように使用するかを可視化してみましょう。

#[inline(never)]
fn recursive_count_down(x: usize) -> usize {
    // Base case
    if x == 0 {
        println!("Boom!");
        return x;
    // Recursive case
    } else {
        println!("{x}...");
        return recursive_count_down(x - 1);
    }
}

#[inline(never)]
fn square(x: usize) -> usize {
    x * x
}

fn main() {
    let args: Vec<String> = std::env::args().collect();

    // 1st arg is binary name, e.g. "./stack_example 2"
    assert!(args.len() <= 2, "Too many arguments - enter one number");

    let x = args
        .iter()
        .nth(1)
        .expect("No arguments")
        .parse()
        .expect("Please provide a number");

    let _ = recursive_count_down(square(x));
}

main 関数は、単一のコマンドライン引数を usize 変数 x にパースします。引数が入力されていない場合、2 個を超える引数が入力された場合、または唯一の引数が正の数でない場合は、エラーメッセージを表示して終了します。
recursive_count_down(square(x)); は、入力引数を 2 乗するために 1 つの関数を呼び出し、次に x^2 から 0 までのカウントダウンシーケンスを出力するために別の関数を呼び出します。
このプログラムが実行時にスタックメモリをどのように使用するかに関心があるため、recursive_count_down または square が呼び出されるたびにコンパイラがスタックフレームを割り当てるよう、属性 #[inline(never)] を追加します。
- 「インライン化」は、スタックフレームの割り当てや caller レジスタの保存を含む関数呼び出しのオーバーヘッドを避けられる場合がある、機会主義的なコンパイラ最適化です³。常に適用できるわけではなく、プログラマとしてそれがどこで行われるかを直接決めることもできません。したがって、それを使わない場合を想定して備えることは現実的です。

cargo run -- 2 で実行すると、このプログラムは次を出力します。

4...
3...
2...
1...
Boom!

では、その実行中にスタックメモリでは何が起きたのでしょうか？呼び出された各関数は、それぞれ独自のスタックフレームを割り当てます。 main 用に 1 つ、square 用に 1 つ、そして recursive_count_down の各再帰呼び出し用に 1 つあります。

すべてのフレームの前に、戻りアドレス（次に実行する文のアドレス、つまり呼び出しが完了した後に CPU が IP を指すべき場所）もスタックへ（下方向に）push されます。
特定の呼び出し規約では、関数の引数をその関数のフレームの前にスタックへ push することが必要な場合があります。一方で、最初のいくつかの引数については最適化としてレジスタを使用し（残りをスタックへ push する）ものもあります。
- 簡潔にするため、この詳細と、callee-saved レジスタの保存/復元のための同様の push/pop 仕組みは省略します。

引数渡しとレジスタ保存を除くと、Boom! が出力されるときのスタックは次のようになります。

上記プログラムの実行終盤におけるスタック図。

プロセスの最大スタック領域を使い尽くす

上記プログラムのクレートは code_snippets/chp4/stack_example にあります。次のエラーでバイナリをクラッシュさせる入力を見つけられますか？このエラーはどこから来るのでしょうか？

thread 'main' has overflowed its stack
fatal runtime error: stack overflow

二分探索アルゴリズム（ここでの “binary” は「2」を意味し、「コンパイル済みバイナリ」を意味するものではありません）は、十分に大きな入力を見つける方法の1つです。しかし、十分に大きな数値を推測するのがおそらく最も簡単です。クラッシュを引き起こす cargo run コマンドを見つけたら、それを書き留めてください。修正が本当に有効であることを証明するために、同じ入力/攻撃を使用します。

MISRA Rule 17.2（「再帰なし」）を思い出してください。この指針を適用することで、このプログラムの正確なインターフェイス（コマンドライン機能、出力内容）を維持しつつ、空間計算量を制限することでメモリ使用の堅牢性を高めることができます。

まず、中心的な問題を理解しましょう。指数的な、O(n^2) のスタック空間使用です。攻撃者の入力は、スタックメモリ使用量に対して非対称な制御を行います。入力整数に対して相対的にスケールします（“R” は再帰関数を示します）。

入力の関数として O(n^2) のスタック使用量を可視化しています。

普遍的な障害モード

再帰は、あらゆる Type-I、II、III システムでスタック枯渇のリスクをもたらします。どの CPU アーキテクチャでも同様です。

スタック安全性のための堅牢化

MISRA 17.2 に対処するには、recursive_count_down を新しい iterative_count_down 実装に置き換えます。

#[inline(never)]
fn iterative_count_down(x: usize) {
    for i in (0..=x).rev() {
        match i {
            i if i == 0 => println!("Boom!"),
            _ => println!("{i}..."),
        }
    }
}

これで、スタックのスケーリングはすべての入力に対して定数、O(1) になります（“I” は反復関数を示します）。

入力の関数として O(1) のスタック使用量を可視化しています。

プログラムがメモリ枯渇で終了しなくなったことを検証するために、先ほど発見したクラッシュする入力で再実行してみてください。エンジニアとして、その成功を見るのは満足感がありませんか？

終える前に、静的メモリがプログラムの静的文字列をどのように支えるのかを理解しましょう。

Rust != スタック安全性

Rust は大部分においてメモリ安全です。既存の言語と比べると大きな飛躍です。しかしスタック安全性、つまり再帰などによって引き起こされるスタックオーバーフローを検出する能力は、プラットフォーム固有です。

クラッシュする入力を見つけたとき、あなたの OS がそれを検出し、プロセスを先制的に強制終了しました。ここで rustc は確かに役立ちました。コンパイル時にスタックプローブを挿入し、実行時にスタックデータの書き込み上限に達した場合、即座に制御を OS に渡せるようにしました。

しかし、多くの #![no_std] システムはこの検出機能をサポートしていません。もしこのプログラムが Type-III マイクロコントローラー上で実行されていたなら、オーバーフローは検出されなかった可能性があります。関数が、事前に設定されたスタック上限を越えた先にたまたま格納されていたデータを破損していたかもしれません。システムによっては、それがブートローダーを含む場合さえあります！

MISRA C 17.2 a は、{platform,language} に依存しないスタック安全性のための価値あるガイドラインです。プログラム内のオーバーフローの可能性を排除する助けになります。

しかし、それでも任意の反復的な呼び出しチェーンについて、最悪ケースのスタック使用量がターゲットプラットフォームの能力を超えないことを保証する必要があります。したがって、完全なスタック安全性は野心的な目標です。 cargo call-stack⁶ が役立ちます。

静的メモリ

静的メモリにはグローバルデータが含まれます。ソースコード内のグローバル変数だけではありません（ただし、それらも静的メモリに置かれます）。ハードコードされた文字列や定数データ（例: include! マクロ[^IncludeMacro] によってコンパイル時に埋め込まれるファイルバイト）もそこに置かれます。 Rust に特化して言えば、次のとおりです。

静的メモリは、static キーワードで宣言されたあらゆる変数も保持します。
直感に反して、'static ライフタイムを持つ項目が静的メモリに格納される場合もあれば、そうでない場合もあります。
const キーワードを使うと、値をコンパイル時に計算できます。結果の値は、変数名が使われる場所に直接インライン化され、静的メモリ位置ではなく、実行可能命令ストリーム内にエンコードされることがあります。

プログラムの実行可能コードも技術的には静的メモリ内に存在しますが、上の図ではそれを区別するために別のボックスを使っています。

静的メモリセクションの中には読み取り専用のものもあれば、書き込み可能なものもあります。これはエクスプロイトに関係しますが、今はこの詳細を無視して、「グローバル」が実際に何を意味するのかに集中しましょう。

静的メモリ内のデータは、プログラムの全ライフタイムにわたって利用可能です。開始時から終了時までです。
静的メモリはスレッド間で共有されます。これには同期上の危険（例: データ競合）や性能を低下させる回避策（例: グローバルロック/ミューテックス）があります。しかし、これは有用で便利でもあります。

スレッドとは何ですか？

プロセスには軽量な代替手段があります。それがスレッドです。複数のスレッドは、1つのプロセスのアドレス空間内に共存します。各スレッドはそれぞれ独自のスタックを持ちます（前のセクションのファイルからプロセスへの図を参照してください）。

マルチスレッドには、マルチプロセスに対して2つの重要な利点があります。

スケジューリング効率 - OS カーネルは、特定のカーネル空間データ構造を共有できることや、CPU レベルの最適化（例: Intel の「ハイパースレッディング」[^HyperThread] 技術）のおかげで、スレッドをより効率的にスケジューリングできます。

並行コンポーネント間のデータ受け渡し - スレッドはプロセスよりも容易かつ効率的にデータを共有でき、データ受け渡しの仲介役としてカーネルを待ったり依存したりする必要がないことがよくあります。静的メモリは、単一プロセス内の複数スレッド間で共有されるため、直接的な手段の1つです。

関数 recursive_count_down の単純化/非最適化されたアセンブリ（CPU が処理する命令ストリーム）を簡単に覗いてみましょう。 1行ずつ見ることはしません。しかし、いくつかの詳細はメモリレイアウトをよりよく理解する助けになります。まず、ソースコードを思い出してください。

#[inline(never)]
fn recursive_count_down(x: usize) -> usize {
    // Base case
    if x == 0 {
        println!("Boom!");
        return x;
    // Recursive case
    } else {
        println!("{x}...");
        return recursive_count_down(x - 1);
    }
}

https://godbolt.org を使って、-C "opt-level=z" フラグ（小さいコードサイズ向けの最適化であり、人間にとっての可読性にも寄与します）付きでアセンブリを生成します（結果はコンパイラバージョン⁷ によって異なる場合があります）。

example::recursive_count_down:
        push    rbx
        sub     rsp, 80
        mov     qword ptr [rsp + 8], rdi
        test    rdi, rdi
        je      .LBB0_1
        lea     rbx, [rsp + 8]
        lea     rax, [rsp + 16]
        mov     qword ptr [rax], rbx
        lea     rcx, [rip + .L__unnamed_1]
        lea     rdi, [rsp + 32]
        mov     qword ptr [rdi], rcx
        mov     qword ptr [rdi + 8], 2
        and     qword ptr [rdi + 32], 0
        mov     rcx, qword ptr [rip + core::fmt::num::imp::<impl core::fmt::Display for usize>::fmt@GOTPCREL]
        mov     qword ptr [rax + 8], rcx
        mov     qword ptr [rdi + 16], rax
        mov     qword ptr [rdi + 24], 1
        call    qword ptr [rip + std::io::stdio::_print@GOTPCREL]
        mov     rdi, qword ptr [rbx]
        dec     rdi
        call    qword ptr [rip + example::recursive_count_down@GOTPCREL]
        jmp     .LBB0_3
.LBB0_1:
        lea     rax, [rip + .L__unnamed_2]
        lea     rdi, [rsp + 32]
        mov     qword ptr [rdi], rax
        mov     qword ptr [rdi + 8], 1
        lea     rax, [rip + .L__unnamed_3]
        mov     qword ptr [rdi + 16], rax
        xorps   xmm0, xmm0
        movups  xmmword ptr [rdi + 24], xmm0
        call    qword ptr [rip + std::io::stdio::_print@GOTPCREL]
        xor     eax, eax
.LBB0_3:
        add     rsp, 80
        pop     rbx
        ret

.L__unnamed_3:

.L__unnamed_4:
        .ascii  "...\n"

.L__unnamed_1:
        .quad   .L__unnamed_3
        .zero   8
        .quad   .L__unnamed_4
        .asciz  "\004\000\000\000\000\000\000"

.L__unnamed_5:
        .ascii  "Boom!\n"

.L__unnamed_2:
        .quad   .L__unnamed_5
        .asciz  "\006\000\000\000\000\000\000"

このアセンブリは何を意味しているのでしょうか？

本書では、扱う範囲を適切に保つため、アセンブリは教えません。しかし、アセンブリを読めることは、システムプログラミングにおいていざというときに役立つ場合があります。また、これは本格的なバイナリ悪用を学ぶための前提条件でもあります。

バイナリ攻撃者側の知識に追いつくには、Practical Binary Analysis: Build Your Own Linux Tools for Binary Instrumentation, Analysis, and Disassembly⁸ を検討してください。Appendix A: A Crash Course on x86 Assembly は Intel マシン向けの手早い入門です。

ここでの目的に対しては、上記の2つの命令に注目してください。

sub rsp, 80（冒頭付近）- フレームをプッシュし、スタックポインター（SP）を80バイト減少させます。

add rsp, 80（末尾付近）- フレームをポップし、スタックポインター（SP）を80バイト増加させます。

このアセンブリスニペットでは多くのことが起きています。静的メモリを理解するうえで関連する詳細が1つあります。各フレームは各文字列の一意なコピーを割り当てていません。割り当てているのは、ASCII文字列を保持する静的メモリ位置への短い（ホスト整数幅の）ポインターだけです。

視覚的には、これは複数の再帰フレームが、出力の印字用に格納された同じ文字列をすべて参照していることを意味します。

静的文字列を参照するスタックフレーム。

これはスタック枯渇の観点では何を意味するのでしょうか？

劣化比率 - 静的メモリは、スタックメモリ使用量に対してほぼ（ポインター幅を除けば）1:N の負荷を持ちます。ここで、
- 1 は静的データ項目の単一コピーです。
- N は 1 個の項目への参照に対する再帰深度です。
- 1:N は アルゴリズムの空間計算量 に影響しません（スタックメモリの N:N データとは異なります）。
枯渇防御 - スタックオーバーフローDoSに対する堅牢化は、言語非依存のパターン（MISRA C 17.2）のレベルで有効です。なぜなら、それはハードウェアレベルで全体の（スタックおよび静的）空間計算量に影響するためです。
- 致命的な実行時障害ベクトルに関して、関数粒度の保証を享受できます！
- プログラム全体の保証については、最悪ケースのスタック使用量も計算し、各ターゲットプラットフォームがそれをサポートすることを確認すれば、この特定のバグクラスは排除されます⁶。

要点

ここで焦点を当てているスタックメモリは至るところで使われており、基本的なプログラミング抽象である関数呼び出しの実行時の足場を提供します。機械的には、同じ名前を持つ Last In First Out（LIFO）データ構造のように動作します。

スタック安全性、つまり実行時にスタック領域が枯渇しないという保証は、再帰を取り除くことで可能になります。 MISRA C ルール 17.2 に従うことによってです。しかし、プラットフォーム固有のスタック安全性に関する主張を行うには、それでも反復的なプログラム全体について最悪ケースのスタック使用量を計算する必要があります。

静的メモリは、グローバル変数と定数データを保持します。これはスタック安全性に意味のある影響を与えません。初期化、起こり得るミューテックス、およびデータキャッシュヒット率を除けば、静的メモリが実行時に与える影響は小さいかもしれません。

次のセクションでは、攻撃者の視点から、より一般的な種類の安全性、すなわち メモリ安全性 と 型安全性 を破る方法を探ります。

MISRA C: 2012 Guidelines for the use of the C language in critical systems (3rd edition). MISRA（2019）。 ↩
[個人的なお気に入り] Computer Systems: A Programmer’s Perspective. Randal Bryant、David O’Hallaron（2015）。 ↩
これは常に真であるとは限りません。現代的なコンパイラが行う可能性のある最適化の1つに「関数インライン化」と呼ばれるものがあります。これは、プログラマーが1つの長い関数を書いたかのように、呼び出し先の関数本体を呼び出し元の関数本体へ取り込むものです。「ホットループ」（多くのループ反復が実行される）内で呼び出される関数では、呼び出しのために各ループ反復でスタックフレームをプッシュすることに伴う小さなオーバーヘッドを避けることで、性能を向上させることができます。トレードオフはバイナリサイズです。インライン化された関数へのソースレベルの各呼び出し箇所は、コードの完全なコピーでなければなりません（呼び出される中央の場所が存在しないためです）。必要になることはまれですが、Rust の inline 属性マクロ⁹ を使うと、この特定の動作を制御できます。 ↩ ↩2
memset. Linux マニュアル（2022年アクセス）。 ↩
zeroize. Tony Arcieri（2022年アクセス）。 ↩
cargo-call-stack. japaric（2023年アクセス）。 ↩ ↩2
-C "opt-level=z" とともに rustc v1.71 を使用しました。 ↩
[個人的なお気に入り] Practical Binary Analysis: Build Your Own Linux Tools for Binary Instrumentation, Analysis, and Disassembly. Dennis Andriesse（2018）。 ↩
The Rust Reference: The inline attribute. The Rust Team（2022年アクセス）。 ↩

Keyboard shortcuts

High Assurance Rust: Developing Secure and Robust Software 日本語版

保証の観点：スタック安全性

スタック

プロセスの最大スタック領域を使い尽くす

スタック安全性のための堅牢化

静的メモリ

要点