Structural testing for message-passing concurrent programs: an extended test model

Developing high-quality, error-free message-passing concurrent programs is not trivial. Although a number of different primitives with associated semantics are available to assist such development, they often increase the complexity of the testing process. In this paper, we extend our previous test model for messagepassing programs and present new structural testing criteria, taking into account additional features used in this paradigm, such as collective communication, non-blocking sends, distinct semantics for non-blocking receives, and persistent operations. Our new model also recognizes that sender primitives cannot always be matched with every receive primitive. This improvement allows us to remove statically a significant number of infeasible synchronization edges that would otherwise have to be analyzed later by the tester. In this paper, the test model is presented using the Message-Passing Interface standard; however, our new model has been designed to be flexible, and it can be configured to support a range of different messagepassing environments or languages. We have carried out case studies showing the applicability of the new test model to represent message-passing programs and also to reveal errors, mainly those errors related to inter-process communication. In addition to increasing the number of features supported by the test model, we have also reduced the overall cost of testing significantly. Our case studies suggest that the number of synchronization edges can be reduced by up to 93%, mainly by eliminating infeasible edges between unmatchable communication primitives. The main contribution of the paper is to present a more flexible test model that provides improved coverage for message-passing programs and at the same time reduces the cost of testing significantl