第一回 カーネル／VM探検隊＠関西で発表してきた！
第一回 カーネル／VM探検隊＠関西（http://atnd.org/events/9074）で発表してきました。
カーネルもVMも話せるような技術は持ってないので自分ができそうなネタで話してきました。
ここでは発表では話さなかった（話せなかった）詳細を書きます。
※更新しました（2011/02/23）
詳細はひとつ下の見出しから
詳細は続きを読むから。
概要
内容： 円周率でプログラミング
結論： 諸事情により（完全には）無理でした☆ ← 作りました（2011/02/23）
発表資料ほか
発表資料は以下のリンクからダウンロードできます。
元ファイル（ODP）： http://goo.gl/ltLEA
PDFファイル： http://goo.gl/v6EkB
発表資料以外のファイル
必要なファイル一式をまとめた物： http://goo.gl/YgtKH
内容
全体の流れは発表資料を見てください。
ここでは技術的詳細を書きます。
環境
スタックにアドレスを積むことや入出力関連は実行時に依存しすぎて難しいので少しコードが書いてあります。
書いた内容は以下の通りです。
- スタックにリターン先のアドレスを積む
- リターン先のアドレスは実行時までわからないのでリターン先アドレスはプログラムとするデータの先頭からのオフセットで持ち、実行時に実効アドレスに変換してスタックに積みます。
- 入出力
- 入出力は実行依存が大きいのでラッパを挟みました。
- しかし、やっている処理はスタックの退避/復旧とcdeclで潰されてしまう可能性のあるECX、EDXの退避/復旧、それを関数呼び出し（CALL命令）ぐらいです。
- 文字読み込み(GET_CHAR)に関しては呼び出した後にEAXに入力された文字が入るというのみ、文字出力（PUT_CHAR）に関しては呼び出し前に出力する文字をEAXに代入するという単純な関数構成にしてあります。
これら以外の処理はすべてリターンアドレスを用いて行います。
brainfxxkの実装
いちいちアドレス列挙で書いてられないのでbrainfxxkのコンパイラをとっとと実装しました。
まず各レジスタの用途は以下のように決めました。
- EAX
- getcharの戻り値用、計算用
- EBX
- PUT_CHAR関数へのポインタ
- ECX
- GET_CHAR関数へのポインタ
- EDX
- データ領域へのポインタ
- ESI
- 計算用
次にbrainfxxkで使われてる命令と対応するアセンブラ及び機械語は以下の通りです。
> ポインタをインクリメント
INC EDX RETN ; 042h, 0C3h これを4回繰り返す。（データの先がint=32bit単位なため）
EDXがデータ領域を指しているのでEDXをインクリメントするだけです。
ただしEDXの先のデータをint型にしているので実際はこのコード片のアドレスを4回出力します。
< ポインタをデクリメント
DEC EDX RET ; 04Ah, 0C3h これを4回繰り返す。
インクリメントと同様、EDXをデクリメントするだけです。
+ ポインタが指す値をインクリメント
INC DWORD PTR DS:[EDX] RETN ; 0FFh, 002h, 0C3h
EDXの先の値をインクリメントするだけです。
- ポインタが指す値をデクリメント
DEC DWORD PTR DS:[EDX] RETN ; 0FFh, 00Ah, 0C3h
インクリメントと同様EDXの先をデクリメントするだけです。
. ポインタが指す値を出力
MOV EAX,DWORD PTR DS:[EDX] RETN ; 08Bh, 002h, 0C3h JMP EBX ; 0FFh, 0E3h
1つでは機械語が長くなってしまうので2つに処理を分けます。
1つ目ではアドレスの先をEAXに移して、その後実際の出力関数（EBX（=PUT_CHAR関数へのポインタ）へ）ジャンプします。
ちなみにジャンプなので出力が終わったらここには戻ってこなくて次の処理（=スタックの最上位のアドレス）に自動的に移ります。
, 1バイトを入力してポインタが指す値に代入
JMP ECX ; 0FFh, 0E1h MOV DWORD PTR DS:[EDX],EAX RETN ; 089h, 002h, 0C3h
入力の場合も長くなるので2つに分けます。
最初に入力関数（ECX（=GET_CHAR関数へのポインタ）へ）ジャンプします。
入力が終わると2つ目の方に移り、入力から受け取ったEAXをアドレスの先に格納します。
[ ポインタが指す値が0なら、対応する ] の直後までジャンプ
MOV ESI, DWORD PTR [EDX] RET ; 08Bh, 032h, 0C3h XOR EAX, EAX RET ; 033h, 0C0h, 0C3h ; ↓ここから OR EAX, ESI RET ; 00Bh, 0C6h, 0C3h ROL ESI, 1 RET ; 0D1h, 0C6h, 0C3h ; ↑ここまでを32回繰り返す CLC RET ; 0F8h, 0C3h ; ↓ここから RCL EAX, 1 RET ; 0D1h, 0D0h, 0C3h CLC RET ; 0F8h, 0C3h ; ↑ここまでを31回繰り返す ROL EAX, 1 RET ; 0D1h, 0C0h, 0C3h ROL EAX, 1 RET ; 0D1h, 0C0h, 0C3h ROL EAX, 1 RET ; 0D1h, 0C0h, 0C3h ROL EAX, 1 RET ; 0D1h, 0C0h, 0C3h ROL EAX, 1 RET ; 0D1h, 0C0h, 0C3h ADD ESP, EAX RET ; 003h, 0E0h, 0C3h POP EAX RET ; 058h, 0C3h SUB ESP, EAX RET ; 02Bh, 0E0h, 0C3h
条件分岐が一番処理がかかりました。
詳細は後に回します。
] 対応する [ にジャンプする
POP EAX RET ; 058h, 0C3h SUB ESP, EAX RET ; 02Bh, 0E0h, 0C3h
対応する位置までスタックを巻き戻します。
巻き戻す方法は対応する[までのスタックの数をスタックに積んでおき、1つ目の処理でその数を取り出します。
そして2つ目の処理で実際にその値を適用させスタックを一気に[の位置まで戻します。
見ての通りすべてのコード片は3バイト以下なので適当に大きなデータを拾ってこれば大抵は含まれてます。
条件分岐の方法
[の処理がEDXが指す先の値が0かどうかで分岐させる必要があります。
通常の方法であるとJZやその関連の命令を使うことになると思うのですが、これらを使ってしまうと一気にコード断片の長さが大きくなってしまいます。
ではどうするか。
結局プログラムはスタックに積んであるものがすべてなので、条件分岐=スタックのポインタを動かすが動かさないかに帰結できます。
つまり、EDXの指すアドレスの先のデータが0かそうでない場合でESPにある定数値を足すか足さないかを行えばよいわけです。
ということで私が取った手段の概略は以下の通りです。
- アドレスの先のデータを取ってくる
- アドレスの先のデータが0かそうでないかで0か1の値を生成する
- ESPに足し込む
- 自動的に分岐
簡単に書けばこうなります。
しかし1つの処理に使えるバイト数が限られてるのでより小さい処理にわけなければなりません。
実際に行なった処理は以下の通りです。
- EDXの先のデータを取ってくる（ESIに代入）
- EAXを0初期化
- EAXにESIの値を論理和をとる
- ESIの値を1ビットシフト
- 3〜4を32ビット分繰り返す
- この時点でESIの値（=EDXの先のデータ）のどこかのビットに1があれば必ずEAXの0ビット目には1が入っている
- よってここからはそれ以外のビットを消す処理を行う
- キャリーフラグを消す
- EAXを1ビットキャリーフラグを含めて回転させる
- 6〜7を31ビット分行う
- さらに数回今度はキャリーフラグを含めずに回転を行い1の値が4ビット目に来るようにする
- ESPに足し込む
- ここで条件分岐
- わざわざ1の位置が4ビット目に来るようにしたのはこの後の0の場合の処理のため
- ここからはアドレスの先のデータが0だった場合
- スタックから対応する]の次の命令までのオフセットを取り出す
- ESPに足しこんで[]の間の処理をスキップする
- ここからはアドレスの先のデータが0以外だった場合だがここでする処理はないためそのまま[]内の処理に移る
4ビット目に来るようにしたのは以下のスタックレイアウトを見ればわかると思います。
| アドレスの先の命令 | 説明 | |
|---|---|---|
| ： | ||
| 1 | ADD ESP, EAX | ESPに足しこみ条件分岐 |
| a2 | POP EAX | スタックから読み飛ばす分を読み取る |
| a3 | 定数 | 読み飛ばす数字 |
| a4 | ADD ESP, EAX | ESPに足しこんで[]の処理をスキップ |
| a5 | 空き | 未使用 |
| b2 | *** | []内の処理の内容 |
1の部分で条件分岐を行います。
この時点でEAXの値は0x00か0x10になっています。
そのため、ESPに足しこんだときにスタックポインタはa2かb2のどちらかを指すことになります。
このように0のときに読み飛ばすためには最低でも3つ分の領域が必要だったので4バイト*3つが確保できる4ビット目に1が来るようにシフトさせました。
あとがき
発表資料にもある通り、結局円周率のデータを用意できなかったので諦めました。
多分探せば普通にあるんでしょうが何もできてない状態だったので最低限でも動かすことをやったら結局こんな結果に・・・
あと、コードセクションに膨大なデータを挿入しようとしても失敗したので結局見つけても無理だっただろうという・・・
一応適当なデータで今回書いたコードに必要なすべての断片を見つけたのがあったので、もし埋めることができたらそれで動かしてたのですが・・・埋め込み方がよくわからなかったです＞＜
PEを自分でいじるという方法もあったのですがフォーマットなんて覚えてｎ（ｒｙ
あと、今回すごく適当に書いたので問題点すごく多いです。
分岐の処理だけでも問題点はすでにわかってます・・・がもう面倒なので直しません
先程の「膨大なデータが埋め込めなかった」ってのも「普通にデータとして埋め込んで実行権限を〜」ってことも言われたりしましたが同様に（ｒｙ
まぁ一発ネタなので内容どうこうよりできる/動いたということが重要なのです！（ｷﾘｯ
ということで私をいじめないでください＞＜ ←
おまけ
「256^3=16MBじゃ足らないんじゃ？」って言われたので少しだけ真面目に考察。
3バイト=24ビットを1つの状態とみると取れる状態は2^24=16777216。
つまり3バイトをひとまとめにして16777216回試行すれば確率的にはほぼ必ず1回は現れることになります。
と考えると一様にランダムなデータであれば3*16777216=48MBのデータがあれば3バイトのデータは普通に現れるはずです。
ちなみに3バイトのデータは途中に現れてもいい（A〜Fがそれぞれ1バイトとしてABC、DEFとあった場合データは連続しているためCDEでも可）ので、とりあえずは48MBよりも小さいのは確実にわかります。
ということで上限は48MBになる、しかも実際はもっと小さい（面倒なのでここからは計算しませんが…）のではないかなぁ〜と。
実際どうなんでしょうか？＞＜
