A dynamic stochastic model for automatic grammar‐based test generation

Grammar‐based test generation provides a systematic approach to producing test cases from a given context‐free grammar. Unfortunately, naive grammar‐based test generation is problematic because of the fact that exhaustive random test case production is often explosive, and grammar‐based test generation with explicit annotation controls often causes unbalanced testing coverage. In this paper, we present an automatic grammar‐based test generation approach, which takes a symbolic grammar as input, requires zero control input from users, and produces well‐distributed test cases. Our approach utilizes a novel dynamic stochastic model where each variable is associated with a tuple of probability distributions, which are dynamically adjusted along the derivation. We further present a coverage tree illustrating the distribution of generated test cases and their detailed derivations. More importantly, the coverage tree supports various implicit derivation control mechanisms. We implemented this approach in a Java‐based system, named Gena. Each test case generated by Gena automatically comes with a set of structural features, which can play an important and effective role on automated failure causes localization. Experimental results demonstrate the effectiveness of our approach, the well‐balanced distribution of generated test cases over grammatical structures, and a case study on grammar‐based failure causes localization. Copyright © 2014 John Wiley & Sons, Ltd.     

State generation and automated class testing

The maturity of object‐oriented methods has led to the wide availability of container classes: classes that encapsulate classical data structures and algorithms. Container classes are included in the C++ and Java standard libraries, and in many proprietary libraries. The wide availability and use of these classes makes reliability important, and testing plays a central role in achieving that reliability. The large number of cases necessary for thorough testing of container classes makes automated testing essential. This paper presents a novel approach for automated testing of container classes based on combinatorial algorithms for state generation. The approach is illustrated with black‐box and white‐box test drivers for a class implemented with the red–black tree data structure, used widely in industry and, in particular, in the C++ Standard Template Library. The white‐box driver is based on a new algorithm for red–black tree generation. The drivers are evaluated experimentally, providing quantitative measures of their effectiveness in terms of block and path coverage. The results clearly show that the approach is affordable in terms of development cost and execution time, and effective with respect to coverage achieved. The results also provide insight into the relative advantages of black‐box and white‐box drivers, and into the difficult problem of infeasible paths. Copyright © 2000 John Wiley & Sons, Ltd.     

ClassBench: a Framework for Automated Class Testing

In contrast to the explosion of activity in object-oriented design and programming, little attention has been given to object testing. We present a novel approach to automated testing designed especially for collection classes. In the ClassBench methodology, a testgraph partially models the states and transitions of the Class-Under-Test (CUT) state/transition graph. To determine the expected behavior for the test cases generated from the testgraph, the tester develops an oracle class, providing essentially the same operations as the CUT but supporting only the testgraph states and transitions. Surprisingly thorough testing is achievable with simple testgraphs and oracles. The ClassBench framework supports the tester by providing a testgraph editor, automated testgraph traversal, and a variety of utility classes. Test suites can be easily configured for regression testing–where many test cases are run–and debugging–where a few test cases are selected to isolate the bug. We present the ClassBench methodology and framework in detail, illustrated on both simple examples and on test suites from commercial collection class libraries. © 1997 John Wiley & Sons, Ltd.     

Formal firewall conformance testing: an application of test and proof techniques

Firewalls are an important means to secure critical ICT infrastructures. As configurable off‐the‐shelf products, the effectiveness of a firewall crucially depends on both the correctness of the implementation itself as well as the correct configuration. While testing the implementation can be done once by the manufacturer, the configuration needs to be tested for each application individually. This is particularly challenging as the configuration, implementing a firewall policy, is inherently complex, hard to understand, administrated by different stakeholders and thus difficult to validate. This paper presents a formal model of both stateless and stateful firewalls (packet filters), including NAT , to which a specification‐based conformance test case generation approach is applied. Furthermore, a verified optimisation technique for this approach is presented: starting from a formal model for stateless firewalls, a collection of semantics‐preserving policy transformation rules and an algorithm that optimizes the specification with respect of the number of test cases required for path coverage of the model are derived. We extend an existing approach that integrates verification and testing, that is, tests and proofs to support conformance testing of network policies. The presented approach is supported by a test framework that allows to test actual firewalls using the test cases generated on the basis of the formal model. Finally, a report on several larger case studies is presented. Copyright © 2014 John Wiley & Sons, Ltd.     

Integration testing of object‐oriented components using finite state machines

In object‐oriented terms, one of the goals of integration testing is to ensure that messages from objects in one class or component are sent and received in the proper order and have the intended effect on the state of the objects that receive the messages. This research extends an existing single‐class testing technique to integration testing of multiple classes. The single‐class technique models the behaviour of a single class as a finite state machine, transforms the representation into a data flow graph that explicitly identifies the definitions and uses of each state variable of the class, and then applies conventional data flow testing to produce test case specifications that can be used to test the class. This paper extends those ideas to inter‐class testing by developing flow graphs, finding paths between pairs of definitions and uses, detecting some infeasible paths and automatically generating tests for an arbitrary number of classes and components. It introduces flexible representations for message sending and receiving among objects and allows concurrency among any or all classes and components. Data flow graphs are stored in a relational database and database queries are used to gather def‐use information. This approach is conceptually simple, mathematically precise, quite powerful and general enough to be used for traditional data flow analysis. This testing approach relies on finite state machines, database modelling and processing techniques and algorithms for analysis and traversal of directed graphs. The paper presents empirical results of the approach applied to an automotive system. This work was prepared by U.S. Government employees as part of their official duties and is, therefore, a work of the U.S. Government and not subject to copyright. Published in 2006 by John Wiley & Sons, Ltd.     

A testing strategy for abstract classes

One of the characteristics of the increasingly widespread use of object‐oriented libraries and the resulting intensive use of inheritance is the proliferation of dependencies on abstract classes. Since abstract classes cannot be instantiated, they cannot be tested in isolation using standard execution‐based testing strategies. A standard approach to testing abstract classes is to instantiate a concrete descendant class and test the features that are inherited. This paper presents a structured approach that supports the testing of features in abstract classes, paying particular attention to ensuring that the features tested are those defined in the abstract class. Two empirical studies are performed on a suite of large Java programs and the results presented. The first study analyses the role of abstract classes from a testing perspective. The second study investigates the impact of the testing strategy on the programs in this suite to demonstrate its feasibility and to comment on the pragmatics of its use. Copyright © 2010 John Wiley & Sons, Ltd.     

From Object‐Z specifications to ClassBench test suites

This paper describes a method for specification‐based class testing that incorporates test case generation, execution, and evaluation based on formal specifications. This work builds on previous achievements in the areas of specification‐based testing and class testing by integrating the two within a single framework. The initial step of the method is to generate test templates for individual operations from a specification written in the Object‐Z specification language. These test templates are combined to produce a finite state machine for the class that is used as the basis for test case execution using the ClassBench test execution framework. An oracle derived from the Object‐Z specification is used to evaluate the outputs. The method is explained using a simple example and its application to a more substantial case study is also discussed. Copyright © 2000 John Wiley & Sons, Ltd.     

JCrasher: an automatic robustness tester for Java

JCrasher is an automatic robustness testing tool for Java code. JCrasher examines the type information of a set of Java classes and constructs code fragments that will create instances of different types to test the behavior of public methods under random data. JCrasher attempts to detect bugs by causing the program under test to ‘crash’, that is, to throw an undeclared runtime exception. Although in general the random testing approach has many limitations, it also has the advantage of being completely automatic: o supervision is required except for off‐line inspection of the test ases that have caused a crash. Compared to other similar commercial and research tools, JCrasher offers several novelties: it transitively analyzes methods, determines the size of each tested method's parameter‐space and selects parameter combinations and therefore test cases at random, taking into account the time allocated for testing; it defines heuristics for determining whether a Java exception should be considered as a program bug or whether the JCrasher supplied inputs have violated the code's preconditions; it includes support for efficiently undoing all the state changes introduced by previous tests; it produces test files for JUnit, a popular Java testing tool; and it can be integrated in the Eclipse IDE. Copyright © 2004 John Wiley & Sons, Ltd.     

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.     

Establishing structural testing criteria for Java bytecode

This paper describes intra‐method control‐flow and data‐flow testing criteria for the Java bytecode language. Six testing criteria are considered for the generation of testing requirements: four control‐flow and two data‐flow based. The main reason to work at a lower level is that, even when there is no source code, structural testing requirements can still be derived and used to assess the quality of a given test set. It can be used, for instance, to perform structural testing on third‐party Java components. In addition, the bytecode can be seen as an intermediate language, so the analysis performed at this level can be mapped back to the original high‐level language that generated the bytecode. To support the application of the testing criteria, we have implemented a tool named JaBUTi (Java Bytecode Understanding and Testing). JaBUTi is used to illustrate the application of the ideas developed in this paper. Copyright © 2006 John Wiley & Sons, Ltd.     

Object‐oriented processing of Java source code

Code transformation and analysis tools provide support for software engineering tasks such as style checking, testing, calculating software metrics as well as reverse‐ and re‐engineering. In this paper we describe the architecture and the applications of JTransform, a general Java source code processing and transformation framework. It consists of a Java parser generating a configurable parse tree and various visitors (transformers, tree evaluators) which produce different kinds of outputs. While our framework is written in Java, the paper further opens an opportunity for a new generation of XML‐based source code tools. Copyright © 2004 John Wiley & Sons, Ltd.     

A Formal Logic Approach to Constrained Combinatorial Testing

Combinatorial testing is as an effective testing technique to reveal failures in a given system, based on input combinations coverage and combinatorial optimization. Combinatorial testing of strength t (t ≥ 2) requires that each t-wise tuple of values of the different system input parameters is covered by at least one test case. Combinatorial test suite generation algorithms aim at producing a test suite covering all the required tuples in a small (possibly minimal) number of test cases, in order to reduce the cost of testing. The most used combinatorial technique is the pairwise testing (t = 2) which requires coverage of all pairs of input values. Constrained combinatorial testing takes also into account constraints over the system parameters, for instance forbidden tuples of inputs, modeling invalid or not realizable input values combinations. In this paper a new approach to combinatorial testing, tightly integrated with formal logic, is presented. In this approach, test predicates are used to formalize combinatorial testing as a logical problem, and an external formal logic tool is applied to solve it. Constraints over the input domain are expressed as logical predicates too, and effectively handled by the same tool. Moreover, inclusion or exclusion of select tuples is supported, allowing the user to customize the test suite layout. The proposed approach is supported by a prototype tool implementation and results of experimental assessment are also presented.     

A threat model‐based approach to security testing

Software security issues have been a major concern in the cyberspace community, so a great deal of research on security testing has been performed, and various security testing techniques have been developed. Threat modeling provides a systematic way to identify threats that might compromise security, and it has been a well‐accepted practice by the industry, but test case generation from threat models has not been addressed yet. Thus, in this paper, we propose a threat model‐based security testing approach that automatically generates security test sequences from threat trees and transforms them into executable tests. The security testing approach we consider consists of three activities in large: building threat models with threat trees; generating security test sequences from threat trees; and creating executable test cases by considering valid and invalid inputs. To support our approach, we implemented security test generation techniques, and we also conducted an empirical study to assess the effectiveness of our approach. The results of our study show that our threat tree‐based approach is effective in exposing vulnerabilities. Copyright © 2012 John Wiley & Sons, Ltd.     

支持用例集并行测试的接口测试平台

针对手工测试成本高、时效性弱和传统的接口自动化测试工具扩展能力不足问题,提出了一个支持用例集并行测试的接口测试平台(OLa). OLa采用分层架构模式将系统分为用户展示层、应用逻辑层、数据服务层和用例执行层.其中,用户展示层基于Vue框架开发,结合Vue Router、Vuex等工具实现单页应用;应用逻辑层基于Spring Boot框架开发;数据服务层基于MyBatis-Plus框架和Spring Data框架开发;用例执行层使用okhttp3、fastjson、jackson等工具实现接口测试.此外,基于系统技术架构、Java网络编程和面向抽象编程的思想,创新性地提出了基于C/S模式的用例执行流程和基于参数识别的自动匹配校验方法,解决了传统的自动化测试工具无法支持并行测试的问题.实验结果表明本文设计与实现的OLa接口测试平台支持单用例测试、用例集的串行测试和并行测试,能够自动识别用例参数并对接口响应内容进行校验,提高了接口测试的灵活性和有效性,降低了测试难度,并能够在用例之间无相互依赖的情况下提高接口测试的效率.     

Tool support for executable documentation of Java class hierarchies

While object‐oriented programming offers great solutions for today's software developers, this success has created difficult problems in class documentation and testing. In Java, two tools provide assistance: Javadoc allows class interface documentation to be embedded as code comments and JUnit supports unit testing by providing assert constructs and a test framework. This paper describes JUnitDoc, an integration of Javadoc and JUnit, which provides better support for class documentation and testing. With JUnitDoc, test cases are embedded in Javadoc comments and used as both examples for documentation and test cases for quality assurance. JUnitDoc extracts the test cases for use in HTML files serving as class documentation and in JUnit drivers for class testing. To address the difficult problem of testing inheritance hierarchies, JUnitDoc provides a novel solution in the form of a parallel test hierarchy. A small controlled experiment compares the readability of JUnitDoc documentation to formal documentation written in Object‐Z. Copyright © 2005 John Wiley & Sons, Ltd.     

基于EDPN的类测试框架及测试用例生成技术的研究

针对基于状态的面向对象软件的类测试过程中存在的不可预测、不可达状态、状态组合“爆炸”和测试用例“爆炸”等问题,提出了基于EDPN模型的类测试、类的交互测试和类的层次测试框架,设计了相应的测试模型;提出了基于EDPN的有标记的唯一输入输出(UIO)测试用例的自动生成方法,生成状态转移路径序列,测试类的状态;提出了基于扩展的EDPN的状态组合的标记关联递推法,生成扩展的正交阵列表,测试类的交互;提出了基于扩展的EMDPN的协同路径(copaths)测试用例的生成方法,生成协同路径序列,测试类的层次。     

Specification and testing of autonomous agents in e‐commerce systems

This paper presents a generic formal framework to specify and test autonomous e‐commerce agents. First, the formalism to represent the behaviour of agents is introduced. The corresponding machinery to define how implementations can be tested follows. Two testing approaches are considered. The first of them, which can be called active, is based on stimulating the implementation under test (IUT) with a test. The peculiarity is that tests will be defined as a special case of autonomous e‐commerce agent. The second approach, which can be called passive, consists of observing the behaviour of the tested agent in an environment containing other agents. As a case study the framework is applied to the e‐commerce system Kasbah. Copyright © 2005 John Wiley & Sons, Ltd.     

Grammar‐based test generation with YouGen

Grammars are traditionally used to recognize or parse sentences in a language, but they can also be used to generate sentences. In grammar‐based test generation (GBTG), context‐free grammars are used to generate sentences that are interpreted as test cases. A generator reads a grammar G and generates L(G), the language accepted by the grammar. Often L(G) is so large that it is not practical to execute all of the generated cases. Therefore, GBTG tools support ‘tags’: extra‐grammatical annotations which restrict the generation. Since its introduction in the early 1970s, GBTG has become well established: proven on industrial projects and widely published in academic venues. Despite the demonstrated effectiveness, the tool support is uneven; some tools target specific domains, e.g. compiler testing, while others are proprietary. The tools can be difficult to use and the precise meaning of the tags are sometimes unclear. As a result, while many testing practitioners and researchers are aware of GBTG, few have detailed knowledge or experience. We present YouGen, a new GBTG tool supporting many of the tags provided by previous tools. In addition, YouGen incorporates covering‐array tags, which support a generalized form of pairwise testing. These tags add considerable power to GBTG tools and have been available only in limited form in previous GBTG tools. We provide semantics for the YouGen tags using parse trees and a new construct, generation trees. We illustrate YouGen with both simple examples and a number of industrial case studies. Copyright © 2010 John Wiley & Sons, Ltd.     

UCov: a user‐defined coverage criterion for test case intent verification

The goal of regression testing is to ensure that the behaviour of existing code, believed correct by previous testing, is not altered by new program changes. This paper argues that the primary focus of regression testing should be on code associated with (1) earlier bug fixes and (2) particular application scenarios considered to be important by the developer or tester. Existing coverage criteria do not enable such focus, for example, 100% branch coverage does not guarantee that a given bug fix is exercised or a given application scenario is tested. Therefore, there is a need for a new and complementary coverage criterion in which the user can definea test requirement characterizing a given behaviour to be covered as opposed to choosing from a pool of pre‐defined and generic program elements. This paper proposes this new methodology and calls it UCov, a user‐defined coverage criterion wherein a test requirement is an execution pattern of program elements, and possibly predicates, that a test case must satisfy. The proposed criterion is not meant to replace existing criteria, but to complement them as it focuses the testing on important code patterns that could go untested otherwise. UCov supports test case intent verification. For example, following a bug fix, the testing team may augment the regression suite with the test case that revealed the bug. However, this test case might become obsolete due to code modifications not related to the bug. But if a test requirement characterizing the bug was defined by the user, UCov would determine that test case intent verification failed. The UCov methodology was implemented for the Java platform, was successfully applied onto 10 real‐life case studies and was shown to have advantages over JUnit. The implementation comprises the following tools: (1) TRSpec: allows the user to easily specify complex test requirements; (2) TRCheck: checks whether user‐defined test requirements were satisfied, that is, supports test case intent verification; and (3) TRMigrate: migrates user‐defined test requirements to subsequent versions of a given program. Copyright © 2016 John Wiley & Sons, Ltd.