Java 反序列化工具 gadgetinspector 初窺

作者：Longofo@知道創宇404實驗室
時間：2019年9月4日
英文版：http://www.bjnorthway.com/1046/

起因

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

關于這個工具

這個工具不是用來尋找漏洞，而是利用已知的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	java/lang/Object	com/sun/deploy/jardiff/JarDiffConstants,com/sun/deploy/jardiff/Patcher	false	newBytes!2![B
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

第一個類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	()Ljava/nio/charset/CharsetEncoder;	false
sun/nio/cs/ext/Big5_HKSCS$Decoder	\<init>	(Ljava/nio/charset/Charset;Lsun/nio/cs/ext/Big5_HKSCS$1;)V	false

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：

類	直接父類+間接父類
com/sun/javaws/OperaPreferences $PreferenceSection$ PreferenceEntryIterator	java/lang/Object、java/util/Iterator
com/sun/java/swing/plaf/windows/WindowsLookAndFeel$XPValue	java/lang/Object、javax/swing/UIDefaults$ActiveValue

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：

類名	方法名	方法描述	污點
java/util/Collections$CheckedNavigableSet	tailSet	(Ljava/lang/Object;)Ljava/util/NavigableSet;	0,1
java/awt/RenderingHints	put	(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;	0,1,2

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：

父方法類名	父方法	父方法描述	子方法類名	子方法子	方法描述	父方法第幾參	參數對象的哪個field被傳遞	子方法第幾參
java/io/PrintStream	write	(Ljava/lang/String;)V	java/io/OutputStream	flush	()V	0	out	0
javafx/scene/shape/Shape	setSmooth	(Z)V	javafx/scene/shape/Shape	smoothProperty	()Ljavafx/beans/property/BooleanProperty;	0		0

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中:

類	方法	方法描述	污染參數
java/awt/color/ICC_Profile	finalize	()V	0
java/lang/Enum	readObject	(Ljava/io/ObjectInputStream;)V	1

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參

樣例分析

現在根據作者的樣例寫個具體的demo實例來測試下上面這些步驟。

demo如下:

IFn.java:
    package com.demo.ifn;

    import java.io.IOException;

    public interface IFn {
        public Object invokeCall(Object arg) throws IOException;
    }

FnEval.java
    package com.demo.ifn;

    import java.io.IOException;
    import java.io.Serializable;

    public class FnEval implements IFn, Serializable {
        public FnEval() {
        }

        public Object invokeCall(Object arg) throws IOException {
            return Runtime.getRuntime().exec((String) arg);
        }
    }

FnConstant.java:
    package com.demo.ifn;

    import java.io.Serializable;

    public class FnConstant implements IFn , Serializable {
        private Object value;

        public FnConstant(Object value) {
            this.value = value;
        }

        public Object invokeCall(Object arg) {
            return value;
        }
    }

FnCompose.java:
    package com.demo.ifn;

    import java.io.IOException;
    import java.io.Serializable;

    public class FnCompose implements IFn, Serializable {
        private IFn f1, f2;

        public FnCompose(IFn f1, IFn f2) {
            this.f1 = f1;
            this.f2 = f2;
        }

        public Object invokeCall(Object arg) throws IOException {
            return f2.invokeCall(f1.invokeCall(arg));
        }
    }

TestDemo.java:
    package com.demo.ifn;

    public class TestDemo {
        //測試拓撲排序的正確性
        private String test;

        public String pMethod(String arg){
            String vul = cMethod(arg);
            return vul;
        }

        public String cMethod(String arg){
            return arg.toUpperCase();
        }
    }

AbstractTableModel.java:
    package com.demo.model;

    import com.demo.ifn.IFn;

    import java.io.IOException;
    import java.io.Serializable;
    import java.util.HashMap;

    public class AbstractTableModel implements Serializable {
        private HashMap<String, IFn> __clojureFnMap;

        public AbstractTableModel(HashMap<String, IFn> clojureFnMap) {
            this.__clojureFnMap = clojureFnMap;
        }

        public int hashCode() {
            IFn f = __clojureFnMap.get("hashCode");
            try {
                f.invokeCall(this);
            } catch (IOException e) {
                e.printStackTrace();
            }
            return this.__clojureFnMap.hashCode() + 1;
        }
    }

注：下面截圖中數據的順序做了調換，同時數據也只給出com/demo中的數據

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

classes.dat:

methods.dat:

Step2 生成passthrough數據流

passthrough.dat:

可以看到IFn的子類中只有FnConstant的invokeCall在passthrough數據流中，因為其他幾個在靜態分析中無法判斷返回值與參數的關系。同時TestDemo的cMethod與pMethod都在passthrough數據流中，這也說明了拓撲排序那一步的必要性和正確性。

Step3 枚舉passthrough調用圖

callgraph.dat:

Step4 搜索可用的source

sources.dat:

Step5 搜索生成調用鏈

在gadget-chains.txt中找到了如下鏈：

com/demo/model/AbstractTableModel.hashCode()I (0)
  com/demo/ifn/FnEval.invokeCall(Ljava/lang/Object;)Ljava/lang/Object; (1)
  java/lang/Runtime.exec(Ljava/lang/String;)Ljava/lang/Process; (1)

可以看到選擇的確實是找了一條最短的路徑，并沒有經過FnCompose、FnConstant路徑。

環路造成路徑爆炸

上面流程分析第五步中說到，如果去掉已訪問過節點的判斷會怎么樣呢，能不能生成經過FnCompose、FnConstant的調用鏈呢？

陷入了爆炸狀態，Search space無限增加，其中必定存在環路。作者使用的策略是訪問過的節點就不再訪問了，這樣解決的環路問題，但是丟失了其他鏈。

比如上面的FnCompose類：

public class Fncompose implements IFn{
    private IFn f1,f2;
    public Object invoke(Object arg){
        return f2.invoke(f1.invoke(arg));
    }
}

由于IFn是接口，所以在調用鏈生成中會查找是它的子類，假如f1,f2都是FnCompose類的對象，這樣形成了環路。

隱式調用

測試隱式調用看工具能否發現，將FnEval.java做一些修改：

FnEval.java
    package com.demo.ifn;

    import java.io.IOException;
    import java.io.Serializable;

    public class FnEval implements IFn, Serializable {
        private String cmd;

        public FnEval() {
        }

        @Override
        public String toString() {
            try {
                Runtime.getRuntime().exec(this.cmd);
            } catch (IOException e) {
                e.printStackTrace();
            }
            return "FnEval{}";
        }

        public Object invokeCall(Object arg) throws IOException {
            this.cmd = (String) arg;
            return this + " test";
        }
    }

結果：

com/demo/model/AbstractTableModel.hashCode()I (0)
  com/demo/ifn/FnEval.invokeCall(Ljava/lang/Object;)Ljava/lang/Object; (0)
  java/lang/StringBuilder.append(Ljava/lang/Object;)Ljava/lang/StringBuilder; (1)
  java/lang/String.valueOf(Ljava/lang/Object;)Ljava/lang/String; (0)
  com/demo/ifn/FnEval.toString()Ljava/lang/String; (0)
  java/lang/Runtime.exec(Ljava/lang/String;)Ljava/lang/Process; (1)

隱式調用了tostring方法，說明在字節碼分析中做了查找隱式調用這一步。

不遵循反射調用

在github的工具說明中，作者也說到了在靜態分析中這個工具的盲點，像下面這中FnEval.class.getMethod("exec", String.class).invoke(null, arg)寫法是不遵循反射調用的，將FnEval.java修改：

FnEval.java
    package com.demo.ifn;

import java.io.IOException;
import java.io.Serializable;
import java.lang.reflect.InvocationTargetException;

public class FnEval implements IFn, Serializable {

    public FnEval() {
    }

    public static void exec(String arg) throws IOException {
        Runtime.getRuntime().exec(arg);
    }

    public Object invokeCall(Object arg) throws IOException {
        try {
            return FnEval.class.getMethod("exec", String.class).invoke(null, arg);
        } catch (NoSuchMethodException e) {
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        } catch (InvocationTargetException e) {
            e.printStackTrace();
        }
        return null;
    }
}

經過測試，確實沒有發現。但是將FnEval.class.getMethod("exec", String.class).invoke(null, arg)改為this.getClass().getMethod("exec", String.class).invoke(null, arg)這種寫法卻是可以發現的。

特殊語法

測試一下比較特殊的語法呢，比如lambda語法？將FnEval.java做一些修改：

FnEval.java:
    package com.demo.ifn;

    import java.io.IOException;
    import java.io.Serializable;

    public class FnEval implements IFn, Serializable {

        public FnEval() {
        }

        interface ExecCmd {
            public Object exec(String cmd) throws IOException;
        }

        public Object invokeCall(Object arg) throws IOException {
            ExecCmd execCmd = cmd -> {
                return Runtime.getRuntime().exec(cmd);
            };
            return execCmd.exec((String) arg);
        }
    }

經過測試，沒有檢測到這條利用鏈。說明目前語法分析那一塊還沒有對特殊語法分析。

匿名內部類

測試匿名內部類，將FnEval.java做一些修改：

FnEval.java:
    package com.demo.ifn;

    import java.io.IOException;
    import java.io.Serializable;

    public class FnEval implements IFn, Serializable {

        public FnEval() {
        }

        interface ExecCmd {
            public Object exec(String cmd) throws IOException;
        }

        public Object callExec(ExecCmd execCmd, String cmd) throws IOException {
            return execCmd.exec(cmd);
        }

        public Object invokeCall(Object arg) throws IOException {
            return callExec(new ExecCmd() {
                @Override
                public Object exec(String cmd) throws IOException {
                    return Runtime.getRuntime().exec(cmd);
                }
            }, (String) arg);
        }
    }

經過測試，沒有檢測到這條利用鏈。說明目前語法分析那一塊還沒有對匿名內部類的分析。

sink->source?

既然能source->sink，那么能不能sink->source呢？因為搜索source->sink時，source和sink都是已知的，如果搜索sink->source時，sink與soure也是已知的，那么source->sink與sink->source好像沒有什么區別？如果能將source總結為參數可控的一類特征，那么sink->source這種方式是一種非常好的方式，不僅能用在反序列化漏洞中，還能用在其他漏洞中（例如模板注入）。但是這里也還有一些問題，比如反序列化是將this以及類的屬性都當作了0參，因為反序列化時這些都是可控的，但是在其他漏洞中這些就不一定可控了。

目前還不知道具體如何實現以及會有哪些問題，暫時先不寫。

缺陷

目前還沒有做過大量測試，只是從宏觀層面分析了這個工具的大致原理。結合平安集團分析文章以及上面的測試目前可以總結出一下幾個缺點（不止這些缺陷）：

callgraph生成不完整
調用鏈搜索結果不完整，這是由于查找策略導致的
一些特殊語法、匿名內部類還不支持
...

設想與改進

對以上幾個缺陷進行改進
結合已知的利用鏈(如ysoserial等)不斷測試
盡可能列出所有鏈并結合人工篩選判斷，而作者使用的策略是只要經過這個節點有一條鏈，其他鏈經過這個節點時就不再繼續尋找下去。主要解決的就是最后那個調用鏈環路問題，目前看到幾種方式：
DFS+最大深度限制
繼續使用BFS，人工檢查生成的調用鏈，把無效的callgraph去掉，重復運行
調用鏈緩存（這一個暫時還沒明白具體怎么解決環路的，只是看到了這個方法）

我的想法是在每條鏈中維持一個黑名單，每次都檢查是否出現了環路，如果在這條鏈中出現了環路，將造成環路的節點加入黑名單，繼續使其走下去。當然雖然沒有了環，也能會出現路徑無限增長的情況，所以還是需要加入路徑長度限制。

嘗試sink->source的實現
多線程同時搜索多條利用鏈加快速度
...

最后

在原理分析的時候，忽略了字節碼分析的細節，有的地方只是暫時猜測與測試得出的結果，所以可能存在一些錯誤。字節碼分析那一塊是很重要的一環，它對污點的判斷、污點的傳遞調用等起著很重要的作用，如果這些部分出現了問題，整個搜索過程就會出現問題。由于ASM框架對使用人員要求較高，所以需要要掌握JVM相關的知識才能較好使用ASM框架，所以接下來的就是開始學習JVM相關的東西。這篇文章只是從宏觀層面分析這個工具的原理，也算是給自己增加些信心，至少明白這個工具不是無法理解和無法改進的，同時后面再接觸這個工具進行改進時也會間隔一段時間，回顧起來也方便，其他人如果對這個工具感興趣也可以參考。等以后熟悉并能操縱Java字節碼了，在回頭來更新這篇文章并改正可能有錯誤的地方。

如果這些設想與改進真的實現并且進行了驗證，那么這個工具真的是一個得力幫手。但是這些東西要實現還有較長的一段路要走，還沒開始實現就預想到了那么多問題，在實現的時候會遇到更多問題。不過好在有一個大致的方向了，接下來就是對各個環節逐一解決了。

參考

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

Paper 本文由 Seebug Paper 發布，如需轉載請注明來源。本文地址：http://www.bjnorthway.com/1034/

Paper - 安全技術精粹

Java 反序列化工具 gadgetinspector 初窺

目錄

起因

關于這個工具

序列化與反序列化

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

控制數據類型=>控制代碼

魔術方法

gadgetinspector工作流程

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

Step2 生成passthrough數據流

Step3 枚舉passthrough調用圖

Step4 搜索可用的source

Step5 搜索生成調用鏈

樣例分析

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

Step2 生成passthrough數據流

Step3 枚舉passthrough調用圖

Step4 搜索可用的source

Step5 搜索生成調用鏈

環路造成路徑爆炸

隱式調用

不遵循反射調用

特殊語法

匿名內部類

sink->source?

缺陷

設想與改進

最后

參考

暫無評論