ネタプログラム
まずはこれを見て欲しい
http://twitter.com/rofi/status/8421655500
おわかりいただけただろうか
ということで、ネタプログラムでした!
解説
まぁただ出しただけではあれなので一応解説を。
以下はものすごく変態的システム依存をしてるのでネタ程度にお楽しみください。
決して重要なプログラムではこのような事はしないでください!*1
目的
以下、プログラムの流れを制作の時と同じ流れで解説していきます*2。
まず、このプログラムの目的とは「C言語でASCIIの文字の機械語だけで"Happy New year!"と表示するプログラムを書く」です。
元々年賀状用のネタなので(^^;
大まかな流れ
ということで、C言語側のプログラムの流れは以下のようになります。
- 文字列表示プログラムを文字列で記述
- 制御をその文字列に移す
C言語側は以上です。
簡単ですね。
次に文字列で書かれた機械語が行うべき処理は以下のようになります。
ちなみに機械語であるため、やることを理解するにはローレイヤーの知識が少し必要となります。
- スタック上に表示文字列をプッシュする
- スタック上に文字列表示関数への引数をプッシュする
- 文字列表示関数を呼び出し
- スタックを巻き戻す
- RET
こんなかんじですね。
C言語で「ローカル変数に文字列を入れて引数に取った文字列表示関数を呼び出す」って事を機械語でやっただけですね。
コーディング1(C言語側)
ではコーディングです。
C言語側は簡単なのでぱぱっとこんな感じに。
#include <stdio.h> int main( void ) { char a[] = "ここに文字列化された機械語が入る"; ( ( void (*)( int (*)( const char * ) ) )( a ) )( puts ); return 0; }
文字列化した機械語を格納した配列の先頭アドレスを関数へのポインタにキャストすることによってこれを関数とみなし、呼び出すことによって制御を移します。
関数へのポインタが分からない方はググッてください。
僕が説明するよりもわかりやすい説明がきっとあるはずなので。
制御を移しても機械語側が文字列を表示させる方法がないので、引数にputs関数を与えてこれを呼び出すことによって"Happy New year!"を表示させることにします。
ちなみにここを
char *a = "ここに文字列化された機械語が入る";
とした場合は文字列の格納場所が異なるので要注意です*3。
コーディング1(機械語側)
では次に機械語側です。
さすがにバイナリデータで書くのは大変なのでアセンブラを用います。
そしてアセンブルしたものから機械語を抜き出すことにします。
アセンブラ自体も面倒なのでC言語のインラインアセンブラを用いてアセンブラを行います。
#include <stdio.h> int main( void ) { __asm { PUSH puts CALL BIN POP EAX } return 0; BIN: __asm { PUSH 217261h ; ar! PUSH 65792077h ; w ye PUSH 654E2079h ; y Ne PUSH 70706148h ; Happ PUSH ESP ; 文字列へのポインタをスタックにプッシュ CALL [ESP+18h] ; puts関数の呼び出し ADD ESP, 14h ; スタックを巻き戻す RET ; RET } }
BINラベル以降の部分が今回必要になる機械語ですね。
最初の4行で文字列"Happy New year!"をスタックに積みます。
次の行で文字列への先頭のポインタ(=現在のスタックポインタ)を積みます。
そして引数として与えられたputs関数を呼び出します。
後はクリーンナップしてRETです。
注意点はスタックはアドレスの大きい方から小さい方向へ積まれていくため、文字列は後ろの文字から順に積んでいく必要があります。
さらに、IntelCPUはリトルエンディアンであるため文字列を数値化するときにバイトオーダーを逆にする必要があります。
これで必要なものは一通り揃いました。
ではこれから機械語を抜き出してみましょう。
PUSH 217261h => 68 61722100 PUSH 65792077h => 68 77207965 PUSH 654E2079h => 68 79204E65 PUSH 70706148h => 68 48617070 PUSH ESP => 54 CALL [ESP+18] => FF5424 18 ADD ESP,14 => 83C4 14 RETN => C3
あとはこれを文字に直すだけです。
問題点
ASCII表を見ると表示可能文字は20h-7Ehらしいです。
これを踏まえて先程の機械語を見てみると・・・
PUSH 217261h => 68 61722100 PUSH 65792077h => 68 77207965 PUSH 654E2079h => 68 79204E65 PUSH 70706148h => 68 48617070 PUSH ESP => 54 CALL [ESP+18] => FF5424 18 ADD ESP,14 => 83C4 14 RETN => C3
この赤い部分は表示可能ではないので文字化はできないですね。
\**を使えば文字列中に表示可能ではない数値も入れられることはできますが、あまり美しくはありませんね。
ということで、このままでは文字列化は出来ないことになります。
では今度は使える文字のみで出来ることを如何に使用して上記のことを達成するかを考えます。
オペコード・マップ
次は表示可能文字がどの命令に相当するのか調べることにします。
これにはhttp://www.intel.co.jp/jp/download/index.htm#ia32の「IA-32 インテル アーキテクチャー・ソフトウェア・デベロッパーズ・マニュアル、中巻」の「オペコード・マップ」を参照してください。
ここには機械語がどの命令に対応するかが書いてあります。
この中で表示可能な文字、つまり20h-7Ehの範囲にある命令を調べます。
同じ命令なのにオペランドが異なるものは別の機械語に当てられてるので、命令の種類としてはそれほど多くないことがわかります。
・・・意外と少ないですね。
さきほどで問題となる部分を上げてみます。
- 文字列の終端を表す\0
- CALL命令
- ESPに加算する値(18h)
- ADD命令
- ESPに加算する値(14h)
- RET命令
この内文字列終端の\0は必須ですが、どうやっても文字として表すことが出来ません。
またそれ以外のものも他の手段はないことはないですが、代用した手段なら表示可能であるという保証はありません。
よって範囲外のものは実行時に作り出すことにします。
つまり、実行時に自己パッチを当てることによって必要な命令/データを作り出すことにします。
コーディング2(C言語側)
自己パッチを当てるためには機械語側が自身のアドレスを知る必要があります。
手段としては相対CALLを行いEIPをスタックに積ませ、それをPOPで取り出す方法が考えられます。
しかし、相対CALLは先程のインテル・アーキテクチャ(ryを参照すると0E8hなのでこれは範囲外です。
そのためこの手は使えない事になります。
よって、自身のアドレスを知らせるために、自身の先頭アドレスも引数として与えることとします。
これをコーディングすると、
#include <stdio.h> int main( void ) { char a[] = "文字列化された機械語が入る"; ( ( void (*)( char *, int (*)( const char * ) ) )( a ) )( a, puts ); return 0; }
となります。
コーディング2(機械語側)
では問題の機械語側のコーディングです。
20h-7Ehの範囲で主に使える命令はオペコード・マップよりPUSH/POP/AND/SUBです。
他にも使える命令はありますが、使おうとすると文字にすることが出来ない場合があったりします。
それらに関してはその時々で説明します。
プログラムの本質的な流れはコーディング1の通りです。
で、問題となっている
- 文字列の終端を表す\0
- CALL命令
- ESPに加算する値(18h)
- ADD命令
- ESPに加算する値(14h)
- RET命令
の点を何らかの方法で解決することにしていきます。
まず、ESPに加算する値(18hと14h)に関してはPUSH/POP命令が使えるので、ダミーデータをたくさん積むことにより値を増加させます。
このことにより、18h,14hを20h-7Ehの範囲に収めてしまいます。
残りのものに関しては実行時に自己パッチを当てることにより解決することにします。
実際にとる方法としては、例えば本来必要なデータが80hが必要だとしましょう。
しかし、80hは範囲外のため表現することが出来ません。
そこで、これを35hと45hに分けることを考えます。
これらは範囲内であるため文字で表現可能です。
そして、これを実行時に35h+45hを行うことにより80hを作り出します。
しかし、今回範囲内に無いためADD命令は使えません。
そのため、SUB命令でパッチを当てます。
加算を行うために負の値を減算することで代用したいのですが、今度は負の値が範囲外となります。
このため、減算を複数回に分けることにより結果的に加算を行うこととします。
では先に作った方のソースを載せます。
今回もインラインアセンブラでやりましたが、内容はアセンブラなのでその部分のみ載せます。
POP EDX POP EAX PUSH EAX PUSH EDX PUSH EDX ; ダミーデータ1 PUSH EDX ; ダミーデータ2 PUSH EDX ; ダミーデータ3 PUSH EDX ; ダミーデータ4 CALL命令のESPに加算する値とその後のスタックを元に戻す値を文字コードの範囲内に納めるためにわざとダミーデータをスタックに積む SUB EAX, 583A734CH ; <= コードの位置に合わせる(RET命令とADD命令の一部の書き換え) SUB EAX, 325D543FH ; <= コードの位置に合わせる(RET命令とADD命令の一部の書き換え) SUB EAX, 75683858H ; <= コードの位置に合わせる(RET命令とADD命令の一部の書き換え) 加算命令は文字コード範囲外なので使用不可。なので、負の値を減算することで加算を実現する。ただし、負の値も文字コード範囲外なので複数回に分けて減算を行う。 PUSH EAX AND EAX, 36574050H AND EAX, 49283529H ; MOVが使えずXORも使えないのでANDで代用。MOV EAX,0と等価。 SUB EAX, 2D7D2923H ; <= パッチデータ作成(RET命令とADD命令の一部の書き換え) SUB EAX, 547C472BH ; <= パッチデータ作成(RET命令とADD命令の一部の書き換え) 加算命令は文字コード範囲外なので使用不可。なので、負の値を減算することで加算を実現する。ただし、負の値も文字コード範囲外なので複数回に分けて減算を行う。 PUSH EAX POP EDX POP EAX SUB DWORD PTR [EAX+52H], EDX ; <= パッチ当て(RET命令とADD命令の一部の書き換え) PUSH EAX AND AL, 34H AND AL, 4BH ; MOVが使えずXORも使えないのでANDで代用。MOV AL,0と等価。 SUB AL, 5AH ; <= パッチデータ作成(CALL命令の書き換え) SUB AL, 7DH ; <= パッチデータ作成(CALL命令の書き換え) 加算命令は文字コード範囲外なので使用不可。なので、負の値を減算することで加算を実現する。ただし、負の値も文字コード範囲外なので複数回に分けて減算を行う。 PUSH EAX POP EDX POP EAX SUB BYTE PTR [EAX+4EH], DL ; <= パッチ当て(CALL命令への書き換え) AND EAX, 513F2556H AND EAX, 2A404821H ; MOVが使えずXORも使えないのでANDで代用。MOV EAX,0と等価w SUB EAX, 784C362AH SUB EAX, 5A712933H SUB EAX, 2D212E42H PUSH EAX PUSH 65792077H PUSH 654E2079H PUSH 70706148H PUSH ESP CALL DWORD PTR[ESP+2CH] ; ※注意 ADD ESP, 24H ; この3行は実際にはこのような状態では埋め込まれず、パッチを当てられる側のデータ(=機械語ではないデータ)で埋め込まれます。 RET ; 実行時に最終的にはこのような命令になるので、参考に書いてます。
では順番に説明していきます。
まず最初にこの機械語の先頭アドレスを取得します。
これは引数として与えられているのでPOPを繰り返し取得します。
その後、スタックを戻しさらにダミーデータを埋め込みます。
これは先程述べたようにESPに加算する値を範囲内に収めるためです。
次に、先程取得した先頭アドレスに減算を行いパッチを当てるアドレスを計算します。
この後パッチするデータを生成します。
その前にEAXをゼロクリアしたいのですが、MOV命令は範囲外ですしXORを使おうとするとオペランドがEAX, EAXとなり、これは仕様書より81hとなってしまいます。
そのため、ANDを2回繰り返し0を作り出します。
ANDの即値に指定する値を上手く作ると、EAXの値が何であれ0を作り出すことが出来ます。
例を見るとすぐに分かりますね
xxxx AND 1010 => x0x0 x0x0 AND 0101 => 0000 x : 未知数
さて、これでパッチする先のアドレス、パッチするデータともに揃ったことになるので実際にパッチを当てます。
当然SUB命令で行うのですが、わざわざアドレス指定に[EAX+52H]を指定しています。
なぜ、最初からEAXにパッチ先のアドレスが入るようにしなかったのかというと、それをしてしまうと命令の後に続くModR/Mバイトというものが範囲外となってしまうためです。
SUB命令などは命令の後にレジスタや即値などを指定出来ますが、それによって命令の機械語が変わってしまいます。
さらに、SUB命令の後に指定するレジスタによってもその命令の後に続くModR/Mバイトという値が変わります。
SUB EAX, EDX
SUB r/m32, r32
の命令に相当します。
その後に続くModR/Mバイトを「ModR/Mバイトによる32ビット・アドレス形式」表を見て調べるとD0hとなります。
これは範囲外なので使えませんね。
なので、範囲内に収めるため8bit即値を足したもの、先の「ModR/Mバイトに〜」表で言うとdisp8[EAX]のところを用いています。
当然足し合わせる即値も範囲内でなければなりません。
これによってRET命令とADD命令の部分にパッチを当て、実際のRET命令とADD命令を作り出します。
同様なことを行いCALL命令も作り出します。
最後に\0を含んだ「ar!\0」をSUB命令を繰り返して作り出し、スタックに積みます。
残りの文字列は表示する文字であり、当然範囲内なのでそのままスタックに積みます。
そしてputs関数を呼び出しあとはパッチが当たっている正常なコードを実行し呼び出し元に戻ります。
以上で機械語部分も出来ました。
ちなみに、今までパッチデータを大量に使用しましたが、このパッチデータは基本的に表示可能文字であればなんでもいいので乱数を発生させて適当に取りました。
出来るだけ文字をバラつかせた方が、見たときにより変態的に不思議に見えるようにしたかったのでw
最終成果物
まぁ最初のURLを見ていただければありますが、ここにもせっかくなので貼っときます。
#include <stdio.h> int main( void ) { char a[] = "ZXPRRRRR-Ls:X-?T]2-X8huP%P@W6%)5(I-#)}--+G|TPZX)PRP$4$K,Z,}PZX(PN%V%?Q%!H@*-*6Lx-3)qZ-B.!-Phw yehy NehHappT(T$,5T+A"; ( ( void (*)( char *, int (*)( const char * ) ) )( a ) )( a, puts ); return 0; }
デバッガなどで追いかけると実際の流れが掴みやすいかもしれません。
余談。
char*型もint (*)( const char * )型も結局はポインタであるため、void*でいいことになります。
これを行ったのが以下のコードです。
http://codepad.org/Uzvw3jZA
#include <stdio.h> int main( void ) { char a[] = "ZXPRRRRR-Ls:X-?T]2-X8huP%P@W6%)5(I-#)}--+G|TPZX)PRP$4$K,Z,}PZX(PN%V%?Q%!H@*-*6Lx-3)qZ-B.!-Phw yehy NehHappT(T$,5T+A"; ( ( void (*)( void *, void * ) )( a ) )( a, puts ); return 0; }
後で気づいたので最初に載せたのはあのようなものになってます。
もっと早くに気づいてれば><
あとがき
書くの疲れました。。。orz
途中からgdgdになってるので、分からないこととか文章がおかしいかと思います。
その時は遠慮なく言ってください><
ここのコメントでも構いませんし、twitter:rofiに投げてくれても構いません。
ちなみにここ、はてダには基本的にプログラミングの話題を載せていくつもりですがtwitterではアイコン/bio詐欺なのでフォローするときは要注意です><
*1:まぁ誰もこんなことしないとは思いますが・・・
*2:ちなみに、完全にシステム依存なので動かない場合があります。一応Intel系のCPU(もしくは互換CPU)を想定してますが「どれ以上のバージョン」だとかはわからないです。それ以外にも実行禁止がかかってたり文字コードがASCIIないしShift-JISでなかったりすると動かないので、動かない場合は諦めてくださいw
*3:特に最終的に出来上がったものは自己パッチを当ててデータを改変するため、このような文字列リテラルでは通常書き換え禁止がセットされてるためにエラーを吐いて落ちたりしますw まぁものは試しにやってみるとわかるかも(ただし責任は負いませんので要注意w)