アセンブラ命令(x86)をクラスタリングしてみた。
以前、出現頻度の高いアセンブラ命令を調べてみる。という記事で命令ごとの出現頻度を調べました。あのときはWindows環境でProgram Files以下のPEファイルを対象にデータをとりましたが、今回はFreeBSDのlibcを対象にデータをとってみたいと思います。
まずはobjdumpでlibcを逆アセンブルした結果をもとに出現頻度を集計します。
01. mov 15138 11. pop 1370 21. cmpl 211 02. lea 2068 12. jne 1180 22. sar 210 03. jmp 2018 13. sub 1067 23. cmpb 202 04. movl 2012 14. push 1037 24. ja 197 05. test 1977 15. and 808 25. jbe 191 06. call 1958 16. xor 717 26. movb 181 07. je 1815 17. ret 583 27. shr 176 08. add 1605 18. or 467 28. shl 159 09. nop 1572 19. movzbl 392 29. imul 140 10. cmp 1498 20. jle 291 30. addl 140
Windows環境と比べてどうでしょうか。上位陣はわりと安定してますね。今回はobjdumpで逆アセンブルしたのでmov、movl、movbが別々にカウントされていたり、int3の代わりにnopが増えていたりとデータの取得方法の違いによる誤差がありますが、まぁ順位については大きな影響はないと思います。
続いて、命令Xが出現したとき次に命令Yが出現する確率を算出します(縦X、横Y)。
mov | lea | jmp | movl | test | call | je | add | nop | |
mov | 41599 | 03531 | 05239 | 03552 | 07038 | 08394 | 01389 | 04034 | 00192 |
lea | 37892 | 14269 | 03197 | 05802 | 02131 | 05092 | 01243 | 06986 | 00118 |
jmp | 38005 | 19701 | 00349 | 06683 | 01496 | 03042 | 00000 | 02195 | 08229 |
movl | 33499 | 01342 | 08598 | 27137 | 01392 | 15060 | 00348 | 05268 | 00099 |
test | 14365 | 00860 | 00051 | 00303 | 00000 | 00000 | 44562 | 00000 | 00658 |
call | 40133 | 03272 | 12372 | 09049 | 17740 | 01840 | 00000 | 04346 | 01074 |
je | 47658 | 03912 | 02645 | 05675 | 04187 | 02534 | 00000 | 04518 | 00386 |
add | 33167 | 02993 | 02993 | 03241 | 03615 | 02057 | 01309 | 06234 | 00000 |
nop | 01847 | 07813 | 03479 | 00355 | 00000 | 00213 | 00639 | 00213 | 83452 |
先頭の0.を省いているので、例えばmovが出現したあとさらに次もmovである確率は0.41599、次がnopである確率は0.00192という感じです。ざっと眺めてみると、testのあとにjeが来る確率は0.44562と非常に高くなっていたり、出現頻度の高さからmovが常に高い値を示していたり、またnopが連続する確率が0.83452となっていたりといろいろと興味深いものになっています。
ではこのデータを使って命令をクラスタリングしてみます。今回は R を使いました。
> data2<-read.csv("C:\\cnts.csv",header=T,row.names=1) > plot(hclust(dist(data2,"canberra"),"ward"),hang=-1)
出現頻度の高い上位32命令をクラスタリングした結果が上の図です。「次に出現する命令」という特徴で分類していますが、わりとうまい具合に似た命令が集まっています。
左端のグループはcmp、testが集まっています。いわゆる条件分岐系ですね。おそらく次にくる命令にje、jneといったものが多いためこのようになったと推測できます。逆にjmp系命令は別々のクラスタに分かれています。これは興味深いですね。je、jneといった単純なイコール比較はcallやjmpと似ており、jle、jg、jaといったものとは別のクラスタになっていますね。なかなか興味深い結果です。個人的にはimulがshrやshlと同じところにいるのが気に入りました。
逆に気に入らないのはnopの場所です。命令の性質上もっと独立しているべきだと思いますが、普通にpush、popと同じ辺りに割り当てられています。この辺りは微妙ですね。
ちなみにkmeansで6つに分けるとちゃんとnopが独立していました(ただ他の命令が微妙な感じですがw)。
> data2.kms<-kmeans(data2,6) > data2.kms$cluster mov lea jmp movl test call je add nop 6 6 6 6 4 6 6 6 3 cmp pop jne sub push and xor ret or 4 1 6 6 2 5 6 6 2 movzbl jle cmpl sar cmpb ja jbe movb shr 5 2 4 5 4 6 6 6 5 shl imul addl js jg 5 5 6 6 6
こんな感じでアセンブラ命令を解析してみるのも面白いかもしれません。
続く…かも?