2012-02-25
ハンド (逆) アセンブルのための x86 ニーモニックの覚え方
バイナリ列を見て x86 のコードかな〜とニヨニヨできる人に、x86 のコードであること、だけじゃなく実際のコード列も読めるようになってほしい！そんな願いから、今回は hex dump のバイト列を見つめてハンド逆アセンブルできるようになるための、効率良い覚え方を紹介します。
今回は、32-bit x86 について解説するよ。
まとめて覚えておきたい 8 つの命令、add, sub, adc, sbb, and, or, xor, cmp (00h〜3Dh)
これらの命令は近い所に配置されていて、しかも命令のルールがほとんど同じです。
つまり、ほとんど同じように覚えることができるのです。opcode map 上では次の領域が相当します。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | |
| 0 | ■ | ■ | ■ | ■ | ■ | ■ | ←add | ■ | ■ | ■ | ■ | ■ | ■ | ←or | ||
| 1 | ■ | ■ | ■ | ■ | ■ | ■ | ←adc | ■ | ■ | ■ | ■ | ■ | ■ | ←sbb | ||
| 2 | ■ | ■ | ■ | ■ | ■ | ■ | ←and | ■ | ■ | ■ | ■ | ■ | ■ | ←sub | ||
| 3 | ■ | ■ | ■ | ■ | ■ | ■ | ←xor | ■ | ■ | ■ | ■ | ■ | ■ | ←cmp | ||
| 4 |
並びの覚え方ですが… xor と cmp に関してはこのまま覚えましょう。その他については…
- 00h〜 と 08h〜: ビットや値を (足す) 感じの操作 (add と or)
- 10h〜 と 18h〜: キャリーを使った加減算 (adc と sbb)
- 20h〜 と 28h〜: ビットや値を (引く) 感じの操作 (and と sub)
- ここでは sub が後に来ていることに注意。
さて、ここでは add 命令 (00h〜05h) について詳しく見てみましょう。これが分かれば、他の 7 つの命令もおのずと理解できるはずです。
00h, 02h: レジスタやメモリに対する操作 (バイト)
命令フォーマット: [00h|02h] [Mod R/M] ([SIB]) ([Address Offset])
00h と 02h の違いはデータがどちらに流れるかというものです。
00h: add reg/mem ← reg 02h: add reg/mem → reg
x86 の基本的な (Mod R/M を使う) 命令では、メモリオペランドは片方につけることしかできません。そのため、メモリをソースとして扱うかデスティネーションとして扱うかでオペコードが違うということになってきます。
ちなみに、レジスタ同士の場合 00h, 02h のどちらを使っても良いので、次の 2 つのバイト列は同じ操作を意味します。
00 c8: add al ← cl (add al, cl) 02 c1: add cl → al (add al, cl)
Mod R/M バイトは全部暗記しておくと読むのが楽になるけど、シェルコードの多くを読むだけであれば、Mod R/M バイトが C0h〜FFh ならレジスタ同士の操作 (SIB バイトやオフセットはつかない)、とだけ覚えておくと扱いやすいです。
01h, 03h: レジスタやメモリに対する操作 (ワード)
00h, 02h と基本は似ています。ただし、基本的にはワード (32-bit x86 の通常モードでは 32-bit) を扱います。ただし、プレフィックス 66h がオペコードの前についている場合、16-bit 操作になります。(16-bit モードの場合には、66h プレフィックスで 32-bit 操作になる)
命令フォーマット: [01h|03h] [Mod R/M] ([SIB]) ([Address Offset])
もちろん、メモリ操作の方向も似ています。
01h: add reg/mem ← reg 03h: add reg/mem → reg
というわけで、レジスタ同士の演算では 01h, 03h で同じ操作の別バイト列が作れます。
01 c8: add eax ← ecx (add eax, ecx) 03 c1: add ecx → eax (add eax, ecx)
04h, 05h: eax レジスタと定数に対する操作
命令フォーマット: [04h] [定数 (1-byte)] [05h] [定数 (4-byte または 2-byte)]
これは、eax レジスタ (あるいは al レジスタ) と定数とで操作を行うための命令です。05h の方はプレフィックス 66h で 16-bit 操作になります。
04 0a: add al, 10 (0x0a) 66 05 e8 03: add ax, 1000 (0x03e8) 05 40 42 0f 00: add eax, 1000000 (0x000f4240)
もっと大きな命令グループ (レジスタ)
x86 のレジスタは 3 ビットの数値で表現されます。その数値が命令の 1 バイト目に含まれる命令グループを紹介しましょう。
| AL | eAX | 0 |
| CL | eCX | 1 |
| DL | eDX | 2 |
| BL | eBX | 3 |
| AH | eSP | 4 |
| CH | eBP | 5 |
| DH | eSI | 6 |
| BH | eDI | 7 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | |
| 4 | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | □ | □ | □ | □ | □ | □ | □ | □ |
| 5 | □ | □ | □ | □ | □ | □ | □ | □ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
| 9 | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ||||||||
| B | □ | □ | □ | □ | □ | □ | □ | □ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
- 40h-47h: INC reg
- 48h-4Fh: DEC reg
- INC と逆にレジスタから 1 を引く命令です。
- 50h-57h: PUSH reg
- 58h-5Fh: POP reg
- 90h-97h: XCHG eAX, reg
- B0h-B7h: MOV reg8, imm8
- 指定のレジスタに定数を入れる際に用いられます。
- B8h-BFh: MOV reg, imm
条件分岐 (70h-7Fh)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | |
| 7 | ■ | □ | ■ | □ | ■ | □ | ■ | □ | ■ | □ | ■ | □ | ■ | □ | ■ | □ |
これには簡単な覚え方は…なさそうです。ただひとつだけ覚えておきたいのは、ある条件とその否定はかならず隣り合っていることです。つまり、short 条件分岐の 1 バイト目、最下位ビットを反転すると、条件が反対になるということです。
72 xx: JE short XX ↑ ↓ 73 xx: JNE short XX
…記事の書き方が雑になってないか?
気のせいではないです、今日中に公開することを急いだ結果がこれだよ! そのうちちゃんと書き足すです。
ハンド (逆) アセンブルを補助するための PDF リスト!
今回はこれを簡単に実現するために、手軽に印刷して参照できる PDF を作ってみました。
http://dl.dropbox.com/u/2476414/TechResources/x86_opcodemap_1_a4.pdf
http://dl.dropbox.com/u/2476414/TechResources/x86_opcodemap_1_b4.pdf
余白の大きい B4 版をオススメします。手元の紙に手軽に印刷できるよう一応 A4 版も作りましたが…ぶっちゃけ見づらいです。
続きは何書く?
Mod R/M バイトについてほとんど何も解説せずに記事を書き終えてしまった (しかもオペコード表だけだと分からない) ので、次回このシリーズを書くとしたら、 Mod R/M バイトと SIB バイトについて、あと Mod R/M を覚えないと書けない単項 (Unary) 命令についても解説してみようと思います。
Permalink | コメント(0) | トラックバック(0) | 23:33 
2012-01-05
グレイコード→次のグレイコード的なカウンタ
@iorivur さんがつぶやいた、グレイコードを直接出すカウンタは…できました。けど複雑な上に実質加算器なので、個人的にはこれはあまり好きになれません。
グレイコードとは
グレイコードとは、1 ステップ進めると 1 ビットだけ変化するという性質を持つ n ビットの数値符号です。ここでは、3 ビットのグレイコードを見てみましょう。
| v | b2 | b1 | b0 |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 1 |
| 3 | 0 | 1 | 0 |
| 4 | 1 | 1 | 0 |
| 5 | 1 | 1 | 1 |
| 6 | 1 | 0 | 1 |
| 7 | 1 | 0 | 0 |
int graycode(int v) { return v ^ (v >> 1); }
「上位のビットに」依存するグレイコード
上の関数は、通常の数値からグレイコードを生成します。では、グレイコードから次のグレイコードを生成できるのか? というのが @iorivur さんの疑問だったみたいです。でまぁ…卑怯ですが、できました。
- 各ビットは、「自ビットより上位ビットすべての偶数パリティ」=P、「自ビット」=Bin、「キャリー」=Cin を受け取る
- 各ビットはキャリーが 1 のときにしか更新されない
- 最下位ビットのキャリーは、通常の加算器と異なり常に 1 (最下位ビットから更新が始まる)
- 各ビットは出力の自ビット=Bout、キャリー=Cout を出力し、Cout はすぐ上のビットの Cin になる
このとき…
| Cin | P | Bin | Bout | Cout |
| 0 | X | X | Bin | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 |
もっと省略すると、
| Cin | P | Bin | Bout | Cout |
| 0 | X | X | Bin | 0 |
| 1 | X | X | ~P | P^Bin |
ただしこれは最上位ビットを除く話です。最上位ビットの場合には、0→1 のとき上記ルールが適用できますが、1→0 のときルールが適用できません。そのため、Cin=1, Bin=1 で、かつ下位ビットすべてが 0 ならば、Bout は 0 にする必要があります。
ビット毎に計算して正しいことを確かめてみてください。
各ビット毎のパリティをあらかじめ求めておく必要はあるものの、これで一応はグレイコード→次のグレイコードが一意に算出できます。だけどこれって加算器を変形しただけだから、実質バイナリ (数値) 変換してるのと変わらないのよね…。
Permalink | コメント(0) | トラックバック(0) | 21:00
2011-08-14
そろそろあの長文に反論するか…。
ふむふむ。一回読んだだけでも、間違っているどころか詭弁に見える部分がある。
というわけで、私の立場から反論させていただきたい。
自己紹介
原著者の方が見ることも考慮して、自己紹介しておこう。私は 大居 司、情報セキュリティ業界の一年生で、今年のセプキャンには JNSA*1 協力メンバーの sutegoma2*2 枠として入場した。(見学させていただいた。)
文を読む
最初の印象は、
- 間違っている部分がある
- 詭弁と受け取られかねない部分がある
- 批判せざるを得ない部分がある
- これって本当に「批判」してる?
順不同にはなってしまうが、おおむね順番通りに指摘する。
情報を守る責任
まず喩え話の A さんが悪いのか B さんが悪いのか。明らかに B さんが悪いだろう。A さんは、自身のアカウント情報を適切に守らなかったという点で責任は生まれるかもしれないが、それは「悪さ」ではない。ここで明らかに間違っていると言えることのひとつが、喩え話の実例としてソニーの件を出したことだ。個人の例と明らかに異なるのは、ソニーが大量の個人情報を扱い、それを不適切な方法で保護してきたことだ。
この件で私が特に重要と思うのは、情報を保持するとき、常に保持と保護に関する責任が生じることだ。個人情報流出事件の報道を見てもらえればわかるはずだが、彼らはまず「流出させた」そのこと自身で批判されているのであり、なぜ流出したのかはその次にくる。
そして、さらに悪いのが Anonymous に関する扱い (GoogleNews で記事がほとんど見られなかった) だが、…貴方の目は節穴か？今からでも Google News で検索してくれ。いくらでも記事が見つかるだろう。間違っているのだと貴方が主張するのであれば、貴方はとんだ嘘つきだ。Anonymous などの記事が少ないとはいえないし、ソニーの批判が多いのは情報流出そのもの (+ この件固有の特殊事情)。私はそう考える。
貴方は間違っていると言い張れる。
私は高専を中退し、結局セプキャンの生徒としては参加できていない。ただし、経験上反例を挙げることはできる。この部分のことだ。
高校生のうちから勉強したからといって，実務で役立つことは皆無である．
役に立っている。はっきり言わせていただく。何度でも言わせていただく。役に立っている。あなたに批判されようと、嘘つきと言われようと、あなたは間違っていると声を大にして言い張れる。exploit の基礎知識、レインボーテーブルなどのオフライン攻撃、x86 CPU の保護機構、すべて高専の、しかも低学年のときに学んだことだ。
実のところこの反論を書こうとした最大の理由はここで、私も強く侮辱されたように感じたし、実際に今年のセプキャンで学び取っているすべての者を愚弄する行為に見えたからだ。はっきり言って、頭に来た。
それ以外の指摘としては、本当に (黒だろうが白だろうが) 情報セキュリティに興味のある人物はどれだけ止めようと学ぶということがある。(実際に私がそうだった。) それなら、正しい情報を正しく使えるように、指導していくというのも重要ではないのか? と。私は、こちらの方が良い効果をもたらすものと確信しているし、講師陣も倫理を教えることは非常に重視している。
追記
おそらく、「皆無」のような強すぎる否定を用いたことで、私が頭にきたんだと思う。例えば、「あまりない」とかだったら、この部分に関して反論することの正当性を半分失っていたことだろう。ちなみに、相手が「ない」と主張している場合に「ない」ことを証明することは比較的難しいが、「ある」ことの証明は簡単にできる。
見ていないこと / 見ていること
セプキャンのチューターに EULA 違反をするような人がいたという話に関しては、私は見ていないし、反証もできないので反論はしない。実のところ、それをやりかねないチューターは知っているので、まぁ…事実のように聞こえてしまう。ただ、筑波とか AC とかのくだり。あなたがセプキャンに参加した時期には正しいのかもしれないが、今年に私が見た限りにおいて、筑波がどうのこうの、というのは目にしなかった。 (私は当時のセプキャンを見ていないのでその点の反論はできないが、新たな主観的事実を提示することはできる。) そして、貴方が遭遇したであろう優生主義の人物に会ったとしたら、確かに、貴方が主張するように指摘してやれば良いのだ。ここで、新たな点が浮かび上がる。
それって批判してるの?
先ほど出てきた点、それはあなたが批判した様々なことが、セプキャンを避ける理由になるか、ということだ。
私が言いたい。関係ない理由を挙げた上で印象操作をしようとしていないか? と。もしそうなら、れっきとした詭弁だ。嘘をついているとか、間違いがあるとか以前の問題だと考えるし、そうでないなら反論してほしい。どちらにしろ…
見て判断してほしい
私の主張だけ見て偏った判断に流れるということも、これはマズいことだ。実のところ、彼の長文の中にも読むべき点はあるし、私自身も結構勢いで書いた部分があり、間違っているかもしれないからだ。URL を再掲しよう。
結論については保留する。怒りに任せて書いた部分もあることから、私自身も批判を免れない。
ただそれでも、私の立場から明らかに間違っている点についての指摘はできたと思うし、あり得る批判を少しでも並べることができたはずだ。
追記
結論だけ言わせていただく。私は、彼の主張が不公正で、判断を誤らせる要因になりかねないと考える。正直なところ、セプキャン希望者の判断の自由を逆に奪いかねないと思っている。私はこの (全体的に酷い) 文章を通じて、誤った部分を指摘し、真に (セプキャン希望者が) 自由に判断できるようにしておきたいと考えている。
Permalink | コメント(5) | トラックバック(0) | 16:44
2011-03-14
線形合同法で色々やってみる。
任意の未来の状態を計算できる乱数について調べてたら、線形合同法ならパラメータを計算し直すだけで何とかならないかと考えた。あと 2ch のログでもこういうのを発見した。(出典: http://unkar.org/r/tech/1192628099 [擬似乱数２ - プログラム技術@2ch掲示板])
140 ：デフォルトの名無しさん[sage]：2008/09/17(水) 19:03:50
XorShift ならちょっと考えればわかる。
線形合同法なら 2^{31}-1 だけ進めた x=Ax+C の A と C を求めれば可能。
メルセンヌツイスタやWELLなら
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/jumpf2.pdf
の方法で周期よりも一つ少ないところへジャンプすれば不可能ではないはず。
というのも、訳あって SIMD 版と非 SIMD 版で全く同じ乱数を使用する必要があり、しかもある程度高速な方が好まれるという事情があるためだ。(あと本来の乱数性もそれほど必要ではない。) 線形合同法は、念の為に説明すると次の形の乱数生成法だ。(パラメータの制約などについては Wikipedia を参照してほしい。)
2 段重ね
では、これを二段重ねにすることを考えてみよう。剰余に関連する定理により、
の両者は等価である。これをさらに展開すると面白いことになる。
となる。つまり、線形合同法のパラメータを変更するだけで、2 段飛ばしの乱数を生成できるようになるのだ。
n 段重ね
さらに一般化しよう。 について、具体的な計算は省略するが、次のようになる。
2^n 段重ね, k+l 段重ね
このままだと を計算するコストが結構ある。これをカバーするには、二段重ねを応用して
段重ねをやって、これを最終的に合成すれば比較的高速に生成できる。2 つの n 段重ねの系列を合成 (k+l 段重ね) するためには、次の計算をすれば良い。
これを使ってできるのが、上にある 2ch ログで答えがあったような、「線形合同法による乱数列の巻き戻し」だ。周期が f の乱数列の場合、f-1 回後の乱数を生成するパラメータを生成すれば、乱数列の巻き戻しが可能になる。(一般的には周期が や
となるから、その周期の一つ前を計算すれば良いわけだ。)
SIMD による乱数列の生成
これは簡単。例えば SSE2 などの 32x4 bit の場合、数式による表現では
とするだけ。
まとめ
SIMD でも変わらない乱数は意外と簡単に生成できた。あとは、他の乱数ももう少し詳しく調べることにする。
Permalink | コメント(0) | トラックバック(0) | 13:11
2011-02-17
x86 で任意精度整数の演算 (一部) をやってみる
FAT12/FAT16 用のブートローダを書こうとしていたときに気づいた問題。FAT12/16 の最大クラスタ数はそれぞれ 2^12, 2^16 より少し少ない値だが、セクタに関してはそうではない。計算するときには 32 ビットの値でセクタ数を計算し、ディスクからのロード操作を行う必要がある。しかも私はブートローダを 8086 互換命令だけで構成したかったので、ヘタに 32 ビット演算 (や eax とかのレジスタ) を使うわけにもいかない。というわけで、16 ビットの命令だけで必要な演算が賄えるかどうかが鍵だった。必要なのは次の演算だ。
- u32 + u32 -> u32
- u32 - u32 -> u32
- u16 * u16 -> u32
- u32 / u16 -> u32
- u32 % u16 -> u16
最初の 2 つ (加減算) は命令をよく知っていれば特に詰まるところなどない。乗算に関しては mul 命令をそのまま使うだけでこのようになる。ただし最後のふたつ、つまり、32 ビットの値を 16 ビットの値で割ったときの商と剰余に関しては、若干の工夫を必要とする…ように見えた。まぁ最初からやっていこう。
加算/減算
x86 には adc, sbb という命令がある。これは普通に加減算をするだけでなく、キャリー/ボローがある場合に余分に 1 を足す/引く命令だ。*1これを使うことで、多倍長の加減ができる。
; DX:AX <- DX:AX + DI:SI add ax, si adc dx, di ; DX:AX <- DX:AX - DI:SI sub ax, si sbb dx, di
乗算
mul 命令はまさにそのための命令だ。16 ビットの mul 命令は AX * (何か) の演算結果を DX:AX という 32 ビットの値として格納する。つまり…
; DX:AX <- AX * DX mul dx
以上だ。
除算 (商, 剰余)
さて、8086 命令だけを使って u32 / u16 の命令を実装するには、どのように多倍長で計算するかということが重要になる。あれ、x86 の div 命令って u32 / u16 の演算をしなかったっけ? とお気づきの方はかなり頭が良い。しかし、ここには大きな落とし穴がある。念の為に div 命令の主な動作を下に示す。
; div X AX = (DX:AX) / X ; Careful! DX = (DX:AX) % X
ここで注意しておきたいのは、商は 16 ビットに収まらなければならないという点だ。例えば u32 / u16 の計算をして、答えが 0x10000 以上、つまり 16 ビットに収まらない場合については #DE (除算エラー) が発生してしまうのだ。これにより、単純な解は消える。何らかの多倍長演算をしなければならないことは一目瞭然だ。そこで、筆算が参考になるかな、と思い、適当な筆算をメモってみた。*2
; 691 / 7 = 98, 691 % 7 = 5
0 9 8
+---------------
7 | (0) 6 9 1
0
------
6 9
6 3
------
6 1
5 6
------
5
お分かりいただけるだろうか。これだけで答えは出たも当然だということを。2 桁の数を引っ張ってきて、それを 1 桁の数で割り、剰余を次に割る 2 桁の数のうちの上位にしたうえで被除数から新たに 1 桁持ってくる。この繰り返しだ。しかも、この原則は 2 進以上なら何でも構わない。10 進数でも、16 進数でも、あるいは 65536 進数や 4294967296 進数でも同じなのだ。*3ただし x86 の div 命令に当てはめると、最初に 2 桁を持ってきてしまった場合に (前述したような) 除算エラーが発生してしまう可能性がある。そのため、最初に持ってくる 2 桁はダミーの 0 を含むことになる。これで商は 16 ビットに収まることが確定する。
次以降は 2 桁 / 1 桁の、一見オーバーフローが発生しそうな演算だが、考えてみてほしい。1 桁毎の商が 10 以上になるのは、どういう場合だ? 上の 10 進数の例で考えるならば、部分的に扱う 2 桁の数が 70 以上になる場合だ。しかし…よく考えてみよう。部分的に扱う 2 桁の数のうち、上位部分は既に行われた演算の剰余だということを。そう、上位からやってくる数は、除数が 7 の場合は 0〜6 しかありえないのだ。下の桁は明らかに、0〜9 だ。つまり、最上位さえ適切に扱ってやれば、後で除算エラーが発生する可能性は消え失せるのだ。
さらに良いお知らせ。div 命令の仕様で、剰余は DX に格納される。しかし、DX というのは次の div 命令において上位 16 ビットとして扱われる値そのものである。つまり、次の桁を「持ってくる」には、AX 部分だけを交換すれば良いのだ。これは効率が良い上に、ブートローダのような小さなプログラムでの実装を容易にする。次のものは実際にブートローダで使うために試験的に実装したものだ。
; (CX:AX) = (AX:CX) / BX, DX = (AX:CX) % BX xor dx, dx ; 31 D2 ; 上位の除算でオーバーフローしないようにする div bx ; F7 F3 ; 上位の部分商と剰余を取る xchg ax, cx ; 91 ; 上位の部分商と下位の桁を交換する div bx ; F7 F3 ; 下位の部分商と剰余 (これは全体の剰余に等しい) を取る
最適化のおかげで、わずか 7 バイトで u32 と u16 の商と剰余が取れている。商 (CX:AX) が元々の被除数 (AX:CX) からひっくり返った配置になるのが気に入らなければ、xchg ax, cx を先頭か末尾に付加して 8 バイト。これだけで全てが間に合う。意外と…小さく済むものだ。
Permalink | コメント(0) | トラックバック(0) | 17:00
