A combinatorial testing strategy for concurrent programs

One approach to testing concurrent programs is called reachability testing, which derives test sequences automatically and on‐the‐fly, without constructing a static model. Existing reachability testing algorithms are exhaustive in that they are intended to exercise all possible synchronization sequences of a concurrent program with a given input. In this paper, we present a new testing strategy, called t‐way reachability testing, that adopts the dynamic framework of reachability testing but selectively exercises a subset of synchronization sequences. The selection of the synchronization sequences is based on a combinatorial testing strategy called t‐way testing. We present an algorithm that implements t‐way reachability testing, and report the results of several case studies that were conducted to evaluate its effectiveness. The results indicate that t‐way reachability testing can substantially reduce the number of synchronization sequences exercised during reachability testing while still effectively detecting faults. Copyright © 2007 John Wiley & Sons, Ltd.     

Reachability testing of concurrent programs

One approach to testing concurrent programs, called reachability testing, generates synchronization sequences automatically and on-the-fly, without constructing any static models. In this paper, we present a general execution model for concurrent programs that allows reachability testing to be applied to several commonly used synchronization constructs. We also present a new method for performing reachability testing. This new method guarantees that every partially ordered synchronization sequence will be exercised exactly once without having to save any sequences that have already been exercised. We describe a prototype reachability testing tool called RichTest and report some empirical results, including a comparison between RichTest and a partial order reduction-based tool called VeriSoft. RichTest performed significantly better for the programs in our study.     

Variable strength combinatorial testing of concurrent programs

Reachability testing is an important approach to testing concurrent programs. It generates and exercises synchronization sequences automatically and on-the-fly without saving any test history. Existing reachability testing can be classified into exhaustive and t-way testing. Exhaustive testing is impractical in many cases while t-way testing may decrease the capability of fault detection in some cases. In this paper, we present a variable strength reachability testing strategy, which adopts the dynamic framework of reachability testing and uses a variable strength combinatorial strategy. Different parameter groups are provided with different covering strength. Variable strength testing covers no t-way combinations but the necessary combinations of parameters having mutual interactions in a concurrent program. It is more reasonable than t-way testing because uniform interactions between parameters do not often exist in concurrent systems. We propose a merging algorithmthat implements the variable strength combinatorial testing strategy and conduct our experiment on several concurrent programs. The experimental results indicate that our variable strength reachability testing reaches a good tradeoff between the effectiveness and efficiency. It can keep the same capability of fault detection as exhaustive reachability testing while substantially reducing the number of synchronization sequences and decreasing the execution time in most cases.     

一个用于Java程序可达性测试的改进方案

Java程序的并发性使它比串行程序更难测试,而可达性测试是一种有效的并发程序测试方法。首先比较了现有的Java程序可达性测试技术,进而提出了一种融合的改进方案以提高同步序列集的生成效率。然后指出新方案已覆盖了用伯恩斯坦条件裁减同步序列集的功能。最后详述如何通过扫描源程序来自动获取同步事件的时序约束关系,进而减少不可行的同步序列,并介绍了相应的实现算法和数据结构。     

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

A dynamic-sized nonblocking work stealing deque

The non-blocking work-stealing algorithm of Arora, Blumofe, and Plaxton (hencheforth ABP work-stealing) is on its way to becoming the multiprocessor load balancing technology of choice in both industry and academia. This highly efficient scheme is based on a collection of array-based double-ended queues (deques) with low cost synchronization among local and stealing processes. Unfortunately, the algorithm's synchronization protocol is strongly based on the use of fixed size arrays, which are prone to overflows, especially in the multiprogrammed environments for which they are designed. This is a significant drawback since, apart from memory inefficiency, it means that the size of the deque must be tailored to accommodate the effects of the hard-to-predict level of multiprogramming, and the implementation must include an expensive and application-specific overflow mechanism. This paper presents the first dynamic memory work-stealing algorithm. It is based on a novel way of building non-blocking dynamic-sized work stealing deques by detecting synchronization conflicts based on “pointer-crossing” rather than “gaps between indexes” as in the original ABP algorithm. As we show, the new algorithm dramatically increases robustness and memory efficiency, while causing applications no observable performance penalty. We therefore believe it can replace array-based ABP work stealing deques, eliminating the need for application-specific overflow mechanisms. This work was conducted while Yossi Lev was a student at Tel Aviv University, and is derived from his MS thesis [1].     

A systematic review of approaches for testing concurrent programs

Concurrent programs are replacing the sequential programs as they utilize the true capabilities of multicore architecture. The extensive use of multicore systems and multithreaded paradigms warrants more attention to the testing of the concurrent programs. The testing concurrent program is not a new field as it has been more than 40 years because the first problem related to the testing concurrent program was addressed by the researchers. The field covers various domains, which include concurrency problems, testing approaches, techniques, graphical representations, tools, and subject systems. This paper aims at providing an overview of research in the domain of testing concurrent programs by classifying it into eight categories: (a) reachability testing, (b) structural testing, (c) model‐based testing, (d) mutation‐based testing, (e) slicing‐based testing, (f) formal methods, (g) random testing, and (h) search‐based testing. The survey is focused on the techniques applied, methodologies followed, and tools used in these aforementioned approaches. Furthermore, the gaps are also identified in different approaches. The paper concludes with the consolidation of various testing parameters along with the future directions. Copyright © 2015 John Wiley & Sons, Ltd.     

多单元协议一致性测试中的同步序列的生成

有限状态机模型一般被用来描述通信协议和其它各类的分布式系统,对于一个多端口的有限状态机,需要多个测试单元进行测试,使用一个包括K个（K≥2）测试单元的测试系统可以检查一个多单元通信协议软件的收发行为是否与协议规格一致,在测试过程中,K个测试单元之间可能会出珊步问题,目前,主要是通过增加外部同步操作来解决同步问题,提出了一种新的同步测试序列生成模型－－同步有向图,它可以判断一个给定的协议规格是否可以在不需要外部同步操作的情况下,产生同步测试序列;如果可以产生,则此生成中以将非同步测试相应的同步测试序列;另外此生成模型还可以用来选择为测试系统增加外部同步通道的方法。     

Anomaly detection in concurrent Java programs using dynamic data flow analysis

Concurrency constructs are widely used when developing complex software such as real-time, networking and multithreaded client–server applications. Consequently, testing a program, which includes concurrency constructs is a very elaborate and complex process. In this work, we first identify the different classes of synchronization anomalies that may occur in concurrent Java programs. We then consider testing concurrent Java programs against synchronization anomalies using dynamic data flow analysis techniques. Moreover, we show how the data flow analysis technique can be extended to detect such anomalies.     

Structural testing criteria for message‐passing parallel programs

Parallel programs present some features such as concurrency, communication and synchronization that make the test a challenging activity. Because of these characteristics, the direct application of traditional testing is not always possible and adequate testing criteria and tools are necessary. In this paper we investigate the challenges of validating message‐passing parallel programs and present a set of specific testing criteria. We introduce a family of structural testing criteria based on a test model. The model captures control and data flow of the message‐passing programs, by considering their sequential and parallel aspects. The criteria provide a coverage measure that can be used for evaluating the progress of the testing activity and also provide guidelines for the generation of test data. We also describe a tool, called ValiPar, which supports the application of the proposed testing criteria. Currently, ValiPar is configured for parallel virtual machine (PVM) and message‐passing interface (MPI). Results of the application of the proposed criteria to MPI programs are also presented and analyzed. Copyright © 2008 John Wiley & Sons, Ltd.     

A class library for implementing, testing, and debugging concurrent programs

We describe the Modern Multithreading (MM) class library. MM is a class library consisting of thread and synchronization classes that provide significant support for testing and debugging multithreaded programs. The synchronization classes implement commonly used synchronization objects such as semaphores, monitors, and asynchronous and synchronous message passing channels, for programs that run on a single computer or on a distributed system. MM uses controlled executions to provide program tracing and replay and to support a number of implementation-based and specification-based testing techniques, including non-deterministic and deterministic testing and several forms of reachability testing. MM is portable and easy to use, and has been implemented in Java and C++, with C++ versions for the POSIX Pthreads library and for the Windows Win32 API.     

Work stealing for GPU‐accelerated parallel programs in a global address space framework

Task parallelism is an attractive approach to automatically load balance the computation in a parallel system and adapt to dynamism exhibited by parallel systems. Exploiting task parallelism through work stealing has been extensively studied in shared and distributed‐memory contexts. In this paper, we study the design of a system that uses work stealing for dynamic load balancing of task‐parallel programs executed on hybrid distributed‐memory CPU‐graphics processing unit (GPU) systems in a global‐address space framework. We take into account the unique nature of the accelerator model employed by GPUs, the significant performance difference between GPU and CPU execution as a function of problem size, and the distinct CPU and GPU memory domains. We consider various alternatives in designing a distributed work stealing algorithm for CPU‐GPU systems, while taking into account the impact of task distribution and data movement overheads. These strategies are evaluated using microbenchmarks that capture various execution configurations as well as the state‐of‐the‐art CCSD(T) application module from the computational chemistry domain. Copyright © 2016 John Wiley & Sons, Ltd.     

A Scalable Parallel Algorithm for Reachability Analysis of Very Large Circuits

This paper presents a scalable method for parallelizing symbolic reachability analysis on a distributed-memory environment of workstations. We have developed an adaptive partitioning algorithm that significantly reduces space requirements. The memory balance is maintained by dynamically repartitioning the state space throughout the computation. A compact BDD representation allows coordination by shipping BDDs from one machine to another. This representation allows for different variable orders in the sending and receiving processes. The algorithm uses a distributed termination protocol, with none of the memory modules preserving a complete image of the set of reachable states. No external storage is used on the disk. Rather, we make use of the network, which is much faster.We implemented our method on a standard, loosely-connected environment of workstations, using a high-performance model checker. Initial performance evaluation of several large circuits shows that our method can handle models too large to fit in the memory of a single node. The partitioning algorithm achieves reduction in space, which is linear in the number of workstations employed. A corresponding decrease in space requirements is measured throughout the reachability analysis. Our results show that the relatively slow network does not become a bottleneck, and that computation time is kept reasonably small.     

Incremental integration testing of concurrent programs

We present a method for selecting test sequences for concurrent programs from labeled transitions systems (LTS). A common approach to selecting test sequences from a set of LTSs is to derive a global LTS, called the reachability graph, and then force deterministic program executions according to paths selected from the graph. However, using a reachability graph for test path selection introduces a state explosion problem. To overcome this problem, a reduced graph can be generated using incremental reachability analysis, which consists of repeatedly generating a reachability graph for a subset of LTSs, reducing this graph, and using the reduced graph in place of the original LTSs. Unfortunately, existing incremental reachability analysis techniques generate reduced graphs with insufficient information for deterministic testing. We present an incremental approach to testing concurrent programs. Incremental testing consists of incremental reachability analysis for test path selection and deterministic testing for test execution. We define a new type of reachability graph for incremental analysis, called an annotated labeled transition system (ALTS). An ALTS is an LTS annotated with information necessary for deterministic testing. We propose practical coverage criteria for selecting tests paths from an ALTS and present an ALTS reduction algorithm. The results of several case studies are reported     

Automatic testing environment for multi-core embedded software—ATEMES

Software testing during the development process of embedded software is not only complex, but also the heart of quality control. Multi-core embedded software testing faces even more challenges. Major issues include: (1) how demanding efforts and repetitive tedious actions can be reduced; (2) how resource restraints of embedded system platform such as temporal and memory capacity can be tackled; (3) how embedded software parallelism degree can be controlled to empower multi-core CPU computing capacity; (4) how analysis is exercised to ensure sufficient coverage test of embedded software; (5) how to do data synchronization to address issues such as race conditions in the interrupt driven multi-core embedded system; (6) high level reliability testing to ensure customer satisfaction. To address these issues, this study develops an automatic testing environment for multi-core embedded software (ATEMES). Based on the automatic mechanism, the system can parse source code, instrument source code, generate testing programs for test case and test driver, support generating primitive, structure and object types of test input data, multi-round cross-testing, and visualize testing results. To both reduce test engineer's burden and enhance his efficiency when embedded software testing is in process, this system developed automatic testing functions including unit testing, coverage testing, multi-core performance monitoring. Moreover, ATEMES can perform automatic multi-round cross-testing benchmark testing on multi-core embedded platform for parallel programs adopting Intel TBB library to recommend optimized parallel parameters such as pipeline tokens. Using ATEMES on the ARM11 multi-core platform to conduct testing experiments, the results show that our constructed testing environment is effective, and can reduce burdens of test engineer, and can enhance efficiency of testing task.     

Compact visualization of Java program execution

The context of this work is a practical, open‐source visualization system, called JIVE, that supports two forms of runtime visualizations of Java programs – object diagrams and sequence diagrams. They capture, respectively, the current execution state and execution history of a Java program. These diagrams are similar to those found in the UML for specifying design–time decisions. In our work, we construct these diagrams at execution time, thereby ensuring continuity of notation from design to execution. In so doing, a few extensions to the UML notation are proposed in order to better represent runtime behavior. As sequence diagrams can become long and unwieldy, we present techniques for their compact representation. A key result in this paper is a novel labeling scheme based upon regular expressions to compactly represent long sequences and an O(r²) algorithm for computing these labels, where r is the length of the input sequence, based upon the concept of ‘tandem repeats’ in a sequence. Horizontal compaction greatly helps minimize the extent of white space in sequence diagrams by the elimination of object lifelines and also by grouping lifelines together. We propose a novel extension to the sequence diagram to deal with out‐of‐model calls when the lifelines of certain classes of objects are filtered out of the visualization, but method calls may occur between in‐model and out‐of‐model calls. The paper also presents compaction techniques for multi‐threaded Java execution with different forms of synchronization. Finally, we present experimental results from compacting the runtime visualizations of a variety of Java programs and execution trace sizes in order to demonstrate the practicality and efficacy of our techniques. Copyright © 2016 John Wiley & Sons, Ltd.     

Automated test case generation for the stress testing of multimedia systems

With the advancement in network bandwidth and computing power, multimedia systems have become a popular means for information delivery. However, general principles of system testing cannot be directly applied to testing of multimedia systems on account of their stringent temporal and synchronization requirements. In particular, few studies have been made on the stress testing of multimedia systems with respect to their temporal requirements under resource saturation. Stress testing is important because erroneous behavior is most likely to occur under resource saturation. This paper presents an automatable method of test case generation for the stress testing of multimedia systems. It adapts constraint solving techniques to generate test cases that lead to potential resource saturation in a multimedia system. Coverage of the test cases is defined upon the reachability graph of a multimedia system. The proposed stress testing technique is supported by tools and has been successfully applied to a real‐life commercial multimedia system. Although our technique focuses on the stress testing of multimedia systems, the underlying issues and concepts are applicable to other types of real‐time systems. Copyright © 2002 John Wiley & Sons, Ltd.     

Data-parallel programming on a network of heterogeneous workstations

We describe a compiler and run-time system that allow data-parallel programs to execute on a network of heterogeneous UNIX workstations. The programming language supported is Dataparallel C, a SIMD language with virtual processors and a global name space. This parallel programming environment allows the user to take advantage of the power of multiple workstations without adding any message-passing calls to the source program. Because the performance of Individual workstations in a multi-user environment may change during the execution of a Dataparallel C program, the run-time system automatically performs dynamic load balancing. We present experimental results that demonstrate the usefulness of dynamic load-balancing In a multi-user environment These results suggest that initially allocating the same amount of work to each processor and letting the dynamic load balancing algorithm adjust the load during program execution yields very good performance. Hence neither the compiler nor the run-time system need a priori knowledge of the speeds of the machines that will participate in a program execution.     

Fault‐driven stress testing of distributed real‐time software based on UML models

In a previous article, a stress testing methodology was reported to detect network traffic‐related Real‐Time (RT) faults in distributed RT systems based on the design UML model of a System Under Test (SUT). The stress methodology, referred to as Test LOcation‐driven Stress Testing (TLOST), aimed at increasing the chances of RT failures (violations in RT constraints) associated with a given stress test location (an network or a node under test). As demonstrated and experimented in this article, although TLOST is useful in stress testing different test locations (nodes and network, it does not guarantee to target (test) all RT constraints in an SUT. This is because the durations of message sequences bounded by some RT constraints might never be exercised (covered) by TLOST. A complementary stress test methodology is proposed in this article, which guarantees to target (cover) all RT constraints in an SUT and detect their potential RT faults (if any). Using a case study, this article shows that the new complementary methodology is capable of targeting the RT faults not detected by the previous test methodology. Copyright © 2009 John Wiley & Sons, Ltd.     

On Symbolic Verification of Weakly Extended PAD

We consider the verification problem of a class of infinite-state systems called wPAD. These systems can be used to model programs with (possibly recursive) procedure calls and dynamic creation of parallel processes. They correspond to PAD models extended with an acyclic finite-state control unit, where PAD models can be seen as combinations of prefix rewrite systems (pushdown systems) with context-free multiset rewrite systems (synchronization-free Petri nets). Recently, we have presented symbolic reachability techniques for the class of PAD based on the use of a class of unranked tree automata. In this paper, we generalize our previous work to the class wPAD which is strictly larger than PAD. This generalization brings a positive answer to an open question on decidability of the model checking problem for wPAD against EF logic. Moreover, we show how symbolic reachability analysis of wPAD can be used in (under) approximate analysis of Synchronized PAD, a (Turing) powerful model for multithreaded programs (with unrestricted synchronization between parallel processes). This leads to a pragmatic approach for detecting the presence of erroneous behaviors in these models based on the bounded reachability paradigm where the notion of bound considered here is the number of synchronization actions.