Test Case Generation of Concurrent Programs Based on Event Graph

This paper attempts to generate test cases for concurrent programs based on event graph. Through the analysis of state transition of event graph, sub-event-graphs can be generated. Each sub-event-graph corresponds to a test case. We may get benefits from this method in the following. (1) While executing the test case, we can monitor the state transition. (2) Every sub-event-graph is an execution path, or a simulation, thus all test cases are feasible. (3) Since the number of states in the event graph is finite, it is not likely to hit state explosion problem in the test generation process.

1 Introduction

A concurrent program specifies two or more processes (or threads) that cooperate in performing a task. Each process is a sequential program that executes a sequence state-ments. The processes cooperate by communicating using variables or message passing. One way to check that a concurrent program correctly implements its specification is to execute the program with a set of test sequences. A test sequence represents a sequence of actions performed by the concurrent processes in the program. These actions are often interprocess communications such as sending and receiving messages.