著者

丸山 冬彦 小川 宏高 松岡 聡

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.40, no.10, pp.39-50, 1999-12-15

被引用文献数

1 1

---

機械語命令列から同じ意味のソースプログラムを復元するデコンパイルという技術は古くから知られており 主に リバースエンジニアリングのための手段の一つとして利用されてきた.実際に Javaとそのバイトコードに関しても いくつかの処理系が提案されているが これまで提供されてきた処理系では Java言語には無いgotoを挿入するなど Java言語の文法を逸脱した結果を出力することがある.また デコンパイルのアルゴリズムがアドホックで 応用の利かないものであるため 我々のOpenJITコンパイラが要求するような 任意のバイトコードから正しいソース構造を復元するでコンパイラフロントエンドとして用いることができない.そこで 我々はJavaバイトコードから適切なJava言語の制御構造を復元するための効果的なアルゴリズムを新しく考案した.アルゴリズムの基本となる考え方は メソッドのコントロールフローグラフに対するドミネータツリーを用いるものである.これはブロック構造が完全な入れ子になる言語の場合 制御構造を表す任意のプログラム片はドミネータツリーにおいて ただ一つのサブツリーをなすという性質に基づいている.この一般性により アルゴリズムはJava以外の言語に適用することも可能である.OpenJITでの予備的な実装による評価では 他のデコンパイラが制御構造の復元に失敗するプログラムであっても 我々のアルゴリズムは適切にそれを復元し かつ 実行速度は同程度であることを示した.The technique called decompilation that reads sequences of machine code and generates the corresponding source program has been known for some time, and utilized primarily for reverse-engineering. For Java and its bytecode, although there have been several proposals of decompilers, most generate outputs that are inappropriately extend the Java language, such as insertion of gotos not present in Java. Moreover, the decompilation algorithms are somewhat ad-hoc and difficult to extend of verify its applicability, which is a hindrance to out OpenJIT compiler which requires a decompiler frontend to recover the correct source structure from arbitrary bytecode. Instead, we have devised a new and effective algorithm for decompilation, with emphasis on properly recovering control structures. The key idea is to base the algorithm around the dominator tree of the control flow graph of a method. This is based on the observation that, for a properly-nested block-structured language, each part of program representing a control structure corresponds to just a single subtree in the dominator tree. As such, the algorithm is general enough to be applied to other languages besides Java. The evaluation of our preliminary implementation in OpenJIT shows that our algorithm properly recovers control structures where other existing decompilers fail, and with relatively equivalent execution speeds.