Research On The Improvement Of Adaptive Random Testing Based On Restriction And Partition Strategies

A key objective of software testing is to find program errors that cause failure in software,at less cost.It requires the identification or generation of a series of test cases that can easily detect a fault with a few test executions as possible.One fundamental software testing technique is Random Testing(RT),which selects test cases according to a random distribution.RT has been popularly applied in many real-world applications to assess software reliability.Although RT has been widely employed due to its advantages,some researchers have criticized its effectiveness in detecting failure.Several researchers have proposed that an enhancement to the failure-detection effectiveness of RT is achieved if random test inputs are widely or evenly spread within the input domain.Attempts to improve the failure finding capability of the traditional RT and the viscerally high potential of evenly spread test cases in detecting a failure within software have led to the proposition of Adaptive Random Testing(ART).ART describes a family of RT-based testing methods that aim to find failures faster.ART takes advantage of the location information of previous non-failure finding test cases to evenly spread random test inputs.To further improve the traditional RT,several contributions to ART have been made over the years given that there are different ways to achieve the even spread of test cases.However,the overheads associated with ART‘s mechanism can be substantial and may outweigh the advantages of executing fewer tests.This has resulted in the proposition of several different ART methods with different strategies;which aim to considerably reduce the time complexity of ART,while maintaining or improving its high fault-detection capability.Additionally,new ART methods with improved effectiveness and efficiency are of the essence.The main work of this thesis is presented as follows.1.This thesis first explains the background and motivations behind the introduction of ART.The study classifies and reviews various proposed ART methods with a focus on their motivation and strategy and findings.The study also explores,contextualizes and reviews some of the existing researches on ART,with a focus on their development trends,and contributions.It also reviews the contributions to ART methods over the years.The review uses 109 ART papers in several journals,workshops,and conference proceedings.From the papers,five different ART research categories and 60 varying ART methods were identified.The study concludes that the field of ART is not yet matured,although it has a relatively large number of studies on its theory and varying methods;but rather one that is devising different strategies to make ART more costeffective and applicable in different test scenarios in order to impact on the industry.2.A new ART implementation that provides a computational cost reduction strategy is presented.The method called Candidate-Exclusion ART(CE-ART),reduces the high overhead of Fixed-Sized-Candidate-Set ART(FSCS-ART)by defining exclusion zones around all candidate test cases and restricting distance computations from each candidate to only previously executed test cases inside the candidate‘s exclusion zone.The approach then directly selects a candidate input as the next test case if it has empty exclusion zone.On the other hand,if all candidates have non-empty exclusion zones,the candidate that is farthest from its nearest previously executed test case is selected as the next test case.Experimental results have shown that the new ART method not only improves on RT but also provides failure-detection effectiveness similar to other ART methods,while significantly minimizing computation overhead.3.The study presents a new and innovative ART implementation,which explores the advantages of repeated geometric bisection of the input domain combined with restricted regions to evenly spread test inputs.The method,called ART by Orthogonal Recursive Bisection with Restriction(ART-ORB),integrates both partition and exclusion strategies.The method sequentially bisects the largest region within the entire input domain into further sub-regions.It selects test inputs randomly from outside of a restricted zone in the largest region.Whenever two previously executed tests are found within the largest region,the method partitions the region geometrically by splitting the largest dimension of the region,through the midpoint of the previously executed tests(in that region).Experimental results have shown better performance in terms of fewer test executions than RT to find failures.Compared with other ART methods,the method has shown comparable performance(in terms of required test executions),but incurs lower test input selection overheads,especially in higher dimensional input space.The study concludes that the method is preferable especially in testing situations involving expensive test input execution.4.Another innovative ART method referred to as ART by Orthogonal Recursive Bisection with Imaginary Offsets(ART-ORBO)is introduced,which also employs repeated geometric bisection of the input domain but integrated with a concept of Imaginary Offsets.The method combines the advantages of two ART method variants: FSCS-ART and ART by Bisection(ARTB),to enhance the spread of test cases and reduce computational overhead.The method orthogonally partitions regions of the input domain to enhance the even spread of test cases,and employs a concept of imaginary offsets to further limit the possibility of test cases being close to each other.The approach generates a set of random test candidates within the largest sub-domain and defines the imaginary offset around this largest sub-domain.It then selects as the next test case,the candidate that is farthest from only the previously executed test cases that are found within the region and within the imaginary offsets region.Empirical results have shown that the method outperforms RT and provides better failure detection effectiveness that is comparable to other ART methods and has significantly improved efficiency,especially in high dimensional input domains.The study concludes that the method should always be used in place of RT,especially when the cost of executing test inputs is high.It can also be a good substitute for a testing situation where other ART methods are required.In summary,this thesis provides major contributions to the theoretical background of ART,and introduces three innovative ART variants that employ restriction and partition strategies to improve the ART technique.