Achieving High MAP-Coverage Through Pattern Constraint Reduction

doi:10.1109/TSE.2022.3144480

Achieving High MAP-Coverage Through Pattern Constraint Reduction

2023-01-01

2

OA

AI

DOI：10.1109/TSE.2022.3144480

Original

Original request for help

Save

Abstract

En 中文

Testing multi-threaded programs is challenging due to the enormous space of thread interleavings. Recently, a code coverage criterion for multi-threaded programs called MAP-coverage has been proposed and shown to be effective for testing concurrent programs. Existing approaches for achieving high MAP-coverage are based on random testing with simple heuristics, which is ineffective in systematically triggering rare thread interleavings. In this study, we propose a novel approach called pattern constraint reduction (PCR), which employs optimized constraint solving to generate thread interleavings for high MAP-coverage. The idea is to iteratively encode and solve path conditions to generate thread interleavings which are guaranteed to improve MAP-coverage. Furthermore, we effectively apply interpolation techniques to reduce the efforts of constraint solving by avoiding solving infeasible constraints. The experiment results on 20 benchmark programs show that our approach complements existing random testing based approaches when there are rare failure-inducing interleaving in the whole search space. Specifically, PCR finds concurrency bugs faster in 18 out of 20 programs, with an average speedup of 4.2x and a maximum speedup of 11.4x.

Keywords:

Computer bugs

Concurrent computing

Instruction sets

Programming

Message systems

Systematics

Sun

Concurrency bug detection

constraint solving

coverage criteria

thread-safe class

Achieving High MAP-Coverage Through Pattern Constraint Reduction

Abstract

Journal

Organization