[發明專利]構建調用鏈轉換圖及引導生成X.509證書變種方法

在審

• 申請號: 202010434699.8
• 申請日: 2020-05-21
• 公開（公告）號: CN113704078A
• 公開（公告）日: 2021-11-26
• 發明（設計）人: 朱佳宇;陳雨亭;沈備軍
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 上海交達專利事務所 31201
• 代理人: 王毓理;王錫麟

1.一種構建調用鏈轉換圖及引導生成X.509證書變種方法，其特征在于，通過構建測試種子集并輸入目標測試程序，得到動態執行中的函數調用鏈信息并映射為調用鏈轉換圖中的初始節點；循環對調用鏈轉換圖中的取樣節點通過變種算子生成新的變種測試用例并根據變種測試用例對應更新調用鏈轉換圖，直至生成目標數量的測試用例。

2.根據權利要求1所述的構建調用鏈轉換圖及引導生成X.509證書變種方法，其特征是，所述的映射是指：調用鏈轉換圖中的節點和測試用例對應，圖的一個節點是一個測試用例集合，該測試用例集合中的任意一個測試用例在目標測試程序上得到的函數調用鏈是一致的。

3.根據權利要求1所述的構建調用鏈轉換圖及引導生成X.509證書變種方法，其特征是，所述的取樣是指：通過計算潛力值并挑選節點和節點中的測試用例以用于生成變種。

4.根據權利要求1所述的構建調用鏈轉換圖及引導生成X.509證書變種方法，其特征是，所述的變種是指：對一個現有的測試用例進行修改生成一個新的測試用例，其實現方式視具體的測試場景而言，可自定義具體的變種方式也可對接已有的模糊測試工具如AFL對測試用例進行修改而生成新的測試用例，在針對X.509證書測試的應用場景中，變種算子可采用mucert工具中提供的變種方法。

5.根據權利要求1所述的構建調用鏈轉換圖及引導生成X.509證書變種方法，其特征是，所述的更新調用鏈轉換圖是指：以更新后的變種測試用例作為輸入得到目標測試程序運行時的函數調用鏈，更新中間文件并映射為轉換圖中的新節點，構造一條調用鏈轉換圖中取樣節點和新節點之間的邊并更新取樣節點所有邊的權值。

6.根據權利要求1所述的構建調用鏈轉換圖及引導生成X.509證書變種方法，其特征是，所述的調用鏈轉換圖是帶權重的有向圖G＝(V,E,W)，其中：V為節點集合，每個節點映射為對應的函數調用鏈hash值，當兩個測試用例同屬于一個節點，則對應的函數調用鏈hash值相同，說明其在目標測試程序上的執行路徑相同；E為調用鏈轉換邊的集合，當一個節點為u，另一個節點為v，u中的一個測試用例在進行變種后得到一個屬于節點v的測試用例，則得到一條從節點u指向節點v的邊，用u-v來標記，則整個邊集合為w為邊上的權重集合，使用w＝weight(u-v)表示在給定節點u的情況下得到指向v節點的概率，從節點u出發的所有邊的權重和為1，即

7.根據權利要求1所述的構建調用鏈轉換圖及引導生成X.509證書變種方法，其特征是，所述的通過變種算子生成新的變種測試用例是指：使用潛能函數計算每個節點的潛力值其中：Out(n)表示節點n的出度，Mutate(n)表示節點n被選中進行變種的次數，在每個節點按照潛力值降序存進隊列后，再從隊列中選取序號為k的節點，其中：|array|表示數組的大小，rand為0-1的隨機數，ε為圖中每個節點都沒有被選中的概率，隨機選取選中節點中的一個測試用例通過變種算子進行修改以生成變種；所述的變種算子根據目標測試程序自定義，將根據變種算子修改后生成的變種測試用例添加回測試集中。

8.根據權利要求1所述的構建調用鏈轉換圖及引導生成X.509證書變種方法，其特征是，所述的更新調用鏈轉換圖是指：收集新生成的變種測試用例在目標程序運行時的函數調用鏈，將函數調用鏈映射為調用鏈轉換圖中的一個節點；迭代取樣調用鏈轉換圖中的節點并選取節點中的測試用例生成變種，根據變種測試用例在目標測試程序中的函數調用鏈映射為圖中的新節點，動態添加原測試用例映射節點和變種映射節點中的邊和更新邊的權值，直至生成目標數量的證書測試用例，并輸入待測程序進行測試。

9.根據權利要求1或8所述的構建調用鏈轉換圖及引導生成X.509證書變種方法，其特征是，所述的更新調用鏈轉換圖具體為：當該節點不存在于原先的調用鏈轉換圖中，則在圖中添加新的節點，記變種測試用例對應的原測試用例所映射的節點為A，新生成的變種測試用例映射的節點為B，在轉換圖中添加一條從A指向B的有向邊，最后將變種測試用例添加回測試集中；

所述的添加一條從A指向B的有向邊，即由節點A指向節點B的邊，同時從節點A出發的邊上的權重需要更新，則節點A被選中進行變種次數為T1，其他從節點A出發的節點Bi包含了T2_i個由節點A中證書生成的變種證書，則從A到Bi的權重被更新為