アセンブラ命令(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)。

movleajmpmovltestcalljeaddnop
mov415990353105239035520703808394013890403400192
lea378921426903197058020213105092012430698600118
jmp380051970100349066830149603042000000219508229
movl334990134208598271370139215060003480526800099
test143650086000051003030000000000445620000000658
call401330327212372090491774001840000000434601074
je476580391202645056750418702534000000451800386
add331670299302993032410361502057013090623400000
nop018470781303479003550000000213006390021383452

 先頭の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)

f:id:b07c00:20131013025626p:plain

 出現頻度の高い上位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 

 こんな感じでアセンブラ命令を解析してみるのも面白いかもしれません。
 続く…かも?