C++のpwn/revで使うSTLコンテナの構造とバグパターン一覧
2021-11-30 23:57:32 Author: ptr-yudai.hatenablog.com(查看原文) 阅读量:139 收藏

この記事はCTF Advent Calendar 2021の1日目の記事です。明日は...誰もいません！誰かなんか投稿してくれ〜。

f:id:ptr-yudai:20211201000502j:plain:w32:h24 *1

2年前pwnを始めた時にC++のpwnがよぐ分がんなかったので、当時の自分に向けてなるべく詳しく説明します。*2 当時C++のpwnが難しいと感じた主な原因は、std::stringやstd::vectorなどの「よく分からん型」と、テンプレートとか仮想メソッドとかの「よく分からん挙動」の存在だと思います。 C++のrevが苦手なのも同じだと思います。*3 特に型(コンテナ)に関しては仕様としては定義されていますが、実装はSTL(Standard Template Library)依存です。 今回はg++でコンパイルされると（libstdc++を使うと）どうなるかを説明します。

といっても私はSTLのソースコードをほとんど呼んでおらず、いつも通り経験則（と、この記事のためにいっぱい検証した結果）を元に書いていますので、大嘘書いてたら教えてください。*4 ソースコードを読みたい人はこの辺を見れば良いと思います。 64-bitを対象にするのでオフセットとかは32-bitと違いますが、挙動や構造体のメンバは32-bitでもほとんど同じだと思います。

では、実際のところpwnでSTLコンテナの知識がどの程度必要かというと、std::stringとstd::vectorだけ知っておけば十分だと思います。 他の種類のコンテナを破壊してexploitに繋げるような問題は私が過去に出題したものを除けばほとんど思いつきません。

std::string

std::stringはpwnで最も頻出で基本的な型ですが、最も奇妙な挙動をする型でもあります。 この型はNULLを含む任意のデータを入れられます。

基本構造

次のような0x20バイトの構造になっています。

+00h: <データへのポインタ>
+08h: <データのサイズ>
+10h: <データ領域の容量>あるいは<データ本体+0h>
+18h: <未使用>あるいは<データ本体+8h>

まずは当たり前ですがデータ本体へのポインタを持っています。 使用時にこのポインタがNULLだと例外が発生します。 このポインタは.c_str()メソッドで返されるポインタそのものです。

次にデータのサイズも持っています。このサイズは大きすぎると例外が発生します。（経験的には32-bitを超えるような値を入れると例外が起きるが、実際のところは知らん。） データサイズは.size()メソッドで返ってくる値で、std::coutで文字列を出力する際の出力文字数にもなります。

ここからが奇妙なのですが、データサイズが15バイト以下のときと16バイト以上のときで挙動が変わります。

データサイズが15バイト以下のときはstd::stringのオフセット+10hにデータ本体が格納されます。 したがって、その場合データへのポインタはstd::stringの先頭+0x10を指します。

データサイズが16バイト以上のときはmallocで別途領域が確保され、そこにデータ本体が格納されます。 この場合オフセット+10hにはデータの容量が記録されます。 容量とは「これまでその領域に入った最も長いデータ」であり、malloc_usable_sizeで返ってくるような値ではありません。 詳しくは後述の代入演算で説明します。

例えば"AAAA"を代入すると次のようになります。

X+0x00: X+0x10
X+0x08: 4
X+0x10: 0x??????0041414141
X+0x18: 0x????????????????

一方、"AAAABBBBCCCCDDDD"を代入すると次のようになります。

X+0x00: Y
X+0x08: 0x10
X+0x10: 0x10
X+0x18: 0x????????????????

Y+0x00: 0x4242424241414141
Y+0x10: 0x4444444443434343

挙動

入力

std::cinで入力すると、データのポインタへストリームからデータが入力されます。 入力データが+10hにあるデータの容量（あるいは内部にデータを持つ場合は16バイト）を超えると再確保が発生します。 再確保は「元のデータ容量 x 2」のサイズだけ確保されます。 元が0x40バイトなら再確保で0x80バイトまで入るようになります。

ただmallocするサイズが倍々に増えるというだけで、malloc_usable_size()がそのまま容量になる訳ではないです。 （つまりメモリ的には0x48バイト入るけど容量は0x42バイトみたいなこともあり得る。）

pwnの文脈ではデータポインタを偽のポインタにし、データ容量を十分大きな値にすれば任意アドレス書き込みが作れます。 ただstd::cinでAAWする問題は個人的に見たことがなく、後述の代入演算を使ってAAWする傾向にあると思います。

出力

std::coutで出力すると、データのポインタからデータサイズ分だけストリームに出力されます。

pwnの文脈ではデータポインタを偽のポインタにし、データサイズを適当な値にすれば任意アドレス読み込みが作れます。

代入

std::stringの代入はデータの中身がコピーされます。

代入元のデータサイズより代入先の容量の方が大きい場合、代入先のポインタにそのままデータがコピーされ、データサイズが更新されます。

代入元のデータサイズより代入先の容量の方が小さい場合、代入先のデータポインタに再確保が発生してからデータがコピーされます。

結合

結合+演算が使われると新しいstd::stringが確保されます。 結合する2つのデータのサイズの和だけの容量で確保され、確保された領域に結合データがコピーされます。 もちろん結合するデータのサイズ和が15バイト以下ならstd::string内部にデータが入ります。

std::vector

std::vectorはSTLとしてstd::stringに並んで最もよく使われる型です。 可変長配列を保持するための型で、構造は自然ですが挙動が非常に複雑で脆弱性を生みやすいためC++ pwnのSTL関連の問題の多くはstd::vectorに関するものになっています。

基本構造

std::vectorは可変長配列であるため、容量やサイズに関する情報を保持する必要があります。 STLではこれらを次のようにポインタで保持しています。

+00h: <配列の先頭の要素へのポインタ>
+08h: <配列の最後の要素の次の位置へのポインタ>
+10h: <配列の容量的な限界位置のポインタ>

したがって、std::vectorは0x18バイトの構造体になります。 std::vectorは生成時に型が決定するので、構造中には1要素のサイズなどの情報は含まれておらず、これらはコンパイル時に機械語にハードコード（というか単に要素サイズに合わせたコードが生成）されます。 挙動については後述しますが、std::vectorの要素はmallocを使ってヒープ上に確保されます。

std::vectorが先頭へのポインタを持つのは自然です。 次に+08hにあるポインタですが、これは次にpush_backした際に入れられる位置を示します。 また、+10hにある容量的な終端のポインタは、push_backした時に再確保が必要かを判断するためのポインタです。 例えばはじめint型の要素を3つ保持すると、サイズと容量は共に12バイトですが、pop_backするとサイズは8バイトになります。 ここから更にpush_backするとき、サイズが8バイトなのに対して容量は12バイトあるので、再確保の必要は無いと判断されます。

例えばint型で[1,2,3,4,5]を順にpush_backした後にerase(vec.begin());すると次のようになります。

+00h: X
+08h: X+0x10
+10h: X+0x14

X+0x00: 2
X+0x04: 3
X+0x08: 4
X+0x0c: 5
X+0x10: ? (実装依存だが通常5が残る)

例外的な構造

【情報提供：@keymoon】

知らなかったのですが、std::vectorは型がboolのときに構造が変わります。 bool型のときは最小単位が1ビットのビット列としてメモリ上に確保され、std::vectorの構造が変わります。

+00h: <ビット列の先頭へのポインタ>
+08h: <不明(ビット列の先頭へのオフセットと思われる)>
+10h: <次にビットを入れるブロックへのポインタ(8バイト単位)>
+18h: <ビット単位でのオフセット>
+20h: <容量的な限界位置のポインタ>

例えばtrueを66回push_backすると

+00h: buffer
+08h: 0
+10h: buffer+0x08
+18h: 2 (=66%64)
+20h: buffer+0x10

となります。

挙動

std::vectorにおいては要素へのアクセスおよび再確保に関する挙動の理解が最も重要です。

要素数と容量の計算

要素数を返すsizeメソッドは(<次にpushされる位置のポインタ> - <先頭ポインタ>) / <1要素のサイズ>を計算しています。 同様に容量を返すcapacityメソッドは(<容量的な終端のポインタ> - <先頭ポインタ>) / <1要素のサイズ>を計算しています。

要素へのアクセス

次のように配列の要素へアクセスするとき範囲チェックは実行されません。

std::vector<int> v = {1, 2, 3};
...
v[index] = value;

したがって、上のようなコードを書くと簡単に範囲外参照を起こします。 一方、これを防ぐためにはatメソッドがあります。

v.at(index) = value;

この場合範囲外参照が起きる（すなわち v.size() <= index である）とき例外を発生します。 あくまで内部でsizeを呼んでいるだけなので、他の脆弱性などで事前に終端へのポインタ等を書き換えられる場合はatメソッドの範囲外参照を突破できます。

要素の挿入・削除

push_back, pop_backの他に、insertで途中に要素を挿入、removeで途中の要素を削除できます。 挿入する際は、挿入位置より後ろのデータが末尾から順に1要素分だけ後ろにずらされます。 削除する際は、削除位置より後ろのデータが削除位置から順に1要素分だけ前にずらされます。

vectorの拡大

std::vectorに対してpush_backする前に、容量が足りない場合（すなわち<要素終端>==<容量終端>のとき）reallocを使った再確保が発生します。 ここで注意したいのが、ヒープの状態によっては再確保発生時に配列の先頭のアドレスが変わる可能性があるという点です。 これは後述するイテレータで非常に重要になります。

vectorの縮小

std::vectorはどれだけpop_backやremoveしても縮小のreallocは発生しません。 しかし、shrink_to_fitメソッドを呼ぶと現在のcapacityに合うように配列が再確保されます。

また、pop_backやremoveしたとき、一番後ろにあったデータはメモリ上では残ったままになります。 （0埋めなどはされません。） この挙動も後述するイテレータで割と重要になることがあります。

イテレータ

範囲外参照以外でvectorに関する脆弱性で見かけるのがイテレータの誤った使用です。 C++においてイテレータは次のように使います。

for (auto element: array) {
  ...
}

上のコードは次のコードと等価です。

for (vector<T> it = array.begin(); it != array.end(); it++) {
  T element = *it;
  ...
}

さて、ここで問題となるのが、上記のfor文の中でarrayに対して要素が追加されたり、あるいは削除されたりするとどのような挙動が発生するでしょうか。

ループ中での要素追加

ループ中にvectorを要素を追加するのは脆弱性を生みます。

先に説明した通り、vectorは容量を超える際に再確保が発生します。 もちろん再確保で同じアドレスが使われる保証は無いので、通常再確保が発生するとvectorの要素のアドレスが変わります。 一方でイテレータは単なるポインタなので、古いアドレスに対して処理を続けます。

したがって、ループ中にpush_backなどをするとUse-after-Freeが発生します。

ループ中での要素削除

まず、次のように記述した場合array.end()は毎回評価されます。 （for文内部でarrayに対する副作用が発生する場合最適化しても必ず評価されます。）

for (vector<T> it = array.begin(); it != array.end(); it++)

したがって、多くの場合は要素を削除してもfor文は正しく配列の最後まで走ってくれます。

しかし、もしfor文の最後で削除が発生するとどうなるでしょうか。 最後のイテレーションに突入する段階では条件

it != array.end()

は成立します。なぜならitは終端の1つ前、すなわち++it==array.end()の状態だからです。 ここで削除が発生するとarray.end()は1要素分小さくなります。 一方次のfor分に突入する際it++が走るため、次のイテレーションでもit != array.end()が成立してしまいます。

このようにイテレーションのカーソルと終端のポインタがすれ違ってしまうことでfor分が止まらなくなります。 for分が止まらないので通常はクラッシュするか例外を投げて死にますが、例外を補足している場合は死なない可能性もあります。 したがって、配列の後ろに偽の要素を入れておけば、それに対する処理が発生します。

通常このようなバグは落ちるのでexploitableにはならないことが多いですが、CTFでは私が観測しただけで過去に3回出題されています。

std::list

std::listは機能的にはstd::vectorと似ていますが、頻繁に中間の要素を削除したり、要素をリストの中間に追加したりする際に高速です。

基本構造

std::listは双方向リストですので、fdとbkに相当するポインタを持っています。 まず、std::listの変数そのものは次のような0x18バイトの構造になっています。

+00h: <forwardポインタ>
+08h: <backwardポインタ>
+10h: <要素数>

sizeメソッドを呼ぶと+10hにある要素数が返されます。 std::vectorと違って要素数の取得にO(n)かかってしまうので要素数データを保持していますが、これは表面的な情報でイテレータなどの内部では使われません。

次に要素そのものはヒープに確保され、次のような構造になっています。

+00h: <forwardポインタ>
+08h: <backwardポインタ>
+10h: <データ実体>

極めて自然ですね。

挙動

イテレータ

std::vector同様にstd::listにもイテレータがあります。

std::listのイテレータはforwardポインタを辿るので、ループ中にリストに要素を追加したり、削除したりしても通常問題は起きません。 ただし、現在処理している箇所のデータを削除した場合、forward/backwardポインタが破壊されるのでunsound behaviorになります。 特にglibc mallocの場合、tcacheやfastbinのリストのポインタがforwardの位置に入ってしまうので、既にfreeされた別領域につながる可能性があります。 とはいえイテレータの終端がなくなるため、何か都合の良い条件でbreakしない限り100% Segmentation Faultを起こします。

その他

その他CTF的なことを強いて言うならstd::listをローカル変数として定義した場合、ヒープにスタックのアドレスが乗っかることになります。 リークできると嬉しいかもですね。

std::forward_list

片方向リストです。

基本構造

トップは8バイトで、先頭要素へのポインタを指しています。

+00h: <forwardポインタ>

std::listと違って要素数を持っていないためsize()メソッドが用意されていません。

ポインタの先にあるデータはもちろん次の要素へのポインタとデータ本体を持っているだけです。

+00h: <forwardポインタ>
+08h: <データ実体>

std::listと違って終端要素のforwardポインタはNULLになります。

挙動

std::listと同じなので特に書くことはないです。 ところで、cpprefjsのforward_lsitのページに

また、forward_listはリンクリストの性質上、挿入・削除のような破壊的操作を行なってもイテレータは無効にならない。

って書いていますが、これは大嘘です。 std::listと同様に挿入は良いですが、イテレータが現在指している要素を削除するとunsound behaviorになります。 公式ではちゃんと

However, an iterator or reference referring to an element is invalidated when the corresponding element is removed (via erase_after) from the list.

と書かれています。

std::pair

std::pairは名前の通り、任意の型の2つの変数を持てる型です。

std::pair<T0, T1> v;

のように宣言し、v.firstとv.secondでそれぞれ1つ目、2つ目の要素にアクセスできます。

基本構造

std::pairは次のように愚直な構造をしています。

+00h: <first>
+XXh: <second>

secondのオフセットはfirstのサイズに依存します。

挙動

特筆すべきことはありません。

std::variant

C++17かそこらで追加された型で、unionみたいに1つの変数が複数の型を持てるという働きをします。 union型との違いは、std::variant型変数への代入が発生すると自動的に型情報も付与されるという点です。 なのでstatic_castとかをしない限りType Confusionが起こらないという利点がありますが、自作クラスをstd::variantに入れる場合はデストラクタやコピーコンストラクタなどを正しく設定しないとUse-after-Free等を起こしやすいという注意点もあります。

基本構造

std::variantは次のような構造をしています。

+00h: <持ち得る型のunion>
+XXh: <型情報> (通常1バイト)

つまり、union型の後ろに1バイトの型情報が付加された形になります。 unionの部分はもちろん最もサイズの大きい型に合わせられます。 例えば

std::variant<std::string, long, bool> v;

なら、std::stringが最大で0x20バイトなので

+00h: union { string, long, bool }
+20h: 型情報(0, 1, 2のいずれか)

となります。 ちなみに256個以上の型を持つvariantの場合型情報は2バイトに拡張されました。そんなプログラム書く人間はいないけど。

挙動

std::variant<T0, T1, T2, ...>

と書いたとき、型情報はT0なら0、T1なら1という風に順に番号が割り当てられます。 この番号はindexメソッドで取得可能で、変数利用時に型チェックをする際などに使います。 何かしらの脆弱性を使ってこの構造体の後ろにある型情報を書き換えることができればType Confusionを起こせます。

std::variantとセットでよく使われるstd::visitという関数があり、すべての型に対して同じ処理を実行することが可能です。 特にstd::visitなどを使うとき、型情報に応じて処理を変えるような機械語が生成されます。 このとき生成される機械語は関数テーブルを利用します。 コンパイル時に、std::variantが取り得る型に対して関数テーブルが生成され、std::visit呼び出し時にindexメソッドが返す値を添字として関数テーブルにアクセスします。 このときindexの値が関数テーブルの範囲を超えているかのチェックは存在しません。 したがって型情報を書き換えてでかい値にすると、関数テーブルで範囲外参照が発生します。 型情報は1バイトなので最大でも0xFFまでしか入れられないという点と、関数テーブルはRead Onlyな領域に作られるという点を考えるとこれが攻撃に実用的かは疑問です。 ただ他の関数テーブルも付近に生成されるので、本来と異なる関数に飛ばすことで関数type confusionとなりexploitableな状況に発展する可能性はあります。

std::shared_ptrはUse-after-Freeなどを防ぐために有効なポインタ管理用STLコンテナです。 セットでstd::weak_ptrという弱い参照を持つ監視用のポインタも用意されています。 その目的の割には比較的複雑な構造なのですが、意外とCTFで使われていることは少ないです。 （少なくともshared_ptrに対して自然にバグを埋め込んでいる問題は見たことがない。それだけ安全ということかも。）

基本構造

std::shared_ptrの構造はやや複雑です。 単純に考えるとshared_ptrはポインタとその参照カウンタを持っていれば良さそうですが、実際には次のような構造になっています。

+00h: <ポインタ実体>
+08h: <メタデータへのポインタ>

+00hにあるポインタ実体は現在そのshared_ptrが保持(共有)しているポインタそのものです。 そして+08hにあるポインタが指すメタデータですが、これはヒープに確保され、次のような構造になっています。

+00h: <vtableのポインタ>
+08h: <参照カウンタ（強い参照）>
+0Ch: <参照カウンタ（弱い参照）>
+10h: <ポインタ実体>

メタデータが本体と分かれている理由は簡単で、先のshared_ptr自体はスコープを外れると消えてしまうからです。

さて、+00hにあるvtableですが、これはデストラクタなどの関数ポインタが入っています。 実はstd::shared_ptr<void>という書き方ができ、1つのshared_ptr変数に任意の型のポインタを代入することが可能です。 このとき型が混合しないように（virtualメソッドと同様に）vtableが生成されます。 型が1つでもvtableは生成され、使われます。

次に+10hにあるポインタですが、これは1つ前の構造に載っていたポインタと同じです。 なぜ2つあるかですが、vtableの関数（例えばデストラクタ）内で使う必要があるためこちらにも同じポインタが存在します。

そして最も重要なのが参照カウンタです。 std::shared_ptrには強い参照と弱い参照の2つの種類のカウンタがあります。 いずれも最初は1に設定されています。 なぜ2つあるかは次の挙動の節で説明します。

挙動

ポインタの代入が発生すると参照カウンタがインクリメントされ、スコープを出る等で所有権が放棄されるとデクリメントされます。 強い参照のカウンタが0になるとデストラクタが呼ばれ、実際にdeleteされます。 （weak_ptrの章で後述しますが、これはポインタ実体をdeleteしますがメタデータがdeleteされるとは限りません。）

強い参照

まず強い参照*5ですが、これは直感的に分かりやすく、ポインタの代入が発生した時点でカウンタが増えます。 つまり、現在所有権を持っている変数の個数と考えれば良さそうです。 shared_ptrがスコープを外れる度にshared_ptrのデストラクタが呼ばれ、その中でスレッドセーフなデクリメントが発生します。 この値はshared_ptrのuse_countメソッドで取得できます。

shared_ptr<X> p, q;
p = shared_ptr<X>(new X()); 
q = p; 
{
  shared_ptr<X> r = p; 
}

弱い参照

次に弱い参照ですが、これはweak_ptrという型の変数にポインタを代入した時点でカウンタが増えます。 weak_ptrは所有権を取りませんが、ポインタの監視はします。 そのためweak_ptrが指すポインタがfreeされている可能性もあります。 これを使うと循環ポインタを持つ構造でshared_ptrを使うことが可能になるなどの使いみちがあります。たぶん。

weak_ptr<X> p;
{
  shared_ptr<X> q(new X()); 
  p = q; 
}

ちなみにexpiredメソッドは強い参照カウンタが0でないかを確認しているだけです。

まとめると、shared_ptrのデストラクタは次の擬似コードのようになっています。

if (strong_refcnt-- == 1) {
  delete ptr; 
  if (weak_refcnt-- == 1) {
    delete meta; 
  }
}

move

shared_ptrに対してstd::moveを利用すると、移動元のshared_ptrの参照カウンタは0になり、ポインタはNULLになりますが、所有権が新しいshared_ptrに移るだけなのでdeleteは発生しません。 通常shared_ptrに対してmoveすることはあり得ません。所有権を移したいならunique_ptrを使えば良いからです。 しかし、atomicなインクリメントを含むshared_ptrは、通常のコピーよりも格段に遅いため、高速化の観点から一時的に使う箇所ではmoveをするようなコードも見られます。 moveした後に正しく所有権を戻さないパスが存在すると、NULL pointer dereferenceなどに繋がります。

shared_ptrに関連するバグ

shared_ptrは参照カウンタを利用してUse-after-Freeを防いでいます。 こんな便利で安全な機能があるのに、人はバグは作り込めるのでしょうか。

競合

shared_ptrの参照カウンタですが、このインクリメント・デクリメント処理はatomicでスレッドセーフです。 当然ですが、そのポインタが指す先のデータを扱う際は開発者が各々でスレッドセーフを実現する必要があります。 shared_ptrを誤って信用してdata raceを引き起こすプログラマもいるらしいです。*6

ポインタの使い回し / 誤用

次のようにshared_ptrを作る前にポインタを作り、それを複数回利用してしまうケースがあります。

T *obj = new T();
...
shared_ptr<T> x(obj);
...
shared_ptr<T> y(obj);

こうなるとxとyそれぞれの参照カウンタが0になるタイミングでobjがfreeされるので、double freeが起こります。 共有するポインタは一時変数に入れず、なるべくshared_ptrする箇所で作成しましょう。 また、getしたポインタを使って新たにshared_ptrを作ってもいけません。

shared_ptrはdeleteしても構いませんが、ポインタ自体をfreeしてはいけません。

shared_ptr<T> x(new T());
...
T *t = x.get();
...
delete t;

当然newした実体はdeleteで消されてしまいますが、以前xはfreeされた領域を指し続けておりUse-after-Freeになります。

std::exception (__cxa_refcounted_exception)

C++にあってCにない代表的なものの1つが例外です。 例外の実装はコンパイラにより異なりますが、g++ではどうなっているのでしょうか。

構造

C++の例外は投げられる時に構造体がヒープに確保されます。 コード中では次のように__cxa_refcounted_exception構造体に例外情報が付加される形で確保されます。

  thrown_size += sizeof (__cxa_refcounted_exception);
  ret = malloc (thrown_size);

投げる例外によりこの構造のサイズは変わりますが、通常加算前のthrown_sizeは8になります。

+00h: <参照カウンタ>
+08h: 
+10h: <型情報へのポインタ> (`std::type_info*`)
+18h: <デストラクタの関数ポインタ>
+20h: <unexpectedHandler> (`std::terminate()`)
+28h: <terminateHandler> (`__verbose_terminate_handler()`)
+30h: <スタックされた次の例外構造体へのポインタ>
+38h: <ネストでcatchされたハンドラの個数>
+3Ch: <handlerSwitchValue>（は？）
...

データが多いので省略しています。 上記の構造体を確保するのは__cxa_allocate_exception関数の役割です。

例外を投げるのは__cxa_throw関数の役割です。 この関数の第一引数には投げる例外のポインタが入ります。 +10hにあるstd::type_infoへのポインタは__cxa_throw関数呼び出し時の第二引数になります。 __cxa_throwの第三引数は例外のデストラクタの関数ポインタが入りますが、const値（char*等）はデストラクタが不要なのでNULLが通常渡されます。

挙動

まだあんまり調べてないので気が向いたら追記します。そろそろアドベントカレンダーの投稿日なのでここまで。 残りは読者の演習課題とする。

STLが関連する過去問

C++製バイナリをpwnする問題はちらほら出ますが、STLで用意されている型を改竄・悪用する問題もいくつか出題されています。

あとはC++製の実製品をpwnする際にC++特有の構造や挙動を知らないとデータを辿れない、といったこともあります。


文章来源: https://ptr-yudai.hatenablog.com/entry/2021/11/30/235732
如有侵权请联系:admin#unsafe.sh