计算机科学 ›› 2018, Vol. 45 ›› Issue (6): 145-150.doi: 10.11896/j.issn.1002-137X.2018.06.025
李航, 臧洌, 甘露
LI Hang, ZANG Lie, GAN Lu
摘要: 符号执行作为一种基本的程序分析技术,已被广泛应用于软件测试领域。研究表明,即使在现有的查询优化技术的支持下,约束求解也仍然是符号执行中最耗时的部分。猜测符号执行的思想是将多次约束求解合并成一次求解,从而减少约束求解消耗的时间。但是,猜测的成功率受猜测深度和路径搜索方向的影响,尤其是路径搜索的方向在较大程度上决定了整体猜测的成功率。因此,引导路径搜索向成功率高的方向进行,对提高猜测符号执行的整体效率至关重要。在猜测符号执行的路径搜索过程中引入蚁群算法,根据节点条件信息初次确定分支路径的权重,在多次迭代中根据分支路径的覆盖情况更新权重,通过权重决定路径搜索的方向。实验表明,该方法有效提升了猜测符号执行的效率。
中图分类号:
[1]KING J C.Symbolic execution and program testing [J].Communications of the ACM,1976,19(7):385-394. [2]ZHANG Y F.Improving the Scalability and Feasibility of Symbolic Execution [D].Changsha:National University of Defense Technology,2013.(in Chinese) 张羽丰.符号执行可扩展性及可行性关键技术研究[D].长沙:国防科学技术大学,2013. [3]WANG H,LIU T,GUAN X,et al.Dependence Guided Symbolic Execution[J].IEEE Transactions on Software Engineering,2017,43(3):252-271. [4]YAN T.Dynamic Symbolic Execution with Segmented[D].Shanghai:East China Normal University,2015.(in Chinese) 颜婷.分段式分析方法在动态符号执行中的应用[D].上海:华东师范大学,2015. [5]ZOU Q,HUANG W,AN J,et al.Redundant constraints elimination for symbolic execution[C]//IEEE Information Technology,Networking,Electronic and Automation Control Conference.IEEE,2016:235-240. [6]KANG W T.Optimization of Constraint Solver for KLEE,A Dynamic Symbolic Execution Tool [D].Chengdu:University of Electronic Science and Technology,2014.(in Chinese) 康文涛.符号执行工具KLEE约束求解优化设计与实现[D].成都:电子科技大学,2014. [7]LI X,LIANG Y,QIAN H,et al.Symbolic execution of complex program driven by machine learning based constraint solving[C]//Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering.ACM,2016:554-559. [8]ZHANG Y,CHEN Z,WANG J.Speculative Symbolic Execution[C]//IEEE,International Symposium on Software Reliability Engineering.IEEE,2012:101-110. [9]DORIGO M.Ant Colonies for the Traveling Salesman Problem[J].Biosystems,1997,43(2):73-81. [10]CHEN L,SHEN J,QIN L,et al.An adaptive ant colony algorithm based on equilibrium of distribution [J].Journal of Software,2003,14(8):1379-1387. [11]STAATS M,PASAREANU C.Parallel symbolic execution for structural test generation[C]//Proceedings of the 19th International Symposium on Software Testing and Analysis.ACM,2010:183-194. [12]DO H,ELBAUM S,ROTHERMEL G.Supporting Controlled Experimentation with Testing Techniques:An Infrastructure and its Potential Impact[J].Empirical Software Engineering,2005,10(4):405-435. |
[1] | 刘鑫, 王珺, 宋巧凤, 刘家豪. 一种基于AAE的协同多播主动缓存方案 Collaborative Multicast Proactive Caching Scheme Based on AAE 计算机科学, 2022, 49(9): 260-267. https://doi.org/10.11896/jsjkx.210800019 |
[2] | 高文龙, 周天阳, 朱俊虎, 赵子恒. 基于双向蚁群算法的网络攻击路径发现方法 Network Attack Path Discovery Method Based on Bidirectional Ant Colony Algorithm 计算机科学, 2022, 49(6A): 516-522. https://doi.org/10.11896/jsjkx.210500072 |
[3] | 孙振强, 罗永龙, 郑孝遥, 章海燕. 一种融合用户情感与相似度的智能旅游路径推荐方法 Intelligent Travel Route Recommendation Method Integrating User Emotion and Similarity 计算机科学, 2021, 48(6A): 226-230. https://doi.org/10.11896/jsjkx.200900119 |
[4] | 郭蕊, 芦天亮, 杜彦辉, 周杨, 潘孝勤, 刘晓晨. 基于改进蚁群算法的WSN源位置隐私保护 WSN Source-location Privacy Protection Based on Improved Ant Colony Algorithm 计算机科学, 2020, 47(7): 307-313. https://doi.org/10.11896/jsjkx.200100056 |
[5] | 曹义亲, 武丹, 黄晓生. 基于改进蚁群算法的轨道缺陷图像分类 Track Defect Image Classification Based on Improved Ant Colony Algorithm 计算机科学, 2019, 46(8): 292-297. https://doi.org/10.11896/j.issn.1002-137X.2019.08.048 |
[6] | 郑本立, 李跃辉. 基于改进蚁群算法的SDN网络负载均衡研究 Study on SDN Network Load Balancing Based on IACO 计算机科学, 2019, 46(6A): 291-294. |
[7] | 张娜, 徐海霞, 包晓安, 徐璐, 吴彪. 一种动态约简的多目标测试用例优先级排序方法 Multi-objective Test Case Prioritization Method Combined with Dynamic Reduction 计算机科学, 2019, 46(12): 208-212. https://doi.org/10.11896/jsjkx.181102106 |
[8] | 李珊珊, 刘福江, 林伟华. 一种基于多起点、多终点的大型火灾救援路径规划方法 Path Planning Method of Large-scale Fire Based on Multiple Starting Points and Multiple Rescue Points 计算机科学, 2019, 46(11A): 134-137. |
[9] | 李光华, 李俊清, 张亮, 辛衍森, 邓华伟. 一种融合蚁群算法和随机森林的特征选择方法 Feature Selection Method Based on Ant Colony Optimization and Random Forest 计算机科学, 2019, 46(11A): 212-215. |
[10] | 陈正钊, 姜人和, 潘敏学, 张天, 李宣东. 基于约束求解的代码查询技术在StackOverflow上的实证研究 Empirical Study of Code Query Technique Based on Constraint Solving on StackOverflow 计算机科学, 2019, 46(11): 137-144. https://doi.org/10.11896/jsjkx.191100501C |
[11] | 叶志斌,严波. 符号执行研究综述 Survey of Symbolic Execution 计算机科学, 2018, 45(6A): 28-35. |
[12] | 张永刚, 程竹元. 最大受限路径相容约束传播算法的研究进展 Research Progress on Max Restricted Path Consistency Constraint Propagation Algorithms 计算机科学, 2018, 45(6A): 41-45. |
[13] | 符晓. 云计算中基于共享机制和群体智能优化算法的任务调度方案 Task Scheduling Scheme Based on Sharing Mechanism and Swarm Intelligence Optimization Algorithm in Cloud Computing 计算机科学, 2018, 45(6A): 290-294. |
[14] | 刘俊, 徐平平, 武贵路, 彭杰. 室内环境下基于最优路径规划的PSO-ACO融合算法 PSO-ACO Fusion Algorithm Based on Optimal Path Planning in Indoor Environment 计算机科学, 2018, 45(11A): 97-100. |
[15] | 王鑫, 王人福, 覃琴, 蒋华. 云存储副本优化选择策略 Optimization Selection Strategy of Cloud Storage Replica 计算机科学, 2018, 45(10): 300-305. https://doi.org/10.11896/j.issn.1002-137X.2018.10.056 |
|