SUMMARY Because of the computationally expensive cost of mutation testing, automated system support is indispensable for conducting mutation testing. Mutation systems can be classified into interpretive and noninterpretive, but recent systems are noninterpretive. Weak mutation is a well‐known cost reduction method of mutation testing, but it is not directly applicable to noninterpretive mutation systems. To address the problem and take advantage of the efficiency of weak mutation, this paper presents a combined weak and strong mutation for noninterpretive Java mutation systems. The new term ‘serialmutant’ is defined as a specialized program to conduct weak mutation against all mutants in an execution and report only weakly killed mutants as strong mutation candidates. Then strong mutation is conducted only for those reported mutants. The paper also describes an implementation based on a previous Java mutation tool, MuJava. Method‐level mutation operators for Java are also redesigned. Experimental results show that the proposed approach efficiently improves the mutation cost in a noninterpretive mutation system. Copyright © 2012 John Wiley & Sons, Ltd.

Abstract Refactoring is a widely accepted technique to improve the software quality by restructuring its design without changing its behavior. In general, a sequence of refactorings needs to be applied until the quality of the code is improved satisfactorily. In this case, the final design after refactoring can vary with the application order of refactorings, thereby producing different quality improvements. Therefore, it is necessary to determine a proper refactoring schedule to obtain as many benefits as possible. However, there is little research on the problem of generating appropriate schedules to maximize quality improvement. In this paper, we propose an approach to automatically determine an appropriate schedule to maximize quality improvement through refactoring. We first detect code clones that are suitable for refactoring and generate the most beneficial refactoring schedule to remove them. It is straightforward to select the best from the exhaustively enumerated schedules. However, such a technique becomes NP‐hard, as the number of available refactorings increases. We apply a genetic algorithm (GA) to generate the best refactoring schedule within a reasonable time to cope with this problem. We compare the GA‐based approach with manual scheduling, greedy heuristic‐based, and exhaustive approaches for four open systems. The results show that the proposed GA‐based approach generates more beneficial schedules than the others. Copyright © 2010 John Wiley & Sons, Ltd.

Understanding software, especially in large-scale, is an important issue for software modification. In large-scale software systems, modularization provides help for understanding them. But, even if a system has a well-modularized design, the modular design can be deteriorated by system change over time. Therefore it is needed to assess and manage modularization in the view of understandability. However, there are rarely studies of a quality assessment model for understandability in the module-level. In this paper, we propose a hierarchical model to assess understandability of modularization in large-scale object-oriented software. To assess understandability, we define several design properties, which capture the characteristics influencing on understandability, and design metrics based on the properties, which are used to quantitatively assess understandability. We validate our model and its usefulness by applying the model to an open-source software system.

The effectiveness of mutation testing depends heavily on the types of faults that the mutation operators are designed to represent. Thus, the quality of the mutation operators is key to mutation testing. Although, mutation operators for object-oriented languages have previously been presented, little research has been done to show the usefulness of the class mutation operators. To assess the usefulness of class mutation operators, we conducted two empirical studies. In the first study, we examine the number and kinds of mutants that are generated for object-oriented programs. In the second study, we investigate the way in which class mutation operators model faults that are not detected by traditional mutation testing. We conducted our studies using a well-known object-oriented system, BCEL.

Mutation testing is a valuable experimental research technique that has been used in many studies. It has been experimentally compared with other test criteria, and also used to support experimental comparisons of other test criteria, by using mutants as a method to create faults. In effect, mutation is often used as a ``gold standard'' for experimental evaluations of test methods. Although mutation testing is powerful, it is a complicated and computationally expensive testing method. Therefore, automated tool support is indispensable for conducting mutation testing. This demo presents a publicly available mutation system for Java that supports both method-level mutants and class-level mutants. MuJava can be freely downloaded and installed with relative ease under both Unix and Windows. MuJava is offered as a free service to the community and we hope that it will promote the use of mutation analysis for experimental research in software testing.

Several module and class testing techniques have been applied to object-oriented (OO) programs, but researchers have only recently begun developing test criteria that evaluate the use of key OO features such as inheritance, polymorphism, and encapsulation. Mutation testing is a powerful testing technique for generating software tests and evaluating the quality of software. However, the cost of mutation testing has traditionally been so high that it cannot be applied without full automated tool support. This paper presents a method to reduce the execution cost of mutation testing for OO programs by using two key technologies, mutant schemata generation (MSG) and bytecode translation. This method adapts the existing MSG method for mutants that change the program behaviour and uses bytecode translation for mutants that change the program structure. A key advantage is in performance: only two compilations are required and both the compilation and execution time for each is greatly reduced. A mutation tool based on the MSG/bytecode translation method has been built and used to measure the speedup over the separate compilation approach. Experimental results show that the MSG/bytecode translation method is about five times faster than separate compilation. Copyright © 2004 John Wiley & Sons, Ltd.

Mutation testing is a fault-based testing technique which provides strong quality assurance. Mutation testing has a very long history for the procedural programs at unit-level testing, but the research on mutation testing of object-oriented programs is still immature. Recently, class mutation operators are proposed to detect object-oriented specific faults. However, any analysis has not been conducted on the class mutation operators. In this paper, we evaluate the orthogonality of the class mutation operators by some experiment. The experimental results show the high possibility that each class mutation operator has fault-revealing power that is not achieved by other mutation operators, i.e. orthogonal. Also, the results show that the number of mutants from the class mutation operators is small so that the cost is not so high as procedural programs.

The existing cohesion metrics for classes do not consider the characteristics of dependent instance variables that are commonly used in a class and, thus, do not properly reflect the cohesiveness of the class. This paper presents an approach for improving the cohesion metrics by considering the characteristics of the dependent instance variables in an object-oriented program.

Abstract The authors insist that monotonicity is a necessary property of a good cohesion metric and the violation of the monotonicity property limits the application of CBMC. They also state that the augmented CBMC can also be used as a guideline for quality evaluation and restructuring of poorly designed classes. This paper raises the question about the necessity of monotonicity by analyzing the reason that causes CBMC to violate the monotonicity property. In addition, we give a detailed description of the restructuring procedure based on CBMC. Copyright © 2003 John Wiley & Sons, Ltd.

The effectiveness of mutation testing depends heavily on the types of faults that the mutation operators are designed to represent. Therefore, the quality of the mutation operators is key to mutation testing. Mutation testing has traditionally been applied to procedural-based languages, and mutation operators have been developed to support most of their language features. Object-oriented programming languages contain new language features, most notably inheritance, polymorphism, and dynamic binding. Not surprisingly; these language features allow new kinds of faults, some of which are not modeled by traditional mutation operators. Although mutation operators for OO languages have previously been suggested, our work in OO faults indicate that the previous operators are insufficient to test these OO language features, particularly at the class testing level. This paper introduces a new set of class mutation operators for the OO language Java. These operators are based on specific OO faults and can be used to detect faults involving inheritance, polymorphism, and dynamic binding, thus are useful for inter-class testing. An initial Java mutation tool has recently been completed, and a more powerful version is currently under construction.

Abstract Although numerous empirical studies have been conducted to measure the fault detection capability of software analysis methods, few studies have been conducted using programs of similar size and characteristics. Therefore, it is difficult to derive meaningful conclusions on the relative detection ability and cost‐effectiveness of various fault detection methods. In order to compare fault detection capability objectively, experiments must be conducted using the same set of programs to evaluate all methods and must involve participants who possess comparable levels of technical expertise. One such experiment was ‘Conflict1’, which compared voting, a testing method, self‐checks, code reading by stepwise refinement and data‐flow analysis methods on eight versions of a battle simulation program. Since an inspection method was not included in the comparison, the authors conducted a follow‐up experiment ‘Conflict2’, in which five of the eight versions from Conflict1 were subjected to Fagan inspection. Conflict2 examined not only the number and types of faults detected by each method, but also the cost‐effectiveness of each method, by comparing the average amount of effort expended in detecting faults. The primary findings of the Conflict2 experiment are the following. First, voting detected the largest number of faults, followed by the testing method, Fagan inspection, self‐checks, code reading and data‐flow analysis. Second, the voting, testing and inspection methods were largely complementary to each other in the types of faults detected. Third, inspection was far more cost‐effective than the testing method studied. Copyright © 2002 John Wiley & Sons, Ltd.

To ensure that a component-based software system can run properly and effectively, the qualities of constituent components have to be assured. Third-party certification is a safe approach that buyers should trust when dealing with component software. However, current third-party certification methods do not support proper functional testing, which is the most important factor when selecting the component. In this paper, we will suggest a framework of third party component testing of functionality, satisfying the following given constraint. evaluation of a large number of components within short period of time in a cost-effective way. In this framework, we identify, the metadata that a component developer should provide to the third party tester and define the process for third party testing using these metadata. To evaluate our framework, we conducted several experiment with Component Test Manager (CTM), prototype tool for EJB component testing. The result shows that our metadata are positively necessary and the participation of a component developer is the key to third party testing.

Deterministic execution testing has been considered a promising method for concurrent program testing because of its reproducibility. However, since deterministic execution requires that a synchronization sequence to be replayed is feasible and valid, it is not directly applicable to a situation in which synchronization sequences, being valid but infeasible, are taken into account. To resolve this problem, we proposed automata-based testing in previous work, where a concurrent program is executed according to one sequence accepted by the automaton recognizing all sequences semantically equivalent to a given sequence. In this paper, we present the automata-based testing environment for Java multi-thread programs, and design and implement key components-automata generator, program transformer and replay controller. Algorithms for generating the equivalence automaton of a given sequence are presented and a program transformation method is suggested in order to guide a program to be executed according to the sequence accepted by the automaton. The replay controller is also redesigned and implemented to adopt the automaton. By illustrating automata-based testing procedures with the gas station example, we show how the proposed approach works in Java multi-threaded programs.

Abstract This paper describes an impact analysis technique that identifies which parts should be retested after a system written in C++ is modified. We are interested in identifying the impacts of changes at the class member level by using dependency relations between class members. We try to find out which member functions need unit‐level retesting and which interactions between them need integration‐level retesting. To get precise analysis results, we adopt a technique that classifies types of changes and analyze the impact for each type. Primitive changes, changes which are associated with C++ features, are first defined and their ripple effects are computed in order to construct a firewall for each type of change systematically. We have applied our prototype tool to a real system with small size. This case study shows some evidence that our approach gives reasonable efficiency and precision as well as being practical for analyzing change impacts of C++ programs. Copyright © 2001 John Wiley & Sons, Ltd.

Abstract Indicating that CBMC does not satisfy the monotonic property in terms of the number of interactions, Xu and Zhou proposed an augmented definition of CBMC by adopting cut set instead of glue methods. The augmented CBMC clearly satisfies the monotonic property. However, CBMC is designed to overcome the problem with respect to the number of interactions and, therefore, focuses on the interaction pattern, especially, member connectivity. Consequently, it does not make sense to mention the monotonic property of CBMC with respect to interaction number. Moreover, the notion of glue methods allows several interpretations on the design quality of a class. However, that meaningful interpretation is not possible for the augmented definition due to the removal of the notion of glue methods. Copyright © 2001 John Wiley & Sons, Ltd.

In object-oriented systems, cohesion refers to the degree of the relatedness of the members in a class and strong cohesion has been recognized as a highly desirable property of classes. We note that the existing cohesion measures do not take into account some characteristics of classes, and thus often fail to properly reflect the cohesiveness of classes. To cope with such a problem, we propose a new cohesion measure where the characteristics of classes are incorporated. Our cohesion measure takes into account the members that actually have impact on the cohesiveness of a class, and is defined in terms of the degree of the connectivity among those members. We develop a cohesion measurement tool for C++ programs, and perform a case study on a well-known class library in order to demonstrate the effectiveness of our new measure. By performing principal component analysis, we also demonstrate that our measure captures a new aspect of class properties which is not captured by the existing cohesion measures. Copyright © 2000 John Wiley & Sons, Ltd.

This paper describes a specification-based regression testing technique that can be applied for revalidating concurrent programs after specification changes. This kind of regression testing technique requires sequencing constraints which specify the precedence relations among synchronization events. In our method, the sequencing constraints are extracted automatically from Message Sequence Charts (MSCs) that are considered to be partial and nondeterministic specifications. We show how to identify the sequencing constraints affected by the modifications of a specification rather than creating new sequencing constraints from scratch to reduce the cost of regression testing. We also describe how to determine whether the affected sequencing constraints are satisfied by the program being tested.

Modified programs are required to be retested to determine whether changes have been made correctly and to investigate whether those cause any adverse effect on the program behavior. Then, the key issue is the extent of the retesting tasks. To save time and efforts, retesting should be done on only the parts that might be affected by changes. Change impact analysis is the activity which identifies the parts to be retested. Object-oriented paradigm is based on several concepts such as encapsulation, inheritance, polymorphism, and dynamic binding. Although these features contribute to the reusability and extensibility of systems, they produce complex dependencies between classes and attributes, which make it difficult to identify the affected components by changes. We propose an approach for analyzing change impact in a class hierarchy. Our approach is based on the class firewall method, but aims to reduce the retesting effort significantly by taking a member function as a test unit. We deal with the impacts of changes associated with various object-oriented features as well as types of changes which can occur at the level of a data member a member function, a class, and an inheritance relation.

It is well known that requirements engineering plays a critical role in software quality. The use case approach is a requirements elicitation technique commonly used in industrial applications. Software requirements are stated as a collection of use cases, each of which is written in the user's perspective and describes a specific flow of events in the system. The use case approach offers several practical advantages in that use case requirements are relatively easy to describe, understand, and trace. Unfortunately, there are a couple of major drawbacks. Since use cases are often stated in natural languages, they lack formal syntax and semantics. Furthermore, it is difficult to analyze their global system behavior for completeness and consistency, partly because use cases describe only partial behaviors and because interactions among them are rarely represented explicitly. We propose the Constraints-based Modular Petri Nets (CMPNs) approach as an effective way to formalize the informal aspects of use cases. CMPNs, an extension of Place/Transition nets, allow the formal and incremental specification of requirements. The major contributions of the paper, in addition to the formal definitions of CMPNs, are the development of: 1) a systematic procedure to convert use cases stated in natural language to a CMPN model; and 2) a set of guidelines to find inconsistency and incompleteness in CMPNs. We demonstrate an application of our approach using use cases developed for telecommunications services.

An underlying assumption for N-version programming technique is that independently developed versions would fail in a statistically independent manner However empirical studies have demonstrated that common mode failures can occur even for independently developed versions, and that common mode failures degrade system reliability. In this paper, we demonstrate that the weakest precondition analysis is effective in determining input spaces leading to common mode failures. We applied the weakest precondition to the Launch Interceptor Programs which were used in several other experiments related to the N-version programming technique. We detected 13 out of 18 fault pairs which have been known to cause common mode failure. These faults were due to logical flaws in program design. Although the weakest precondition analysis may be labor-intensive since they are applied manually our results convincingly demonstrate that it is effective for identifying input spaces causing common mode failures and further improving the reliability of N-version software.

The SCR method models a system using a set of variables and state machines whose behaviour is described by tabular notations. This paper proposes an interleaving semantics for SCR specifications in terms of timed transition systems. The semantics is given by identifying each of the components of a timed transition system from a given SCR specification. The concurrent behaviour of a SCR specification is defined as a set of computations of the resulting timed transition system.

A new method for version controlling of a tree structure is presented. The key feature of the method is that the latest state of a tree is retained and other versions are constructed from it on request, and information on the change history of a node is maintaind in its parent node. Several algorithms for efficient manipulation of the tree have been developed, and it has been demonstrated that they correctly manipulate the tree. The performance of these algorithms has been compared with those of other tree-based methods, and found to be nearly optimal in all aspects of the comparison. © 1997 John Wiley & Sons, Ltd.

Classes are the fundamental concepts in the object-oriented paradigm. They are the basic units of object-oriented programs, and serve as the units of encapsulation, which promotes their modifiability and reusability. However, improper modeling in the design phase or uncontrolled changes during the maintenance phase can degrade the quality of classes, which leads to programs which are cumbersome to maintain or extend. The paper proposes a method for assessing the quality of classes and restructuring them. The authors define an abstraction as the most cohesive form of a class, and the cohesion indicates the extent to which a class approaches the abstraction. Assessment and restructuring are both based on the notion of class cohesion. Less cohesive classes can be transformed into a form of an abstraction by restructuring them.

We discuss how conventional testing criteria such as branch coverage can be applied to the testing of member functions inside a class. To support such testing techniques we employ symbolic execution techniques and finite state machines (FSMs). Symbolic execution is performed on the code of a member function to identify states that are required to fulfil a given criterion. We use FSMs to generate a sequence of member functions leading to the identified states. Our technique is a mixture of code-based and specification-based testing techniques in the sense that it uses information derived from codes using symbolic execution together with information from specifications using FSMs for testing activities.

Guaranteeing reproducibility and minimizing probe effects are major issues in the parallel program debugging. The paper suggests a new debugging method, called the Detect and Reproduce method, for message-based parallel programs. The proposed method is designed to guarantee the reproducible behaviors of a target program and to alleviate probe effects by reducing both the number of the probes to be inserted into a program and the amount of information gathered by those probes. The proposed method achieves such effects by employing a static analysis technique to detect nondeterminacy. By detecting nondeterminacy before running the program, only a small number of probes are required to assure reproducibility. To analyze message-based programs statically, an MHB (minimal happened before) model is designed to catch the synchronization structures and algorithms have been developed to locate nondeterminacy based on the MHB model. Utilizing the analysis results, probes are inserted only into the places where nondeterminacy is likely to take place.

In object-oriented testing literature, a class is considered to be a basic unit of testing. A major characteristic of classes is the interaction between data members and member functions. This interaction is represented as definitions and uses of data members in member functions and can be properly modeled with finite state machines (FSM). We discuss how FSMs can be effectively used for class testing. We demonstrate how to specify the behavior of classes using FSMs and present a test case generation technique based on FSMs. In our technique, FSMs are transformed into a flow of the graph from which we can explicitly identify data flows of the FSM. Then we generate test cases using conventional data flow testing techniques upon the flow graph.

The paper presents the results of an experiment that compared error detection capability of voting, instrumentation, and Fagan inspection methods. Several experiments have measured effectiveness of various error detection methods. However, most experiments have used different programs; consequently, the results are generally incompatible and do not allow one to make objective comparison on the cost-effectiveness of various approaches. Software cannot be developed using an unlimited amount of resources, and practitioners need empirical and objective data on the cost-effectiveness of various error detection methods to decide which methods to use during software development. Results of this experiment is significant because these methods have been applied to the same program. Furthermore, the participant's educational and industrial experience are comparable to that of the previous experiments. We confirmed the previous finding that detecting errors in reliable programs is difficult; none of the three methods detected more than half of all the known errors in the programs. Of the three methods employed, participants detected more errors by using Fagan inspection method than they did by voting or instrumentation. When the average number of hours needed to detect an error was compared, Fagan inspection method was shown to be more cost-effective than instrumentation method.

Process modeling has become increasingly attractive in the software engineering community. In process modeling, the enactment of software process model is a dominant theme. In order to correctly and smoothly enact the software process model, it is necessary to detect the inconsistencies contained in the software process model early, before the software process model is instantiated to actual enactment engine. We provide an analysis framework and an enactment mechanism for the AttNet model which is based on Petri nets and supports the distributed software processes.>

Software restructuring is recognized as a promising method to improve logical structure and understandability of a software system which is composed of modules with loosely-coupled elements. In this paper, we present methods of restructuring an ill-structured module at the software maintenance phase. The methods identify modules performing multiple functions and restructure such modules. For identifying the multi-function modules, the notion of the tightly-coupled module that performs a single specific function is formalized. This method utilizes information on data and control dependence, and applies program slicing to carry out the task of extracting the tightly-coupled modules from the multi-function module. The identified multi-function module is restructured into a number of functional strength modules or an informational strength module. The module strength is used as a criterion to decide how to restructure. The proposed methods can be readily automated and incorporated in a software tool.

Abstract Software revalidation through retesting during the maintenance phase is essential for establishing confidence in the reliability of the modified programs. In this paper, we present a testing criterion and techniques for revalidating modified programs as well as the conditions to determine the necessity for revalidation of the modified program. By comparing programs and identifying the textual and semantic changes between them, it is shown that the number of test cases to be rerun can be reduced compared to the current revalidation methods. Our method is applicable to programs with different control structures from the original program with a little effort by treating the test case reuse problem as a constraint satisfaction problem. In addition, application of an zero‐one integer programming model to select the minimal set of paths to be retested is explored.

Researchers in software as well as software engineering are having difficulty defining projects with concrete goals and well-organized teams as demanded by funding sources. Upcoming large-scale software projects initiated by the government are expected to create a lot of research opportunity and thereby drive the domestic software technology to a higher level. A review is presented of Korea's software industry and software technology, and future issues are examined.>