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.     

基于规格说明的若干逻辑覆盖测试准则

基于规格说明的测试可以在不需要了解软件程序代码的情况下对软件进行功能测试.判定是形式规格说明中用于描述前、后置条件的主要形式.分析了基于规格说明的逻辑覆盖测试准则,针对已有的决定性逻辑覆盖测试准则的不足,提出了掩盖性逻辑覆盖测试准则,并对其进行了详细分析.提出了掩盖性逻辑覆盖测试准则的一个可行的测试生成算法.根据该准则生成的测试用例能够发现条件的掩盖性带来的错误.然后,从判定的结构入手,分析了条件之间的约束关系、复杂判定的分解与合成、判定之间的关系.这些分别能够阐明逻辑覆盖中条件间的耦合性问题、同一个条件在判定中的多次出现问题以及判定在程序中的位置问题.继而提出了全真判定覆盖、全假判定覆盖、完全子判定覆盖、唯一条件真覆盖以及唯一条件假覆盖等测试准则.满足这些测试准则的测试用例集能检测出不同类型的错误.最后,给出了这些测试准则之间的包含关系图,并建议了不同测试准则适用的应用场景.     

基于规格说明的若干逻辑覆盖测试准则

基于规格说明的测试可以在不需要了解软件程序代码的情况下对软件进行功能测试.判定是形式规格说明中用于描述前、后置条件的主要形式.分析了基于规格说明的逻辑覆盖测试准则,针对已有的决定性逻辑覆盖测试准则的不足,提出了掩盖性逻辑覆盖测试准则,并对其进行了详细分析.提出了掩盖性逻辑覆盖测试准则的一个可行的测试生成算法.根据该准则生成的测试用例能够发现条件的掩盖性带来的错误.然后,从判定的结构入手,分析了条件之间的约束关系、复杂判定的分解与合成、判定之间的关系.这些分别能够阐明逻辑覆盖中条件间的耦合性问题、同一个条件在判定中的多次出现问题以及判定在程序中的位置问题.继而提出了全真判定覆盖、全假判定覆盖、完全子判定覆盖、唯一条件真覆盖以及唯一条件假覆盖等测试准则.满足这些测试准则的测试用例集能检测出不同类型的错误.最后,给出了这些测试准则之间的包含关系图,并建议了不同测试准则适用的应用场景.     

TestEra: Specification-Based Testing of Java Programs Using SAT

TestEra is a framework for automated specification-based testing of Java programs. TestEra requires as input a Java method (in sourcecode or bytecode), a formal specification of the pre- and post-conditions of that method, and a bound that limits the size of the test cases to be generated. Using the method's pre-condition, TestEra automatically generates all nonisomorphic test inputs up to the given bound. It executes the method on each test input, and uses the method postcondition as an oracle to check the correctness of each output. Specifications are first-order logic formulae. As an enabling technology, TestEra uses the Alloy toolset, which provides an automatic SAT-based tool for analyzing first-order logic formulae. We have used TestEra to check several Java programs including an architecture for dynamic networks, the Alloy-alpha analyzer, a fault-tree analyzer, and methods from the Java Collection Framework.     

SimFuzz: Test case similarity directed deep fuzzing

Fuzzing is widely used to detect software vulnerabilities. Blackbox fuzzing does not require program source code. It mutates well-formed inputs to produce new ones. However, these new inputs usually do not exercise deep program semantics since the possibility that they can satisfy the conditions of a deep program state is low. As a result, blackbox fuzzing is often limited to identify vulnerabilities in input validation components of a program. Domain knowledge such as input specifications can be used to mitigate these limitations. However, it is often expensive to obtain such knowledge in practice. Whitebox fuzzing employs heavy analysis techniques, i.e., dynamic symbolic execution, to systematically generate test inputs and explore as many paths as possible. It is powerful to explore new program branches so as to identify more vulnerabilities. However, it has fundamental challenges such as unsolvable constraints and is difficult to scale to large programs due to path explosion. This paper proposes a novel fuzzing approach that aims to produce test inputs to explore deep program semantics effectively and efficiently. The fuzzing process comprises two stages. At the first stage, a traditional blackbox fuzzing approach is applied for test data generation. This process is guided by a novel test case similarity metric. At the second stage, a subset of the test inputs generated at the first stage is selected based on the test case similarity metric. Then, combination testing is applied on these selected test inputs to further generate new inputs. As a result, less redundant test inputs, i.e., inputs that just explore shallow program paths, are created at the first stage, and more distinct test inputs, i.e., inputs that explore deep program paths, are produced at the second stage. A prototype tool SimFuzz is developed and evaluated on real programs, and the experimental results are promising.     

Non-specification-based approaches to logic testing for software

Testing is a crucial part of the development of software systems. In this paper, we consider testing of an implementation that is intended to satisfy a Boolean formula. In the literature, specification-based testing has been suggested for this purpose. Typically, such methods first hypothesize a fault class and then generate tests. However, there is almost no research that justifies fault classes proposed previously. Moreover, specifications amenable to automatic test generation are not always available to testers in practice. Based on these observations, we examine the applicability of non-specification-based approaches, which need no specification in the form of a Boolean formula to create tests. We compare a specification-based approach to three non-specification-based approaches, namely, random testing, antirandom testing, and combinatorial testing. The results of an experiment show that combinatorial testing is often comparative to specification-based testing and is superior to both random testing and antirandom testing.     

Program testing by specification mutation

Both theoretical and empirical arguments suggest that specifications and implementations are equally important sources of information for generating test cases. Nevertheless, the majority of test generation procedures described in the literature deal only with the program source, ignoring specifications. In this paper we outline a procedure for measuring test case effectiveness using specifications given in predicate calculus form. This method is similar to the mutation analysis method of testing programs.     

Specification-based Testing for Gui-based Applications

The development of GUI-based applications has raised a lot of new issues, one of them being how to automate effective testing for applications with complicated graphical user interactions. In this paper, we discuss the architectural issues and the implementation concerns of our approach to an automated specification-based testing technique for GUI-based applications. This approach is carried out by enriching existing architecture for automated specification-based testing. An essential part of our work is a visual environment to obtain test specifications. This environment pre-runs the Application Under Test (AUT) under its own control, with two prominent characteristics: First, testers can edit test specifications within the true GUI environment of the AUT. Second, the recorded input and output contain the same references as those in the AUT, so that the test cases generated from the edited specification can be used directly by test oracles during the automated testing procedure.We present our running prototype of a visual specification editor that allows users to graphically manipulate test specifications when these specifications are given in term of Finite State Machines (FSM) and the implementations of the AUT are GUI-based Java applications.     

面向RISC-V的汇编程序语义等价性自动化测试系统

本文设计并实现了一套面向RISC-V的汇编程序语义等价性自动化测试系统.在面向RISC-V开发软件时,尤其是基于扩展指令(例如向量指令)编写高效的程序时,很难避免以手写汇编的方式编写代码.例如,为标准的C函数库编写相应的向量版函数.与编译器自动生成的代码不同,手写的汇编代码虽然可以最大限度地提高程序的效率,但因绕过了编译时对程序的约束(如类型检查、寄存器分配等)而对开发者提出了更高的要求.能否对新版本与标准版本的汇编程序进行快速地、自动化的语义等价性测试,将大大影响代码的正确性和软件开发和调试的效率.已有面向RISC-V的测试框架缺乏对语义等价性测试的支持,也未考虑程序执行带来的副作用.本研究基于模拟器的动态测试环境,设计并实现了一套面向RISC-V的汇编程序语义等价性自动化测试系统.系统通过跟踪机器状态,捕获程序执行的副作用,并结合用户定义的测试目标生成测试报告.实验表明,本系统相比已有的测试系统,能够有效地对RISC-V汇编程序的语义等价性进行测试.     

一种用于软件测试的程序结构划分方法

软件测试中的结构性测试是以程序的结构为基础生成测试用例，以测试准则为判定测试的充分性，由于程序结构的复杂性，难于保证对程序进行充分而高效的测试，本文提出了一种基于程序依赖图的程序结构划分的测试方法，即程序块划分法。该方法难过对程序进行结构划分，将复杂的程序分解为若干程序块，并通过程序块间的数据依赖关系导出各程序块的语义，从而使测试可以在程序块的级别的基础上独立进行。     

Use of sequencing constraints for specification-based testing ofconcurrent programs

This paper presents and evaluates a specification-based methodology for testing concurrent programs. This methodology requires sequencing constraints, which specify restrictions on the allowed sequences of synchronization events. Sequencing constraints for a concurrent program can be derived from the program's formal or informal specification. Details of the proposed testing methodology based on the use of Constraints on Succeeding and Preceding Events (CSPE) are given. How to achieve coverage and detect violations of CSPE constraints for a concurrent program, according to deterministic and nondeterministic testing of this program, are described. A coverage criterion for CSPE-based testing is defined and analyzed. The results of empirical studies of CSPE-based testing for four concurrent problems are reported. These results indicate that the use of sequencing constraints for specification-based testing of concurrent programs is a promising approach     

ConData: A Tool for Automating Specification-Based Test Case Generation for Communication Systems

This paper describes a tool called ConData used as test generation for communication protocols specified as extended finite state machines. The strategy for test generation combines different specification-based test methods: (i) transition testing for the control part of a protocol and (ii) syntax and equivalence partitioning for the data part. The tool uses a representation of the protocol in PSL (Protocol Specification Language), which is transformed into a format readable by a Prolog program. This implements the test strategies mentioned above. The text also presents some results obtained in the test generation for the protocol of the Tele-command Communication System of the SACI-1 satellite.     

A distributed framework for demand-driven software vulnerability detection

Security testing aims at detecting program security flaws through a set of test cases and has become an active area of research. The challenge is how to efficiently produce test cases that are highly effective in detecting security flaws. This paper presents a novel distributed demand-driven security testing system to address this challenge. It leverages how end users use the software to increase the coverage of essential paths for security testing. The proposed system consists of many client sites and one testing site. The software under test is installed at each client site. Whenever a new path is about to be exercised by a user input, it will be sent to the testing site for security testing. At the testing site, symbolic execution is used to check any potential vulnerability on this new path. If a vulnerability is detected, a signature is automatically generated and updated to all client sites for protection. The benefits are as follows. First, it allows us to focus testing on essential paths, i.e., the paths that are actually being explored by users or attackers. Second, it stops an attacker from exploiting an unreported vulnerability at the client site. A prototype system has been implemented to evaluate the performance of the proposed system. The results show that it is both effective and efficient in practice.     

Test frame updating in CPM testing of Prolog programs

Category Partition Method (CPM) is a general approach to specification-based program testing, where test frame reduction and refinement are two important issues. Test frame reduction is necessary since too many test frames may be produced, and test frame refinement is important since during CPM testing new information about test frame generation may be achieved and considered incrementally. Besides the information provided by testers or users, implementation related knowledge offers alternative information for reducing and refining CPM test frames. This paper explores the idea by proposing a call patterns semantics based test frame updating method for Prolog programs, in which a call patterns analysis is used to collect information about the way in which procedures are used in a program. The updated test frames will be represented as constraints. The effect of our test frame updating is two-fold. On one hand, it removes “uncared” data from the original set of test frames; on the other hand, it refines the test frames to which we should pay more attention. The first effect makes the input domain on which a procedure must be tested a subset of the procedure’s input domain, and the latter makes testers stand more chance to find out the faults that are more likely to show their presence in the use of the program under consideration. Our test frame updating method preserves the effectiveness of CPM testing with respect to the detection of faults we care. The test case generation from the updated set of test frames is also discussed. In order to show the applicability of our method an approximation call patterns semantics is proposed, and the test frame updating on the semantics is illustrated by an example.

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.     

A theoretical basis for stepwise refinement and the programming calculus

A uniform treatment of specifications, programs, and programming is presented. The treatment is based on adding a specification statement to a given procedural language and defining its semantics. The extended language is thus a specification language and programs are viewed as a subclass of specifications. A partial ordering on specifications/programs corresponding to ‘more defined’ is defined. In this partial ordering the program/specification hybrids that arise in the construction of a program by stepwise refinement form a monotonic sequence. We show how Dijkstra's calculus for the derivation of programs corresponds to constructing this monotonic sequence. Formalizing the calculus thus gives some insight into the intellectual activity it demands and allows us to hint at further developments.     

Automatic Synthesis of Recursive Programs: The Proof-Planning Paradigm

We describe a proof method that characterises a family of proofs corresponding to the synthesis of recursive functional programs. This method provides a significant degree of automation in the construction of recursive programs from specifications, together with correctness proofs. This method makes use of meta-variables to allow successive refinement of the identity of unknowns, and so allows the program and the proof to be developed hand in hand. We illustrate it with parts of a substantial example—the synthesis of a unification algorithm.     

An experimental assessment of module documentation-based testing

Context

Testing a module that has memory using the black-box approach has been found to be expensive and relatively ineffective. Instead, testing without knowledge of the specifications (white-box approach) may not be effective in showing whether a program has been properly implemented as stated in its specifications. We propose instead a grey-box approach called Module Documentation-based Testing or MD-Test, the heart of which is an automatic generation of the test oracle from the external and internal views of the module.

Objective

This paper presents an empirical analysis and comparison of MD-Test against three existing testing tools.

Method

The experiment was conducted using a mutation-testing approach, in two phases that assess the capability of MD-Test in general and its capability of evaluating test results in particular.

Results

The results of the general assessment indicate that MD-Test is more effective than the other three tools under comparison, where it is able to detect all faults. The second phase of the experiment, which is significant to this study, compares the capabilities of MD-Test and JUnit-black using the test evaluation results. Likewise, an analysis of the test evaluation results shows that MD-Test is more effective and efficient, where MD-Test is able to detect at least the same number of faults as, or is at par with, the black-box approach.

Conclusion

It is concluded that test evaluation using grey-box approach is more effective and efficient that the black-box approach when testing a module that has memory.     

基于统计占优分析的变异测试

为数众多的变异体产生的高昂测试代价严重影响了变异测试技术在实际程序中的应用.为了大幅度减少弱变异测试中变异体的数量,提出基于统计占优分析的变异体约简方法.该方法首先利用变异前后的语句构造变异分支,并将所有变异分支集成到原程序中,形成新的被测程序;然后,通过统计测试用例对各个变异分支的覆盖信息,确定变异分支之间的占优关系;最后得到非被占优分支集,其对应的变异体就是约简后的变异体.将该方法用于8个程序的测试,结果表明:该方法能够约简平均90%的变异体,从而显著提高了变异测试的效率.     

Path testing of computer programs with loops using a tool for simple loop patterns

The purpose of this paper is to present a method for testing computer programs with iteration loops. Given such programs, we have shown that for classes of program paths, identified as sequences of simple loop paths, there is a characterizing function called a simple loop pattern. The key idea of simple loop patterns is that these special functions form a base set which can represent any path computation in the given program. A software tool called SILOP has been developed to automatically generate these simple loop patterns, and each corresponding sequence of simple loop paths can be considered as a test case. The tester uses each test case, and with knowledge of the application program, can generate corresponding test data. This paper also presents a method for selecting the specific paths and test data to determine the simple loop pattern reliably. The tester can use this selection method to predict the number of tests required. In order to apply this selection method, the given program must be a linear computer program. The SILOP tool and this test selection method have been applied to commercial software; in this paper, this computational experience is reported and several examples are given to demonstrate the approach.