前言
在上一章中我给大家介绍了基于代码流的方案，这一章里，我将会介绍基于API序列与基于变量计数的方案。
由于这两种方案目前在网上还未能找到针对Dex的开源实现，所以这里我会简单介绍下其原理实现。
基于API序列的原理
API（Application Programming Interface）一般指的是系统或他人提供的编程接口。
这里我把API定义为所有被调用的方法，在我们编写代码的过程中，一般情况下都会调用各种API，这些API可以分为三类：
1) 系统API
2) 别人提供的SDK或开源库中的API
3) 自己编写的API。
其中无论是别人提供的SDK还是开源库，都会被一起打包进我们的应用中，因此这类API可与自己编写的API统一称为用户API（泛指dex文件中的所有方法）。
也就是说，这里我把API划分为系统API及用户API两类。
由于系统API是固定的，所以系统API可以通过类名+方法名+方法签名来限定，但用户API的类名和方法都能混淆，因而用户API无法准确识别。
因此，为了提高相似度的准确性，应该设置一个分值，使得系统API的得分远远高于用户API的得分。
API序列就是在同一个方法中，不同API调用的序列。一个方法中可能有0个到多个API的调用，同时同一个API可能被调用多次，因而我们需要记录每个API在同一个方法中调用的次数。
根据上面的结论，我们这里设置一个API的调用（记为API记录）为调用序列中的一个元素，则API记录应包含3个元素：关键字（用于识别系统API）、分值、调用次数。
那么我们就可以通过两个方法的API序列来比较两个方法的相似度。同理，我们可以通过两个类的API序列来比较两个类的相似度。
由于很多方法的API调用都比较少甚至于没有，因此基于方法的维度来比较相似度相对来说比较不准确，本文使用基于类的维度。
基于API序列的流程
基于API序列的流程分为几步：
1) 把第一个应用中每一个类的API调用转换为一个无序的API调用序列
2) 把第二个应用中每一个类的API调用转换为一个无序的API调用序列
3) 从两个应用中各取出一个API调用序列进行两两比较，并计算出相似度。
4) 如果找到完全一样的，就停止并记录下来。
5) 否则与第二个应用的所有序列都比较一次，然后去掉不相似的，留下相似的结果以便后缀使用。
6) 转到第1步，直到所有序列比较完毕。
7) 先过滤出完全一样的，然后按得分依次找到最相似的，剩下的当新增或删除处理。
8) 最后计算出总的相似度。
其中，第3步中的计算相似度，是通过计算两个序列相同的个数占平均个数的比例。
基于API序列的模拟实现
这里同样使用ASMDEX来实现（使用ASM基本类似，有兴趣的自己试试），限于篇幅，这里同样没处理重复比较的问题，算法使用暴力。
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
| public class ApiMain implements Opcodes {
static class ApiRecord {
// 用来识别是否系统API
public String key;
// 用于提高相似度的准确率
public int score;
// 调用次数
public int invokeTimes = 0;
public ApiRecord(String key, int score) {
this.key = key;
this.score = score;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
ApiRecord other = (ApiRecord) obj;
if (invokeTimes != other.invokeTimes)
return false;
if (key == null) {
if (other.key != null)
return false;
} else if (!key.equals(other.key))
return false;
return true;
}
}
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;
float allScore = 0;
List<List<ApiRecord>> firstRecordList = new ArrayList<List<ApiRecord>>();
List<List<ApiRecord>> secondRecordList = new ArrayList<List<ApiRecord>>();
skipFirstCount = parse(firstNode, firstRecordList);
skipSecondCount = parse(secondNode, secondRecordList);
// 为了简单易懂，和代码流的相似度计算一样，这里的计算也是会出现重用的情况，大家请自行改写
for(List<ApiRecord> firstRecords : firstRecordList) {
float maxScore = 0;
Iterator<List<ApiRecord>> iter = secondRecordList.iterator();
for(;iter.hasNext();) {
float score = calcuateScore(firstRecords, iter.next());
if(score > maxScore) {
maxScore = score;
}
if(maxScore > 0.999f) {
break;
}
}
if(maxScore > 0.999f) {
identicalCount++;
} else if(maxScore > 0.2f) {
similarityCount++;
allScore += maxScore;
} else {
delCount++;
}
}
newCount = Math.abs(firstRecordList.size() - secondRecordList.size());
// 相似度结果： (完全相同数量+相似度总得分+跳过的最少值)/最大的方法数
similarityScore = (identicalCount + allScore + Math.min(skipFirstCount, skipSecondCount)) / (double)Math.max(firstNode.classes.size(), secondNode.classes.size()) * 100;
// 输出结果
System.out.println("Elements:\t" + firstRecordList.size() + "<->" + secondRecordList.size());
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");
}
public static float calcuateScore(List<ApiRecord> firstRecords, List<ApiRecord> secondRecords) {
// 这里是基于无序的API序列
int identicalCount = 0;
Iterator<ApiRecord> firstIter = firstRecords.iterator();
while(firstIter.hasNext()) {
ApiRecord firstRecord = firstIter.next();
Iterator<ApiRecord> secondIter = secondRecords.iterator();
while(secondIter.hasNext()) {
if(firstRecord.equals(secondIter.next())) {
secondIter.remove();
firstIter.remove();
identicalCount++;
break;
}
}
}
return identicalCount / ((firstRecords.size() + secondRecords.size()) / 2.0f);
}
// 转换为API记录
public static int parse(ApplicationNode applicationNode, List<List<ApiRecord>> recordMap) {
int skipCount = 0;
final Set<String> allMethodKey = getAllMethodKey(applicationNode);
for(ClassNode classNode : applicationNode.classes) {
// 以类为基准进行相似度识别
final Map<String, ApiRecord> records = new HashMap<String, ApiRecord>();
if(classNode.methods != null) {
for(MethodNode methodNode : classNode.methods) {
if(methodNode.instructions.size() == 0) {
continue;
}
methodNode.accept(new MethodVisitor(ASM4) {
@Override
public void visitMethodInsn(int opcode, String owner, String name, String desc, int[] arguments) {
super.visitMethodInsn(opcode, owner, name, desc, arguments);
String key = ApiMain.toString(owner, name, desc);
if(!records.containsKey(key)) {
// 识别是用户API还是系统API
boolean isUserApi = allMethodKey.contains(key);
// 用户API统一使用空串，不作区分，系统API使用其签名
// 用户API分值为1，系统API分值为30
records.put(key, new ApiRecord(isUserApi?"":key, isUserApi?1:30));
}
// 增加调用次数
records.get(key).invokeTimes++;
}
});
}
}
if(records.isEmpty()) {
// 没有记录，作跳过处理
++skipCount;
} else {
recordMap.add(new ArrayList<ApiRecord>(records.values()));
}
}
return skipCount;
}
// 获取所有方法的标识
public static Set<String> getAllMethodKey(ApplicationNode applicationNode) {
Set<String> res = new HashSet<String>();
for(ClassNode classNode : applicationNode.classes) {
if(classNode.methods != null) {
for(MethodNode methodNode : classNode.methods) {
res.add(toString(classNode.name, methodNode.name, methodNode.name));
}
}
}
return res;
}
public static String toString(String owner, String name, String desc) {
return owner + "." + name + desc;
}
}
|
基于变量计数的原理
在Java编程中，变量包括成员变量、临时变量、参数。在bytecode中，变量包括成员变量、本地变量（前面是参数，后面是临时变量），而在dalvik bytecode中，变量包括成员变量、寄存器（前面是临时变量，后面是参数）。
基于变量计数，即基于变量读写次数的比较。不过，这里为了提高相似度，增加一个特殊的变量计数——方法调用。
与基于API序列类似，这里设计一个变量调用的记录，其中包括读取次数、写入次数、得分（这里没加入标识来区分API，有兴趣的可以自己加上）。其中这里设计方法调用这个特殊变量得分最高，成员变量得分次之，临时变量得分最低。
基于变量计数的流程与实现
基于变量计数与基于API序列的流程基本一致，不过基于asm与基于asmdex的获取数据的方式却是不大一样，这与bytecode和dalvik bytecode的设计有关。
bytecode中读写成员变量的指令对应于ASM的visitFieldInsn方法，而读写本地变量的指令对应于ASM的visitVarInsn方法（其实还有visitIincInsn方法）。
dalvik bytecode中读写成员变量的指令对应于ASMDEX的visitFieldInsn方法，这一点与bytecode基本类似。但由于大部分指令都会读写寄存器（对应于bytecode的本地变量），因此代码处理起来会相对复杂一点点。
下面是变量计数记录的代码，（ASM及ASMDEX均可使用）：
1
2
3
4
5
6
7
8
| public class VarRecord {
// 用于提高相似度的准确率
public int score;
// 读取次数
public int readTimes = 0;
// 写入次数
public int writeTimes = 0;
}
|
接下来我采用的是ASM(ASMDEX的实现请自行研究)，这里我只给出关键的代码，流程相关的代码请借鉴基于API序列的代码：
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
| public static int parse(List<ClassNode> classes, List<List<VarRecord>> varRecordsList) {
int skipCount = 0;
for(ClassNode classNode : classes) {
// 以类为基准进行相似度识别
final Map<String, VarRecord> records = new HashMap<String, VarRecord>();
if(classNode.methods != null) {
for(MethodNode methodNode : classNode.methods) {
if(methodNode.instructions.size() == 0) {
continue;
}
methodNode.accept(new MethodVisitor(ASM5) {
@Override
public void visitMethodInsn(int opcode, String owner, String name, String desc, boolean itf) {
super.visitMethodInsn(opcode, owner, name, desc, itf);
// 方法的得分设为30，调用一次就认为写一次
get(owner+name+desc, 30).writeTimes++;
}
@Override
public void visitFieldInsn(int opcode, String owner, String name, String desc) {
super.visitFieldInsn(opcode, owner, name, desc);
if(opcode == GETFIELD || opcode == GETSTATIC) {
// 属性的得分设为30，GETFIELD与GETSTATIC均为读取
get(owner+name+desc, 25).readTimes++;
} else {
get(owner+name+desc, 25).writeTimes++;
}
}
@Override
public void visitVarInsn(int opcode, int var) {
super.visitVarInsn(opcode, var);
// xload类指令用来读取本地变量
if(opcode >= ILOAD && opcode <= ALOAD) {
get(var+"", 1).readTimes++;
} else if(opcode >= ISTORE && opcode <= ASTORE) {
// xstore类指令用来写入本地变量
get(var+"", 1).writeTimes++;
}
}
@Override
public void visitIincInsn(int var, int increment) {
super.visitIincInsn(var, increment);
// 先读取，后写入
VarRecord vr = get(var+"", 1);
vr.readTimes++;
vr.writeTimes++;
}
// 简单封装下
public VarRecord get(String key, int score) {
if(!records.containsKey(key)) {
records.put(key, new VarRecord());
records.get(key).score = score;
}
return records.get(key);
}
});
}
}
if(records.isEmpty()) {
// 没有记录，作跳过处理
++skipCount;
} else {
varRecordsList.add(new ArrayList<VarRecord>(records.values()));
}
}
return skipCount;
}
|
该方法针对方法调用(visitMethodInsn)、属性调用(visitFieldInsn)、本地变量读写(visitVarInsn、visitIincInsn)进行重写，并作记录。
记录得到的数据即可用于进行相似度分析。