Worst-Case Execution Time Testing via Evolutionary Symbolic Execution
Aquino A., Denaro G., Salza P.
Article in conference proceedings
Worst-case execution time testing amounts to constructing a test case triggering the worst-case execution time of a program, and has many important applications to identify, debug and fix performance bottlenecks and security holes of programs. We propose a novel technique for worst-case execution time testing combining symbolic execution and evolutionary algorithms, which we call "Evolutionary Symbolic Execution", that (i) considers the set of the feasible program paths as the search space, (ii) embraces the execution cost of the program paths as the fitness function to pursue the worst path, (iii) exploits symbolic execution with random path selection to collect an initial set of feasible program paths, (iv) incrementally evolves by steering symbolic execution to traverse new program paths that comply with execution conditions combined and refined from the currently collected program paths, and (v) periodically applies local optimizations to the worst currently identified program path to speed up the identification of the worst path. We report on a set of initial experiments indicating that our technique succeeds in generating good worst-case execution time test cases for programs with which existing approaches cannot cope.
Proceedings of the 29th International Symposium on Software Reliability Engineering (ISSRE)
Start page number
End page number
IEEE International Symposium on Software Reliability Engineering (ISSRE)
Memphis, Tennessee, USA
15-18 October 2018