Worst-Case Execution Time Testing via Evolutionary Symbolic Execution
Additional information
Authors
Type
Article in conference proceedings
Year
2018
Language
English
Abstract
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.
Conference proceedings
Proceedings of the 29th International Symposium on Software Reliability Engineering (ISSRE)
Month
October
Start page number
76
End page number
87
Meeting name
IEEE International Symposium on Software Reliability Engineering (ISSRE)
Meeting place
Memphis, Tennessee, USA
Meeting date
15-18 October 2018
ISSN
2332-6549
