Ordered Sequence Testing Criteria for Concurrent
Programs and the Support Tool
Eisuke Itoh*, Yutaka Kawaguchi*, Zengo Furukawa** and Kazuo Ushijima*∗ Dept. of Computer Science and Communication Engineering,∗∗ Educational Center for Information Processing,
Kyushu University.
6-10-1 hakozaki, Higashi-ku, Fukuoka, 812, JAPAN.
E-mail: itou, kawaguti, zengo, ushijima@csce.kyushu-u.ac.jp

Abstract
Testing of programs is important to increase reliability of the programs. Coverage is a ratio of
the number of worked test-events to all test-events,
and it is used as a metric of testing suﬃciency andreliability. The test-events are deﬁned by a testing
criterion.
Some testing criteria are proposed for evaluating testing suﬃciency of sequential programs.
However, the criteria are inadequate for concurrent programs. New testing criteria must be introduced for concurrent programs.
This paper proposes new testing criteria, Ordered Sequence Criteria (OSC for short) for concurrent programs. OSC are concerned with interprocess communication and synchronization. An
OSCk selects k-length sequences of statements related to communication or synchronization. The
sequences should be executed at least once in testing. OSCk presents various levels of testing according to values of k. The OSC2 is reliable fora program which is correct or which includes communication errors. A prototype is implemented forcoverage measuring based on OSC2 .

1Introduction

Testing has been playing an important role inprogram development. Most programs are tested
to increase their reliability. Generally, a programis tested through the following 5 steps.

1. Test case generation.
2. Test data selection.
3. Program testing.
4. Judgment of results.
5. Evaluation of testing suﬃciency.
We are interested in the 5th step; evaluation of
testing suﬃciency. Many testers use coverage for
evaluating testing suﬃciency. Coverage is a ratio of worked test-events to all test-events, whichshould be executed in the program testing step.
Coverage reveals us the testing suﬃciency quantitatively, and the test-events are deﬁned by a testing criterion.
Various testing criteria and tools based on thecriteria have been used to increase conﬁdence forconventional sequential programs. For examples,four well-established testing criteria for sequential programs are statements testing (C0 ), branch
testing (C1 ), path testing (C∞ ), and all-du-path
testing. The path testing criterion (C∞ ) is thestrongest one of all control-ﬂow testing criteria[5].
The all-du-path criterion is the strongest one ofdata-ﬂow path selection criteria[2].
In recent years, concurrent programs are usedpractically. It is obvious that only using testing
criteria proposed for sequential programs is inadequate for evaluating testing reliability of a concurrent program, because the testing criteria proposed for sequential programs do not care the two
characteristics of concurrent program. The ﬁrst
characteristic is nondeterministic execution andthe second is interprocess communication or syn-chronization.
There are some testing criteria for concurrent
programs. Taylor et al.[10] proposed the concept of structural testing of concurrent programs.
They deﬁned the concurrency state and graphas a model of concurrent programs, and propose
some testing criteria based on the concurrency
graph. The concurrency graph consists of nodes
and edges. A node denotes a combination of statesof each process, and an edge denotes state transition. The concurrency state and graph has two
diﬃculties.

we describe a prototype of a coverage measuringsystem and experience of OSC . Finally, we conclude this paper in section 7.

2

Test-events and Coverage

In this section, we present some deﬁnitions ofterms and notations.
The ﬁrst, we deﬁne a set of test-events witha testing criterion. A test-event is an event that
tester ought to execute in the program testing stepand the test-events are deﬁned by a testing criterion.

1. The larger the number of states of each process, the larger the size of the concurrency
graph.

Deﬁnition 1 Test-events set : T E(cri)
Let cri is a testing criterion. We express a set of2
test-events deﬁned by cri as T E(cri).

2. The number of processes must be ﬁxed before the concurrency state and graph is constructed.

For example, let consider a program and testing
criterion C0 (statements testing). The C0 requires
execution of all statements of the program at least
once. The test-events set of the program with C0
isMost concurrent programs generate dynamic
ally process. Testing criteria based on the concurrency graph, therefore, are not always suitable
for testing of concurrent program.
Tai et al.[9] developed an approach to reproducing the entry call arrival and rendezvous sequence (called Syn-sequence) of an Ada programusing an added task for controlling the execution
order. And they proposed a testing criterion basedon the Syn-sequence.
Furukawa et al.[4] proposed a testing criterion
for Ada programs, named rendezvous path testing
criterion. The rendezvous path testing criterion
requires execution of pairs entry call statement
and accept statement. But the rendezvous pathtesting criterion can only apply to Ada programs
testing.
The rest of this paper is organized as follows.
In section 2, we deﬁne some terms and notations. In section 3, we consider an execution sequence of concurrent program based on interleaving model. In section 4, we propose new testing
criteria, named ordered sequence criteria (OSC for
short), and show the test-events of OSC in an example concurrent program. In section 5, we discuss reliability of OSC , discuss feasibility of a testevent of OSC , and study subsumption relations
OSC with another testing criteria. In section 6,

T E(C0 ) = {all statements in the program}.
Next, we deﬁne coverage. Coverage is a ratio of
the number of worked test-events to the numberof test-events in T E. Deﬁnition of coverage Cov
is presented.
Deﬁnition 2 Coverage : Cov
Cov =

|W |
× 100 (%),|T E(Cri)|

where W is a set of worked test-events, T E(Cri)is the set of test-events of a testing criterion Cri,2and | · | represents the size of the set.
Next, we deﬁne a concurrency statement and aset of the concurrency statements.
Deﬁnition 3 Concurrency statement :We call a statement related to interprocess communication or synchronization as a concurrency
statement.

22The instances of concurrency statement are thefork() statement which is an UNIX system call,or entry call and accept statements of Ada rendezvous, or deﬁnition and use statements of ashared variable.
We deﬁne a set consists of concurrency statements, and express this set as Sync.

Proc 1Proc2

1: begin

4: begin

2: m

5: m

3: end1;

0;

6: endFigure 1. A concurrent program.

Deﬁnition 4 Sync :Sync = {all concurrency statements
in a program } .

An execution of a process is described as a paththrough the control ﬂow graph of the process. We
express a path :2
3path =< a1 , a2 , · · · ak > ,Execution Sequences of Concurrent
Programs

where aj ∈Ni , a1 =si , ak =fi and <aj ,aj+1 >∈Ei
(1 ≤ j < k) .
An execution sequence of a program is described
as a sequence of statements in the program, andthis sequence is made from shuﬄing of the paths ofprocesses. Provided that any execution sequencemust satisfy the constraints with the interprocess
communication and synchronization. We express
an execution sequence exc seq :In this section, we consider execution sequencesof a concurrent program on the interleaving
model[1]. The interleaving model have been used
to represent a behavior of a concurrent program
running on a single processor computer.
On the interleaving model, a concurrent program behaves as follows. A concurrent program
consists of some processes, each of which behaves
like a sequential program. The processes communicate and/or synchronize each other. A processor
selects one statement from a process and executes
it. A statement selection is arbitrary except the
selection of concurrency statement.
We express a concurrent program P :exc seq =< b1 , b2 , · · · , bl > ,where bj (1≤j≤l) is a statements in the program,l is the length of exec seq.
We can deﬁne a set of all execution sequences :Exc Seq(P) = {exe seq}.

P = (P1 , P2 , · · · Pn ) ,For example, P is a program in Figure 1. The
P has two processes, Proc1 and Proc2. The pathof Proc1 is <1,2,3>, and the path of Proc2 is<4,5,6>. The set of execution sequences of P
iswhere Pi (1 ≤ i ≤ n) is a process and n is thenumber of processes in P.
We describe a process as a control ﬂow graph.
In the control ﬂow graph, each node represents
a statement, each edge between nodes represents
the ﬂow of control from one node to another. We
express a process Pi :Exc Seq(P) = {< 123456 >,< 124356 >, < 124536 >, < 124563 >,< 142356 >, < 142536 >, < 142563 >,< 145236 >, < 145263 >, < 145623 >,< 412356 >, < 412536 >, < 412563 >,< 415236 >, < 415263 >, < 415623 >,< 451236 >, < 451263 >, < 451623 >,< 456123 > }.

Pi = (Ni , Ei , si , fi ), 1 ≤ i ≤ n ,where Ni is a set of nodes, Ei is a set of edges, si
is a start node and fi is a terminate node of theprocess Pi .
3

of same statements to the T E.

If all exc seqs in a program are executed (covered), it is possible to detect all errors in the
program. However, the number of elements of
Exc Seq is generally inﬁnite, then all exc seqs arenever covered.

4

Proc1

OSC for concurrent programs

In this section, we propose new testing criteria, OSC (Ordered Sequence Criteria). An OSCk
is deﬁned with respect to execution order of concurrency statements.
4.1

Proc2

1

1’

2

2’

3

3’

4

4’

Figure 2. Clone processes. Where a circle denotes anode of a control flow graph. A solid arrow denotes acontrol flow, and a dash arrow denotes communicationor synchronization.

Deﬁnition of OSC

If all execution sequences of a concurrent program are covered in testing, it is possible to detect
all errors in the program. But the execution sequences are so many that it is impossible to cover
all of them. The characteristics of concurrent programs are nondeterministic execution and interprocess communication and synchronization. We
are only interest in the characteristics as a testevent.
In execution of a concurrent program as illustrated in the previous section Figure 1, the difference of the order of execution of concurrency
statements may lead to a diﬀerent output. We
consider that the order of execution of concurrency
statements should be a test-event for concurrent
program testing. In the concrete, we consider thata k-length (k≥1) ordered sequence which consistof concurrency statements should be a test-events.
Some programming languages have functions
for dynamic process generation, for example, task
type of Ada, and fork() system call of UNIX.
Most concurrent programs accordingly have dynamic process generation. The generated processes (clones) have a same source but their behavior may be diﬀerent. If a clone process communicates and/or synchronizes with another clone, as
shown in Figure 2, a same statement but in another process may be executed continuously. Then
it is possible to appear a subsequence which has
a same statement continuously in an execution sequence. Thus, it is necessary to append some ordered sequences which include subsequence consist

Now we propose new testing criteria, named
OSC . An OSCk requires that at least once execution of k-length ordered sequences in testing,which a sequence consists of k concurrency statements.
Deﬁnition 5 OSCk :Suppose that P is a concurrent program andSync is a set of all concurrency statements in P.
Construct k-length ordered sequences with concurrency statements. An OSCk requires executionof the all k-length ordered sequences at least once.

2

Test-events on OSCk (k≥1) is described as the following expression.
T E(OSCk ) = {< s1 , s2 , · · · sk > |si ∈ Sync, 1 ≤ i ≤ k}.
OSCk presents various levels of testing according to values of k. OSCk has the following eﬀects
according to values of k.
1. k = 1
OSC1 requires execution of all concurrency
statements at least once. The set T E(OSC1 )is accordingly equal to Sync. If a programsatisﬁes OSC1 in testing, then all concurrency
statements are tested at least once. Where,a term satisfy means that the coverage of thetesting criterion is 100% in the program testing.
4Consumer

Producer

2. k = 2
OSC2 requires execution of 2-length orderedsequences of concurrency statements at least
once. Here we call a 2-length sequence as anordered pair. If a process communicates orsynchronizes with another process, the communication or synchronization is represented
as an ordered pair in the execution sequence.
If a program satisﬁes OSC2 in testing, then allcommunication and synchronization between
two processes are tested at least once.

1 Product data

2 P(pro)7 P(con)

3 P(exclude)

8 P(exclud)

write data
4 in buffer

9 read datafrom buffer

Buffer5 V(exclude)

10 V(exclude)6

11 V(pro)V(con)

12Consume data

3. k = ∞If a concurrent program has some loops,
the length of an execution sequence may beinﬁnite. And the length of the sequencewhich is extracted concurrency statementsfrom the execution sequence may be also inﬁnite. OSC∞ can be deﬁned as a testing criterion which requires at least once executionof inﬁnite length ordered sequences. However
the OSC∞ is never satisﬁed.

Figure 3. The control flow graph of the ProducerConsumer Problem. A solid arrow denotes an edge,
a dash arrow denotes a communication.

where a number in the expression corresponds toa concurrency statement number in Figure 3. The
size of T E(OSC1 ) is 8 (=|Sync|).
T E(OSC2 ) is

4.2

An example :Consumer Problem

The

Producer-T E(OSC2 ) = {< 2, 2 >, < 2, 3 >, < 2, 5 >, < 2, 6 >,< 2, 7 >, < 2, 8 >, < 2, 10 >, < 2, 11 >,< 3, 2 >, < 3, 3 >, < 3, 5 >, < 3, 6 >,< 3, 7 >, < 3, 8 >, < 3, 10 >, < 3, 11 >,< 5, 2 >, < 5, 3 >, < 5, 5 >, < 5, 6 >,< 5, 7 >, < 5, 8 >, < 5, 10 >, < 5, 11 >,..
.

As further clariﬁcation of the ideas presented
above subsection, we present the test-events of
OSC from the Producer-Consumer Problem. The
control ﬂow graph of the Producer-Consumer
Problem using semaphore is illustrated in the Figure 3. In the program, the Producer process products a data and puts it into a buﬀer, the Consumer
process gets the data from the buﬀer and consumes it. The two processes repeat their works.
The Buﬀer is shared with the Producer and theConsumer.
The set Sync of the program is< 11, 2 >, < 11, 3 >, < 11, 5 >, < 11, 6 >,< 11, 7 >, < 11, 8 >, < 11, 10 >, < 11, 11 >}.
The size of T E(OSC2 ) is 64 (=|Sync|2 ) .
T E(OSC3 ) is
T E(OSC3 ) = {< 2, 2, 2 >, < 2, 2, 3 >, · · ·< 3, 2, 2 >, < 3, 2, 3 >,< 5, 2, 2 >, < 5, 2, 3 >,..
.

Sync = {2, 3, 5, 6, 7, 8, 10, 11}.
Now, we express the T E(OSCk ) (k=1,2,3) of
Producer-Consumer Problem. The test-events according to the value of k are expressed as follows.

< 2, 11, 11 >,< 3, 11, 11 >,< 5, 11, 11 >,< 11, 2, 2 >, < 11, 2, 3 >, · · · < 11, 11, 11 >} .

T E(OSC1 ) is

The size of T E(OSC2 ) is 512 (=|Sync|3 ).

T E(OSC1 ) ={< 2 >, < 3 >, < 5 >, < 6 >,< 7 >, < 8 >, < 10 >, < 11 >},After all, the size of T E(OSCk ) is equal to|Sync|k .
5

5Discussion

Proc1

In this section, we discuss the reliability of OSC
for concurrent programs, the feasibility of testevents on OSC , and the subsumption relations
OSC with another testing criteria.
5.1

Proc2

1

2
error

Figure 4. Communication error.

Reliability

Howden[5] deﬁned a term reliable as follow. If
a program satisﬁes a testing criterion Cri and all
errors in the program are detected, then Cri isreliable for the program. However, the testing criterion which is reliable for any program is only
exhaustive test[11]. Any practical testing criterion
is only reliable for a program which is correct or
includes some particular errors.
To analyze the reliability of OSC for programs,
we analyze errors of concurrent programs. An
error of concurrent programs can be typed asfollows[1, 3].

Proc1

Proc2

1

4

2

3

Proc3

6

5

Figure 5. A concurrent program which have unexecutable ordered sequences. A numbered circle denotes
a concurrency statement.

Let consider communication from statement 1
to 2 shown in Figure 4. And let the communication is an complete communication error. If thecommunication occurs in an execution of the program, the execution order of statement 1 and 2
is only either < 1, 2 > or < 2, 1 >. The two orders must be included in T E(OSC2 ). Therefore,
if the program satisﬁes OSC2 in testing, the error
must be actualized. Hence, OSC2 is reliable fora program which is correct or includes complete
communication errors.

1. Inner process errors.
Inner process errors like the errors of sequential programs.
2. Communication errors.
3. Synchronization errors.
OSC only interest interprocess communicationand synchronization. Therefore, OSC are not reliable for a program which includes inner processerrors. We consider the reliability of OSC for a
program which includes communication errors. A
communication error is further typed as follows.

5.2

Feasibility

In this subsection, we consider the feasibility ofthe test-event of OSC .
There may be many unexecutable events in a
set T E(OSC), because we deﬁne a test-event for
OSCk as a k−tuple of concurrency statements.
Let consider a concurrent program illustrated in
Figure 5 and the OSC2 . T E(OSC2 ) of the programis
T E(OSC2 ) = {< 1, 1 >, < 1, 2 >, < 1, 3 >, · · · , < 1, 6 >< 2, 1 >, < 2, 2 >, < 2, 3 >, · · · , < 2, 6 >..
.

(2-a) Complete communication errors
If a process always communicates error datawith another process, then this communication is a complete communication error.
(2-b) Partial communication errors
If a process often communicates error datawith another process, then this communication is a partial communication error.
OSC2 is reliable for a program which is corrector which includes perfect communication errors.
We proof.
6< 6, 1 >, < 6, 2 >, < 6, 3 >, · · · , < 6, 6 > } .

We are able to consider a super testing criterion, which requires execution of all sequences in
Exc Seq(P) at least once. We deﬁne this super
testing criterion as CC∞ .

In the set T E(OSC2 ), there are many unexecutable ordered sequences. The same number
pairs like < 1, 1 > or < 2, 2 > are never executed.
The ordered pairs like < 1, 3 >, < 2, 1 >, < 3, 1 >,which have reverse or skipping order through acontrol ﬂow graph of a process, are also never executed. The coverage of OSC2 consequently neveramounts to 100% in this program.
The same number pairs and reverse or skipping ordered pairs are introduced for testing of
programs which have dynamic process generation.
If a tested program has no dynamic process generation, then it is necessary to remove the same
number pairs and the reverse or skipping orderedpairs from the test-event set.
5.3

Deﬁnition 7 CC∞ :A testing criterion which requires at least once execution along with all possible execution sequence2of a program in testing.
A set of test-events of CC∞ is described as
T E(CC∞ ) = Exc Seq(P) .
On the CC∞ , the two following subsumption relations stand.
CC∞ ⊃ C∞ ∧ CC∞ ⊃ OSC∞ .

Subsumption

Figure 6 shows all subsumption relations discussed in this subsection. In Figure 6, an arrow
represents a subsumption relation. That is, a testing criterion on tail of an arrow subsumes the criterion which on the arrow head.

In this section, we study subsumption relationsof OSC with another testing criteria. First, wedeﬁne a term subsume as follows.

PPPPPq
)

OSC∞
C∞
?
?
OSC3
C2
?
?
OSC2
C1
?
?
OSC1 
C0
CC∞

Deﬁnition 6 Subsume
If a program satisﬁes a testing criterion A, andthe program also satisﬁes a testing criterion B,
then the A subsumes the B. And we express this2
relation as A ⊃ B .
The following subsumption relations obviously
stand.
Ci+1 ⊃ Ci , i ≥ 1.

Figure 6. Subsumption relations.

OSCi+1 ⊃ OSCi , i ≥ 1.

6

The set T E(C0 ) consists of all statements ina program P, and) the set T E(OSC1 ) is equal
to Sync of P. That is, T E(OSC) is a subset of
T E(C0 ). Hence,

Support Tool

To verify the eﬀectiveness of OSC , we constructa prototype of measuring coverage system[6, 7].
The target of our system is C concurrent programs
which run on UNIX and which include system calls
related with semaphore operations. Since many
C concurrent programs are running on UNIX, we
expect to use our system in testing of many programs.
Concurrent processing of a C concurrent program is implemented through making use of system calls, which are library functions archived inC0 ⊃ OSC1 .
Because OSC2 considers the execution ordersof the concurrency statements in the other process, then the Cm (m≥1) don’t subsume the OSCk(k≥2).
Cm ⊃ OSCk (m ≥ 1, k ≥ 2) .
7

UNIX. There are some system calls for interprocess communication. For instance, semaphore,message pass, FIFO[8] and socket[12]. Since thesemaphore is the most primitive function for concurrent processing, we select it for the ﬁrst target. The semaphore is provided with a systemcall semop on the UNIX SYSTEM V[12].
6.1

Input : P

Source program(C concurrent program)

Program transformation
part

P’

Outline of the system

Transformed sourcecodeF

To note and record worked test-events in a single run, we adopt a program transformation approach. Figure 7 illustrates the outline of our system. Our system is constructed with 3 subsystems.
(1) Program Transformation partThe ﬁrst subsystem’s input is a source program
P ; the outputs are a transformed program P’ anda ﬁle F . This subsystem scans the P . If the subsystem ﬁnds a concurrency statement, then writes
its statement number to the ﬁle F . At the sametime, this subsystem adds a monitoring process
to P and inserts many communication statements
into existing processes. We call the inserted communication statements as a probe. P’ exhibits all
behavior of P.
(2) Execution partThe second subsystem makes the transformed
program P’ run. In the test execution, a single
run will not generate complete coverage for any
testing criterion except on the most trivial of programs. Thus the coverage statistics need to be retained and correlated over a set of runs. In a running, every concurrency statement must request
permission from the monitor through a probe before proceeding; The monitor records the permission duly and permits their proceedings. This subsystem repeats the transformed program runningand appending the activities to the ﬁle seq.
(3) Coverage Calculation part
The third subsystem’s inputs are ﬁle F and seq,
where F is output by the Program Transformation
part and seq is output by the Program Execution part; this subsystem outputs the coverage of
OSC2 . The ﬁle F hold all concurrency statement
numbers in the tested program. This subsystemconstructs a set T E(OSC2 ), at the next, this sub-A file represent
the set of

Program Execution
part

seq

"Sync"

Execution
sequences of "s"(sSync )

Coverage colculation
part

Output : Cov

Coverage

Figure 7. The outline of the measuring coverage system.

system picks up the worked test-events from theﬁle seq and appends these worked events to theset W . For example, if the contents of the ﬁle seq
isseq =< a, b, c, d, e, >,where a, b, c, · · · ∈ Sync. Then, W (worked testevents) is the following ordered pairs.
W = {< a, b >, < b, c >, < c, d >, < d, e >},provided that the each of elements of W has nosame one.
Finally the third subsystem calculates coverage
according to the deﬁnition of coverage.
8

Table 1. Coverages of Producer-Consumer Problem.

Counts of
semop
215
586
1171
2341
3512
9363

The number of
executed test-events
7
16
17
20
21
21

Philosopher1

Table 2. Coverage of Two Dinig Philosopher.

Coverage
(%)
10.9
25.0
26.6
31.2
32.8
32.8

Counts of
semop
82
166
622
1012
1468

5 P(fork2)

2 P(fork2)

6 P(fork1)

EAT

EAT

3 V(fork2)

7 V(fork1)

4 V(fork1)

8 V(fork2)

THINK

THINK

T E(OSC2 ) = {< 1, 1 >, < 1, 2 >, · · · < 1, 7 >, < 1, 8 >,< 2, 1 >, < 2, 2 >, · · ·< 2, 8 >,
..
..
..
.
.
.
< 8, 1 >, < 8, 2 >, · · ·< 8, 8 > }.

Table 2 shows the coverage of OSC2 of Two Dining Philosophers.
Table 1 and Table2 shows us that there arebound of coverage. The reasons of the bound is
the following two things:

Figure 8. Flow graph of Two Dining Philosophers.

6.2

Coverage
(%)
23.4
37.5
43.8
43.8
45.3

Figure 8.

Pilosopher2

1 P(fork1)

The number of
executed test-events
15
24
28
28
29

1. As discussed in section5.2, there are unexecutable test-events in T E(OSC2 ).
It is necessary to remove the unexecutable
test-events from T E.

Experiments of the system

We measured coverage of OSC2 of two concurrent programs, Producer-Consumer Problem andDining philosophers with this system. The two
programs are run on SUN Sparc Station ELC.
At ﬁrst, we measured coverage of OSC2 of
Producer-Consumer Problem. The ﬂow graph of
Producer-Consumer Problem is illustrated in Figure 3. Our system transformed this program torecord all concurrency activities, ran the transformed program several times and calculated coverage. The results of coverage is presented in Table 1.
Next, we measured the coverage of Two Dining
Philosophers. Figure 8 shows the ﬂow graph of
Two Dining Philosophers.
The following expression represents T E(OSC2 )of Two Dining Philosophers, provided that a number in the expression corresponds to a number in

2. In T E(OSC2 ), there are some test-events
which executable but yet covered.
It is necessary to make an test data set to becover the event or necessary to force a execution order.
The program transformation approach must appear an overhead incurred arising from the insertion of the probes and the monitoring process. We
measured the execution time overhead of Producer
Consumer Problem and Table 3 describes the timeoverhead. The time is measured with time command of UNIX.
Table 3 shows that the execution time of P’ hasvery large overhead than that of original. The
reason of the large overhead is structure of monitor. In the system, if a concurrency statement in
P’ is about to execute, then the monitor process9trol of execution is one of the diﬃculties encountered in the testing of concurrent programs. It is
nondeterministic which execution sequence is covered in an running and consequently it is nondeterministic which ordered sequence is covered. The
processor nonpredictably choose one of the statement.
For forcing an ordered sequence in a running ofa concurrent program, we should avail the added
monitor process. Tai et. al.[9] have developed
an approach to reproducing the entry call arrivaland rendezvous sequence of an Ada program using
an added task to control the execution sequence.
Tai’s approach can avail to our system.
It is necessary for forcing an ordered sequence
to improve our system. The improvement is asfollows. The system transforms the tested program P into P’, such that P’ allows as input not
only test data but also ordered sequences of concurrency statements which tester want to cover.
Of course, the P’ may has moniter process andprobes. The added monitor force the execution
order of concurrency statements along with given
ordered sequence. Every concurrency statements
must request permission from monitor throughprobe before proceeding; the monitor permits thestatement’s proceeding which is next statement ofgiven ordered sequence.

Table 3. Execution time table of original ProducerConsumer Problem and the translated program.

Produced Data P (sec) P’ (sec)(byte)
40
0.0†
7.6
365
0.3
57.6
1208
0.7
208.6
† : less than 0.1 sec

Count of
semop
322
2922
9600

write the event in the ﬁle seq. The execution time
is consequently increased by the ﬁle inputs. It isnecessary to tune up recording part of the added
monitoring process.
6.3

An strategy for eﬀective use of OSC

Described in above section, the coverage of OSC
may not be 100%. It is necessary to devise the effective use of the coverage for evaluation of testing
suﬃciency. To use the coverage of OSC eﬃciency,
we recommend a strategy, in which there is thethree steps. We show the steps.
First step:
Execute testing a concurrent program with aset of test data and measure the coverage of OSC.
If the coverage is not 100%, then the tester list up
the yet covered test-events.

7

Conclusion

In this paper, we proposed new testing criteria
OSC for evaluation of testing reliability. The OSC
is simple and portable testing criteria for using intesting. The OSC is fundamentally based on thesource code of a concurrent program, therefore,
the number of test-events must be ﬁnite. We also
discussed the reliability of the OSC for a concurrent program. The OSC2 is reliable for a program
which is correct or which includes complete communication errors. Furthermore we discussed thesubsumption relation OSC with another testing
criteria. We also implemented a measuring coverage system and measured the coverage of OSC2 on
two concurrent programs with this system. Since
OSC2 may request execution with unexecutableordered sequences, the coverage of OSC2 may not

Second step:
Decide every yet covered test-event whether it isan executable event or not. If a test-event is not
executable, then remove it from the test-events
set, else remain it.
Third step:
To cover the remainder events, run the programand measure coverage again. But to cover the remainder events, it needs two works, test data selection and forcing an execution ordered sequence.
Let consider the test data selection. Test data
commonly are not able to select automatically,
then the tester has to select test data by oneself.
Next, let consider the forcing execution. Con10

References

be 100%. We consider a strategy for eﬀective use
the coverage of OSC.
There are some future problems:• Improve the coverage evaluate system.

[1] Ben-Ari, M. : Principles of Concurrent Programming, Prentice Hall International, Inc.
1982.

– Apply another system calls.
Our system only correspondence
semaphore (semop system call) on
UNIX SYSTEM V. There are many
interprocess communication systemcall on UNIX. It is necessary to deal
with these functions.
Now, we are
improving our system to record an
function socket, which is a interprocess
communication interface on BSD UNIX.

[2] Clarke, L. A., Podgurski, A., Richardson, D.
J. and Zeil, S. J. : A Formal Evaluation of
Data Flow Path Selection Criteria, IEEE Trans.
Softw. Eng., Vol.15, No.11, pp.1318-1332, 1989.
[3] Furukawa, Z. and Ushijima, K. : A Testing
Method for Concurrent Programming, Proc. of
6th JSSST, pp.185-188, 1989 (in Japanese).

– Expand length of ordered sequence.
Our system only measures coverage of
OSC2 . It is necessary to improve the system to measure coverage of OSCk (k ≥3).

[4] Furukawa, Z. and Ushijima, K. : Reliability of
the Rendezvous Path Testing Criterion for Ada
Concurrent Programs, Trans. IEICE, Vol.J75D-I, No.5, pp.288-297, 1992 (in Japanese).
[5] Howden, W. E. : Reliability of the Path Analysis Testing Strategy, IEEE Trans. Softw. Eng.,
Vol.SE-3, No.4, pp.226-278, 1976.

• Expansion of the OSC .
– Remove unexecutable sequences.
As discussed in subsection5.2, the OSCk
may request executions of unexecutableordered sequences. It is necessary to
remove the unexecutable ordered sequences from the test-events set.

[6] Itoh, E., Kawaguchi, Y., Furukawa, Z. andUshijima, K. : Testing Criteria for Interprocess
Communication in C Concurrent Programs.
IPSJ SIG Notes, 93-SE-90, pp.9-16, 1993. (inJapanese)– Forcing an ordered sequence.
The system must allow the ordered sequences as input for forcing ordered sequences of concurrency statements.

[7] Kawaguchi, Y., Itoh, E., Furukawa, Z. andUshijima, K. : On constructing testing reliability evaluation system with ordered sequence
testing criteria, IPSJ SIG Notes, 96-SE-14,
pp.107-114, 1994 (in Japanese).

• Distinction all dynamically generated processes in program.
Our system is constructed on UNIX. On
UNIX, any running process has an uniqueprocess numbers. For utilizing the process
number, it is possible to more deﬁnite test.

[8] Rockkind, M. j. : Advanced UNIX Programming, Prentice Hall International, Inc. 1985.
[9] Tai, K. C., Carver, R. H. and Obaid, E. E. :Debugging Concurrent Ada Programs by Deterministic Execution, IEEE Trans. Softw. Eng.,
Vol.17, No.1, pp.45-63, 1992.

Acknowledgment
We thank Prof.
J. Cheng, Prof.
H.
Taniguchi for encouragement and valuable comments. We also thank T.Katayama, K.Simozono
and H.Kashima for discussion about testing andsystem implementation.

[10] Taylor, R. N., Levine, D. L. and Kelly, C. D.
: Structural Testing of Concurrent Programs,
IEEE Trans. Softw. Eng., Vol 18, No.3, pp.206215, 1992.
11

[11] Weyuker, E. J. : The Complexity of Data
Flow Criteria for Test Data Selection, Information Processing Letters, Vol.19, pp.103-109,
1984.
[12] Leﬄer, S. J., Mckusuck, M. K., Karels, M. J.
and Quarterman, J. S. : The Design and Implementation of the 4.3BSD UNIX Operating System, Addison-Wesley Publishing Co. Inc. 1989.

12