Program Complexity Analysis Method Combining Evolutionary Algorithm with Symbolic Execution

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.

Keywords

• complexity analysis|symbolic execution|evolutionary algorithm|path detection|worst case execution path