Summary Comprehensive, automated software testing requires an oracle to check whether the output produced by a test case matches the expected behaviour of the programme. But the challenges in creating suitable oracles limit the ability to perform automated testing in some programmes, and especially in scientific software. Metamorphic testing is a method for automating the testing process for programmes without test oracles. This technique operates by checking whether the programme behaves according to properties called metamorphic relations. A metamorphic relation describes the change in output when the input is changed in a prescribed way. Unfortunately, finding the metamorphic relations satisfied by a programme or function remains a labour‐intensive task, which is generally performed by a domain expert or a programmer. In this work, we propose a machine learning approach for predicting metamorphic relations that uses a graph‐based representation of a programme to represent control flow and data dependency information. In earlier work, we found that simple features derived from such graphs provide good performance. An analysis of the features used in this earlier work led us to explore the effectiveness of several representations of those graphs using the machine learning framework of graph kernels, which provide various ways of measuring similarity between graphs. Our results show that a graph kernel that evaluates the contribution of all paths in the graph has the best accuracy and that control flow information is more useful than data dependency information. The data used in this study are available for download at http://www.cs.colostate.edu/saxs/MRpred/functions.tar.gz to help researchers in further development of metamorphic relation prediction methods. Copyright © 2015 John Wiley & Sons, Ltd.

Automated program repair (APR) techniques fix faults by repeatedly modifying suspicious code until a program passes a set of test cases. Although generating a repair is the goal of APR, a repair can have negative consequences. The quality of a repair is reduced when the repair introduces new faults and/or degrades maintainability by adding irrelevant but functionally benign code. We used two APR approaches to repair faulty binary operators: (1) find a repair in existing code by applying a genetic algorithm to replace suspicious code with other existing code as done by GenProg, and (2) mutate suspicious operators within a genetic algorithm. Mutating operators was clearly more effective in repairing faulty operators than using existing code for a repair. We also evaluated the approaches in terms of two potential negative effects: (1) the introduction of new faults and (2) a reduction of program maintainability. We found that repair processes that use tests that satisfy branch coverage reduce the number of new faults. In contrast, repair processes using tests that satisfy statement coverage and randomly generated tests introduce numerous new faults. We also demonstrate that a mutation based repair process produces repairs that should be more maintainable compared to those produced using existing code.

ABSTRACT Scientific programmers can improve the performance of function evaluation by precomputing and storing results in a lookup table (LUT), thereby replacing costly evaluation code with an inexpensive memory access. A code transformation that replaces computation with LUT code can improve performance; however, accuracy is reduced because of error inherent in reconstructing values from LUT data. LUTs are commonly used to approximate expensive elementary functions. The current practice is for software developers to: (i) manually identify expressions that can benefit from an LUT; (ii) modify the code by hand to implement the LUT transformation; and (iii) run experiments to determine if the resulting error is within application requirements. This approach reduces productivity, obfuscates code, and limits programmer control over accuracy and performance. We propose source code analysis and program transformation to substantially automate LUT transformations. Our approach uses a novel optimization algorithm that selects Pareto optimal sets of expressions that benefit most from an LUT, on the basis of the error and performance estimates. We demonstrate our methodology with the Mesa tool, which achieves speedups of 1.4–6.8× on scientific codes with an acceptable loss of accuracy. Our tool makes the programmer more productive and facilitates finding effective LUT transformations. Copyright © 2013 John Wiley & Sons, Ltd.

Much software lacks test oracles, which limits automated testing. Metamorphic testing is one proposed method for automating the testing process for programs without test oracles. Unfortunately, finding the appropriate metamorphic relations required for use in metamorphic testing remains a labor intensive task, which is generally performed by a domain expert or a programmer. In this work we present a novel approach for automatically predicting metamorphic relations using machine learning techniques. Our approach uses a set of features developed using the control flow graph of a function for predicting likely metamorphic relations. We show the effectiveness of our method using a set of real world functions often used in scientific applications.

The Repository for Model-Driven Development (ReMoDD) contains artifacts that support Model-Driven Development (MDD) research and education. ReMoDD is collecting (1) documented MDD case studies, (2) examples of models reflecting good and bad modeling practices, (3) reference models (including metamodels) that can be used as the basis for comparing and evaluating MDD techniques, (4) generic models and transformations reflecting reusable modeling experience, (5) descriptions of modeling techniques, practices and experiences, and (6) modeling exercises and problems that can be used to develop classroom assignments and projects. ReMoDD provides a single point of access to shared artifacts reflecting high-quality MDD experience and knowledge from industry and academia. This access facilitates sharing of relevant knowledge and experience that improve MDD activities in research, education and industry.

Scientific programmers can speed up function evaluation by precomputing and storing function results in lookup table (LUTs), thereby replacing costly evaluation code with an inexpensive memory access. A code transform that replaces computation with LUT code can improve performance, however, accuracy is reduced because of error inherent in reconstructing values from LUT data. LUT transforms are commonly used to approximate expensive elementary functions. The current practice is for software developers to (1) manually identify expressions that can benefit from a LUT transform, (2) modify the code by hand to implement the LUT transform, and (3) run experiments to determine if the resulting error is within application requirements. This approach reduces productivity, obfuscates code, and limits programmer control over accuracy and performance. We propose source code analysis and program transformation to substantially automate the application of LUT transforms. Our approach uses a novel optimization algorithm that selects Pareto optimal sets of expressions that benefit most from LUT transformation, based on error and performance estimates. We demonstrate our methodology with the Mesa tool, which achieves speedups of 1.4-6.9× on scientific codes while managing introduced error. Our tool makes the programmer more productive and improves the chances of finding an effective solution.

The primary claimed benefits of aspect-oriented programming (AOP) are that it improves the understandability and maintainability of software applications by modularizing crosscutting concerns. Before there is widespread adoption of AOP, developers need further evidence of the actual benefits as well as costs. Applying AOP techniques to refactor legacy applications is one way to evaluate costs and benefits. We replace crosscutting concerns with aspects in three industrial applications to examine the effects on qualities that affect the maintainability of the applications. We study several revisions of each application, identifying crosscutting concerns in the initial revision and also crosscutting concerns that are added in later revisions. Aspect-oriented refactoring reduced code size and improved both change locality and concern diffusion. Costs include the effort required for application refactoring and aspect creation, as well as a decrease in performance.

Many automated static analysis (ASA) tools have been developed in recent years for detecting software anomalies. The aim of these tools is to help developers to eliminate software defects at early stages and produce more reliable software at a lower cost. Determining the effectiveness of ASA tools requires empirical evaluation. This study evaluates coding concerns reported by three ASA tools on two open source software (OSS) projects with respect to two types of modifications performed in the studied software CVS repositories: corrections of faults that caused failures, and refactoring modifications. The results show that fewer than 3% of the detected faults correspond to the coding concerns reported by the ASA tools. ASA tools were more effective in identifying refactoring modifications and corresponded to about 71% of them. More than 96% of the coding concerns were false positives that do not relate to any fault or refactoring modification.

Abstract 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.

Evidence suggests that as software ages the original realizations of design patterns remain in place, and participants in design pattern realizations accumulate "grime" - non-pattern-related code. This research examines the consequences that grime buildup has on the testability of general purpose design patterns. Test cases put in place during the design phase and initial implementation of a project can become ineffective as the system matures. The evolution of a design due to added functionality or defect fixing increases the coupling and dependencies between many classes that must be tested. We show that as systems age, the growth of grime and the appearance of anti-patterns increase testing requirements. Early recognition and removal of grime and anti-patterns can potentially improve system testability.

A common belief is that software designs decay as systems evolve. This research examines the extent to which software designs actually decay by studying the aging of design patterns in successful object oriented systems. Aging of design patterns is measured using various types of decay indices developed for this research. Decay indices track the internal structural changes of a design pattern realization and the code that surrounds the realization. Hypotheses for each kind of decay are tested. We found that the original design pattern functionality remains, and pattern decay is due to the "grime ", non-pattern code, that grows around the pattern realization.

Moving program code that implements cross-cutting concerns into aspects can improve the maintainability of legacy systems. This kind of refactoring, called aspectualization, can also introduce faults into a system. A test driven approach can identify these faults during the refactoring process so that they can be removed. We perform systematic testing as we aspectualize commercial VLSI CAD applications. The process of refactoring these applications revealed the kinds of faults that can arise during aspectualization, and helped us to develop techniques to reduce their occurrences

Security critical systems must perform at the required security level, make effective use of available resources, and meet end-users expectations. Balancing these needs, and at the same time fulfilling budget and time-to-market constraints, requires developers to design and evaluate alternative security treatment strategies. In this paper, the authors presented a development framework that utilizes Bayesian belief networks (BBN) and aspect-oriented modeling (AOM) for a cost-benefit trade-off analysis of treatment strategies. AOM allows developers to model pervasive security treatments separately from other system functionality. This eases the trade-off by making it possible to swap treatment strategies in and out when computing return on security investments (RoSI). The trade-off analysis is implemented using BBN, and RoSI is computed by estimating a set of variables describing properties of a treatment strategy. RoSI for each treatment strategy is then used as input to choice of design.

Case studies can help to validate claims that open source software development produces higher quality software at lower cost than traditional commercial development. One problem inherent in case studies are external validity - we do not know whether or not results from one case study apply to another development project. We gain or lose confidence in case study results when similar case studies are conducted on other projects. This case study of the FreeBSD project, a long-lived open source project, provides further understanding of open source development. The paper details a method for mining repositories and querying project participants to retrieve key process information. The FreeBSD development process is fairly well-defined with proscribed methods for determining developer responsibilities, dealing with enhancements and defects, and managing releases. Compared to the Apache project, FreeBSD uses 1) a smaller set of core developers - developers who control the code base - that implement a smaller percentage of the system, 2) a larger set of top developers to implement 80 percent of the system, and 3) a more well-defined testing process. FreeBSD and Apache have a similar ratio of core developers to people involved in adapting and debugging the system and people who report problems. Both systems have similar defect densities and the developers are also users in both systems.

Although program faults are widely studied, there are many aspects of faults that we still do not understand, particularly about OO software. In addition to the simple fact that one important goal during testing is to cause failures and thereby detect faults, a full understanding of the characteristics of faults is crucial to several research areas. The power that inheritance and polymorphism brings to the expressiveness of programming languages also brings a number of new anomalies and fault types. In prior work we presented a fault model for the appearance and realization of OO faults that are specific to the use of inheritance and polymorphism. Many of these faults cannot appear unless certain syntactic patterns are used. The patterns are based on language constructs, such as overriding methods that directly define inherited state variables and non-inherited methods that call inherited methods. If one of these syntactic patterns is used, then we say the software contains an anomaly and possibly a fault. We describe the syntactic patterns for each OO fault type. These syntactic patterns can potentially be found with an automatic tool. Thus, faults can be uncovered and removed early in development.

Fault insertion based techniques have been used for measuring test adequacy and testability of programs. Mutation analysis inserts faults into a program with the goal of creating mutation-adequate test sets that distinguish the mutant from the original program. Software testability is measured by calculating the probability that a program will fail on the next test input coming from a predefined input distribution, given that the software includes a fault. Inserted faults must represent plausible errors. It is relatively easy to apply standard transformations to mutate scalar values such as integers, floats, and character data, because their semantics are well understood. Mutating objects that are instances of user defined types is more difficult. There is no obvious way to modify such objects in a manner consistent with realistic faults, without writing custom mutation methods for each object class. We propose a new object mutation approach along with a set of mutation operators and support tools for inserting faults into objects that instantiate items from common Java libraries heavily used in commercial software as well as user defined classes. Preliminary evaluation of our technique shows that it should be effective for evaluating real-world software testing suites.

Object-oriented programs cause a shift in focus from software units to the way software classes and components are connected. Thus, we are finding that we need less emphasis on unit testing and more on integration testing. The compositional relationships of inheritance and aggregation, especially when combined with polymorphism, introduce new kinds of integration faults, which can be covered using testing criteria that take the effects of inheritance and polymorphism into account. This paper demonstrates, via a set of experiments, the relative effectiveness of several coupling-based OO testing criteria and branch coverage. OO criteria are all more effective at detecting faults due to the use of inheritance and polymorphism than branch coverage.

"Software test-coverage measures" quantify the degree of thoroughness of testing. Tools are now available that measure test-coverage in terms of blocks, branches, computation-uses, predicate-uses, etc. that are covered. This paper models the relations among testing time, coverage, and reliability. An LE (logarithmic-exponential) model is presented that relates testing effort to test coverage (block, branch, computation-use, or predicate-use). The model is based on the hypothesis that the enumerable elements (like branches or blocks) for any coverage measure have various probabilities of being exercised; just like defects have various probabilities of being encountered. This model allows relating a test-coverage measure directly with defect-coverage. The model is fitted to 4 data-sets for programs with real defects. In the model, defect coverage can predict the time to next failure. The LE model can eliminate variables like test-application strategy from consideration. It is suitable for high reliability applications where automatic (or manual) test generation is used to cover enumerables which have not yet been tested. The data-sets used suggest the potential of the proposed model. The model is simple and easily explained, and thus can be suitable for industrial use. The LE model is based on the time-based logarithmic software-reliability growth model. It considers that: at 100% coverage for a given enumerable, all defects might not yet have been found.

Object-oriented (OO) design patterns define collections of interconnected classes that serve a particular purpose. A design pattern is a structural unit in a system built out of patterns, not unlike the way a function is a structural unit in a procedural program or a class is a structural unit in an OO system designed without patterns. When designers treat patterns as structural units, they become concerned with issues such as coupling and cohesion at a new level of abstraction. We examine the notion of pattern coupling to classify how designs may include coupled patterns. We find many examples of coupled patterns; this coupling may be "tight" or "loose", and provides both benefits and costs. We qualitatively assess the goodness of pattern coupling in terms of effects on maintainability, factorability, and reusability when patterns are coupled in various ways.

A primary expected benefit of object-oriented (OO) methods is the creation of software systems that are easier to adapt and maintain. OO design patterns are especially geared to improve adaptability, since patterns generally increase the complexity of an initial design in order to ease future enhancements. For design patterns to really provide benefit, they must reduce the cost of future adaptation. The evidence of improvements in adaptability through the use of design patterns and other design structures consists primarily of intuitive arguments and examples. There is little empirical evidence to support claims of improved flexibility of these preferred structures. In this case study, we analyze 39 versions of an evolving industrial OO software system to see if there is a relationship between patterns, other design attributes, and the number of changes. We found a strong relationship between class size and the number of changes-larger classes were changed more frequently. We also found two relationships that we did not expect: (1) classes that participate in design patterns are not less change prone-these pattern classes are among the most change prone in the system, and (2) classes that are reused the most through inheritance tend to be more change prone. These unexpected results hold up after accounting for class size, which had the strongest relationship with changes.

It is well-known that uncontrolled change to software can lead to increasing evolution costs caused by deteriorating structure and compromised system qualities. For complex systems, the need to carefully manage system evolution is critical. In this paper we outline an approach to managing evolution of object-oriented (OO) software. The approach is based on a goal-directed, cyclic process, in which OO models are transformed and quantitatively evaluated in each cycle. Evaluation criteria guide developers in choosing between alternative transformations in each cycle. The process, transformations, and evaluation techniques can be used to develop systems from a set of baseline models.

Summary form only given. The authors are currently developing a model-driven, repository-based approach to system evolution management. The primary domain of interest is the telecommunication IT system area, but the techniques are applicable to organizations with integrated systems of systems. The approach is model-driven in the sense that data and object-oriented (OO) models (expressed in the Unified Modeling Language (UML)) are used to represent system implementations at various levels of abstractions (business requirements, system requirements, logical and physical design).

Mutation analysis inserts faults into a program to create test sets that distinguish the mutant from the original program. Inserted faults must represent plausible errors. Standard transformations can mutate scalar values such as integers, floats, and character data. Mutating objects is an open problem, because object semantics are defined by the programmer and can vary widely. We develop mutation operators and support tools that can mutate Java library items that are heavily used in commercial software. Our mutation engine can support reusable libraries of mutation components to inject faults into objects that instantiate items from these common Java libraries. Our technique should be effective for evaluating real-world software testing suites.

The use of commercial-off-the-shelf (COTS) products creates a software integration problem, whether a single COTS software component is being integrated into a software system, or the whole system is being built primarily from COTS products. This integration may require considerable effort and affect system quality. A good estimate of integration cost can help in the decision of whether or not to use a COTS solution, the selection of the best COTS products, and determine the amount and type of glueware that needs to be built. In this paper, we introduce a set of variables that have the potential to estimate the integration cost. We present a classification scheme of software architectures with respect to the integration of COTS products. The scheme is based on inter-component interactions within software architectures. The classification scheme allows the comparison of integration costs of different COTS products relative to different software architectures.

Many existing software systems can benefit from restructuring to reduce maintenance cost and improve reusability. Yet, intuition-based, ad hoc restructuring can be difficult and expensive, and can even make software structure worse. We introduce a quantitative framework for software restructuring. In the framework, restructuring decisions are guided by visualized design information and objective criteria. The design information can be extracted directly from code to restructure existing or legacy software. Criteria for comparing alternative design structures include measures of design-level cohesion and coupling. Restructuring is accomplished through a series of decomposition and composition operations which increase the cohesion and/or decrease the coupling of individual system components. An example and a case study demonstrate the framework. The framework ensures that restructuring results in measurable improvements in design quality. Copyright © 1999 John Wiley & Sons, Ltd.

Cohesion was first introduced as a software attribute that, when measured, could be used to predict properties of implementations that would be created from a given design. Unfortunately, cohesion, as originally defined, could not be objectively assessed, while more recently developed objective cohesion measures depend on code-level information. We show that association-based and slice-based approaches can be used to measure cohesion using only design-level information. An analytical and empirical analysis shows that the design-level measures correspond closely with code-level cohesion measures. They can be used as predictors of or surrogates for the code-level measures. The design-level cohesion measures are formally defined, have been implemented, and can support software design, maintenance and restructuring.

Cohesion was first developed to predict properties of implementations created from a given design. Unfortunately, cohesion, as originally defined, could not be objectively assessed, while more recently developed objective cohesion measures depend on code level information. We show that association based and slice based approaches can be used to measure cohesion using only design level information. Our design level cohesion measures are formally defined, can be readily implemented, and can support software design, maintenance, and restructuring.

During testing, it is nearly impossible to run all statements or branches of a program. It is especially difficult to test the code used to respond to exceptional conditions. This untested code, often the error recovery code, will tend to be an error prone part of a system. We show that test coverage can be increased through an "assertion violation" technique for injecting software faults during execution. Using our prototype tool, Visual C-Patrol (VCP), we were able to substantially increase test branch coverage in four software systems studied.

Abstract One class of program defects results from illegal sequences of otherwise legal operations in software implementations. Explicit statement of sequencing constraints, however, is not a common activity when specifying software even when using formal specification methods. This paper shows that constraints on program execution sequences can be derived directly from algebraic specifications. Results include heuristic methods for generating sequencing constraints and a generalization of these methods into automatable rules. The heuristics can be integrated into a specification methodology such as Larch. Engineers can use the generated sequencing constraints to detect sequencing defects in software even before dynamic testing begins. The method can be used to increase the reliability of software that is specified using algebraic methods.

Models the relationship between testing effort, coverage and reliability, and presents a logarithmic model that relates testing effort to test coverage: statement (or block) coverage, branch (or decision) coverage, computation use (c-use) coverage, or predicate use (p-use) coverage. The model is based on the hypothesis that the enumerables (like branches or blocks) for any coverage measure have different detectability, just like the individual defects. This model allows us to relate a test coverage measure directly to the defect coverage. Data sets for programs with real defects are used to validate the model. The results are consistent with the known inclusion relationships among block, branch and p-use coverage measures. We show how the defect density controls the time-to-next-failure. The model can eliminate variables like the test application strategy from consideration. It is suitable for high-reliability applications where automatic (or manual) test generation is used to cover enemerables which have not yet been tested.>

Executable assertions can be inserted into a program to find software faults. Unfortunately, the process of designing and embedding these assertions can be expensive and time consuming. We have developed the C-Patrol tool to reduce the overhead of using assertions in C programs. C-Patrol allows a developer to reference a set of previously defined assertions, written in virtual C, bind assertion parameters, and direct the placement of the assertions by a pre-processor.

We examine the functional cohesion of procedures using a data slice abstraction. Our analysis identifies the data tokens that lie on more than one slice as the "glue" that binds separate components together. Cohesion is measured in terms of the relative number of glue tokens, tokens that lie on more than one data slice, and super-glue tokens, tokens that lie on all data slices in a procedure, and the adhesiveness of the tokens. The intuition and measurement scale factors are demonstrated through a set of abstract transformations.>

One class of program defect results from illegal sequences of otherwise legal operations in software implementations. Expressions that specify the correct sequences can be written in the Cecil sequencing constraint language. Programs can then be checked at compile time by the Cesar analysis system. Explicit statement of sequencing constraints, however, is not a common activity when specifying software even when using formal specification methods. In this paper, we describe methods to derive constraints on program execution sequences from algebraic specifications. We provide heuristic methods for generating these constraints from the specifications and generalize the methods into automatable rules. Using these generated constraints, we can then detect sequencing defects in software before dynamic testing begins.

Program slices are used to model module cohesion. For the authors purposes, a slice is a projection of program text that includes only the data tokens relevant to one output. The authors define six cohesion metrics in terms of these slices, and evaluate the effects of classes of module changes on these metrics. They find that the effects on cohesion metrics are notably more predictable when the changes result from adding code rather than from moving code.>

Software testing often requires massive numbers of test cases that must be manually inspected for correctness. This paper demonstrates the use of software “test oracles” to automate the process of checking the correctness of program output. The Prosper system, implemented by the authors, can be used to define test oracles and monitor the runtime behavior of software. An effective method to design software for testability must include the concurrent development of test oracles.

The authors define a software process model (SPM). The SPM is a model of evolution of the full set of documents produced in a software project. It is a general model for software development using any development approach, providing a framework for measuring, analyzing, and understanding the software development process. The authors use the model to characterize formally research in software measures and metrics. Data obtained from two software projects are presented in the SPM format.>