The published papers are distributed over a number of discrete testing topics, such as failure injection [26], formal verification [27—33], static analysis [34—36], testing-driven development [37—39], controlled execution [40—46], mutation testing [47—49], model checking [50—53], model-based testing [54, 55], structural testing [56—72], symbolic analysis [73, 74], search-based testing [75, 76], interleaving coverage testing [77], probabilistic concurrency testing [78], reachability testing [20, 79—91], and test case generation [92—94].
We highlight just some of the relevant related research here, given the scope of this paper. A larger set of references can be found in the systematic review in [95]. Yang and Chung [59] proposed a static analysis technique to identify whether a given concur- rent path is traversable in some execution. The technique is based on the analysis of the possible execution order of rendezvous statements within the given concurrent path. The execution order of rendezvous statements in this concurrent path is used to define a precede relation.
In addition, several precedence rules and an algorithm are proposed to derive precede relations defined in a con- current path. From the precede relations and the semantics of Ada, decision rules are considered to determine statically infeasible paths. This approach does not generate the combinatorial explosion problem that occurs in the reachability analysis. Taylor et al. ZALUSKA all-concurrency-paths, all-proper-cc-histories, all-edges-between-cc-states, all-cc-states, and all- possible-rendezvous.
The hierarchy among these criteria is analyzed. They stressed that every approach based on reachability analysis would be limited in practice by state space explosion. They mentioned some alternatives to overcome the associated constraints. In the same vein as Taylor et al. These criteria focus on the rendezvous among tasks. They also presented a hierarchy among these criteria. Yang et al. The parallel program model used consists of multiple threads of control that can be executed simulta- neously.
A parallel program flow graph is constructed and is traversed to obtain the paths, variable definitions, and uses. All paths that have definition and use of variables related with parallelism of threads constitute test requirements to be exercised.
The authors present the foundations and theoretical results for structural testing of parallel programs, with a definition of the all-du-path and all-uses cri- teria for shared-memory programs. This work inspired the test model definition for message-passing parallel programs, described in Section 2. Test data and concurrent test paths are generated by traversing the BPEL flow graph model. In this way, complete test cases are generated through a combination of test paths and input data.
Kojima et al. To overcome the very large quantity of test cases required when the number of elements increases, the authors proposed to suppress test cases considering the relation happens-before between local blocks those that do not include operating shared resources and focus the testing activity in the external operation blocks instead i. This approach does not directly address the large quantity of synchronization pairs that occur in the static analysis.
The proposed analysis is carried out by the dialyzer, a software tool that aims to balance soundness and completeness by using reduced CFGs and removing sync-edges given Erlang programming characteristics.
In contrast to our proposal, the source code cannot be entirely covered because of the approach adopted for reducing the CFGs. Humphrey et al. The ISP is able to search the execu- tion space of an MPI program dynamically to detect a set of bugs related to deadlocks, resource leaks such as MPI object leaks , and violations of C assertions placed in the code.
In contrast to our work, this paper presents a fully dynamic approach, designed to detect a specific set of errors. Edelstein et al. This architecture combines a replay algorithm with a seeding technique, where the coverage is specific to race conditions. This seeding technique inserts sleep statements into the program, on the basis of shared-memory accesses and synchronization events. Heuristics are used to decide when a sleep statement must be activated.
The replay algorithm is used to re-execute a test when race conditions are detected, ensuring that all accesses in a race will be executed. The focus of this work is the non-determinism problem and not specifically code coverage and testing criteria.
Sherman et al. A saturation point happens when additional testing effort is unlikely to provide additional coverage of the source code. Wong et al. The reachability graph is used to represent concurrent programs and to select test sequences using the all-node and all-edge. The methods aim to generate a small test sequence set that will cover all the nodes and the edges in a reachability graph.
For this, the methods provide information about which parts of the program should be covered first effectively to increase the coverage of these criteria. The authors stressed that the major advantage of the reachability graph is that only feasible paths will be generated.
However, the authors did not explain how to generate the reachability graph from the concurrent program or how to deal with the state space explosion. Lei and Carver [20] proposed a method based on reachability testing to obtain all of the executable synchronizations of a concurrent program from a given execution of the program in a way that reduces the number of redundant synchronizations.
As this method uses dynamic infor- mation, only feasible synchronizations are generated, which is a considerable advantage. However, a difficulty with this method is the high number of possible combinations of synchronization that are generated. For complex programs, this number is extremely high, which limits the practical applica- tion of this approach. In [81], Carver and Lei proposed a distributed reachability testing algorithm, allowing different test sequences to be executed concurrently.
This algorithm reduces the time to execute the synchronizations, but the authors did not comment about the effort necessary to analyze the results from these executions. The method described in [20] is essentially complementary to our approach.
However, the authors did not address how to select the test case that will be used for the initial run, whereas we make use of the static analysis of the program to select the optimum test cases in advance. This paper contributes to this research effort by extending the structural test model proposed in [5].
The main contribution of our work is a proposed flexible test model that provides improved coverage of message-passing programs, together with a significantly reduced testing activity cost. The flexibility of our test model has been improved in several different ways, mainly because now it is possible to generalize sends and receives in the same set Nsync , where Nsync can be configured to represent logical sub-groups or clusters of primitives able to interact with each other.
Clustering primitives reduces significantly the amount of infeasible sync-edges and, consequently, the amount of s-use, s-c-use, and s-p-use associations. This relatively straightforward change is nevertheless very important because of the reduction in costs of detecting infeasible elements automatically.
Indeed, the large amount of infeasible elements that must still be analyzed manually by the tester represents a very high cost in the static approach. The extension proposed in this paper contributes significantly in this direction by creating a test model able to support the primitive cluster concept.
We propose four new testing criteria in addition to the ones already provided. They improve over- all testing activity quality by acting as a guideline for test case generation and also by establishing a metric to determine whether the testing activity is completed or not. These new criteria concentrate on message-passing standard primitives, non-blocking checking of the communication primitive status, and the use of buffers after non-blocking communication primitives.
The case study results demonstrate that the sets of elements extracted from the source code are effective in representing the features considered by the new model. Considering these reductions in Es , the amount of required elements generated for the testing criteria related to the communication also was conse- quently reduced.
Considering our case studies, these reductions mean that the tester will not be required to analyze elements of the ring program and 35, elements of the Jacobi program during the testing activity. Introduction to Parallel Computing, 2nd edn. Addison Wesley: Harlow, Rapps S, Weyuker EJ.
Selecting software test data using data flow information. MIT Press: Cambridge, Forum MPI. University of Tennessee: Knoxville, TN, Structural testing criteria for message-passing parallel programs.
Concurrency and Computation: Practice and Experience ; — Structural testing for semaphore-based multithread programs. Springer: Heidelberg, ; — Parallel Computing ; 22 6 — Gropp WD, Lusk E. Data flow testing in the presence of unexecutable paths.
Replay and testing for concurrent programs. IEEE Software ; 8 2 — Coverage testing criteria for message-passing parallel programs. ValiPar: a testing tool for message-passing parallel programs. Springer: Berlin, ; — A tool for structural testing of MPI programs. Web services composition testing: a strategy based on struc- tural testing of parallel programs. A language for the description of program instrumenta- tion and the automatic generation of instrumenters.
Using coverage and reachability testing to improve concurrent program testing quality. Lei Y, Carver RH. Reachability testing of concurrent programs. Mohnen M. A graph free approach to data flow analysis. In Compiler Construction, Vol. Data Flow Analysis: Theory and Practice.
Howden WE. Reliability of the path analysis testing strategy. Krawczyk H, Wiszniewski B. Classification of software defects in parallel programs. Tanenbaum AS. Modern Operating Systems, 2nd edn. Enforcer—efficient failure injection. In Formal Methods, Vol. Modeling multithreaded applications using Petri nets. International Journal of Parallel Programming ; 30 5 — Parametric and sliced causality.
In Computer Aided Verification, Vol. Heidelberg: Berlin, ; — Yang Z, Sakallah K. Trace-driven verification of multithreaded programs. A self-adaptive test framework for concurrent programs.
Storm: static unit checking of concurrent programs. Composable specifications for structured shared-memory communi- cation. Xu K, Liang D. Formally defining a graphical language for monitoring and checking object interactions. HAVE: detecting atomicity violations via integrated dynamic and static analysis. Chen J. Guided testing of concurrent programs using value schedules. PhD Thesis, University of Waterloo, Christakis M, Sagonas K. Detection of asynchronous message passing errors using static analysis.
Springer: Berlin, ; 5— Improving automated testing of multi-threaded software. Ricken M, Cartwright R. ConcJUnit: unit testing for concurrent programs. IMUnit: improved multithreaded unit testing. Preemption sealing for efficient concurrency testing. Technical Report, Microsoft, Dantas A. Obtaining trustworthy test results in multi-threaded systems.
Delay-bounded scheduling. Yu J, Narayanasamy S. A case for an interleaving constrained shared-memory multi-processor. Kamil A, Yelick K. Enforcing textual alignment of collectives using dynamic checks. Rungta N, Mercer EG. A meta heuristic for effectively detecting concurrency errors. Springer: Heidelberg, ; 23— MuTMut: efficient exploration for mutation testing of multithreaded code.
Sen A, Abadir MS. Coverage metrics for verification of concurrent systemic designs using mutation testing. Mutation operators for actor systems. Inspect: a runtime model checker for multithreaded C programs. Technical Report, University of Utah, Correctness analysis based on testing and checking for OpenMP programs. Musuvathi M, Qadeer S. Fair stateless model checking. SMT-based symbolic model checking for multi-threaded programs.
Modeling and testing multi-threaded asynchronous systems with Creol. Electronic Notes in Theoretical Computer Science ; — Conformance testing of distributed concurrent systems with executable designs. Springer: Berlin, ; 61— Coverage based testing for concurrent software. Saturation-based testing of concurrent programs. Path analysis testing of concurrent programs. Information and Software Technology ; 34 1 — The analysis of infeasible concurrent paths of concurrent Ada programs.
A path analysis approach to concurrent program testing. An incremental approach to structural testing of concurrent software.
Incremental integration testing of concurrent programs. A model for concurrent states and its coverage criteria. A method for determining testing scenarios for parallel and distributed software. Software testing and metrics for concurrent computation through task decomposition.
Software testing and metrics for concurrent computation. Test-case generation for concurrent programs with the testing crite- ria using interaction sequences. Test-case generation method for concurrent programs including task-types. Event interactions graph for test-case generations of concurrent programs. A method for structural testing of Ada concurrent programs using the event interactions graph.
Design and implementation of test-case generation for concurrent programs. Timing-sequence testing of parallel programs. Journal of Computer Science and Technology ; 15 1 — Efficient testing of concurrent programs with abstraction-guided symbolic execu- tion. In Model Checking Software, Vol.
A platform for search-based testing of concurrent software. McMinn P. Search-based failure discovery using testability transformations to generate pseudo-oracles. A study of interleaving coverage criteria. A randomized scheduler with probabilistic guarantees of finding bugs.
A combinatorial testing strategy for concurrent programs. Software Testing Verification and Reliability ; 17 4 — Also helpful is a controllable run-time scheduler.
The techniques proposed are suitable for Ada or CSP-like languages. Best results are obtained for programs having only static naming of tasking objects. Article :. Skip to main content. This service is more advanced with JavaScript available. Advertisement Hide. Authors Authors and affiliations Rafael R. Prado Paulo S. Souza Simone R. Souza George G. Dourado Raphael N. Conference paper First Online: 29 March Keywords Web services Structural testing tools Concurrent software.
This is a preview of subscription content, log in to check access. Barbosa, E. In: SEKE , pp. Ciortea, L. Eler, M.
0コメント