基于圈復雜度的階段動態符號執行
2020年信息技術與網絡安全第4期
畢雪潔1，於家偉1，李世明1,2
(1.哈爾濱師范大學 計算機科學與信息工程學院，黑龍江 哈爾濱 150025； 2.上海市信息安全綜合管理技術研究重點實驗室，上海 200240)
摘要： 為了緩解動態符號執行不可避免的路徑爆炸等問題，提出了基于圈復雜度的階段動態符號執行CCSDSEM優化算法。該算法通過計算約束判定條件為真的數量來衡量代碼的圈復雜度，然后依據圈復雜度的閾值進行分階段動態符號執行，使動態符號執行梯度進行，緩解路徑選擇指數爆炸，合理縮放符號執行。最后在KLEE中實現CCSDSEM框架，并對測試程序做了檢測。CCSDSEM將符號執行的運行時間顯著縮短，提升了生成測試用例的數量。
中圖分類號：TP393.08
文獻標識碼：A
DOI： 10.19358/j.issn.2096-5133.2020.04.005
引用格式：畢雪潔，於家偉，李世明.基于圈復雜度的階段動態符號執行［J］.信息技術與網絡安全，2020,39（4）：24-29.
文獻標識碼：A
DOI： 10.19358/j.issn.2096-5133.2020.04.005
引用格式：畢雪潔，於家偉，李世明.基于圈復雜度的階段動態符號執行［J］.信息技術與網絡安全，2020,39（4）：24-29.
Stage dynamic symbol execution based on cyclomatic complexity
Bi Xuejie1，Yu Jiawei1，Li Shiming1,2
(1.College of Computer Science and Information Engineering,Harbin Normal University,Harbin 150025,China; 2.Shanghai Key Laboratory of Integrated Administration Technologies for Information Security,Shanghai 200240,China)
Abstract： In order to alleviate problems such as the path explosion of dynamic symbol execution contraction,this paper proposes an optimization algorithm for stage dynamic symbol execution based on cyclomatic complexity(CCSDSEM).The algorithm realizes the cyclomatic complexity of the code by calculating the constraints to determine the exact number,and then executes the dynamic symbol execution in stages according to the threshold of cycle complexity,makes the dynamic symbol execution gradient,replaces the path selection index explosion,and scales the symbol execution reasonably.The above optimization framework was implemented in KLEE,and the test program was tested.CCSDSEM significantly changes the runtime of symbolic execution,increasing the number of test cases generated.
Key words : cyclomatic complexity;concolic execution;scaling symbolic execution;software testing
0 引言
路徑爆炸問題降低了軟件測試的效率和質量，也給軟件埋下隱患。如何緩解路徑爆炸問題成為軟件安全測試中的一個研究熱點，符號執行成為緩解該問題嚴重程度的重要技術之一。其主要算法思想為利用符號變量來取代測試過程的真實用例，從而在執行過程中獲取對應的執行路徑，成為生成高覆蓋測試用例和在復雜軟件應用程序中查找深度錯誤的有效技術之一；因該技術能夠處理復雜結構程序，開發人員也經常用之于程序自動測試、程序缺陷檢測、測試用例生成等。
本文詳細內容請下載：http://www.shi-ke.cn/resource/share/2000003201
作者信息：
畢雪潔1，於家偉1，李世明1,2
(1.哈爾濱師范大學 計算機科學與信息工程學院，黑龍江 哈爾濱 150025；2.上海市信息安全綜合管理技術研究重點實驗室，上海 200240)
此內容為AET網站原創，未經授權禁止轉載。