CMuJava:一个面向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.     

Distributed reachability testing of concurrent programs

Reachability testing is an approach to verifying concurrent programs. During reachability testing, every partially ordered synchronization sequence of a program with a given input is exercised exactly once. In this paper, we present the design and implementation of a distributed reachability testing algorithm for a cluster of workstations. This algorithm allows different test sequences to be exercised concurrently by different workstations without any synchronization, and without any duplication of sequences among workstations. Dynamic load balancing is performed using a work‐stealing scheme. A novel aspect of this scheme is that work‐stealing requests progress in rounds. This round‐based structure identifies overloaded workstations to target for work stealing. Empirical studies show good speedup for four benchmark Java programs and one Lotos specification. Copyright © 2010 John Wiley & Sons, Ltd.     

并发程序切片原型系统的设计与实现

并发程序切片是并发程序分析的一种重要手段。针对多线程共享变量通信机制,在通过程序分析工具CodeSurfer获取程序基本信息的基础上构造程序可达图,生成以程序状态和语句二元组为节点的并发程序依赖图,实现了基于程序可达图的并发程序切片原型系统。初步实验结果表明,与传统的切片方法相比,采用基于程序可达图的并发程序切片方法,可有效地解决依赖关系不可传递问题,获得高精度的并发程序切片。     

A rigorous approach towards test case generation

This paper presents a method to generate test cases for sequential programs and concurrent programs written in a flow based program language. Test cases of sequential programs are generated based on condition calculation, and can be combined together to form SYN-sequences for concurrent program testing. Semantics of the language provides an infrastructure for the test case generation, and thus our method may be considered as a rigorous and systematic approach to the program testing. Compared with some formal testing methods, our method can avoid hitting state explosion problem in the test formation. Besides, the complexity analysis reveals that our method is time saving. Our method has been applied to generate test cases for PPP over ATM, a subsystem of IAD that runs data and voice over DSL.     

Concurrent programming in VISO

Concurrent programming is more difficult to use and understand than sequential programming. In order to simplify this type of programming a number of approaches have been developed such as visual programming. Visual Occam (VISO) is a visual programming language for concurrent programming. It has a graphical syntax based on the language Occam and its semantics is represented both in petri net and process calculus. This paper presents a modular visual approach to write concurrent programs using the VISO language. Concurrent programs in VISO are specified graphically at different levels of abstraction. This paper describes this modular visual approach by constructing two examples in VISO. The first example is a simple concurrent program and it is mainly used to show the details of constructing a concurrent program in VISO. The second example is a larger concurrent program with more levels of abstraction. Copyright © 2000 John Wiley & Sons, Ltd.     

MuJava: an automated class mutation system

Several module and class testing techniques have been applied to object‐oriented (OO) programs, but researchers have only recently begun developing test criteria that evaluate the use of key OO features such as inheritance, polymorphism, and encapsulation. Mutation testing is a powerful testing technique for generating software tests and evaluating the quality of software. However, the cost of mutation testing has traditionally been so high that it cannot be applied without full automated tool support. This paper presents a method to reduce the execution cost of mutation testing for OO programs by using two key technologies, mutant schemata generation (MSG) and bytecode translation. This method adapts the existing MSG method for mutants that change the program behaviour and uses bytecode translation for mutants that change the program structure. A key advantage is in performance: only two compilations are required and both the compilation and execution time for each is greatly reduced. A mutation tool based on the MSG/bytecode translation method has been built and used to measure the speedup over the separate compilation approach. Experimental results show that the MSG/bytecode translation method is about five times faster than separate compilation. Copyright © 2004 John Wiley & Sons, Ltd.     

面向Java的分布式程序测试系统

由于程序的分布运行,测试分布式程序必须同时考虑并发特性和运行环境.介绍了一个面向Java语言的分布式程序测试系统JDPT(Java-oriented distributed program testing system).JDPT基于运行环境定义事件,通过事件序列记录分布式程序的运行过程,并定义事件约束检测可行事件序列集的有效性.通过该技术,JDPT可以有效地判断程序在运行环境中并发执行的正确性,适用于跨平台的Java程序测试.     

面向共享内存并行程序的测试技术

随着并行编程越来越普及,并行程序的测试也变得越来越重要。本文面向共享内存的并行程序,研究一种新的并行程序测试技术,设计了工具CPTester,采用冗余分析方法避免重复的结果。和已有工作不同的是CPTester能够自动生成每一个并行bug的上下文信息,对程序员理解并修复一个并行bug具有重要意义。将CPTester在一些真实的并行程序上进行实验评测,结果显示CPTester能够有效地检测到程序中的并行bug,且每一个并行bug都有相应的上下文信息来描述该bug触发的根本原因。     

面向国产平台的程序并发性能分析技术

随着国产处理器和国产操作系统的逐步推广应用,越来越多的开发人员在国产平台下开发多线程程序.目前国产平台普遍采用的Qt Creator工具中缺乏可视化的并发性能分析工具,使得优化由于多线程同步/互斥和资源竞争带来的性能问题变得特别困难.设计一种Qt Creator下的并发性能分析方案,通过实时监控程序并发事件,采集程序运行过程中的并发性能数据,分析程序并发性能瓶颈和死锁原因,并以插件形式进行多视图数据显示.通过实验表明,该并发性能分析方案可以方便、快捷地辅助用户开发多线程并发程序,提高软件开发效率.     

Implementing prototype testing tools

Testing tools are software analyzers that use information from particular executions of a program as well as information about a specification and the program text itself. Research prototypes of such tools are essential to investigate the ideas they embody. Often, hand calculation is so tedious and error-prone that an investigator cannot obtain any intuition about his or her ideas without an implementation to aid in experiments. Traditionally, such tools have been implemented in conventional high-level languages (e.g., C, Pascal), a process that takes more time than a prototype should. The technology of compiler generators and logic programming, applied to the idea of self-instrumenting programs, drastically shortens the prototype cycle. This paper describes a general method for implementing prototype tools, gives examples of several old and new testing techniques fitted into the method, and discusses the ease with which such prototypes may be changed.     

A transformation‐based approach to testing concurrent programs using UML activity diagrams

Unified Modeling Language (UML) activity diagrams are widely used to model concurrent interaction among multiple objects. In this paper, we propose a transformation‐based approach to generating scenario‐oriented test cases for applications modeled by UML activity diagrams. Using a set of transformation rules, the proposed approach first transforms a UML activity diagram specification into an intermediate representation, from which it then constructs test scenarios with respect to the given concurrency coverage criteria. The approach then finally derives a set of test cases for the constructed test scenarios. The approach resolves the difficulties associated with fork and join concurrency in the UML activity diagram and enables control over the number of the resulting test cases. We further implemented a tool to automate the proposed approach and studied its feasibility and effectiveness using a case study. Experimental results show that the approach can generate test cases on demand to satisfy a given concurrency coverage criterion and can detect up to 76.5% of seeded faults when a weak coverage criterion is used. With the approach, testers can not only schedule the software test process earlier, but can also better allocate the testing resources for testing concurrent applications. Copyright © 2015 John Wiley & Sons, Ltd.     

Reproducible testing of monitors

This paper describes a systematic method for testing monitor modules which control process interactions in concurrent programs. A monitor is tested by executing a concurrent program in which the processes are synchronized by a clock to make the sequence of interactions reproducible. The method separates the construction and implementation of test cases and makes the analysis of a concurrent experiment similar to the analysis of a sequential program. The implementation of a test program is almost mechanical. The method, which is illustrated by an example, has been successfully used to test a multicomputer network program written in Concurrent Pascal.     

基于有限状态进程的事件约束定义

测试分布式程序需要定义事件约束来检测程序执行产生的事件序列.事件约束需要根据程序的规约来推导.FSP是一类描述并发程序形式化规约的进程代数记法.它将并发进程描述为动作序列,其中动作可对应到规约级事件.E-CSPE约束在给定状态谓词下定义前后运行事件间的顺序关系.根据FSP的操作符和并发控制机制可推导E-CSPE约束.推导出来的E-CSPE约束考虑到并发程序的安全和进展属性,可据以判断程序运行的正确性和测试的充分性.     

一种并发程序依赖性分析方法

并发程序的依赖性分析是并发程序分析，理解，调试，测试和维护的重要手段，由于并发程序执行的不确定性，目前，尚有很多难点有待解决，针对Ada任务机制，首先提出了一种简洁，有效的并发程序表示方法－并发程序流图，然后讨论了由任务间同步引起的同步依赖和由访问共享变量引起的任务数据依赖，建立了并发程序依赖图，并在此基础上给出了一种有效的并发程序依赖性分析算法，得到一个比较精确的依赖性，较好地解决了并发程序依赖关系不可传递性问题。     

GC-MCR:有向图约束指导的并发缺陷检测方法

约束求解应用到程序分析的多个领域,在并发程序分析方面也得到了深入的应用.并发程序随着多核处理器的快速发展而得到广泛使用,然而并发缺陷对并发程序的安全性和可靠性造成了严重的影响,因此,针对并发缺陷的检测尤为重要.并发程序线程运行的不确定性导致的线程交织爆炸问题,给并发缺陷的检测带来了一定挑战.已有并发缺陷检测算法通过约减无效线程交织,以降低在并发程序状态空间内的探索开销.比如,最大因果模型算法把并发程序状态空间的探索问题转换成约束求解问题.然而,其在约束构建过程中会产生大量冗余和冲突的约束,大幅度增加了约束求解的时间以及约束求解器的调用次数,降低了并发程序状态空间的探索效率.针对上述问题,提出了一种有向图约束指导的并发缺陷检测方法 GC-MCR (directed graph constraint-guided maximal causalityreduction).该方法旨在通过使用有向图对约束进行过滤和约减,从而提高约束求解速度,并进一步提高并发程序状态空间的探索效率.实验结果表明:GC-MCR方法构建的有向图可以有效优化约束的表达式,从而提高约束求解器的求解速度并减少求解器的调用次...     

Graphs for Mining-Based Defect Localization in Multithreaded Programs

Trends in modern multicore architecture design requires software developers to develop and debug multithreaded programs. Consequently, software developers must face new challenges because of bug patterns occurring at runtime and due to the non-deterministic behavior of multi-threaded program executions. This calls for new defect-localization techniques. There has been much work in the field of defect localization for sequential programs on the one side and on the localization of specific multithreading bugs on the other side, but we are not aware of any general technique for multithreaded programs. This paper proposes such an approach. It generalizes data mining-based defect-localization techniques for sequential programs. The techniques work by analyzing call graphs. More specifically, we propose new graph representations of multithreaded program executions as well as two mining-based localization approaches based on these representations. Our evaluation shows that our technique yields good results and is able to find defects that other approaches cannot localize.     

基于共享内存的多核时代数据结构研究

随着计算机硬件技术的发展,如今我们已经迈入了多核CPU时代.然而,作为软件核心的数据结构仍然是按照单核CPU和顺序型准则来设计的.在基于共享内存的多核时代,大量并发运行的线程会交替地修改数据,产生不可预期的结果,因而我们面临着严峻挑战.针对基于共享内存多核时代数据结构的相关研究进行综述.首先,对比了并发与并行的区别,归纳了基于演进条件(progress condition)的多核数据结构分类,对近年来学术界对各种类型并发数据结构的研究进行综述.在此基础上,剖析了并发数据结构设计和实现的关键技术,并从并发数据结构的开发流程、正确性验证等方面进行了归纳阐述.最后,基于这些讨论,对多核架构下并发数据结构未来的研究趋势和应用前景进行了展望.     

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.     

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.