All‐uses testing of shared memory parallel programs

Parallelism has become a way of life for many scientific programmers. A significant challenge in bringing the power of parallel machines to these programmers is providing them with a suite of software tools similar to the tools that sequential programmers currently utilize. Unfortunately, writing correct parallel programs remains a challenging task.In particular, automatic or semi‐automatic testing tools for parallel programs are lacking. This paper takes a first step in developing an approach to providing all‐uses coverage for parallel programs. A testing framework and theoretical foundations for structural testing are presented, including test data adequacy criteria and hierarchy, formulation and illustration of all‐uses testing problems, classification of all‐uses test cases for parallel programs, and both theoretical and empirical results with regard to what can be achieved with all‐uses coverage for parallel programs. Copyright © 2003 John Wiley & Sons, Ltd.     

Estimating the correctness of computer programs

Program testing will for some time remain the major means by which program designers convince themselves and others of the correctness or validity of their programs. Thus it is desirable to be able to use test results to measure the degree to which a program approaches correctness. The probability of correctness of a program can sometimes be estimated according to the success of testing. A general parameter is introduced which has the property that its value is zero for a correct program and is greater than zero for an incorrect program. Under reasonable interpretations, the parameter is related, through probability density functions, to characteristics which are observable through program testing. For instance, if the parameter is interpreted as the number of errors in a program, a related, observable characteristic is the number of errors discovered through testing. Upper bounds on the parameter value are established as a function of the value of the observed characteristic and the desired level of confidence in the result. Results are presented for cases of combinations of interpretations, observable characteristics, and probability density functions.     

基于线程调度顺序控制的多线程程序测试

随着多核技术越来越普及,多线程程序的编程也越来越流行。但是多线程程序的正确性问题已经严重影响软件可靠性,且现有的测试技术不能很好地满足多线程程序的需求。本文重点研究多线程程序中最常见的一种bug,即数据竞争,提出一种基于线程调度顺序控制的测试方法。该方法混合静态方法和动态方法,能够有效地找到多线程程序中存在的数据竞争,且能够区分出哪些数据竞争是有害的,需要程序员优先修复。实验结果显示,对于数据竞争的触发概率,本文的方法使其平均从0.53%提高到79.2%,且本文所引入的运行时开销平均只有80%,与相关方法所引入370%的开销相比更优。     

CMuJava:一个面向Java程序并发变异体生成系统

并发程序由多个共享存储空间并发执行的流程组成.由于流程之间执行次序的不确定性,使得并发软件系统的测试比较困难.变异测试是一种基于故障的软件测试技术,广泛用于评估测试用例集的充分性和测试技术的有效性.将变异测试应用于并发程序的一个关键问题是,如何高效地生成大量的模拟并发故障的变异体集合.给出了一种并发程序的变异测试框架,...     

一种数据结构制导的线程划分方法与执行模型

在对程序进行并行化时,为了保证结果的正确性,并行编译器只能采取一种保守的策略,也就是,如果它不能确定两段代码在并行执行时是否会发生冲突,它就不允许这两段代码并行执行.虽然这种做法保证了正确性,但同时也限制了对并行性的开发.在这种背景下,许多推测多线程方法被提了出来,这些方法通过允许可能冲突的代码段并行执行来把握更多的并行机会,同时,通过从冲突中恢复来保证结果的正确性.然而,传统推测多线程方法所使用的“沿控制流将串行程序划分为多个线程”的做法并不适合不同数据结构上的操作在控制流中相互交错的情况,因为如果沿控制流将程序线性地划分为多个线程,则同一个数据结构上的操作将被分到不同的线程中,从而非常容易发生冲突.为了有效地对这些程序进行并行化,提出了一种基于数据结构的线程划分方法与执行模型.在这种方法中,程序中的对象被划分成多个组,同一组中对象上的操作被分派到同一个线程中去执行,从而降低了在同一个数据结构上发生冲突的可能性.     

Testing homogeneous spreadsheet grids with the "what you see iswhat you test" methodology

Although there has been recent research into ways to design environments that enable end users to create their own programs, little attention has been given to helping these end users systematically test their programs. To help address this need in spreadsheet systems (the most widely used type of end-user programming language), we previously introduced a visual approach to systematically testing individual cells in spreadsheet systems. However, the previous approach did not scale well in the presence of largely homogeneous grids, which introduce problems somewhat analogous to the array-testing problems of imperative programs. We present two approaches to spreadsheet testing that explicitly support such grids. We present the algorithms, time complexities, and performance data comparing the two approaches. This is part of our continuing work to bring to end users at least some of the benefits of formalized notions of testing without requiring knowledge of testing beyond a naive level     

An approach and tool for measurement of state variable based data-flow test coverage for aspect-oriented programs

ContextData-flow testing approaches have been used for procedural and object-oriented programs, and shown to be effective in detecting faults. However, few such approaches have been evaluated for aspect-oriented programs. In such programs, data-flow interactions can occur between base classes and aspects, which can affect the behavior of both. Faults resulting from such interactions are hard to detect unless the interactions are specifically targeted during testing.ObjectiveThis paper presents an approach and tool implementation for measuring data-flow coverage based on state variables defined in base classes or aspects in AspectJ programs. The paper also reports on an empirical study that compares the cost and effectiveness of data-flow test criteria that are based on state variables with two control-flow criteria.MethodEffectiveness of the criteria was evaluated for various fault types. Cost-effectiveness of test suites that cover all state variable definition-use associations (DUAs) was evaluated for three coverage levels: 100%, 90%, and 80%.ResultsThe effort needed to obtain a test case that achieves data-flow coverage is higher than the effort needed to obtain a test case that covers a block or a branch in an advised class. Covering certain data flow associations requires more effort than for other types of data flow associations. The data-flow test criteria based on state variables of a base-class are in general more effective than control-flow criteria.ConclusionsOverall, it is cost-effective to obtain test suites at the 90% coverage level of data-flow criteria.     

Using concepts of content‐based image retrieval to implement graphical testing oracles

Automation of testing is an essential requirement to render it viable for software development. Although there are several testing techniques and criteria in many different domains, developing methods to test programs with complex outputs remains an unsolved challenge. This setting includes programs with graphical output, which produce images or interface windows. One possible approach towards automating the testing activity is the use of automatic oracles in which a reference image, taken as correct, can be used to establish a correctness measure in the tested program execution. A method that uses concepts of content‐based image retrieval to facilitate oracle automation in the domain of programs with graphics output is presented. Two case studies, one using a computer‐aided diagnostic system and one using a Web application, are presented, including some reflections and discussions that demonstrate the feasibility of the proposed approach. Copyright © 2011 John Wiley & Sons, Ltd.     

Systematic testing and formal verification to validate reactive programs

The use of systematic testing and formal verification in the validation of reactive systems implemented in synchronous languages is illustrated. Systematic testing and formal verification are two techniques for checking the consistency between a program and its specification. The approach to validation is through specification: two system views are developed in addition to the program, a behavioural specification for systematic testing and a logical specification for formal verification. Pursuing both activities, reactive programs can be validated both more efficiently (in terms of costs) and more effectively (in terms of confidence in correctness). This principle is demonstrated here using the well known lift example.     

MujavaX: 一个支持非均匀分布的变异生成系统

变异分析是一种广泛用来评估软件测试技术性能的方法.已有的变异分析技术通常将变异算子平均地应用于原始程序.由于现实程序中的故障分布往往具有群束的特征,采用平均分布的变异分析方法不能客观地评估软件测试技术的性能.前期研究工作中提出了非均匀分布的变异分析方法,采用实例研究验证了不同的故障分布对测试技术性能评估的影响.为了增强非均匀分布的变异分析方法的实用性,开发了支持非均匀分布的变异生成系统MujavaX,该系统是对广泛实践的Mujava工具的扩展与改进.采用一个实例系统验证了开发的MujavaX的正确性与可行性,实验结果表明该系统能够生成指定分布的非均匀变体集合.     

Verifying Timing Constraints of Real-Time Systems by Means of Evolutionary Testing

Many industrial products are based on the use of embedded computer systems. Usually, these systems have to fulfil real-time requirements, and correct system functionality depends on their logical correctness as well as on their temporal correctness. In order to verify the temporal behavior of real-time systems, previous scientific work has, to a large extent, concentrated on static analysis techniques. Although these techniques offer the possibilty of providing safe estimates of temporal behavior for certain cases, there are a number of cases in practice for which static analysis can not be easily applied. Furthermore, no commercial tools for timing analysis of real-world programs are available. Therefore, the developed systems have to be thoroughly tested in order to detect existing deficiencies in temporal behavior, as well as to strengthen the confidence in temporal correctness. An investigation of existing test methods shows that they mostly concentrate on testing for logical correctness. They are not specialised in the examination of temporal correctness which is also essential to real-time systems. For this reason, existing test procedures must be supplemented by new methods which concentrate on determining whether the system violates its specified timing constraints. Normally, a violation means that outputs are produced too early, or their computation takes too long. The task of the tester therefore is to find the input situations with the longest or shortest execution times, in order to check whether they produce a temporal error. If the search for such inputs is interpreted as a problem of optimization, evolutionary computation can be used to automatically find the inputs with the longest or shortest execution times. This automatic search for accurate test data by means of evolutionary computation is called evolutionary testing. Experiments using evolutionary testing on a number of programs with up to 1511 LOC and 5000 input parameters have successfully identified new longer and shorter execution times than had been found using other testing techniques. Evolutionary testing, therefore, seems to be a promising approach for the verification of timing constraints. A combination of evolutionary testing and systematic testing offers further opportunities to improve the test quality, and could lead to an effective test strategy for real-time systems.     

Programs as partial graphs II: Recursion

In Part I of the paper, we have proposed a unified relational algebra approach using partial graphs for theoretical investigations on semantics, correctness and termination. This approach is extended here to systems of recursive programs, allowing not only sequencing and conditional branching as a control structure but also flow diagrams.An equivalence proof of operational and denotational semantics is obtained which is strictly based on axioms of relational algebra. A short new proof of an important completeness result is given in the generalized setting of systems of recursive flow diagram programs. Finally, Hitchcock-Park's theorem on derivatives is formulated in the general case of nondeterministic recursive flow diagram programs.     

一种基于动态并行区的OpenMP程序开发模式

通常,OpenMP程序开发将开发过程、程序正确性检测和性能分析分离开来.为此,提出动态并行区的概念,并在此基础上提出一种新的OpenMP程序开发模式,将OpenMP程序的开发过程、正确性检测和性能分析紧密地联系起来.在OpenMP程序开发的每一阶段,都能确保程序的正确性;同时,通过精确的性能分析与细微的性能调整,使得OpenMP程序的性能随开发的不断深入而逐步得到改进.据此开发的NPB2.3 OpenMP Fortran版的实测结果显示出该模式的可行性.     

被动测试和主动测试的研究

协议测试对于保证协议实现的正确性起着至关重要的作用．现在研究较多的测试方法是主动测试,被动测试则是一种新兴的测试方法．对两种测试思想进行比较，提出了将两者结合以获得更好测试质量和测试效率的算法，即先对IUT进行被动测试．通过测试收集一些有用的启发式信息．然后再将这些信息用于指导后续的主动测试，此算法已被用于BGP协议的测试，实验证明该算法可以提高主动测试效率。     

Generating effective tests for concurrent programs via AI automated planning techniques

Testing concurrent programs is a challenging problem due to interleaving explosion: even for a fixed set of inputs, there is a huge number of concurrent runs that need to be tested to account for scheduler behavior. Testing all possible schedules is not practical. Consequently, most effective testing algorithms only test a select subset of runs. For example, limiting testing to runs that contain data races or atomicity violations has been shown to capture a large proportion of concurrency bugs. In this paper we present a general approach to concurrent program testing that is based on techniques from artificial intelligence (AI) automated planning. We propose a framework for predicting concurrent program runs that violate a collection of generic correctness specifications for concurrent programs, namely runs that contain data races, atomicity violations, or null-pointer dereferences. Our prediction is based on observing an arbitrary run of the program, and using information collected from this run to model the behavior of the program, and to predict new runs that contain bugs with one of the above noted violation patterns. We characterize the problem of predicting such new runs as an AI sequential planning problem with the temporally extended goal of achieving a particular violation pattern. In contrast to many state-of-the-art approaches, in our approach feasibility of the predicted runs is guaranteed and, therefore, all generated runs are fully usable for testing. Moreover, our planning-based approach has the merit that it can easily accommodate a variety of violation patterns which serve as the selection criteria for guiding search in the state space of concurrent runs. This is achieved by simply modifying the planning goal. We have implemented our approach using state-of-the-art AI planning techniques and tested it within the Penelope concurrent program testing framework [35]. Nevertheless, the approach is general and is amenable to a variety of program testing frameworks. Our experiments with a benchmark suite showed that our approach is very fast and highly effective, finding all known bugs.     

Testing input validation in Web applications through automated model recovery

Input validation is essential and critical in Web applications. It is the enforcement of constraints that any input must satisfy before it is accepted to raise external effects. We have discovered some empirical properties for characterizing input validation in Web applications. In this paper, we propose an approach for automated recovery of input validation model from program source code. The model recovered is represented in a variant of control flow graph, called validation flow graph, which shows essential input validation features implemented in programs. Based on the model, we then formulate two coverage criteria for testing input validation. The two criteria can be used to guide the structural testing of input validation in Web applications. We have evaluated the proposed approach through case studies and experiments.     

Automated verification and testing of user‐interactive undo features in database applications

User‐interactive undo is a recovery facility that enables users to correct mistakes easily by canceling or re‐executing operations that have already been executed. This paper presents an interesting common structural property that has been discovered in programs that implementing user‐interactive undo features. The property shows that there is a one‐to‐one correspondence between program statements that raise erroneous effects and those statements that can undo these effects. Statistical validation has been conducted which gives evidences to show that this property holds for 99 per cent of all the cases. An approach for automated verification of user‐interactive undo features in database applications through the use of this empirical property is further proposed. Based on the verification results, test cases are automatically generated to confirm the correctness of these features. A case study has been conducted to evaluate the performance of the proposed verification and testing approach in terms of fault detection capability. Copyright © 2010 John Wiley & Sons, Ltd.     

Developing a self-applicable verification system. Theory and practice

Compared with traditional testing, the deductive verification represents a more formal way to establish the program correctness. However, can we be sure that the verification system itself is correct? The theoretical foundations of Hoare logic were examined in classical works, and some soundness/completeness theorems are well known. Nevertheless, we practically are not aware of implementations of those theoretical methods subjected to anything more than testing. In other words, our ultimate goal is a verification system that can be self-applicable (at least partially). In our recent studies, we applied the MetaVCG approach in order to make such a task more feasible.     

A General Model of Unit Testing Efficacy

Much of software engineering is targeted towards identifying and removing existing defects while preventing the injection of new ones. Defect management is therefore one important software development process whose principal aim is to ensure that the software produced reaches the required quality standard before it is shipped into the market place. In this paper, we report on the results of research conducted to develop a predictive model of the efficacy of one important defect management technique, that of unit testing. We have taken an empirical approach. We commence with a number of assumptions that led to a theoretical model which describes the relationship between effort expended and the number of defects remaining in a software code module tested (the latter measure being termed correctness). This model is general enough to capture the possibility that debugging of a software defect is not perfect and could lead to new defects being injected. The Model is examined empirically against actual data and validated as a good predictive model under specific conditions. The work has been done in such a way that models are derived not only for the case of overall correctness but also for specific types of correctness such as correctness arising from the removal of defects contributing to shortcoming in reliability (R-type), functionality (F-type), usability (U-type) and maintainability (M-type) aspects of the program subject to defect management.     

Integration testing of Object-Oriented and Aspect-Oriented programs: A structural pairwise approach for Java

Several testing approaches focus on finding faults in software units of implementation. A problem not addressed by unit testing is the interaction among units, with respect to the correctness of their interfaces. In this paper a structural integration testing approach for Object-Oriented (OO) and Aspect-Oriented (AO) Java programs is presented. To make the activity more feasible, we address the testing of pairs of units (i.e., methods and pieces of advice). A model called (PairWise Def-Use) graph to represent the flow of control and data between pairs of units is proposed. Based on the , the following family of testing criteria is defined: all-pairwise-integrated-nodes (control-flow based), all-pairwise-integrated-edges (control-flow based), and all-pairwise-integrated-uses (data-flow based). To evaluate the proposed approach, an implementation of the criteria in a testing tool is presented along with an example of usage and an exploratory study. The study with 7 AO programs that are also OO was conducted to investigate the cost of application and usefulness of the approach. Results provided evidence that the criteria are practical and useful for integration testing of OO and AO programs.