きっかけ

大学のC言語プログラミングの講義で、以下のような課題がありました。

入力が中断されるまで繰り返し、整数である文字列を標準入力から受け取り
それを事前に確保した長さ100程度の配列に格納したうえで
その最大値と最小値を計算せよ。

ただし、(ポインタの講義なので)配列へはインデクサ [] ではなく
ポインタを通してアクセスせよ

講義資料には、ヒントとなるようなサンプルプログラムも掲載されており、それも考慮すると以下のような実装になるのではないでしょうか？¹

int x[100];
int *ptr = x;

for (int i = 0;; i++)
{
    printf("please input number #%d: ", i);
    if (scanf("%d", ptr) == EOF)
    {
        break;
    }
    ptr++;
}

しかしこれでは、確保した配列の長さ 100 を超えて値を書き込むことができてしまいます。
講義資料の別の個所には

配列の範囲を超えてポインタを移動させると意味のない値になる

とあります。おそらく多くの人がそう思っていることでしょう。
しかし、実際にはそうではないのです。

予め断っておきますが、これは初心者向けのC言語プログラミングの講義の内容であり、課題の内容が悪いとかそのようなことを言う意図は全くありません。

しかし、このようなプログラムがあったときに、多分多くの人が想像するよりずっと怖いことができてしまうので、今回はそれを紹介したいと思います。

なお、この記事を書いている私自身、C言語についてはそんなに詳しくありませんので間違いなどありましたらご指摘ください。

メモリの使い方の話

さて、プログラム内で使用するメモリには大きく分けてスタックとヒープがあり...という話は有名なので割愛します。知らない人は調べてください。

さて、私がメインで書いている C# の「配列」はヒープ確保ですが、C言語の配列はスタック確保です。C# だと stackalloc と同じです( 型は T[] でなく、 Span<T> になりますが)。

で、このスタックの使い方なんですが、関数に入るときに、その関数で必要な分のスタック領域を確保します。のちに関係してくるので、この確保の仕組みを簡単に説明しておきます。なお、あんまりわからなくても本記事の核心には支障ないです。

まず、ある関数が確保しているスタック領域は、その始まりのアドレスとその終わりのアドレスによって表現されます。なにかすごい概念が存在しているわけではなく、単にアドレスが2つあります。

具体的なイメージを見ていきましょう。(実際はもう少し複雑ですが)。

void main()
{
    int a;
    int b;
    hoge();
}

void hoge()
{
    int c;
}

int が 4byte と仮定すると、この main 関数では 8byte のスタック領域が必要です。なので

データ名	値
スタックの始まり	0
スタックの終わり	8

という風にデータが書き込まれ、スタックが確保されます。
このうえで、一例として、a のアドレスは 0 、 b のアドレスは 4 になります。

そして、別の関数 hoge を呼び出したことで、新たなスタック領域が必要になります。
まず、今までの「スタックの終わり」を「スタックの始まり」に代入します。
こうすることで、今までと違う新しい領域に書き込むことになります。
あとは、「スタックの終わり」を、新しい「スタックの始まり」から必要量だけ大きい値に設定するだけです。
hoge は 4byte が必要なので、

データ名	値
スタックの始まり	8
スタックの終わり	12

としましょう。

しかし、これだと1つ問題が残ります。もともとの「スタックの始まり」と「スタックの終わり」をどこかに記憶しておかないと、 hoge 関数から抜けて main 関数に戻ることができなくなってしまうのです。

ですから、もともとのデータを、main 関数に割り当てたスタック領域と hoge 関数に割り当てたスタック領域の間に記憶しておくことにします。

アドレス	用途
0	ローカル変数 `a`
4	ローカル変数 `b`
8	`main` 関数のスタックの始まり
12	`main` 関数のスタックの終わり
16	ローカル変数 `c`

として、hoge 関数に割り当てるスタック領域は

データ名	値
スタックの始まり	16
スタックの終わり	20

とします。

あとは、hoge 関数から抜けるときに、記憶しておいた main 関数における始まりと終わりの値をスタックから読みだして、もとに戻してあげます。

データ名	値	どこから？
スタックの始まり	0	アドレス `8` に格納しておいた値
スタックの終わり	8	アドレス `12` に格納しておいた値

これで、hoge 関数が使用していたスタック領域は解放されました。

実際にやっていることは、この2つのアドレス値の出し入れや加算だけですので、参照カウンタやガベージコレクタなどに比べ、極めて低コストでメモリを確保・解放することができます。関数を抜ければ勝手に解放されるため、解放漏れの心配もありません。とても効率的な仕組みです。

実際のプログラムも、このような形でスタック領域というものが確保・解放されるのですが、少し違う点があります。

何故か² マイナスの方向に確保していきます。

そのため、先ほどの例だと、

アドレス(相対値)	用途
-20	ローカル変数 `c`
-16	`main` 関数のスタックの始まり
-12	`main` 関数のスタックの終わり
-8	ローカル変数 `a`
-4	ローカル変数 `b`
0	スタックの原点(アクセス不可)

みたいになります。main 関数の内部ではプラスの方向に並べるので、a => b の順ですが、hoge 関数用の領域を確保する場合はマイナス方向に確保されます。

今回は説明のため簡略化しましたが、実際には 16 の倍数などキリのいい数字になるようにスタック領域が確保され、今回のように 4byte しか必要がなくてもそれ以上の領域が確保されることがままあります³。

手元の環境の場合、x86_64 の CPU と 64bit の Linux という組み合わせなので、スタックの始まりと終わりはそれぞれ、rbp と rsp という名前の2つのレジスタに記憶されます。

配列のその先へ

前置きが長くなりましたが、ここまで理解すると配列のその先に何があるか想像がつくのではないでしょうか。

スタックはマイナス方向に確保していっているので、配列のその先に存在するのは、その関数を呼び出したときに入れた「スタックの始まり」と「スタックの終わり」のアドレス、そしてその関数を呼び出した関数のローカル変数...のはずです。

確かめてみましょう。
64bit環境なので、説明の都合上 int だった箇所を long に変更していますが、できることは変わりません。

main 関数で宣言したローカル変数を配列のその先から探し出し、その値を書き換えてみたいと思います。

#include <stdio.h>
#include <stdlib.h>

void hoge();

int main()
{
    long fuga = 0xDEADBEEF;
    printf("%lx\n", fuga);
    hoge();
    printf("%lx\n", fuga);

    return 0;
}

void hoge()
{
    long x[100];
    int i;
    for (i = 100;; i++)
    {
        printf("log> %lx\n", x[i]);
        if (x[i] == 0xDEADBEEF)
        {
            printf("local variable found!! index={%d}\n", i);
            x[i] = 0x12345678;
            break;
        }
    }
    return;
}

手元の環境で実行すると以下の出力が得られました。

deadbeef
log> 7ffff7fbe2e8
log> ae16a17c142f9100
log> 7fffffffde90
log> 5555555551a0
log> 7fffffffdf80
log> deadbeef
local variable found!! index={105}
12345678

と、ちゃんと配列のその先にローカル変数が存在し、値が書き換えられることが証明されました。
怖いですね。

さて、さきほどの理論に沿えば、配列 ( hoge 関数の確保したスタック領域 ) と main 関数のローカル変数の間には、「スタックの始まり」や「スタックの終わり」が保存されているはずです。

いつからか知らないですが、vscodeのデバッグ機能でレジスタの値も見れるので、main 関数にブレークポイントを挿入して rbp と rsp の値を見てみましょう。

さきほどの実験で、ローカル変数を探すまでに見つかったすべての値をログ出力していたので見比べてみてください。ちゃんと rbp および rsp の値を見つけることができていますね。

しかし、その2つの値の間に何か別の値が挟まっているのが確認できます。
最後に、この値で遊んでみましょう。

リターンアドレス

関数を呼び出すときに記憶しておかねばならない値として、「スタックの始まり」、「スタックの終わり」以外に、大事なものが1つあります。関数の呼び出しが終了したときにどの命令から再開すればいいのか、です。

これは、次に実行すべき命令のアドレスという形で、rbp や rsp の値と同じように、スタックに押し込まれます。リターンアドレスなどと呼ばれるやつです。

今回、rbp と rsp の間に挟まっていたものはおそらくこのリターンアドレスだと考えられますから、実験してみましょう。

戻り先は main 関数の途中ですから、おそらくそのアドレスは main 関数のアドレス(関数ポインタ) からほんのちょっとだけ離れた場所にあると考えられます。試してみましょう。

#include <stdio.h>
#include <stdlib.h>

void hoge();

int main()
{
    long fuga = 0xDEADBEEF;
    printf("%lx\n", fuga);
    printf("%lx\n", &main);
    hoge();
    printf("%lx\n", fuga);

    return 0;
}

void hoge()
{
    long x[100];
    int i;
    for (i = 100;; i++)
    {
        printf("log> %lx\n", x[i]);

        if (x[i] == 0xDEADBEEF)
        {
            printf("local variable found!! index={%d}\n", i);
            x[i] = 0x12345678;
            break;
        }
    }
    return;
}

deadbeef
55969d09e189
log> 7efd9f57c2e8
log> 4f767465a0525d00
log> 7ffe232735a0
log> 55969d09e1d8
log> 7ffe23273690
log> deadbeef
local variable found!! index={105}
12345678

あくまでアドレスなため、さきほどの実行結果とは異なることに留意してください。
rbp と rsp の間にある値は、main 関数のアドレス(2行目)からほんの少し進んだ値であることがわかります。

55969d09e1d8 - 55969d09e189 がその進み分です。ミスりそうな16進数の計算ですが、windows標準の電卓の「プログラマ電卓」機能によれば、4F(79) だそうです。優秀。

せっかくなので逆アセンブルして確かめにいきます。
gdb を起動し、disas <関数名> で逆アセンブルできます。
出力をおなじみの intel 記法にするにはあらかじめ、set disassembly-flavor intel しておきます。
set logging on をしておくと、ファイルにも出力されるので記事を書くときに便利です。

Dump of assembler code for function main:
   0x0000000000001189 <+0>:	endbr64 
   0x000000000000118d <+4>:	push   rbp
   0x000000000000118e <+5>:	mov    rbp,rsp
   0x0000000000001191 <+8>:	sub    rsp,0x10
   0x0000000000001195 <+12>:	mov    eax,0xdeadbeef
   0x000000000000119a <+17>:	mov    QWORD PTR [rbp-0x8],rax
   0x000000000000119e <+21>:	mov    rax,QWORD PTR [rbp-0x8]
   0x00000000000011a2 <+25>:	mov    rsi,rax
   0x00000000000011a5 <+28>:	lea    rdi,[rip+0xe5c]        # 0x2008
   0x00000000000011ac <+35>:	mov    eax,0x0
   0x00000000000011b1 <+40>:	call   0x1090 <printf@plt>
   0x00000000000011b6 <+45>:	lea    rsi,[rip+0xffffffffffffffcc]        # 0x1189 <main>
   0x00000000000011bd <+52>:	lea    rdi,[rip+0xe44]        # 0x2008
   0x00000000000011c4 <+59>:	mov    eax,0x0
   0x00000000000011c9 <+64>:	call   0x1090 <printf@plt>
   0x00000000000011ce <+69>:	mov    eax,0x0
   0x00000000000011d3 <+74>:	call   0x11f7 <hoge>
   0x00000000000011d8 <+79>:	mov    rax,QWORD PTR [rbp-0x8]
   0x00000000000011dc <+83>:	mov    rsi,rax
   0x00000000000011df <+86>:	lea    rdi,[rip+0xe22]        # 0x2008
   0x00000000000011e6 <+93>:	mov    eax,0x0
   0x00000000000011eb <+98>:	call   0x1090 <printf@plt>
   0x00000000000011f0 <+103>:	mov    eax,0x0
   0x00000000000011f5 <+108>:	leave  
   0x00000000000011f6 <+109>:	ret    
End of assembler dump.

<+74> が、今問題となっている hoge 関数への call 命令です。そして、その次の命令は <+79> ですから、先ほど計算した 79 と一致します。

リターンアドレスの改ざん

では、リターンアドレスであることが証明できたので、リターンアドレスを書き換えてみましょう。
今回は、まったく関係のない piyo 関数を用意し、そのアドレスにリターンアドレスを書き換えることで制御フローを改ざんしてみたいと思います。

#include <stdio.h>
#include <stdlib.h>

void hoge();

void piyo();

int main()
{
    long fuga = 0xDEADBEEF;
    printf("%lx\n", fuga);
    printf("%lx\n", &main);
    hoge();
    printf("%lx\n", fuga);

    return 0;
}

void hoge()
{
    long x[100];
    int i;
    for (i = 100;; i++)
    {
        printf("log> %lx\n", x[i]);

        if (i == 103)
        {
            printf("return address found!! index={%d}\n", i);
            x[i] = &piyo;
            break;
        }
    }
    return;
}

void piyo()
{
    printf("ぴよぴよ\n");
}

deadbeef
56027e6a8189
log> 7fc3460e62e8
log> fb33a6b31da57300
log> 7ffe02a871c0
log> 56027e6a81d8
return address found!! index={103}
ぴよぴよ
5647 Segmentation fault      ./run.out

「ぴよぴよ」と標準出力に表示されました！
これは、リターンアドレスを書き換えたことで実際に piyo 関数の中身が実行されたことを意味します。
そして、main 関数に戻れなくなりセグフォしました。

と、なんとローカル変数の値だけでなく(それだけでも十分怖い！)、制御フローまで書き換えることができてしまうわけです。

さいごに

ここで最初のプログラムに立ち戻ってみましょう。

int x[100];
int *ptr = x;

for (int i = 0;; i++)
{
    printf("please input number #%d: ", i);
    if (scanf("%d", ptr) == EOF)
    {
        break;
    }
    ptr++;
}

今回はプログラムの内部から、配列の境界のその先に値を書き込みましたが、最初のプログラムを何も変更せずとも、頑張って100行の標準入力を与え、そのうえで今回の実験で書き込んだような値を標準入力に与えることで、実験で示したようなローカル変数の書き換えやリターンアドレスの書き換えといった操作を行うことができます。

したがって、私のメイン言語である C# をはじめとする後発のメモリ安全な言語では、多少の実行時間コストを払ってでも、必ず境界値を超えないことを言語的に保障するしくみが実装されています。
境界値を超えたアクセスを試みると即時に、例外やエラー、パニックなどが発生し、その時点で実行が中断されるためこのような危険が発生することを回避しています。

特にプログラミング初心者の頃に憎んでいた IndexOutOfRangeException ですが、こうみるとなんだか有難く感じますね。

補足説明

コメントをいただいた箇所を中心に補足説明をつらつらと書いていきます。

「きっかけ」セクションの課題プログラムに関して

あくまで、大学の一講義に対する「課題」の答案であり、現実世界でのプログラムではありません
- 指定された(古い)条件でエラー・警告なくコンパイルされる必要があります
- ポインタについての講義の課題ですので、ポインタを使用する必要があります
  - 加えて、インクリメント・デクリメントのみで操作せよとの条件です
- 現実世界のプログラムとして優れていることより、講義内容に即していることが評価されます。
- そもそも答えを知りえないので、課題の解答として正しいかもわかりません。
講義資料中の、標準入力を受け取る例のコードが無限ループです
- 講義内容だけをもとにコーディングすると、無限ループ実装になる可能性が高いでしょう。
  - 知らないのが悪い、というのは間違ってはいないかもしれないですが、初心者に知ることを求めるのはあまりに酷です。
  - このように、攻撃手法や危険性を発信することで「知らない」を減らせますし、それがコミュニティの利益であり、責務であるように思われます。
実際の講義の課題の解答から意図的に改変しています
- コピペ(盗用)の防止のためです。
  - 不正行為に加担もしたくないですし、疑われたくもないので。
  - 最近コピペが多いようで、大学もこのあたり厳しくなっています。
- このままコピペして課題の解答の一部として利用すると、不正解になります。
「きっかけ」であり、このコードに固有の問題について論じているわけではないです。
- 「もしかしてこの課題のコード、危ないのでは？」と思ったのが今回の実験の動機だったにすぎません。
- このコードについて深くとやかくいうことに本質的な意味はほとんどありません。

配列の境界の先の「意味のない値」に関して

「意味のない値」 = 「未初期化・未割り当て」くらいの解釈です
- でも「未初期化・未割り当て」ではないよね、という話
１つに、「これはスタックポインタの退避先です」「これはリターンアドレスです」と説明できる
- 用途があって、使われているのだから意味はあるよね
2つ目に、プログラムに不正な動作をさせることができる
- 特に悪意あるユーザー、攻撃者から見れば非常に大きな意味があるでしょう

「未定義」に関して

C言語の規定としては未定義で当然
- 配列の境界外アクセスを積極的に利用したコードなんて、もちろん書くべきではない
- 当然、未定義かどうかなんてユーザーや攻撃者には知ったこっちゃない
端的には実装依存
- とはいえ、現代の大抵のコンピュータで有効であると思われる
  - 本稿で説明したようなスタックの概念があれば原理的に通用する
- コンパイラ・実行環境(のABI)の組で決定論的と思われる
  　- 少なくとも本稿で実験した組では成立する
  - 再現性は十分にある
- 「実装依存なので、一部の環境では危険ですけど」は許されない
  - 一箇所でも攻撃されたらまずい
  - 可能な限り安全であるように努める責務はあるよね
現実的に攻撃できるならアウト
- まぁまぁ有名な攻撃手法ではあると思われる

実証コードの成立条件

そもそも「実証コード」
- 関係のないコードを省いて、論点に関連するコードだけにしている
  - 実世界のコードとは異なるのが当然
- この「実証コード」が成立しないケースを探すことにあまり意味はない
  - 同じ手法の別のコードが通用するならば何の意味もないので。
スタックに書き込みができてしまうので呼び出し元関数のローカル変数やリターンアドレスが改ざんできるという話
- スタックに　あるものしか書き換えられるわけがない
- ローカル変数がスタックに配置されるケース(よくある)
- 関数呼び出しが発生するケース(よくある)
「どんなケースを想定した実証なのか」を常に意識せねばならない
- あくまで想定される状況を簡略化して実験してるだけなので、主は実際のケース

関数をインライン化しない

本実験コードは「関数を呼び出す」というケースを再現しています
- 実際に関数なしでコーディング、あるいはすべてをインライン化することは非現実的
  - 妥当な仮定と考えられる
- インライン化などで関数呼び出しが消滅すれば当然再現しないです
  - ただ実証コードではなく実際のプログラムなら全部インライン化はできないわけで

ローカル変数をスタックに確保する

ローカル変数をスタックに確保するケースを再現しています
- 実証コードではローカル変数であるコード上の意味がないです
  - 定数でも(正常なコードとしては)よいはず
これまたスタックを全く使わないということ非現実的
- 妥当な仮定と考えられる
当然、引数を配置すべきレジスタ(環境依存)に、即値でロードしたら再現しません
- もちろん、実際のプログラムで全部そうすることはできないわけで

「ローカル変数をスタックに置く」というのは、以下のような操作のことです

   0x0000000000001195 <+12>:	mov    eax,0xdeadbeef
   0x000000000000119a <+17>:	mov    QWORD PTR [rbp-0x8],rax

まず eax レジスタに即値 0xdeadbeef を配置します。
次に、rbp から8byteオフセットされた位置、すなわちスタックの一番底にrax レジスタの値、つまり 0xdeadbeef を書き込んでいるわけです。
[] が目印となるように、これはメモリへの書き込み操作です。

一方、コメントにあるような最適化コードでは

main:
        push    rbx                   
        mov     ebx, 3735928495      
        mov     edi, OFFSET FLAT:.LC2
        xor     eax, eax
        mov     rsi, rbx            
        call    printf
        xor     eax, eax
        call    hoge

となり、値 3735928495 はレジスタ内で完結しており、メモリには配置されません。
( ebx -> rsi(引数))
とはいえ、これは実証コードゆえこのローカル変数が「意味のある用途に使用されていない」ことに起因する面が大きく、実際のコードで必ずレジスタで完結するというものではありません。

環境依存性

本稿で掲載した実行結果は一例です
- アドレスや目標のインデックスは環境によって変動しうる値です
  - ただし、問題にはなりません
- ただし、アドレスが変わろうと存在はします
  - なお、同一プログラム内でのアドレスの相対値はコンパイルし直さない限りほぼ同じです
本稿で行ったように、メモリを観察できれば目標とする値を発見できます
- これには別の脆弱性が必要かもしれませんが、普遍的な手法となります。
- 攻撃者が改ざんしたいショッピングサイトのポイント、ゲームのスコア...、どれもそんなにありふれた数値ではないかもしれません
多少時間がかかろうが、数回失敗しようが、一回成功すれば攻撃成功です
- たまたま探している値と似た別の値があってダマされた...なんて意味がありません
  - 何回も解析、あるいはトライすればいいのですから

実際に提出した課題をもとにしていますが、パクられたくないので微妙に変えています。 ↩
知っている人がいたら教えてください... ↩
というか、そうしないと scanf 関数などを呼んだときに落ちます。ハマりポイント。 ↩