在二进制翻译中利用本地库代码

谭月辉，尹文龙，郭宝锋，崔佩璋

(1.山西农业大学 信息学院， 山西 晋中 030801; 2 陆军工程大学石家庄校区 电子与光学工程系， 石家庄 050003)

二进制翻译[1]已广泛应用于软件安全分析[2]、软件逆向工程、系统虚拟等领域，并已成为软件迁移的主流技术。例如，FX!32把x86平台下的Win32应用程序翻译到Alpha平台[3]；昆士兰大学开发的跨平台静态二进制翻译器UQBT，可以支持不同源平台和目的平台[4]；跨平台动态二进制翻译器QEMU，支持进程级和系统级虚拟，已支持国产龙芯平台[5]。

主流二进制翻译可以分为动态二进制翻译、静态二进制翻译和动静结合的二进制翻译。动态二进制翻译是一种即时翻译技术，在运行目标程序时动态生成所需代码，能够较好解决代码发现和代码定位问题[6-8]。动态二进制翻译需要在执行目标程序的同时生成目标代码，代码优化时间包含于程序执行时间，所以不能采用深度的优化方法。另外，动态二进制翻译须在执行所生成目标代码的同时，完成加载分析、运行环境设置、实时翻译、代码缓存管理、代码块切换等工作。一些技术如热路径优化[9]、寄存器映射[10]、多线程优化[5]等提高了动态二进制翻译的效率，但未解决动态二进制翻译效率低的问题。静态二进制翻译在不运行目标程序的情况下，静态分析可执行程序，提取指令进行翻译，能采用复杂的代码分析和优化算法，生成高质量代码，执行效率高[5]。但静态二进制翻译难处理代码发现和代码定位问题，在实际应用中受到限制。

由于程序的局部性特点，即20%的代码占用了80%的执行时间。二进制翻译生成的代码质量是影响二进制翻译效率的最重要的因素。传统优化技术着重于从中间代码层到目标指令层的基本块级优化，而忽视了不同平台间具有的共享代码库。本文为充分利用当前可执行文件使用动态链接库的特点，针对动态链接库共享代码进行替换，从而减少翻译开销和提升代码质量，提升系统效率。

本文首先使用形式化的方法给出代码优化的上界，然后提出使用本地函数库的Jecket方法并证明该方法对翻译的代码块达到了理论的优化上界，最后，在流行的动态二进制翻译器QEMU系统中实现该算法，并使用nbench测试集验证了Jecket算法能够显著提升运行效率。

1 相关研究

Jens提出了动态二进制翻译的形式化模型，首先，Jens根据理论计算机图灵机模型提出了更接近真实机的形式化表示形式，进而给出了二进制翻译遵循的原则，最后给出代码优化的上界的表示形式。其中一些重要的理论表示如下：

M(S,I,γ)表示计算机，其中:S表示计算机的状态，I表示计算机的指令集，γ表示I×S→S的映射，表示在某个机器状态下对某条指令的解释。

令Ms(S,I,γ)表示源平台计算机，Mt(S,I,γ)表示模板平台计算机，基于此，二进制翻译可表示为：

寻找一个映射φ使得源平台在当前状态下s解释指令i，总有对应的目标平台对应的状态s′执行i′=φ(i)。该映射φ就是二进制翻译的核心工作之一。

由于映射φ并不是唯一的，为了得到最优的形式，各种中间表示优化方法都是对映射函数φ的简化，对于Jens所实现的系统Yirr-Ma，Jens证明了其最优形式代码优化包括机器状态映射和指令映射，并举例说明其代码优化最优情况下增加的开销是290%。

Jens致力于优化机器状态的映射和指令块的翻译，而忽略了从语义层的模拟，导致其优化无法从更高的语义层面上的语义块的映射。本文从程序等价变换的角度给出了二进制翻译可度量的优化上界，从而在理论和实践上指导工程应用。

2 二进制翻译的等价性和优化上界

程序等价变换是指在保持程序功能不变的前提下，对程序的结构、执行模式、存储模式、编程模式等做出的变换。目的是提高变换后程序的执行效率、安全性、可移植性等，包括低级语言到低级语言的变换，如二进制翻译、数学库的性能调优；高级语言到低级语言的变换，典型的高级语言编译器；串行程序到并行程序的变换，如高性能平台软件并行化移植。程序变换的等价性，目前只能在给定的系统上判定程序变换前后功能性语义的等价性，尚没有统一的等价性定义。二进制翻译是一种指令层次的程序等价变换，其有关理论也适用于二进制翻译。

2.1 二进制翻译等价性定义

根据Jens的二进制翻译模型，结合程序变换的相关理论，把二进制翻译的等价性在指令层面和语义层面给出等价性定义。

定义1指令级等价 源平台Ms，目标平台Mt，当满足γ(s,i)=γ′(φ(s),φ(i))=γ′(s′,φ(i))时，二进制翻译指令映射和状态映射是等价的。

该定义说明了在指令级别模拟的强等价情况，是程序等价的强等价模式。在一些二进制翻译器中，对源平台指令进行逐条指令解释执行就满足指令级等价要求。但是这种强等价定义限制了优化函数的层次，只能对每个指令进行优化，而不能根据指令所在基本块或者函数语义进行优化。

定义2语义级等价源平台Ms，目标平台Mt，对于任意指令序列t={i1,i2,i3,…}当满足γ(s,t)=r′(φ(s),φ(t))=γ′(s′,t′)时，二进制翻译指令映射和状态映射是等价的。

语义级等价要求Mt在初始状态执行了翻译的目标平台指令序列φ(t)后，得到的最终状态与源平台执行t得到的状态对应。并不要求对每条指令的执行都有一个与之对应的中间状态，使得基于基本块、超级块和函数级的优化能够进行。

等价性定义类似于数学同构概念，能够反映出源平台和目标平台在可计算性上的一致性。根据该等价性定义，我们给出二进制翻译的优化上界。

2.2 二进制翻译优化上界

证明：

令δs,δt表示平台Ms和Mt的编译过程，有

Es=δs(B)

Et=δt(B)

那么，经过二进制翻译生成的可执行文件Est可表示为

可见，二进制翻译过程是程序从源文件B到Mt平台可执行文件的一种变换过程，同样的δt也是B到Et的一种变换，而且有

该定理是显而易见的，通常由于二进制翻译系统的复杂性和不同平台的特殊性，二进制翻译的效率是本地码的1/5，甚至更低。所以，充分利用本地码能够极大的提高二进制翻译效率。

3 Jecket算法

使用Jecket算法(Jecket的涵义是算法封装)对本地库函数进行封装，在目标平台模拟源平台参数传递和返回规则，实现目标二进制文件运行时调用本地库函数的功能。主要包括以下3个阶段，库函数识别、调用库函数的指令翻译、执行时本地库函数调用。

3.1 调用库函数的指令翻译

根据可执行文件.sym表和.plt表，可以分析出指令的调用地址和库函数名的对应关系。符号表.sym包括符号名称、符号类型和绑定属性、相关段索引、符号的值、符号的大小，其中根据符号类型如STT_FUNC函数类型、符号大小和符号名称来判断该符号是否是库函数。图 1展示了通过可执行文件符号表获取函数信息的算法过程。

一般情况下，在翻译阶段，如果函数调用指令调用动态链接库函数，首先根据该库函数的参数列表按照源平台参数传递规则提取出所有参数，然后使用所提取的参数调用目的平台对应的库函数。在函数返回后，获取函数返回值，并将该返回值按照源平台规则返回到相应的寄存器或者变量。

图2给出了一般情况下的调用库函数的指令的翻译算法。在进行库函数本地化时，库函数信息如库函数名、参数类型、参数列表、返回值类型等需预先获取。由于库函数是开放并且文档十分丰富，获得此类函数信息十分方便。该算法针对源指令为函数调用指令的情况，当调用的目标函数在func_array中时，根据func_array的函数参数和返回值信息生成对于参数传递指令和调用指令，最后生成函数返回处理指令。

特殊的库函数调用需要复杂的处理机制，当调用的库函数参数为结构体指针时，源平台与目的平台结构体的实现不完全一致，例如某字段位数不同，字段的数据类型不同。在调用目标库函数前，需要临时申请目的平台结构体空间，函数返回后把临时结构体的各项值存储到源平台结构体的对应位置。

当调用的库函数参数个数和类型不确定，如printf、sprintf、fprintf时，需要在调用接口实现对格式化字符串的分析，获取实时的参数，然后调用目的平台库函数。

3.2 执行时本地库函数调用

执行本地库函数调用时可以直接执行生成的二进指令，为了实现方便并利于调试，可采用执行时调用本地库函数可使用类似于QEMU中的helper函数机制，执行环境包括参数信息，源平台CPUState环境指针等传递到helpery函数,helper函数根提取出参数并计算，得到结果写入源平台CPUState对应位置。图 3展示了调用正弦函数sin的helper代码示例。

由于库函数的复杂性和多样性，在进行库函数封装时需要处理参数获取、返回值获取、格式化字符串分析、结构体中各项值获取等问题，库函数封装是一项具有挑战性的工作。在源可执行程序多次调用库函数的情况下，库函数本地化调用能够显著提升运行效率。

4 实验

下面给出Jecket的性能测试，并与QEMU进行对比，使用nbench测试集测试了qemu-1.7.2版本实现Jecket算法前后的CPU，FPU和内存系统的性能。

令TQEMU和TSQEMU分别为QEMU和SQEMU执行可执行程序时的时间,Sspeedup为SQEMU相对QEMU的加速比，

实验的目的在于验证SQEMU的正确性和效率，nbench含有正确性验证模块，测试用例如表1所示，实验环境如表2所示。

表1 Nbench-2.2.3测试用例

表2 二进制翻译环境

经统计，对nbench测试项目的生成代码指令数减少了27.73%。从图4可以看出：使用本地包装算法Jecket后，nbench测试项目最高达到了60.70倍的加速。NEURAL NET测试项目频繁使用库函数exp，经过Jecket封装，直接调用本地库函数，减少了大量的翻译时间和生成代码，极大的提升了执行效率。对于没有使用本地库函数的测试项目如NUMERIC SORT，BITFIELD，FP EMULATIOIN等，函数本地化并不影响其执行效率。该测试集结果显示，对于含有库函数调用的应用，Jecket算法有极大的加速比。

5 结论

1) 给出了二进制翻译作为程序变化的形式化表示方法，然后给出优化过程的一个优化上界，探讨了逼近此优化上界的方案并给出利用本地库函数替换翻译过程和执行代码的Jecket方法，并证明了通过Jecket的库函数部分代码可以达到优化上界的执行效率。

2) 通过在二进制翻译器qemu系统中实现Jecket算法并使用nbench测试集测试了Jecket算法的加速效率。对于核心区域含有库函数调用的应用显著提高了系统效率。