前言
这里所说的相似度分析是针对Android应用来说的，主要是指Dex文件的分析。
通过相似度分析，可以快速地识别一款应用是否来源于另一款应用，如版本更新、重打包之类的。这对于病毒分析、重打包分析等非常之有用。
目前市面上主流的相似度分析方案有3种：基于代码流、基于API序列、基于变量计数。本章将介绍基于代码流的方案。
基于代码流的方案是指针对同一个方法中的多条指令进行连续性识别，Androguard中的androsim.py工具就是基于这种原理。当然，有了前面的知识，我们也可以自己写一个类似的工具。
androsim.py的使用
androsim.py是Androguard中的一个工具，因此需要先安装Androguard。Androguard下载与安装请参见官方文档：http://code.google.com/p/androguard/
androsim.py使用非常简单，用法如下：
androsim.py -i <first.apk> <second.apk>
androsim.py的测试
下面是某款软件旧版与新版测试的结果：
Elements:
IDENTICAL: 1566
SIMILAR: 414
NEW: 73
DELETED: 24
SKIPPED: 0
–> methods: 92.527568% of similarities
下面是两款不同软件的测试结果：
Elements:
IDENTICAL: 158
SIMILAR: 1641
NEW: 1531
DELETED: 5938
SKIPPED: 0
–> methods: 31.538353% of similarities
基于代码流的流程设想
androsim.py的分析流程设想（具体实现比较复杂，有兴趣的可以去研究下）：
1) 先取第一个apk的一个方法的指令列表
2) 然后与第二个apk的所有方法的指令列表依次进行指令比较（像KMP这类字符串算法），并分别计算得到相似度。
3) 如果找到完全一样的，就停止并记录下来
4) 否则把所有方法都比较一次，然后去掉不相似的，留下相似的结果以便后缀使用。
5) 转到第1步，直到所有方法比较完毕
6) 先过滤出完全一样的，然后按得分依次找到最相似的，剩下的当新增或删除处理。
7) 最后计算出总的相似度。
其中，第2步中的计算相似度，是通过计算两个指令列表中连续相同指令的个数占全部指令中的比例。
基于代码流的模拟实现
这个功能实现使用ASM或ASMDEX都差不多，不过使用ASM需要先用dex2jar转换一下。这边为了方便，直接使用ASMDEX。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
| public class Main implements Opcodes {
public static void main(String[] args) throws IOException {
// 针对的是两个不同dex之前的相似度
ApplicationNode firstNode = new ApplicationNode(ASM4);
ApplicationNode secondNode = new ApplicationNode(ASM4);
ApplicationReader ar = new ApplicationReader(ASM4, new FileInputStream("classes1.dex"));
ar.accept(firstNode, 0);
ar = new ApplicationReader(ASM4, new FileInputStream("classes2.dex"));
ar.accept(secondNode, 0);
// 定义相应的结果变量
int identicalCount = 0;
int similarityCount = 0;
int newCount = 0;
int delCount = 0;
int skipFirstCount = 0;
int skipSecondCount = 0;
double similarityScore = 0;
int firstMethodCount = 0;
int secondMethodCount = 0;
float allScore = 0;
for(ClassNode firstClassNode : firstNode.classes) {
if(firstClassNode.methods != null) {
for(MethodNode firstMethodNode : firstClassNode.methods) {
++firstMethodCount;
// 抽象方法及本地方法当作skip处理
if(firstMethodNode.instructions.size() == 0) {
++skipFirstCount;
continue;
}
float maxScore = 0;
boolean foundIdentacal = false;
for(ClassNode secondClassNode : secondNode.classes) {
// 找到完全一样的，就没必要再找了
if(foundIdentacal) {
break;
}
if(secondClassNode.methods != null) {
for(MethodNode secondMethodNode : secondClassNode.methods) {
if(secondMethodNode.instructions.size() == 0) {
continue;
}
float score = getScore(firstMethodNode.instructions, secondMethodNode.instructions);
if(score > 0.999f) {
foundIdentacal = true;
++identicalCount;
break;
} else if(score > maxScore) {
maxScore = score;
}
}
}
}
// 这里设置20%以上才算相似，否则认为此方法已经删除。
if(!foundIdentacal){
if(maxScore < 0.2) {
++delCount;
} else {
++similarityCount;
allScore += maxScore;
}
}
}
}
}
for(ClassNode secondClassNode : secondNode.classes) {
if(secondClassNode.methods != null) {
for(MethodNode secondMethodNode : secondClassNode.methods) {
++secondMethodCount;
if(secondMethodNode.instructions.size() == 0) {
++skipSecondCount;
continue;
}
}
}
}
// 多出来的算新增
newCount = Math.abs(firstMethodCount - secondMethodCount);
// 相似度结果： (完全相同数量+相似度总得分+跳过的最少值)/最大的方法数
similarityScore = (identicalCount + allScore + Math.min(skipFirstCount, skipSecondCount)) / (double)Math.max(firstMethodCount, secondMethodCount) * 100;
// 输出结果
System.out.println("Elements:");
System.out.println("\tIDENTICAL:\t" + identicalCount);
System.out.println("\tSIMILAR:\t" + similarityCount);
System.out.println("\tNEW:\t\t" + newCount);
System.out.println("\tDELETED:\t" + delCount);
System.out.println("\tSKIPPED:\t" + Math.min(skipFirstCount, skipSecondCount));
System.out.println("\t--> methods: " + similarityScore + "% of similarities");
}
private static float getScore(InsnList firstInsnList, InsnList secondInsnList) {
// 保证firstInsnList的指令数最多
if(firstInsnList.size() < secondInsnList.size()) {
InsnList tmpList = firstInsnList;
firstInsnList = secondInsnList;
secondInsnList = tmpList;
}
int firstSize = firstInsnList.size();
int secondSize = secondInsnList.size();
// 为了简单起见，这里直接使用暴力，算法好的童鞋可以试着优化成KMP或更优的方案
int maxMatchCount = 0;
end:for(int i=0;i<firstSize;++i) {
for(int j=0;j<secondSize;++j) {
int count = 0;
for(int k=0;i+k<firstSize && j+k<secondSize;++k) {
// 匹配到相同时，继续往后匹配，直到匹配不上
// 这里匹配的依据为操作码一致
if(firstInsnList.get(i+k).getOpcode() == secondInsnList.get(j+k).getOpcode()) {
++count;
} else {
break;
}
}
if(count > maxMatchCount) {
maxMatchCount = count;
}
// 匹配的最大数量已经超过当前剩余的指令，则没必要找下去了
if(maxMatchCount > secondSize - j) {
break end;
}
}
}
// 相似度算法: 最大匹配数/平均指令长度
return maxMatchCount / ((firstSize + secondSize) / 2.0f);
}
}
|
在上面的代码，我直接使用最高相似度的得分，并没有处理方法比较重合的问题，另外也可以做很多改进，如已找到完全相同的方法避免重复处理、计算得分时的算法优化等等，大家有兴趣的话可以试着把它做得更完善。
下面给大家看下我的一个运行结果：
Elements:
IDENTICAL: 695
SIMILAR: 5711
NEW: 1
DELETED: 1649
SKIPPED: 282
–> methods: 47.81350373478352% of similarities
问题与建议
androsim.py在使用时非常耗内存，特别是方法数较多且相似度不高的情况下，会出现内存不足的情况（我的机器配置是8G内存，基本1.5W个方法就不行了）。
因此如果需要兼容大型应用的相似度比较的话，建议大家按照上面的大体思路自己做一个相应的实现，并且针对性地做内存方面的优化。