Exhaustive property oriented model-based testing with symbolic finite state machines

We advocate a fusion of property-oriented testing (POT) and model-based testing (MBT). The existence of a symbolic finite state machine (SFSM) model fulfilling the properties of interest is exploited for property-directed test data generation and to create a test oracle. A new test generation strategy is presented for verifying that the system under test (SUT) satisfies the same LTL safety conditions over a given set of atomic propositions as the model. We prove that this strategy is exhaustive in the sense that any SUT violating at least one of these formulae will fail at least one test case of the generated suite. It is shown that the existence of a model allows for significantly smaller exhaustive test suites as would be necessary for POT without reference models. As a corollary, the main theorem also generalises a known result about SFSM-based conformance testing for language equivalence. Our approach fits well to industrial development processes for (potentially safety-critical) cyber-physical systems, where both models and properties representing system requirements are elaborated for development, verification, and validation.     

An empirical investigation into branch coverage for C programs using CUTE and AUSTIN

Automated test data generation has remained a topic of considerable interest for several decades because it lies at the heart of attempts to automate the process of Software Testing. This paper reports the results of an empirical study using the dynamic symbolic-execution tool, CUTE, and a search based tool, AUSTIN on five non-trivial open source applications. The aim is to provide practitioners with an assessment of what can be achieved by existing techniques with little or no specialist knowledge and to provide researchers with baseline data against which to measure subsequent work. To achieve this, each tool is applied ‘as is’, with neither additional tuning nor supporting harnesses and with no adjustments applied to the subject programs under test. The mere fact that these tools can be applied ‘out of the box’ in this manner reflects the growing maturity of Automated test data generation. However, as might be expected, the study reveals opportunities for improvement and suggests ways to hybridize these two approaches that have hitherto been developed entirely independently.     

Using symbolic execution and data flow criteria to aid test data selection

The utilization is described of a data flow path selection criterion in a symbolic execution system. The system automatically generates a subset of program paths according to a certain control flow criterion. This subset is called the ZOT-subset, since it requires paths that traverse loops zero, one and two times. Experience indicates that traversing this subset of program paths is enough to cover most control flow and data flow components of the program. The problem with the ZOT-subset is that it might contain, for large programs, a large number of paths. The number of paths in this subset can be reduced by concentrating on executable paths that cover vital components of programs such as data flow components. This object is achieved by employing a data flow path selection criterion in the system. The system symbolically executes the paths of the ZOT-subset, and creates a system of branch conditions for each one. The user determines infeasible paths by checking the consistency of each system of conditions. The system selects feasible paths from the ZOT-subset that cover the data flow criterion. Solving the systems of conditions of the selected paths provides the user with test data to fulfil the given data flow criterion.     

An approach for experimentally evaluating effectiveness and efficiency of coverage criteria for software testing

Experimental work in software testing has generally focused on evaluating the effectiveness and effort requirements of various coverage criteria. The important issue of testing efficiency has not been sufficiently addressed. In this paper, we describe an approach for comparing the effectiveness and efficiency of test coverage criteria using mutation analysis. For each coverage criterion under study, we generate multiple coverage-adequate minimal test suites for a test-program from a test-pool, which are then executed on a set of systematically generated program mutants to obtain the fault data. We demonstrate the applicability of the proposed approach by describing the results of an experiment comparing the three code-based testing criteria, namely, block coverage, branch coverage, and predicate coverage. Our results suggest that there is a trade-off between effectiveness and efficiency of a coverage criterion. Specifically, the predicate coverage criterion was found to be most effective but least efficient whereas the block coverage criterion was most efficient but least effective. We observed high variability in the performance of block test suites whereas branch and predicate test suites were relatively consistent. Overall results suggest that the branch coverage criterion performs consistently with good efficiency and effectiveness, and it appears to be the most viable option for code-based control flow testing.     

Compiler testing using a sentence generator

A system for assisting in the testing phase of compilers is described. The definition of the language to be compiled drives an automatic sentence generator. The language is described by an extended BNF grammar which can be augmented by actions to ensure contextual congruence, e.g. between definition and use of identifiers. For deep control of the structure of the produced sample the grammar can be described by step-wise refinements: the generator is iteratively applied to each level of refinement, producing at last compilable, complete programs. The implementation is described and some experimental results are reported concerning PLZ, MINIPL and some other languages.     

A novel formalization of symbolic trajectory evaluation semantics in Isabelle/HOL

This paper presents a formal symbolic trajectory evaluation (STE) theory based on a structural netlist circuit model, instead of an abstract next state function. We introduce an inductive definition for netlists, which gives an accurate and formal definition for netlist structures. A closure state function of netlists is formally introduced in terms of the formal netlist model. We refine the definition of the defining trajectory and the STE implementation to deal with the closure state function. The close correspondence between netlist structures and properties is discussed. We present a set of novel algebraic laws to characterize the relation between the structures and properties of netlists. Finally, the application of the new laws is demonstrated by parameterized verification of the properties of content-addressable memories.     

An overview on test generation from functional requirements

Despite the fact that the test phase is described in the literature as one of the most relevant for quality assurance in software projects, this test phase is not usually developed, among others, with enough resources, time or suitable techniques.To offer solutions which supply the test phase, with appropriate tools for the automation of tests generation, or even, for their self-execution, could become a suitable way to improve this phase and reduce the cost constraints in real projects.This paper focuses on answering a concrete research question: is it possible to generate test cases from functional requirements described in an informal way? For this aim, it presents an overview of a set of relevant approaches that works in this field and offers a set of comparative analysis to determine which the state of the art is.     

Effects of computer-based testing on test performance and testing motivation

Computer-based testing (CBT) is a green computing strategies used to reduce paper consumption. However, some scholars have questioned the effectiveness of CBT and suggested for conducting systematic studies on CBT to carefully check its reliability and validity before opting for it. Recently, some studies have evaluated the effectiveness of CBT by comparing it with paper–pencil testing (PPT), and the findings were inconsistent. Besides this, most of these studies have been conducted using quasi or basic experimental designs without identifying testing effects on test takers. The limitation of these design is testing effects might occur when a participant in the control or treatment group is tested at least twice on a same test, and it influences the outcomes of taking a posttest, therefore, the findings might be misinterpreted. This study employed a Solomon four-group experimental design (2 × 3 factorial design) on a group of student teachers (n = 140) to compare CBT and PPT on test performance (test scores), testing time and testing motivation. Results indicated that the CBT mode is more reliable in terms of internal and external validity. The CBT significantly reduced testing time and developed stronger self-efficacy, intrinsic and social testing motivation in the participants.     

Generating input data structures for automated program testing

Automatic test data generation usually concerns identifying input values that cause a selected path to execute. If a given path involves pointers, then input values may be represented in terms of two‐dimensional dynamic data structures such as lists or trees. Thus, it is very important to identify the shape of the input data structure describing how many nodes are required and how nodes are connected each other. The approach presented in this paper makes use of the points‐to information for each statement in the selected path for the shape generation. It also converts each statement into a static single assignment (SSA) form without pointer dereferences. The SSA form serves as a system of constraints to be solved to yield input values for non‐pointer types. An empirical evaluation shows that shape generation can be achieved in linear time in terms of the number of pointer dereference operations. Copyright © 2008 John Wiley & Sons, Ltd.     

Software testing effectiveness modeling-Based on complete or missing detection data

Software testing is a critical part in software development life cycle. To some extent, software testing determines the success of the final product. An effective software testing helps to detect the potential bugs or faults and ensure the release of a defect free software product. However, only a little attention has been paid to testing effectiveness evaluation. How to evaluate testing effectiveness appropriately？ And what are the criteria for effectiveness evaluation？ This paper proposes a method which helps to assess the effectiveness of software testing properly so as to ensure the performance of testing process. And it concerns two testing situation： one is the historical testing data is complete and the other is the necessary testing data is missing.     

Mutation testing on an object-oriented framework: An experience report

Context

The increasing presence of Object-Oriented (OO) programs in industrial systems is progressively drawing the attention of mutation researchers toward this paradigm. However, while the number of research contributions in this topic is plentiful, the number of empirical results is still marginal and mostly provided by researchers rather than practitioners.

Objective

This article reports our experience using mutation testing to measure the effectiveness of an automated test data generator from a user perspective.

Method

In our study, we applied both traditional and class-level mutation operators to FaMa, an open source Java framework currently being used for research and commercial purposes. We also compared and contrasted our results with the data obtained from some motivating faults found in the literature and two real tools for the analysis of feature models, FaMa and SPLOT.

Results

Our results are summarized in a number of lessons learned supporting previous isolated results as well as new findings that hopefully will motivate further research in the field.

Conclusion

We conclude that mutation testing is an effective and affordable technique to measure the effectiveness of test mechanisms in OO systems. We found, however, several practical limitations in current tool support that should be addressed to facilitate the work of testers. We also missed specific techniques and tools to apply mutation testing at the system level.     

Empirical evaluation of the fault detection effectiveness and test effort efficiency of the automated AOP testing approaches

Context

Testing process is a time-consuming, expensive, and labor-intensive activity in any software setting including aspect-oriented programming (AOP). To reduce the testing costs, human effort, and to achieve the improvements in both quality and productivity of AOP, it is desirable to automate testing of aspect-oriented programs as much as possible.

Objective

In recent past years, a lot of research effort has been devoted to testing aspect-oriented programs but less effort has been dedicated to the automated AOP testing. This denotes that the current research on automated AOP testing is not sufficient and is still in a stage of infancy. In order to advance the state of the research in this area and to provide testers of AOP-based projects with a comparison basis, a detailed evaluation of the current automated AOP testing approaches in a thorough and experimental manner is required. Thus, the objective of this paper is to provide such evaluation of the current approaches.

Method

In this paper, we carry out an empirical study based on mutation analysis to examine four (namely Wrasp, Aspectra, Raspect, and EAT) existing automated AOP testing approaches, particularly their underlying test input generation and selection strategies, with regard to fault detection effectiveness. In addition, the approaches are compared in terms of required effort in detecting faults as part of efficiency evaluation.

Results

The experimental results and comparison provided insights into the effectiveness and efficiency of automated AOP testing with their respective strengths and weaknesses. Results showed that EAT is more effective than the other automated AOP testing approaches but not significant for all approaches. EAT was found to be significantly better than Wrasp at 95% confidence level (i.e. p < 0.05), but not significantly better than Aspectra or Raspect. Concerning the test effort efficiency, Wrasp was significantly (p < 0.05) efficient with requiring the lowest amount of test effort compared to the other approaches. Whereas, EAT showed to be not very efficient by recording the highest amount of test effort.

Conclusion

This implies that EAT can currently be the most effective automated AOP testing approach but perhaps less efficient. More generally, search-based testing (as underlying strategy of EAT approach) might achieve better effectiveness but at the cost of greater test effort compared to random testing (as underlying strategy of other approaches).     

Evaluating test suite characteristics,cost, and effectiveness of FSM-based testing methods

ContextTesting from finite state machines has been investigated due to its well-founded and sound theory as well as its practical application. There has been a recurrent interest in developing methods capable of generating test suites that detect all faults in a given fault domain. However, the proposal of new methods motivates the comparison with traditional methods.ObjectiveWe compare the methods that generate complete test suites from finite states machines. The test suites produced by the W, HSI, H, SPY, and P methods are analyzed in different configurations.MethodComplete and partial machines were randomly generated varying numbers of states, inputs, outputs, and transitions. These different configurations were used to compare test suite characteristics (number of resets, test case length) and the test suite length (i.e., the sum of the length of its test cases). The fault detection ratio was evaluated using mutation testing to produce faulty implementations with an extra state.ResultsOn average, the recent methods (H, SPY, and P) produced longer test cases but smaller test suites than the traditional methods (W, HSI). The recent methods generated test suites of similar length, though P produced slightly smaller test suites. The SPY and P methods had the highest fault detection ratios and HSI had the lowest. For all methods, there was a positive correlation between the number of resets and the test suite length and between the test case length and the fault detection ratio.ConclusionThe recent methods rely on fewer and longer test cases to reduce the overall test suite length, while the traditional methods produce more and shorter test cases. Longer test cases are correlated to fault detection ratio which favored SPY, though all methods have a ratio of over 92%.     

Fourier analysis of symbolic data: A brief review

We overview and discuss several methods for the Fourier analysis of symbolic data, such as DNA sequences, emphasizing their mutual connections. We consider the indicator sequence approach, the vector and the symbolic autocorrelation methods, and methods such as the spectral envelope, that for each frequency optimize the symbolic-no-numeric mapping to emphasize any periodic data features. We discuss the equivalence or connections between these methods. We show that it is possible to define the autocorrelation function of symbolic data, assuming only that we can compare any two symbols and decide if they are equal or distinct. The autocorrelation is a numeric sequence, and its Fourier transform can also be obtained by summing the squares of the Fourier transform of indicator sequences (zero/one sequences indicating the position of the symbols). Another interpretation of the spectrum is given, borrowing from the spectral envelope concept: among all symbolic-to-numeric mappings there is one that maximizes the spectral energy at each frequency, and leads to the spectrum.     

一种基于双约束传播的面向路径自动随机测试方法

随机测试是一种常用的软件测试自动化方法。该方法随机地从程序输入域中选取测试输入,其自动测试实现容易。但随机地从输入域中选取满足某种测试准则的输入数据,测试生成效率较低。为此提出了一种基于双约束传播的面向路径自动随机测试方法,通过对输入变量的取值范围进行切分,执行两次约束传播来求取指定路径的输入域,在此基础上开发了一个自动随机测试生成系统,并与PRT方法进行了实验对比分析。结果表明,该方法计算出的路径输入域更加精确,可有效地减少对无效域的测试生成,提高了随机测试的效率。     

Determining the effectiveness of three software evaluation techniques through informal aggregation

ContextAn accepted fact in software engineering is that software must undergo verification and validation process during development to ascertain and improve its quality level. But there are too many techniques than a single developer could master, yet, it is impossible to be certain that software is free of defects. So, it is crucial for developers to be able to choose from available evaluation techniques, the one most suitable and likely to yield optimum quality results for different products. Though, some knowledge is available on the strengths and weaknesses of the available software quality assurance techniques but not much is known yet on the relationship between different techniques and contextual behavior of the techniques.ObjectiveThis research investigates the effectiveness of two testing techniques – equivalence class partitioning and decision coverage and one review technique – code review by abstraction, in terms of their fault detection capability. This will be used to strengthen the practical knowledge available on these techniques.MethodThe results of eight experiments conducted over 5 years to investigate the effectiveness of three techniques – code reading by stepwise abstraction, equivalence class partitioning and decision (branch) coverage were aggregated using a less rigorous aggregation process proposed during the course of this work.ResultsIt was discovered that the equivalence class partitioning and the decision coverage techniques behaved similarly in terms of fault detection capacity (and type of faults caught) based on the programs and fault classification used in the experiments. They both behaved better than the code reading by stepwise abstraction technique.ConclusionOverall, it can be deducted from the aggregation results that the equivalence class partitioning and the decision coverage techniques used are actually equally capable in terms of the type and number of faults detected. Nevertheless, more experiments is still required in this field so that this result can be verified using a rigorous aggregation technique.     

智能优化在软件测试中的应用综述

软件测试是软件开发活动中一个关键且耗时的环节,其核心是生成满足特定准则的测试数据.随着软件复杂程度的不断增加,软件测试的难度也越来越高.使用遗传算法等智能优化方法解决复杂软件的测试问题,是近年来软件工程领域的一个研究热点.鉴于此,针对智能优化在软件测试的应用进行综述,首先介绍软件测试的基本原理和方法;然后介绍智能优化在...     

面向云测试的并行测试用例自动生成方法

为实现云计算环境下的高效软件测试,提出一种Web 应用系统功能测试的并行测试用例自动生成方法。该方法首先根据场景流图采用深度优先遍历算法生成并行测试路径,录制组合产生并行测试脚本,并进行参数化处理;然后,使用基于搜索的软件测试(SBST)方法自动生成可经过目标路径的有效测试数据集,脚本与数据耦合形成大量可并行部署的自动化测试用例。为验证方法的有效性设计了自动化云测试原型系统。实验结果表明,该并行测试用例自动生成方法可以高效地为云平台提供测试用例输入,提高测试效率。