计算机科学 ›› 2018, Vol. 45 ›› Issue (6): 145-150.doi: 10.11896/j.issn.1002-137X.2018.06.025

• 软件与数据库技术 • 上一篇    下一篇

基于蚁群算法的猜测符号执行的路径搜索

李航, 臧洌, 甘露   

  1. 南京航空航天大学计算机科学与技术学院 南京211106
  • 收稿日期:2017-03-05 出版日期:2018-06-15 发布日期:2018-07-24
  • 作者简介:李 航(1991-),男,硕士,CCF会员,主要研究方向为软件测试,E-mail:422813555@qq.com;臧 洌(1965-),女,硕士,副教授,主要研究方向为机器学习、入侵检测,E-mail:zangliwen@nuaa.edu.cn(通信作者);甘 露(1991-),女,硕士,主要研究方向为机器学习、软件缺陷预测

Search of Speculative Symbolic Execution Path Based on Ant Colony Algorithm

LI Hang, ZANG Lie, GAN Lu   

  1. School of Computer Science and Technology,Nanjing University of Aeronautics & Astronautics,Nanjing 211106,China
  • Received:2017-03-05 Online:2018-06-15 Published:2018-07-24

摘要: 符号执行作为一种基本的程序分析技术,已被广泛应用于软件测试领域。研究表明,即使在现有的查询优化技术的支持下,约束求解也仍然是符号执行中最耗时的部分。猜测符号执行的思想是将多次约束求解合并成一次求解,从而减少约束求解消耗的时间。但是,猜测的成功率受猜测深度和路径搜索方向的影响,尤其是路径搜索的方向在较大程度上决定了整体猜测的成功率。因此,引导路径搜索向成功率高的方向进行,对提高猜测符号执行的整体效率至关重要。在猜测符号执行的路径搜索过程中引入蚁群算法,根据节点条件信息初次确定分支路径的权重,在多次迭代中根据分支路径的覆盖情况更新权重,通过权重决定路径搜索的方向。实验表明,该方法有效提升了猜测符号执行的效率。

关键词: 猜测符号执行, 路径搜索, 蚁群算法, 约束求解

Abstract: Symbolic execution has been widely used in the field of software testing.The research shows that constraint solving is the most time-consuming part in symbolic execution,even though some optimization techniques are used.The speculative symbolic execution reduces the consuming time of constraint solved by making several continuous constraint solving merge into once.The success rate of every time guess is affected by the depth of conjecture and the direction of search,especially the direction of search.Therefore,how to guide the path search to conduct in the direction of success is very important to improve the efficiency of speculative symbolic execution.In this paper,ant colony algorithm was used to search the path.Firstly,according to the node condition,the weight of branch path was determined.Then,the weight of a branch was updated according to whether this branch is covered in every time guess.This paper chose the direction of search based on the weight of branch.The experimental results show that the proposed method can improve the efficiency of speculative symbol execution effectively.

Key words: Ant colony algorithm, Constraint solving, Path search, Speculative symbolic execution

中图分类号: 

  • TP311
[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
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!