 Open Access
 Total Downloads : 164
 Authors : Karthika Surendran, Syama. R
 Paper ID : IJERTV3IS041131
 Volume & Issue : Volume 03, Issue 04 (April 2014)
 Published (First Online): 19042014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
A Comparative Study on Various Approaches to Anti Random Testing
Karthika Surendran[1]
Computer Science and Engineering SCTCE
Trivandrum, Kerala, India
AbstractThe testing phase is of always primary concern to the programmers. It is not just because it takes maximum time, cost and effort but also because that it helps in identifying unrevealed errors in the software. Hence this area is of great interest to researchers. Over the years many techniques and approaches have been found to do the testing phase of the software. The two basic strategies of testing are whitebox and blackbox testing methods. This work mainly focuses on the five various anti random techniques, which is a blackbox testing and an overview on the random testing is also made. This work is done as a comparative study of these five techniques. It has been recognized that the anti random testing can be applied to objectoriented software also. Hence a study on it is also done in the paper. The paper explains the different software failure input patterns and establishes the comparison work based on the study of the response of the testing methods to these patterns.
Keywords Anti random testing, various approaches to anti random testing, comparison of anti random testing techniques, a type of blackbox testing

INTRODUCTION
Software testing is the phase in the software development process that aims at revealing all the unrevealed errors of the software so that these errors can be corrected. It is the last phase in the software development process. This phase mainly focuses on generating the test cases and also executing these test cases for validating the behaviour of the software system. Hence it is very much evident that quality of the test case can affect the quality of the software testing. This phase consumes maximum cost, effort and money during the software development process. The two basic methods of software testing are blackbox and whitebox testing. Whitebox testing, also called clear box, glassbox, transparentbox and structural testing actually tests the internal structure and the working of the software. It is usually done at unit, integration, system levels of the process. Blackbox testing, also called functional, behavioral, requirements and closedbox testing actually tests the functionality of the software. It is usually done at unit, integration, system and acceptance levels of the process. Random testing (RT) is a type of blackbox testing which is efficient and is well used in industries. This technique is well explained in section III. However this technique has disadvantages.
Syama. R[2]
Computer Science and Engineering Assistant Professor
SCTCE
Trivandrum, Kerala, India
Hence its improved technique called Anti Random Testing (ART) was developed over the years. The general ART algorithm is explained in detail in section III. This work mainly focuses on the ART. The various five approaches to Anti Random testing are studied in detail in this work. The five techniques of RT are explained in detail in section III. The first technique studied is Markov Chain Monte Carlo method (MCMCRT) [1], which makes use of the Bayesian inference for generating random test cases. The second method discussed is Fixed Size Candidate Set (FCFSART) [2], which uses the distance between test cases and candidate set to find the next test case. The third method explained is Restricted Adaptive Random Testing by Random Partitioning (ART RP Res) [3], which makes use of the principle of restriction to find the next test case. The fourth method is Adaptive Random Testing Based On Two Point Partitioning (ARTTPP) [4], which uses two points partitioning to generate the next test data. It is also found that ART can be used in the objectoriented cases also. The fifth technique is Feedback Directed Random Test Generation (RT fd) [5], which can be applied to object oriented programs. A comparison of these five techniques is shown in section IV. The comparison of the techniques is done based on the different types of inputs and the failure causing inputs which are explained in detail in section II. The work is concluded in section V with the inference obtained from the comparison made.

SOFTWARE FAILURE PATTERNS
The inputs that are failure causing can be plotted together and it is found that this can form any of the three following patterns:1) block failure pattern: the inputs that cause failure are within a specified area. This kind of block may be found in the statement block under a compound predicate according to the program code perspective. The example is for a fault in the branch such as if(a<=x && x<=b && c<=y && y<=d) , the failure causing input area can be denoted as {(a,b),(c,d)} (shown in fig.1), 2) strip failure pattern: the inputs may form the shape of a narrow strip pattern and may be predicate faults in a branch. For example if a programmer writes if (x+y>=k2) instead of if(x+y>=k1) the failure causing inputs will lie in a strip and the width can be calculated by k1k2 (shown in fig.2) and
3) point pattern: the failure causing inputs may scatter into some points or small areas within the whole input domain. These faults can be found in branch with modulo operation or bitwise operation. For example some statements in a
branch if(x%10==0 && y%10==0) belongs to this category of failure causing inputs (shown in fig.3).
Fig.1. Block pattern
selecting it from the input domain and then execute it. If no failure is revealed then add the executed test case to the empty set or else stop. In the third step generate new test cases based on the executed set of test cases. In the fourth step execute the test case generated in the third step and if no failure is revealed then add it to the set of test cases and perform the third step or else stop.
The random testing technique has various advantages like simplicity, high speed easiness in understanding, complete automation possible, cost effectiveness and so on. However applying it on the software some drawbacks are also been found. These drawbacks includes inefficiency, need for large test cases , using only the rate of failure causing inputs to compute the effectiveness [9], empirical knowledge is not addressed and so on.
Fig.2. Strip pattern
Fig.3. Point pattern
The percentage of the failure causing
inputs is defined by failure rate and is denoted by . For a finite sized input domain with m failure causing inputs, = m/d. The F – measure denotes the (random) number of test cases needed to detect the first failure. This is a natural measure for a testing strategy performance as it stops when the first failure is detected. The Fmeasure is used in all Adaptive Random Testingcases and hence it is ideal for comparison purposes. The theoretical mean F measure can be calculated by 1/. For example, in the case of failure rate
0.01 the theoretical mean F measure is equal to 100, which means that a failure will occur only after the execution of 100 test cases on average. The relative F measure of a method is the F measure of this method related to the theoretical mean F measure of Random Testing, i.e. 1/. If the mean F measure of a method is no worse than Random Testing then its relative mean F measure should be below or atmost 1. The relative mean F measure has the advantage that it is independent of failure rates and hence can be easily compared for different failure rates [3],[4],[12].

BACKGROUND
The random testing (RT) approach executes the testing procss of the software by randomly generating independent test cases. The general RT technique can be explained with the algorithm that consists of the following steps[1]. In the first step, set an executed set to be empty. In the second step generate an initial test case by randomly
Hence a new technique is developed and studied by Chen et al. [7] in 2004 to overcome the limitations of the random testing approach [6]. This technique is called the anti random testing (ART). It spreads the test cases to the maximum level possible. The executed set (set of distinct executed test cases that have not revealed any failures) and the candidate set (set of randomly selected test cases without replacement) are the two disjoint sets of test cases used in ART. Initially the executed set is taken empty. The first test case is generated by randomly selecting from the input domain. Until a failure is revealed the executed set will be incrementally updated with the chosen element from the candidate set. The farthest element in the candidate set from all the executed test cases is computed and it becomes the next test case [12]. Basically the ART can be again on the whole classified into categories: distancebased strategy and partitioningbased strategy [4]. The pseudocode of ART is as follows:
Z={}
add random test case to Z and execute it repeat until stopping criteria is satisfied sample set W of random test cases
for each w of these W test cases
w.minD = min(dist(w,z Z))
execute and add to Z the w with maximum minD [6]

ANTI RANDOM TESTING APPROACHES
The anti random testing can be classified into various methods, based on the techniques used in each method to randomly generate the test cases. These methods are explained in this section.

MARKOV CHAIN MONTE CARLO METHOD
(MCMCRT)
The earlier MCMCRT scheme had a disadvantage that it cannot be used for continuous inputs. Hence it could not be practically used with floatingpoint arguments that can be float and double. A new MCMCRT technique was eventually developed from this method [1].
The new method makes use of the distance between the points. The new method makes use of probability mass or density function to generate samples. The posterior distributions in Bayesian inference are effectively used to generate these samples. These samples are used in the method to handle the parameters. There are several sample generation techniques and one such effective technique is Metropolis Hastings (MH) algorithm. The acceptance probability of the candidate and a random number determines whether the selected candidate should be added to the set of test cases or not. The steps of the MCMCRT1 algorithm are as follows:

An initial test case is generated by random selection from the input domain.

A new candidate is generated according to the proposal distribution.

If the acceptance probability is less than a random number then the new candidate is not accepted as a test case or else the candidate is added to the set of generated test cases.

Steps 2 and 3 are repeated for a fixed number of iterations and the generated test case is returned as the result.
This algorithm takes large computation time because the steps 2 and 3 have to be repeated. This problem is solved in MCMCRT2 by replacing the proposal distribution.
The drawback of the MCMCRT1 is that steps 2 and 3 have to be repeated and this contributes to large computation time. To improve the situation the proposal distribution is replaced with the random walk process. The implementation of MCMCRT2 is explained below.
The steps of the MCMCRT2 algorithm are as follows:

A candidate is generated by random selection from the input domain.

If the acceptance probability is less than a random number step 1 is executed or else the generated candidate is accepted as the new test case.
MCMCRT1 technique uses the iterative technique, which is a drawback of that method. Hence to improve the working the repetition of this technique is discarded and a new technique is hence developed, which forms the MCMCRT2 method. MCMCRT2 can be explained similar to MCMCRT1 but without the repetition of steps. MCMCRT2 technique is found to be faster as it does not involve the iteration step of MH algorithm as in MCMCRT1.


FIXED SIZE CANDIDATE SET ADAPTIVE RANDOM TESTING (FCFSART)
This is the first proposed ART method [2]. In this method a few candidates (one of which will eventually become the new test case) are randomly generated, say k candidates are generated randomly. For each candidate in the candidate list the test case that is previously executed and is closest to it is located and the distance between them
are also calculated. The candidate with the largest such distance will become the next test case. This whole process will be repeated till the stopping condition is reached. The stopping condition is either the exhaustion of testing resources or the detection of potential failures.
The following figures explain the working of this algorithm. The four previously executed test cases are denoted by t1 to t4 and let c1 to c3 be the set of randomly generated candidates (value of k is taken as 3) from which one will be selected as the next test case. These test cases and candidates are shown in the fig.4. The fig.5 shows that the nearest previously executed test case of each candidate is found out and also that the distance between them is determined. These distances are compared in fig.6 and the candidate with largest such distance is selected as the next test case in fig.7. This process continues till the stopping condition is reached.
Fig.4. Multiple candidates are randomly selected
Fig.5. Nearest previously executed test case to each candidate is determined
Fig.6. These nearest distances are compared along all candidates
Fig.7. The candidate with longest such distance is selected

RESTRICTED ADAPTIVE RANDOM TESTING(ARTRP Res)
The method of ART by Random Partitioning was proposed by Chen et al. [8]. In
this method initially the whole input region is considered as the initial region and a test case is selected from it. Then the test case inclusive region is divided into four sub regions. The next test case is randomly selected from the maxarea region of these subregions. This process continues till the stopping condition is reached. This method is simple and have nearly linear runtime and with this method automation of Random Testing is also feasible and this method measures better Fvalue. But along with these advantages this method is also found to have a disadvantage that in all cases it cannot generate test cases widely and hence cannot avoid closely located test cases in all the situations.
Hence a new technique which includes the principle of restriction is developed [3]. The newly developed technique achieves minimum distance between the inputs by selecting test cases from restricted areas and hence avoids nearby and consecutive test cases. This method also requires only few test cases for its working.
The new method is similar to the old method developed by Chen but the difference is that this new method selects the next test case randomly only from the restricted version of the region with maxarea. The region with the largest area is always subdivided and among these subregions the region with maximum area becomes the next region from which the next case is randomly selected from its restricted version. This process continues till the stopping condition is reached. The stopping condition is either a failure is detected or the testing resources exhausts. The steps of the algorithm are as follows:

Initialize the candidate list of the test region with
{{(xmin,ymin)(xmax,ymax)}}.

Select the test region with maximal area from the candidate list and remove it. If there are everal such regions then one of them should be chosen randomly.

A point should be randomly selected from within the new restricted test region.

If the randomly selected point in step 3 is a failure causing input then it should be reported and the process is to be terminated.

Else the current test region should be divided into four test regions and should be added to the candidate list.

Unless the resources for testing are exhausted proceed with step 2.
The following figures explain the working of this algorithm. Initially the method starts with the whole input region as the initial region (it is shown in fig.8). Fig.9 shows that the whole region is divided with respect to this point. Fig.10 and fig.11 shows that from among the sub regions the region with maxarea is selected and it is from the restricted version of this sub region that the next test case is randomly selected. This process is continued until the stopping criterion has been reached.
Fig.8. First test case selection
Fig.9. First partitioning
Fig.10. Second test case generation
Fig.11. Second partitioning
However the key issue of this method is that it needs a test oracle, the software that can evaluate the outputs and decides pass or fail.


ADAPTIVE RANDOM TESTING BASED ON TWO POINT PARTITIONING(ARTTPP)
It is possible in the traditional adaptive random testing partitioning approaches for the two sampled test inputs to get very close to each other. Hence such a test case generation technique based on two points partitioning is proposed [4]. Basically the current region with the maximum area is selected as the object for partitioning and the partitioning is done at the midpoint of the two selected points. Initially a test point is randomly generated in the region. The second point is then selected from a set of candidates according to the criterion of farthest distance. This procedure of partitioning is
repeated until the stopping condition is reached. The stopping condition is till either the potential faults are reached or the size of set of test data reaches a preset limit. The steps of the algorithm are as follows:

Add the whole input domain into the region list and initialize the set of data set as .

Select the region with maximum area from the region list and remove it from the region list.

A new input point is to be randomly generated in this region if there are no previous test inputs in the max area region and also it should be added to the set of data set or else step 4 is done.

Let the existing test input in the maxarea region be denoted by Ti and generate k candidate points in the maxarea region. Calculate the distance between Ti and each of the candidate point. Select the farthest point from Ti as the second test case (denoted as Ti+1) in the maxarea region. Add this new test case to the set of test cases.

When a new test case is generated in the steps 3 and 4 and is added to the set of test cases it should be validated whether it can hit the failurecausing region or not. If it is true then the process is terminated or else the process is continued to append other test inputs.

The midpoint of the corresponding points of Ti and Ti+1 is computed. The current maxarea region is subdivided into four regions via this midpoint. These sub regions are then added to the list of regions. Continue with step 2.
Fig. 12 explains the operation of the algorithm in detail.
Fig.12. Illustration of twopoint partitioning strategy


FEEDBACK DIRECTED RANDOM TEST
GENERATION (RTfd)
As the result of researches done in the anti random technique it was found this technique can be used for objectoriented programs also [5]. The algorithm uses earlier computed values as inputs to randomly select a method or constructor and hence generate test cases. This technique has got its name as it uses feedback from a test case to generate the next test case. If a test case is found to be error generating then it is unnecessary to build new test cases on it. Hence new test cases will be built only on test cases that are error free. The basic steps of the algorithm includes declaration of error sequences and non error sequences, creating new sequences, discarding duplicates, executing new sequences and checking contracts, classifying new sequences and outputs and if the condition is violated then it is error sequence else is non error sequence and apply filters. The technique includes steps such as: 1). Method sequences 2). Extending sequences 3).Feedbackdirected generation 4).Filtering and 5).Repetition. The algorithm is as follows: GenerateSequences(classes, contracts, filters, timeLimit)

errorSeqs {} // Their execution violates a contract.

nonErrorSeqs {} // Their execution violates no contract.

while timeLimit not reached do

// Create new sequence.

m(T1 Tk) randomPublicMethod(classes) 6seqs,valsrandomSeqsAndVals(nonErrorSe qs; T1
Tk)

newSeq extend(m,seqs,vals)

// Discard duplicates.

if newSeq nonErrorSeqs U errorSeqs then

continue

end if

// Execute new sequence and check contracts.

~o,violated execute(newSeq,contracts)

// Classify new sequence and outputs.

if violated = true then

errorSeqs errorSeqs U {newSeq}

else

nonErrorSeqs nonErrorSeqs U {newSeq}

setExtensibleFlags (newSeq, filters; ~o) // Apply filters.

end if

end while

return nonErrorSeqs,errorSeqs [5]



COMPARISON
MCMC method can be concluded as a better option than ART and RRT; uses information on location of failures; has improved computation time and Fvalue; works also for discrete input; but has higher overhead value than RT.
ARTTPP is costbenefit and has better performance and is best for block pattern but do not work in linear runtime. ART RP Res is also simple, faster and effective and needs only lesser no: of test cases and works best for all the three patterns but works only for rectangular input domains and needs test oracle for test efficient execution.
RTfd is a better method and can work without user inputs when implemented in RADOOP but only for Object Oriented Programming.
The results of the comparison done are shown in the table 1.
Table 1. Comparison table of output for each failure pattern
FAILURE PATTERN
INFERENCE
Point
ARTTPP is suitable
Strip
MCMCRT is suitable and when is 0.005 ARTTPP is best and RP is worst and when is 0.01 TPP is worst
Block
ARTTPP is better for all values of and MCMCRT is also suitable

CONCLUSION
Testing is the last yet important phase of the software development process. The testing has two main strategies black box testing and white box testing. This work mainly focuses on the various adaptive random testing techniques, which falls under the category of black box testing. An overview of random testing is done initially. The general idea of adaptive random testing is explained. The work also includes a study on various failure input patterns to the software and the Fmeasure that can be used to express the performance of the different testing methods. The various adaptive random testing techniques are explained in the work. These techniques are not only studied but also compared according to their effectiveness
of the performance. The application of adaptive random testing to objectoriented programs is also discussed in the work. The paper cncludes
with the inference derived from the comparative study on these techniques.

REFERENCES

Bo Zhou, Hiroyuki Okamura, Tadashi Dohi, Enhancing Performance of Random Testing through Markov Chain Monte Carlo Methods, IEEE Trans. Computers, vol. 62, no. 1, pp. 186 192, January 2013.

Tsong Yueh Chen, FeiChing Kuo, Robert G. Merkel, T.H. Tse, Adaptive Random Testing: the ART of Test Case Diversity, J. Systems and Software, vol. 83, no. 1, pp. 6066, 2010.

Johannes Mayer, Restricted Adaptive Random Testing by Random Partitioning, 2012.

Chengying Mao, Adptive Random Testing Based on TwoPoint Partitioning, Informatica 36, pp. 297303, 2012.

Carlos Pacheo, Shuvendu K. Lahiri, Michael D. Ernst, Thomas Ball, Feedbackdirected Random Test Generation, 2012.

Andrea Arcuri, Lionel Briand, Adaptive Random Testing: An Illusion of Effectiveness, 2012.

T.Y. Chen, H. Leung, and I. K. Mak, Adaptive Random Testing In Advances in Computer Science, pp. 320329, 2004.

T. Y Chen, G. Reddy, R. Merkel, and P. K. Wong, Adaptive random testing through dynamic partitioning, In Proceedings of the 4th International Conference on Quality Software (QSIC 2004), IEEE Computer Society, pp. 7986, September 2004.