基于非用户操作序列的恶意软件检测方法

罗文塽，曹天杰

(中国矿业大学 计算机科学与技术学院，江苏 徐州 221116)(*通信作者电子邮箱luows@cumt.edu.cn)

0 引言

Android自2012年以来一直是最流行的移动操作系统，它以其开放性和实用性赢得了大多数人的喜爱[1]。由于其开放性等特点，Android的市场份额在2016年第三季度达到了86.8%，仅在中国国内，Android手机就卖出了多达4.25亿部，占国内智能手机销售量的81%。

近几年，Android手机发展迅猛，Android平台上的应用软件数量日益增多，Android手机为用户带来了极大便利，但同时也为黑客提供了各种机会。由于Android系统的开源性以及市场自身制度的不完善，导致恶意软件数量急剧增加[2]。McAfee Labs的一份报告中显示，移动恶意软件数量在2017年第一季度增长了37%[3]。Android恶意软件数量一直处于上升阶段，并且新的恶意软件数量也在不断增加。今天，虽然用户享受了Android应用程序带来的便利，但用户的个人信息，如电话号码、当前位置和联系信息等，可能会被一些不良的应用程序开发商滥用。许多恶意的智能手机应用程序未经用户许可窃取用户信息，拨打电话，发送短信等，给用户带来了巨大的威胁。为了保护用户，Android应用市场非常需要强大的分析工具来识别和删除恶意应用，因此，如何有效地完成对恶意软件的检测已经成为了一项亟待解决的问题。

1 相关工作

近些年Android恶意软件的检测被越来越多的研究学者所关注，目前恶意软件检测工作主要分为静态检测和动态检测[4]。

静态分析是在不运行代码的情况下，对应用程序进行反编译,然后对其进行源代码级的解析。Junaid等[5]提出了一个Dexteroid的静态分析框架，它通过反向工程生命周期模型来捕获Android组件的行为，导出事件序列并使用它们来检测由特定事件序列发起的攻击。Wu等[6]通过提取数据流相关的应用程序编程接口(Application Programming Interface， API)级特征，并采用机器学习方法进一步优化数据流相关的API列表进行恶意软件检测，该方法大幅度提高了敏感数据传输分析的效率，得到了97.66%的准确率。Arzt等[7]提出了一个静态污点分析系统FlowDroid，通过构建一个过程间控制流图，采用图可达性分析来识别可能的隐私泄露路径。Du等[8]提出了一种基于多源的方法来检测Android恶意软件，强调传统的静态特性、控制流图和重打包的特点。每个类别的特征被视为特征提取规则建立和分类中的独立信息源。使用Dempster-Shafer算法来融合这些信息源，以提高恶意软件检测的准确性，而不增加从反汇编代码中提取的太多不稳定特性，并且在抗代码混淆技术方面具有更好的性能。Guan等[9]提出了一个RepDetector的原型，该原型基于语义的方法来检测重打包的应用程序。通过使用状态流图捕获函数的输入输出状态，以描述应用程序的语义行为，通过使用马氏距离比较不同应用程序之间函数的相似度，从而进行恶意软件识别，该方法可以有效地检测出重打包的应用程序，并且可以容忍某些噪声插入或复杂的混淆，因此具有抗混淆性。Feizollah等[10]提出了AndroDialysis，一个分析两种不同类型的Intent对象的系统。该系统评估显式和隐式Android Intents的有效性，作为识别恶意应用程序的一个显著特征。实验结果表明Intents拥有语义丰富的特征，与其他特征如权限相比，能够对恶意软件的意图进行编码，具有更快、更好的恶意软件检测效果。Wang等[11]提出了一个DroidChain的原型系统，通过结合静态分析和行为链模型，使用矩阵理论Wxshall-extend来计算可达性矩阵从而进行恶意软件检测。

动态分析通过在受控环境中运行应用程序并监视其行为来完成恶意软件的检测。动态检测使用的技术手段主要是软件行为监控，从而得到软件的行为信息。Xiao等[12]使用系统调用序列来区分恶意软件。通过跟踪在不同事件下的应用程序的系统调用，使用两个不同的特征模型频率向量和共生矩阵，从系统调用序列中提取特征，并应用重力向量的自适应正则化和其他机器学习算法，分别基于上述两个模型来识别Android恶意软件。实验结果表明，共生矩阵具有更好的检测率。Enck等[13]提出TaintDroid，目的是跟踪隐私敏感数据流，并监视应用程序如何访问和操纵用户个人数据，以便检测敏感数据何时通过不受信任的应用程序离开系统。孙润康等[14]分析了当前Android恶意软件特征，提出了一种Android软件行为动态监控框架，并通过采用信息增益、卡方检验和Fisher Score的特征选择方法评估了支持向量机、决策树、k-近邻和朴素贝叶斯分类器在Android恶意软件分类检测方面的有效性。Feng等[15]提出了一个SCDFLOW(Selecting Critical Data Flows)系统，该系统通过特征选择算法CFlowSel，基于每个流的频率差来自动选择Android应用程序中的关键数据流，并将这些关键数据流作为异常行为检测特征，通过关键数据流进行恶意软件识别。

静态检测可以对软件进行全面分析，并且检测速度较快，但对未知恶意软件的检测具有一定滞后性。动态检测准确率较高，但同时检测成本也较高，检测时间较长，且无法覆盖程序中的所有路径。本文采用静态检测的方法。对于智能手机恶意软件的静态检测主要是针对应用程序中敏感数据传输的检测，即用户的隐私数据是否离开设备。然而，在这个时代，许多良性的应用程序通常需要收集敏感数据，如位置、联系人来提供给用户更多的功能和服务。云的出现，使得大多数应用程序的数据向云端发送；同时，窃取用户数据的恶意应用程序也可能表现出相同的行为，使用户的隐私信息遭到泄露，这大幅度增加了通过敏感数据传输的检测来识别恶意应用程序的难度，因此，敏感数据的传输本身可能不表示真正的隐私泄露。本文提出了一种静态的恶意软件检测方法，通过提取API调用信息，构建应用程序的函数调用流程图，提取出其中的非用户操作序列进行恶意软件检测，并通过不断更新恶意行为库的方式来解决对未知恶意软件的检测的滞后性问题。

2 相关概念

2.1 敏感API

应用程序的字节码中包含应用程序的代码等信息，如API调用信息。应用程序使用这些API函数完成应用程序所需功能，如获取手机的个人信息，发送短信、拨打电话等；同样恶意软件也需通过调用API函数来完成相应的恶意行为。所以，利用API调用信息，可以间接地推断出应用程序的行为和意图，尤其是那些权限受到保护的API调用函数。敏感API只占API总数的一小部分，然而，通过它们，恶意软件可以访问敏感信息或执行敏感任务。为了识别恶意软件，本文重点关注受Android权限管理的部分敏感API。

2.2 函数调用流程

函数调用流程图表示了应用程序中函数的调用关系，函数之间的调用关系反映了应用程序的行为，本文使用它将给定的应用程序转换为图形表示，即函数调用流程图，其中包含必要的结构信息来描述应用程序的行为。

通过使用反编译工具对应用程序进行反编译得到应用程序的字节码文件，从中捕获应用程序中函数之间的调用关系。它可以表示为有向图G=(V，E)。V={vi|1≤i≤n}表示给定应用程序调用的函数集合，其中每个vi∈V对应一个函数名称。E⊆V×V表示函数调用集合，其中边(vi，vj)∈E表示从调用函数vi到被调用函数vj存在一个调用，vi是调用函数，vj是被调用函数。

2.3 非用户操作序列

Android应用程序经常在不经过用户同意的情况下，将用户的隐私数据传输到未知目的地。尤其是在云的出现后，许多良性的应用程序提供从云到终端用户的服务，这些应用程序通常需要收集用户的隐私数据发送到云以完成应用程序的某些功能。同时，恶意应用程序利用云作为中介进行用户的隐私数据的窃取。所以，敏感数据的传输本身不能表示真正的隐私泄露。本文将非用户意图的敏感数据传输视为隐私泄露，而用户意图的敏感数据传输视为正常行为，因此，使用非用户操作序列的方式进行恶意软件检测。

1)用户意图的数据传输。为了使用应用程序提供的一些功能，用户经常通过应用程序发送其移动终端的隐私信息。例如，当使用信息管理应用时，用户可以通过在触摸屏上点击几个按钮来将信息转发到第三方。当使用地图等基于位置的应用程序时，用户通常会发送其所在的位置得到用户想要获取的一些信息。由于应用程序获取用户隐私信息是在用户知情且与用户意图一致的情况下，所以本文不应将这种传输视为隐私泄漏。

2)非用户意图的数据传输。应用程序在未经用户的许可下对用户的隐私数据进行传输被定义为非用户意图的数据传输或隐私泄漏。在大多数情况下，用户不知道这种传输，因为恶意应用程序总是以隐身的方式这样做。

3)非用户操作序列。本文将应用程序的所有函数调用流程中不存在用户操作的序列定义为非用户操作序列。本文通过提取应用程序中的API调用信息构建应用程序的函数调用流程图，删除函数流程图中的用户操作调用序列，进一步提取出其中的非用户操作序列。

2.4 编辑距离

编辑距离(Edit Distance)，又称Levenshtein距离，是指两个字符串之间由一个转成另一个所需的最少编辑操作次数。编辑操作包括将一个字符替换成另一个字符、插入一个字符、删除一个字符。编辑距离越小，两个字符串的相似度越大。为了计算出两个非用户操作序列的相似度，本文通过计算两个非用户操作序列之间的编辑距离从而得到序列之间的差异度，进行相似度判断。本文通过替换、插入、删除操作求出两个序列的最小编辑距离。

3 本文恶意软件检测方法的实现

本文恶意软件检测方法如图1所示，主要由敏感API的选取、非用户操作序列的提取、非用户操作序列之间的相似性度量以及恶意软件的检测识别四部分组成。

该检测方法的主要工作步骤如下：

1)通过使用Androguard分析工具对应用程序进行反编译，提取出其中的API调用信息。对恶意样本中使用的API进行统计分析，提取出其中在恶意样本中使用频率较高的API作为敏感API。

2)对训练样本进行API调用信息提取，并以其所调用的API函数为核心构建样本的函数调用流程图，提取出函数调用图中的非用户操作序列作为恶意软件检测的恶意行为库。

3)通过对待检测样本进行反编译，提取出其中的敏感API，构建函数流程图，并提取出样本中的非用户操作序列。采用编辑距离算法计算待检测样本的非用户操作序列与恶意行为库的差异度。

4)将计算出来的差异度值与设定的阈值相比较来进行恶意软件检测。如果待检测样本与恶意行为库的差异度小于或等于该阈值，则判定该检测样本为恶意软件；否则为正常样本。

3.1 敏感API的选取

Android平台提供了一些API，应用软件可用这些函数与底层Android系统进行交互。这些API涉及收集用户的私人信息或系统信息，访问Web服务，发送和删除手机短信服务(Short Message Service， SMS)消息，录音，访问和阅读内容提供商等。例如：“getLine1Number()”函数用于获取用户手机号码，造成用户手机号码泄露；“getDeviceId()”函数用于获取设备Id，造成设备IMEI泄露。本文以统计方式通过对实验样本中用到的API进行分析以确定恶意软件经常使用的敏感API，如表1所示。

表1 敏感API

3.2 非用户操作序列的提取方法

由于良性软件和恶意软件都会对用户的敏感信息进行操作，因此敏感信息的传输本身可能不代表真正的隐私泄露，但通常用户不希望应用程序在不知情的情况下对隐私信息进行操作，所以敏感数据是否经用户操作来进行传输可用来作为识别恶意行为的一个指标。因此，本文中重点研究未经用户操作的敏感信息传输是否存在恶意行为，进而判断其是否为恶意软件。函数之间的调用关系反映了应用程序的行为，本文使用函数调用图来表示应用程序的函数调用关系，进而从中提取应用程序的非用户操作序列，进行恶意软件行为识别。

本文通过使用Androguard分析工具对Android安装包(Android Package， APK)进行反编译，提取出API调用信息。以其所调用的敏感API函数为核心构建应用程序的函数调用流程图。对于调用了敏感API的函数，采用向后遍历调用图以查找可能触发它的所有事件。在所有触发事件中通过KMP(Knuth-Morris-Pratt)算法搜索是否存在用户操作。在本文中将所有触发事件的操作序列作为主串，用户操作作为模式串进行用户操作序列匹配，从而查找是否存在非用户操作序列，流程如图2所示。

3.2.1 函数调用图的构建

本文通过广度优先遍历构建每个敏感API函数的函数调用流程图，并将所有流程图合并为应用程序的完整函数流程图，构建函数调用流程图的具体步骤如下：

1)对于应用程序调用的每个敏感API函数，采用广度优先遍历的方式，获得该敏感API函数所调用的函数集合以及被调用的函数集合，形成该敏感API函数的函数调用关系图。

2)对图中每个函数分别提取其所调用的函数的集合以及被调用的函数集合插入图中，重复遍历直至应用程序中的所有函数均已被遍历或程序流程结束。

3)将应用程序的每个敏感API函数调用关系图进行合并，去除重复操作成为该应用程序的完整函数调用关系图。

图2 非用户操作序列提取流程

在上述过程中生成的函数调用流程图，每个节点代表一个函数，每条边代表函数之间的先后调用关系。本文采用给节点编号的方式来表示一个应用程序的函数调用流程图，以方便后续生成的非用户操作序列之间进行比较，从而得出非用户操作序列之间的差异度。如恶意样本在获取设备ID和发送信息中所调用的敏感API函数getDeviceId()和sendTextMessage()生成的函数流程如图3所示，其在生成恶意样本的整体函数调用流程图的过程中删除重复节点，最终形成如图4所示的函数调用流程。

图3 恶意样本中敏感API函数调用流程

3.2.2 非用户操作序列的提取

本文通过采用向后遍历调用图以查找函数调用流程图中可能触发敏感API函数的所有事件。在所有触发事件中通过KMP算法搜索是否存在用户操作，进而形成非用户操作序列。提取非用户操作序列的具体步骤如下：

1)将上述形成的应用程序函数调用流程图采用从尾节点向后遍历的方式查找可能触发路径中的敏感API函数的函数节点。

2)在所有触发事件中通过KMP算法搜索是否存在用户操作。若存在用户操作，则在函数调用流程图中删除该路径，若与其他路径存在共同部分，则删除其余部分路径以保证其他路径的完整性。

3)重复遍历上述操作直至所有路径均以被遍历。函数调用流程图中的所有路径形成操作序列，最终形成应用程序的非用户操作序列集合。

在上述过程中，每个非用户操作序列代表该序列中敏感API函数的函数调用流程，通过将该敏感API函数的函数调用序列与恶意行为库中相同敏感API函数下的函数调用序列进行对比，从而判断该应用程序是否存在恶意行为。

3.3 非用户操作序列的相似性度量方式

本文以敏感API函数调用的非用户操作序列为特征，计算应用程序与恶意软件的相似性，也就是计算相同敏感API函数调用的非用户操作序列的相似性。本文采用编辑距离来计算操作序列的相似性。

设str1，str2为需要比较的两个非用户操作序列，为了计算两个非用户操作序列之间编辑距离，本文通过替换、插入、删除操作求出两个序列的最小编辑距离，因此，两个非用户操作序列的编辑距离为：

其中：d[i-1,j]+1代表str2插入一个操作所需代价，d[i,j-1]+1代表字符串str1删除一个操作所需代价。当xi=yj时，表示两个操作相同，所以与d[i-1,j-1]代价相同；否则代价加1，d[i,j]为以上三者中代价最小的一项。在本文的实验中，本文将两个非用户操作序列的长度分别定义为n，m，则两个非用户操作序列的差异度定义为两个序列的编辑距离之和与两个序列长度的比值，即：

在上述计算两个非用户操作序列相似性的过程中，两个序列的编辑距离越小，差异度就越小，相似性越大；反之，编辑距离越大，差异度就越大，相似性越小。

3.4 恶意软件的识别

通过上述的相似性度量方法，计算待检测样本中每个敏感API函数的非用户操作序列与恶意行为库中相同敏感API函数的非用户操作序列之间的差异度值，将该差异度值与设定的阈值进行比较，当待检测样本与恶意行为库的差异度值小于或等于该阈值，则判定该样本为恶意软件；否则为正常样本。

4 实验与分析

4.1 实验样本

为了对本文的方法进行验证，从VirusShare和Google官网获得1 500个样本，其中有1 200个恶意样本和300个正常样本。首先把收集的1 200个恶意软件分为两部分，其中70%用于训练作为样本数据集；另外的30%作为检测数据集。通过杀毒软件对从Google收集的300个应用程序进行检测确保实验的准确性。

4.2 度量指标

1)召回率(recall rate)。恶意软件被正确地检测为恶意软件的数量在所有恶意软件中的比例：

recall_rate=TP/(TP+FN)

2)漏报率(false negative rate)。恶意软件被错误地检测为良性软件的数量在所有恶意软件中的比例。

false_negative_rate=FN/(TP+FN)

3)准确率(precision rate)。良性软件被正确地检测为良性软件的数量在所有良性软件中的比例：

precision_rate=TN/(TN+FP)

4)误报率(false positive rate)。良性软件被错误地检测为恶意软件的数量在所有良性软件中的比例：

false_positive_rate=FP/(TN+FP)

数值模型中，仅在A2和A3两个控制孔内设置恒定控制水压，以此改变煤体中孔隙压力分布，形成非对称的孔隙压力场，如图6所示。模型边界荷载为定值，分别为8、12 MPa；控制水压为一变量，分别为0～10 MPa，每个模型控制水压相差2 MPa，煤、岩体各项参数见表1。模拟结果及分析如下。

5)正确率(accuracy)。被正确检测的软件的数量在所有软件中比例：

accuracy=(TP+TN)/(TP+TN+FP+FN)

4.3 实验结果

为了验证本文提出的方法的有效性，本文应用收集的360个恶意样本和300的正常样本进行检测，并与著名的Android恶意应用检测工具Androguard和FlowDroid[7]进行对比。Androguard恶意应用检测工具是一个Android恶意软件静态检测工具，该检测方法可以查看应用程序使用权限，获取应用程序中的所有方法，获取调用某个特殊API的方法信息以及获取应用程序的整体函数调用流程，通过静态分析应用程序代码检测恶意应用程序。

本文通过对恶意样本进行逆向分析，提取出恶意样本中的权限和API调用信息。以其所调用的API函数为核心构建恶意样本的函数调用流程图，进而获取恶意样本的非用户操作序列形成恶意行为库。对上述待检测样本采用相同方法获得每个API调用函数的非用户操作序列并采用编辑距离算法计算待检测样本与恶意行为库中的编辑距离，将计算出来的差异度值与设定的阈值作比较，进而判断该检测样本是否为恶意软件。本文选择不同的阈值进行恶意软件判断，并对相应的检测效果进行比较，结果如图5～6所示。

图5 不同阈值下的检测成功率

综合图5～6可以看出，在阈值为0.07时，检测总体正确率达到90.3%，此时本文提出的方法具有较好的检测效果。对于应用程序的误报和漏报情况，主要是由于一些应用仍然存在非用户操作的隐私泄露，其中大多数应用程序是社交网络服务(Social Networking Services， SNS)应用程序或具有嵌入式广告模块的应用程序。另一方面，恶意数据泄漏可能会隐藏在一些正常数据传输之中，以绕过最先进的安全验证。

图6 不同阈值下的漏报率和误报率

将上述实验中阈值为0.07的检测结果与Androguard和FlowDroid进行比较，对样本的检测结果如表2所示。

由表2可以看出，本文所述的恶意软件检测方法与Androguard检测方法相比在正常样本检测方面存在一些不足，但在恶意样本检测中相比Androguard检测方法能够检测出更多的恶意软件，检测效果更优，比Androguard检测方法在召回率上提升了30%。与FlowDroid检测方法相比本文所述的检测方法在正常样本和恶意样本检测中召回率和准确率均有提升，在正常样本检测中准确率提升了10%，在恶意样本检测中召回率提升了4%。

表2 3种方法的对比结果

5 结语

本文通过提取API调用信息构建应用程序的函数调用流程图，进一步提取出其中的非用户操作序列，并通过判断各非用户操作序列的相似性来进行恶意软件检测。实验结果表明，本文所提出的方法在阈值为0.07的条件下达到了90.8%的召回率和90.3%的正确率，具有较好的检测结果。本文的检测方法有够有效地识别出恶意软件，但在SNS应用程序和具有嵌入式广告模块的应用程序的检测中存在一定的误报。

References)

[1] 彭国军,李晶雯,孙润康,等.Android恶意软件检测研究与进展[J].武汉大学学报(理学版),2015,61(1):21-33.(PENG G J, LI J W, SUN R K, et al. Android malware detection research and development [J]. Journal of Wuhan University (Natural Science Edition), 2015, 61(1): 21-33.)

[2] 卿斯汉.Android安全研究进展[J].软件学报,2016,27(1):45-71(QING S H. Research progress on Android security [J]. Journal of Software, 2016, 27(1): 45-71)

[3] McAfee Labs. McAfee labs threats report [EB/OL]. [2017- 06- 01]. https://www.mcafee.com/us/resources/reports/rp-quarterly-threats-jun- 2017.pdf.

[4] FEIZOLLAH A, ANUAR N B, SALLEH R, et al. A review on feature selection in mobile malware detection [J]. Digital Investigation, 2015, 13: 22-37.

[5] JUNAID M, LIU D, KUNG D. Dexteroid: detecting malicious behaviors in Android apps using reverse-engineered life cycle models [J]. Computers & Security, 2016, 59: 92-117.

[6] WU S Y, WANG P, LI X, et al. Effective detection of android malware based on the usage of data flow APIs and machine learning [J]. Information and Software Technology, 2016, 75(C): 17-25.

[7] ARZT S, RASTHOFER S, FRITZ C, et al. FlowDroid: precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android apps [C]// PLDI 2014: Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2014: 259-269.

[8] DU Y, WANG X Q, WANG J F. A static Android malicious code detection method based on multi-source fusion [J]. Security & Communication Networks, 2015, 8(17): 3238-3246.

[9] GUAN Q, HUANG H, LUO W, et al. Semantics-based repackaging detection for mobile apps [C]// ESSoS 2016: Proceedings of the 2016 International Symposium on Engineering Secure Software and Systems. Berlin: Springer, 2016: 89-105

[10] FEIZOLLAH A, ANUAR N B, SALLEH R, et al. AndroDialysis: analysis of Android intent effectiveness in malware detection [J]. Computers & Security, 2016, 65: 121-134.

[11] WANG Z, LI C, YUAN Z, et al. DroidChain: a novel Android malware detection method based on behavior chains [J]. Pervasive & Mobile Computing, 2016, 32:3-14.

[12] XIAO X, XIAO X, JIANG Y, et al. Identifying Android malware with system call co-occurrence matrices [J]. Transactions on Emerging Telecommunications Technologies, 2016, 27(5): 675-684.

[13] ENCK W, GILBERT P, CHUN B G, et al. TaintDroid: an information flow tracking system for real-time privacy monitoring on smartphones [J]. Communications of the ACM, 2014, 57(3): 99-106.

[14] 孙润康,彭国军,李晶雯,等.基于行为的Android恶意软件判定方法及其有效性[J].计算机应用,2016,36(4):973-978.(SUN R K, PENG G J, LI J W, et al. Behavior oriented method of Android malware detection and its effectiveness [J]. Journal of Computer Applications, 2016, 36(4): 973-978.)

[15] FENG P, SUN C, MA J. Selecting critical data flows in android applications for abnormal behavior detection [J]. Mobile Information Systems, 2017, 2017: Article ID 7397812.

This work is partially supported by the National Natural Science Foundation of China (61303263).

LUOWenshuang, born in 1993, M. S. candidate. Her research interests include network security, mobile terminal security.

CAOTianjie, born in 1967, Ph. D., professor. His research interests include cryptology, information security.