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

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

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

图  1  检测模型

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

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

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

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

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

${\diamondsuit _{\rm{u}}}, {\diamondsuit _{\rm{b}}} $分别表示典型的一元与二元运算，如与、或、非、取余等。另外需要说明的是本文将Dalvik指令集中的array-length指令划分为一元运算，以符号$\ell $标识，以求简洁地表述程序行为。

SDIL的语义表达式由3种参数组成：m.pc表示当前执行指令，A代表当前分析的DEX文件，C表示执行当前指令前的堆栈初始状态，$ C = \langle S, H, \langle m, {\rm{pc}}, R\rangle ::SF\rangle $。

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

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

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

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

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

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

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

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

输入：函数调用关系图G_d=(V, E)，包含敏感调用的函数节点v

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

new stack s=null

push v

findPath (s, v)

  for each u=v.prev & & u→v unmarked do

    if s.serch (u)!=null

      mark circle

      continue

    else

      push u

      findPath (s, u)

    end if

  end for

  if!mark circle

    save path

  end if

pop

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

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

图  2  函数调用关系图示例

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

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

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

1) 若S₁给某变量赋值，而S₂使用了此变量，则称这两条语句之间存在流依赖关系，记为${S_1}{\delta ^{\rm{f}}}{S_2} $；

2) 若S₂给某变量赋值，而S₁使用了此变量，则称这两条语句之间存在反依赖关系，记为${S_1}{\delta ^{\rm{a}}}{S_2} $；

3) 若S₁与S₂都给某个变量赋值，则称这两条语句之间存在输出依赖关系，记为$ {S_1}{\delta ^{\rm{o}}}{S_2}$；

4) 若S₂是否会执行取决于S₁，则称这两条语句之间存在控制依赖关系，记为$ {S_1}{\delta ^{\rm{c}}}{S_2}$。

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

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

BLOCK 1

 new v2 < -ArrayList

 p1 < -paramString

 v6 < -′imei′, v7 < -m3

 v2.@add (v5 < -@BasicNameValuePair (v6, v7))

 v6 < -″pm″, v7 < -″1″

 v2.@add (v5 < -@BasicNameValuePair (v6, v7))

BLOCK 2

 :gogo_1

 v5 < -m6

 if v5==0 :cond_1

BLOCK 3

 v5 < -@equal (v5, v6 < -″″)

 if v5 < =0 goto cond_1

BLOCK 4

    v6 < -′ostype′, v7 < -m6

    v2 < -@add (v5 < -@BasicNameValuePair (v6, v7))

BLOCK 5

 :cond_1

  v5 < -@RU.U11.U5()

  m6 < -v5

BLOCK 6

 v5 < -″newhi″

 v5 < -@endsWith (p1, v5)

 if v5!=0

BLOCK 7

 v6 < -″php″

 p1.@append (v6)

BLOCK 8

 v5 < -p1.length

 v6 < -0x14

 if v5 > v6 :cond 2

BLOCK 9

    v3 < -@HttpPost (p1)

    v6 < -″UTF-8″

    v3.@setEntity (v5 < -@UrlEncodedForm Entity (v2), v6)

    v5 < -v5.@execute (v3).@getSatusLine (). @getStatusCode ()

    if v5!=0xc8 gote :cond_3

BLOCK 10

      v6 < -′pm′, v7 < -′1′

      v2.@add (v5 < -@BasicNameValue Pair (v6, v7))

BLOCK 11

     :cond_3

      v6 < -′pm′, v7 < -′-1′

      v2.@add (v5 < -@BasicNameValue Pair (v6, v7))

      goto :goto_1

BLOCK 12

  :cond2

   v3 < -@RU.U11.U3()

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

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

式中，${p_1}, {p_2}, \cdots, {p_n} $为函数的传入参数；${\text{out}}[{B_n}] = \emptyset $。

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

3) 确定初始基本块${B_\mathbb{C}} $与数据条件约束$\mathbb{C} $，其中${B_\mathbb{C}} $为已知的包含敏感调用的基本块，$\mathbb{C} $为${B_\mathbb{C}} $中敏感调用的参数，以及${B_\mathbb{C}} $中与此参数存在数据依赖关系的变量集合。

4) 从基本块${B_\mathbb{C}} $出发，在控制流图中倒序遍历搜索，计算其所有父节点B_Δ与${B_\mathbb{C}} $的数据依赖关系：若基本块B_Δ既不与$\mathbb{C} $存在流依赖关系，也不与${B_\mathbb{C}} $存在控制依赖关系，则表明B_Δ与${B_\mathbb{C}} $无关，可以从控制流图G_c中去除此基本块。

5) 若基本块B_Δ与${B_\mathbb{C}} $的数据约束$\mathbb{C} $存在流依赖关系，需要对其中所有与流依赖相关的语句c_i=exp分析，若exp为定值，则${\mathbb{C}_{{\text{new}}}} = \mathbb{C}-{c_i} $；若exp为使用了变量集合$V = \{ {v_i}\} (i \in {\mathbb{Z}^ + }) $的表达式，则${\mathbb{C}_{{\text{new}}}} = \mathbb{C} \cup V $。

6) 若B_Δ≠B_start，则令${B_\mathbb{C}} = {B_\Delta } $，重复步骤4) 和5)，迭代计算。

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

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

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

通过路径优化可以极大地降低后续符号执行过程中的计算量，在得到优化后的控制流图${G_c}^\prime = (V', E', {\text{start}}, {\text{end}}) $后，就可以对其进行展开和符号计算。

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

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

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

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

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

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

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

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

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

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

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

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