Structural coverage criteria for LUSTRE/SCADE programs

LUSTRE is a data‐flow synchronous language, on which is based the SCADE tool‐suite, widely used for specifying and programming critical reactive applications in the areas of avionics, energy or transport. Therefore, testing LUSTRE programs, that is, generating test data and assessing the achieved test coverage, is a major issue. Usual control‐flow‐based test coverage criteria (statement coverage, branch coverage, etc.) are not relevant for LUSTRE programs. In this paper, a new hierarchy of adequacy criteria tailored to the LUSTRE language is presented. These criteria are defined on operator networks, which are usual models for LUSTRE programs. The criteria satisfaction measure is automated in LUSTRUCTU , a non‐intrusive tool (no instrumentation of the code), based on the symbolic computation of path activation conditions. The applicability and the relevance of the criteria are assessed on a case study. Copyright © 2008 John Wiley & Sons, Ltd.     

Practical testing of a C99 compiler using output comparison

A simple technique is presented for testing a C99 compiler, by comparing its output with the output from pre‐existing tools. The advantage to this approach is that new test cases can be added in bulk from existing sources, reducing the need for in‐depth investigation of correctness issues and for creating new test code by hand. This technique was used in testing the PalmSource Palm OS® Cobalt ARM C/C++ cross‐compiler for Palm‐Powered® personal digital assistants, primarily for standards compliance and the correct execution of generated code. The technique described here found several hundred bugs, mostly in our in‐house code, but also in longstanding high‐quality front‐ and back‐end code from Edison Design Group and Apogee Software. It also found 18 bugs in the GNU C compiler, as well as a bug specific to the Apple version of GCC, a bug specific to the Suse version of GCC, and a dozen bugs in versions of GCC for the ARM processor, several of which were critical. Copyright © 2007 John Wiley & Sons, Ltd.     

Milepost GCC: Machine Learning Enabled Self-tuning Compiler

Tuning compiler optimizations for rapidly evolving hardware makes porting and extending an optimizing compiler for each new platform extremely challenging. Iterative optimization is a popular approach to adapting programs to a new architecture automatically using feedback-directed compilation. However, the large number of evaluations required for each program has prevented iterative compilation from widespread take-up in production compilers. Machine learning has been proposed to tune optimizations across programs systematically but is currently limited to a few transformations, long training phases and critically lacks publicly released, stable tools. Our approach is to develop a modular, extensible, self-tuning optimization infrastructure to automatically learn the best optimizations across multiple programs and architectures based on the correlation between program features, run-time behavior and optimizations. In this paper we describe Milepost GCC, the first publicly-available open-source machine learning-based compiler. It consists of an Interactive Compilation Interface (ICI) and plugins to extract program features and exchange optimization data with the cTuning.org open public repository. It automatically adapts the internal optimization heuristic at function-level granularity to improve execution time, code size and compilation time of a new program on a given architecture. Part of the MILEPOST technology together with low-level ICI-inspired plugin framework is now included in the mainline GCC. We developed machine learning plugins based on probabilistic and transductive approaches to predict good combinations of optimizations. Our preliminary experimental results show that it is possible to automatically reduce the execution time of individual MiBench programs, some by more than a factor of 2, while also improving compilation time and code size. On average we are able to reduce the execution time of the MiBench benchmark suite by 11% for the ARC reconfigurable processor. We also present a realistic multi-objective optimization scenario for Berkeley DB library using Milepost GCC and improve execution time by approximately 17%, while reducing compilation time and code size by 12% and 7% respectively on Intel Xeon processor.     

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.     

基于pCTL的循环优化测试用例自动生成方法

循环优化测试对保证现代编译器质量有着重要作用.传统手工构造测试用例方法面临着效率低的问题,而目前的自动构造方法对循环优化的针对性不足.提出并实现了一种基于参数化分支时序逻辑(pCTL)的循环优化测试用例自动生成方法.并用生成的测试用例对GCC-4.1.1进行覆盖率测试,结果表明该方法可以生成具有很高针对性的循环优化测试用例,并且很少的测试用例即可达到较高的覆盖程度.     

Can fault‐exposure‐potential estimates improve the fault detection abilities of test suites?

Code‐coverage‐based test data adequacy criteria typically treat all coverable code elements (such as statements, basic blocks or outcomes of decisions) as equal. In practice, however, the probability that a test case can expose a fault in a code element varies: some faults are more easily revealed than others. Thus, several researchers have suggested that if one could estimate the probability that a fault in a code element will cause a failure, one could use this estimate to determine the number of executions of a code element that are required to achieve a certain level of confidence in that element's correctness. This estimate, in turn, could be used to improve the fault‐detection effectiveness of test suites and help testers distribute testing resources more effectively. This conjecture is intriguing; however, like many such conjectures it has never been directly examined empirically. If empirical evidence were to support this conjecture, it would motivate further research into methodologies for obtaining fault‐exposure‐potential estimates and incorporating them into test data adequacy criteria. This paper reports the results of experiments conducted to investigate the effects of incorporating an estimate of fault‐exposure probability into the statement coverage test data adequacy criterion. The results of these experiments, however, ran contrary to the conjectures of previous researchers. Although incorporation of the estimates did produce statistically significant increases in the fault‐detection effectiveness of test suites, these increases were quite small, suggesting that the approach might not be able to produce the gains hoped for and might not be worth the cost of its employment. Copyright © 2002 John Wiley & Sons, Ltd.     

基于GCC的VLIW编译系统研究

VLIW机器在单个机器周期中同时发射并执行多个的并行操作,从而获得较高的指令级并行度,这些操作之间的依赖分析和调度工作则被完全交给相应的编译器执行,因此VLIW的并行性能能否充分发挥取决于VLIW体系结构相关编译器的质量。GNU开发的GCC是被最广泛使用的编译系统之一,它具有多语言、多平台支持的能力和开放的结构,能够运用各种成熟的常规编译优化技术生成高效的代码。文章分析了VLIW及GCC的结构特点,提出了一种基于GCC的VLIW编译系统设计方案,利用GCC进行RTL中间代码一级的体系结构无关优化和少量体系结构相关优化,在汇编代码一级针对VLIW结构进行体系结构相关的优化,从而充分利用GCC的成熟编译技术快速开发高效的VLIW多语言编译系统。     

On the use of a similarity function for test case selection in the context of model‐based testing

Test case selection in model‐based testing is discussed focusing on the use of a similarity function. Automatically generated test suites usually have redundant test cases. The reason is that test generation algorithms are usually based on structural coverage criteria that are applied exhaustively. These criteria may not be helpful to detect redundant test cases as well as the suites are usually impractical due to the huge number of test cases that can be generated. Both problems are addressed by applying a similarity function. The idea is to keep in the suite the less similar test cases according to a goal that is defined in terms of the intended size of the test suite. The strategy presented is compared with random selection by considering transition‐based and fault‐based coverage. The results show that, in most of the cases, similarity‐based selection can be more effective than random selection when applied to automatically generated test suites. Copyright © 2009 John Wiley & Sons, Ltd.     

Coverage-driven Automated Compiler Test Suite Generation

The paper presents a novel approach to automated compiler test suite generation based on the source level specification. Several coverage criteria are introduced. The application of the proposed methodology to testing the realistic programming language is discussed.     

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.     

Measuring a Java Test Suite Coverage Using JML Specifications

We propose in this paper a way to measure the coverage of a Java test suite by considering the JML specification associed to the Java program under test. This approach is based on extracting a predicate-based graph from the JML method specifications. We then measure the coverage of this latter w.r.t. nodes of the graph that are visited by the test suite. In addition, we propose to check whether the test suite satisfies classical condition coverage criteria. We also introduce a tool, to be used as precompiler for Java, that is in charge of measuring and reporting the coverage according to these criteria.     

Automatic test case generation from Simulink/Stateflow models using model checking

Model‐based test generation techniques based on random input generation and guided simulation do not satisfy the demands of high test coverage and completeness guarantees as required by safety‐critical applications. Recently, test generation techniques based on model checking have been reported to bridge this gap. To evaluate the effectiveness of these techniques, an in‐house tool suite, AutoMOTGen, has been developed for Simulink/Stateflow and applied on real‐life case studies at General Motors. This paper outlines the test generation methodology of AutoMOTGen and gives a comparative study with a commercial, primarily random input‐based, test generation tool on the same set of examples. The results indicate that in terms of coverage, model checking‐based techniques complement the random input‐based techniques. In addition, they provide proofs for unreachability that can aid in debugging the models. Therefore, it is recommended that model checking‐based tools be utilized to complement and enhance the effectiveness of model‐based testing methods in safety‐critical systems engineering. Copyright © 2013 John Wiley & Sons, Ltd.     

Improving Fault Detection Capability by Selectively Retaining Test Cases during Test Suite Reduction

Software testing is a critical part of software development. As new test cases are generated over time due to software modifications, test suite sizes may grow significantly. Because of time and resource constraints for testing, test suite minimization techniques are needed to remove those test cases from a suite that, due to code modifications over time, have become redundant with respect to the coverage of testing requirements for which they were generated. Prior work has shown that test suite minimization with respect to a given testing criterion can significantly diminish the fault detection effectiveness (FDE) of suites. We present a new approach for test suite reduction that attempts to use additional coverage information of test cases to selectively keep some additional test cases in the reduced suites that are redundant with respect to the testing criteria used for suite minimization, with the goal of improving the FDE retention of the reduced suites. We implemented our approach by modifying an existing heuristic for test suite minimization. Our experiments show that our approach can significantly improve the FDE of reduced test suites without severely affecting the extent of suite size reduction     

代码覆盖测试技术在MODE-S应答机中的应用

代码覆盖测试技术可用于结构覆盖测试和程序复杂度分析,代码覆盖测试技术可用于测试用例设计,提高软件测试效率,指导编写高质量的程序代码,代码覆盖是软件测试的底线.代码覆盖测试技术及方法的研究,为软件覆盖测试提供了理论依据.在Mode-S应答机项目中应用TRACE覆盖测试技术,确保了产品满足适航软件标准RTCA/DO-178B LEVEL B的要求.     

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.     

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.

Structural testing criteria for message‐passing parallel programs

Parallel programs present some features such as concurrency, communication and synchronization that make the test a challenging activity. Because of these characteristics, the direct application of traditional testing is not always possible and adequate testing criteria and tools are necessary. In this paper we investigate the challenges of validating message‐passing parallel programs and present a set of specific testing criteria. We introduce a family of structural testing criteria based on a test model. The model captures control and data flow of the message‐passing programs, by considering their sequential and parallel aspects. The criteria provide a coverage measure that can be used for evaluating the progress of the testing activity and also provide guidelines for the generation of test data. We also describe a tool, called ValiPar, which supports the application of the proposed testing criteria. Currently, ValiPar is configured for parallel virtual machine (PVM) and message‐passing interface (MPI). Results of the application of the proposed criteria to MPI programs are also presented and analyzed. Copyright © 2008 John Wiley & Sons, Ltd.     

All‐uses testing of shared memory parallel programs

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

基于DD-路径的代码覆盖技术及应用

讨论了结构覆盖测试技术和程序复杂度,研究了基于决策到决策路径(DD-路径)的代码覆盖技术.DD-路径技术一方面可应用于测试用例设计以实现代码覆盖,同时,在嵌入式系统的应用中能显著提高代码的编写质量,最后,在Mode-S应答机项目中,应用了基于DD-路径的覆盖技术,显著地提高了测试效率.