基于语义的Android敏感行为静态分析方法

董 航，刘 洋，李承泽，付 戈，张 淼，杨义先



基于语义的Android敏感行为静态分析方法

董 航1，刘 洋2，李承泽1，付 戈2，张 淼1，杨义先1

(1. 北京邮电大学信息安全中心 北京海淀区 100876；2. 国家计算机网络应急技术处理协调中心 北京朝阳区 100029)

提出一种基于语义的Android敏感行为静态分析方法。该方法首先基于样本统计结果，利用精简Dalvik指令集作为本文分析的中间语言，实现对指令层的形式化语义描述；之后，基于中间语言发现检测样本中的敏感调用，并通过控制依赖关系追溯调用路径；最后，在控制流分析基础上, 对存在敏感调用的路径约束求解路径条件。最终求解出具体后台行为及触发条件，揭示出样本后台行为的执行全过程。该方法缓解了符号执行中的路径爆炸问题，实验验证了该方法可以有效地对移动应用后台行为进行分析，并及时获取特征检测无法发现的未知移动恶意应用程序。

Android; 行为分析; 约束求解; 形式化描述

近年来，在诸多移动平台中，针对Android平台的恶意程序比例迅速攀升，数量呈爆发式增长[1]。新增的移动恶意程序中，Android平台占据了绝大多数，增长率超过了33%，远远大于传统的桌面平台，从而导致移动应用安全形势异常严峻。

基于终端的恶意程序的发展过程有着清晰的脉络。在Symbian系统上，文献[2]在2004年最早揭示了手机病毒，引起了人们对移动平台软件安全分析的逐步重视。2007~2009年间，文献[3-4]相继研究了智能手机的病毒特征，对智能手机系统结构和安全机制进行了分析，并提出了一种病毒检测及预警系统。随后文献[5]在Android应用分析中引入了自组织网络中的分布式计算机制，提高了分析效率。与此同时，Android平台著名应用分析工具Androguard利用归一化压缩距离(normalized compression distance, NCD)进行Android的应用程序相似性分析[6]，以压缩特征判断恶意软件。进一步，文献[7]以此为基础，从Davlik指令层面提取恶意软件特征。但这些方法大部分都是针对应用自身特征，难以识别含有未知特征的样本，从而引起漏报。

基于语义的检测方法的提出为更好地检测未知恶意软件提供了支撑，桌面平台下已有部分研究人员开展了相关研究，并取得了较好的效果[7]，但是移动平台下的研究才刚刚开始。在与移动平台语义检测相关的工作中，文献[8]最早通过对指令和成员的符号描述，将符号计算应用于Java card虚拟机中；文献[9]借助于Java分析工具Java pathfinder，将符号执行机制引入Android源代码分析中，自动化地分析Android源码中的缺陷，但是，其分析目标是程序源码，并不能对Android应用程序中Dalvik字节码进行检测。文献[10]在分析应用程序缺陷时对Android Dalvik指令进行了符号描述，但该分析方法主要面向缺陷分析，在分析应用的恶意行为时效率不高。

为了解决Android平台恶意代码分析问题，识别应用程序敏感行为，发现未知的恶意应用，本文在总结几种现有的智能终端应用程序分析方法和工具的基础上，提出了一种基于语义的Android应用行为检测方法，通过分析测试样本中的后台行为及其触发条件，从而更准确地识别未知的恶意程序。

1 检测模型概述

本文将移动应用程序的敏感和恶意行为看作一系列操作序列，这些序列最终均会触发关键的系统调用。本文提出的方法中，需要将重要系统调用做“敏感”标记，并以此建立规则模版。在规则模板中，认为正常行为与敏感行为的区别在于触发这些操作的源头：若一条包含敏感调用的操作序列的源来自于用户交互，则认为此行为源自用户操作，在完成此敏感操作时用户是知情的；反之，则认为此序列为应用后台发起的敏感调用。

同时，为了计算和验证这些存在敏感调用的路径条件，本文在流追踪的基础上借鉴符号执行的思想，约束求解路径条件，优化分析路径，最终提出了基于语义的代码行为检测模型，用于解出样本的具体后台行为和触发条件。

本文提出的检测模型如图1所示，核心思想是通过函数调用关系图G=(,)提出包含敏感调用的函数节点N，之后以N为结束符号遍历G，获取G中包含N的所有可能路径，并判断这些路径的源函数节点是否包含用户交互行为；之后，使用数据流分析方法分析包含用户行为的敏感路径P的每个方法，去除无关节点，进一步优化分析路径；最后，对路径求解约束，由N中敏感调用的具体参数计算得出敏感路径P的触发条件。

如图1所示，分析引擎通过分析由抽象语法树提取的控制流、数据流，定位敏感行为发生的关键位置，结合通过对控制依赖关系的分析，去掉不必要的分支，优化分析对象，缓解路径爆炸问题并节省约束求解时间；接下来，根据到达定值定理先完成对规则指定的关键变量的分析，精简出必要的路径供符号计算模块进行进一步分析。符号计算模块通过语义表达式对由simple-dalvik intermediate language(SDIL)中间语言描述的程序行为抽象进行约束求解，去掉冗余路径，提升分析效率，最终计算出敏感行为的触发条件及其可达性。

图1 检测模型

2 精简Dalvik指令集

为了减轻符号计算中语义描述的工作量，提高分析效率，本文对3000个Android样本中的所有指令分布情况进行统计分析，结合指令的实际执行结果，在保留Dalvik指令集的基础上，总结出一个以Dalvik指令为基础，包含了13条指令的精简指令集作为本文分析的中间语言，称此指令集为SDIL，具体语法如下：

SDIL的语法中，用于表示应用程序中的目标文件，由类(cls)、域(fld)、方法(mtd)和字符串(str)组成。在原Dalvik指令集中，str是以id为索引的资源映射，其中包括方法名、类名等信息，而在SDIL中，为了分析的方便，将映射全部展开，在之后的符号计算中不需要寻找映射，而可以直接使用str。

应用程序的其他组成部分cls、fld与mtd均有各自的展开式，如cls由名称、父类、接口与主体组成，主体又是由fld与mtd组成，mtd由方法名及方法主体mbody构成。

语句stmt存在于方法的主体mbody中，包括了多种表达式，如指令move reg reg，表明当前SDIL指令为move，后面操作数限定为两个寄存器。这些指令的具体语义将在后文详细表述。

SDIL的语义表达式由3种参数组成：pc表示当前执行指令，代表当前分析的DEX文件，表示执行当前指令前的堆栈初始状态，。

语义表达式中的每一个状态语句的计算都符合以下形式化表达：

如SDIL中const指令的语义表达式为：

参考Dalvik指令官方文档并结合实际分析，结果表明，在执行指令const后，静态堆和动态堆不变，而调用堆中计数器加一，操作数的值将被赋给目的寄存器。类似地，本文对所有SDIL指令都进行了形式化的语义表达。

3 分析算法

3.1 路径提取

词法和语法解析器可以对中间语言遍历，生成对应的抽象语法树。通过遍历抽象语法树，可以很容易地获取程序的控制依赖关系和生成控制流图。

在获取SDIL指令集的抽象语法树之后，即可通过对其遍历分析和提取函数调用关系图，遍历过程使用深度优先算法，获取函数调用关系图G=(,)。函数调用关系图G是一个有向有环图，其边的方向表明函数调用关系。

路径提取的实质是对包含了敏感调用的函数节点V的函数调用关系图G遍历，本文采取的方法是对函数调用关系图G逆向搜索。考虑到图G是一个有向有环图，在遍历的过程中需要重点考虑环的处理，通过对节点是否会构成环进行判断，实现有环图的开环。

算法1说明了从遍历函数调用关系图G=(,)中寻找所有到节点V的可能路径并开环的过程。

算法1：遍历调用关系图寻找敏感调用路径

输入：函数调用关系图G=()，包含敏感调用的函数节点

输出：包含敏感调用的函数调用路径

new stack=null

push

findPath(,)

for each=prev &&→unmarked do

if.serch()!= null

mark circle

continue

else

push

findPath(,)

end if

end for

if !mark circle

save path

end if

pop

与通常意义上的静态缺陷分析要求遍历完整路径的思想不同，本文所提方法主要针对恶意应用中的特定行为分析，故可以通过去掉与敏感行为发生路径无关的节点，仅提取与分析目标相关的函数调用路径，在降低路径爆炸风险的同时，也为进一步分析节省了大量的计算工作。

以图2所示的函数调用关系图为例，其中函数包含了敏感调用HttpClient.execute()，经过算法1计算，可以提取出与敏感调用相关的路径，如表1所示。

图2 函数调用关系图示例

表1 与敏感调用相关的调用路径

通过路径提取可以对包含敏感调用的路径进行简单分析：若通过算法1提取出的路径的开始节点仅为用户交互函数，或仅为非用户交互函数，则可以初步判断路径是否为后台路径，然而图2的遍历结果中既包括了与用户交互相关的路径，也包含了无用户交互的路径。在这种情况下，需要在此基础上对路径中的数据流与控制流进行追踪，通过SDIL语义描述，使用符号计算的思想，约束求解路径条件。

3.2 路径优化

符号计算通常会占用大量的资源，然而本文引入符号计算的主要目的只是为了求解移动应用中特定敏感行为的触发条件，并不需要展开完整控制流。为了避免产生路径爆炸等问题，在进行符号计算之前，需要对函数内部的控制流图进行预处理，通过对函数内部细节的优化，减少不必要的计算分支。数据流分析是本文处理和优化函数内控制流的主要思想，利用到达定制定理，计算并剔除与敏感数据无关的分支，从而达到减少计算量的目的。本方法所涉及的一些定义如下。

定义 对顺序出现的两条语句1与2，定义以下4种数据依赖关系：

1) 若1给某变量赋值，而2使用了此变量，则称这两条语句之间存在流依赖关系，记为；

2) 若2给某变量赋值，而1使用了此变量，则称这两条语句之间存在反依赖关系，记为；

3) 若1与2都给某个变量赋值，则称这两条语句之间存在输出依赖关系，记为；

4) 若2是否会执行取决于1，则称这两条语句之间存在控制依赖关系，记为。

该定义也可扩展为控制流图中的基本块之间的关系。

本文分析的一段带有敏感调用的SDIL代码为：

BLOCK 1

new2<-ArrayList

1<-paramString

6<-′imei′,7<-3

2.@add(5<-@BasicNameValuePair(6,7))

6<-″pm″,7<-″1″

2.@add(5<-@BasicNameValuePair(6,7))

BLOCK 2

:gogo_1

5<-m6

if5==0 :cond_1

BLOCK 3

5<-@equal(5,6<-″″)

if5<=0 goto cond_1

BLOCK 4

6<-′ostype′,7<-6

2<-@add(5<-@BasicNameValuePair (6,7))

BLOCK 5

:cond_1

5<-@RU.U11.U5( )

6<-5

BLOCK 6

5<-″newhi″

5<-@endsWith(1,5)

if5!=0

BLOCK 7

6<-″php″

1.@append(6)

BLOCK 8

5<-1.length

6<-0x14

if5 >6 :cond 2

BLOCK 9

3<-@HttpPost(1)

6<-″UTF-8″

3.@setEntity(5<-@UrlEncodedForm Entity(2),6)

5<-5.@execute(3).@getSatusLine(). @getStatusCode()

if5 != 0xc8 gote :cond_3

BLOCK 10

6<-′pm′,7<-′1′

2.@add(5<-@BasicNameValue Pair(6,7))

BLOCK 11

:cond_3

6<-′pm′,7<-′-1′

2.@add(5<-@BasicNameValue Pair(6,7))

goto :goto_1

BLOCK 12

:cond2

3<-@RU.U11.U3()

本文所使用的流优化算法的核心思想是在到达定值定理的基础上，根据所需追踪的数据条件约束，判断控制流图G=(,,start,end)中与无关的分支，从而达到优化的目的，算法主要包括7个步骤：

1) 初始化到达定值分析中的in[B]，out[B]，gen[B]与kill[B]。其中对in[B]的初始化需要考虑函数两种情况，即：

2) 迭代计算得到所有的基本块的in[B]与out[B]。

7) 结束所有基本块的搜索，将剩余的基本块按照控制关系生成新的控制流图，可达路径保存至可达路径队列，以备符号计算。

图3展示的是优化前后的控制流图对比，其中编号为9的基本块中存在敏感API调用。

图3 SDIL指令及对应控制流图

3.3 符号计算

通过路径优化可以极大地降低后续符号执行过程中的计算量，在得到优化后的控制流图后，就可以对其进行展开和符号计算。

符号计算中的约束来源于精简指令集的语义规则。结果表明，当路径条件为时，关键参数3的值为HttpPost(1).@setEntity(@UrlEncoded FormEntity(2),UTF8')。从约束求解的结果可以看出，敏感调用的参数依赖于整个函数的入参1，单对此函数的计算并不能完整分析出敏感调用的具体参数。在这种情况下，需要持续迭代，将函数及参数1做为主调函数中的敏感调用，基于前文算法逐个进行优化和符号计算，最终求解出完整的路径条件与敏感参数表达式。

本文使用的计算方法为静态计算，也会遇到一般符号执行中所面临的外部环境交互问题。本文采用的是对系统调用函数构建环境建模库的方法，缓解对外部调用的依赖。

4 实 验

本文主要从语义提取后路径优化效率及分析结果两方面进行评估。为了评估本文所提算法的优化效率，从测试数据中随机选取5个样本，对其经过优化前后的指令条数进行了统计，统计结果如表2所示。

表2 路径优化比例

从分析结果可以看出，本文所提路径优化算法可以极大地降低实际分析的工作量，基于敏感路径分析的优化算法一般情况下可以去掉80%～90%的无关指令；通过数据流优化算法，可以在此基础上进一步优化20%左右的无关路径。最终输入到符号计算中的仅为不到10%的指令，极大地提升了分析效率。

图4 检测工具所检测的发送短信行为

基于前文的理论和算法，开发了一套用于分析手机恶意软件后台行为的分析工具，并用实际样本进行了测试，从测试的正常样本中发现了一些具有后台行为的应用程序。这些应用程序并未被杀毒软件划归为恶意应用范畴，但是其行为又可能对用户产生影响。分析中发现，很多软件会在后台将用户相关数据通过网络或短信发送，如图4所示。这些信息若被不法分子利用，将会严重危害用户的个人信息安全。

本文作者所在项目组已将通过本方法发现的10余类典型恶意样本提交至国家互联网应急响应中心处置。

5 结 束 语

本文的贡献主要包括以下3个部分：

1) 提出了一套以Dalvik指令集为基础的精简指令集。指令集针对移动恶意代码行为的特点，将原指令集进行语义归纳与优化，同时仍保持源程序的语义与控制关系；

2) 在精简指令集的基础上，提出了基于语义的行为分析方法，方法通过精简指令对样本代码进行符号化抽象，跟踪敏感调用追踪相关数据流和控制流变化，解决了一般的分析方法无法有效追踪移动应用行为的问题；

3) 完成了原型系统开发，实现了基于语义的移动恶意代码行为提取和检测等功能。测试结果表明，本文所提方法可以有效发现移动应用的后台行为，对未知恶意软件具有较好的识别能力。

本文提出的方法将Android指令集精简并提炼出了用于分析应用行为的中间语言，可以高效地对应用行为进行形式化描述。通过对控制流、数据流和控制依赖关系的深度分析，在并在计算的过程中不断优化分析路径，缓解了符号执行中的路径爆炸问题。最终通过路径追溯，可以发现应用在非用户确认的情况下执行的后台行为并计算其触发条件，揭示出样本后台行为的执行全过程。实验表明本方法可以发现特征检测无法发现的未知移动恶意应用程序，在一定程度上弥补了现有特征分析不能有效发现未知应用的问题。

[1] 工信部国家互联网应急中心. 2013年我国互联网网络安全态势综述[EB/OL]. [2014-03-20]. http://www.199it.com/ archives/206597.html.

CNCERT. Overview of 2013 China's Internet network security situation[EB/OL]. [2014-03-20]. http://www. 199it.com/archives/206597.html.

[2] DAGON D, MARTIN T, STARNER T. Mobile phones as computing devices: the viruses are coming![J]. Pervasive Computing, 2004, 3(4): 11-15.

[3] CHEUNG J, WONG S, YANG H, et al. Smartsiren: Virus detection and alert for smartphones[C]//Proc of the 5th Int Conf on Mobile Systems, Applications and Services. New York: ACM, 2007: 258-271.

[4] SHABTAI A, FLEDEL Y, KANONOV U, et al. Google Android: a state-of-the-art review of security mechanisms[EB/OL]. [2014-03-20]. http://www.docin. com/p-189587298.html.

[5] SCHMIDT A D, BYE R, SCHMIDT H G, et al. Static analysis of executables for collaborative malware detection on Android[C]//ICC'09 IEEE Int Conf on Communications. [S.l.]: IEEE, 2009: 1-5.

[6] DESNOS A. Android: Static analysis using similarity distance[C]//2012 45th Hawaii Int Conf on System Science (HICSS). Los Alamitos: IEEE Computer Society, 2012: 5394-5403.

[7] 李挺, 董航, 袁春阳, 等. 基于Dalvik指令的Android恶意代码特征描述及验证[J]. 计算机研究与发展, 2014, 51(7): 1458-1466.

LI Ting, DONG Hang, YUAN Chun-yang, et al. Description of android malware feature based on dalvik instructions[J]. Journal of Computer Research and Development, 2014, 51(7): 1458-1466.

[8] 王蕊, 冯登国, 杨轶, 等. 基于语义的恶意代码行为特征提取及检测方法[J]. 软件学报, 2012(2): 378-393.

WANG Rui, FENG Deng-guo, YANG-Yi, et al. Semantics- based malware behavior signature extraction and detection method[J]. Journal of Software, 2012(2): 378-393.

[9] SIVERONI I A. Operational semantics of the java card virtual machine[J]. The Journal of Logic and Algebraic Programming, 2004, 58(1): 3-25.

[10] MIRZAEI N, MALEK S, PASAREANU C S, et al. Testing Android apps through symbolic execution[J]. Sigsoft Softw Eng Notes, 2012, 37(6): 1-5.

[11] KARLSEN HS, WOGENSEN ER, OLESEN MC, et al. Study, formalisation, and analysis of Dalvik bytecode[C]// Proc of the Seventh Workshop on Bytecode Semantics, Verification, Analysis and Transformation (BYTECODE 2012). Tallinn: ETAPS, 2012.

编 辑 叶 芳

Semantic-Based Sensitive Behavior Analysis Method for Android

DONG Hang1, LIU Yang2, LI Cheng-ze1, FU Ge2, ZHANG Miao1, and YANG Yi-xian1

(1. Information Security Center, Beijing University of Posts and Telecommunications Haidian Beijing 100876; 2. National Computer Network Emergency Response Technical Team/Coordination Center of China Chaoyang Beijing 100029)

This paper proposes a semantic-based sensitive behavior analysis method for Android. With sample statistics results, the method firstly adopts a simple-Dalvik intermediate language (SDIL) as the intermediate language for text analysis, thus giving a symbolic semantics description for instructions. Then the method uses SDIL to detect sensitive calls from the samples and traces the call paths according to the control dependence. Then based on control-flow analysis, the method adopts constraint solving to obtain path conditions. At last, the method finds the background behaviors with trigger conditions, thus the whole process of background behavior execution will be showed as well. This method can release the path explosion problem in the process of symbolic execution. With experiment under our platform, it proves that the method can analyze the background behaviors of mobile application efficiently, and find the unknown mobile malicious applications which can not be found by traditional feature detection methods in time.

Android; behavior analysis; constraint solve; formal description

TP309.5

A

10.3969/j.issn.1001-0548.2017.02.019

2014-05-16；

2016-07-06

国家自然科学基金(61302087)；国家科技支撑计划(2012BAH06B02)；教育部博士点基金(20120005110017)

董航(1986-)，男，博士，主要从事软件安全和移动互联网安全方面的研究.