这篇文章用马尔可夫链建模API序列，依据恶意和正常的APP虽然可能调用相同的API序列，但是调用顺序不同。文章用的是纯静态分析的方法.

《MAMADROID: Detecting Android Malware by Building Markov Chains of Behavioral Models》NDSS 2017

方法：四步走

overview

文章其实用的并不是API，而是用的API所属的family或者package，如上图，一个API，属于一个类；类属于package；package属于family。作者也是有苦衷的，静态分析得到的API太多了，下面详细说。

第一步拿到apk用soot等工具反编译出Call Graph；第二步从Call Graph中遍历出API序列，同时抽象成package/family序列；第三步马尔可夫链建模；第四步二分类。

一、提取Call Graph

拿到这个APP的apk，然后用静态分析工具Soot和FlowDroid提取出API Call Graph。例如图2是一个恶意软件的代码段：

可以提取出的API Call Graph：

二、提取序列

首先识别出图上所有的起始节点，然后遍历整个图找到所有的执行路径，从而得到了这个APP的API序列。

理想很丰满，但是由于文章是从静态分析提取出的API序列，44k个app，一共提取出了超过1000万API，这意味着词典大小是1000万，转移矩阵有1000万个节点。因此没办法只能将API归类，把API抽象到对应的package或者family。

package一共有340种，包括：Android 243、Google API 95、 自定义 1(很可能包含恶意动作)、 模糊 1。

family一共有11种，包括自定义和模糊。

这样就把API抽象归类，词典大小就降下来了，提取出序列如图4：

三、马尔可夫链建模

这就是一个一阶马尔可夫链，如Fig 5，对应上面的Fig 4和Fig 3：

得到一个 v o c a b _ s i z e × v o c a b _ s i z e vocab\_size \times vocab\_size vocab_size×vocab_size大小的转移矩阵，这个APP的特征向量就是这个转移矩阵。可以用PCA来降维，可以更好。

之后的分类器都基于马尔可夫链提取出来的特征向量。

四、分类

用四个分类算法：Random Forests、1-Nearest Neighbor(1-NN)、3-Nearest Neighbor(3-NN)、SVM。算法的输入就是第三步中得到的特征向量。

实验效果

实验效果很好，毕竟是用一个APP的所有序列的信息来分类这个APP，信息相当大，任务相较于我们的工作简单了很多。

但是模型aging问题严重，用老样本训练，新样本准确率会下降（新样本训练，老样本准确率却很好，不放图了）

这篇文章呼吁和引导的接下来的方向也是解决模型的老化问题。