作者：Longofo@知道創(chuàng)宇404實(shí)驗(yàn)室?
時間：2019年9月4日
創(chuàng)新互聯(lián)主要從事網(wǎng)站設(shè)計制作、做網(wǎng)站、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)施甸,10余年網(wǎng)站建設(shè)經(jīng)驗(yàn),價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18982081108
一開始是聽@Badcode師傅說的這個工具，在Black Hat 2018的一個議題提出來的。這是一個基于字節(jié)碼靜態(tài)分析的、利用已知技巧自動查找從source到sink的反序列化利用鏈工具。看了幾遍作者在Black Hat上的演講視頻與PPT，想從作者的演講與PPT中獲取更多關(guān)于這個工具的原理性的東西，可是有些地方真的很費(fèi)解。不過作者開源了這個工具，但沒有給出詳細(xì)的說明文檔，對這個工具的分析文章也很少，看到一篇平安集團(tuán)對這個工具的分析，從文中描述來看，他們對這個工具應(yīng)該有一定的認(rèn)識并做了一些改進(jìn)，但是在文章中對某些細(xì)節(jié)沒有做過多的闡釋。后面嘗試了調(diào)試這個工具，大致理清了這個工具的工作原理，下面是對這個工具的分析過程，以及對未來工作與改進(jìn)的設(shè)想。
這個工具不是用來尋找漏洞，而是利用已知的source->...->sink鏈或其相似特征發(fā)現(xiàn)分支利用鏈或新的利用鏈。
這個工具是在整個應(yīng)用的classpath中尋找利用鏈。
這個工具進(jìn)行了一些合理的預(yù)估風(fēng)險判斷（污點(diǎn)判斷、污點(diǎn)傳遞等）。
這個工具會產(chǎn)生誤報不是漏報（其實(shí)這里還是會漏報，這是作者使用的策略決定的，在后面的分析中可以看到）。
這個工具是基于字節(jié)碼分析的，對于Java應(yīng)用來說，很多時候我們并沒有源碼，而只有War包、Jar包或class文件。
這個工具不會生成能直接利用的Payload，具體的利用構(gòu)造還需要人工參與。
序列化（Serialization）是將對象的狀態(tài)信息轉(zhuǎn)化為可以存儲或者傳輸形式的過程，轉(zhuǎn)化后的信息可以存儲在磁盤上，在網(wǎng)絡(luò)傳輸過程中，可以是字節(jié)、XML、JSON等格式；而將字節(jié)、XML、JSON等格式的信息還原成對象這個相反的過程稱為反序列化。
在JAVA中，對象的序列化和反序列化被廣泛的應(yīng)用到RMI（遠(yuǎn)程方法調(diào)用）及網(wǎng)絡(luò)傳輸中。
JDK(ObjectInputStream)
XStream(XML,JSON)
Jackson(XML,JSON)
Genson(JSON)
JSON-IO(JSON)
FlexSON(JSON)
Fastjson(JSON)
...
不同的反序列化庫在反序列化不同的類時有不同的行為、被反序列化類的不同"魔術(shù)方法"會被自動調(diào)用，這些被自動調(diào)用的方法就能夠作為反序列化的入口點(diǎn)(source)。如果這些被自動調(diào)用的方法又調(diào)用了其他子方法，那么在調(diào)用鏈中某一個子方法也可以作為source，就相當(dāng)于已知了調(diào)用鏈的前部分，從某個子方法開始尋找不同的分支。通過方法的層層調(diào)用，可能到達(dá)某些危險的方法(sink)。
ObjectInputStream
例如某個類實(shí)現(xiàn)了Serializable接口，ObjectInputStream.readobject在反序列化類得到其對象時會自動查找這個類的readObject、readResolve等方法并調(diào)用。
例如某個類實(shí)現(xiàn)了Externalizable接口，ObjectInputStream.readobject在反序列化類得到其對象時會自動查找這個類的readExternal等方法并調(diào)用。
Jackson
ObjectMapper.readValue在反序列化類得到其對象時，會自動查找反序列化類的無參構(gòu)造方法、包含一個基礎(chǔ)類型參數(shù)的構(gòu)造方法、屬性的setter、屬性的getter等方法并調(diào)用。
...
在后面的分析中，都使用JDK自帶的ObjectInputStream作為樣例。
作者說，在反序列化漏洞中，如果控制了數(shù)據(jù)類型，我們就控制了代碼。這是什么意思呢？按我的理解，寫了下面的一個例子：
重慶分公司
重慶分公司
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?{
????????//將構(gòu)造好的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，并進(jìn)行反序列化????????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");????}}為了方便我把所有類寫在一個類中進(jìn)行測試。在Person類中，有一個Animal類的屬性pet，它是Cat和Dog的接口。在序列化時，我們能夠控制Person的pet具體是Cat對象或者Dog對象，因此在反序列化時，在readObject中pet.eat()具體的走向就不一樣了。如果是pet是Cat類對象，就不會走到執(zhí)行有害代碼Runtime.getRuntime().exec("calc");這一步，但是如果pet是Dog類的對象，就會走到有害代碼。
即使有時候類屬性在聲明時已經(jīng)為它賦值了某個具體的對象，但是在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?{
????????//將構(gòu)造好的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，并進(jìn)行反序列化
????????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類中，不能通過構(gòu)造器或setter方法或其他方式對pet賦值，屬性在聲明時已經(jīng)被定義為Cat類的對象，但是通過反射能將pet修改為Dog類的對象，因此在反序列化時依然會走到有害代碼處。
這只是我自己對作者"控制了數(shù)據(jù)類型，就控制了代碼"的理解，在Java反序列化漏洞中，很多時候是利用到了Java的多態(tài)特性來控制代碼走向最后達(dá)到惡意執(zhí)行目的。
在上面的例子中，能看到在反序列化時沒有調(diào)用Person的readobject方法，它是ObjectInputStream在反序列化對象時自動調(diào)用的。作者將在反序列化中會自動調(diào)用的方法稱為"魔術(shù)方法"。
使用ObjectInputStream反序列化時幾個常見的魔術(shù)方法：
Object.readObject()
Object.readResolve()
Object.finalize()
...
一些可序列化的JDK類實(shí)現(xiàn)了上面這些方法并且還自動調(diào)用了其他方法（可以作為已知的入口點(diǎn)）：
HashMap
Object.hashCode()
Object.equals()
PriorityQueue
Comparator.compare()
Comparable.CompareTo()
...
一些sink：
Runtime.exec()，這種最為簡單直接，即直接在目標(biāo)環(huán)境中執(zhí)行命令
Method.invoke()，這種需要適當(dāng)?shù)剡x擇方法和參數(shù)，通過反射執(zhí)行Java方法
RMI/JNDI/JRMP等，通過引用遠(yuǎn)程對象，間接實(shí)現(xiàn)任意代碼執(zhí)行的效果
...
作者給出了一個從Magic Methods(source)->Gadget Chains->Runtime.exec(sink)的例子：
上面的HashMap實(shí)現(xiàn)了readObject這個"魔術(shù)方法"，并且調(diào)用了hashCode方法。某些類為了比較對象之間是否相等會實(shí)現(xiàn)equals方法（一般是equals和hashCode方法同時實(shí)現(xiàn)）。從圖中可以看到AbstractTableModel$ff19274a正好實(shí)現(xiàn)了hashCode方法，其中又調(diào)用了f.invoke方法，f是IFn對象，并且f能通過屬性__clojureFnMap獲取到。IFn是一個接口，上面說到，如果控制了數(shù)據(jù)類型，就控制了代碼走向。所以如果我們在序列化時，在__clojureFnMap放置IFn接口的實(shí)現(xiàn)類FnCompose的一個對象，那么就能控制f.invoke走FnCompose.invoke方法，接著控制FnCompose.invoke中的f1、f2為FnConstant就能到達(dá)FnEval.invoke了（關(guān)于AbstractTableModel$ff19274a.hashcode中的f.invoke具體選擇IFn的哪個實(shí)現(xiàn)類，根據(jù)后面對這個工具的測試以及對決策原理的分析，廣度優(yōu)先會選擇短的路徑，也就是選擇了FnEval.invoke，所以這也是為什么要人為參與，在后面的樣例分析中也可以看到）。
有了這條鏈，只需要找到觸發(fā)這個鏈的漏洞點(diǎn)就行了。Payload使用JSON格式表示如下：
{
????"@class":"java.util.HashMap",
????"members":[
????????2,
????????{
????????????"@class":"AbstractTableModel$ff19274a",
????????????"__clojureFnMap":{
????????????????"hashcode":{
????????????????????"@class":"FnCompose",
????????????????????"f1":{"@class","FnConstant",value:"calc"},
????????????????????"f2":{"@class":"FnEval"}
????????????????}
????????????}
????????}
????]
}如作者所說，正好使用了五個步驟：
????????//?枚舉全部類以及類的所有方法????????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(cla***esourceEnumerator);
????????????methodDiscovery.save();
????????}
????????//生成passthrough數(shù)據(jù)流????????if?(!Files.exists(Paths.get("passthrough.dat")))?{
????????????LOGGER.info("Analyzing?methods?for?passthrough?dataflow...");
????????????PassthroughDiscovery?passthroughDiscovery?=?new?PassthroughDiscovery();
????????????passthroughDiscovery.discover(cla***esourceEnumerator,?config);
????????????passthroughDiscovery.save();
????????}
????????//生成passthrough調(diào)用圖????????if?(!Files.exists(Paths.get("callgraph.dat")))?{
????????????LOGGER.info("Analyzing?methods?in?order?to?build?a?call?graph...");
????????????CallGraphDiscovery?callGraphDiscovery?=?new?CallGraphDiscovery();
????????????callGraphDiscovery.discover(cla***esourceEnumerator,?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();
????????}
????????//搜索生成調(diào)用鏈????????{
????????????LOGGER.info("Searching?call?graph?for?gadget?chains...");
????????????GadgetChainDiscovery?gadgetChainDiscovery?=?new?GadgetChainDiscovery(config);
????????????gadgetChainDiscovery.discover();
????????}要進(jìn)行調(diào)用鏈的搜索，首先得有所有類及所有類方法的相關(guān)信息：
public?class?MethodDiscovery?{
????private?static?final?Logger?LOGGER?=?LoggerFactory.getLogger(MethodDiscovery.class);
????private?final?List?discoveredClasses?=?new?ArrayList<>();//保存所有類信息????private?final?List?discoveredMethods?=?new?ArrayList<>();//保存所有方法信息????...
????...
????public?void?discover(final?Cla***esourceEnumerator?cla***esourceEnumerator)?throws?Exception?{
????????//cla***esourceEnumerator.getAllClasses()獲取了運(yùn)行時的所有類(JDK?rt.jar)以及要搜索應(yīng)用中的所有類????????for?(Cla***esourceEnumerator.Cla***esource?cla***esource?:?cla***esourceEnumerator.getAllClasses())?{
????????????try?(InputStream?in?=?cla***esource.getInputStream())?{
????????????????Cla***eader?cr?=?new?Cla***eader(in);
????????????????try?{
????????????????????cr.accept(new?MethodDiscoveryClassVisitor(),?Cla***eader.EXPAND_FRAMES);//通過ASM框架操作字節(jié)碼并將類信息保存到this.discoveredClasses，將方法信息保存到discoveredMethods????????????????}?catch?(Exception?e)?{
????????????????????LOGGER.error("Exception?analyzing:?"?+?cla***esource.getName(),?e);
????????????????}
????????????}
????????}
????}
????...
????...
????public?void?save()?throws?IOException?{
????????DataLoader.saveData(Paths.get("classes.dat"),?new?Cla***eference.Factory(),?discoveredClasses);//將類信息保存到classes.dat????????DataLoader.saveData(Paths.get("methods.dat"),?new?MethodReference.Factory(),?discoveredMethods);//將方法信息保存到methods.dat
????????Map?classMap?=?new?HashMap<>();
????????for?(Cla***eference?clazz?:?discoveredClasses)?{
????????????classMap.put(clazz.getHandle(),?clazz);
????????}
????????InheritanceDeriver.derive(classMap).save();//查找所有繼承關(guān)系并保存????}} 來看下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
和上面的表格信息對應(yīng)一下，是吻合的
類名：com/sun/deploy/jardiff/JarDiffPatcher
父類： java/lang/Object，如果一類沒有顯式繼承其他類，默認(rèn)隱式繼承java/lang/Object，并且java中不允許多繼承，所以每個類只有一個父類
所有接口：com/sun/deploy/jardiff/JarDiffConstants、com/sun/deploy/jardiff/Patcher
是否是接口：false
成員：newBytes!2
和上面的表格信息對應(yīng)一下，也是吻合的
類名：com/sun/corba/se/impl/presentation/rmi/InvocationHandlerFactoryImpl$CustomCompositeInvocationHandlerImpl，是一個內(nèi)部類
父類： 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。因?yàn)槭莾?nèi)部類，所以多了個this成員，這個this指向的是外部類
methods.dat
同樣找?guī)讉€比較有特征的
| 類名 | 方法名 | 方法描述信息 | 是否是靜態(tài)方法 |
|---|---|---|---|
| sun/nio/cs/ext/Big5 | newEncoder | ()Ljava/nio/charset/CharsetEncoder; | false |
| sun/nio/cs/ext/Big5_HKSCS$Decoder | \ | (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對象
是否是靜態(tài)方法：false
sun/nio/cs/ext/Big5_HKSCS$Decoder#\
類名：sun/nio/cs/ext/Big5_HKSCS$Decoder
方法名：\
方法描述信息： (Ljava/nio/charset/Charset;Lsun/nio/cs/ext/Big5_HKSCS1;)V參數(shù)1是java/nio/charset/Charset類型，參數(shù)2是sun/nio/cs/ext/Big5HKSCS1;)V參數(shù)1是java/nio/charset/Charset類型，參數(shù)2是sun/nio/cs/ext/Big5HKSCS1類型，返回值void
是否是靜態(tài)方法：false
繼承關(guān)系的生成：
繼承關(guān)系在后面用來判斷一個類是否能被某個庫序列化、以及搜索子類方法實(shí)現(xiàn)等會用到。
public?class?InheritanceDeriver?{
????private?static?final?Logger?LOGGER?=?LoggerFactory.getLogger(InheritanceDeriver.class);
????public?static?InheritanceMap?derive(Map?classMap)?{
????????LOGGER.debug("Calculating?inheritance?for?"?+?(classMap.size())?+?"?classes...");
????????Map>?implicitInheritance?=?new?HashMap<>();
????????for?(Cla***eference?cla***eference?:?classMap.values())?{
????????????if?(implicitInheritance.containsKey(cla***eference.getHandle()))?{
????????????????throw?new?IllegalStateException("Already?derived?implicit?classes?for?"?+?cla***eference.getName());
????????????}
????????????Set?allParents?=?new?HashSet<>();
????????????getAllParents(cla***eference,?classMap,?allParents);//獲取當(dāng)前類的所有父類
????????????implicitInheritance.put(cla***eference.getHandle(),?allParents);
????????}
????????return?new?InheritanceMap(implicitInheritance);
????}
????...
????...
????private?static?void?getAllParents(Cla***eference?cla***eference,?Map?classMap,?Set?allParents)?{
????????Set?parents?=?new?HashSet<>();
????????if?(cla***eference.getSuperClass()?!=?null)?{
????????????parents.add(new?Cla***eference.Handle(cla***eference.getSuperClass()));//父類????????}
????????for?(String?iface?:?cla***eference.getInterfaces())?{
????????????parents.add(new?Cla***eference.Handle(iface));//接口類????????}
????????for?(Cla***eference.Handle?immediateParent?:?parents)?{
????????????//獲取間接父類，以及遞歸獲取間接父類的父類????????????Cla***eference?parentCla***eference?=?classMap.get(immediateParent);
????????????if?(parentCla***eference?==?null)?{
????????????????LOGGER.debug("No?class?id?for?"?+?immediateParent.getName());
????????????????continue;
????????????}
????????????allParents.add(parentCla***eference.getHandle());
????????????getAllParents(parentCla***eference,?classMap,?allParents);
????????}
????}
????...
????...} 這一步的結(jié)果保存到了inheritanceMap.dat：
| 類 | 直接父類+間接父類 |
|---|---|
| com/sun/javaws/OperaPreferencesPreferenceSectionPreferenceSectionPreferenceEntryIterator | java/lang/Object、java/util/Iterator |
| com/sun/java/swing/plaf/windows/WindowsLookAndFeel$XPValue | java/lang/Object、javax/swing/UIDefaults$ActiveValue |
這里的passthrough數(shù)據(jù)流指的是每個方法的返回結(jié)果與方法參數(shù)的關(guān)系，這一步生成的數(shù)據(jù)會在生成passthrough調(diào)用圖時用到。
以作者給出的demo為例，先從宏觀層面判斷下：
FnConstant.invoke返回值與參數(shù)this(參數(shù)0，因?yàn)樾蛄谢瘯r類的所有成員我們都能控制，所以所有成員變量都視為0參)、arg(參數(shù)1)的關(guān)系：
與this的關(guān)系：返回了this.value，即與0參有關(guān)系
與arg的關(guān)系：返回值與arg沒有任何關(guān)系，即與1參沒有關(guān)系
結(jié)論就是FnConstant.invoke與參數(shù)0有關(guān)，表示為FnConstant.invoke()->0
Fndefault.invoke返回值與參數(shù)this(參數(shù)0)、arg(參數(shù)1)的關(guān)系：
與this的關(guān)系：返回條件的第二個分支與this.f有關(guān)系，即與0參有關(guān)系
與arg的關(guān)系：返回條件的第一個分支與arg有關(guān)系，即與1參有關(guān)系
結(jié)論就是FnConstant.invoke與0參，1參都有關(guān)系，表示為Fndefault.invoke()->0、Fndefault.invoke()->1
在這一步中，gadgetinspector是利用ASM來進(jìn)行方法字節(jié)碼的分析，主要邏輯是在類PassthroughDiscovery和TaintTrackingMethodVisitor中。特別是TaintTrackingMethodVisitor，它通過標(biāo)記追蹤JVM虛擬機(jī)在執(zhí)行方法時的stack和localvar，并最終得到返回結(jié)果是否可以被參數(shù)標(biāo)記污染。
核心實(shí)現(xiàn)代碼（TaintTrackingMethodVisitor涉及到字節(jié)碼分析，暫時先不看）：
public?class?PassthroughDiscovery?{
????private?static?final?Logger?LOGGER?=?LoggerFactory.getLogger(PassthroughDiscovery.class);
????private?final?Map>?methodCalls?=?new?HashMap<>();
????private?Map>?passthroughDataflow;
????public?void?discover(final?Cla***esourceEnumerator?cla***esourceEnumerator,?final?GIConfig?config)?throws?IOException?{
????????Map?methodMap?=?DataLoader.loadMethods();//load之前保存的methods.dat????????Map?classMap?=?DataLoader.loadClasses();//load之前保存的classes.dat????????InheritanceMap?inheritanceMap?=?InheritanceMap.load();//load之前保存的inheritanceMap.dat
????????Map?cla***esourceByName?=?discoverMethodCalls(cla***esourceEnumerator);//查找一個方法中包含的子方法????????List?sortedMethods?=?topologicallySortMethodCalls();//對所有方法構(gòu)成的圖執(zhí)行逆拓?fù)渑判????????passthroughDataflow?=?calculatePassthroughDataflow(cla***esourceByName,?classMap,?inheritanceMap,?sortedMethods,
????????????????config.getSerializableDecider(methodMap,?inheritanceMap));//計算生成passthrough數(shù)據(jù)流，涉及到字節(jié)碼分析????}
????...
????...
????private?List?topologicallySortMethodCalls()?{
????????Map>?outgoingReferences?=?new?HashMap<>();
????????for?(Map.Entry>?entry?:?methodCalls.entrySet())?{
????????????MethodReference.Handle?method?=?entry.getKey();
????????????outgoingReferences.put(method,?new?HashSet<>(entry.getValue()));
????????}
????????//?對所有方法構(gòu)成的圖執(zhí)行逆拓?fù)渑判????????LOGGER.debug("Performing?topological?sort...");
????????Set?dfsStack?=?new?HashSet<>();
????????Set?visitedNodes?=?new?HashSet<>();
????????List?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>?outgoingReferences,
????????????????????????????????????List?sortedMethods,?Set?visitedNodes,
????????????????????????????????????Set?stack,?MethodReference.Handle?node)?{
????????if?(stack.contains(node))?{//防止在dfs一條方法調(diào)用鏈中進(jìn)入循環(huán)????????????return;
????????}
????????if?(visitedNodes.contains(node))?{//防止對某個方法及子方法重復(fù)排序????????????return;
????????}
????????Set?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);
????}} 拓?fù)渑判?/p>
有向無環(huán)圖（DAG）才有拓?fù)渑判?，?DAG 圖沒有拓?fù)渑判颉?當(dāng)有向無環(huán)圖滿足以下條件時：
每一個頂點(diǎn)出現(xiàn)且只出現(xiàn)一次
若A在序列中排在B的前面，則在圖中不存在從B到A的路徑
這樣的圖，是一個拓?fù)渑判虻膱D。樹結(jié)構(gòu)其實(shí)可以轉(zhuǎn)化為拓?fù)渑判颍負(fù)渑判?不一定能夠轉(zhuǎn)化為樹。
以上面的拓?fù)渑判驁D為例，用一個字典表示圖結(jié)構(gòu)
?graph?=?{
?????"a":?["b","d"],
?????"b":?["c"],
?????"d":?["e","c"],
?????"e":?["c"],
?????"c":?[],
?}代碼實(shí)現(xiàn)
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的插入隊(duì)列??queue?=?[u?for?u?in?graph?if?degrees[u]?==?0]
??res?=?[]
??while?queue:
??????u?=?queue.pop()
??????res.append(u)
??????for?v?in?graph[u]:
??????????#?移除邊，即將當(dāng)前元素相關(guān)元素的入度-1??????????degrees[v]?-=?1
??????????if?degrees[v]?==?0:
??????????????queue.append(v)
??return?resprint(TopologicalSort(graph))?#?['a',?'d',?'e',?'b',?'c']但是在方法的調(diào)用中，我們希望最后的結(jié)果是c、b、e、d、a，這一步需要逆拓?fù)渑判?，正向排序使用的BFS，那么得到相反結(jié)果可以使用DFS。為什么在方法調(diào)用中需要使用逆拓?fù)渑判蚰兀@與生成passthrough數(shù)據(jù)流有關(guān)?？聪旅嬉粋€例子：
...
????public?String?parentMethod(String?arg){
????????String?vul?=?Obj.childMethod(arg);
????????return?vul;
????}...那么這里arg與返回值到底有沒有關(guān)系呢？假設(shè)Obj.childMethod為
...
????public?String?childMethod(String?carg){
????????return?carg.toString();
????}...由于childMethod的返回值carg與有關(guān)，那么可以判定parentMethod的返回值與參數(shù)arg是有關(guān)系的。所以如果存在子方法調(diào)用并傳遞了父方法參數(shù)給子方法時，需要先判斷子方法返回值與子方法參數(shù)的關(guān)系。因此需要讓子方法的判斷在前面，這就是為什么要進(jìn)行逆拓?fù)渑判颉?/p>
從下圖可以看出outgoingReferences的數(shù)據(jù)結(jié)構(gòu)為：
{
????method1:(method2,method3,method4),
????method5:(method1,method6),
????...}而這個結(jié)構(gòu)正好適合逆拓?fù)渑判?/p>
但是上面說拓?fù)渑判驎r不能形成環(huán)，但是在方法調(diào)用中肯定是會存在環(huán)的。作者是如何避免的呢？
在上面的dfsTsort實(shí)現(xiàn)代碼中可以看到使用了stack和visitedNodes，stack保證了在進(jìn)行逆拓?fù)渑判驎r不會形成環(huán)，visitedNodes避免了重復(fù)排序。使用如下一個調(diào)用圖來演示過程：
從圖中可以看到有環(huán)med1->med2->med6->med1，并且有重復(fù)的調(diào)用med3，嚴(yán)格來說并不能進(jìn)行逆拓?fù)渑判?，但是通過stack、visited記錄訪問過的方法，就能實(shí)現(xiàn)逆拓?fù)渑判?。為了方便解釋把上面的圖用一個樹來表示：
對上圖進(jìn)行逆拓?fù)渑判颍―FS方式）：
從med1開始，先將med1加入stack中，此時stack、visited、sortedmethods狀態(tài)如下：
med1還有子方法？有，繼續(xù)深度遍歷。將med2放入stack，此時的狀態(tài)：
med2有子方法嗎？有，繼續(xù)深度遍歷。將med3放入stack，此時的狀態(tài)：
med3有子方法嗎？有，繼續(xù)深度遍歷。將med7放入stack，此時的狀態(tài)：
med7有子方法嗎？沒有，從stack中彈出med7并加入visited和sortedmethods，此時的狀態(tài)：
回溯到上一層，med3還有其他子方法嗎？有，med8，將med8放入stack，此時的狀態(tài)：
med8還有子方法嗎？沒有，彈出stack，加入visited與sortedmethods，此時的狀態(tài)：
回溯到上一層，med3還有其他子方法嗎？沒有了，彈出stack，加入visited與sortedmethods，此時的狀態(tài)：
回溯到上一層，med2還有其他子方法嗎？有，med6，將med6加入stack，此時的狀態(tài)：
med6還有子方法嗎？有，med1，med1在stack中？不加入，拋棄。此時狀態(tài)和上一步一樣
回溯到上一層，med6還有其他子方法嗎？沒有了，彈出stack，加入visited和sortedmethods，此時的狀態(tài)：
回溯到上一層，med2還有其他子方法嗎？沒有了，彈出stack，加入visited和sortedmethods，此時的狀態(tài)：
回溯到上一層，med1還有其他子方法嗎？有，med3，med3在visited中？在，拋棄。
回溯到上一層，med1還有其他子方法嗎？有，med4，將med4加入stack，此時的狀態(tài)：
med4還有其他子方法嗎？沒有，彈出stack，加入visited和sortedmethods中，此時的狀態(tài)：
回溯到上一層，med1還有其他子方法嗎？沒有了，彈出stack，加入visited和sortedmethods中，此時的狀態(tài)（即最終狀態(tài)）：
所以最后的逆拓?fù)渑判蚪Y(jié)果為：med7、med8、med3、med6、med2、med4、med1。
生成passthrough數(shù)據(jù)流
在calculatePassthroughDataflow中遍歷了sortedmethods，并通過字節(jié)碼分析，生成了方法返回值與參數(shù)關(guān)系的passthrough數(shù)據(jù)流。注意到下面的序列化決定器，作者內(nèi)置了三種：JDK、Jackson、Xstream，會根據(jù)具體的序列化決定器判定決策過程中的類是否符合對應(yīng)庫的反序列化要求，不符合的就跳過：
對于JDK(ObjectInputStream)，類否繼承了Serializable接口
對于Jackson，類是否存在0參構(gòu)造器
對于Xstream，類名能否作為有效的XML標(biāo)簽
生成passthrough數(shù)據(jù)流代碼：
