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 numberrnof different primitives with associated semantics are available to assist such development, they often increasernthe complexity of the testing process. In this paper, we extend our previous test model for messagepassingrnprograms and present new structural testing criteria, taking into account additional features used inrnthis paradigm, such as collective communication, non-blocking sends, distinct semantics for non-blockingrnreceives, and persistent operations. Our new model also recognizes that sender primitives cannot alwaysrnbe matched with every receive primitive. This improvement allows us to remove statically a significantrnnumber of infeasible synchronization edges that would otherwise have to be analyzed later by the tester.rnIn this paper, the test model is presented using the Message-Passing Interface standard; however, our newrnmodel has been designed to be flexible, and it can be configured to support a range of different messagepassingrnenvironments or languages. We have carried out case studies showing the applicability of the newrntest model to represent message-passing programs and also to reveal errors, mainly those errors related torninter-process communication. In addition to increasing the number of features supported by the test model,rnwe have also reduced the overall cost of testing significantly. Our case studies suggest that the numberrnof synchronization edges can be reduced by up to 93%, mainly by eliminating infeasible edges betweenrnunmatchable communication primitives. The main contribution of the paper is to present a more flexible testrnmodel that provides improved coverage for message-passing programs and at the same time reduces the costrnof testing significantly