Using Graph Match Method to Resolve Multi-Way Branch in Binary Translation

Binary translation has become an important way for software migration. For binary translation systems, how to exploit binary codes and translate them effectively is an important problem. However, indirect jumps in binary codes dont give the jump target explicitly, which will narrow the translation coverage and negatively affect the translation performance. In regular binaries, indirect jumps are often used for multi-way branches, candidate targets are reserved in a jump table. A technique to resolve these multi-way branches are presented, which can find the jump table to make the indirect jump target codes in view, and help translate these codes effectively and finally improve the performance of binary translation system. The technique presented can extract the semantic of the examined codes, and finally recover the codes accord with the expected semantic. In this technique, the semantic of some correlated codes is expressed using a graph, which is called semantic graph here. The technigue can efficiently express the information of pre-defined semantic and can be easily constructed from binary codes. This technique tolerates different codes generated from different compile options, and also effectively sieves the instructions irrelevant to the expected semantic. Experiment results shows that, for gcc, perlbmk, and crafty in SPEC CINT2000 benchmark, translation coverage can be improved by a range of 9.85% to 22.13%, and the performance speedup(ref input size) can be improved by a range of 8.30% to 17.71%, while the time complexity of the algorithm used is O(1).