GadgetInspector源码阅读学习

学习下SAST的内容，先从GadgetInspector开始。

涉及到大量asm和java字节操作码的知识，有点困难，日后还是要系统学下好。

文章参考：

https://xz.aliyun.com/t/7058

https://tttang.com/archive/1683/

网上很多文章感觉讲的很明白了，这里记录下核心逻辑的笔记。

局部污点分析

逆拓扑排序

首先要了解逆拓扑排序，例如一个有向无环图

A->B

A->C

B->D

C->D

这里，节点 D 依赖于 B 和 C，而 B 和 C 都依赖于 A

我想知道D是否依赖于A，那么就可以从逆拓扑排序的结果里找了。

比如这个排序结果就是[D, B, C, A] ，但注意的是，逆拓扑只能保证一个大概结果，比如我们无法判断B,C之间的关系。所以要判断这类关系还要看原始图结构

GadgetInspector的拓扑排序是基于DFS的，网上文章有很多，原理不写了，直接看他怎么实现的。

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) {

				//环存在，直接return（不应该有环）
        if (stack.contains(node)) {
            return;
        }
        // 访问过了，直接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);
        }
  			
  			//最后栈是空的，全remove掉了
        stack.remove(node);
  			//该节点访问过了，加进visitedNodes
        visitedNodes.add(node);
  			//将该节点加入排序结果
        sortedMethods.add(node);
    }

污点分析

在抵达一个方法的时候，先把this放在局部变量表第一位

然后来到TaintTrackingMethodVisitor#visitVarInsn

ALOAD是引用类型的（对象），其他几个Int Float Double Long，反序列化中没啥用，直接给他忽略了。所以只有ALOAD分支才入操作数栈

然后来到PassthroughDiscovery#visitInsn

如图，会从操作数栈里获取污点

为啥是拿栈顶的呢？因为JVM规定，返回值总是位于栈顶。

但是这里有点没太搞懂，他结果不是有可能有多个索引吗，这样的话只能获取一个？

最后会回到gadgetinspector.PassthroughDiscovery#calculatePassthroughDataflow

缓存结果在passthroughDataflow

那么假如在某个函数里调用了另一个函数呢？此时就会来到：visitMethodInsn

如图，重点在最后几行。passthroughDataflow就是之前的缓存结果，这也是为什么要逆拓扑排序。实际debug时，总是Object的构造函数最先被分析，因为Object是所有类的父类，其构造函数当然处于逆拓扑排序的开头部分。

这样，在某个函数调用另一个函数的时候，总可以在缓存里取到结果。

callgraph部分和这部分差不多，就不写了。

SourceDiscovery

这个类是决定反序列化入口的抽象类，可以先看其子类JacksonSourceDiscovery

非常简单，构造函数，getter和setter可以作为入口。那么另一个呢？

SimpleSourceDiscovery

第一次才知道java有这个方法，类似php的__destruct，实际环境中根本没人这么写！

然后看readObject，原生的反序列化入口。

看网上的文章老说无法处理动态代理，看起来作者后来是加进去了。

hashCode和equals也可以作为入口，可以把他们丢进hashMap触发。

最后是一个groovy的代理

https://github.com/frohoff/ysoserial/blob/master/src/main/java/ysoserial/payloads/Groovy1.java

Gadget chain:
		ObjectInputStream.readObject()
			PriorityQueue.readObject()
				Comparator.compare() (Proxy)
					ConvertedClosure.invoke()
						MethodClosure.call()
							...
						  		Method.invoke()
									Runtime.exec()

利用链挖掘

第二关键的部分，现在我们已经有了所有想要的数据，接下来就是利用链挖掘的算法了。

首先加载了methodMap和inherianceMap，这些是在污点分析之前生成的。

methodMap里面是所有的方法，包含方法名，描述符等信息。

inheritanceMap结构是{某个类：{所有父类/接口集合}}

因为java可以重写方法，运行时不确定是哪个类。例如

AbstactClass 和 ImplementationClassA, ImplementationClassB

假设声明AbstractClass clazz。这个clazz可以是上面三者任意一个，只有运行时才能确定。

methodsByClass结构：{某类：{该类所有方法}}

然后生成subClassMap，结构是：{某类：{所有子类/实现}}。和inheritanceMap刚好相反

遍历methodMap，首先判断method是否静态，静态方法不可被重写，是的话直接跳。

然后获得该方法对应的类 的所有子类的方法，一个一个检查是否重名并且描述符相同（重写方法）。如果有丢到overridingMethods。最后再丢到methodImplMap

所以methodImplMap的结构：{某方法：{它的所有重写方法}}

回到GadgetChanDiscovery#discover， 这里对callGraph也做了整合，最终graphCallMap结构大致为：{某方法：{该方法里调用的所有方法}}

这一步是source初始化，GadgetChainLink包含了sourceMethod和污点参数的信息。

最后一步了。

GadgetChain chain = methodsToExplore.pop();
GadgetChainLink lastLink = chain.links.get(chain.links.size()-1);

先从methodsToExplore弹出一个chain，然后获取这个chain的最后一个Link节点。

Set<GraphCall> methodCalls = graphCallMap.get(lastLink.method);

从graphCallMap获取这个Link节点方法中，调用的所有其他方法。

if (graphCall.getCallerArgIndex() != lastLink.taintedArgIndex) {
    continue;
}

然后进入遍历，判断是否能被参数污染，不能就跳

Set<MethodReference.Handle> allImpls = implementationFinder.getImplementations(graphCall.getTargetMethod());

获取被调用的方法的所有重写/实现。再次遍历这个集合：

GadgetChainLink newLink = new GadgetChainLink(methodImpl, graphCall.getTargetArgIndex());
if (exploredMethods.contains(newLink)) {
    continue;
}

GadgetChain newChain = new GadgetChain(chain, newLink);

生成新Link节点，if防止死循环。如果没问题就生成newChain，由之前的chain和newLink拼接而成。

if (isSink(methodImpl, graphCall.getTargetArgIndex(), inheritanceMap)) {
    discoveredGadgets.add(newChain);
} else {
    methodsToExplore.add(newChain);
    exploredMethods.add(newLink);
}

判断是不是sink，是的话加入discoverdGadgets，不是的话，丢进methodsToExplore，以后循环遍历的时候继续往下找。并且还要计入exploredMethods防止重复。

随着methodsToExplore不断pop，exploredMethods不断增加，最后methodToExplore大小为0时，遍历结束，将结果写入txt文件里。

完。