高级检索

    二进制翻译中解析多目标分支语句的图匹配方法

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

    • 摘要: 二进制翻译技术现已成为实现软件移植的重要手段.在二进制翻译系统中,如何有效地挖掘程序的代码并对其进行高效翻译是影响系统性能的关键,而二进制代码中间接跳转语句的存在,使得静态时难以得到它的跳转目标,影响了代码的发掘率和最终的翻译效果.在通常的应用程序中,间接跳转指令经常用来实现多目标分支语义,分支目标存放在跳转表中.提出了一种解析多目标分支语句及其跳转表的方法,能够挖掘出间接跳转的目标,进而对其进行有效翻译并提高二进制翻译系统的性能.该方法提出使用语义图来对预期语义进行刻画和表达.语义图能够对考察的指令序列进行语义提取,识别出与预期语义相匹配的指令流,还可以应对编译器在不同优化选项下生成的指令,并能有效滤除不相关指令带来的干扰.实验结果表明,对于SPEC CINT2000中的部分测试用例,代码翻译的覆盖率可以提高9.85%~22.13%,相应带来的性能提升可达到8.30%~17.71%,而使用的算法时间复杂度仅为O(1).

       

      Abstract: 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).

       

    /

    返回文章
    返回