Facilitating program performance profiling via evolutionary symbolic execution. (21st November 2019)

• Record Type: Journal Article
• Authors: Aquino, Andrea; Braione, Pietro; Denaro, Giovanni; Salza, Pasquale
• Other Names: Natella Roberto guestEditor.; Ghosh Sudipto guestEditor.
• Is Part Of: Software testing, verification & reliability. Volume 30:Number 2(2020)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2019-11-21
• Subjects: genetic algorithms -- software engineering -- symbolic execution -- worst‐case execution time; Computer software -- Testing -- Periodicals; Computer software -- Verification -- Periodicals; Computer software -- Reliability -- Periodicals; 005.14
• DOI: 10.1002/stvr.1719
• Languages: English
• ISSNs: 0960-0833

Abstract

Summary: Performance profiling can benefit from test cases that hit high‐cost executions of programs. In this paper, we investigate the problem of automatically generating test cases that trigger the worst‐case execution of programs and propose a novel technique that solves this problem with an unprecedented combination of symbolic execution and evolutionary algorithms. Our technique, which we refer to as 'Evolutionary Symbolic Execution', embraces the execution cost of the program paths as the fitness function to pursue the worst execution. It defines an original set of evolutionary operators, based on symbolic execution, which suitably sample the possible program paths to make the search process effective. Specifically, our technique defines a memetic algorithm that (i) incrementally evolves by steering symbolic execution to traverse new program paths that comply with execution conditions combined and refined from the currently collected worse program paths and (ii) periodically applies local optimizations to the execution conditions of the worst currently identified program path to further 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 test cases for programs with which existing approaches cannot cope. Also, we show that, as far as the problem of generating worst‐case test cases is concerned, the distinguishing evolutionary operators based on symbolic execution that we define in this paper are more effective than traditional operators that directly manipulate the program inputs. Abstract : Performance profiling can benefit from test cases that hit high‐cost executions of programs. In this paper, we investigate the problem of automatically generating test cases that trigger the worst‐case execution of programs and propose a novel technique that solves this problem with an unprecedented combination of symbolic execution and evolutionary algorithms. We report on a set of initial experiments indicating that our method succeeds in generating good worst‐case test cases for programs with which existing approaches cannot cope.