Testing Concurrent Programs to Achieve High Synchronization Coverage

The effectiveness of software testing is often assessed by mea-suring coverage of some aspect of the software, such as its code. There is much research aimed at increasing code cov-erage of sequential software. However, there has been lit-tle research on increasing coverage for concurrent software. This paper presents a new technique that aims to achieve high coverage of concurrent programs by generating thread schedules to cover uncovered coverage requirements. Our technique first estimates synchronization-pair coverage re-quirements, and then generates thread schedules that are likely to cover uncovered coverage requirements. This pa-per also presents a description of a prototype tool that we implemented in Java, and the results of a set of studies we performed using the tool on a several open-source programs. The results show that, for our subject programs, our tech-nique achieves higher coverage faster than random testing techniques; the estimation-based heuristic contributes sub-stantially to the effectiveness of our technique