AVATAR - Automated coVerAge-based Testing via static-dynamic Abstraction Refinement and coarsening

Structural testing coverage is a proxy measure of the adequacy of testing that can be useful to both software quality managers and tester designers. Despite this, few of the many structural coverage criteria studied in academia find common application in industrial practice, due to both the scarce availability of automated support for generating test suites with high coverage and the penalizing impact of infeasible program elements. This project aims to define a new generation of structural testing approaches to automatically generate test suites with high structural coverage, and correctly account for a relevant number of infeasible elements of the coverage domain. This project will suitably exploit the combination of dynamic and static analysis techniques. Static program analyses quickly explode in complexity and become intractable, while dynamic program analyses scale to large programs, but do not cover the state space exhaustively. Recently static and dynamic analyses have been combined to exploits the positive synergy of observed facts (brought by dynamic analysis) and deductions that can be generalized from these (brought by static analysis). This project will integrate data from concrete executions of the program with the statically analysis of an abstract (over-approximated) and finite model of the program state space. It will study the use of abstraction refinement and coarsening (ARC) that we have introduced in a recent paper, to re-aggregate the states generated by the refinement process as the analysis of the program progresses. Our preliminary results based on combining abstract refinement with concolic execution to refine branch coverage are very encouraging. This project will exploit these results by exploring the applicability of coarsening to the combination of other static and dynamic analysis techniques to refine complex coverage criteria. The detailed goals of the project are to (1) define new approaches to structural testing to achieve accurate coverage according to different classes of coverage criteria, (2) define new program analysis algorithms that combine static and dynamic analysis to efficiently generate test suites and analyze infeasible targets throughout industrial-size programs, (3) define new reference abstractions that allow for optimizing the trade-off between precision and costs of the analysis for different classes of structural testing criteria, and (4) study the effectiveness of different coverage criteria by evaluating to what extent the test suites that satisfy the coverage criteria can expose program defects, and by comparing the effectiveness across different classes of coverage criteria.