BIBLIOS

Document type
Conference papers

Document subtype
Extended abstract/Short paper

Title
Augmenting Search-based Techniques with Static Synthesis-based Input Generation

Participants in the publication
Paulo Santos (Author)
LASIGE
Jose Campos (Author)
Dep. Informática
LASIGE
Christopher S. Timperley (Author)
UNIVERSIDADE DE CARNEGIE MELLON
Alcides Fonseca (Author)
Dep. Informática
LASIGE

Summary
Automated test generation helps programmers to test their software with minimal intervention. Automated test generation tools produce a set of program inputs that maximize the possible execution paths, presented as a test coverage metric. Proposed approaches fall within three main approaches. Search-based methods work on any program by randomly searching for inputs that maximize coverage. Heuristic-based methods can be used to have better performance than pure random-search. Constraint-based methods use symbolic execution to restrict the random inputs to those guaranteed to explore different paths. Despite making the execution slower and supporting very few programs, these methods are more efficient because the search space is vastly reduced. The third approach combines the previous two to support any program and takes advantage of the space search reduction when able, at the cost of slower execution. We propose a fourth approach that also refines search-based with constraints. However, instead of requiring a slower symbolic execution when measuring coverage, constraints are statically extracted from the source code before the search procedure occurs. Our approach supports all programs (as in Search-Based) and reduces the search-space (as in Constraint-based methods). The innovation is that static analysis occurs only once and, despite being less exact that symbolic execution, it can significantly reduce the execution cost in every coverage measurement. This paper introduces this approach, describes how it can be implemented and discusses its advantages and drawbacks.


Institution
FACULDADE DE CIÊNCIAS DA UNIVERSIDADE DE LISBOA

Event
2021 IEEE/ACM 14th International Workshop on Search-Based Software Testing (SBST)

Publication Identifiers

Address
Madrid, Spain

Publisher
IEEE


Document Identifiers
DOI - https://doi.org/10.1109/sbst52555.2021.00009
URL - http://dx.doi.org/10.1109/sbst52555.2021.00009

Keywords
Software testing Synthesizers Static analysis Evolutionary Computation