文献标识码: A
文章编号: 0258-7998(2014)07-0130-04
自修改代码SMC(Self-Modifying Code)是程序运行期间修改或产生代码的一种机制[1]。自修改代码以其具有在程序执行过程中动态地修改和产生程序本身执行的指令的特点,在增加代码的理解难度阻止逆向工程和软件保护方面有广泛的应用[2-3]。有文献利用自修改代码技术描述基于RSA算法的软件加密保护方法[4],把自修改的特点和经典的RSA加密算法结合起来保护软件。为了能兼容原有的程序以及对现有程序进行完整支持,有的处理器实现了对自修改代码的支持[5-6]。在二进制翻译中,解决自修改代码问题,首先是要能够发现自修改代码,由于自修改代码的动态性,使得对一个纯静态翻译器来说是不可能的,对动态翻译器也比较困难。如果能够提供一些手段监视被修改的代码[7],就可以在发现源机器代码被修改后,置其对应的目标机器代码无效并进行重新翻译,从而解决自修改代码问题。DAISY[8]系统通过在页设置写保护标识,实现在发现自修改时销毁页中所有的翻译信息。QEMU[9-10]系统把所有翻译过的块的目标代码段存放在自己开辟的内存空间Code cache中。被翻译器翻译的程序的执行就是执行Code cache中翻译好的代码块。在自修改代码发生时,QEMU通过系统信号判断,然后清空Code cache中所有翻译好的块。参考文献[11]也给出关于二进制翻译中自修代码的介绍。
1 自修改代码
下面是一段汇编编写的自修改代码:
START: nop
mov $0x04, %eax
LOOP: inc %eax
TARGET: xor %eax, %eax
test %eax, %eax
jnz END
MODIFY: movb $0x32, TARGET
0x32 = “inc %eax”
jmp LOOP
END: nop
对于这段代码,当程序运行到MODIFY标识时,此处对应的指令“movb $0x32, TARGET”向地址为TARGET的内存单元写数据0x32,对应位置上的指令被修改,被修改位置上原来的指令“xor %eax, %eax”被自修改而变成了指令“inc %eax %eax”;程序继续运行至jmp LOOP指令,跳转到LOOP位置,当再次运行到TARGET位置时,则运行修改后的指令“inc %eax %eax”而非原代码段的指令“xor %eax, %eax”,这样“test %eax, %eax”的结果是非零值,接着jnz END使得程序运行结束。如果该段程序没有MODIFY这一自修改代码指令,此程序段将陷入死循环中。
2 QEMU的自修改代码机制
QEMU系统[9-10]是由法国人Farbic开发的一款多源多目标的二进制翻译系统。它支持源平台有PPC、ARM、X86、MIPS、SPARC和X86_64等,目标平台可以是X86、PPC、ARM、MIPS等。
QEMU系统中的Code cache是其为了存储翻译后的块而开辟的内存空间,通过存储基本块对应的翻译后的块到Code cache中,避免重复翻译带来的时间开销,加速翻译器翻译的效率。QEMU系统开辟了16 MB的内存空间作为系统的Code cache,并对每一个翻译块按照其生成的次序加入到Code cache中,直至Code cache被充满。当Code cache被充满时,QEMU采用全清空策略清除Code cache中所有翻译好的块,实际上就是清除QEMU中维护的源与目标之间的Hash表。全清空策略就是Code cache 从低地址到高地址依次存放每个翻译后的代码块,当出现Code cache 空间不足或程序阶段行为突变时,就将清除Code cache中所有翻译好代码块。在发生自修改时,QEMU同样采用全清空策略清除Code cache中翻译好的块,以防止因为自修改造成的Code cache不一致而使得翻译的程序错误执行。
3 自修改代码对翻译效率的影响分析
实验采用的操作系统是CetOS-4.6, 翻译器采用QEMU-0.9.0,针对的源和目标平台都是Intel x86指令集。
为了叙述方便,这里用SmcPro表示一个自修该代码实例。该实例把第1节中的自修改代码进行了进一步修改,用COUNT控制代码的循次数(即自修改代码的次数)。
为了描述方便,这里将用到的几个符号作如下说明: 对于SmcPro,根据自修改次数COUNT不同的值,相对应的程序为SMC_COUNT。如SMC_100表示SmcPro的COUNT为100,即自修改代码执行次数为100次。NSMC_COUNT表示与SMC_COUNT拥有相同代码量但不包含自修代码的程序段。
下面对SMC_COUNT和NSMC_COUNT程序在物理机和QEMU上进行测试和分析。
3.1 物理机上自修改代码的影响
表1是对每一个SMC_COUNT和NSMC_COUNT在物理机上执行10次得到的平均值对照表,行和列交汇的值为对应程序的执行时间效率。例如:表中行SMC和列50相交的位置的值是SMC_50在物理机上执行10次的时间平均值。
分析表1中的数据可知, SMC_COUNT和NSMC_COUNT在物理机上的执行时间相当。事实上,这正是由于它们在执行指令数量上是一致的,可以得出结论:物理机上自修改代码对程序运行的性能没有影响,程序的运行时间取决于程序运行过程中实际执行的指令数量。
3.2 QEMU上自修改代码的影响
下面对SMC_COUNT和NSMC_COUNT在QEMU用户模式下的测试结果进行分析,其中每个数据都是经过10次测试得到的平均值。有些数据是通过QEMU提供的日志信息得到, QEMU在用户模式下,通过-d out_asm参数可以将翻译的块信息输出到日志文件/tmp/qemu.log中。
3.2.1 时间对比
图1给出了在QEMU上执行的SMC和NSMC程序的执行时间和COUNT关系图,从表1和图1可知,对于在物理机上执行时间上基本没有差别的SMC和NSMC程序,在QEMU上的执行时间差别随自修改同比次数的增加而越来越大。
从图1可以清楚地看到,在QEMU上运行的测试程序随着自修改同比次数的增加,自修改程序比非自修改程序在执行时间上增加得更加明显。
对图1中的NSMC在自修改同比次数大于1 000后所表示的点进行线性拟合,可以得到式(1):
Tnsmc=0.000 026×C+0.000 291 (1)
其中,Tnsmc表示图中的纵坐标,即程序执行时间;C表示横坐标,即COUNT。
由式(1)可知,对于非自修改程序,COUNT平均每增加1,对应的时间增加0.000 026 s。
同样得到:
Tsmc=0.000 151×C-0.010 899 (2)
其中,Tsmc表示图中的纵坐标,即程序执行时间;C表示横坐标,即COUNT。
由式(2)可知,对于自修改程序,COUNT平均每增加1,对应的时间增加0.000 151 s,而截距为负值说明随着COUNT的增加,时间增加的速度也在增加。
由式(1)、式(2)可以得到,SMC程序执行时间随COUNT增大的增长率和NSMC程序的增长率的比值为:
由此可见,SMC程序的运行时间开销随COUNT的增长率是NSMC程序的约5.82倍。
图2是NSMC程序在QEMU和物理机上的执行时间对比图。由图可知,NSMC程序在QEMU和物理机上的执行时间都随COUNT的增加而增加,在QEMU上的执行时间略大于在物理机上的执行时间。为了对图进行定量分析,这里给出降速因子的定义。
定义:一个程序Pro(SMC或NSMC程序)在QEMU上的执行时间与其在物理机上的执行时间的比值,称为该程序在QEMU上执行的降速因子,记作:SDF(Pro)。
对于图2中所有描述出来的数据点,可以计算得出所有NSMC程序在QEMU上执行的平均降速因子:SDF(NSMC)=1.033 421。
图3是SMC在QEMU和物理机上的执行时间对比,SMC程序在QEMU和物理机上的执行时间随COUNT的增加而增加,在QEMU上的执行时间远远大于在物理机上的执行时间,增长速度也较物理机上要快得多。对于自修改同比次数大于1 000的点,计算得出图3中表示的所有SMC程序在QEMU上执行的平均降速因子SDF(SMC)=5.925 423。
3.2.2 翻译块数量对比
图4所示为翻译的块数与COUNT的关系图,纵坐标表示翻译的块数,用BLOCK表示,缩写表示为BLK。从图4可以看到,在QEMU翻译器上,SMC程序随着自修改同比次数的增加,翻译块的数量也在增加,而NSMC程序翻译块的个数基本不变。
对图4中NSMC表示的折线进行线性拟合,可以得到:
BLK=-0.003 045×C+1 672 (4)
其中,BLK表示图中的纵坐标,即翻译的块数;C表示横坐标,即COUNT。由式(4)可知,对于非自修改程序,随着COUNT的增加,翻译的块数在少量地减少,平均COUNT每增加1,翻译块数减少0.003 045块。
对图4中的SMC表示量,通过对COUNT大于1 000的点进行线性拟合,可以得到:
BLK=10.508 430×C+1 712.533 333 (5)
其中,BLK表示图中的纵坐标,即翻译的块数BLOCK;C表示横坐标,即COUNT。由式(5)可知,对于自修改程序,COUNT平均每增加1,对应的翻译块增加10.508 430个。
由式(2)和式(5)可知,对于自修改程序每增加一块造成的时间开销TPB(Time Per Block)为:
3.2.3 翻译块数对执行时间影响
图5和图6描述了程序在QEMU上执行的时间与翻译块数的关系。在翻译块的数量比较少时,程序在QEMU上的执行时间很难发现规律,执行时间具有很大的随机性;随着翻译块数的小幅增加,执行时间时增时减,如图5所示。但是当翻译块的数量增加到一定程度后,执行时间逐渐开始基本成线性增加,如图6所示,当翻译块数超过10 000后,程序的执行时间与翻译块数量基本成线性关系,通过对10 000块以后的数据点进行线性拟合得到的斜率为0.000 0144,这与式(6)的结论相当。由此可知, 当翻译块的数量达到一定程度后, 程序在QEMU上的执行时间与翻译块的数量基本成线性关系。
由于自修改代码是在程序执行过程中修改程序本身的,在以块为单位的二进制翻译过程中,随着自修次数的增加,造成的翻译块也急剧增加,从而使得程序在翻译器上的执行时间大大增加,究其根本原因是因为自修造成的Code cache中翻译好的块失效。在QEMU中,翻译器每翻译一个块都会把翻译后可以在目标机上执行的代码存放到Code cache中,但是由于自修代码的出现使得在Code cache中的块与源代码块在语义上不一致,因此必须清除掉Code cache中的翻译好的块,否则将执行与原来语义不一致的代码,造成翻译的错误。QEMU在自修改代码发生时对Code cache采用全清空策略[6],这样导致在Code cache中的所有翻译好的块都失效,从而在程序再次执行这些块时,不得不重新翻译,随着自修改同比次数的增加,重复翻译的块数也在急剧增加,翻译效率也就急剧下降。
通过测试用例对自修改代码和非自修改代码进行测试和分析,可以得出以下基本结论:(1)在物理机上,自修改代码对程序的执行时间没有影响;(2)自修改代码程序在QEMU上的执行时间随自修改同比次数增长的速度是非自修改程序的约5.82倍; (3)非自修改代码在QEMU上执行的平均降速因子约为1.033 421; (4)自修改代码在QEMU上执行的平均降速因子约为5.925 423;(5)自修改代码平均每增加1次自修改,对应在QEMU上的翻译块约增加10.51块; (6)在QEMU上执行的程序,翻译块数超过一定的值后,执行时间与翻译块数基本成线性关系。
在以块为基本单位的二进制翻译器中,当自修改代码发生时,被修改的源代码所在的块对应的Code cache中翻译好的块就必须被清除,否则将造成语义上的不一致,导致翻译错误。本文量化分析了自修改代码对QEMU翻译效率的影响,得出了一些初步结论,下一步将继续研究自修改代码翻译效率的提高问题。
参考文献
[1] Self-modifying code[EB/OL].(2009-04)[2014-01].http://en.wikipedia.org/wiki/Self-modifying code.
[2] KANZAKI Y, MONDEN A, NAKAMURA M, et al. Expl-oiting selfmodication mechanism for program protection[C].In:Proceedings of the 27th Annual International ComputerSoftware and Applications Conference, USA: IEEE Press,2003:170-181.
[3] MADOU M, ANCKAERT B, MOSELEY P, et al. Softwareprotection through dynamic code mutation[C]. In: Proceed-ings of Information Security Applications Conference, USA:ACM Press, 2005:194-206.
[4] 莫翩晨, 林和, 蔡万景,等. 基于RSA算法与自修改机制的软件保护[J]. 计算机研究与发展, 2006,43(3):140-144.
[5] Intel.IA-32 Intel architecture software developer′s manu-als[Z]. 2005.
[6] 张浩,钱学海.自修改代码在Godson-X上的处理实现[J].计算机工程, 2008,34(3):102-104.
[7] GSCHWIND M, ALTMAN E, SATHAYE S, et al. Dynamicand transparent binary translation[J]. IEEE Computer Soci-ety, 2000,33(3):54-59.
[8] EBCIOGLU K, ALTMAN E. DAISY: dynamic compilatonfor 100 percent architectural compatibility[C]. In: Proceed-ings of ISCA24, New York: ACM Press, 1997:26-37.
[9] QEMU: The open source processor emulator[EB/OL].(2010-03-31)[2014-01-26].http://fabrice.bellard.free.fr/qemu/about.html.
[10] BELLARD F. QEMU, a fast and portable dynamic trans-lator[C]. USENIX Annual Technical Conference, APR10-15, USENIX Association Proceedings of the Freenix/Open Source Track, 2005:41-46.
[11] SMITH J, NAIR R. Virtual machines: versatile platformsfor systems and processes[M]. Morgan Kaufmann, 2005.