Computer Science ›› 2018, Vol. 45 ›› Issue (6): 145-150.doi: 10.11896/j.issn.1002-137X.2018.06.025

• Software & Database Technology • Previous Articles     Next Articles

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

CLC Number: 

  • 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] LIU Xin, WANG Jun, SONG Qiao-feng, LIU Jia-hao. Collaborative Multicast Proactive Caching Scheme Based on AAE [J]. Computer Science, 2022, 49(9): 260-267.
[2] GAO Wen-long, ZHOU Tian-yang, ZHU Jun-hu, ZHAO Zi-heng. Network Attack Path Discovery Method Based on Bidirectional Ant Colony Algorithm [J]. Computer Science, 2022, 49(6A): 516-522.
[3] SUN Zhen-qiang, LUO Yong-long, ZHENG Xiao-yao, ZHANG Hai-yan. Intelligent Travel Route Recommendation Method Integrating User Emotion and Similarity [J]. Computer Science, 2021, 48(6A): 226-230.
[4] GUO Rui, LU Tian-liang, DU Yan-hui, ZHOU Yang, PAN Xiao-qin, LIU Xiao-chen. WSN Source-location Privacy Protection Based on Improved Ant Colony Algorithm [J]. Computer Science, 2020, 47(7): 307-313.
[5] TIAN Xian-zhen, SUN Li-qiang, TIAN Zhen-zhong. Image Reconstruction Based on Ant Colony Algorithm [J]. Computer Science, 2020, 47(11A): 231-235.
[6] CAO Yi-qin, WU Dan, HUANG Xiao-sheng. Track Defect Image Classification Based on Improved Ant Colony Algorithm [J]. Computer Science, 2019, 46(8): 292-297.
[7] ZHENG Ben-li, LI Yue-hui. Study on SDN Network Load Balancing Based on IACO [J]. Computer Science, 2019, 46(6A): 291-294.
[8] ZHANG Na, XU Hai-xia, BAO Xiao-an, XU Lu, WU Biao. Multi-objective Test Case Prioritization Method Combined with Dynamic Reduction [J]. Computer Science, 2019, 46(12): 208-212.
[9] LI Shan-shan, LIU Fu-jiang, LIN Wei-hua. Path Planning Method of Large-scale Fire Based on Multiple Starting Points and Multiple Rescue Points [J]. Computer Science, 2019, 46(11A): 134-137.
[10] CHEN Zheng-zhao, JIANG Ren-he, PAN Min-xue, ZHANG Tian, LI Xuan-dong. Empirical Study of Code Query Technique Based on Constraint Solving on StackOverflow [J]. Computer Science, 2019, 46(11): 137-144.
[11] YE Zhi-bin,YAN Bo. Survey of Symbolic Execution [J]. Computer Science, 2018, 45(6A): 28-35.
[12] ZHANG Yong-gang, CHENG Zhu-yuan. Research Progress on Max Restricted Path Consistency Constraint Propagation Algorithms [J]. Computer Science, 2018, 45(6A): 41-45.
[13] LIU Jun, XU Ping-ping, WU Gui-lu, PENG Jie. PSO-ACO Fusion Algorithm Based on Optimal Path Planning in Indoor Environment [J]. Computer Science, 2018, 45(11A): 97-100.
[14] WANG Xin, WANG Ren-fu, QIN Qin, JIANG Hua. Optimization Selection Strategy of Cloud Storage Replica [J]. Computer Science, 2018, 45(10): 300-305.
[15] XIE Yong-hao, GAO Song-feng and DAI Ming-zhu. Virtual Network Mapping Optimization Based on Improved Ant Colony Algorithm [J]. Computer Science, 2017, 44(Z6): 312-313.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!