Computer Science

Computer Science ›› 2021, Vol. 48 ›› Issue (12): 107-116.doi: 10.11896/jsjkx.210200052

• Computer Software • Previous Articles     Next Articles

Program Complexity Analysis Method Combining Evolutionary Algorithm with Symbolic Execution

ZHOU Sheng-yi1,2, ZENG Hong-wei 1   

  1. 1 School of Computer Engineering and Science,Shanghai University,Shanghai 200444,China
    2 Shanghai Key Laboratory of Computer Software Evaluating and Testing,Shanghai 201112,China
  • Received:2021-02-04 Revised:2021-07-07 Online:2021-12-15 Published:2021-11-26
  • About author:ZHOU Sheng-yi,born in 1997,postgraduate.Her main research interests include program analysis and so on.
    ZENG Hong-wei,born in 1966,Ph.D,professor,Ph.D supervisor,is a senior member of China Computer Federation.His main research interests include software formal method and software testing.
  • Supported by:
    National Key R & D Program of China(2020YFB1006003).

PDF (PC)

738

Abstract: The worst case execution path is an important indicator of program complexity,which helps to discover possible complexity vulnerabilities in the system.In recent years,the application of symbolic execution in program complexity analysis has made great progress,however,the existing methods have the problems of poor generality and long analysis time.EvoWca,an evolutionary algorithm for worst-case path detection,is proposed in this paper.Its core idea is to use known worst-case path characteristics of programs at smaller input sizes to guide the construction of initial path sets at larger input sizes.Evolutionary algorithm is then simulated to combine,mutate,and select routes iteratively,and the worst path detected within the search range approximates the path corresponding to the worst time complexity.Based on this algorithm,a prototype tool EvoWca2j for program complexity analysis is implemented.The tool and existing technologies are used to explore the worst path and evaluate the execution efficiency of a group of Java programs.The experimental results show that,compared with the existing methods,EvoWca2j'sgenerality and exploration efficiency are significantly improved.

Key words: Complexity analysis, Evolutionary algorithm, Path detection, Symbolic execution, Worst case execution path

CLC Number: 

  • TP311.5
[1]ANDALAM S,ROOP P S,GIRAULT A,et al.A Predictable Framework for Safety-Critical Embedded Systems[J].IEEE Transactions on Computers,2014,63(7):1600-1612.
[2]HANSEN J,HISSAM S A,MORENO G A.Statistical-Based WCET Estimation and Validation[C]//International Workshop on Worst-case Execution Time Analysis.DBLP,2009.
[3]FERDINAND C.Worst case execution time prediction by static program analysis[C]//18th International Parallel and Distributed Processing Symposium.IEEE,2004.
[4]LUCKOW K,KERSTEN R,PASAREANU C.Symbolic Complexity Analysis Using Context-Preserving Histories[C]//2017 IEEE International Conference on Software Testing,Verification and Validation (ICST).IEEE,2017.
[5]AQUINO A,DENARO G,SALZA P.Worst-Case Execution Time Testing via Evolutionary Symbolic Execution[C]//2018 IEEE 29th International Symposium on Software Reliability Engineering (ISSRE).IEEE,2018.
[6]NOLLER Y,KERSTEN R,PÂSÂREANU C S.Badger:com- plexity analysis with fuzzing and symbolic execution[C]//Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis.2018:322-332.
[7]ZHANG J,ZHANG C,XUAN J F,et al.Recent Progress in Program Analysis[J].Journal of Software,2019,30(1):80-109.
[8]CADAR C,SEN K.Symbolic execution for software testing: three decades later[J].Communications of the ACM,2013,56(2):82-90.
[9]BALDONI R,COPPA E,DELIA D C,et al.A Survey of Symbolic Execution Techniques[J].ACM Computing Surveys,2018,51(3):1-39.
[10]CREPINSEK M,LIU S H,MERNIK M.Exploration and ex- ploitation in evolutionary algorithms:A survey[J].ACM Computing Surveys,2013,45(3):35.
[11]JANSEN T,WEGENER I.The Analysis of Evolutionary Algorithms－A Proof that Crossover Really Can Help[J].Algorithmica,2002,34(1):47-66.
[12]STEPHENS N,GROSEN J,SALLS C,et al.Driller:Augmenting Fuzzing Through Selective Symbolic Execution[C]//Network and Distributed System Security Symposium.2016.
[13]GODEFROID P,LEVIN M,MOLNAR D.Automated whitebox fuzz testing[C]//Proceedings of the Network and Distributed System Security Symposium(NDSS 2008).San Diego,California,USA,DBLP,2008.
[14]AVGERINOS T,REBERT A,CHA S K,et al.Enhancing symbolic execution with veritesting[J].Communications of the ACM,2016,59(6):93-100.
[15]YI Q,YANG Z,GUO S,et al.Eliminating Path Redundancy via Postconditioned Symbolic Execution[J].IEEE Transactions on Software Engineering,2017,44(1):25-43.
[16]HAVELUND K,PRESSBURGER T.Model checking JAVA programs using JAVA PathFinder[J].International Journal on Software Tools for Technology Transfer,2000,2(4):366-381.
[17]ANAND S,PASAREANU C S,VISSER W.JPF-SE:A symbo- lic execution extension to Java pathfinder[C]//Tools & Algorithms for the Construction & Analysis of Systems,Internatio-nal Conference,Tacas,Held As Part of the Joint European Conferences on Theory & Practice of Software.Braga,Portugal,Proceeding,2007.
[18]MOFFETT Y,DINGEL J,BEAULIEU A.A.Verifying Protocol Conformance Using Software Model Checking for the Mo-del-Driven Development of Embedded Systems[J].IEEE Transac-tions on Software Engineering,2013,39(9):1307-1325.
[19]BAI G,YE Q,WU Y,et al.Towards Model Checking Android Applications[J].IEEE Transactions on Software Engineering,2017,44(6):595-612.
[20]BURNIM J,JUVEKAR S,SEN K.WISE:Automated test ge- neration for worst-case complexity[C]//2009 IEEE 31st International Conference on Software Engineering.IEEE,2009:463-473.
[1] SUN Gang, WU Jiang-jiang, CHEN Hao, LI Jun, XU Shi-yuan. Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance [J]. Computer Science, 2022, 49(6): 297-304.
[2] LI Li, LI Guang-peng, CHANG Liang, GU Tian-long. Survey of Constrained Evolutionary Algorithms and Their Applications [J]. Computer Science, 2021, 48(4): 1-13.
[3] ZHAO Yang, NI Zhi-wei, ZHU Xu-hui, LIU Hao, RAN Jia-min. Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform [J]. Computer Science, 2021, 48(11A): 30-38.
[4] ZHU Han-qing, MA Wu-bin, ZHOU Hao-hao, WU Ya-hui, HUANG Hong-bin. Microservices User Requests Allocation Strategy Based on Improved Multi-objective Evolutionary Algorithms [J]. Computer Science, 2021, 48(10): 343-350.
[5] ZHANG Qing-qi, LIU Man-dan. Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery [J]. Computer Science, 2020, 47(8): 284-290.
[6] CHEN Meng-hui, CAO Qian-feng and LAN Yan-qi. Heuristic Algorithm Based on Block Mining and Recombination for Permutation Flow-shop Scheduling Problem [J]. Computer Science, 2020, 47(6A): 108-113.
[7] YANG Hao, CHEN HONG-mei. Mixed-sampling Method for Imbalanced Data Based on Quantum Evolutionary Algorithm [J]. Computer Science, 2020, 47(11): 88-94.
[8] XIE Teng-yu,ZHOU Xiao-gen,HU Jun,ZHANG Gui-jun. Contact Map-based Residue-pair Distances Restrained Protein Structure Prediction Algorithm [J]. Computer Science, 2020, 47(1): 59-65.
[9] HUANG Zhao,HUANG Shu-guang,DENG Zhao-kun,HUANG Hui. Automatic Vulnerability Detection and Test Cases Generation Method for Vulnerabilities Caused by SEH [J]. Computer Science, 2019, 46(7): 133-138.
[10] GENG Huan-tong, HAN Wei-min, ZHOU Shan-sheng, DING Yang-yang. MOEA/D Algorithm Based on New Neighborhood Updating Strategy [J]. Computer Science, 2019, 46(5): 191-197.
[11] FANG Hao, WU Li-fa, WU Zhi-yong. Automatic Return-to-dl-resolve Exploit Generation Method Based on Symbolic Execution [J]. Computer Science, 2019, 46(2): 127-132.
[12] JIN Ting, TAN Wen-an, SUN Yong, ZHAO Yao. Social Team Formation Method Based on Fuzzy Multi-objective Evolution [J]. Computer Science, 2019, 46(2): 315-320.
[13] LIU Xin-ping, GU Chun-hua, LUO Fei, DING Wei-chao. Improved NSGA-II Algorithm Based on Loser Group and Hybrid Coding Strategy [J]. Computer Science, 2019, 46(10): 222-228.
[14] YE Zhi-bin,YAN Bo. Survey of Symbolic Execution [J]. Computer Science, 2018, 45(6A): 28-35.
[15] LI Hang, ZANG Lie, GAN Lu. Search of Speculative Symbolic Execution Path Based on Ant Colony Algorithm [J]. Computer Science, 2018, 45(6): 145-150.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.