这篇文章用马尔可夫链建模API序列，依据恶意和正常的APP虽然可能调用相同的API序列，但是调用顺序不同。文章用的是纯静态分析的方法.
《MAMADROID: Detecting Android Malware by Building Markov Chains of Behavioral Models》NDSS
方法：四步走
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：
得到一个vocab_size×vocab_sizevocab\_size \times vocab\_sizevocab_size×vocab_size大小的转移矩阵，这个APP的特征向量就是这个转移矩阵。可以用PCA来降维，可以更好。
之后的分类器都基于马尔可夫链提取出来的特征向量。
四、分类
用四个分类算法：Random Forests、1-Nearest Neighbor(1-NN)、3-Nearest Neighbor(3-NN)、SVM。算法的输入就是第三步中得到的特征向量。
实验效果
实验效果很好，毕竟是用一个APP的所有序列的信息来分类这个APP，信息相当大，任务相较于我们的工作简单了很多。
但是模型aging问题严重，用老样本训练，新样本准确率会下降（新样本训练，老样本准确率却很好，不放图了）
这篇文章呼吁和引导的接下来的方向也是解决模型的老化问题。
