深入分析GadgetInspector核心代码（三）-阿里云开发者社区

5.8 xxxTaint

一些出入栈和局部变量表的操作

这些方法并不影响Stack的POP/PUSH，只是往已有的位置设置污染信息

protected Set<T> getStackTaint(int index) {
    // 出栈，注意是栈结构，index=0为栈顶
    return savedVariableState.stackVars.get(savedVariableState.stackVars.size()-1-index);
}
protected void setStackTaint(int index, T ... possibleValues) {
    Set<T> values = new HashSet<T>();
    for (T value : possibleValues) {
        values.add(value);
    }
    // 入栈，index=0为栈顶
    savedVariableState.stackVars.set(savedVariableState.stackVars.size()-1-index, values);
}
protected void setStackTaint(int index, Collection<T> possibleValues) {
    // 同上
    Set<T> values = new HashSet<T>();
    values.addAll(possibleValues);
    savedVariableState.stackVars.set(savedVariableState.stackVars.size()-1-index, values);
}
protected Set<T> getLocalTaint(int index) {
    // 局部变量表直接操作
    return savedVariableState.localVars.get(index);
}
protected void setLocalTaint(int index, T ... possibleValues) {
    // 局部变量表直接操作
    Set<T> values = new HashSet<T>();
    for (T value : possibleValues) {
        values.add(value);
    }
    savedVariableState.localVars.set(index, values);
}
protected void setLocalTaint(int index, Collection<T> possibleValues) {
    // 局部变量表直接操作
    Set<T> values = new HashSet<T>();
    values.addAll(possibleValues);
    savedVariableState.localVars.set(index, values);
}

5.9 couldBeSerialized

是否能被序列化，决策者其实就是一个方法，用来判断什么情况下可以被序列化，什么情况下存在漏洞

protected static final boolean couldBeSerialized(SerializableDecider serializableDecider, InheritanceMap inheritanceMap, ClassReference.Handle clazz) {
        // 决策者后续分析
        if (Boolean.TRUE.equals(serializableDecider.apply(clazz))) {
            return true;
        }
        // 获取所有子类
        Set<ClassReference.Handle> subClasses = inheritanceMap.getSubClasses(clazz);
        if (subClasses != null) {
            // 遍历所有子类是否存在可被序列化的class
            for (ClassReference.Handle subClass : subClasses) {
                // 使用决策者判断是否可被序列化
                if (Boolean.TRUE.equals(serializableDecider.apply(subClass))) {
                    return true;
                }
            }
    }
    return false;
}

比如Jackson的决策者

@Override
public Boolean apply(ClassReference.Handle handle) {
    if (isNoGadgetClass(handle)) {
        return false;
    }
    // 类是否通过决策的缓存集合
    Boolean cached = cache.get(handle);
    if (cached != null) {
        return cached;
    }
    Set<MethodReference.Handle> classMethods = methodsByClassMap.get(handle);
    if (classMethods != null) {
        for (MethodReference.Handle method : classMethods) {
            // 该类只要有无参构造方法就通过决策
            if (method.getName().equals("<init>") && method.getDesc().equals("()V")) {
                cache.put(handle, Boolean.TRUE);
                return Boolean.TRUE;
            }
        }
    }
    cache.put(handle, Boolean.FALSE);
    return Boolean.FALSE;
}
private boolean isNoGadgetClass(ClassReference.Handle clazz) {
    // 黑名单匹配
    if (JacksonSourceDiscovery.skipList.contains(clazz.getName())) {
        return true;
    }
    return false;
}

5.10 作用

该类模拟了JVM中的operand Stack和Local Varaibles，个人理解相当于把完全静态的代码做成了半动态，结合业务逻辑代码，实现数据流动分析。POP和PUSH的都是空Set，如果分析中认为存在污点，那么就把对应Set位置设为污染

6 PassthroughDataflowClassVisitor

该类不是重点，第7条PassthroughDataflowMethodVisitor应重点关注

6.1 构造

// [类名->类信息]
Map<ClassReference.Handle, ClassReference> classMap;
// 要观察的方法
private final MethodReference.Handle methodToVisit;
// [子类->[父类,父类的父类...]]或相反
private final InheritanceMap inheritanceMap;
// 方法返回值与哪个参数有关系
private final Map<MethodReference.Handle, Set<Integer>> passthroughDataflow;
// 决策者
private final SerializableDecider serializableDecider;
// 当前visit的类名
private String name;
// 一个MethodVisitor
private PassthroughDataflowMethodVisitor passthroughDataflowMethodVisitor;
public PassthroughDataflowClassVisitor(...) {
    super(api);
    // 赋值
    this.classMap = classMap;
    this.inheritanceMap = inheritanceMap;
    this.methodToVisit = methodToVisit;
    this.passthroughDataflow = passthroughDataflow;
    this.serializableDecider = serializableDecider;
}

6.2 visit

public void visit(int version, int access, String name, String signature,
                  String superName, String[] interfaces) {
    super.visit(version, access, name, signature, superName, interfaces);
    this.name = name;
    // 当前类不是要观察方法所属的类则跳过
    if (!this.name.equals(methodToVisit.getClassReference().getName())) {
        throw new IllegalStateException("Expecting to visit " + methodToVisit.getClassReference().getName() + " but instead got " + this.name);
    }
}

6.3 visitMethod

public MethodVisitor visitMethod(int access, String name, String desc,
                                 String signature, String[] exceptions) {
    // 当前visit的方法不是目标方法需要跳过
    if (!name.equals(methodToVisit.getName()) || !desc.equals(methodToVisit.getDesc())) {
        return null;
    }
    // method visitor不能重复
    if (passthroughDataflowMethodVisitor != null) {
        throw new IllegalStateException("Constructing passthroughDataflowMethodVisitor twice!");
    }
    // 对当前方法进行观察
    MethodVisitor mv = super.visitMethod(access, name, desc, signature, exceptions);
    // 跟入7
    passthroughDataflowMethodVisitor = new PassthroughDataflowMethodVisitor(
            classMap, inheritanceMap, this.passthroughDataflow, serializableDecider,
            api, mv, this.name, access, name, desc, signature, exceptions);
    // 参考3.2，出于兼容性的考虑
    return new JSRInlinerAdapter(passthroughDataflowMethodVisitor, access, name, desc, signature, exceptions);
}

6.4 getReturnTaint

// 一个非visit方法，获得返回污点，返回值与哪些参数有关
public Set<Integer> getReturnTaint() {
   if (passthroughDataflowMethodVisitor == null) {
       throw new IllegalStateException("Never constructed the passthroughDataflowmethodVisitor!");
  }
   return passthroughDataflowMethodVisitor.returnTaint;
}

6.5 作用

与7结合分析数据流之间的污染

7 PassthroughDataflowMethodVisitor

继承自TaintTrackingMethodVisitor

7.1 构造

// 父类TaintTrackingMethodVisitor在7分析
private static class PassthroughDataflowMethodVisitor extends TaintTrackingMethodVisitor<Integer> {
// [类名->类信息]
   private final Map<ClassReference.Handle, ClassReference> classMap;
   // [子类->[父类,父类的父类...]]或相反
   private final InheritanceMap inheritanceMap;
// [方法名->[1,2,3]] 方法返回值与哪个参数有关系
   private final Map<MethodReference.Handle, Set<Integer>> passthroughDataflow;
   // 后文分析，决策者
   private final SerializableDecider serializableDecider;
   // 当前方法access（public/private...）
   private final int access;
   // 当前方法desc（void(int a) -> (I)V）
   private final String desc;
   // 被污染的返回
   private final Set<Integer> returnTaint;
   public PassthroughDataflowMethodVisitor(...);
       // 赋值
       this.classMap = classMap;
       this.inheritanceMap = inheritanceMap;
       this.passthroughDataflow = passthroughDataflow;
       this.serializableDecider = serializableDeciderMap;
       this.access = access;
       this.desc = desc;
       returnTaint = new HashSet<>();
  }

7.2 visitCode

在进入方法体的时候调用

父类先清空stack和局部变量表，重新设置局部变量表为正确的值

然后交给子类给该方法每个参数位置设置污染到局部变量表

// visit流程中最先调用的
public void visitCode() {
    super.visitCode();
    // local variables数组
    int localIndex = 0;
    // 参数数量
    int argIndex = 0;
    // 判断逻辑参考2.1
    if ((this.access & Opcodes.ACC_STATIC) == 0) {
        // 非静态情况，本地变量[0] = this
        // 添加到本地变量表集合
        setLocalTaint(localIndex, argIndex);
        localIndex += 1;
        argIndex += 1;
    }
    for (Type argType : Type.getArgumentTypes(desc)) {
        // 判断参数类型，得出变量占用空间大小，然后存储
        // 例如long的大小是2，int大小为1
        setLocalTaint(localIndex, argIndex);
        localIndex += argType.getSize();
        // 参数数量
        argIndex += 1;
    }
}

7.3 visitInsn

无操作数的操作，注意子类和父类的顺序不可乱

子类：

如果操作是return，将返回值加入到返回污点中

父类：

进行POP/PUSH等正常操作

public void visitInsn(int opcode) {
    switch(opcode) {
        // 从当前方法返回int
        case Opcodes.IRETURN:
        // 从当前方法返回float
        case Opcodes.FRETURN:
        // 从当前方法返回对象引用
        case Opcodes.ARETURN:
            // 父类方法，返回污点里保存栈顶元素
            returnTaint.addAll(getStackTaint(0));
            break;
        // 从当前方法返回long
        case Opcodes.LRETURN:
        // 从当前方法返回double
        case Opcodes.DRETURN:
            // 父类方法，返回污点里保存栈顶元素（size为2）
            returnTaint.addAll(getStackTaint(1));
            break;
        // 从当前方法返回void不处理
        case Opcodes.RETURN:
            break;
        default:
            break;
    }
    // 交给父类
    super.visitInsn(opcode);
}

7.4 visitFieldInsn

字段（属性）相关的操作

子类：

如果opcode是GETFIELD，这个操作需要从Stack里POP出一个对象再把得到的值PUSH进去

如果这个字段类型包括基类都可以被反序列化，那么目前栈顶的这个对象就是污染

可以看到，先暂存了这个污染对象

父类：

模拟JVM的POP/PUSH操作，这时候栈顶就是PUSH进去的值

根据暂存的污染对象，把目前栈顶的值设置为污染

这样做的目的是能够让污染传递下去，从右边到左边

public void visitFieldInsn(int opcode, String owner, String name, String desc) {
   switch (opcode) {
       // 如果是获得STATIC变量的值跳过
       case Opcodes.GETSTATIC:
           break;
       // 如果是设置STATIC变量的值跳过
       case Opcodes.PUTSTATIC:
           break;
       // 如果是获得普通字段的值
       case Opcodes.GETFIELD:
           // 获取字段类型
           Type type = Type.getType(desc);
           // 非long和double时size为1
           if (type.getSize() == 1) {
               // 可能为引用类型
               // 是否不可序列化
               Boolean isTransient = null;
               // 父类方法，判断调用的字段类型是否可序列化
               if (!couldBeSerialized(serializableDecider, inheritanceMap, new ClassReference.Handle(type.getInternalName()))) {
                   isTransient = Boolean.TRUE;
              } else {
                   // 若调用的字段可被序列化，则取当前类实例的所有字段，找出调用的字段，判断是否被标识了transient
                   // 找到当前的类信息
                   ClassReference clazz = classMap.get(new ClassReference.Handle(owner));
                   while (clazz != null) {
                       // 遍历字段
                       for (ClassReference.Member member : clazz.getMembers()) {
                           if (member.getName().equals(name)) {
                               // 如果字段是TRANSIENT的不可被反序列化则跳过
                               isTransient = (member.getModifiers() & Opcodes.ACC_TRANSIENT) != 0;
                               break;
                          }
                      }
                       if (isTransient != null) {
                           break;
                      }
                       // 向上父类遍历查找可被序列化字段
                       clazz = classMap.get(new ClassReference.Handle(clazz.getSuperClass()));
                  }
              }
               // 污点列表
               Set<Integer> taint;
               if (!Boolean.TRUE.equals(isTransient)) {
                   // 可被序列化
                   taint = getStackTaint(0);
              } else {
                   // 不可被序列化
                   taint = new HashSet<>();
              }
               // 父类处理
               super.visitFieldInsn(opcode, owner, name, desc);
               // 设置栈顶是污点
               setStackTaint(0, taint);
               return;
          }
           break;
       // 如果是设置普通字段的值，跳过
       case Opcodes.PUTFIELD:
           break;
       default:
           throw new IllegalStateException("Unsupported opcode: " + opcode);
  }
   super.visitFieldInsn(opcode, owner, name, desc);
}

7.5 visitMethodInsn

方法的调用需要从Stack里面取参数，最后把返回值压入Stack，参考5.7.6中的图片

关于passthroughDataflow，已经进行DFS排序，调用链最末端最先被visit，因此，调用到的方法必然已被visit分析过（参考三梦师傅）

子类做的事：

得到模拟Stack中应该获取的参数，设置到argTaint

如果是构造方法，那么argTaint第0位this就是污染

根据已有的passthroughDataflow得到与返回值有关的参数索引Set，加入污染

父类做的事：

参考5.7.6，根据方法调用需要的参数，在Stack中POP

如果是构造方法，那么argTaint第0位this就是污染

如果是void ObjectInputStream.defaultReadObject()不传参，这时候对象本身this就是污染，给局部变量表第0位设置污染

如果目前的方法恰好匹配到白名单（很可能存在漏洞）那么白名单函数的参数位置设置到污染

根据已有的passthroughDataflow得到与返回值有关的参数索引Set，加入污染

如果当前类是集合类子类，认为集合中所有元素都是污染；如果返回对象或数组，认为返回也是污染

最后把污染结果入栈，这模拟的就是执行完方法的PUSH返回值

子类继续做：

这时候子类取到Stack顶的RETURN值，在父类的污染中再加入子类得到的污染

注意：重复添加了很多污染，会不会重复？不会，因为污染是参数的位置int值组成的Set，Set特性是不会重复

// 如果方法中有方法相关的操作
public void visitMethodInsn(int opcode, String owner, String name, String desc, boolean itf) {
   // 获取method参数类型
   Type[] argTypes = Type.getArgumentTypes(desc);
   // 静态调用
   if (opcode != Opcodes.INVOKESTATIC) {
       // 如果执行的非静态方法，则本地变量[0]=this
       // 这里获得的参数类型argTypes中不存在this，需要手动加
       Type[] extendedArgTypes = new Type[argTypes.length+1];
       System.arraycopy(argTypes, 0, extendedArgTypes, 1, argTypes.length);
       // 把this的type加到0，后面的往后推
       extendedArgTypes[0] = Type.getObjectType(owner);
       argTypes = extendedArgTypes;
  }
   // 获取返回值类型大小
   int retSize = Type.getReturnType(desc).getSize();
   // 返回值污点
   Set<Integer> resultTaint;
   switch (opcode) {
       // 任何一种方法调用
       case Opcodes.INVOKESTATIC:
       case Opcodes.INVOKEVIRTUAL:
       case Opcodes.INVOKESPECIAL:
       case Opcodes.INVOKEINTERFACE:
           // 构造污染参数集合
           final List<Set<Integer>> argTaint = new ArrayList<Set<Integer>>(argTypes.length);
           for (int i = 0; i < argTypes.length; i++) {
               // 占位
               argTaint.add(null);
          }
           // 由于方法调用需要弹出栈中的参数
           int stackIndex = 0;
           for (int i = 0; i < argTypes.length; i++) {
               Type argType = argTypes[i];
               if (argType.getSize() > 0) {
                   // 根据参数类型大小，从栈底获取入参，参数入栈是从右到左的
                   argTaint.set(argTypes.length - 1 - i, getStackTaint(stackIndex + argType.getSize() - 1));
              }
               // stack深度根据size增加
               stackIndex += argType.getSize();
          }
           // 构造方法的调用
           if (name.equals("<init>")) {
               // 参数this就是污点
               resultTaint = argTaint.get(0);
          } else {
               resultTaint = new HashSet<>();
          }
           // 方法返回值与哪个参数有关系，可能是空
           Set<Integer> passthrough = passthroughDataflow.get(new MethodReference.Handle(new ClassReference.Handle(owner), name, desc));
           if (passthrough != null) {
               for (Integer passthroughDataflowArg : passthrough) {
                   // 加入污点
                   resultTaint.addAll(argTaint.get(passthroughDataflowArg));
              }
          }
           break;
       default:
           throw new IllegalStateException("Unsupported opcode: " + opcode);
  }
   // 传递
   super.visitMethodInsn(opcode, owner, name, desc, itf);
   // 存在返回，设置返回为污点
   if (retSize > 0) {
       getStackTaint(retSize-1).addAll(resultTaint);
  }
}

关于这个passthroughDataFlow是个全局变量，是一个缓存，visit一个类就缓存一次

PassthroughDataflowClassVisitor cv = new PassthroughDataflowClassVisitor(classMap, inheritanceMap,
       passthroughDataflow, serializableDecider, Opcodes.ASM6, method);
cr.accept(cv, ClassReader.EXPAND_FRAMES);
passthroughDataflow.put(method, cv.getReturnTaint());

7.6 作用

与6结合分析数据流之间的污染，由5 TaintTrackingMethodVisitor作为驱动，模拟JVM执行代码

8 PassthroughDiscovery

业务逻辑代码，同样是重点

8.1 属性

// 方法调用关系
private final Map<MethodReference.Handle, Set<MethodReference.Handle>> methodCalls = new HashMap<>();
// passthroughDataflow
private Map<MethodReference.Handle, Set<Integer>> passthroughDataflow;

8.2 discover

这里需要注意一个流程：先DFS排序，然后再进行PassthroughDataflowMethodVisitor的数据流污染分析，分析见8.7

// 加载文件记录的所有方法信息
Map<MethodReference.Handle, MethodReference> methodMap = DataLoader.loadMethods();
// 加载文件记录的所有类信息
Map<ClassReference.Handle, ClassReference> classMap = DataLoader.loadClasses();
// 加载文件记录的所有类继承、实现关联信息
InheritanceMap inheritanceMap = InheritanceMap.load();
// 搜索方法间的调用关系，缓存至methodCalls集合，返回类名->类资源，见8.3
Map<String, ClassResourceEnumerator.ClassResource> classResourceByName = discoverMethodCalls(classResourceEnumerator);
// 对方法调用关系进行字典排序，见8.4
List<MethodReference.Handle> sortedMethods = topologicallySortMethodCalls();
// 得到passthroughDataflow，见8.6
passthroughDataflow = calculatePassthroughDataflow(classResourceByName, classMap, inheritanceMap, sortedMethods,config.getSerializableDecider(methodMap, inheritanceMap));

8.3 discoverMethodCalls

主要是结合3，4做方法内的方法调用收集，没有什么难度

private Map<String, ClassResourceEnumerator.ClassResource> discoverMethodCalls(final ClassResourceEnumerator classResourceEnumerator) throws IOException {
   // className -> classResource
   Map<String, ClassResourceEnumerator.ClassResource> classResourcesByName = new HashMap<>();
   // all classes
   for (ClassResourceEnumerator.ClassResource classResource : classResourceEnumerator.getAllClasses()) {
       // 读入字节码
       try (InputStream in = classResource.getInputStream()) {
           // ASM解析
           ClassReader cr = new ClassReader(in);
           try {
               // 参考3和4，记录了方法调用
               MethodCallDiscoveryClassVisitor visitor = new MethodCallDiscoveryClassVisitor(Opcodes.ASM6);
               cr.accept(visitor, ClassReader.EXPAND_FRAMES);
               // 保存
               classResourcesByName.put(visitor.getName(), classResource);
          } catch (Exception e) {
               LOGGER.error("Error analyzing: " + classResource.getName(), e);
          }
      }
  }
   return classResourcesByName;
}

8.4 topologicallySortMethodCalls

核心代码

private List<MethodReference.Handle> topologicallySortMethodCalls() {
   Map<MethodReference.Handle, Set<MethodReference.Handle>> outgoingReferences = new HashMap<>();
   // copy
   for (Map.Entry<MethodReference.Handle, Set<MethodReference.Handle>> entry : methodCalls.entrySet()) {
       MethodReference.Handle method = entry.getKey();
       outgoingReferences.put(method, new HashSet<>(entry.getValue()));
  }
   LOGGER.debug("Performing topological sort...");
   // 深度优先搜索，利用stack回溯
   Set<MethodReference.Handle> dfsStack = new HashSet<>();
   // 已被visit的节点
   Set<MethodReference.Handle> visitedNodes = new HashSet<>();
   // 排序结果
   List<MethodReference.Handle> sortedMethods = new ArrayList<>(outgoingReferences.size());
   for (MethodReference.Handle root : outgoingReferences.keySet()) {
       // 见8.5
       dfsTsort(outgoingReferences, sortedMethods, visitedNodes, dfsStack, root);
  }
   LOGGER.debug(String.format("Outgoing references %d, sortedMethods %d", outgoingReferences.size(), sortedMethods.size()));
   return sortedMethods;
}

8.5 dfsTsort

遍历集合中的起始方法，进行递归深度优先搜索DFS，实现逆拓扑排序。最终结果是调用链的最末端排在最前面，这样才能实现入参、返回值、函数调用链之间的污点影响（参考三梦师傅）

stack保证了在进行逆拓扑排序时不会形成环，visitedNodes避免了重复排序（参考Longofo师傅）

深入分析参考8.7

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);
}

8.6 calculatePassthroughDataflow

private static Map<MethodReference.Handle, Set<Integer>> calculatePassthroughDataflow(Map<String, ClassResourceEnumerator.ClassResource> classResourceByName,Map<ClassReference.Handle, ClassReference> classMap,InheritanceMap inheritanceMap,List<MethodReference.Handle> sortedMethods,SerializableDecider serializableDecider) throws IOException {
   final Map<MethodReference.Handle, Set<Integer>> passthroughDataflow = new HashMap<>();
   for (MethodReference.Handle method : sortedMethods) {
       // 跳过static静态代码块
       if (method.getName().equals("<clinit>")) {
           continue;
      }
       // 获取所属类进行观察
       ClassResourceEnumerator.ClassResource classResource = classResourceByName.get(method.getClassReference().getName());
       try (InputStream inputStream = classResource.getInputStream()) {
           ClassReader cr = new ClassReader(inputStream);
           try {
               // 参考6和7
               PassthroughDataflowClassVisitor cv = new PassthroughDataflowClassVisitor(classMap, inheritanceMap,passthroughDataflow, serializableDecider, Opcodes.ASM6, method);
               cr.accept(cv, ClassReader.EXPAND_FRAMES);
               // 缓存方法返回值与哪个参数有关系
               passthroughDataflow.put(method, cv.getReturnTaint());
          } catch (Exception e) {
               LOGGER.error("Exception analyzing " + method.getClassReference().getName(), e);
          }
      } catch (IOException e) {
           LOGGER.error("Unable to analyze " + method.getClassReference().getName(), e);
      }
  }
   return passthroughDataflow;
}

8.7 分析

关于逆拓扑排序，参考Longofo师傅的文章，对图片做了一些优化和精简

这是一个方法调用关系：

17d65bff5fe1ce72eec025769068cfc4_640_wx_fmt=png&wxfrom=5&wx_lazy=1&wx_co=1.png

在排序中的stack和visited和sorted过程如下：

只要有子方法，就一个个地入栈

addcf422462c924d668b62c383d6118a_640_wx_fmt=png&wxfrom=5&wx_lazy=1&wx_co=1.png

到达method7发现没有子方法，那么弹出并加入visited和sorted

49505cf231ab73663ec7022d1d1fbb33_640_wx_fmt=png&wxfrom=5&wx_lazy=1&wx_co=1.png

回溯上一层，method3还有一个method8子方法，压栈

7eabe8aa21c0a0d6bf5e8425fd52e152_640_wx_fmt=png&wxfrom=5&wx_lazy=1&wx_co=1.png

method8没有子方法，回溯上一层method3也没有，都弹出并进入右侧

a7f60b60ea013a37375bf803d4e91203_640_wx_fmt=png&wxfrom=5&wx_lazy=1&wx_co=1.png

到达method6，有子方法，压栈，找到method6下的method1，压栈，注意这里是Set结构不重复，所以压了等于没压

da671ec3b12e03754bd672772441fa15_640_wx_fmt=png&wxfrom=5&wx_lazy=1&wx_co=1.png

回溯后method6和method2都没有子方法了，弹出并进入右边

8511983c45fd3de923796e13e077cab6_640_wx_fmt=png&wxfrom=5&wx_lazy=1&wx_co=1.png

往后执行遇到method1的两个子方法method3和method4，由于method3已在visited，直接return，把method4压栈。然后method4没有子方法弹栈，最后剩下的method1也没有子方法，弹栈

641bb164d294cc8a059b7a01c22be5f2_640_wx_fmt=png&wxfrom=5&wx_lazy=1&wx_co=1.png

最终得到的排序结果就是7836241，达到了最末端在最开始的效果

深入分析GadgetInspector核心代码（三）