基于圈复杂度的阶段动态符号执行  

Stage dynamic symbol execution based on cyclomatic complexity

作　　者：毕雪洁 於家伟 李世明[1,2] Bi Xuejie;Yu Jiawei;Li Shiming(College of Computer Science and Information Engineering,Harbin Normal University,Harbin 150025,China;Shanghai Key Laboratory of Integrated Administration Technologies for Information Security,Shanghai 200240,China)

机构地区：[1]哈尔滨师范大学计算机科学与信息工程学院,黑龙江哈尔滨150025 [2]上海市信息安全综合管理技术研究重点实验室,上海200240

出　　处：《信息技术与网络安全》2020年第4期24-29,共6页Information Technology and Network Security

基　　金：上海市信息安全管理技术研究重点实验室开放课题(AGK2015003)。

摘　　要：为了缓解动态符号执行不可避免的路径爆炸等问题,提出了基于圈复杂度的阶段动态符号执行CCSDSEM优化算法。该算法通过计算约束判定条件为真的数量来衡量代码的圈复杂度,然后依据圈复杂度的阈值进行分阶段动态符号执行,使动态符号执行梯度进行,缓解路径选择指数爆炸,合理缩放符号执行。最后在KLEE中实现CCSDSEM框架,并对测试程序做了检测。CCSDSEM将符号执行的运行时间显著缩短,提升了生成测试用例的数量。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.

关 键 词：圈复杂度 动态符号执行 阶段执行 软件测试 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]