Testing of Concurrent Program: A Reach-ability Testing Approach
Mr. Punit Kumar1, Dr. Shukhdeep Singh2
1M.Tech, CSE, DCR University of Science & Technology, Sonepat, Haryana, India
2Assistant Professor, CSE, DCR University of Science & Technology, Sonepat, Haryana, India
Abstract
To increase the speed of computers we are increasing the efficiency of the hardware by using multiple cores and also develop the concurrent program. With the development of the concurrent program we have increased the execution speed but it becomes very difficult to test these programs because of non-deterministic running behavior of these programs. So we cannot test these using sequential testing techniques. Different testing techniques have been proposed for testing the concurrent programs. This paper reviews some of the testing strategies for testing the concurrent programs.
Keywords: Testing of concurrent program, Synchronization Sequence, Multithreaded.
Introduction
Testing is the process of executing the program in order to detect errors. The conventional approach to testing a program P is to execute P with each selected test input once and then compare the test results with the expected results. If an execution of P with input X produces an incorrect result, then after the error has been located and corrected, P is executed with input X in order to verify that the error has been corrected. P is also executed with some or all of the previously successful inputs in order to verify that no new errors have been introduced. (Such testing, called regression m, is also needed after P has been modified for enhancement.)[1]
It is generally accepted that it is much harder to test concurrent programs than sequential ones, mostly because of the potentially indeterminate behavior of concurrent programs. Because of this indeterminacy, errors are more difficult to expose, test results are more difficult to analyze, and tests are more difficult to control, making them generally irreproducible.[2]
The nondeterministic execution behavior of program P creates the following testing problems: [1]
(1) When testing P with input X, a single execution is insufficient to determine the correctness of P with input X. Even if P with input X has been executed successfully many times, it is possible that a future execution of P with input X will produce an incorrect result.
(2) After P has been modified for correcting the error detected by an execution of P with input X, one or more successful executions of P with input X do not imply that the detected error has been corrected.
(3) After P has been modified for correction or enhancement, successful executions of P with previously tested inputs do not imply that the modification does not introduce new errors.
After literature survey we deduced the different testing technique to test the concurrent Program:-
- Testing based on static analysis.
- Testing based on deterministic execution.
- Testing based on NondeterministicExecution.
- Testing based on reach-ability testing technique.
- Testing based on execution trace.
- Mutation Based Testing of concurrent Program
Descriptions of these techniques are given as follows:
1. Testing based on static analysis
Taylor proposed this is Structural or white-box testing method [3]. This technique applies the traditional structural testing strategies to the concurrent programs. Each program unit defines a flow graph. Each statement in unit is represented by node in the graph and each transfer of control is represented by a directed edge.
Taylor’s criteria have two major born defects. Namely, it is complicate to generate concurrency graph for a concurrent program and difficult to monitor concurrency states involved in this execution.
Weiss's work is about the theoretical foundation of concurrent program testing. He simulated the execution behavior of a concurrent program by a set of serializations which are sequential programs from merging the bodies of thetasks in the program. However, to generate serializations for a concurrent program is difficult andtedious, especially when the number of tasks is large.
Ren-Dar Yang and Chyan-GoeiChungt[4]separately model the static and dynamic structure of a concurrent program. The static structure corresponds to the syntactic view of execution behavior, which is the possible execution flow of the statements, and the dynamic structure corresponds to the run-time view, which is the possible rendezvous relationship among concurrent tasks. We use flow-graph to represent the static structure and rendezvous graph to represent the dynamic structure of a concurrent program.
2. Testing based on deterministic execution
Tai, Carver and Obaid proposed a deterministic execution technique to test and debug the concurrent programs.[1]
The deterministic execution testing approach is defined as follows:
(1) Select a set of tests, each of the form (X,S), where X and S are an input and a SYN-sequence of P respectively.
(2) For each selected test (X,S),
(2.1) Determine whether or not S is feasible for P with input X by attempting to force a deterministicexecution of P with input X according to S, and
(2.2) if S is feasible examine the result of this execution. Note that in this testing approach, a test for P is not just an input of P; it consists of an input and a SYN-sequence of P.
The deterministic execution testing approach provides the following advantages over single or multiple execution testing:
(a) This approach allows the use of carefully selected SYN-sequences to test a concurrent program P. Notice that singular or multiple executions testing of P exercises feasible SYN-sequences and can detect the existence of invalid feasible Sq-sequences of P, but not the existence of valid, infeasible SYN-sequences Of P. Deterministic execution testing can detect both types of errors.
(b) Assume that an error is detected by an execution of P. After an attempt has been made to correct the error, P can be tested with the input and SYN-sequence of this erroneous execution in order to make sure that the error has been corrected.
(c) After P has been modified for correction or enhancement,P can be tested with the inputs and SYN-sequences of previous executions of P in order to make sure that themodification does not introduce new errors.
Problems in Deterministic Execution Testing[1]
Problems in Deterministic Execution Testing and Debugging of Concurrent Programs are as follows:
SYN-Sequence Definition Problem: A SYN-sequence of a concurrent program P can be defined in terms of synchronization constructs supported by the concurrent language in which P is written or by the underlying operating system. Different forms of SYN-sequences of a concurrent program may be needed for the purposes of testing and debugging.
SYN-Sequence Collection Problem: As mentioned earlier, it is necessary to collect the SYN-sequence of an execution of a concurrent program for the purposes of testing and debugging.
SYN-Sequence Replay Problem: An execution of a concurrent program P with input X can be repeated by forcing the SYN-sequence of this execution during an execution of P with input X. The replay problem deals with how to force the execution of a feasible SYN-sequence.
SYN-Sequence Selection Problem:To perform deterministicexecution testing of a concurrent program P, we need to selectSYN-sequences according to the specification and implementation of P.
SYN-Sequence Feasibility Problem: For a selected SYN-sequence of P with input X, we determine whether it is feasible for P with input X.
Approaches for Software testing under deterministic testing [5]
Two basic approaches to software testing are:-
1. Specification-based
2. Program-based testing.
Description of these approaches is given as:-
1. Specification-based
A number of languages and models for specifying concurrency have been developed. In this approach, aspecification is written in the form of an abstract program,which describes the valid behavior of a program without describing particular implementation mechanisms that achieve the required behavior.
Various styles for writing abstract programs were discussed as :
The state-oriented style, the state space of the program is explicitly defined. Program behavior is defined as a collection of alternative sequences of events and a changing state.
The constraint-oriented style is to provide a set of sequencing constraints, each describing separate restrictions on a subset of the events. A complete program is formed by combining all of these constraints.
Constraints-Based Specification of Concurrent Programs has three notations:
Task Specification Language (TSL)
TSL constraints describe patterns of events that must occur or must not occur during a program's execution. For a given event sequence S, when the activating event matches an event of S,
- If the specified event matches an event of S before the terminating event then the TSL constraint is satisfied.
- If the terminating event matches an event of S before thespecified event, the TSL constraint is violated.
- If the specified and terminating events match the same event of S,
- If “until" is used, the TSL constraint is satisfied.
- If “before" is used, the TSL constraint is violated.
The CSPE (Constraints on Succeeding and Preceding Events)
Wedescribe three basic types of constraints on succeeding events for a concurrent program unit U. Each constraint is preceded by a constraint operator "op" which is one of the following: "a" for "always", "p" for "possibly", or "-" for "never". Informally,
- a[E1 -> E2]U denotes that during an execution of U, immediately after an occurrence of event E1, an occurrence of event E2 is always valid (but E2 need not necessarily occur).
- ~[E1 -> E2]U denotes that during an execution of U, immediately after an occurrence of event E1, an occurrence of event E2 is never valid.
- p[El -> E2]U denotes that during an execution of U, immediately after an occurrence of event El, an occurrence of event E2 is possibly valid (i.e., neither always valid nor never valid). p[E1 -> E2] is often associated with the necessary and sufficient condition C under which event E2 can immediately follow event E1. (Condition C is called the "pre-condition" of event E2.) This is denoted by p [El -> E2] C. If C is true, then Uis capable of executing E2 after E1.
Causality Relations
Each event may have a number of attributes. Two basic causality relations are defined below:
- E1 -> E2 denotes that the occurrence of event E1 is a condition for the occurrence of event E2 and that attributes of E2 may refer to attributes of E1.
- ~ E1 -> E2 denotes that the non-occurrence of event E1 is a condition for the occurrence of event E2 and that attributes of E2 may not refer to attributes of E1.
Program-based testing
In this approach we add some extra code during the code generation of program. This code helps in proper monitoring of the program execution and also helps in testing of the program.
3. Testing based on Nondeterministic Execution.
Nondeterministic testing of P involves the following steps: [6]
(1) Select a set of inputs of P,
(2) For each selected input X, execute P with X one or more times and examine the result of each execution. This approach is commonly used for testing concurrent programs. Nondeterministic testing of P with input X has three major problems.
- First, some feasible SYN-sequence of P with input X may be executed many times.
- Second, some feasible SYN-sequences of P with input X may never be executed.
- Third, the existence of SYN-sequences that are valid, but infeasible for P with input X can never be detected.
4. Prefix-based testing and Reach-ability testing technique
Prefix-Based Testing
One possible combination of nondeterministic and deterministic testing, called prefix-based testing, is to execute P with input X and SYN-sequence S as follows: [6,7]
(1) Perform deterministic testing of P according to X and S. If this deterministic testing succeeds (i.e., it reaches the end of S), then go to step (2).
(2) Continue the execution of P with input X by performing nondeterministic testing of P.
If S is prefix-feasible for P with input X, then prefix-based testing replays S in step (1). The purpose of prefix-based testing is to start nondeterministic testing from a specific program state other than the initial program state.
Reach-ability testing [6]
Assume that every execution of P with input X terminates. A general description of reach-ability testing of P with input X is the following:
(1) Perform nondeterministic testing of P with input X to collect some (feasible) SYN-sequences.
(2) For each collected SYN-sequence S, derive its race- variants by changing the outcome of race conditions in S. These race-variants are prefixes of other SYN- sequences of P with input X.
(3) For each new race-variant derived in (2), perform prefix-based testing of P with input X and the race-variant to execute and collect additional SYN-sequences for P with input X.
(4) For each new SYN-sequence collected in (3), repeat (2),
5. Testing based on execution trace:
This is classified into two groups: REPLAY and PARTIAL REPLAY. [8]
REPLAY serves as tools for controlling the execution path in the program, while PARTIAL REPLAY can be employed to save debugging time in addition to control the execution path.
Replay of Concurrent-C Programs
This approach to replay of concurrent programs can be divided into two phases, monitoring and reproducing phase.
In the monitoring phase, we add a control process to the original program. The interactions between the control process and the application processes are shown in Fig. 1.
Fig. 1. Monitoring Phase of Replay of Program[8]
Where the arcs indicate the directions of information flow. Whenever an event occurs, a report is sent to the control process. The function of the control process is to receive reports of the events from the program under debugging and to record theseevents ina file, called event descriptor file. By this mechanism, all events of interest are stored.
In the reproducingphase, another control process is added. Fig.2. shows the relationship between the control process and the application processes.
Fig. 2. Reproducing Phase of replay of program [8]
Just before each event is about to occur, a request for permission is sent to the control process. The control process reads the event descriptor file, accepts the requests from the application processes, chooses the right one among them and enables its further execution as soon as the request of the next event arrives. The synchronization sequence is reproduced in this way.
6.Mutation Based Testing Technique
Mutation-based software testing is a powerful technique for testing software systems. It requires executing many slightly different versions of the same program to evaluate the quality of the test cases used to test the program.
Mutation-based testing has been applied to sequential software. However, some problems are encountered when it is applied to concurrent programs. These problems are because of the non-deterministic behavior of the executions of concurrent programs.
Below, we describe two different approaches to testing a concurrent program CP. Both approaches are useful during mutation-based testing.
- Multiple Execution Testing (MET)
- Deterministic Execution Testing (DET)
Description of these approaches given as:
Multiple Execution Testing (MET)
To increase confidence in the testing results, a commonly used approach, called multiple executiontesting (MET), is the following:
- Select a set of inputs of CP,
- For each selected input X, execute CP with X multiple times and examine the result of each execution.
Deterministic Execution Testing (DET)
Deterministic execution testing (DET) approach to testing a concurrent program CP is defined as follows:
(1) Select a set of IN-SYN test cases. An IN-SYN test case is of the form (X,R), where X and R are an input and a SYN-sequence of CP.
(2) For each selected IN-SYN test case (X,R):
(2.1) determine whether or not R is feasible for CP with input X by attempting to force R to be exercised during an execution of CP with input X,
(2.2) compare the actual result of the forced execution with the expected result of the forced execution. If the actual and expected results of the forced execution in (2.1) are different, then an erroris detected.
Deterministic execution testing (DET) has advantages over multiple executions testing (MET), it requires additional effort for selecting SYN-sequences and determining their feasibility. The amount of effort for selecting SYN-sequences can be reduced by combining DET and MET.
Below, we outline a test procedure for deterministic execution mutation testing (DEMT) of concurrent Ada programs.
- First randomly generate R-sequences using MET, until the mutation score has reached a steady value.
- Then we select IN-SYN test cases and apply DET in order to achieve an adequate mutation score.
Conclusion:
From this survey report it has been concluded that testing of concurrent program difficult as of sequential program. Different researcher has proposed various techniques for testing. But in concurrent program testing faces some challenges 1) Coverage Criteria: Testing may generate a large number test case. To seek the tradeoff between the coverage and test effort we need to select the test case according to the coverage criteria. 2) As the number of the thread executing simultaneously then we also needs to check for the deadlock and starvation of threads.3)Non-deterministic behavior of running of multithreaded program cause the testing more difficult.
The techniques of testing discussed above has sort out these problem up to a large extent, but this area need more work to make the testing work more reliable and efficient as of the sequential program testing.
References:
[1] K C. Tai, “TESTING OF CONCURRENT SOFTWARE”.1989 IEEE
[2] Stewart N. Weiss,“A FORMAL FRAMEWORK FOR THE STUDY OF CONCURRENT PROGRAM TESTING”. 1988 IEEE
[3] R.N. 'I'aylor, D.L. Levine, “Structural testing of concurrent program”. IEEE Train on software eng I992
[4] Ren-Dar Yangt and Chyan-Goei Chung, “A Path Analysis Approach to Concurrent Program Testing”.1990 IEEE
[5]Kuo-Chung Tai,Richard H. Carver, “Use of Sequencing Constraints for Specifying, Testing, and Debugging Concurrent Programs”.1994 IEEE
[6] Kuo-Chung Tai, “Reachability Testing of Asynchronous Message-Passing Programs” 1997 IEEE
[7] Jian Chen, Richard Carver, “Selecting and Mapping Test Sequences from Formal Specifications of Concurrent Programs”.1997 IEEE
[8]Jason Lee, Kuo-Hua Wang and Ching-RoungChouj, “An Implementation of Software Tools for Replay and Partial Replay of Concurrent-C Programs”.1990 IEEE
[9] Dr. Richard Carver, Dept. of Computer Science George Mason University Fairfax, “MUTATION-BASED TESTING OF CONCURRENT PROGRAMS”. INTERNATIONAL TEST CONFERENCE 1993.