年明けてから、ふとした思い付きで、call graph生成ツール(https://github.com/Hiroshi123/bin_tools)を作っている。 目的としては、windowsとmacのsourceのないdllを効率良く理解することを目的としている。 現状はelf向けのもの(中途)のみできてる。
で、ある程度出来上がったら、まとめを書こうと思ったのだけれど、いくつか壁があって、この辺で、作業の途中ログとして、 少し書いておく。(満足いく形で、全部出来たら再更新するつもり)
コアなアイデアとしては、x86で,callという命令があるのだけど、それが、多くの場合、 0xe8 +現状のコード実行位置からの相対offset で表現されるので、binaryをparseして、e8が見つかったら、次の4byteみて,call先となれる対象か否かを確認する。 "call先となれる"というのは、各関数の先頭を意味している。 "各関数"とは、開発者が定義した関数,または、他のdllに定義され、動的linkされる関数としている。
qemuみたいに全部書く(https://github.com/qemu/qemu/blob/master/target/i386/translate.c)のは少々重いが、かといって、 instructionの区切りが分からないと0xe8が求めているopcodeなのか他の命令のoperandなのか分からない。そこで、0xe8の次4つのbyte からcall先のアドレスを算出し、本来callされるアドレスか否かを調べることで、e8がcallを意味していることをかなりの精度で確信できる。 我ながら、うまいこと思い付いたものだ。
関数の頭のbyteをとるには、まず、object formatのシンボルテーブルをみる。 ここで、value(elf,coff,macho共通)という値に、関数のfileからのoffset情報が入っている。 ただ、そのfileから動的linkされる関数の頭のアドレスは当然シンボルテーブルに入ってない。 本当の遷移先はまだ決まってない(実行時にloaderが決める)からだ。 ここで、少し、動的linkのお話しだが、loaderは直接0xe8後の4byteを書き換えるなどという乱暴なことはしない。 そんなことをすれば、コード領域を書き込み可能になってしまう。 そこで、compilerは、別途書き込み可能な形でmapされた領域にあるアドレスに書いてあるデータを次の%ripとして 読むという処理を入れる。0xff 0x25 + 4byte(%rip相対)で表現される。 そして、この理由は実は、よくわかってないのだが、この処理を各呼び出し口が実行するのではなく、この6byteをcallする 処理を各呼び出し口は持っている。 このアドレスを求め、さらに関数の名前と結び付ける手段はobject format毎に異なる。 elfだったら、relocation tableをみて、書き換え前のgotの値が、pltの次のアドレスを指しているか、plt.gotがあったら、 それを直接dynamic link tableと関連付けるという処理だし、mach-oだったら、stubs,__symbol_ptrというsectionを使って 似た様なことをやる。
こうして、シンボルテーブルを先頭アドレスと名前付きで求めたら、あとは、それを元に、実際の関数の先頭アドレスから、binaryを 読んでいき、0xe8を見つけたら、他の先頭とマッチするかを確認すれば良い。
ここで、小さな問題と大きな問題が発生。 小さな問題だが、elfはご親切に関数のサイズをシンボルテーブルに設定しているのだが、coffはaux(補助的、つまり任意な形)として、mach-oのnlistに関しては全くこの値を保持していない。 その為、coff,mach-ohは、各関数の長さを知る為、次の関数から登ってc3を見つけ出す、という処理が必要な模様。 大きな問題だが、これは、formatの話しでは無いのだが、関数のcallにもう一つの0xff + registerの値というのがあり、それを吐き出すcompilerが時々いる。0xffを0xe8と同じ容量で、detectしようとすると、検知ミスと実行時間の増大に繋がる。binaryに現れる0xffの頻度は0xe8より圧倒的に高いし、レジスタの中を確かめる処理も追加する必要がある。幸いこれは、mingw64の一部のdll関数の呼び出しだけなので、今の所は無視しているのだが...
何れにせよ、この静的解析とも動的解析とも付かぬ遊びだが、中々面白い。 もし、ご興味があれば、是非、自分で作ってみることをオススメする。
追記:2019:2/17
静的linkerの仕組みを調べてたら、あるobjectfileにある関数のcaller,calleeの全ての関係って、上記の様なcall先を探す亜流な手法でなくても、compiler(cc -c .c -o .o)が提供してくれるsection情報を元に全て分かる様になっているよう。 というか、そもそも、call graph生成って静的linkerのrelocationの副次産物に過ぎない。
どういうことかというと、静的linkerがrelocatable objectをrelocationする時に、ccが、object file内外含めてcallの遷移先を可能な限りarchitectureに依存しないで探す為に、その関数から呼ばれるrelocation対象関数の一覧をsectionとして提供してくれてる。elfだったら、.rela.text, mac-oならdynsymtab。 だからobject file生成はrelocation前のobject fileがある場合は、それを対象にした方が良いみたい。ただしrelocation後のobject fileしか手元に無ければ、それらのsectionはrelocation後,静的linkerによって書き換えられてしまうので、上記の方法もそれなりに有用かもしれない。
