Java 反序列化工具 gadgetinspector 初窺 （上）

• 2019 年 10 月 5 日
• 筆記

作者：Longofo@知道創宇404實驗室 時間：2019年9月4日

起因

一開始是聽@Badcode師傅說的這個工具，在Black Hat 2018的一個議題提出來的。這是一個基於位元組碼靜態分析的、利用已知技巧自動查找從source到sink的反序列化利用鏈工具。看了幾遍作者在Black Hat上的演講影片[1]與PPT[2]，想從作者的演講與PPT中獲取更多關於這個工具的原理性的東西，可是有些地方真的很費解。不過作者開源了這個工具[3]，但沒有給出詳細的說明文檔，對這個工具的分析文章也很少，看到一篇平安集團對這個工具的分析，從文中描述來看，他們對這個工具應該有一定的認識並做了一些改進，但是在文章中對某些細節沒有做過多的闡釋。後面嘗試了調試這個工具，大致理清了這個工具的工作原理，下面是對這個工具的分析過程，以及對未來工作與改進的設想。

關於這個工具

•這個工具不是用來尋找漏洞，而是利用已知的source->…->sink鏈或其相似特徵發現分支利用鏈或新的利用鏈。•這個工具是在整個應用的classpath中尋找利用鏈。•這個工具進行了一些合理的預估風險判斷（污點判斷、污點傳遞等）。•這個工具會產生誤報不是漏報（其實這裡還是會漏報，這是作者使用的策略決定的，在後面的分析中可以看到）。•這個工具是基於位元組碼分析的，對於Java應用來說，很多時候我們並沒有源碼，而只有War包、Jar包或class文件。•這個工具不會生成能直接利用的Payload，具體的利用構造還需要人工參與。

序列化與反序列化

序列化（Serialization）是將對象的狀態資訊轉化為可以存儲或者傳輸形式的過程，轉化後的資訊可以存儲在磁碟上，在網路傳輸過程中，可以是位元組、XML、JSON等格式；而將位元組、XML、JSON等格式的資訊還原成對象這個相反的過程稱為反序列化。

在JAVA中，對象的序列化和反序列化被廣泛的應用到RMI（遠程方法調用）及網路傳輸中。

Java 中的序列化與反序列化庫

•JDK(ObjectInputStream)•XStream(XML,JSON•Jackson(XML,JSON)•Genson(JSON)•JSON-IO(JSON)•FlexSON(JSON)•Fastjson(JSON)•…

不同的反序列化庫在反序列化不同的類時有不同的行為、被反序列化類的不同"魔術方法"會被自動調用，這些被自動調用的方法就能夠作為反序列化的入口點(source)。如果這些被自動調用的方法又調用了其他子方法，那麼在調用鏈中某一個子方法也可以作為source，就相當於已知了調用鏈的前部分，從某個子方法開始尋找不同的分支。通過方法的層層調用，可能到達某些危險的方法(sink)。

•ObjectInputStream

例如某個類實現了Serializable介面，ObjectInputStream.readobject在反序列化類得到其對象時會自動查找這個類的readObject、readResolve等方法並調用。

例如某個類實現了Externalizable介面，ObjectInputStream.readobject在反序列化類得到其對象時會自動查找這個類的readExternal等方法並調用。

•Jackson

ObjectMapper.readValue 在反序列化類得到其對象時，會自動查找反序列化類的無參構造方法、包含一個基礎類型參數的構造方法、屬性的setter、屬性的getter等方法並調用。

•…

在後面的分析中，都使用JDK自帶的ObjectInputStream作為樣例。

控制數據類型=>控制程式碼

作者說，在反序列化漏洞中，如果控制了數據類型，我們就控制了程式碼。這是什麼意思呢？按我的理解，寫了下面的一個例子：

public class TestDeserialization {        interface Animal {          public void eat();      }        public static class Cat implements Animal,Serializable {          @Override          public void eat() {              System.out.println("cat eat fish");          }      }        public static class Dog implements Animal,Serializable {          @Override          public void eat() {              try {                  Runtime.getRuntime().exec("calc");              } catch (IOException e) {                  e.printStackTrace();              }              System.out.println("dog eat bone");          }      }        public static class Person implements Serializable {          private Animal pet;            public Person(Animal pet){              this.pet = pet;          }            private void readObject(java.io.ObjectInputStream stream)                  throws IOException, ClassNotFoundException {              pet = (Animal) stream.readObject();              pet.eat();          }      }        public static void GeneratePayload(Object instance, String file)              throws Exception {          //將構造好的payload序列化後寫入文件中          File f = new File(file);          ObjectOutputStream out = new ObjectOutputStream(new FileOutputStream(f));          out.writeObject(instance);          out.flush();          out.close();      }        public static void payloadTest(String file) throws Exception {          //讀取寫入的payload，並進行反序列化          ObjectInputStream in = new ObjectInputStream(new FileInputStream(file));          Object obj = in.readObject();          System.out.println(obj);          in.close();      }        public static void main(String[] args) throws Exception {          Animal animal = new Dog();          Person person = new Person(animal);          GeneratePayload(person,"test.ser");          payloadTest("test.ser");    //        Animal animal = new Cat();  //        Person person = new Person(animal);  //        GeneratePayload(person,"test.ser");  //        payloadTest("test.ser");      }  }

為了方便我把所有類寫在一個類中進行測試。在Person類中，有一個Animal類的屬性pet，它是Cat和Dog的介面。在序列化時，我們能夠控制Person的pet具體是Cat對象或者Dog對象，因此在反序列化時，在readObject中pet.eat()具體的走向就不一樣了。如果是pet是Cat類對象，就不會走到執行有害程式碼Runtime.getRuntime().exec("calc");這一步，但是如果pet是Dog類的對象，就會走到有害程式碼。

即使有時候類屬性在聲明時已經為它賦值了某個具體的對象，但是在Java中通過反射等方式依然能修改。如下：

public class TestDeserialization {        interface Animal {          public void eat();      }        public static class Cat implements Animal, Serializable {          @Override          public void eat() {              System.out.println("cat eat fish");          }      }        public static class Dog implements Animal, Serializable {          @Override          public void eat() {              try {                  Runtime.getRuntime().exec("calc");              } catch (IOException e) {                  e.printStackTrace();              }              System.out.println("dog eat bone");          }      }        public static class Person implements Serializable {          private Animal pet = new Cat();            private void readObject(java.io.ObjectInputStream stream)                  throws IOException, ClassNotFoundException {              pet = (Animal) stream.readObject();              pet.eat();          }      }        public static void GeneratePayload(Object instance, String file)              throws Exception {          //將構造好的payload序列化後寫入文件中          File f = new File(file);          ObjectOutputStream out = new ObjectOutputStream(new FileOutputStream(f));          out.writeObject(instance);          out.flush();          out.close();      }        public static void payloadTest(String file) throws Exception {          //讀取寫入的payload，並進行反序列化          ObjectInputStream in = new ObjectInputStream(new FileInputStream(file));          Object obj = in.readObject();          System.out.println(obj);          in.close();      }        public static void main(String[] args) throws Exception {          Animal animal = new Dog();          Person person = new Person();            //通過反射修改私有屬性          Field field = person.getClass().getDeclaredField("pet");          field.setAccessible(true);          field.set(person, animal);            GeneratePayload(person, "test.ser");          payloadTest("test.ser");      }  }

在Person類中，不能通過構造器或setter方法或其他方式對pet賦值，屬性在聲明時已經被定義為Cat類的對象，但是通過反射能將pet修改為Dog類的對象，因此在反序列化時依然會走到有害程式碼處。

這只是我自己對作者"控制了數據類型，就控制了程式碼"的理解，在Java反序列化漏洞中，很多時候是利用到了Java的多態特性來控制程式碼走向最後達到惡意執行目的。

魔術方法

在上面的例子中，能看到在反序列化時沒有調用Person的readobject方法，它是ObjectInputStream在反序列化對象時自動調用的。作者將在反序列化中會自動調用的方法稱為"魔術方法"。

使用ObjectInputStream反序列化時幾個常見的魔術方法：

•Object.readObject() •Object.readResolve()•Object.finalize()•…

一些可序列化的JDK類實現了上面這些方法並且還自動調用了其他方法（可以作為已知的入口點）：

•HashMap

•Object.hashCode() •Object.equals()

•PriorityQueue •Comparator.compare() •Comparable.CompareTo()

•…

一些sink：

•Runtime.exec()，這種最為簡單直接，即直接在目標環境中執行命令•Method.invoke()，這種需要適當地選擇方法和參數，通過反射執行Java方法•RMI/JNDI/JRMP等，通過引用遠程對象，間接實現任意程式碼執行的效果•…

作者給出了一個從Magic Methods(source)->Gadget Chains->Runtime.exec(sink)的例子：

上面的HashMap實現了readObject這個"魔術方法"，並且調用了hashCode方法。某些類為了比較對象之間是否相等會實現equals方法（一般是equals和hashCode方法同時實現）。從圖中可以看到AbstractTableModel$ff19274a正好實現了hashCode方法，其中又調用了f.invoke方法，f是IFn對象，並且f能通過屬性__clojureFnMap獲取到。IFn是一個介面，上面說到，如果控制了數據類型，就控制了程式碼走向。所以如果我們在序列化時，在__clojureFnMap放置IFn介面的實現類FnCompose的一個對象，那麼就能控制f.invoke走FnCompose.invoke方法，接著控制FnCompose.invoke中的f1、f2為FnConstant就能到達FnEval.invoke了（關於AbstractTableModel$ff19274a.hashcode中的f.invoke具體選擇IFn的哪個實現類，根據後面對這個工具的測試以及對決策原理的分析，廣度優先會選擇短的路徑，也就是選擇了FnEval.invoke，所以這也是為什麼要人為參與，在後面的樣例分析中也可以看到）。

有了這條鏈，只需要找到觸發這個鏈的漏洞點就行了。Payload使用JSON格式表示如下：

{  "@class":"java.util.HashMap",  "members":[  2,          {  "@class":"AbstractTableModel$ff19274a",  "__clojureFnMap":{  "hashcode":{  "@class":"FnCompose",  "f1":{"@class","FnConstant",value:"calc"},  "f2":{"@class":"FnEval"}                  }              }          }      ]  }

gadgetinspector 工作流程

如作者所說，正好使用了五個步驟：

// 枚舉全部類以及類的所有方法  if (!Files.exists(Paths.get("classes.dat")) || !Files.exists(Paths.get("methods.dat"))                  || !Files.exists(Paths.get("inheritanceMap.dat"))) {              LOGGER.info("Running method discovery...");              MethodDiscovery methodDiscovery = new MethodDiscovery();              methodDiscovery.discover(classResourceEnumerator);              methodDiscovery.save();          }  //生成passthrough數據流  if (!Files.exists(Paths.get("passthrough.dat"))) {              LOGGER.info("Analyzing methods for passthrough dataflow...");              PassthroughDiscovery passthroughDiscovery = new PassthroughDiscovery();              passthroughDiscovery.discover(classResourceEnumerator, config);              passthroughDiscovery.save();          }  //生成passthrough調用圖  if (!Files.exists(Paths.get("callgraph.dat"))) {              LOGGER.info("Analyzing methods in order to build a call graph...");              CallGraphDiscovery callGraphDiscovery = new CallGraphDiscovery();              callGraphDiscovery.discover(classResourceEnumerator, config);              callGraphDiscovery.save();          }  //搜索可用的source  if (!Files.exists(Paths.get("sources.dat"))) {              LOGGER.info("Discovering gadget chain source methods...");              SourceDiscovery sourceDiscovery = config.getSourceDiscovery();              sourceDiscovery.discover();              sourceDiscovery.save();          }  //搜索生成調用鏈          {              LOGGER.info("Searching call graph for gadget chains...");              GadgetChainDiscovery gadgetChainDiscovery = new GadgetChainDiscovery(config);              gadgetChainDiscovery.discover();          }

Step1 枚舉全部類以及每個類的所有方法

要進行調用鏈的搜索，首先得有所有類及所有類方法的相關資訊：

public class MethodDiscovery {    private static final Logger LOGGER = LoggerFactory.getLogger(MethodDiscovery.class);    private final List<ClassReference> discoveredClasses = new ArrayList<>();//保存所有類資訊  private final List<MethodReference> discoveredMethods = new ArrayList<>();//保存所有方法資訊      ...      ...  public void discover(final ClassResourceEnumerator classResourceEnumerator) throws Exception {  //classResourceEnumerator.getAllClasses()獲取了運行時的所有類(JDK rt.jar)以及要搜索應用中的所有類  for (ClassResourceEnumerator.ClassResource classResource : classResourceEnumerator.getAllClasses()) {  try (InputStream in = classResource.getInputStream()) {                  ClassReader cr = new ClassReader(in);  try {                      cr.accept(new MethodDiscoveryClassVisitor(), ClassReader.EXPAND_FRAMES);//通過ASM框架操作位元組碼並將類資訊保存到this.discoveredClasses，將方法資訊保存到discoveredMethods                  } catch (Exception e) {                      LOGGER.error("Exception analyzing: " + classResource.getName(), e);                  }              }          }      }      ...      ...  public void save() throws IOException {          DataLoader.saveData(Paths.get("classes.dat"), new ClassReference.Factory(), discoveredClasses);//將類資訊保存到classes.dat          DataLoader.saveData(Paths.get("methods.dat"), new MethodReference.Factory(), discoveredMethods);//將方法資訊保存到methods.dat            Map<ClassReference.Handle, ClassReference> classMap = new HashMap<>();  for (ClassReference clazz : discoveredClasses) {              classMap.put(clazz.getHandle(), clazz);          }          InheritanceDeriver.derive(classMap).save();//查找所有繼承關係並保存      }  }

來看下classes.dat、methods.dat分別長什麼樣子：

•classes.dat

找了兩個比較有特徵的

第一個類com/sun/deploy/jardiff/JarDiffPatcher：

和上面的表格資訊對應一下，是吻合的

•類名：com/sun/deploy/jardiff/JarDiffPatcher•父類：java/lang/Object，如果一類沒有顯式繼承其他類，默認隱式繼承java/lang/Object，並且java中不允許多繼承，所以每個類只有一個父類•所有介面：com/sun/deploy/jardiff/JarDiffConstants、com/sun/deploy/jardiff/Patcher•是否是介面：false•成員：newBytes!2![B，newBytes成員，Byte類型。為什麼沒有將static/final類型的成員加進去呢？這裡還沒有研究如何操作位元組碼，所以作者這裡的判斷實現部分暫且跳過。不過猜測應該是這種類型的變數並不能成為污點所以忽略了

第二個類com/sun/corba/se/impl/presentation/rmi/InvocationHandlerFactoryImpl$CustomCompositeInvocationHandlerImpl：

和上面的表格資訊對應一下，也是吻合的

•類名：com/sun/corba/se/impl/presentation/rmi/InvocationHandlerFactoryImpl$CustomCompositeInvocationHandlerImpl，是一個內部類•父類：com/sun/corba/se/spi/orbutil/proxy/CompositeInvocationHandlerImpl•所有介面：com/sun/corba/se/spi/orbutil/proxy/LinkedInvocationHandler,java/io/Serializable•是否是介面：false•成員：stub!130!com/sun/corba/se/spi/presentation/rmi/DynamicStub!this$0!4112!com/sun/corba/se/impl/presentation/rmi/InvocationHandlerFactoryImpl，!*!這裡可以暫時理解為分割符，有一個成員stub，類型com/sun/corba/se/spi/presentation/rmi/DynamicStub。因為是內部類，所以多了個this成員，這個this指向的是外部類

•methods.dat

同樣找幾個比較有特徵的

sun/nio/cs/ext/Big5#newEncoder：

•類名：sun/nio/cs/ext/Big5 •方法名：newEncoder •方法描述資訊：()Ljava/nio/charset/CharsetEncoder; 無參，返回java/nio/charset/CharsetEncoder對象 •是否是靜態方法：false

sun/nio/cs/ext/Big5_HKSCS$Decoder#<init>：

•類名：sun/nio/cs/ext/Big5_HKSCS$Decoder•方法名：<init>•方法描述資訊：(Ljava/nio/charset/Charset;Lsun/nio/cs/ext/Big5_HKSCS$1;)V 參數1是java/nio/charset/Charset類型，參數2是sun/nio/cs/ext/Big5_HKSCS$1類型，返回值void•是否是靜態方法：false

繼承關係的生成：

繼承關係在後面用來判斷一個類是否能被某個庫序列化、以及搜索子類方法實現等會用到。

public class InheritanceDeriver {      private static final Logger LOGGER = LoggerFactory.getLogger(InheritanceDeriver.class);        public static InheritanceMap derive(Map<ClassReference.Handle, ClassReference> classMap) {          LOGGER.debug("Calculating inheritance for " + (classMap.size()) + " classes...");          Map<ClassReference.Handle, Set<ClassReference.Handle>> implicitInheritance = new HashMap<>();          for (ClassReference classReference : classMap.values()) {              if (implicitInheritance.containsKey(classReference.getHandle())) {                  throw new IllegalStateException("Already derived implicit classes for " + classReference.getName());              }              Set<ClassReference.Handle> allParents = new HashSet<>();                getAllParents(classReference, classMap, allParents);//獲取當前類的所有父類                implicitInheritance.put(classReference.getHandle(), allParents);          }          return new InheritanceMap(implicitInheritance);      }      ...      ...      private static void getAllParents(ClassReference classReference, Map<ClassReference.Handle, ClassReference> classMap, Set<ClassReference.Handle> allParents) {          Set<ClassReference.Handle> parents = new HashSet<>();          if (classReference.getSuperClass() != null) {              parents.add(new ClassReference.Handle(classReference.getSuperClass()));//父類          }          for (String iface : classReference.getInterfaces()) {              parents.add(new ClassReference.Handle(iface));//介面類          }            for (ClassReference.Handle immediateParent : parents) {              //獲取間接父類，以及遞歸獲取間接父類的父類              ClassReference parentClassReference = classMap.get(immediateParent);              if (parentClassReference == null) {                  LOGGER.debug("No class id for " + immediateParent.getName());                  continue;              }              allParents.add(parentClassReference.getHandle());              getAllParents(parentClassReference, classMap, allParents);          }      }      ...      ...  }

這一步的結果保存到了inheritanceMap.dat：

Step2 生成passthrough 數據流

這裡的passthrough數據流指的是每個方法的返回結果與方法參數的關係，這一步生成的數據會在生成passthrough調用圖時用到。

以作者給出的demo為例，先從宏觀層面判斷下：

FnConstant.invoke返回值與參數this(參數0，因為序列化時類的所有成員我們都能控制，所以所有成員變數都視為0參)、arg(參數1)的關係：

•與this的關係：返回了this.value，即與0參有關係•與arg的關係：返回值與arg沒有任何關係，即與1參沒有關係•結論就是FnConstant.invoke與參數0有關，表示為FnConstant.invoke()->0

Fndefault.invoke返回值與參數this(參數0)、arg(參數1)的關係：

•與this的關係：返回條件的第二個分支與this.f有關係，即與0參有關係•與arg的關係：返回條件的第一個分支與arg有關係，即與1參有關係•結論就是FnConstant.invoke與0參，1參都有關係，表示為Fndefault.invoke()->0、Fndefault.invoke()->1

在這一步中，gadgetinspector是利用ASM來進行方法位元組碼的分析，主要邏輯是在類PassthroughDiscovery和TaintTrackingMethodVisitor中。特別是TaintTrackingMethodVisitor，它通過標記追蹤JVM虛擬機在執行方法時的stack和localvar，並最終得到返回結果是否可以被參數標記污染。

核心實現程式碼（TaintTrackingMethodVisitor涉及到位元組碼分析，暫時先不看）：

public class PassthroughDiscovery {        private static final Logger LOGGER = LoggerFactory.getLogger(PassthroughDiscovery.class);        private final Map<MethodReference.Handle, Set<MethodReference.Handle>> methodCalls = new HashMap<>();      private Map<MethodReference.Handle, Set<Integer>> passthroughDataflow;        public void discover(final ClassResourceEnumerator classResourceEnumerator, final GIConfig config) throws IOException {          Map<MethodReference.Handle, MethodReference> methodMap = DataLoader.loadMethods();//load之前保存的methods.dat          Map<ClassReference.Handle, ClassReference> classMap = DataLoader.loadClasses();//load之前保存的classes.dat          InheritanceMap inheritanceMap = InheritanceMap.load();//load之前保存的inheritanceMap.dat            Map<String, ClassResourceEnumerator.ClassResource> classResourceByName = discoverMethodCalls(classResourceEnumerator);//查找一個方法中包含的子方法          List<MethodReference.Handle> sortedMethods = topologicallySortMethodCalls();//對所有方法構成的圖執行逆拓撲排序          passthroughDataflow = calculatePassthroughDataflow(classResourceByName, classMap, inheritanceMap, sortedMethods,                  config.getSerializableDecider(methodMap, inheritanceMap));//計算生成passthrough數據流，涉及到位元組碼分析      }      ...      ...      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()));          }            // 對所有方法構成的圖執行逆拓撲排序          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)) {//防止在dfs一條方法調用鏈中進入循環              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);      }  }

拓撲排序

有向無環圖（DAG）才有拓撲排序，非 DAG 圖沒有拓撲排序。當有向無環圖滿足以下條件時：

•每一個頂點出現且只出現一次

•若A在序列中排在B的前面，則在圖中不存在從B到A的路徑

這樣的圖，是一個拓撲排序的圖。樹結構其實可以轉化為拓撲排序，而拓撲排序 不一定能夠轉化為樹。

以上面的拓撲排序圖為例，用一個字典表示圖結構

 graph = {       "a": ["b","d"],       "b": ["c"],       "d": ["e","c"],       "e": ["c"],       "c": [],   }

程式碼實現

graph = {      "a": ["b","d"],      "b": ["c"],      "d": ["e","c"],      "e": ["c"],      "c": [],  }    def TopologicalSort(graph):    degrees = dict((u, 0) for u in graph)    for u in graph:        for v in graph[u]:            degrees[v] += 1    #入度為0的插入隊列    queue = [u for u in graph if degrees[u] == 0]    res = []    while queue:        u = queue.pop()        res.append(u)        for v in graph[u]:            # 移除邊，即將當前元素相關元素的入度-1            degrees[v] -= 1            if degrees[v] == 0:                queue.append(v)    return res    print(TopologicalSort(graph)) # ['a', 'd', 'e', 'b', 'c']

但是在方法的調用中，我們希望最後的結果是c、b、e、d、a，這一步需要逆拓撲排序，正向排序使用的BFS，那麼得到相反結果可以使用DFS。為什麼在方法調用中需要使用逆拓撲排序呢，這與生成passthrough數據流有關。看下面一個例子：

...      public String parentMethod(String arg){          String vul = Obj.childMethod(arg);          return vul;      }  ...

那麼這裡arg與返回值到底有沒有關係呢？假設Obj.childMethod為

...      public String childMethod(String carg){          return carg.toString();      }  ...

由於childMethod的返回值carg與有關，那麼可以判定parentMethod的返回值與參數arg是有關係的。所以如果存在子方法調用並傳遞了父方法參數給子方法時，需要先判斷子方法返回值與子方法參數的關係。因此需要讓子方法的判斷在前面，這就是為什麼要進行逆拓撲排序。

從下圖可以看出outgoingReferences的數據結構為：

{      method1:(method2,method3,method4),        method5:(method1,method6),      ...  }

而這個結構正好適合逆拓撲排序

但是上面說拓撲排序時不能形成環，但是在方法調用中肯定是會存在環的。作者是如何避免的呢？

在上面的dfsTsort實現程式碼中可以看到使用了stack和visitedNodes，stack保證了在進行逆拓撲排序時不會形成環，visitedNodes避免了重複排序。使用如下一個調用圖來演示過程：

從圖中可以看到有環med1->med2->med6->med1，並且有重複的調用med3，嚴格來說並不能進行逆拓撲排序，但是通過stack、visited記錄訪問過的方法，就能實現逆拓撲排序。為了方便解釋把上面的圖用一個樹來表示：

對上圖進行逆拓撲排序（DFS方式）：

從med1開始，先將med1加入stack中，此時stack、visited、sortedmethods狀態如下：

med1還有子方法？有，繼續深度遍歷。將med2放入stack，此時的狀態：

med2有子方法嗎？有，繼續深度遍歷。將med3放入stack，此時的狀態：

med3有子方法嗎？有，繼續深度遍歷。將med7放入stack，此時的狀態：

med7有子方法嗎？沒有，從stack中彈出med7並加入visited和sortedmethods，此時的狀態：

回溯到上一層，med3還有其他子方法嗎？有，med8，將med8放入stack，此時的狀態：

med8還有子方法嗎？沒有，彈出stack，加入visited與sortedmethods，此時的狀態：

回溯到上一層，med3還有其他子方法嗎？沒有了，彈出stack，加入visited與sortedmethods，此時的狀態：

回溯到上一層，med2還有其他子方法嗎？有，med6，將med6加入stack，此時的狀態：

med6還有子方法嗎？有，med1，med1在stack中？不加入，拋棄。此時狀態和上一步一樣

回溯到上一層，med6還有其他子方法嗎？沒有了，彈出stack，加入visited和sortedmethods，此時的狀態：

回溯到上一層，med2還有其他子方法嗎？沒有了，彈出stack，加入visited和sortedmethods，此時的狀態：

回溯到上一層，med1還有其他子方法嗎？有，med3，med3在visited中？在，拋棄。

回溯到上一層，med1還有其他子方法嗎？有，med4，將med4加入stack，此時的狀態：

med4還有其他子方法嗎？沒有，彈出stack，加入visited和sortedmethods中，此時的狀態：

回溯到上一層，med1還有其他子方法嗎？沒有了，彈出stack，加入visited和sortedmethods中，此時的狀態（即最終狀態）：

所以最後的逆拓撲排序結果為：med7、med8、med3、med6、med2、med4、med1。

生成passthrough數據流

在calculatePassthroughDataflow中遍歷了sortedmethods，並通過位元組碼分析，生成了方法返回值與參數關係的passthrough數據流。注意到下面的序列化決定器，作者內置了三種：JDK、Jackson、Xstream，會根據具體的序列化決定器判定決策過程中的類是否符合對應庫的反序列化要求，不符合的就跳過：

•對於JDK(ObjectInputStream)，類是否繼承了Serializable介面•對於Jackson，類是否存在0參構造器•對於Xstream，類名能否作為有效的XML標籤

生成passthrough數據流程式碼：

...      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) {//依次遍歷sortedmethods，並且每個方法的子方法判定總在這個方法之前，這是通過的上面的逆拓撲排序實現的。              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 {                      PassthroughDataflowClassVisitor cv = new PassthroughDataflowClassVisitor(classMap, inheritanceMap,                              passthroughDataflow, serializableDecider, Opcodes.ASM6, method);                      cr.accept(cv, ClassReader.EXPAND_FRAMES);//通過結合classMap、inheritanceMap、已判定出的passthroughDataflow結果、序列化決定器資訊來判定當前method的返回值與參數的關係                      passthroughDataflow.put(method, cv.getReturnTaint());//將判定後的method與有關係的污染點加入passthroughDataflow                  } 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;      }  ...

最後生成了passthrough.dat：

Step3 枚舉 passthrough 調用圖

這一步和上一步類似，gadgetinspector 會再次掃描全部的Java方法，但檢查的不再是參數與返回結果的關係，而是方法的參數與其所調用的子方法的關係，即子方法的參數是否可以被父方法的參數所影響。那麼為什麼要進行上一步的生成passthrough數據流呢？由於這一步的判斷也是在位元組碼分析中，所以這裡只能先進行一些猜測，如下面這個例子：

...      private MyObject obj;        public void parentMethod(Object arg){          ...          TestObject obj1 = new TestObject();          Object obj2 = obj1.childMethod1(arg);          this.obj.childMethod(obj2);          ...      }  ...

如果不進行生成passthrough數據流操作，就無法判斷TestObject.childMethod1的返回值是否會受到參數1的影響，也就無法繼續判斷parentMethod的arg參數與子方法MyObject.childmethod的參數傳遞關係。

作者給出的例子：

AbstractTableModel$ff19274a.hashcode與子方法IFn.invoke：

•AbstractTableModel$ff19274a.hashcode的this(0參)傳遞給了IFn.invoke的1參，表示為0->IFn.invoke()@1• 由於f是通過this.__clojureFnMap(0參)獲取的，而f又為IFn.invoke()的this(0參)，即AbstractTableModel$ff19274a.hashcode的0參傳遞給了IFn.invoke的0參，表示為0->IFn.invoke()@0

FnCompose.invoke與子方法IFn.invoke：

•FnCompose.invoked的arg(1參)傳遞給了IFn.invoke的1參，表示為1->IFn.invoke()@1•f1為FnCompose的屬性(this，0參)，被做為了IFn.invoke的this(0參數)傳遞，表示為0->IFn.invoke()@1•f1.invoke(arg)做為一個整體被當作1參傳遞給了IFn.invoke，由於f1在序列化時我們可以控制具體是IFn的哪個實現類，所以具體調用哪個實現類的invoke也相當於能夠控制，即f1.invoke(arg)這個整體可以視為0參數傳遞給了IFn.invoke的1參(這裡只是進行的簡單猜測，具體實現在位元組碼分析中，可能也體現了作者說的合理的風險判斷吧)，表示為0->IFn.invoke()@1

在這一步中，gadgetinspector也是利用ASM來進行位元組碼的分析，主要邏輯是在類CallGraphDiscovery和ModelGeneratorClassVisitor中。在ModelGeneratorClassVisitor中通過標記追蹤JVM虛擬機在執行方法時的stack和localvar，最終得到方法的參數與其所調用的子方法的參數傳遞關係。

生成passthrough調用圖程式碼（暫時省略ModelGeneratorClassVisitor的實現，涉及到位元組碼分析）：

public class CallGraphDiscovery {      private static final Logger LOGGER = LoggerFactory.getLogger(CallGraphDiscovery.class);        private final Set<GraphCall> discoveredCalls = new HashSet<>();        public void discover(final ClassResourceEnumerator classResourceEnumerator, GIConfig config) throws IOException {          Map<MethodReference.Handle, MethodReference> methodMap = DataLoader.loadMethods();//載入所有方法          Map<ClassReference.Handle, ClassReference> classMap = DataLoader.loadClasses();//載入所有類          InheritanceMap inheritanceMap = InheritanceMap.load();//載入繼承圖          Map<MethodReference.Handle, Set<Integer>> passthroughDataflow = PassthroughDiscovery.load();//載入passthrough數據流            SerializableDecider serializableDecider = config.getSerializableDecider(methodMap, inheritanceMap);//序列化決定器            for (ClassResourceEnumerator.ClassResource classResource : classResourceEnumerator.getAllClasses()) {              try (InputStream in = classResource.getInputStream()) {                  ClassReader cr = new ClassReader(in);                  try {                      cr.accept(new ModelGeneratorClassVisitor(classMap, inheritanceMap, passthroughDataflow, serializableDecider, Opcodes.ASM6),                              ClassReader.EXPAND_FRAMES);//通過結合classMap、inheritanceMap、passthroughDataflow結果、序列化決定器資訊來判定當前method參數與子方法傳遞調用關係                  } catch (Exception e) {                      LOGGER.error("Error analyzing: " + classResource.getName(), e);                  }              }          }      }

最後生成了passthrough.dat：

Step4 搜索可用的 source

這一步會根據已知的反序列化漏洞的入口，檢查所有可以被觸發的方法。例如，在利用鏈中使用代理時，任何可序列化並且是java/lang/reflect/InvocationHandler子類的invoke方法都可以視為source。這裡還會根據具體的反序列化庫決定類是否能被序列化。

搜索可用的source：

public class SimpleSourceDiscovery extends SourceDiscovery {        @Override      public void discover(Map<ClassReference.Handle, ClassReference> classMap,                           Map<MethodReference.Handle, MethodReference> methodMap,                           InheritanceMap inheritanceMap) {            final SerializableDecider serializableDecider = new SimpleSerializableDecider(inheritanceMap);            for (MethodReference.Handle method : methodMap.keySet()) {              if (Boolean.TRUE.equals(serializableDecider.apply(method.getClassReference()))) {                  if (method.getName().equals("finalize") && method.getDesc().equals("()V")) {                      addDiscoveredSource(new Source(method, 0));                  }              }          }            // 如果類實現了readObject，則傳入的ObjectInputStream被認為是污染的          for (MethodReference.Handle method : methodMap.keySet()) {              if (Boolean.TRUE.equals(serializableDecider.apply(method.getClassReference()))) {                  if (method.getName().equals("readObject") && method.getDesc().equals("(Ljava/io/ObjectInputStream;)V")) {                      addDiscoveredSource(new Source(method, 1));                  }              }          }            // 使用代理技巧時，任何擴展了serializable and InvocationHandler的類會受到污染。          for (ClassReference.Handle clazz : classMap.keySet()) {              if (Boolean.TRUE.equals(serializableDecider.apply(clazz))                      && inheritanceMap.isSubclassOf(clazz, new ClassReference.Handle("java/lang/reflect/InvocationHandler"))) {                  MethodReference.Handle method = new MethodReference.Handle(                          clazz, "invoke", "(Ljava/lang/Object;Ljava/lang/reflect/Method;[Ljava/lang/Object;)Ljava/lang/Object;");                    addDiscoveredSource(new Source(method, 0));              }          }            // hashCode（）或equals（）是將對象放入HashMap的標準技巧的可訪問入口點          for (MethodReference.Handle method : methodMap.keySet()) {              if (Boolean.TRUE.equals(serializableDecider.apply(method.getClassReference()))) {                  if (method.getName().equals("hashCode") && method.getDesc().equals("()I")) {                      addDiscoveredSource(new Source(method, 0));                  }                  if (method.getName().equals("equals") && method.getDesc().equals("(Ljava/lang/Object;)Z")) {                      addDiscoveredSource(new Source(method, 0));                      addDiscoveredSource(new Source(method, 1));                  }              }          }            // 使用比較器代理，可以跳轉到任何groovy Closure的call()/doCall()方法，所有的args都被污染          // https://github.com/frohoff/ysoserial/blob/master/src/main/java/ysoserial/payloads/Groovy1.java          for (MethodReference.Handle method : methodMap.keySet()) {              if (Boolean.TRUE.equals(serializableDecider.apply(method.getClassReference()))                      && inheritanceMap.isSubclassOf(method.getClassReference(), new ClassReference.Handle("groovy/lang/Closure"))                      && (method.getName().equals("call") || method.getName().equals("doCall"))) {                    addDiscoveredSource(new Source(method, 0));                  Type[] methodArgs = Type.getArgumentTypes(method.getDesc());                  for (int i = 0; i < methodArgs.length; i++) {                      addDiscoveredSource(new Source(method, i + 1));                  }              }          }      }  ...

這一步的結果會保存在文件sources.dat中:

Step5 搜索生成調用鏈

這一步會遍歷全部的source，並在callgraph.dat中遞歸查找所有可以繼續傳遞污點參數的子方法調用，直至遇到sink中的方法。

搜索生成調用鏈：

public class GadgetChainDiscovery {        private static final Logger LOGGER = LoggerFactory.getLogger(GadgetChainDiscovery.class);        private final GIConfig config;        public GadgetChainDiscovery(GIConfig config) {          this.config = config;      }        public void discover() throws Exception {          Map<MethodReference.Handle, MethodReference> methodMap = DataLoader.loadMethods();          InheritanceMap inheritanceMap = InheritanceMap.load();          Map<MethodReference.Handle, Set<MethodReference.Handle>> methodImplMap = InheritanceDeriver.getAllMethodImplementations(                  inheritanceMap, methodMap);//得到方法的所有子類方法實現（被子類重寫的方法）            final ImplementationFinder implementationFinder = config.getImplementationFinder(                  methodMap, methodImplMap, inheritanceMap);            //將方法的所有子類方法實現保存到methodimpl.dat          try (Writer writer = Files.newBufferedWriter(Paths.get("methodimpl.dat"))) {              for (Map.Entry<MethodReference.Handle, Set<MethodReference.Handle>> entry : methodImplMap.entrySet()) {                  writer.write(entry.getKey().getClassReference().getName());                  writer.write("t");                  writer.write(entry.getKey().getName());                  writer.write("t");                  writer.write(entry.getKey().getDesc());                  writer.write("n");                  for (MethodReference.Handle method : entry.getValue()) {                      writer.write("t");                      writer.write(method.getClassReference().getName());                      writer.write("t");                      writer.write(method.getName());                      writer.write("t");                      writer.write(method.getDesc());                      writer.write("n");                  }              }          }            //方法調用map，key為父方法，value為子方法與父方法參數傳遞關係          Map<MethodReference.Handle, Set<GraphCall>> graphCallMap = new HashMap<>();          for (GraphCall graphCall : DataLoader.loadData(Paths.get("callgraph.dat"), new GraphCall.Factory())) {              MethodReference.Handle caller = graphCall.getCallerMethod();              if (!graphCallMap.containsKey(caller)) {                  Set<GraphCall> graphCalls = new HashSet<>();                  graphCalls.add(graphCall);                  graphCallMap.put(caller, graphCalls);              } else {                  graphCallMap.get(caller).add(graphCall);              }          }            //exploredMethods保存在調用鏈從查找過程中已經訪問過的方法節點，methodsToExplore保存調用鏈          Set<GadgetChainLink> exploredMethods = new HashSet<>();          LinkedList<GadgetChain> methodsToExplore = new LinkedList<>();          //載入所有sources，並將每個source作為每條鏈的第一個節點          for (Source source : DataLoader.loadData(Paths.get("sources.dat"), new Source.Factory())) {              GadgetChainLink srcLink = new GadgetChainLink(source.getSourceMethod(), source.getTaintedArgIndex());              if (exploredMethods.contains(srcLink)) {                  continue;              }              methodsToExplore.add(new GadgetChain(Arrays.asList(srcLink)));              exploredMethods.add(srcLink);          }            long iteration = 0;          Set<GadgetChain> discoveredGadgets = new HashSet<>();          //使用廣度優先搜索所有從source到sink的調用鏈          while (methodsToExplore.size() > 0) {              if ((iteration % 1000) == 0) {                  LOGGER.info("Iteration " + iteration + ", Search space: " + methodsToExplore.size());              }              iteration += 1;                GadgetChain chain = methodsToExplore.pop();//從隊首彈出一條鏈              GadgetChainLink lastLink = chain.links.get(chain.links.size()-1);//取這條鏈最後一個節點                Set<GraphCall> methodCalls = graphCallMap.get(lastLink.method);//獲取當前節點方法所有子方法與當前節點方法參數傳遞關係              if (methodCalls != null) {                  for (GraphCall graphCall : methodCalls) {                      if (graphCall.getCallerArgIndex() != lastLink.taintedArgIndex) {                          //如果當前節點方法的污染參數與當前子方法受父方法參數影響的Index不一致則跳過                          continue;                      }                        Set<MethodReference.Handle> allImpls = implementationFinder.getImplementations(graphCall.getTargetMethod());//獲取子方法所在類的所有子類重寫方法                        for (MethodReference.Handle methodImpl : allImpls) {                          GadgetChainLink newLink = new GadgetChainLink(methodImpl, graphCall.getTargetArgIndex());//新方法節點                          if (exploredMethods.contains(newLink)) {                              //如果新方法已近被訪問過了，則跳過,這裡能減少開銷。但是這一步跳過會使其他鏈/分支鏈經過此節點時，由於已經此節點被訪問過了，鏈會在這裡斷掉。那麼如果這個條件去掉就能實現找到所有鏈了嗎？這裡去掉會遇到環狀問題，造成路徑無限增加...                              continue;                          }                            GadgetChain newChain = new GadgetChain(chain, newLink);//新節點與之前的鏈組成新鏈                          if (isSink(methodImpl, graphCall.getTargetArgIndex(), inheritanceMap)) {//如果到達了sink，則加入discoveredGadgets                              discoveredGadgets.add(newChain);                          } else {                              //新鏈加入隊列                              methodsToExplore.add(newChain);                              //新節點加入已訪問集合                              exploredMethods.add(newLink);                          }                      }                  }              }          }            //保存搜索到的利用鏈到gadget-chains.txt          try (OutputStream outputStream = Files.newOutputStream(Paths.get("gadget-chains.txt"));               Writer writer = new OutputStreamWriter(outputStream, StandardCharsets.UTF_8)) {              for (GadgetChain chain : discoveredGadgets) {                  printGadgetChain(writer, chain);              }          }            LOGGER.info("Found {} gadget chains.", discoveredGadgets.size());      }  ...

作者給出的sink方法：

private boolean isSink(MethodReference.Handle method, int argIndex, InheritanceMap inheritanceMap) {  if (method.getClassReference().getName().equals("java/io/FileInputStream")                  && method.getName().equals("<init>")) {  return true;          }  if (method.getClassReference().getName().equals("java/io/FileOutputStream")                  && method.getName().equals("<init>")) {  return true;          }  if (method.getClassReference().getName().equals("java/nio/file/Files")                  && (method.getName().equals("newInputStream")                  || method.getName().equals("newOutputStream")                  || method.getName().equals("newBufferedReader")                  || method.getName().equals("newBufferedWriter"))) {  return true;          }  if (method.getClassReference().getName().equals("java/lang/Runtime")                  && method.getName().equals("exec")) {  return true;          }  /*          if (method.getClassReference().getName().equals("java/lang/Class")                  && method.getName().equals("forName")) {              return true;          }          if (method.getClassReference().getName().equals("java/lang/Class")                  && method.getName().equals("getMethod")) {              return true;          }          */  // If we can invoke an arbitrary method, that's probably interesting (though this doesn't assert that we  // can control its arguments). Conversely, if we can control the arguments to an invocation but not what  // method is being invoked, we don't mark that as interesting.  if (method.getClassReference().getName().equals("java/lang/reflect/Method")                  && method.getName().equals("invoke") && argIndex == 0) {  return true;          }  if (method.getClassReference().getName().equals("java/net/URLClassLoader")                  && method.getName().equals("newInstance")) {  return true;          }  if (method.getClassReference().getName().equals("java/lang/System")                  && method.getName().equals("exit")) {  return true;          }  if (method.getClassReference().getName().equals("java/lang/Shutdown")                  && method.getName().equals("exit")) {  return true;          }  if (method.getClassReference().getName().equals("java/lang/Runtime")                  && method.getName().equals("exit")) {  return true;          }  if (method.getClassReference().getName().equals("java/nio/file/Files")                  && method.getName().equals("newOutputStream")) {  return true;          }  if (method.getClassReference().getName().equals("java/lang/ProcessBuilder")                  && method.getName().equals("<init>") && argIndex > 0) {  return true;          }  if (inheritanceMap.isSubclassOf(method.getClassReference(), new ClassReference.Handle("java/lang/ClassLoader"))                  && method.getName().equals("<init>")) {  return true;          }  if (method.getClassReference().getName().equals("java/net/URL") && method.getName().equals("openStream")) {  return true;          }  // Some groovy-specific sinks  if (method.getClassReference().getName().equals("org/codehaus/groovy/runtime/InvokerHelper")                  && method.getName().equals("invokeMethod") && argIndex == 1) {  return true;          }  if (inheritanceMap.isSubclassOf(method.getClassReference(), new ClassReference.Handle("groovy/lang/MetaClass"))                  && Arrays.asList("invokeMethod", "invokeConstructor", "invokeStaticMethod").contains(method.getName())) {  return true;          }  return false;      }

對於每個入口節點來說，其全部子方法調用、孫子方法調用等等遞歸下去，就構成了一棵樹。之前的步驟所做的，就相當於生成了這顆樹，而這一步所做的，就是從根節點出發，找到一條通往葉子節點的道路，使得這個葉子節點正好是我們所期望的sink方法。gadgetinspector對樹的遍歷採用的是廣度優先(BFS)，而且對於已經檢查過的節點會直接跳過，這樣減少了運行開銷，避免了環路，但是丟掉了很多其他鏈。

這個過程看起來就像下面這樣：

通過污點的傳遞，最終找到從source->sink的利用鏈

注：targ表示污染參數的index，0->1這樣的表示父方法的0參傳遞給了子方法的1參

參考

•https://i.blackhat.com/us-18/Thu-August-9/us-18-Haken-Automated-Discovery-of-Deserialization-Gadget-Chains.pdf•https://i.blackhat.com/us-18/Thu-August-9/us-18-Haken-Automated-Discovery-of-Deserialization-Gadget-Chains-wp.pdf•https://www.youtube.com/watch?v=wPbW6zQ52w8•https://mp.weixin.qq.com/s/RD90-78I7wRogdYdsB-UOg