| Software testing has been accepted as one of the most vital components of software engineering discipline and remains one of the most widely practiced and studied approaches for assessing and improving software quality.With painstaking efforts,through intricate abstractions,software engineers have integrated testing into every level of the software development valuechain.But regardless of all the efforts,“bugs” inadvertently “creep” into software leading to their ultimate failures.Numerous testing techniques have therefore been developed and used to boost the confidence of developers that software has certain qualities that meet various aspirations of stakeholders.Most of these techniques focus on strategies for selecting test cases.Efficient and effective test case generation has been a subject of both academic and industrial interest.Among the many contributions to this subject,random testing(RT)has been most successful and often preferred for its simplicity,flexibility,efficiency,ease of automation,etc.Recently,the effectiveness of RT has come under scrutiny by a growing body of researchers who have criticized it for failure to make use of any information to guide the testing process.The ineffectiveness conundrum is strongly connected to the philosophical underpinnings of RT.The philosophy of RT is founded on the premise that software usage and behavior cannot be predicted,hence test input for evaluating software quality should also be selected in an unpredictable way(randomly).Although this assertion is still true,various empirical observations have showed that more often,programmers are prone to making certain types of mistakes which leads to the crystallization of inputs which causes most programs to fail.The geometrical shapes and distribution of these failure causing inputs has been termed as failure patterns.Armed with this additional information,these researchers are driven by the intuition that,a slightly modified RT that evenly distribute test cases within the input domain of a program can take advantage of the likely presence of these failure patterns to significantly improve the failure detection capability of RT.These group of methods have collectively been classified as adaptive random testing(ART)methods.Therefore,ART systematically guides or filters randomly generated test cases to enhance even distribution,with the view to improving the effectiveness of RT.So far,the results have been very impressive but the mechanism for evenly spreading test cases has resulted in a very expensive overhead cost for ART.Software failures are still discovered faster in RT than ART methods and since most often the testing process is terminated as soon as failure is detected,many considers ART's advantage over RT as superficial;a major drawback to ART's success.Additionally,there have been research findings which have suggested that ART is very close to its theoretical optimum in terms of effectiveness.This has prompted proponents to intensify research over the years to improving the efficiency of ART whiles preserving its effectiveness objective.Despite the overhead setback,ART has offered a new insight to software testing and has provided a fresh impetus to make software usage safer and more reliable.This research makes some contribution to this course with a clear definition of a goal of minimizing the efficiency deficit incurred by ART.The main contributions of this thesis are as follows:1.A modified algorithm of fixed sized candidate set(FSCS)called FSCS with overlapping(FSCS-O)is proposed.FSCS test case selection involves two major processes;randomly selecting candidate(potential)test cases and a process of identifying the best candidate.The first stage is considered trivial,but in identifying the best candidate,FSCS is caught in a logical trap of evaluating every candidate by computing their distances to all the previously executed test cases.The selection criterion makes it logically impossible to improve upon the efficiency without compromising on effectiveness.In our approach,data mining strategy is utilized to gain additional information which led to definition of a new selection criterion called overlapping;a situation where the distance metric of the currently evaluated candidate is superior to the validated value of the most recently executed test case.It was established by analyzing the test suits of FSCS that overlapping condition occurs approximately 50% of the time during test case selection process.This gave a strong indication that using overlapping instead of the original “best candidate” criterion would provide a substantial overhead reduction of FSCS.The newly proposed method does not require the evaluation of every candidate.In the evaluation process,once an overlapping condition occurs,the search process for the best candidate is terminated.Results of simulations and experiments showed that FSCS-O reduces the computations of FSCS by as much as one-fourth without adversely affecting effectiveness.2.A relational memory selection(RMS)approach is presented as an overhead reduction strategy for ART.The overhead burden of ART is rooted in the continual bloating numbers of unsuccessful test cases.As the number of failed attempts at finding program fault increases,so does the burden of generating successive test cases.Therefore,using a subset instead of the entire set of executed test cases runs through almost all the overhead strategies of ART and holds a good promise to current research objectives.To this end,partitioning seems to be the most natural solution,but how can this be achieved effectively and efficiently? RMS relies on the exploitation and coordination of large number of partitions as a basis to achieve lower overhead cost.All the partitions are targeted simultaneously using only the corresponding subset of executed test cases within each partition for generating test cases.To execute the pool of the generated test cases while concurrently enforcing even-distribution,a two-level implementation of Adaptive Random Sequence(ARS)is proposed which considers both local and global diversity contents of the test cases spatially.Results from simulations and experiment shows that the proposed strategy maintains a good failure detection capability in high dimension like its predecessors(partitioning based methods)whiles significantly improving upon the efficiency of ordinary ART method.Its level of efficiency is also superior to the state-of-the-art overhead reduction strategy of ART.3.To further improve the efficiency of Mirror Adaptive Random Testing(MART),a forgetting strategy based on spatial information of already executed test cases,is implemented to reduce the complexity of MART from quadratic to a near-linear without negatively impacting on failure detection capabilities.MART is an overhead reduction strategy for ART.Theoretical analysis shows that,MART's advantage over ordinary ART is dependent on the number of mirror partitions implemented,but empirical evidence shows a contradiction.Implementing a larger number of mirror partitions does not always guarantee a more efficient utilization of testing resources.The evidence further suggests that MART's own strength also turns out to be its own weakness leaving the tester in a dilemma of implementing a lower or higher mirror scheme.Before the testing process begins,the tester is required to select a partitioning scheme which determines the number of partitions within each dimension of input domain.Unfortunately,there is a potential risk that a program's failure region may not have any relationship with one or more dimensions of the input domain leading to the generation of ineffective mirror test cases.The underlying cause of this problem has been diagnosed.The study takes the view that,anytime the tester partitions a dimension,the mirror partitions are allocated in such a way that no partition within the source domain shares a common range(on any dimension)with its corresponding mirror partitions.To do this,multiple numbers of partitions within the input domain are dedicated as source domain.Then through systematic elimination of linearly related partitions,the remaining partitions are logically assigned as mirror partitions to the source domains.This removes any potential risks of generating defective mirror test cases.4.Results from the previous studies gave a greater insight into the actual problem that confronts MART as a testing strategy.Diversity has been recognized as a well-grounded principle in almost every test case selection strategy.In this study,the problem of MART has been connected to diversity-related crisis.The mapping functions of MART have been identified as the major culprit.A pragmatic solution that inherits all the positive characteristics of MART but is unaffected by MARTs pitfalls is proposed.In this novel mirror testing strategy called Random Border Mirror Transform(RBMT),a diversity vector is arithmetically integrated into the displacement vectors of MART to generate mirror test cases which are unique in all dimensions.Firstly,virtual images of actual mirror partitions are created by defining a random border along each dimension of input domain for every mirror partition.This creates an exact replica pair of partitions within the original and the virtual mirror partitions.The image created by a test case using MART is then transformed(by the displacement vectors)into a virtual image after which the corresponding image pair within the original mirror domain is selected to generate the actual test case.An extensive simulation and experiment is performed using real-world programs to evaluate the proposed method.RBMT recorded a remarkable improvement over all the schemes of MART especially where failure unrelated parameters existed in programs.It also emerged that,even with the highest recommended scheme of MART,RBMT guarantees a stable effectiveness and efficiency in all the experiment programs under study.It is envisaged that this thesis will immensely contribute to bridging the inefficiency gap between ART and RT. |
PDF Full Text Request