A cost-effective adaptive random testing algorithm for object-oriented software testing

Abstract

The rapid development of object oriented programming (OOP) technology has made it one of the mainstream programming technologies that has been widely used in the design and development of object oriented software (OOS). The inheritance, encapsulation and polymorphism properties of object-oriented language can improve the reusability, scalability and interoperability of software while increasing the difficulty of testing OOS. Researchers have proposed a variety of testing methods to test OOS among which random testing (RT) has been widely used due to its simplicity and ease of use. An OMISS-ARTsum algorithm is proposed in this paper that uses improved OMISS random test FSCS-ART with max-sum standard, which is an implementation version of fixed-sized-candidate-set ART. The OMISS-ARTsum algorithm calculates the total distance between a candidate test case and the executed test case set before the next test case is selected from the set of candidate test cases. Unlike the traditional max-sum based FSCS-ART algorithm, OMISS-ARTsum does not calculate the distance between each executed test case and the candidate case and then sum up the total distance, but uses the method of summing up all the executed test cases and the candidate cases. The information of executing test cases is saved as a whole and the distance between the executed test case set and candidate cases is calculated at the same time. Experiment shows that compared to the OMISS-ART algorithm, the proposed OMISS-ARTsum algorithm can reduce the time overhead.

Keywords

Object oriented software adaptive random testing test input time cost

1 Introduction

In recent years, object oriented programming (OOP) technology has experienced rapid development that has made it the mainstream programming technology and has been widely used in the design and development of object oriented software (OOS). The three characteristics of object-oriented languages, i.e., inheritance, encapsulation and polymorphism, [1, 2] help to improve software reusability, scalability and interoperability while increasing the difficulty of OOS testing [3]. Software testing is an important means of guaranteeing software quality [4]. For this reason, researchers have proposed a variety of test methods to test the security of OOS [5 –9].

A very important issue in software testing is the selection of test cases. Effective software testing automatically picks up test cases because manual selection is time-consuming and labor-intensive. Random testing (RT) [10 –12] is a technique for automatically selecting test cases. The principle is simple, that is, to randomly select test cases from the entire input field. RT has a wide range of practicalities, is easy to implement in automated test tools, has no overhead for selecting test cases from a test input set, and does not treat different test cases differently when test cases are selected. Therefore, the technology that guarantees software quality [13 –15] makes it easy to evaluate the effectiveness of software and is also widely used in the industry [16].

Researchers have found that defective software usually has a continuous failure area. Therefore, if the test cases selected by the random test can be evenly distributed throughout the input domain, the effectiveness of the test method will be greatly improved. Based on this, Chen et al. proposed adaptive random testing (ART) [17] that is dedicated to enhancing the ability of RT to detect faults. ART guides the generation of test cases by using a similarity/non-similarity measure to distribute test cases as evenly as possible throughout the input domain [18, 19]. ART has been widely used in programs with numerical inputs. However, due to the complex structure of OOS programs, the difficulty of calculating the differences between test inputs has increased, making the application of ART to object-oriented software a great challenges.

To quantify the differences between OOS test cases, researchers have proposed the concept of distance metrics for measuring the distance between non-numeric inputs and some formulas. Ciupa et al. proposed a measure mechanism for calculating the distance between two objects from the same class or derived from the same ancestor and proposed an object-oriented adaptive random test algorithm based on this distance measure mechanism [20, 21]. Object-oriented software (ARTOO) selects the candidate case that is the farthest from all the test cases in the executed test case set from the set of candidate test cases as the next test to be executed.

Lin et al. claimed that the input space of object-oriented programs is usually multi-dimensional [22] and extended ARTOO to propose a divergence-oriented approach to adaptive random testing (DO-ART). DO-ART selects the test cases furthest from all used test cases from the test case pool so that the selected test cases are evenly distributed across the test case pool. Chen et al. observed that OOS test cases usually contain multiple objects and multiple methods of multiple classes [23], including a collection of objects and a sequence of method calls, and the distance metric used by ARTOO and DO-ART cannot calculate this. Therefore, they proposed a measure of the difference in test input in object-oriented software, which was named the object and method invocation sequence similarity (OMISS).

Let’s now review some technologies on software testing. First is random testing in which test cases are randomly selected from the entire input domain. Because of its simple principle and easy implementation, it is widely used in OOS testing. Ciupa et al. studied the predictability of randomized tests [24] and, through experiments, found out that from the beginning of the experiment, after 10 minutes, 30% of all failures were detected, and after 90 minutes, 38% of all failures were detected. At the same time, they also found that the relative number of faults detectable by random tests is predictable, but the faults detected based on different test case generators are different, ie the type of faults detectable by RT is unpredictable. Moreover, the time when the RT detected the first error was also predictable. They found that RT could quickly find the first error, as in their experiments, always within 30 seconds.

Ciupa et al. concluded that the number of faults detected by different test case generators is roughly the same [25] and, therefore, the number of detected faults can be used as a standard to judge whether a test method is good and accurate. Through experimental research, it was found that each test method has its specific detectable abnormalities. Almost no test method can detect all the abnormalities that could be detected by other test methods, that is, no test method can completely replace test methods. Therefore, they concluded that RT can be used in conjunction with other test methods to find different faults.

Random testing refers to random selection of test cases from the input domain, i.e., each test case is equally likely to be selected. Adaptive random testing selects test cases from the entire input domain according to certain rules, i.e., each test case is no longer equally likely to be selected. Chen et al. found that test cases in a program are clustered according to whether they can reveal the nature of the fault, i.e., the test cases causing the errors are gathered together, and so are the safe test cases. Based on this finding, Chen et al. proposed that if the test cases selected by the random test were evenly distributed throughout the input domain, the likelihood of these test cases detecting errors would increase. Therefore, Chen et al. proposed ART [26], which uses some test case selection rules to guide the generation of test cases, which can greatly improve the ability of random tests to find errors. Chen et al. also proposed an adaptive random test for a fixed number of candidate test cases (SCS-ART). The algorithm has a set of candidate test cases and a set of executed test cases. Each time the candidate test case set is selected, the farthest distance from all the test cases in the executed test case set is executed. The candidate use case is the next pending use case [27]. Experiments showed that SCS-ART greatly improved the ability of RT detection errors [28].

ARTOO [21] is an object-oriented adaptive random test method for testing Eiffel programs. Its test input contains a specific method and an object, which is the call object of the method. When the next test case is selected, the target object and the parameters of the method are selected, which selects the object furthest from the used object and the parameter farthest from the used parameter. Therefore, the distance metric in ARTOO is used to calculate the distance between two objects, which consists of the basic distance, the type distance and the recursive distance.

DO-ART [22] is an extension of ARTOO. Its test case involves a selected object and a sequence of method calls with length n. The last method called is the method being tested. The previous n-1 call method is used to create selected object. DO-ART uses the distance measure of ARTOO, but prepares a set of test inputs for the test program with each test input being significantly different from the other test inputs. OMISS-ART [23] is a similarity measurement mechanism that uses test input in an object-oriented program. The distance metric used in OMISS-ART calculates the distance between multiple objects, containing multiple classes and test cases for multiple methods.

Unit testing of OOS based on RT technology has been receiving attention in the software testing community [10 , 29–32]. D’Amorim et al. proposed unit testing as an important, common and substantial part of software development [33]. They analyzed that unit testing typically involves two main technologies, i.e., automated test generation techniques and automated test classification techniques. Among them, automatic test generation techniques include random generation and symbolic execution and automatic test classification techniques include techniques based on uncaught exceptions inferred from manually provided tests and operational models that violate rules. Consequently, they developed a model-based symbol testing method for OOS unit testing and conducted experimental research to compare the performance of the method and the other three technologies. The other three technologies are model-based random testing, abnormal symbol based testing and random tests based on exceptions. They found that random generation is uncertain and depends on random seeds that can produce different test cases while symbolic execution has opposite properties due to incompleteness of theorem prover and incompleteness of the constraint solver. They also found that these technologies are complementary in revealing faults and it is recommended that test tools and test users apply several techniques to the same test code to find errors more effectively.

Barus et al. proposed an adaptive random test algorithm (ARTsum) [34] for testing structured software with non-numeric inputs, which has a linear time overhead, i.e., the time it takes to pick n test cases is O(n). They proposed that in order to apply ART to software with non-numeric inputs, a suitable distance tool for measuring the difference between non-numeric inputs is needed. They used the concept of classification and selection from class partition testing to measure the distance between structured test cases. Then a new FSCS-ART algorithm is implemented based on the classification-selection distance metric and the max-sum selection criteria. When ARTsum picks the next test case from the set of candidate test cases, it calculates the sum of the distances between each candidate use case and all executed test cases and selects the largest test case as the next pending test case. ARTsum uses an integer tuple S to hold information about all executed test cases and the classification-selection distance metric to calculate each candidate use case and executed test.

2 Adaptive random testing

Chen et al. found that the distribution of the test input causing the fault showed three modes [26], namely, dot, strip and block. Inputs that cause errors in the dot pattern are not aggregated into one or more regions, but are widely dispersed throughout a large portion of the input domain. Inputs that cause errors in the strip mode form the shape of the strip. Inputs that cause errors in the block mode are concentrated in a closed area. Studies have shown that the distribution of errors that cause the formation of strips and blocks are widespread and the point-like differences are relatively rare. Based on this, Chen et al. proposed adaptive random test to make the test cases distributed as evenly as possible throughout the input domain so that when error, strip and block distributions are presented, errors can be found more quickly, thereby increasing randomness. Test failure detection efficiency.

Many researchers have found that the inputs that cause faults tend to form a continuous region [35]. Based on this finding, Chen et al. proposed an adaptive random test [17, 26] to make the test input more evenly distributed throughout the input domain, thus improving the effectiveness of random testing. In order to achieve a uniform distribution of test inputs, researchers have proposed a number of adaptive random test algorithms.[22 , 36–43] ART is no longer a random selection of test cases, but a selection of test cases through certain rules, among which are distance-based selection, selection based on exclusion regions and selection based on region division.

FSCS-ART [26] is the most classic and most important adaptive random test algorithm based on distance operation. Each time a test case is selected, it has a fixed number of candidate test cases and then the candidate test case is calculated and executed. FSCS-ART has two sets of test inputs, one is the executed set called E and the other is the candidate set called C, and the test cases in C are randomly generated. The core idea of FSCS-ART is to select the candidate test case furthest away from the test case in distance E from C according to the distance metric formula. In determining the farthest concept, a commonly used standard is max-min. The algorithm of the standard is used to first calculate the distance between each candidate test case and each test case in E, record the minimum distance, and then select the smallest distance. An alternative criterion is max-sum, which uses the standard algorithm to calculate the distance between each candidate test case and each test case in E, and then selects the distance and the largest candidate use case. Use of max-sum to select the standard FSCS-ART is shown in the following.

Algorithm 2.1: FSCS-ART based on max-sum selection criteria
1: Input: Distance metric DistMetric
2: E = {} //E is a set of executed test cases
3: Randomly generate test cases t
4: Add t to E
5: while does not meet the predefined stop condition do
6: maxDist = 0.0
7: Randomly generate k candidate test
8: cases: C = {c1, c2, . . . , ck}
9: for Each candidate use case c in C_i do
10: disti = 0.0
11: Each test case in t for t_j do
Calculate the distance d between c_i
and t according to DistMetric _j
12: dist_i+ = d_j
13: end for
14: if maxDist < dist_ithen
15: maxDist = disti
16: t = ci
17: end if
18: end for
19: Add t to E
20: end while

RRT (Restricted Random Testing) [44] is the most primitive random region-based random test algorithm. It divides a removal area with the same radius around each test case that has been executed but does not reveal the error. The test case can be selected from the removal area and can only be selected from outside the removal area.

ART-B and ART-RP are two basic randomization test algorithms based on region partitioning [38]. After ART-B randomly selects a test case from an unselected area, it divides the area and continues to pick. Each time ART-RP randomly selects test cases from the largest blank area, the area is divided at the selected test cases after selection.

MART (Mirror Adaptive Random Testing) [39] uses multiple selection rules. It first divides the input domain into multiple different regions, such as m, and then uses FSCS-ART to pick test cases in the first region and m-1 tests in other m-1 regions using mapping methods.

Algorithm validity metrics are used to describe the ability and efficiency of the algorithm to detect errors. Commonly used metrics are: F-measure (F^m), i.e., the number of test cases spent on finding the first error, F^m-time, i.e., the time it takes to find the first error, E-measure (E^m), i.e., the number of failures detected by a fixed number of test cases, P-measure (P^m), i.e., the probability of discovering at least one failure in the program with a fixed number of test cases [45]. The lower the F^m of an algorithm, the lower the F^m-time, and the higher the E^m, the higher the P^m and the more effective the algorithm is.

3 Efficient adaptive random algorithm based on omiss metrics

This section presents the OMISSsum metrics and formulas for calculating the distance between a test case and n test cases based on the OMISS metric [23]. Then, based on the OMISSsum distance metric, a time-efficient object-oriented adaptive random test algorithm is proposed.

Data abstraction, inheritance, and dynamic binding are three basic concepts of object-oriented programming [3]. Most object-oriented programming languages use classes for data abstraction and use class derivation to inherit from another class: derived classes inherit members of the base class. Dynamic binding allows the compiler to decide whether to use a function defined in the base class or a function defined in a derived class. A class is an abstraction of a series of concrete concepts that look different but essentially the same. It consists of properties and methods. An object is an instance of a class that has some specific property values and common behavior. The properties section includes custom properties and properties that are inherited from the parent class. In addition, attributes can be divided into reference attributes and non-reference attribute. The type of the reference attribute is a reference type, such as a class, etc., and the type of the non-reference attribute is a basic type, such as bool, int, char, and so on.

For the two parts: t.OBJ and t.MINV, t.OBJ represents a collection of objects and objects in an object collection can come from many different classes and t.MINV represents a sequence of method calls. When the method being called is non-static, the method call requires objects and methods, where the object is the caller, the method is the callee, and the object and method are from the same class. Therefore, for any non-static methods called in t.MINV, the corresponding call object must appear in t.OBJ. In general, for test input, the object part and the method call part are not empty. However, in the case of testing only the correctness of the constructor, the method call sequence part is empty whereas in the case of testing only the correctness of the static method, the object set part is empty.

Chen et al. proposed to use the OMISS metric to describe the difference between the two test cases in the OOS that have the test case structure, i.e., test case distance in OMISS metrics [23]. Testcase Distance is equal to the sum of the distance between the object set (TCobjDist) and the distance between the method call sequences (TCmSeqDist). That is, the distance between the two test cases t₁ and t₂ is: TestcaseDistance (t₁, t₂)

$\begin{matrix} TCobjDist {(t}_{1} . OBJ, t_{2} . OBJ) \\ = TCmSeqDi {st (t}_{1} . MINV, t_{2} . MINV) \end{matrix}$ (1)

The distance between the method call sequences includes the difference in length between the two method call sequences (LenD), the difference in the method set (MsD), and the difference in the method call sequence (SD). The difference based on the method set is equal to 1 minus the number of methods in which the intersection of t1.MINV and t2.MINV is divided by the number of methods of t¹.MINV and t².MINV. The difference in the method call sequence treats the method call sequence as an ordered list and calculates the ratio of the number of positions in the two method sequences that are not the same at the same position to the length of the shorter method sequence.

When the distance between object sets in OMISS is calculated, first the set with fewer objects is expanded by adding empty objects so that the expanded object set and the set with more objects contains the same number of objects. For example, suppose there are k¹ objects in t¹.OBJ, k² objects in t².OBJ, and k² is smaller than k¹, then t².k¹-k² empty objects should be added to OBJ so that there are k¹ objects in t².OBJ. Then the order of the objects in t¹.OBJ is fixed and the k¹ objects in t².OBJ are arranged to be aligned with the objects in t¹.OBJ for a total number of k¹! arrangement. Then, the distances between the two objects t¹.OBJ and t².OBJ are calculated. The smallest total distance among the k¹! total number of distances is the distance between t¹.OBJ and t².OBJ.

Object distance is used to measure the difference between two objects. Object distance in OMISS (ObjDist) is equal to the sum of the distance of the object’s behavior part (BehDist) and the distance of the object’s attribute part (AttDist). That is, the distance between two objects p and q is ObjDist(p, q) = BehDist(p.M, q.M)+AttDist(p.A, q.A) if neither p nor q is null, where pM represents the behavior part of the object p, i.e., the method part of the class associated with the object p and pA represents the attribute part of the object p. The distance between the behavioral parts of the two objects p and q includes the difference in the number of methods and the set of methods contained in the class they are associated with. When the behavior distance is calculated, we should first consider the behavior part of the class associated with p and q as the two method sets pM and qM. BLenD is equal to the absolute value of the difference between the number of methods included in pM and qM where k^p . M represents the number of methods contained in pM; the difference in method content BMsD is equal to 1 minus the ratio of the number of methods included in the intersection of pM and qM to the number of methods contained in the union of pM and qM where pAN represents the set of non-reference attributes contained in object p and pAR represents the set of reference attributes contained in object p.

Calculation of the distance of the reference properties of the objects p and q iteratively uses the formula for calculating the distance between the object sets, i.e., pAR and qAR are treated as two object sets, and the formula is refDist (p.AR, q.AR)*TCobjDist (p.AR, q.AR) where α is a non-negative number, usually α = 1/2.

The non-reference attribute distance between two objects p and q contains two parts, one is the difference in attribute type (typeDist) and the other is the difference in attribute value, i.e., the basic distance (secDist). The basic distance is treated as an auxiliary distance in the OMISS metric and is saved in the form of the distance representation a + bi where a is the primary distance and b is the auxiliary distance because the OMISS distance definition considers the structural difference of the object to be more important than the value of the constructed object.

We now propose an object-oriented adaptive random test algorithm with lower time overhead, which takes nearly linear time in selecting n test cases. Compared to the FSCS-ART algorithm, the algorithm also has a set of candidate test cases, but uses max-sum to pick the criteria and use a new way to calculate the sum of the distances of each candidate test case from all previously executed test cases. Before describing the algorithm, let’s briefly review the basic implementation of the FSCS-ART algorithm based on the OMISS metric using the max-sum standard. Assume that n test cases have been selected and executed, which is denoted as E = t₁, t₂,..., t_n. The test case distance in the OMISS metric is equal to the sum of the method call sequence distance and the object set distance. Object distance is equal to method distance, reference attribute distance and non-reference attribute

As discussed in the previous section, it takes O(n) time to calculate the sum of the distances between a test case and n test cases using the OMISS metric. This section improves the formula for calculating the total distance between a test case and n test cases using the OMISS metric, and gives a new calculation formula so that the loop used in the new calculation formula is independent of the number of executed test cases, i.e., it has nothing to do with n. Since the new calculation formula is based on the OMISS summation formula, the new formula for calculating the total distance between a test case and n test cases is called the OMISSsum metric. The main idea of the OMISSsum metric is to treat the n executed test cases as a whole and use only one OMISSsum metric to get the total distance.

As described, the test case t consists of two parts: a collection of objects in t.OBJ-t and the method call sequence in t.MINV-t. Let’s define the test case set E as two parts: E.OBJ and E.MINV. E.OBJ is a collection of object collections where each object in the inner set of objects comes from a different executed test case. E.MINV is a collection of method sequences. If E = t₁, t₂, and t₁.OBJ = o₁₁, o₁₂, o₁₃ and t₁.MINV = m₁₁,m₁₂, t₂.OBJ = o₂₁, o₂₂, o₂₃, t₂.MINV = m₂₁, m₂₂, _m23, then E.OBJ = o₁₁, o₂₁, o₁₂, o₂₂,o₁₃, o₂₃, E.MINV = m₁₁, m₁₂, m₂₁, m₂₂, m₂₃.

Given the test case t and the test case set E, the distance between t and E (sum_TestcaseDistance) is equal to the sum of the object set distance (sum_TCobjDist) and the method call sequence distance (sum_TCmSeqDist), i.e., sum_TestcaseDistance(t, E) = sum_TCobjDist(t.OBJ, E.OBJ)+sum_TCmSeqDist(t.MINV, E.MINV).

To calculate the distance between a collection of objects, i.e., the distance between t.OBJ and E.OBJ, we need to add a null value to a collection with fewer elements according to the number of elements in t.OBJ and E.OBJ to make the two collections have the number of elements. For example, for E.OBJ = o₁₁, o₂₁, o₁₂, o₂₂, o₁₃, o₂₃, if t.OBJ = o₁, o₂, we need to add an empty object to t.OBJ, and if t.OBJ = o₁, o₂, o₃, o₄, we need add an empty collection of objects to E.OBJ. The distance between t.OBJ and E.OBJ is equal to the minimum of the sum of the distances of the objects in t.OBJ and the elements in E.OBJ, which are differently arranged.

4 Experiment and analysis

In this section, the three algorithms, i.e., OMISS-ARTsum, OMISS-ART and RT, are compared. For each method, 200 experiments are carried out with different seeds and the average was taken as the final result.

The variant test [48] is a fault-based widely used software testing technique that provides a test standard for testing the effectiveness of test case sets in fault detection capabilities. In the mutation analysis, for a given test input, if the running variant program (the wrong version obtained by injecting a simple syntax to change the original program) is different from the result of running the original program, the implanted error is found. This means that the test input has detected a fault. In the experimental analysis, the mutation test is also used to study the effectiveness and efficiency of the proposed algorithm.

In order to obtain the validity and time overhead of the OMISS-ARTsum algorithm for fault detection, we choose to study six target programs. These six programs are all from open source websites [49 –52] and are implemented in C# or C++. Table 1 summarizes the details of the six target programs and their implant errors. As can be seen from the table, these target programs have advantages and disadvantages as experimental objects. Calendar and SATM are small-scale libraries that are implanted with 5 and 4 failures, respectively. The size of the NSort library and the Wavelet Library library are also relatively small, respectively, with 15 and 14 faults being implanted. The IceChat and the Foundation libraries are large and have the most number of failure implants, 24 and 28, respectively. In all six procedures, faults are implanted into randomly selected methods and none of methods is implanted with two or more errors. Thirteen common mutation operations [48, 53] are: arithmetic operator substitution, logical operator substitution, relational operator substitution, constant substitution scalar, scalar replacement scalar, scalar substitution constant, array reference replacement constant, subclass type New method calls, parameter order changes, accessor method changes, access modifier changes, hidden variable missing, and replacement of attributes with member fields.

Table 1
Class libraries

Index Name of class library Number of lines in the code D Number Number of public methods Number of faults Description of class library

1 Calendar 287 5 27 5 C++ class library, mock calendar

2 SATM 197 1 9 4 C++ class library, analog ATM machine

3 WaveletLibrary 2406 12 84 15 C# class library, wavelet algorithm

4 NSort 1118 18 61 14 C# class library, sorting algorithm

5 Icechat 71000 101 271 24 C# class library, server and client

6 Foundation 149547 641 4480 28 C++ class library, computer network communication

Index	Name of class library	Number of lines in the code	D Number	Number of public methods	Number of faults	Description of class library
1	Calendar	287	5	27	5	C++ class library, mock calendar
2	SATM	197	1	9	4	C++ class library, analog ATM machine
3	WaveletLibrary	2406	12	84	15	C# class library, wavelet algorithm
4	NSort	1118	18	61	14	C# class library, sorting algorithm
5	Icechat	71000	101	271	24	C# class library, server and client
6	Foundation	149547	641	4480	28	C++ class library, computer network communication

In the experiment setup, for each target program, each test algorithm used a different seed to run 200 times to obtain the average of F_m. In order to obtain the number of errors detected when executing a fixed number of test cases, i.e. E_m, each test algorithm performed a total number of 5000 test cases. In order to study the number of detected test cases as the number of test cases increases, the number of detected faults and the time required to select test cases, when the number of test cases n = 100, 500, 1000, 1500,..., 4000 is recorded as well as the detected number of failures and the time spent. The test case picking time is also the average of 200 test runs using different seeds.

When generating a test case pool, each test case contains a maximum of 5 objects and methods and the test case pool contains a total of 10,000 test cases. The number of test cases (k) to be included is set to 10 when the algorithm uses the set of candidate test cases. The experiment showed that the efficiency of fault detection increases with increasing k, but the detection efficiency increases slowly after k is greater than 10 [31]. When the algorithm calculates the distance between test cases, the recursion depth is set to 4 if recursive calculation is involved. All experiments were performed on a machine with an Intel dual-core i3-4170, 3.70 GHz processor, 4GB RAM,

5 Conclusion

With the rapid development of object-oriented programming technology, object-oriented software is widely used in all walks of life. The inheritance, encapsulation and polymorphism of object-oriented languages, although beneficial to reusability, scalability and interoperability of software, increase the difficulty of testing OOS.Researchers have proposed a variety of test methods to test the security of OOS, which is one of the most popular testing techniques due to its simplicity and ease of implementation. In order to improve the ability of RT to detect faults, researchers proposed ART that is committed to guiding the generation of test cases and distributing them evenly throughout the test input domain. ART is primarily used for programs with numeric inputs. In order to apply ART to OOS, a metric needs to be designed to calculate the distance between object-oriented software test cases. Currently, the metrics for calculating the distance between OOS test cases are the ARTOO and the OMISS metrics. The ARTOO metric is used to calculate the distance between objects and the OMISS metric is used to calculate the distance between a test case containing a collection of objects and a sequence of method calls. Since the FSCS-ART algorithm using ARTOO metrics or OMISS metrics is needed to calculate the distance between the candidate test case and all executed test cases (n test cases) when selecting the next test case, there is the need to use n ARTOO metrics or OMISS metrics. In order to reduce the number of calculations and the calculation time, two improved metrics were proposed in this paper. Three object-oriented adaptive random test algorithms were proposed based on the corresponding metrics. A large number of experiments were carried out to verify the feasibility of the proposed algorithm. The main work can be summarized as follows. We analyzed the distance metric for the object-oriented software test for processing the distance between test cases with multiple objects and multiple methods - OMISS distance metric, and improved the OMISS distance metric to calculate the distance between a test case and n test cases with a formula. We presented the OMISS-ARTsum algorithm based on the improved formula for the OMISSsum metric. OMISS-ARTsum is based on the OMISSsum metric, max-sum picking standard FSCS-ART algorithm. When the OMISS-ARTsum algorithm selects the next test case to be executed from the set of candidate test cases, the information of all executed test cases is saved as a whole and the distance between the executed test case set and the candidate use case is calculated once.

Footnotes

Acknowledgments

The work in this paper has been supported by NQI Research on Key Technologies of Resource Aggregation and Sharing (No. 2017YFF0209602).

References

Pezze

, Young

, Testing object-oriented software, In 26th International Conference on Software Engineering, IEEE, (2004), 739–740.

Chen

H.Y.

, Tse

T.H.

, Chan

F.T.

, Chen

T.Y.

, In black and white: an integrated approach to class-level testing of object-oriented programs, ACM Transactions on Software Engineering and Methodology7(3) (1998), 250–295.

Binder

R.V.

, Testing object-oriented software: a survey, Software Testing, Verification and Reliability6(3-4) (1996), 125–252.

Bertolino

, Software testing research: Achievements, challenges, dreams, In Future of Software Engineering 2007, Los Alamitos, California, USA, IEEE Computer Society Press (2007), 75–84.

Ciupa

, Leitner

, Oriol

, Meyer

, Experimental assessment of random testing for object-oriented software, In 2007 International Symposium on Software Testing and Analysis ACM, (2007), 84–94.

Ducournau

, Perfect hashing as an almost perfect subtype test, ACM Transactions on Programming Languages and Systems30(6) (2008), 33.

Labiche

, Thévenod-Fosse

, Waeselynck

, Durand

M.H.

, Testing levels for object-oriented software, In 22nd International Conference on Software Engineering, ACM, (2000), 136–145.

d’Amorim

, Lauterburg

, Marinov

, Delta execution for efficient state-space exploration of object-oriented programs, IEEE Transactions on Software Engineering34(5) (2008), 597–613.

Andrews

J.H.

, Groce

, Weston

, Xu

R.-G.

, Random test run length and effectiveness, In 2008 23rd IEEE/ACM International Conference on Automated Software Engineering, IEEE CS, (2008), 19–28.

10.

Pacheco

, Lahiri

S.K.

, Ernst

M.D.

, Ball

, Feedback-directed random test generation, In 29th International Conference on Software Engineering, IEEE, (2007), 75–84.

11.

Chen

T.Y.

, Kuo

F.-C.

, Towey

, Zhou

, A revisit of three studies related to random testing, Science China Information Sciences58(5) (2015), 1–9.

12.

Pacheco

, Lahiri

S.K.

, Ball

, Finding errors in. net with feedback-directed random testing, In 2008 International Symposium on Software Testing and Analysis, ACM, (2008), 87–96.

13.

Ceccato

, Marchetto

, Mariani

, Nguyen

C.D.

, Tonella

, An empirical study about the effectiveness of debugging when random test cases are used, In 34th International Conference on Software Engineering, IEEE, (2012), 452–462.

14.

Zheng

, Zhang

, Lyu

, Xie

, Random unit-test generation with mut-aware sequence recommendation, In 2010 IEEE/ACM International Conference on Automated Software Engineering, ACM, (2010), 293–296.

15.

Andrea

, Muhammad

Z.I.

, Lionel

, Random testing: Theoretical results and practical implications, IEEE Transactions on Software Engineering38(2) (2011), 258–277.

16.

Pacheco

, Lahiri

S.K.

, Ball

, Finding errors in Net with feedback-directed random testing, In 2008 International Symposium on Software Testing and Analysis, ACM, (2008), 87–96.

17.

Chen

T.Y.

, Kuo

F.-C.

, Merkel

R.G.

, Tse

T.H.

, Adaptive random testing: The art of test case diversity, Journal of Systems and Software83(1) (2010), 60–66.

18.

Chen

T.Y.

, Kuo

F.-C.

, Liu

, Adaptive random testing based on distribution metrics, Journal of Systems and Software82(9) (2009), 1419–1433.

19.

Chen

T.Y.

, Kuo

F.-C.

, Liu

, Wong

W.E.

, Code coverage of adaptive random testing, IEEE Transactions on Reliability62(1) (2013), 226–237.

20.

Ciupa

, Leitner

, Oriol

, Meyer

, Object distance and its application to adaptive random testing of object-oriented programs, In 1st International Workshop on Random Testing, ACM, (2006), 55–63.

21.

Ciupa

, Leitner

, Oriol

, Meyer

, Artoo: Adaptive random testing for object-oriented software, In ACM/IEEE 30th International Conference on Software Engineering IEEE (2008), 71–80.

22.

Lin

, Tang

, Chen

, Zhao

, A divergence-oriented approach to adaptive random testing of java programs, IEEE CS (2009), 221–232.

23.

Chen

, Kuo

F.-C.

, Chen

T.Y.

, Towey

, Su

, Huang

, A similarity metric for the inputs of OO programs and its application in adaptive random testing, IEEE Transactions on Reliability66(2) (2017), 373–402.

24.

Ciupa

, Pretschner

, Leitner

, Oriol

, Meyer

, On the predictability of random tests for object-oriented software, In 1st International Conference on Software Testing, Verification and Validation, IEEE (2008), 72–81.

25.

Ciupa

, Pretschner

, Oriol

, Leitner

, Meyer

, On the number and nature of faults found by random testing, Software Testing Verification and Reliability21(1) (2011), 3–28.

26.

Chen

T.Y.

, Leung

, Mak

I.K.

, Adaptive random testing, ACM (2004), 320–329.

27.

Kuo

F.C.

, Chen

T.Y.

, Liu

, Enhancing adaptive random testing in high dimensional input domains, In 2007 ACM symposium on Applied computing, ACM, New York, USA, (2007), 1467–1472.

28.

Huang

, Xie

, Chen

, Failure-detection capability analysis of implementing parallelism in adaptive random testing algorithms, In 28th Annual ACM Symposium on Applied Computing, ACM, New York, USA, (2013), 1049–1054.

29.

Godefroid

, Klarlund

, Sen

, Dart: directed automated random testing, ACM Sigplan Notices, ACM, 40(6) (2005), 213–223.

30.

Pacheco

, Ernst

M.D.

, Randoop: feedback-directed random testing for java, In Companion to the 22nd ACM SIGPLAN Conference on Object-oriented Programming Systems and Applications Companion, ACM, (2007), 815–816.

31.

Oriol

, Tassis

, Testing, Net code with yeti, In 2010 15th IEEE International Conference on Engineering of Complex Computer Systems. IEEE (2010), 264–265.

32.

Chen

H.Y.

, Tse

T.H.

, Equality to equals and unequals: A revisit of the equivalence and nonequivalence criteria in class-level testing of object-oriented software, IEEE Transactions on Software Engineering39(11) (2013), 1549–1563.

33.

d’Amorim

, Pacheco

, Xie

, Marinov

, Ernst

M.D.

, An empirical comparison of automated generation and classification techniques for object-oriented unit testing, In 21st IEEE/ACM International Conference on Automated Software Engineering, IEEE, (2006), 59–68.

34.

Barus

A.C.

, Chen

T.Y.

, Kuo

F.-C.

, Liu

, Merkel

, Rothermel

, A cost-effective random testing method for programs with non-numeric inputs, IEEE Transactions on Computers, IEEE (2016), 1–14.

35.

Chen

T.Y.

, Kuo

F.-C.

, Liu

, Wong

W.E.

, Code coverage of adaptive random testing, IEEE Transactions on Reliability62(1) (2013), 226–237.

36.

Anand

, Burke

E.K.

, Chen

T.Y.

, Clark

, Cohen

M.B.

, Grieskamp

, Harman

, Harrold

M.J.

, McMinn

, An orchestrated survey of methodologies for automated software test case generation, Journal of Systems and Software86(8) (2013), 1978–2001.

37.

Chan

K.P.

, Chen

T.Y.

, Towey

, Restricted random testing: Adaptive random testing by exclusion, International Journal of Software Engineering and Knowledge Engineering16(04) (2006), 553–584.

38.

Chen

T.Y.

, Merkel

R.G.

, Eddy

, Wong

P.K.

, Adaptive random testing through dynamic partitioning, In 4th International Conference on Quality Software, IEEE (2004), 79–86.

39.

Chen

T.Y.

, Kuo

F.-C.

, Merkel

R.G.

, Ng

S.P.

, Mirror adaptive random testing, Information and Software Technology46(15) (2004), 1001–1010.

40.

Liu

, Xie

, Yang

, Lu

, Chen

T.Y.

, Adaptive random testing through test profiles, Software: Practice and Experience41(10) (2011), 1131–1154.

41.

Mayer

, Lattice-based adaptive random testing, In 20th IEEE/ACM international Conference on Automated Software Engineering, ACM (2005), 333–336.

42.

Shahbazi

, Tappenden

A.F.

, Miller

, Centroidal voronoi tessellations-a new approach to random testing, IEEE Transactions on Software Engineering39(2) (2013), 163–183.

43.

Tappenden

A.F.

, Miller

, A novel evolutionary approach for adaptive random testing, IEEE Transactions on Reliability58(4) (2009), 619–633.

44.

Chan

K.P.

, Chen

T.Y.

, Towey

, Restricted random testing, In 7th International Conference on Software Quality, Springer, London, UK, (2001), 321–330.

45.

Chen

T.Y.

, Kuo

F.-C.

, Merkel

R.G.

, On the statistical properties of the f-measure, In 4th International Conference on Quality Software (2004), 146–153.

46.

Levenshtein

V.I.

, Binary codes capable of correcting deletions, insertions, and reversals, In Doklady Akademii Nauk. SSSR, (1965), 845–848.

47.

Chan

K.P.

, Chen

T.Y.

, Towey

, Forgetting test cases, In 30th Annual International Computer Software and Applications Conference, IEEE, 1 (2006), 485–494.

48.

Jia

, Harman

, An analysis and survey of the development of mutation testing, IEEE Transactions on Software Engineering37(5) (2011), 649–678.

49.

Code-forge-free open source codes forge and sharing. URL: http://www.codeforge.com, (2013).

50.

Code-plex-open source project hosting. URL: http://www.codeplex.com, (2013).

51.

Codeproject - for those who code. URL: http://www.codeproject.com, (2013).

52.

“Github, where software is built,” URL: https://github.com, (2015).

53.

Derezinska

, Quality assessment of mutation operators dedicated for C# programs, In 2006 6th International Conference on Quality Software, IEEE, (2006), 227–234.

54.

d’Amorim

, Pacheco

, Xie

, Marinov

, Ernst

M.D.

, On the statistical properties of testing effectiveness measures, Journal of Systems and Software (2006), 591–601.