基于动态数据流分析的虚拟机保护破解技术

黄荷洁,康 绯,舒 辉

(解放军信息工程大学数学工程与先进计算国家重点实验室,郑州450000)

基于动态数据流分析的虚拟机保护破解技术

黄荷洁,康 绯,舒 辉

(解放军信息工程大学数学工程与先进计算国家重点实验室,郑州450000)

由于虚拟机采用虚拟化技术和代码混淆技术,采用传统的逆向分析方法还原被虚拟机保护的算法时存在较大困难。为此,提出一种基于动态数据流分析的虚拟机保护破解方法。以动态二进制插桩平台Pin作为支撑,跟踪记录被虚拟机保护的算法在动态执行过程中的数据流信息,对记录的数据流信息进行整理分析,获取虚拟机指令的解释执行轨迹,还原程序的控制流图,根据轨迹信息对数据生成过程进行分层次、分阶段还原,并由分析人员结合控制流图和数据生成过程进行算法重构。实验结果证明,该方法能够正确还原程序的控制流和数据生成过程,辅助分析人员完成被保护算法的重构。

数据流分析;虚拟机保护;控制流还原;算法还原

1 概述

软件核心算法的逆向分析在网络协议逆向、恶意代码机理分析、协议特征提取等安全应用中发挥着重要的作用。目前恶意软件广泛采用虚拟机保护等抗分析技术对核心算法进行保护,使得已有的逆向分析方法面临新的挑战。

虚拟机保护技术[1]是指将基于x86指令系统的可执行代码转换为字节码(Pcode)并加入虚拟机解释器,程序运行时,由虚拟机解释器对转换后的Pcode进行解释执行。为增加逆向分析难度,虚拟机保护软件通常采用指令集随机化、虚假跳转指令、垃圾指令、常数加密等方式对虚拟机解释器进行高强混淆[2],使得一条汇编指令经虚拟机处理后,会膨胀几百甚至几千倍。采用传统的静态分析与动态调试技术对虚拟机进行分析,得到的是虚拟机解释器的逻辑,并不能获取被保护代码的语义信息;同时由于采用了混淆技术,通过人工分析还原虚拟机指令与x86指令对应关系,然后还原被保护算法的方式也很难奏效。因此深入研究虚拟机保护技术,提出有效的自动化分析方法显得意义重大。

在典型的虚拟机保护逆向分析研究成果中,文献[3]提出通过动态数据流分析、污点追踪和聚类分析等手段,获取字节码语法语义信息。这种方法只能还原部分Pcode的语义信息。Rolf Rolles提出通过逆向虚拟机结构,化简被混淆指令,将虚拟机指令转换中间语言,然后将中间语言编译转换为对应的x86指令的方法来还原被保护的代码[4]。这种方法要求虚拟机解释器的结构满足一定条件,因此,并不具有通用性;同时通过指令化简很难有效应对虚拟机中使用高强度混淆代码。文献[5]提出通过识别被保护软件的API调用,然后抽取出所有影响API参数的指令来近似表示程序的原始代码。这种方法只能得到影响API参数的指令,因此,并不能有效还原被保护算法。

针对当前分析方法对于重构被保护算法方面存在的不足,本文提出一种基于动态数据流分析[6-7]的虚拟机保护破解方法,利用动态二进制插桩[8]平台Pin[9]将虚拟机解释器动态执行过程中的数据流信息记录成二进制文件,并以这些文件作为分析基础,提取虚拟机指令的执行轨迹,然后重构被保护算法的控制流;采用改进的数据流分析[7,10]算法对被保护算法的输出数据的生成过程进行分层次、分阶段还原;最终由分析人员结合控制流和数据生成过程对被保护算法进行重构。

2 虚拟机保护破解方法

首先定义虚拟机保护破解要解决的具体问题。

定义1 虚拟机保护破解

对于一个被虚拟机保护的函数F(x),对它进行破解是指通过还原被保护算法的控制流图(Control Flow Graph,CFG)和函数输入、输出数据之间的运算关系(IOOR),最终重构出被保护算法,得到F′(x),使得对于任意的输入x,有F(x)=F′(x),即F(x)与F′(x)等价。

本文方法的基本原理是虚拟机解释器对虚拟机代码(VMCode)的解释执行轨迹包含着程序的控制流信息,虚拟机的执行过程包含着数据的处理过程,通过对虚拟机执行过程中的数据流信息进行整理分析,能够得到被保护算法的CFG和IOOR,最终重构出被保护算法。具体而言,在虚拟机指令未被混淆的情况下,x86指令被转换为等价的Pcode,因此, x86指令代码与VMCode的CFG相同,同时,对于同样的输入,VMCode与x86指令代码的执行轨迹一致。通过对VMCode的读取过程进行提取和分析,能够重构原始x86指令代码的控制流。由于虚拟机的本质只是将原始x86指令的逻辑隐藏在Pcode的解释执行过程中。因此采用数据流分析技术,能够还原出被保护算法的输入、输出数据之间的运算关系。将数据的运算过程与控制流进行整合,就能重构出被保护算法。

基于以上研究思路,将虚拟机保护破解过程分为3个阶段:动态执行轨迹记录,控制流图还原和数据生成过程还原阶段。动态执行轨迹记录阶段主要记录每条指令的寄存器和访存信息。控制流还原阶段通过对访存信息进行分析,识别出VMCode所在内存区域,获取VMCode的执行轨迹信息,然后还原程序的CFG。数据生成过程还原阶段通过对输出数据进行分层次、分阶段数据流追踪,获取其生成过程。

2.1 动态执行轨迹记录

对于基于数据流分析的虚拟机逆破解方法而言,获取真实可靠的进程动态执行信息是重要的基础环节。为此,笔者编写了基于动态分析平台 Pin的指令流记录插件,记录用户指定程序片段在执行期间的数据流信息。由于虚拟机中加入了大量垃圾指令,因此实际执行到的指令条数往往规模庞大,为了提高效率,采用缓存延迟写入技术将执行期的每条指令的寄存器值和内存读写信息记录为二进制文件,供后期分析使用。

2.2 控制流图还原

控制流图还原的基本思路是虚拟机执行过程包含了对VMCode的读取和解释执行,通过对每条指令的访存信息进行整理筛选,就能得到VMCode所在内存区域,根据VMCode的读取轨迹能够部分地还原CFG,通过多次运行,增大路径覆盖率,最终完整地还原被保护算法的CFG。

定义2 虚拟机输入数据(VMInput)

获取虚拟机指令区域(VMInsRgn)就是对VMInput进行整理筛选的过程。VMInput由3个部分组成:虚拟机指令,堆栈中的临时数据,可执行模块中的相关数据。VMInsRgn满足如下3个条件:包含于可执行模块中;包含于或与虚拟机解释器所在的PE文件的节相邻;被IDA静态分析识别为数据。按照上述条件对 VMInput进行筛选,最终得到VMInsRgn＜InsStartAddr,InsSize＞,其中,InsStartAddr是区域的起始地址;InsSize是区域大小。

在定位VMInsRgn后,将对此区域进行的读操作视为虚拟机指令读取,因此,对此区域的内存读取轨迹的集合就是虚拟机指令的执行轨迹,记作traces,每一条执行轨迹记作trace＜StartAddr,EndAddr＞,表示一串内存空间连续的虚拟机指令被读取, StartAddr,EndAddr分别表示虚拟机指令起始、结束地址。生成traces的具体算法如下:

Step 1 将当前trace的StartAddr、EndAddr置为无效,取第1条指令的内存读取信息Rc＜Addr, Size＞,其中,Addr表示内存的起始地址;Size表示大小。

Step 2 如果Rc与VMInsRgn满足InsStartAddr≤Addr＜(InsStartAddr+InsSize),转 Step 3,否则转Step 4。

Step 3 上次读取的虚拟机指令区域Rb与Rc是否满足AddrRb+SizeRb=AddrRc,满足则转Step 4;否则EndAddrtrace=AddrRb+SizeRb,并开始一条新的轨迹trace_new,同时StartAddrtrace_new=AddrRc。

Step 4 指令分析是否结束,结束则算法结束,否则读取下一条指令访存信息存入Rc,转Step 2。

定义3 虚拟机基本块

一条顺序执行的Pcode序列,且只有一个入口和一个出口,入口是其中的第1条Pcode,出口是最后一条Pcode,记作VMBB＜StartAddr,EndAddr＞,其中,StartAddr和EndAddr表示虚拟机基本块的起始和结束地址。

为了能够重构虚拟机指令的控制流,首先需要将TRACES划分基本块。根据基本块的定义,首先将traces拆分,将拆分结果作为虚拟机指令的基本块。划分基本块的算法如下:

Step 1 将一条trace＜StartAddr,EndAddr＞看做一个由虚拟机指令构成的内存区域 U ＜StartAddr,EndAddr＞;

Step 2 将U1,U2,…,Um拆分为 VMBB1, VMBB2,…,VMBBn,使其满足如下条件:

(1)对于∀ VMBBi和 VMBBj,满足VMBBi∩VMBBj=Ø

(2)对∀VMBBi,∃Uj使得满足以下任意一个:

Step 3 拆分后的VMBB1,VMBB2,…,VMBBn为虚拟机指令的基本块。

如图1所示,3条执行轨迹U1,U2和U3,经过拆分后得到 4个基本块 VMBB1,VMBB2,VMBB3, VMBB4。

图1 轨迹拆分为基本块的过程

顺着虚拟机指令执行轨迹,在连续执行的VMBB之间绘制有向边,可以得到被保护算法的部分CFG。图1经过重构之后到控制流图(图2),可以看到存在B2→B2和B2→B3的边,可以推断出B2的尾部存在条件分支跳转语句。通过输入不同数据增加路径覆盖率,能够得到较完整的CFG。

图2 控制流图

2.3 数据生成过程还原

为了获取被保护算法的输入、输出数据之间的运算关系,需要对输出数据进行数据流追踪,追踪过程应该结合虚拟机自身特点以及控制流信息来优化追踪过程,例如:虚拟机通常采用常数加密、垃圾指令混淆,因此实际执行到的指令规模非常庞大,对整个执行过程进行数据流追踪的方法并不适用;对于被保护算法中调用的子函数,虚拟机并不会对其进行保护,如以下代码所示,如果VMProtectedFunc函数是被保护的函数,函数中调用了func1,那么func1是不会被保护的,因此,对算法重构来说,子函数并不需要进行数据流分析,只需要获取函数输入、输出之间的关系;对于控制流中的循环结构,只需要分析1次;对于条件跳转的分析,则需要首先定位虚拟机解释执行轨迹的差异点,然后进行反向追踪。因此本文对数据生成过程的分析以VMBB为单位,采用分层次、分阶段的方式进行,即根据控制流图还原阶段对程序中控制结构如条件跳转、循环结构以及函数调用的识别结果,将反向数据流跟踪过程划分阶段,以VMBB为分析单位,获取程序对数据的处理过程,生成数据流传播树TPT＜Node,Edge＞,其中, Node是TPT中所有节点的集合,包含了污点源和指令操作数;Edge是TPT的边的集合,记录了所有节点的上下级和逻辑运算关系。

由于虚拟机解释器被高强度混淆,因此首先需要对数据流分析算法进行改进。常数加密是虚拟机中大量使用的混淆手段。Themida[11]虚拟机解释器代码中常见的指令序列如下:

指令序列1:

指令序列2:

如果对指令序列1进行反向数据流追踪,并假定eax为污点源。经过反向数据流追踪最终得到如图3所示的数据流传播树。显然由于算法中的常数加密,导致树的节点个数增多,同时树的高度也增加了。同理,如果指令序列2进行数据流追踪,并假定ecx为污点源,由于数据流分析并不分析每条指令的语义信息,最终会导致ecx与edx寄存器错误的关联。

图3 数据流传播树

由于虚拟机执行过程中指令规模庞大,为减少数据流传播树的节点个数,降低树的高度,方便传播关系的分析,有必要对这些指令序列进行处理。对于上述例子,在对指令序列1中的mov edx,ecx进行分析时,如果能够识别出ecx的值为常数,就不再需要对ecx进行污点分析;同理,对指令序列2中的sub ecx,edx进行分析时,如果能识别出ecx是常数,则不会将ecx与edx关联。为了应对常数加密,引入常量识别算法,该算法以x86指令基本块为单位,识别同一基本块中的某条指令在多次执行过程中的值是否为固定值。具体算法流程如图4所示。

图4 常量识别算法流程

除了常数加密,虚拟机中大量使用堆栈来存取、传递临时数据,存在大量类似如下的指令序列:

如果对edi进行反向数据流追踪,最终由于数据的移动使树的高度增加。通过对传送类指令(如mov,push,pop,xchg等)进行处理,当分析该类指令时,并不增加新的叶子节点,只替换其父节点,就能有效地降低树高。

引入常量识别和传送类指令优化后,设计针对虚拟机的反向数据流跟踪算法,该算法首先将用户指定的内存区域标记为污点源,然后逆着程序的执行轨迹进行污点传播分析,最终生成一张TPT。该算法能够解决污点源由哪些数据、经过哪些运算产生等问题,算法流程如图5所示。

图5 数据流追踪算法流程

3 系统实现与测试

本文基于Pin设计并实现了虚拟机保护算法的破解系统。系统的工作流程如下:

(1)在Pin的监控下运行测试程序,通过执行轨迹记录模块记录指令的数据流信息。

(2)控制流还原模块识别出虚拟机指令所在区域,提取虚拟机指令执行轨迹信息,然后划分VMBB并还原CFG。

(3)数据生成过程还原模块辅助分析人员完成对数据的生成过程的逆向分析,由分析人员结合控制流图和数据的生成过程对被保护算法进行重构。

为了验证该算法还原技术的有效性,本文通过Themida提供的SDK方式对一段算法进行虚拟机加壳保护,采用该技术进行还原。测试环境如表1所示。

表1 测试环境

使用Themida SDK方式对代码进行虚拟化保护,只需要对被保护的源代码加上起始标志VM_START和结束标志VM_END这2个宏,编译生成可执行程序之后,运行Themida进行加壳。测试代码如下:

编译生成的程序经过IDA反汇编,结果如下:

采用 Themida默认的虚拟机保护设置,即Processor Type:Mutable CISC processor;Multiprocessor: 1 CPU;Opcode Type:Metamorphic-Level2;Dynamic Opcode:20%Dynamic对代码进行虚拟机保护。

通过以下代码调用函数,并对VM_test函数进行动态轨迹记录。分析记录结果获取虚拟机输入数据,结合IDA分析得到0x4f1ad6～0x4f5216为虚拟机指令所在区域。

char data[]="VM_test";

VM_test(data,strlen(data),true);

通过IDA反汇编原始x86指令得到被保护算法的CFG如图6所示。经过控制流还原,得到虚拟机指令的CFG,如图7所示。

图6 x86指令的控制流图

图7 虚拟机指令的控制流图

对比 x86指令和虚拟机指令的 CFG,得到VMBB与x86指令基本块的对应关系,如表2所示。

表2 寄存器信息二进制文件格式

对算法的运算过程进行逆向,首先确定要分析的数据为pdata指向的最终输出数据。对输出的数据的第一个字节进行反向数据流追踪,以虚拟机基本块为单位分析输入输出数据,确定数据的生成过程在基本块0x4f4ee3～0x4f5197,起始和结束执行指令序列分别为1847260和1986050。通过对此执行序列范围以内的指令进行反向数据流追踪,得到数据流传播树,如图8所示,可以看出,数据只是进行了简单的异或,同理可以还原其他基本块中对输出数据的处理过程。

图8 数据流传播树

通过输入不同数据覆盖更多路径,对记录的执行轨迹信息进行分析,最终得到程序的控制流。对0x4f4e2c～0x4f4ee2的几次不同解释执行过程进行比对,找到差异点,进行反向数据流追踪,可以得到循环次数与VM_test的第2个参数有关。结合控制流和虚拟机基本块的逆向分析,最终能够实现对被保护算法的重构。

4 结束语

本文以动态数据流分析技术为基础,提出一种针对虚拟机保护的破解方法,论述了基本原理和实现过程,并通过实例测试加以验证。测试结果表明,该方法能够对被保护算法的控制流图和数据生成过程进行有效还原,辅助分析人员完成对被保护算法的重构,通过提高被保护代码的执行覆盖率,最终实现被保护算法的完整还原。后续改进工作包括:分析不同指令集和保护强度的虚拟机,给出更有针对性的逆向分析方法,并设计相应的还原算法,实现对被保护算法更自动化的还原。

[1] 段 钢.加密与解密[M].3版.北京:电子工业出版社,2009.

[2] Collberg C,Nagra J.Surreptitious Software:Obfuscation, Watermarking,and Tamperproofing for Program Protection[M].[S.l.]:Addison-Wesley Professional,2009.

[3] Sharif M,Lanzi A,Giffin J.Automatic Reverse Engineering of Malware Emulators[C]//Proc.of 2009 IEEE Symposium on Security and Privacy.Berkeley,USA: IEEE Press,2009:94-109.

[4] Rolles R.Unpacking Virtualization Obfuscators[C]// Proc.of WOOT'09.Montreal,Canada:[s.n.],2009:1.

[5] Coogan K,Lu Gen,Debray S.Deobfuscatiion Virtualization-obfuscated Software:A Semantics-based Approa-ch [C]//Proc.of CCS'11.Chicago,USA:ACM Presss, 2011:275-284.

[6] 陈火旺,刘春林,谭庆平,等.程序设计语言编译原理[M].3版.北京:国防工业出版社,2007.

[7] Newsome J,Song D.Dynamic Taint Analysis for Automatic Detection,Analysis,and Signature Generation of Exploits on Commodity Software[C]//Proc.of NDSS'05. San Diego,USA:[s.n.],2005.

[8] Nethercote N.Dynamic Binary Analysis and Instrumentation or Building Tools Is Easy[D].Cambridge,UK: University of Cambridge,2004.

[9] Luk Chi-Keung.Pin:Building Customized Program Analysis Tools with Dynamic Instrumentation[C]//Proc. of PLDI'05.Chicago,USA:[s.n.],2005:190-200.

[10] Clause J,Li Wanchun,Orso A.Dytan:A Generic Dynamic Taint Analysis Framework[C]//Proc.of International Symposium on Software Testing and Analysis. London,UK:[s.n.],2007:196-206.

[11] Oreans Technologies:Themida[EB/OL].[2009-05-06]. http://www.oreans.com/.

编辑 金胡考

Reverse Technology of Virtual Machine Protection Based on Dynamic Dataflow Analysis

HUANG He-jie,KANG Fei,SHU Hui
(State Key Laboratory of Mathematical Engineering and Advanced Computing, PLA Information Engineering University,Zhengzhou 450000,China)

Traditional reverse analysis methods are not very effective in the analysis of the algorithms protected by virtual machine because of virtualization technology and code obfuscation technology.Aiming at this problem,this paper presents a virtual machine protection reverse engineering technique based on dataflow analysis.It uses Pin platform to record the data flow information during the execution of the protected algorithms dynamically,analyses the record information,restores the track of the virtual machine instructions and the control flow graph of the protected algorithms, gets data generation process hierarchically by using the track information.Then the analyzer uses those information to reconstruct the protected algorithms.Experimental results show that the proposed method can correctly restore the program control flow and data generation process,and assist the analyzer to reconstruct the protected algorithms.

dataflow analysis;virtual machine protection;control flow reduction;algorithm reduction

1000-3428(2014)09-0059-07

A

TP309

10.3969/j.issn.1000-3428.2014.09.013

国家保密局科研基金资助项目(BMKY2013B03-1)。

黄荷洁(1989-),男,硕士研究生,主研方向:网络与信息安全;康 绯,副教授;舒 辉,副教授、博士。

2013-09-11

2013-11-02E-mail:cssembly@gmail.com