近年来，恶意程序数量持续增加，卡巴斯基反恶意软件研究团队每天检测到32.5万种最新恶意文件^[1]，世界范围内拥有大量待分析的恶意程序样本。

目前，国内外面向二进制程序恶意性、安全性和脆弱性的算法识别技术展开了大量研究，已经成为恶意程序检测^[2-3]、协议逆向分析^[4-6]和加解密算法分析^[7-8]的重要研究内容。其中绝大部分是针对特定算法(如密码算法、摘要算法)的特点设计识别方案，但是不能识别广义的恶意程序算法。

程序算法识别技术可以分为静态识别技术^[8-9]和动态识别技术^[10-12]2种。静态识别技术通过分析二进制程序的静态反编译结果，提取程序算法的签名、常数特征等，实现程序算法的精确匹配。此方法无法对抗恶意程序常用的混淆、加壳、变异等保护手段，也无法识别没有签名特征的程序算法。

动态识别技术是在程序运行阶段实时监控恶意程序的指令执行及寄存器、内存的数据存储，能够避免代码静态保护手段带来的干扰，获取程序实际执行的指令流程和数据值，避免了无常数特征和签名特征的情况，但是识别的精确性难以保证。

由于恶意程序常经过代码混淆，本文提出一种基于离线指令流分析的恶意程序算法识别技术，构建动态的、指令级、启发式、普适的算法识别流程，能够在缺乏静态分析的情况下，记录并分析程序的动态汇编指令流，准确识别恶意程序的关键函数算法功能，包括但不限于分组密码、公钥密码、哈希摘要、字符串处理等，能够辅助分析恶意程序行为。

1 离线汇编指令流分析识别框架

动态识别技术可以分为实时分析识别和离线分析识别2种。实时分析识别利用程序动态监控技术，维护程序正常执行的同时，对当前执行的指令进行实时的分析和识别，其时间和空间负载难以支持对普通规模的程序的分析^[8]。

本研究采用离线分析识别的方法，将动态识别的过程拆分为动态指令流记录、离线指令流分析(特征提取)和算法识别模型3个独立的模块，能够将负载控制在实用范围内。离线分析识别框架流程图如图1所示，本文将对框架的构建思路、应用技术和算法模型进行详细阐述。

2 动态指令流记录

为了绕过恶意程序的代码混淆技术，研究选择利用Intel的Pin二进制插桩平台编写指令流记录模块，动态地记录程序执行的每条指令，并将指令流记录在基本块索引和程序流程日志两部分中。

研究采用基本块(basic block,BBL)作为汇编指令流记录的基本粒度，记录程序的基本块并建立索引序列。程序指令流以基本块索引序列的形式记录于日志，供后续进行离线分析。

1) 基本块索引记录

基本块是由若干条顺序无跳转的指令序列组成的指令流片段，可能被程序多次执行。每个基本块在首次执行时被分配1个唯一的索引号，并将索引号、基本块所含的指令序列记录于基本块索引文件中。

2) 程序流程记录

监控到程序执行一个基本块时，首先搜索基本块的索引号并记录在程序流程日志中。然后，监控基本块内的汇编指令的执行流程，按顺序指令内存操作数的值也记录在程序流程日志中。

3 离线指令流分析

离线分析的目的是从指令流中提取出程序算法的特征，供程序算法识别算法进行学习和建模。本研究从行为语义轮廓特征和关键常数特征2个维度进行分析，并提出特征提取方法。

程序算法和功能一般封装成函数，因此对程序算法功能的识别可以归结为对函数的识别。函数指令流片段可以通过动态影子调用栈分析技术^[13]，从程序动态指令流中进行切片划分。

3.1 行为语义轮廓特征提取

汇编指令流蕴含了程序的整个行为语义信息，根据函数功能的不同，汇编指令流的宏观语义和结构特征呈现出多样性。

程序的行为语义轮廓特征主要包括函数的统计特征(指令条数、操作码频度)，语义结构(选择结构、循环结构)和数据引用(数据依赖)特征等3个方面。

1) 指令条数。

指令条数是算法复杂度的度量指标。通过指令频度统计方法，对函数指令流片段中的指令条数计数，记作N。

2) 操作码频度。

不同类别的程序算法存在对特定操作码的使用偏向，如分组密码、摘要算法中移位运算指令的频度相比正常函数明显提高。统计指令流中非条件跳转类操作码的执行频度，其特征向量集合记作N_op。

3) 选择结构。

选择结构是程序算法不可或缺的部分，条件跳转指令代表了选择结构分支。因此通过统计条件跳转类的操作码在基本块中出现的静态频度，即可提取出选择结构的数量特征，其特征向量集合记作N_jmp。

4) 循环结构。

循环结构是函数功能重要的结构特征，难以被其他方式替代。选取循环结构的嵌套深度D_loop、每层嵌套循环体的执行轮数N_loop、递归结构标识R等3类结构特征组合为循环结构的特征向量。基于汇编指令流的循环结构的识别技术见节3.1.2 。

5) 数据依赖。

函数功能(特别是密码算法)本质上是对数据参数的处理过程，函数引入的数据主要分为函数参数、全局数据、立即数3类，并且将数据以变量的形式进行结构化处理。函数的数据依赖特征向量记作Ref，包括变量总数、数据总量、变量类型、变量长度等。具体的数据依赖识别技术见节3.1.3。

以下依次介绍面向上述5类行为语义轮廓特征提取的3种分析技术：指令频度特征统计技术、循环嵌套特征分析技术、数据依赖特征分析技术。

3.1.1 指令频度特征统计技术

为提取指令条数N、操作码频度N_op={N_code}和选择结构N_jmp等特征，需要利用指令频度统计技术，通过顺序检查指令流中的汇编指令并按照下列规则进行计数。

a) 是汇编指令，则N=N+1。

b) 是非条件跳转类的汇编指令，操作数是code，则N_code=N_code+1。

c) 是条件跳转类的汇编指令，则N_jmp=N_jmp+1.

3.1.2 循环嵌套特征分析技术

为提取循环结构特征，基于有向控制流图的静态分析^[14]方法无法对抗代码混淆技术的干扰。本研究提出面向指令流序列的循环嵌套分析方法，能识别递归和循环结构，并且提取嵌套深度和执行轮数等特征。

1) 循环结构定义。

程序的循环结构分为for循环、while循环、do-while循环、递归4种形式。

for循环、while循环和do-while循环在高级语言层面存在语法差别，但在汇编层面逻辑结构类似，其控制流结构示意图如图2所示。

其中，循环条件判断节点是一个以条件跳转指令结尾的基本块，其他节点可能由多个基本块组成。

递归结构的特点是，函数所属的基本块内的汇编指令调用函数自身。若在循环嵌套识别的搜索过程中发现这种情况，直接标识为递归结构并将描述递归的特征R置为真。

2) 指令流循环嵌套识别算法。

循环条件判断节点是循环结构的固定入口点，也是每轮循环的必经节点。因此通过搜索重复执行的基本块，能够识别出指令流中的循环结构。然后再采用递归策略，识别循环间的嵌套关系。

在程序汇编指令流记录阶段，每个基本块都分配了唯一索引号，因此重复执行的基本块在程序流程日志中记录为相同的索引号，能够方便的识别循环的重复执行操作。因此算法选择以程序流程日志中的基本块索引序列作为分析对象。

设函数的基本块索引序列为Ω=(B₁,B₂,B₃,…,B_N)，其中B_i∈indexs，indexs是基本块的索引号集合。初始化基本块嵌套深度序列D=(D₁,D₂,D₃,…,D_N)，D_i∈R。

循环嵌套后向搜索算法的伪代码如表1所示。

算法1的基本流程描述如下。

a) 针对输入的Ω序列，向后遍历基本块索引序列，搜索到2个最近的且重复执行的基本块，假设下标分别为i和j，进入下一步。若无法找到，则退出算法。

b) 对D_sub=(D_i,…,D_j)的嵌套深度值进行有条件的更新，并将Ω_sub=(B_i,…,B_j)作为新的输入序列，递归调用重复基本块的搜索算法，从而找出外层循环体内部嵌套的内层循环体，设置嵌套深度。递归搜索完毕后算法回溯到外层，继续向后重复a)步骤。

算法执行完毕后对D进行统计分析，提取最大嵌套深度D_loop和每层嵌套深度的循环体执行轮数N_loop作为特征向量。

3.1.3 数据依赖特征分析技术

为提取数据依赖特征Ref，本研究提出利用离线污点跟踪技术的数据依赖分析技术，能够标定外部数据的来源，提取函数依赖的数据类型、数量和规模。

3.1.3.1 离线污点跟踪

离线污点跟踪技术用于分析二进制程序的数据传播过程^[4]，具体的分析对象是记录下的汇编指令流日志。离线污点跟踪技术的主要定义如下。

1) 污点数据

污点是根据规则标定的跟踪目标，每个污点有唯一的索引标签，称作污点标签。污点数据的载体包括寄存器和内存，被污点传播(污染)的数据载体称作污点数据，污点数据中包含污点标签信息。

2) 污点标定

为了分析污点传播，首先需要引入污点。污点标定是根据污点标定规则，将污点标签赋予某个数据载体，并将其标记为污点数据的过程。

3) 污点传播

设汇编指令有源操作数X和目标操作数Y，操作数作为污点数据的载体，又被称为数据载体。若指令操作使得含有污点的数据从数据载体X传播到数据载体Y，则将X的污点标签添加或覆盖到Y中。

4) 污点消除

如果某条汇编指令的操作，使得未受污染的数据载体X给污点数据Y赋值，则清空Y的污点标签，并置为未污染状态。

3.1.3.2 数据依赖识别算法

函数参数的传递分为堆栈传递和寄存器传递2种，全局数据则由非堆栈的内存区间进行传递，立即数也是函数的重要数据依赖之一。数据依赖识别算法通过改进的污点跟踪策略，能够识别函数引入的数据来源，从而进一步分析数据依赖关系。

1) 改进污点跟踪策略

数据依赖识别算法的核心是采用特殊策略的污点跟踪算法，利用污点跟踪标定污点数据并分析传播流程的特性，识别外部数据的原始来源。根据以上目标改进的污点跟踪策略如下。

a) 拓展数据载体

数据载体拓展为栈内存、非栈内存、寄存器和立即数等4种类别。如果汇编指令的内存操作数的取址与esp相关，则记作栈内存，否则记作非栈内存。

b) 全污点标定

如果某条指令可能引起污点传播，但源操作数是未被污染的数据载体，则对其执行污点标定，并执行污点传播。

c) 无污点消除

为了避免污点数据的重复引入，取消污点消除的逻辑，污点数据不会被消除。

执行污点跟踪的过程中将记录所有进行污点标定的汇编指令，称作污点指令。由污点指令组成的序列称为污点引入指令流。污点指令的源操作数即为函数依赖的外部数据。

2) 提取数据依赖特征

程序算法逻辑中，数据以变量的形式存在和被处理。因此，污点引入指令流中满足以下条件的数据载体会被识别为一个变量：a) 作为污点指令源操作数的寄存器；b) 作为污点指令源操作数的立即数；c) 污点引入指令流中连续引入且地址连续的内存。同时，变量包括函数参数、全局数据和立即数3种数据类型，识别规则分别为：a) 变量载体是栈内存或寄存器；b) 变量载体是非栈内存；c) 变量载体是立即数。

利用上述数据变量特征的识别方法，能够提取出变量总数、数据总量、变量类型、变量长度等函数数据依赖的统计特征集合Ref。

3.2 关键常数特征提取

程序执行过程中通常会引用或生成特定的数据，作为算法参数、判断条件或者特定行为编号，这部分特定的数据称为关键常数。例如恶意程序会判断满足特定的条件(如时间)，才会执行恶意行为。

通过分析动态指令流，提取关键常数数值，能够从微观数值的维度对算法进行描述，作为行为语义轮廓特征的重要补充。

在指令层面，关键常数包括常量参数、系统调用号和库函数索引。同类功能的函数算法为了保证语义和结果的一致性，通常拥有固定的关键常数特征。

研究将通过分析函数的汇编指令流，识别关键常数，并将关键常数记号记录于关键常数日志中。描述关键常数的定义、提取方法和记号形式如下。

1) 常量参数

常量参数是固定数值的数据，是保证算法功能的运算结果一致性的首要特征。

常量参数可能以立即数或者全局数据的形式被函数引用，因此要基于节3.1.3 的数据，依赖分析出的污点引入指令流，从中提取出污点指令的源操作码的数值、类型。

立即数常量的记号是IMM_N，N∈R；全局数据常量的记号是MEM_N，N∈R。

2) 系统调用号

系统调用大致可分为设备管理、文件管理、进程控制、进程通信、存储管理、线程管理6类，是操作系统提供给编程人员的接口，每个系统调用函数分配有唯一的系统调用号。同样的函数功能必须通过同类的系统调用实现。

以Windows系统为例，系统调用号保存在eax寄存器中，系统调用的汇编指令包括syscall、sysenter或int 0x2e。因此，分析时需要实时记录程序eax寄存器的数值，当检查到系统调用指令出现，则取出eax的数值并记录为系统调用。

系统调用号的记号是SYS_N，N∈R。

3) 库函数

库函数是操作系统提供的较高语义抽象层次的公用函数，在程序中广泛出现。Pin二进制插桩平台具有一定的库函数分析能力，能够直接记录基本块的函数名称。同时，使用IDA等逆向分析工具，可以快速准确地识别出库函数名。

库函数的记号是LIB_Func，Func是库函数名。

4 恶意程序算法识别模型

恶意程序算法识别模型旨在利用机器学习和模型融合技术，结合行为语义轮廓和关键常数2个维度的特征，实现识别模型的优势互补，完成函数算法功能的高精度的分类识别。

首先，针对2个维度的特征，利用支持向量机(support vector machine，SVM)和朴素贝叶斯(naive Bayes,NB)机器学习算法，分别构建机器学习识别模型，称为初阶识别模型。然后构建仲裁模型，对2个初阶模型进行模型融合。融合过程示意图如图3所示。

4.1 行为语义轮廓初阶识别模型

行为语义轮廓特征是对函数算法功能的统计特征、结构特征的描述，针对行为语义轮廓特征构建的初阶识别模型使用SVM监督学习模型。SVM模型能够在少量样本的情况下，在模型的复杂性和推广能力之间寻求最佳折中。

1) 模型训练

首先需要准备模型的训练集，训练集由二进制程序样本组成。训练集中的样本划分为若干个算法类别C={C₁,C₂,…,C_M}，每个类别都应有相应的样本存在。针对每个程序样本的算法函数进行离线分析，提取出样本的行为语义轮廓特征向量Z=(N,N_op,N_jmp,N_loop,D_loop,R,Ref)。

SVM模型通过学习训练集的特征向量和算法类别的对应关系，能够自动拟合训练集并构建SVM分类器模型。

2) 模型识别

在识别阶段，面对从待识别样本中提取的语义轮廓特征向量，分类器计算样本属于所有算法类别的概率集合p_SVM={p(C_j|Z)|C_i∈C }，其中p(C_j|Z)最高的C_i即为样本的算法类别识别结果。

4.2 关键常数初阶识别模型

关键常数特征是对算法的公式参数、运算结果、固定行为的描述，针对关键常数特征构建的初阶识别模型使用朴素贝叶斯监督学习模型。NB分类算法^[15]是一种基于Bayes全概率公式的机器学习方法，应用于特征的条件独立性假设之上，能够忽略语法和特征词的顺序。

设由若干文档d组成的文档集合中，文档可能所属的全部类别集合是C={C₁,C₂,…，C_M}，文档中所有特征词集合是W={w₁,w₂,…，w_N}。NB分类器的学习和分类过程如下：1) 计算类别C_j中出现特征词w_i的先验概率p(w_i|C_j)。2) 计算类别C_j出现的概率p(C_j)，计算方法是C_j的文档数除以所有文档数。3) 将待分类的文档转换为特征词序列，d=(w⁰,w¹,…,w^m)，其中wⁱ∈W。4) 计算p(C_j |d)=p(C_j)$\prod\limits_{i=1}^{m}{{}}$p(w_i|C_j)。概率最高的C_j是文档d的识别类别。

本研究将函数的关键常数日志作为文档，将关键常数记号作为特征词，利用NB分类算法原理构建算法识别模型。

1) 模型训练

针对程序算法的训练集，提取出样本的关键常数日志D=(d₁,…,d_k)，并统计特征词集合W和类别集合C，通过NB分类器的学习步骤1)和2)计算先验概率。

2) 模型识别

在识别阶段，分析生成待识别样本的关键常数日志文档，通过步骤3)和4)得到p_Bayes={p(C_j|d) |C_j∈C}，概率最高的C_j即为样本的算法类别识别结果。

4.3 仲裁模型

节4.2构建的2个初阶算法识别模型，是从不同的角度对程序的算法功能进行描述，并根据特征的统计特性构造的机器学习模型。

为了综合2个模型的优点，使整体模型能够结合2个维度的特征向量，构建出准确性更高、泛化能力更强的识别模型，研究引入了仲裁模型对2个初阶模型进行模型融合，融合过程如图3所示。

设经过特征提取的程序样本x=(Z,d,C_j)，其中Z是行为轮廓特征向量，d是特征词序列，C_j为程序样本的算法类别。将原始程序样本集X={x₁,…,x_N}按1∶1随机采样分割为初阶训练集X₁={x₁,…,x_n}和初阶测试集X₂={x_n+1,…,x_N}。

1) 初阶模型训练

初阶模型包括行为语义轮廓初阶识别模型和关键常数特征初阶识别模型。2个模型都采用X₁作为训练集，选择相应的特征向量进行学习，完成初阶模型的构建。

2) 初阶模型识别

2个初阶模型都对X₂样本集的样本进行识别，并输出样本的初阶类别概率特征向量p=(p_SVM,p_Bayes)，其中p_SVM是SVM模型输出的样本属于各类别的概率，p_Bayes是贝叶斯模型输出的样本属于各类别的概率。根据初阶模型的初步识别结果，将X₂中的样本拓展为x=(Z,d,p_SVM,p_Bayes,C_j)。

3) 仲裁模型训练

选择SVM作为仲裁模型，实现对初阶模型进行融合。仲裁模型的训练方法是，将拓展后的X₂样本集作为训练集，以p=(p_SVM,p_Bayes)作为特征向量进行模型学习。

4) 仲裁模型识别

面对未知类别的样本，首先提取样本的特征向量，对2个初阶模型进行识别，获得初阶类别概率特征向量p；然后将p作为仲裁模型的输入，以仲裁模型的识别结果作为样本的算法类别识别结果。

5 测试与结果分析

为验证离线指令流分析对算法描述的效果，以及模型构建思路的正确性，分别对2个初阶模型和仲裁模型进行测试验证。

恶意程序的关键算法函数大多为密码算法、字符串处理以及很多无法狭义归类的功能函数。考虑到数据集的丰富性，本文选用的程序样本数据集来自程序设计线上测试平台(http://code.bupt.edu.cn/)，搜集了包括密码算法、字符串处理、非狭义算法在内的20个类别的C++程序代码样本并进行编译，每个类别的样本数量在10~200个之间，整个样本集共包含2 066个代码样本。

数据集中的20个算法涵盖了密码算法、排序算法、字符串操作、数学求解、递归算法等狭义算法共10类，以及非狭义算法功能共10类。因此算法识别模型在本数据集样本上的评估效果能够对等于恶意程序样本。

5.1 评估指标

选取准确率、召回率和F1值作为评估指标。

1) 正确率

被识别为本类别的样本中，确实属于本类别的样本所占的比例。准确率越高，则查准率越高。

2) 召回率

本类别的样本中，被正确识别为本类别的样本所占的比例。召回率越高，则查全率越高。

3) F1值

F1值等于正确率×召回率×2 / (正确率+召回率)，F1值越高，则模型的综合评价越高。

5.2 初阶模型测试

将数据集按照1∶1比例随机采样为初阶训练集和初阶测试集。使用训练集对2个初阶模型进行训练，生成的2个算法识别模型在初阶测试集上的识别结果如表2和3所示。表中只列出10类狭义算法的类别名称和评估指标，最终的总评指标是对20类算法评估指标的加权平均值。

面向行为语义轮廓特征的SVM算法识别模型的平均F1值为98.1%，在素数检验、水仙花数求解、最大值、斐波那契数列等以算法语义为主的算法识别中表现优异。

面向关键常数特征的贝叶斯算法识别模型的平均F1值为95.9%。擅长识别多表代换加密、凯撒加密等以关键常数参数为主的算法。

2个初阶模型在算法识别上各有优势，两者明显呈现互补关系，并且都有超过95%的准确率和召回率，单模型的效果已经达到较高水准。

5.3 仲裁模型测试

将初阶测试集按照8∶2比例随机采样为融合训练集和融合测试集。令仲裁模型对融合训练集的初阶类别概率特征向量p进行学习，然后在融合测试集上进行识别。识别结果如表4所示。

因为对初阶测试集的二次采样操作，融合测试集样本总数只有207个，单次测试的说服力不强。因此，对仲裁模型同时采用十折验证法，即将初阶测试集平均划分为10份，每份占原样本集的10%。10轮测试中，每次选择1份样本集作为融合测试集，其他9份作为融合训练集，计算识别模型的F1值。

十折验证的F1值分别为100%、98.9%、100%、100%、98.9%、97.4%、100%、97.4%、98.7%、99.2%、99.2%。因此，仲裁模型的平均F1值为99.1%，和表3的评估结果一致。

5.4 测试结果分析

2个初阶模型和仲裁模型在20分类数据集上的对比识别结果如图4所示。相比于初阶模型，仲裁模型的识别效果得到极大提升,准确率、召回率和F1值都超过99%，总体上拥有相当高的准确性。

对于大部分程序算法类别，经初阶模型融合互补后，F1值超过或者等于初阶模型的最大F1值，说明模型融合达到了特征向量综合互补的效果。

因为仲裁模型的训练集样本数少于初阶模型的训练集样本数，且两者的训练集样本不存在交集。所以对于少数程序算法类别(编号3、7、8)，仲裁模型的F1值略微低于F1值最高的初阶模型属于正常现象。

仲裁模型通过对初阶模型的识别结果的合理融合，对二进制程序进行了全方位、多角度的行为描述，构造了面向恶意程序关键函数算法功能的普适机器学习识别模型，并且达到了预期的精确效果。

6 结论

本文提出基于离线汇编指令流分析的恶意程序算法识别技术，综合运用了逆向分析、污点跟踪、机器学习等技术，能够在汇编指令层面从多角度提取程序的动态行为特征，并自动生成面向恶意程序关键函数的算法功能智能识别模型。

测试结果表明：该方法能够精确识别程序函数的广义算法功能，拥有动态、普适、高准确的优点。下一步工作将基于本文提出的识别模型，对恶意程序如病毒、木马、蠕虫的高阶行为乃至整个程序的行为进行识别和分类，从而实现恶意程序检测的智能化。