前言
最近打算开始入门一些自动化审计工具，拿gadget-inspector入手。主要学习了两篇文章，一个是三梦师傅的，一个是Longofo师傅。可以说，如果有一定的字节码基础，加上这两篇文章的学习，gadget-inspector的底层源码应该能够理解的七七八八了。
笔者在看完上面两篇文章后，感觉还剩下两三分没学到位。于是梳理了一下整个过程，把比较模糊的地方拿出来再细看了看，才有了这篇文章。
因此，这篇文章并不是完整分析gadget-inspector的底层源码，而是仅用于记录一些笔者学习过程中遇到的小问题，建议结合上面两篇文章一起阅读。
逆拓扑排序
关于逆拓扑排序，在Longofo师傅的文章中给出了比较详细的讲解，不过我仍有一些不太理解的地方，于是把这个部分进行详细分析一下。
这里先啰嗦一嘴，为什么要进行这个逆拓扑排序？
逆拓扑排序是在PassthroughDiscovery阶段进行的，这个阶段的主要任务是寻找能污染方法返回值的方法参数。设想，如果某个方法的方法体中又调用了别的方法，且将参数进行了传递，例如
package com.zfirm;
import java.io.IOException;
public class Main {
public String main(String args) throws IOException {
String cmd = new A().method1(args);
return new B().method2(cmd);
}
}
class A {
public String method1(String param) {
return param;
}
}
class B {
public String method2(String param) {
return new C().method3(param);
}
}
class C {
public String method3(String param) {
return param;
}
}
class D{
public StringBuilder method4(){
return new StringBuilder("aa");
}
}
B类的method2方法调用了C类的method3方法，并且把method2的参数param直接传给了method3，然后将method3的返回值当作method2的返回值。按照直观感受，如果我们要判断method2的参数能否污染返回值，我们必须得跟入method3进行查看。如果method3的参数能污染method3的返回值，那么method2的参数也能污染。
这里说的有点绕，不过仔细看两遍还是能懂的。作者编程的思路与上述的思路是一致的。抽象地说，如果有这么一条调用链A->B->C->D，并且方法参数从A一直传递到D，那么我们需要倒序检查，依次检查D、C、B、A。因此，我们需要一个算法来生成这样的顺序，然后我们再按照这个顺序去检查，最终判断A方法的参数能否污染返回值。生成这样的顺序的算法就是逆拓扑序算法。
gadget-inspector中给出的代码实现如下，实际上就是dfs
private List<MethodReference.Handle> topologicallySortMethodCalls() {
Map<MethodReference.Handle, Set<MethodReference.Handle>> outgoingReferences = new HashMap<>();
for (Map.Entry<MethodReference.Handle, Set<MethodReference.Handle>> entry : methodCalls.entrySet()) {
MethodReference.Handle method = entry.getKey();
outgoingReferences.put(method, new HashSet<>(entry.getValue()));
}
// Topological sort methods
LOGGER.debug("Performing topological sort...");
Set<MethodReference.Handle> dfsStack = new HashSet<>();
Set<MethodReference.Handle> visitedNodes = new HashSet<>();
List<MethodReference.Handle> sortedMethods = new ArrayList<>(outgoingReferences.size());
for (MethodReference.Handle root : outgoingReferences.keySet()) {
dfsTsort(outgoingReferences, sortedMethods, visitedNodes, dfsStack, root);
}
LOGGER.debug(String.format("Outgoing references %d, sortedMethods %d", outgoingReferences.size(), sortedMethods.size()));
return sortedMethods;
}
private static void dfsTsort(Map<MethodReference.Handle, Set<MethodReference.Handle>> outgoingReferences,
List<MethodReference.Handle> sortedMethods, Set<MethodReference.Handle> visitedNodes,
Set<MethodReference.Handle> stack, MethodReference.Handle node) {
if (stack.contains(node)) {
return;
}
if (visitedNodes.contains(node)) {
return;
}
Set<MethodReference.Handle> outgoingRefs = outgoingReferences.get(node);
if (outgoingRefs == null) {
return;
}
stack.add(node);
for (MethodReference.Handle child : outgoingRefs) {
dfsTsort(outgoingReferences, sortedMethods, visitedNodes, stack, child);
}
stack.remove(node);
visitedNodes.add(node);
sortedMethods.add(node);
}
我们对照Longofo师傅给出的图来进行分析
这个图每个圆圈代表一个方法，可以看到存在方法的递归调用，med1->med2->med6->med1。这种调用在实际代码中是非常常见的，它会给逆拓扑序算法的编写带来一些麻烦，稍有不慎可能就会造成死循环。
先来看topologicallySortMethodCalls方法。outgoingReferences可以理解为一张图，就对应上面给出的方法调用图。它存储的是调用者方法与被调用方法的关系，根据上面的图，可以得出
{"med1":{"med2","med3","med4"},"med2":{"med3","med6"},省略...}
然后初始化了三个集合，分别是dfsStack、visitedNodes和sortedMethods。
- dfsStack：存储当前正在遍历的路径
- visitedNodes：存储已经遍历过的节点（方法）
- sortedMethods：存储已经排序完毕的节点（方法）
private List<MethodReference.Handle> topologicallySortMethodCalls() {
Map<MethodReference.Handle, Set<MethodReference.Handle>> outgoingReferences = new HashMap<>();
for (Map.Entry<MethodReference.Handle, Set<MethodReference.Handle>> entry : methodCalls.entrySet()) {
MethodReference.Handle method = entry.getKey();
outgoingReferences.put(method, new HashSet<>(entry.getValue()));
}
// Topological sort methods
LOGGER.debug("Performing topological sort...");
Set<MethodReference.Handle> dfsStack = new HashSet<>();
Set<MethodReference.Handle> visitedNodes = new HashSet<>();
List<MethodReference.Handle> sortedMethods = new ArrayList<>(outgoingReferences.size());
for (MethodReference.Handle root : outgoingReferences.keySet()) {
dfsTsort(outgoingReferences, sortedMethods, visitedNodes, dfsStack, root);
}
LOGGER.debug(String.format("Outgoing references %d, sortedMethods %d", outgoingReferences.size(), sortedMethods.size()));
return sortedMethods;
}
然后就开始从每一个入口方法开始，调用dfs进行遍历。这里有些的小细节要注意
【1】处，如果stack中包含node，说明node在本次dfs路径中出现过。比如med1->med2->med6->med1。当med1第二次出现时，我们选择直接return，如果不return就会造成死循环。不过，解决了死循环的同时也带来了一些问题。我们按照这样的算法得到的顺序是med7、med8、med3、med6、med2、med4、med1。如果我们单看med6->med1，我们判断med6的参数是否影响返回值时，需要先看med1，而由于med1排在med6后面，还没计算，所以此时med1的参数是否影响返回值我们还不得而知，因此也没法判断med6。
【2】处，碰到已经排序过的node直接返回
private static void dfsTsort(Map<MethodReference.Handle, Set<MethodReference.Handle>> outgoingReferences,
List<MethodReference.Handle> sortedMethods, Set<MethodReference.Handle> visitedNodes,
Set<MethodReference.Handle> stack, MethodReference.Handle node) {
//【1】
if (stack.contains(node)) {
return;
}
//【2】
if (visitedNodes.contains(node)) {
return;
}
Set<MethodReference.Handle> outgoingRefs = outgoingReferences.get(node);
if (outgoingRefs == null) {
return;
}
stack.add(node);
for (MethodReference.Handle child : outgoingRefs) {
dfsTsort(outgoingReferences, sortedMethods, visitedNodes, stack, child);
}
stack.remove(node);
visitedNodes.add(node);
sortedMethods.add(node);
}
其实总的看下来，所谓的逆拓扑排序实际上就是dfs，而且感觉在递归调用的处理上会有点小问题，可能会导致med6判断结果有误。
passthrough.dat的作用
笔者在完整看完一遍文章之后，总感觉有些地方还是不太理解，看似整个程序非常有逻辑，分为了五大步骤，但是这五个步骤之间的关系似乎不是那么的明显，其中最让我费解的就是第二步生成的这个passthrough.dat到底有什么用，接下来就来探索一下它的用处。
生成passthrough.dat是在第二步（配合文末的图来看），用到它是在第三步——生成调用图。具体怎么用的呢？
在第三步CallGraphDiscovery::discover中，将passthrough.dat读取了进来，然后传递给了ModelGeneratorClassVisitor的构造方法
跟进ModelGeneratorClassVisitor的构造方法，将passthroughDataflow保存到了字段当中
紧接着在ModelGeneratorClassVisitor::visitMethod对方法进行观察时，将passthroughDataflow传递给了ModelGeneratorMethodVisitor的构造方法
跟进ModelGeneratorMethodVisitor，发现它将passthroughDataflow传递给了父类的构造方法
跟进父类TaintTrackingMethodVisitor的构造方法，发现它将passthroughDataflow保存到了字段当中
到这里可以做个小结，passthroughDataflow一共被保存到了两处，一处是在ModelGeneratorMethodVisitor的父类TaintTrackingMethodVisitor字段中，另一处是在ModelGeneratorClassVisitor的字段中。实际上真正用到它的是在前面一处。
我们来用一个例子来看看，用下面这个代码生成一个jar包，让gadget-inspector进行分析。
package com.zfirm;
import java.io.IOException;
public class Main {
public String main(String args) throws IOException {
String cmd = new A().method1(args);
return new B().method2(cmd);
}
}
class A {
public String method1(String param) {
return param;
}
}
class B {
public String method2(String param) {
return new C().method3(param);
}
}
class C {
public String method3(String param) {
return param;
}
}
class D{
public StringBuilder method4(){
return new StringBuilder("aa");
}
}
这里有些小技巧。虽然说我们可以使用jdk原生的类作为例子进行分析，但是这分析起来会复杂很多，所以我们构造了一个简单的例子。但是在调试时，想要程序在分析这些类时让断点停下来需要一些技巧。
这里有两种方法，一个是设置条件断点。在ModelGeneratorClassVisitor::visitMethod方法中设置条件断点
不过这种方式会导致程序执行得非常慢，断点很久才能停下来。所以有了下面这种笨办法，就是直接加代码进行判断（85-87行），然后打上断点。这种方式程序就很快能跑到断点处停下来了。
回到主题，接着分析passthrough.dat的作用。我们按照上面的方式打好断点后，当断点停下来时，就是程序准备生成上面那个例子的调用图了。
接下来的就会看到轮番调用ModelGeneratorMethodVisitor的各个方法:visitCode、visitFieldInsn、visitMethodInsn等，这里不重复分析，三梦师傅的文章讲的很详细。概括一下就是：每条字节码都会对应一种方法，在asm对字节码进行分析时，就会找到对应的方法去进行回调执行。
我们来看method2的字节码，前面部分忽略，重点关注第5条invokevirtual，这是准备调用method3了
在asm分析这条字节码时，回调的方法是ModelGeneratorMethodVisitor::visitMethodInsn，在这个方法末尾调用了父类的visitMethodInsn
跟进TaintTrackingMethodVisitor::visitMethodInsn，这个方法的作用实际上就是在模拟方法执行
@Override
public void visitMethodInsn(int opcode, String owner, String name, String desc, boolean itf) {
final MethodReference.Handle methodHandle = new MethodReference.Handle(
new ClassReference.Handle(owner), name, desc);
Type[] argTypes = Type.getArgumentTypes(desc);
//如果不是静态方法，则扩充参数列表，将第一个参数设置为为this
if (opcode != Opcodes.INVOKESTATIC) {
Type[] extendedArgTypes = new Type[argTypes.length+1];
System.arraycopy(argTypes, 0, extendedArgTypes, 1, argTypes.length);
extendedArgTypes[0] = Type.getObjectType(owner);
argTypes = extendedArgTypes;
}
final Type returnType = Type.getReturnType(desc);
final int retSize = returnType.getSize();
//模拟方法执行
switch (opcode) {
case Opcodes.INVOKESTATIC:
case Opcodes.INVOKEVIRTUAL:
case Opcodes.INVOKESPECIAL:
case Opcodes.INVOKEINTERFACE:
//初始化污点参数集合
final List<Set<T>> argTaint = new ArrayList<Set<T>>(argTypes.length);
for (int i = 0; i < argTypes.length; i++) {
argTaint.add(null);
}
//模拟方法执行：从操作数栈中弹出对应的参数，保存到污点参数集合中
for (int i = 0; i < argTypes.length; i++) {
Type argType = argTypes[i];
if (argType.getSize() > 0) {
for (int j = 0; j < argType.getSize() - 1; j++) {
pop();
}
argTaint.set(argTypes.length - 1 - i, pop());
}
}
//返回值污点
Set<T> resultTaint;
if (name.equals("<init>")) {
// Pass result taint through to original taint set; the initialized object is directly tainted by
// parameters
resultTaint = argTaint.get(0);
} else {
resultTaint = new HashSet<>();
}
// If calling defaultReadObject on a tainted ObjectInputStream, that taint passes to "this"
if (owner.equals("java/io/ObjectInputStream") && name.equals("defaultReadObject") && desc.equals("()V")) {
savedVariableState.localVars.get(0).addAll(argTaint.get(0));
}
for (Object[] passthrough : PASSTHROUGH_DATAFLOW) {
if (passthrough[0].equals(owner) && passthrough[1].equals(name) && passthrough[2].equals(desc)) {
for (int i = 3; i < passthrough.length; i++) {
resultTaint.addAll(argTaint.get((Integer)passthrough[i]));
}
}
}
if (passthroughDataflow != null) {
Set<Integer> passthroughArgs = passthroughDataflow.get(methodHandle);
if (passthroughArgs != null) {
for (int arg : passthroughArgs) {
resultTaint.addAll(argTaint.get(arg));
}
}
}
// Heuristic; if the object implements java.util.Collection or java.util.Map, assume any method accepting an object
// taints the collection. Assume that any method returning an object returns the taint of the collection.
if (opcode != Opcodes.INVOKESTATIC && argTypes[0].getSort() == Type.OBJECT) {
Set<ClassReference.Handle> parents = inheritanceMap.getSuperClasses(new ClassReference.Handle(argTypes[0].getClassName().replace('.', '/')));
if (parents != null && (parents.contains(new ClassReference.Handle("java/util/Collection")) ||
parents.contains(new ClassReference.Handle("java/util/Map")))) {
for (int i = 1; i < argTaint.size(); i++) {
argTaint.get(0).addAll(argTaint.get(i));
}
if (returnType.getSort() == Type.OBJECT || returnType.getSort() == Type.ARRAY) {
resultTaint.addAll(argTaint.get(0));
}
}
}
if (retSize > 0) {
//模拟方法执行：将返回值入栈
push(resultTaint);
for (int i = 1; i < retSize; i++) {
push();
}
}
break;
default:
throw new IllegalStateException("Unsupported opcode: " + opcode);
}
super.visitMethodInsn(opcode, owner, name, desc, itf);
sanityCheck();
}
我们重点关注这部分，因为这里用到了passthroughDataflow。
首先从passthroughDataflow获取target方法的污染参数下标集合保存到了passthroughArgs。
然后遍历passthroughArgs，将其转变为caller方法的污染参数下标集合，然后保存到resultTaint中
我们先让它执行676行，获取到的target方法的污染参数下标集合里有一个元素1，这里target方法为method3，caller方法为method2，说明method3下标为1的参数可以污染method3的返回值（下标0为this），这个结果显而易见
class B {
public String method2(String param) {
return new C().method3(param);
}
}
class C {
public String method3(String param) {
return param;
}
}
继续向下跟进到for循环，执行argTaint.get(arg)，这里argTaint保存的是caller方法在调用target方法时使用的参数。这些参数都是以caller方法的参数列表下标来呈现的。
比如现在argTaint有两个元素，0号下标为this，1号下标为arg1。arg1说明这个参数是caller方法参数列表中的第一个参数，也即method2参数列表中的param参数。这也就说明，在method2(caller)调用method3(target)时，将method2的param参数传递给了method3进行调用。
在执行argTaint.get(arg)时，就是将caller方法的参数列表和target方法的参数列表联系了起来，建立了对应关系。逻辑是这样的：arg是target参数列表中可以污染返回值的参数下标，而argTaint又存储了caller方法在调用target方法时使用的参数列表，那么，argTaint.get(arg)就是获取了arg在caller参数列表中的下标，实现了污点传递的效果。笔者表达能力有限，这里说的或许有点绕，建议多看几遍理解。
然后将arg1加入到了resultTaint中，表示method2的arg1能够能够在method2调用method3时污染返回值。
最后，为了模拟方法执行，将返回值入栈
实际上这里想要实现的就是一个污点传递，如果代码再复杂一些，method2变成这样。那么我们通过上面的分析，知道了method2的param参数是可以污染method3的返回值的，也就能污染局部变量s，紧接着在分析Runtime.getRuntime().exec(s);时就能将其判断为sink。
设想，如果没有passthroughDataflow，我们就没法判断method3的param参数能否污染返回值，也就没法判断局部变量s能否被method2的param参数污染，最终也无从判断Runtime.getRuntime().exec(s);是否是sink点。
class B {
public String method2(String param) {
String s = new C().method3(param);
Runtime.getRuntime().exec(s);
return s;
}
}
总结
最后贴一张个人总结的流程图（忽略水印
参考文章