Search based algorithms for test sequence generation in functional testing

ContextThe generation of dynamic test sequences from a formal specification, complementing traditional testing methods in order to find errors in the source code.ObjectiveIn this paper we extend one specific combinatorial test approach, the Classification Tree Method (CTM), with transition information to generate test sequences. Although we use CTM, this extension is also possible for any combinatorial testing method.MethodThe generation of minimal test sequences that fulfill the demanded coverage criteria is an NP-hard problem. Therefore, search-based approaches are required to find such (near) optimal test sequences.ResultsThe experimental analysis compares the search-based technique with a greedy algorithm on a set of 12 hierarchical concurrent models of programs extracted from the literature. Our proposed search-based approaches (GTSG and ACOts) are able to generate test sequences by finding the shortest valid path to achieve full class (state) and transition coverage.ConclusionThe extended classification tree is useful for generating of test sequences. Moreover, the experimental analysis reveals that our search-based approaches are better than the greedy deterministic approach, especially in the most complex instances. All presented algorithms are actually integrated into a professional tool for functional testing.     

Systematic scenario test case generation for nuclear safety systems

ContextThe current validation tests for nuclear software are routinely performed by random testing, which leads to uncertain test coverage. Moreover, validation tests should directly verify the system’s compliance with the original user’s needs. Unlike current model-based testing methods, which are generally based on requirements or design models, the proposed model is derived from the original user’s needs in text through domain-specific ontology, and then used to generate validation tests systematically.ObjectiveOur first goal is to develop an objective, repeatable, and efficient systematic validation test scheme that is effective for large systems, with analyzable test coverage. Our second goal is to provide a new model-based validation testing method that reflects the user’s original safety needs.MethodA model-based scenario test case generation for nuclear digital safety systems was designed. This was achieved by converting the scenarios described in natural language in a Safety Analysis Report (SAR) prepared by the power company for licensing review, to Unified Modeling Language (UML) sequence diagrams based on a proposed ontology of a related regulatory standard. Next, we extracted the initial environmental parameters and the described operational sequences. We then performed variations on these data to systematically generate a sufficient number of scenario test cases.ResultsTest coverage criteria, which are the equivalence partition coverage of initial environment, the condition coverage, the action coverage and the scenario coverage, were met using our method.ConclusionThe proposed model-based scenario testing can provide improved testing coverage than random testing. A test suite based on user needs can be provided.     

Estimating software testing complexity

ContextComplexity measures provide us some information about software artifacts. A measure of the difficulty of testing a piece of code could be very useful to take control about the test phase.ObjectiveThe aim in this paper is the definition of a new measure of the difficulty for a computer to generate test cases, we call it Branch Coverage Expectation (BCE). We also analyze the most common complexity measures and the most important features of a program. With this analysis we are trying to discover whether there exists a relationship between them and the code coverage of an automatically generated test suite.MethodThe definition of this measure is based on a Markov model of the program. This model is used not only to compute the BCE, but also to provide an estimation of the number of test cases needed to reach a given coverage level in the program. In order to check our proposal, we perform a theoretical validation and we carry out an empirical validation study using 2600 test programs.ResultsThe results show that the previously existing measures are not so useful to estimate the difficulty of testing a program, because they are not highly correlated with the code coverage. Our proposed measure is much more correlated with the code coverage than the existing complexity measures.ConclusionThe high correlation of our measure with the code coverage suggests that the BCE measure is a very promising way of measuring the difficulty to automatically test a program. Our proposed measure is useful for predicting the behavior of an automatic test case generator.     

Automatic test case generation for structural testing of function block diagrams

ContextFunction Block Diagram (FBD) is increasingly used in safety-critical applications. Test coverage issues for FBDs are frequently raised by regulators and users. However, there is little work at this aspect on testing FBD at model level. Our previous study has designed a new data-flow test coverage criterion, FB-Path Complete Condition Test Coverage (FPCC), that can directly test FBD structures and effectively detect function mutation errors. Nevertheless, because FPCC scheme involves several data-flow concepts and thus it is somewhat complicated to comprehend and to generate FPCC-complied test cases. An automatic test suite generator for FPCC is highly desirable.ObjectiveThis study designs an automatic test case generator, FPCCTestGen, for FPCC so as to enhance the practicability and acceptance of the FPCC approach.MethodFirst, a supporting infrastructure for performing automatic FBD-to-UPPAAL-for-FPCC transformation is designed. The supporting infrastructure includes templates, declarations, and functions as building blocks for transformation. Then, for each input FBD, represented in PLCopen XML format, FPCCTestGen performs parsing and converts FBD components into corresponding UPPAAL model components using aforementioned building blocks. After that, queries related to FPCC characteristics are submitted to UPPAAL model checker for verification. Finally, the verification traces are analyzed to obtain a FPCC-complied test suite.ResultsA safety injection system is used as a case study. Preliminary results show that the generated test suite achieves the highest FPCC percentage with a near optimal number of test cases.ConclusionThis automatic test case generation tool is effective and thus, can promote the use of the new test coverage criterion. Methodology used in FPCCTestGen is generic and can be applied to test suite generation for other test criteria on data-flow programs.     

Testing aspect‐oriented programs with finite state machines

Aspect‐oriented programming yields new types of programming faults due to the introduction of new constructs for dealing with crosscutting concerns. To reveal aspect faults, this paper presents a framework for testing whether or not aspect‐oriented programs conform to their state models. It supports two families of strategies (i.e. structure‐oriented and property‐oriented) for automated generation of aspect tests from aspect‐oriented state models. A structure‐oriented testing strategy derives tests and test code from an aspect‐oriented state model to meet a given structural coverage criterion, such as state coverage, transition coverage, or round trip. A property‐oriented testing strategy generates test code from the counterexamples of model checking. Two such strategies are checking an aspect‐oriented state model against trap properties and checking mutants of aspect models against system properties. Mutation analysis of aspect‐oriented programs is used to evaluate the effectiveness of these testing strategies. The experiments demonstrate that testing aspect‐oriented programs against their state models can detect many aspect faults. The comparative evaluations also reveal that the structure‐oriented and property‐oriented testing strategies complement each other—some aspect faults were detected by the structure‐oriented strategies, but not by the property‐oriented strategies and vice versa. Copyright © 2010 John Wiley & Sons, Ltd.     

Generating semantically valid test inputs using constrained input grammars

ContextGenerating test cases based on software input interface is a black-box testing technique that can be made more effective by using structured input models such as input grammars. Automatically generating grammar-based test inputs may lead to structurally valid but semantically invalid inputs that may be rejected in early semantic error checking phases of a system under test.ObjectiveThis paper aims to introduce a method for specifying a grammar-based input model with the model’s semantic constraints to be used in the generation of positive test inputs. It is also important that the method can generate effective test suites based on appropriate grammar-based coverage criteria.MethodFormal specification of both input structure and input semantics provides the opportunity to use model instantiation techniques to create model instances that satisfy all specified constraints. The input interface of a subject system can be specified using a high-level specification scheme such as attribute grammars, and a transformation function from this scheme to an instantiable formal modeling language can generate the desired model instances.ResultsWe propose a declarative grammar-based input specification method that is based on a variation of attribute grammars and allows the user to specify input constraints in addition to input structure. The model can be instantiated automatically to generate structurally and semantically valid test inputs. The proposed method has the capability to specify test requirements and coverage criteria and use them to generate valid test suites that satisfy test coverage criteria requirements.ConclusionThe work presented in this paper provides a black-box test generation method for grammar-based software inputs that can automatically generate criteria-covering test suites.     

Empirical evaluations on the cost-effectiveness of state-based testing: An industrial case study

ContextTest models describe the expected behavior of the software under test and provide the basis for test case and oracle generation. When test models are expressed as UML state machines, this is typically referred to as state-based testing (SBT). Despite the importance of being systematic while testing, all testing activities are limited by resource constraints. Thus, reducing the cost of testing while ensuring sufficient fault detection is a common goal in software development. No rigorous industrial case studies of SBT have yet been published.ObjectiveIn this paper, we evaluate the cost-effectiveness of SBT on actual control software by studying the combined influence of four testing aspects: coverage criterion, test oracle, test model and unspecified behavior (sneak paths).MethodAn industrial case study was used to investigate the cost-effectiveness of SBT. To enable the evaluation of SBT techniques, a model-based testing tool was configured and used to automatically generate test suites. The test suites were evaluated using 26 real faults collected in a field study.ResultsResults show that the more detailed and rigorous the test model and oracle, the higher the fault-detection ability of SBT. A less precise oracle achieved 67% fault detection, but the overall cost reduction of 13% was not enough to make the loss an acceptable trade-off. Removing details from the test model significantly reduced the cost by 85%. Interestingly, only a 24–37% reduction in fault detection was observed. Testing for sneak paths killed the remaining eleven mutants that could not be killed by the conformance test strategies.ConclusionsEach of the studied testing aspects influences cost-effectiveness and must be carefully considered in context when selecting strategies. Regardless of these choices, sneak-path testing is a necessary step in SBT since sneak paths are common while also undetectable by conformance testing.     

Validation of SDL specifications using EFSM-based test generation

Existing methods for testing an SDL specification mainly allow for either black box simulation or conformance testing to verify that the behavior of an implementation matches its corresponding model. However, this relies on the potentially hazardous assumption that the model is completely correct. We propose a test generation method that can accomplish conformance verification as well as coverage criteria-driven white box testing of the specification itself. We first reformat a set of EFSMs equivalent to the processes in an SDL specification and identify “hot spots” – nodes or edges in the EFSM which should be prioritized during testing to effectively increase coverage. Then, we generate test sequences intended to cover selected hot spots; we address the possible infeasibility of such a test sequence by allowing for its rejection decided by a constraint solver and re-generation of an alternate test sequence to the hot spot. In this paper, we present our test generation method and tool, and provide case studies on five SDL processes demonstrating the effectiveness of our coverage-based test sequence selection.     

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

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

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

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

A search-based framework for automatic testing of MATLAB/Simulink models

Search-based test-data generation has proved successful for code-level testing but almost no search-based work has been carried out at higher levels of abstraction. In this paper the application of such approaches at the higher levels of abstraction offered by MATLAB/Simulink models is investigated and a wide-ranging framework for test-data generation and management is presented. Model-level analogues of code-level structural coverage criteria are presented and search-based approaches to achieving them are described. The paper also describes the first search-based approach to the generation of mutant-killing test data, addressing a fundamental limitation of mutation testing. Some problems remain whatever the level of abstraction considered. In particular, complexity introduced by the presence of persistent state when generating test sequences is as much a challenge at the Simulink model level as it has been found to be at the code level. The framework addresses this problem. Finally, a flexible approach to test sub-set extraction is presented, allowing testing resources to be deployed effectively and efficiently.     

Analysing the effectiveness of rule-coverage as a reduction criterion for test suites of grammar-based software

The term grammar-based software describes software whose input can be specified by a context-free grammar. This grammar may occur explicitly in the software, in the form of an input specification to a parser generator, or implicitly, in the form of a hand-written parser. Grammar-based software includes not only programming language compilers, but also tools for program analysis, reverse engineering, software metrics and documentation generation. Hence, ensuring their completeness and correctness is a vital prerequisite for their use. In this paper we propose a strategy for the construction of test suites for grammar based software, and illustrate this strategy using the ISO C^+ + grammar. We use the concept of grammar-rule coverage as a pivot for the reduction of an implementation-based test suite, and demonstrate a significant decrease in the size of this suite. The effectiveness of this reduced test suite is compared to the original test suite with respect to code coverage and more importantly, fault detection. This work greatly expands upon previous work in this area and utilises large scale mutation testing to compare the effectiveness of grammar-rule coverage to that of statement coverage as a reduction criterion for test suites of grammar-based software. This work finds that when grammar rule coverage is used as the sole criterion for reducing test suites of grammar based software, the fault detection capability of that reduced test suite is greatly diminished when compared to other coverage criteria such as statement coverage.

Optimizing compilation with preservation of structural code coverage metrics to support software testing

Code‐coverage‐based testing is a widely‐used testing strategy with the aim of providing a meaningful decision criterion for the adequacy of a test suite. Code‐coverage‐based testing is also mandated for the development of safety‐critical applications; for example, the DO178b document requires the application of the modified condition/decision coverage. One critical issue of code‐coverage testing is that structural code coverage criteria are typically applied to source code whereas the generated machine code may result in a different code structure because of code optimizations performed by a compiler. In this work, we present the automatic calculation of coverage profiles describing which structural code‐coverage criteria are preserved by which code optimization, independently of the concrete test suite. These coverage profiles allow to easily extend compilers with the feature of preserving any given code‐coverage criteria by enabling only those code optimizations that preserve it. Furthermore, we describe the integration of these coverage profile into the compiler GCC. With these coverage profiles, we answer the question of how much code optimization is possible without compromising the error‐detection likelihood of a given test suite. Experimental results conclude that the performance cost to achieve preservation of structural code coverage in GCC is rather low. Copyright © 2012 John Wiley & Sons, Ltd.     

Defining a test coverage criterion for model-level testing of FBD programs

ContextThe Programmable Logic Controller (PLC) is being integrated into the automation and control of computer systems in safety–critical domains at an increasing rate. Thoroughly testing such software to ensure safety is crucial. Function Block Diagram (FBD) is a popular data-flow programming language for PLC. Current practice often involves translating an FBD program into an equivalent C program for testing. Little research has been conducted on coverage of direct testing a data-flow program, such as an FBD program, at the model level. There are no commonly accepted structural test coverage criteria for data-flow programs. The objective of this study is to develop effective structural test coverage criterion for testing model-level FBD programs. The proposed testing scheme can be used to detect mutation errors at the logical function level.ObjectiveThe purpose of this study is to design a new test coverage criterion that can directly test FBD programs and effectively detect logical function mutation errors.MethodA complete test set for each function and function block in an FBD program are defined. Moreover, this method augments the data-flow path concept with a sensitivity check to avoid fault masking and effectively detect logical function mutation errors.ResultsPreliminary experiments show that this test coverage criterion is comprehensive and effective for error detection.ConclusionThe proposed coverage criterion is general and can be applied to real cases to improve the quality of data-flow program design.     

Mutation based test case generation via a path selection strategy

ContextGenerally, mutation analysis has been identified as a powerful testing method. Researchers have shown that its use as a testing criterion exercises quite thoroughly the system under test while it achieves to reveal more faults than standard structural testing criteria. Despite its potential, mutation fails to be adopted in a widespread practical use and its popularity falls significantly short when compared with other structural methods. This can be attributed to the lack of thorough studies dealing with the practical problems introduced by mutation and the assessment of the effort needed when applying it. Such an incident, masks the real cost involved preventing the development of easy and effective to use strategies to circumvent this problem.ObjectiveIn this paper, a path selection strategy for selecting test cases able to effectively kill mutants when performing weak mutation testing is presented and analysed.MethodThe testing effort is highly correlated with the number of attempts the tester makes in order to generate adequate test cases. Therefore, a significant influence on the efficiency associated with a test case generation strategy greatly depends on the number of candidate paths selected in order to achieve a predefined coverage goal. The effort can thus be related to the number of infeasible paths encountered during the test case generation process.ResultsAn experiment, investigating well over 55 million of program paths is conducted based on a strategy that alleviates the effects of infeasible paths. Strategy details, along with a prototype implementation are reported and analysed through the experimental results obtained by its employment to a set of program units.ConclusionThe results obtained suggest that the strategy used can play an important role in making the mutation testing method more appealing and practical.     

Specification-driven model transformation testing

Testing model transformations poses several challenges, among them the automatic generation of appropriate input test models and the specification of oracle functions. Most approaches for the generation of input models ensure a certain coverage of the source meta-model or the transformation implementation code, whereas oracle functions are frequently defined using query or graph languages. However, these two tasks are usually performed independently regardless of their common purpose, and sometimes, there is a gap between the properties exhibited by the generated input models and those considered by the transformations. Recently, we proposed a formal specification language for the declarative formulation of transformation properties (by means of invariants, pre-, and postconditions) from which we generated partial oracle functions used for transformation testing. Here, we extend the usage of our specification language for the automated generation of input test models by SAT solving. The testing process becomes more intentional because the generated models ensure a certain coverage of the transformation requirements. Moreover, we use the same specification to consistently derive both the input test models and the oracle functions. A set of experiments is presented, aimed at measuring the efficacy of our technique.     

Dynamic stopping criteria for search-based test data generation for path testing

ContextEvolutionary algorithms have proved to be successful for generating test data for path coverage testing. However in this approach, the set of target paths to be covered may include some that are infeasible. It is impossible to find test data to cover those paths. Rather than searching indefinitely, or until a fixed limit of generations is reached, it would be desirable to stop searching as soon it seems likely that feasible paths have been covered and all remaining un-covered target paths are infeasible.ObjectiveThe objective is to develop criteria to halt the evolutionary test data generation process as soon as it seems not worth continuing, without compromising testing confidence level.MethodDrawing on software reliability growth models as an analogy, this paper proposes and evaluates a method for determining when it is no longer worthwhile to continue searching for test data to cover un-covered target paths. We outline the method, its key parameters, and how it can be used as the basis for different decision rules for early termination of a search. Twenty-one test programs from the SBSE path testing literature are used to evaluate the method.ResultsCompared to searching for a standard number of generations, an average of 30–75% of total computation was avoided in test programs with infeasible paths, and no feasible paths were missed due to early termination. The extra computation in programs with no infeasible paths was negligible.ConclusionsThe method is effective and efficient. It avoids the need to specify a limit on the number of generations for searching. It can help to overcome problems caused by infeasible paths in search-based test data generation for path testing.     

Model-based testing using UML activity diagrams: A systematic mapping study

Context:The Unified Modeling Language (UML) has become the de facto standard for software modeling. UML models are often used to visualize, understand, and communicate the structure and behavior of a system. UML activity diagrams (ADs) are often used to elaborate and visualize individual use cases. Due to their higher level of abstraction and process-oriented perspective, UML ADs are also highly suitable for model-based test generation. In the last two decades, different researchers have used UML ADs for test generation. Despite the growing use of UML ADs for model-based testing, there are currently no comprehensive and unbiased studies on the topic.Objective:To present a comprehensive and unbiased overview of the state-of-the-art on model-based testing using UML ADs.Method:We review and structure the current body of knowledge on model-based testing using UML ADs by performing a systematic mapping study using well-known guidelines. We pose nine research questions, outline our selection criteria, and develop a classification scheme.Results:The results comprise 41 primary studies analyzed against nine research questions. We also highlight the current trends and research gaps in model-based testing using UML ADs and discuss some shortcomings for researchers and practitioners working in this area. The results show that the existing approaches on model-based testing using UML ADs tend to rely on intermediate formats and formalisms for model verification and test generation, employ a multitude of graph-based coverage criteria, and use graph search algorithms.Conclusion:We present a comprehensive overview of the existing approaches on model-based testing using UML ADs. We conclude that (1) UML ADs are not being used for non-functional testing, (2) only a few approaches have been validated against realistic, industrial case studies, (3) most approaches target very restricted application domains, and (4) there is currently a clear lack of holistic approaches for model-based testing using UML ADs.     

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.     

Automated generation of test oracles using a model-driven approach

ContextSoftware development time has been reduced with new development tools and paradigms, testing must accompany these changes. In order to release software products in a timely manner as well as to minimise the impact of possible errors introduced during maintenance interventions, testing automation has become a central goal. Whilst research has produced significant results in test case generation and tools for test case (re)-execution, one of the most important open problems in testing is the automation of oracle generation. The oracle decides whether the program under test has or has not behaved correctly and then issues a pass/fail verdict. In most cases, writing the oracle is a time-consuming activity that, moreover, is manual in most cases.ObjectiveThis article automates two important steps in the test oracle: obtention of expected output and its comparison with the actual output, using a model-driven approach.MethodThe oracle automation problem is resolved using a model-driven framework, based on OMG standards: UML is used as metamodel and QVT and MOF2Text as transformation languages. The automated testing framework takes the models that describe the system as input, using UML notation and derives from them the test model and then the test code, following a model-driven approach. Test oracle procedures are obtained from a UML state machine.ResultsA complete executable test case at functional test level is obtained, composed of a test procedure with parametrized input test data and expected result automation.ConclusionThe oracle automation is obtained using a model-driven approach, test cases are obtained automatically from UML models. The model-driven testing framework was applied to an industrial application and has been useful to testing automation for the main functionalities in the system.