A common problem in the interclass integration testing of object-oriented software is to determine the order in which classes are integrated and tested, which is generally called the class integration test order (CITO) generation problem. The CITO can affect the design and execution of test cases, the order in which integration faults are revealed, and the required test stubs. Therefore, an optimal CITO for an object-oriented program is desired because it can facilitate the detection of integration faults or bugs, and meanwhile save test efforts. However, searching for the optimal CITO is a NP hard problem. Therefore, the existing studies aim to devise a CITO with the lowest possible test efforts.

Despite the encouraging results obtained by the existing approaches, some problems limit the performance and generality of these approaches. One limitation is that these approaches are ineffective due to the ignorance of the factors that affect the overall stubbing cost of CITOs (Problem 1). The other limitation is that these approaches are inefficient when generating the CITOs for programs with a moderately large number of classes (Problem 2). Another significant threat is that a test oracle problem exists in these CITO generation systems (Problem 3). In this thesis, we deal with these three problems.

For Problem 1, the unsatisfactory effectiveness is due to the ignorance of the factors that affect the overall test efforts. To address this problem, a new cycle-breaking algorithm ANS is introduced to perform a good Analysis of the relationship between the Number of removed dependencies and the related Stubbing complexity, which are the two main factors that affect the overall test efforts. Given a set of class dependencies that are going to be removed, this algorithm finds superior alternatives that break the same cycles or an equal number of cycles with lower stubbing cost than the original class dependencies.

For Problem 2, the inefficiency of the existing approaches for CITO generation is caused by the huge search space, and therefore, we propose a method called CITOSC (Class Integration Test Order generation with Similar-class Combination), which is based on the hypothesis that similar-class combination can remove class dependencies and yield a smaller problem space. Identical class dependence and symmetric classes are the two main properties that are used to identify similar classes.

To address Problem 3, we apply Metamorphic Testing (MT) to validate CITO generation systems and implement it as CITOMT (validating Class Integration Test Order generation systems with Metamorphic Testing). MT has been applied to alleviate test oracle problem in other areas of software testing. Metamorphic Relations (MRs), which are the key components of MT, reason about relations between test outputs of a system. We propose five kinds of MRs to ensure the quality of the CITO generation systems. In these proposed MRs, follow-up test inputs are generated by modifying classes or class dependencies in the source test inputs while some characteristics of the source test outputs are preserved, for example, the same CITO or the equal stubbing cost. Faults can be detected in the CITO systems if an individual MR is violated for certain tests.

Experiments are conducted to evaluate the performance of these proposed methods. The cycle-breaking algorithm ANS achieved reduction of more than 13% in the test efforts, thus outperforming other competing techniques. With similar-class combination, CITOSC minimized the search space. Specifically, it reduced the numbers of classes and class dependencies by over 10% and 6%, respectively, for six of nine used Java programs. Moreover, for four programs, CITOSC reduced the number of cycles among class dependencies by more than 20%. For CITOMT, failure detection of MT has been successfully demonstrated on three systems implementing the above mentioned competing techniques. On mutation analysis, more than 84% of faulty programs can be detected by all MRs for these CITO generation systems under investigation. To the best of our knowledge, we are the first to introduce MT to validating CITO generation systems. We hope that the promising results will interest and encourage more in-depth research in this field.