Modified Harris Hawks Optimization Based Test Case Prioritization for Software Testing

Manar Ahmed Hamza, Abdelzahir Abdelmaboud, Souad Larabi-Marie-Sainte,Haya Mesfer Alshahrani, Mesfer Al Duhayyim, Hamza Awad Ibrahim,Mohammed Rizwanullahand Ishfaq Yaseen

1Department of Computer and Self Development, Preparatory Year Deanship, Prince Sattam bin Abdulaziz University,AlKharj, 16278, Saudi Arabia

2Department of Information Systems, College of Science and Arts, King Khalid University, Mahayil Asir, 62529,Saudi Arabia

3Department of Computer Science, College of Computer and Information Sciences, Prince Sultan University,P.O.Box No.66833, Rafha Street, Riyadh, 11586, Saudi Arabia

4Department of Information Systems, College of Computer and Information Sciences, Princess Nourah bint Abdulrahman University, P.O.Box 84428, Riyadh, 11671, Saudi Arabia

5Department of Natural and Applied Sciences, College of Community-Aflaj, Prince Sattam bin Abdulaziz University,16278, Saudi Arabia

6College of Computer at Al-Gunfudah, Umm Al-Qura University, Al-Gunfudah, 24382, Saudi Arabia

Abstract: Generally, software testing is considered as a proficient technique to achieve improvement in quality and reliability of the software.But, the quality of test cases has a considerable influence on fault revealing capability of software testing activity.Test Case Prioritization (TCP) remains a challenging issue since prioritizing test cases is unsatisfactory in terms of Average Percentage of Faults Detected (APFD) and time spent upon execution results.TCP ismainly intended to design a collection of test cases that can accomplish early optimization using preferred characteristics.The studies conducted earlier focused on prioritizing the available test cases in accelerating fault detection rate during software testing.In this aspect, the current study designs a Modified Harris Hawks Optimization based TCP (MHHO-TCP) technique for software testing.The aim of the proposed MHHO-TCP technique is to maximize APFD and minimize the overall execution time.In addition,MHHO algorithm is designed to boost the exploration and exploitation abilities of conventional HHO algorithm.In order to validate the enhanced efficiency of MHHO-TCP technique, a wide range of simulations was conductedon different benchmark programs and the results were examined under several aspects.The experimental outcomes highlight the improved efficiency of MHHO-TCP technique over recent approaches under different measures.

Keywords: Software testing; harris hawks optimization; test case prioritization; apfd; execution time; metaheuristics

1 Introduction

The increasing importance of software testing adds significant value to the quality of software and indirectly towards social development and national economy.Inappropriately-developed and tested software might lead to serious issues, especially in issues concerning national security, etc., Further, it also brings high maintenance costs and huge amount of property loss [1].Software testing is considered as a significant process to assure the trustworthiness and consistency of a software.Particularly,Automated Software Testing (AST) can improve testing efficiency, shorten testing time, and greatly reduce the manual workforce in this domain.Over the last few years, AST has gained a considerable interest in the field of both academics and industry.In general, test data automatic generation is a challenging and key task in AST [2].A relevant test dataset can increase fault exposure probability and can efficiently reduce the testing execution time.In addition to these two problems discussed above, coverage ratio is a crucial index to estimate the quality of test dataset [3].In comparison with functional testing, structural testing is a cost-efficient process in fault detection of programs.So, this process is extensively studied and applied.

Current software testing methods aremostly used for deterministic programs [4].Indeed, there are several kinds of uncertainties experienced in real-time programs, for instance fuzziness/randomness,which suggest that the behaviour of these programs are not certain.Particularly, in case of a program with uncertainty and when a program is repeatedly run with a similar test data point, it might cover different statements or even different outputs, or sometimes traverse different paths too.In this scenario, prior test adequacy condition remains inappropriate.Now, the outcomes from few studies focused on testing a program with non-determinism.However, some of the studies focus on programs that is composed of randomness.Alternatively, the programs with randomness exist extensively in real-time applications like network software, game software, and Windows operating system [5].

Although software testing is recurrently performed, it is mostly performed in a hurried manner,owing to fixed resources and time constraints.As a result, it can be described that Test Case Prioritization (TCP) application can improve test feasibility from ST activity [6].But, the studies in literature employed prioritization on test cases that passed with test case selection.Two researchers namely, Harold and Rothermel evaluated the concept in a wide context and proposed a novel method.TCP is an NP-Hard problem since it needs to check each feasible permutation sequence.Similarly, the rapid expansion of software makes one to resort to metaheuristics optimization algorithm to resolve the problems within a certain period of time [7].Hence, the authors started looking into nature on how nature maintains an optimal balance.At present, several attempts are being made to find an optimum ordering through nature-inspired algorithm.

With this motivation, the current study designs a modified Harris Hawks Optimization-based TCP (MHHO-TCP) technique for software testing.The aim of the proposed MHHO-TCP technique is to maximize APFD and minimize the overall execution time.In addition, MHHO algorithm is also designed to boost both exploration and exploitation abilities of conventional HHO technique.The design of MHHO technique for TCP in software testing shows the novelty of current work.In order to validate the enhanced efficiency of MHHO-TCP technique, a wide range of simulations was conducted upon different benchmark programs and the results were investigated under several aspects.

Rest of the paper is arranged as follows.Section 2 briefs about related works, Section 3 introduces the proposed model, Section 4 discusses about performance validation, and Section 5 concludes the study.

2 Related Works

Spieker et al.[8] presented Retecs, a novel methodology to manually learn TCP and perform CI selection for the purpose of reducing round-trip time among developers’feedback on failed test cases and code commits.Retecs technique use RL algorithm for both selection and prioritization of test cases based on failure history, duration, and last implementation status.Panwar et al.[9] proposed CS and M-ACO algorithms to conclude the test cases in an enhanced order under time-constraint environments.Since this method is dependent on individual parameters, cuckoo search algorithm is preferred which is different from other optimization methods and is very effective and easy to perform.

Miranda et al.[10] presented the FAST family of TCP methods which radically changes the landscapes through borrowing algorithms, widely used in big data, to find relevant items.FAST technique provides scalable similarity-based TCP in white-box and black-box methods.The experimental results from practical Java and C subjects show that the fastest member of the family outperformed other black-box methods in terms of efficacy without considerable impact on efficiency.Further, it also outperformed white-box approach.Ali et al.[11] proposed a relevant solution and examined the prevailing problems towards regression testing in agile practices.The presented method has 2 stages while in initial phase, test case is prioritized through clustering while this test case changes frequently.If it is a tie, then the test case is prioritized according to their corresponding coverage criteria and failure frequencies.In the next phase, test cases with coverage criteria/high frequency of failure are elected.The presented method was authenticated through experimental research on three industrial subjects.

Hajjaji et al.[12] presented a similarity-based prioritization that is effectively employed on product samples.In this method, different products are gradually chosen based on the feature to be tested next, so as to increase the feature interaction coverage as soon as possible in product-wise testing.Xing et al.[13] adapted an advanced SI method—Artificial Fish School Algorithm to resolve the TCP problems.Particularly, the coding algorithm of artificial fish school was developed along with test case set; effective execution time and the average percentage of test-point coverage were chosen for optimization of strategies such as tail-chase, cluster, and forage behaviours of artificial fish school; the optimum solutions were attained through population iterations.

Gokilavani et al.[14] presented a multi-objective-based TCP and test case selection for distributed cloud platforms.Resemblance-Based Cluster Head (RBCH) method was presented in this study to select the CH based on total similarity among other test cases.Sivaji et al.[15] proposed a new African Buffalo-based Convolution Neural Slicing (AB-CNS) algorithm to reduce both resource and time consumption, when implementing regression testing.At first, the presented approach was implemented in test case minimalization task.It was prioritized using the FF of AB-CNS.Khalilian et al.[16] introduced an improved version of the methods discussed above in two ways.Firstly, the authors introduced a novel prioritization formula by gaining a variable coefficient as per the available historical efficiency data that act as feedback from previous test session.Next, a set of exhaustive research works has been carried out in the evaluation of system performances.

3 The Proposed Model

In this study, a novel MHHO-TCP technique is designed for TCP on software testing.The aim of the proposed MHHO-TCP technique is to maximize APFD and minimize the overall execution time.In addition, MHHO algorithm is designed to boost both exploration and exploitation abilities of conventional HHO algorithm.

3.1 Design of MHHO Algorithm

HHO is a metaheuristic technique and is applied as a competent solution to difficult issues.HHO is simulated by the attitude of Harris hawks, an intelligent bird.This species follows a process that empowers them to catch a prey, even there are chances for the prey to escape.Being a procedure modelled under mathematical process, it allows their computational execution.HHO has a stochastic technique which explores difficult search spaces for finding the optimum solution.The fundamental steps of HHO are attained under different conditions of energy.The exploration stage is inspired from the process where Harris’s hawk cannot track the prey exactly.The hawks arbitrarily perch at distinct places and wait for its prey utilizing two operators that are chosen on the fundamental of probabilityqas provided in Eq.(1), whereq＜0.5 implies that the hawks perch at the place of another population member and its prey (for instance, rabbit).Whenq≥0.5, the hawk is at arbitrary place nearby the population range.In order to facilitate the reason of HHO, a record of symbols utilized from this technique is determined as follows.

The exploration stage is determined as follows

The average place of HawksXmis demonstrated as given herewith

whereX(t) illustrates the places from iteration to all Hawks,tandNidentifies with the entire number of Hawks.The average place is attained by utilizing distinct techniques though this is the simplest rule.There is a need to achieve optimum transition from exploration to exploitation.At this point, shift is expected amongst the varying inspired exploitative performances that depend upon the escaping energy factor,Eof the prey that reduces dramatically in the escaping performance.

where,E0, andTimply the primary escape energy and the maximal amount of iterations correspondingly.

Soft besiege is a vital phase in HHO which can be demonstrated, whenr≥0.5and|E|≥0.5.In this condition, the rabbit has enough energy.If it follows, the rabbit carries out an arbitrarymisleading shift to escape.However, during the metaphor, it could not do so.Besiege stage is determined based on the subsequent rule.

where△X(t) signifies the variance place of the vector to every rabbit and current place from the iterationt,andJ= 2(1 -r5).The rabbits exhibit unplanned jumping capability throughout the escape stage.TheJvalue differs arbitrarily from all iterations to represent the performance of rabbit.In extreme siege phase, ifr≥0.5and|E|＜0.5.The prey becomes tired and does not possess escape strength anymore [17].During this analysis, the present place is modified as given herewith.

As in the performance of hawks from real life, it slowly performs an optimum dive towards the prey, when it is required to capture a particular prey under competitive conditions.

Soft besiege, projected from the preceding in Eq.(7), is carried out from progressive quick dive,onlyif|E|≥0.5 butr＜0.5.During this analysis, the rabbit possess sufficient energy to escape.So, it is implemented as a soft siege previously while the attack comes as a surprise.Fig.1 demonstrates the flowchart of HHO technique.

whereSstands for arbitrary vector sized 1×DandLFrepresents Levy Fight purpose which is utilized in Eq.(9):

Figure 1: Flowchart of HHO

Atthispoint,u,vrefer to arbitrary values amongst 0 and1,β signifies the default constant which is fixed at 1.5.The last phase from the procedure is to update the places of hawks based on the equations given below.

whereyandZrefer to the attained outputs utilized in Eqs.(7) and (8).

In this progressive fast dive,HHOrepresents the already hard-pressed one, where it occursif|E|＜0.5 andr＜0.5.At this point, the strength of rabbits to escape is insufficient.So, hard siege was proposed before many surprise attacks were made for catching as well as killing the prey.During this phase, the Hawks seek to reduce different distances between their prey and their average place.

The values ofyandZare presented with the help of novel rules in Eqs.(12) and (13), whereX(t)demonstrates the value attained, utilizing Eq.(2).

In literature [18], it is demonstrated that HHO outperformed many advanced techniques and it addresses many optimization problems.But, a new adapted MHHO method is presented in current research work to promote search efficiency of HHO so as to attain fast convergence speed, robustness,and better solution accuracy.It is not challenging to define the modifications inEwhich couldgenerate a major difference in simulation result.Thus, a novelEupgrading system is deployed in MHHO for promoting both exploitation and exploration abilities of HHO.The complete modifications made so far are given herewith.

Generally, two optimization approaches are followed in each metaheuristic algorithm such as exploitation and exploration.Exploration represents a global search in searching space; and exploitation represents the local optimum solution.From an algorithmic point of view,Eis a connection between exploitation and exploration.When |E|≥1, the Harris hawks adapt a global search method to search for prey.On the other hand, when |E|＞1, local searching model is employed to hunt the prey.Moreover, when |E|＜0.5,‘Hard besiege’strategy is performed; when 1≥|E|≥0.5,‘Soft besiege’system is elected by the hawks.The drawbacks of the originalEupgrade system are stated.

Based on the last value ofE1, under the approach 6, is not zero.In approach 6, after the iteration,consider that the prey must have energy to escape and so the performances of the model can be improved.In the next half of iteration, |E| could never be more than 1 in 1, 2, and 4 strategies.But,in the 1sthalf of the iteration, approach 4 is extremely exploratory, approach 1 follows, and the last is approach 2.

whereasE0represents an arbitrary value in the range of (-1,1);sinandcosrepresent sine and cosine functions, correspondingly [19].The amount of iterations is represented bytwhileTis the maximal amount of iterations.edenotes the base amount of exponential functions, and the value is around 2.71828.The major time complexity of MHHO and HHO is based on three methods namely, fitness evaluation, hawk updating, and random initialization.Thus, it is formulated as follows.

In which N represents the population size, T denotes the overall number of iterations and Dimension denotes the amount of decision parameters.

3.2 Application of MHHO Algorithm for TCP

Assume that there are five test cases to be prioritized while the possibility of having the optimal prioritized arrangement is (1/5!) factorials as shown in Fig.2.Every test case performs as firefly agents,when the distances among every test case represent the attractiveness functions amongst firefly agents.To identify the best-prioritized arrangement, the proposed method is utilized by string metrics as a FF.In this work, the real outcome of the distance estimated for every standard program is not demonstrated.Because, the amount of test cases and their corresponding content is too lengthy and huge in size to be sufficiently demonstrated.In fact, to demonstrate how distance is estimated in this study, five dummy test cases were generated.‘Edit distance’includes the evaluation of string characters, in which the quantified values represent the minimum number of replacements, insertions,and deletions to convert 1stinto 2ndstring.Edit distance is set to include only the least conversion of 1stinto 2ndstring.

Figure 2: Test cases

In TFIDF, term frequency, tf, first computation is initiated with the help of elected string/term frequency in a document.In other words, tf represents the number of terms t that exists within d document.While, the equation for inverse document frequency, idf handles the importance of terms in a pool of documents.Then, TFIDF is formulated as follows.

Inwhich: T=termfrequency in each document; t=termfrequency in one document;N=number of term that exist all over the documents; and nt = amount of documents has t term.These 2-string metrics are later utilized in the calculation of weight and distance of dummy test case table [20].TFIDF is a standout system among commonly-used term weighing systems in data retrieval methods.Based on this ability, TF-IDF is frequently used in research works.The weight amongst test cases is employed to assign brightness amongst firefly agents in MHHO-TCP.

The election of the next test case, in movement upgradation, depends on the weights of test cases that performas brightness over distances among the test case, in which themaximumvalue gets elected as the following move.In arithmetical equation, the brightness of test case on distance estimation is represented as follows.

As the weights of each dummy test case remains the same, the shortest distance is the only metric taken into account, because of the analogous weights of each dummy test case.But, in benchmark program/actual case study, the same weight problem reduces and the distance becomes heavily dynamic.Next the test case distance is evaluated by edit distance with the help of TFIDF string metrics.The total distance traveled denotes the prioritized test cases.The short distances of whole sequences of the test case are taken into account as the optimal distance.The optimal ones are chosen based on MHHO-TCP technique.

4 Experimental Validation

The proposed MHHO-TCP model was validated for its performance under different aspects and the results are discussed in this section.The results were investigated under varying iterations and benchmark functions namely, Gzip, Grep, TCAS, and CSTCAS.

Tab.1 and Fig.3 shows the results from detailed Average Percentage of Faults Detected (APFD)analysis accomplished by MHHO-TCP model against existing methods under Gzip benchmark function.The figure shows that Greedy technique accomplished a poor performance with least APFD values.Simultaneously, PSD technique gained somewhat improved APFD values.Moreover, LBS and FA techniques reached moderately closer APFD values.However, the proposed MHHO-TCP model outperformed existing techniques and achieved the maximum APFD values under all iterations.

Table 1: Results of the analysis of MHHO-TCP techniques in terms of APFD under Gzip dataset

Table 1: Continued

Tab.2 and Fig.4 shows the results achieved by the presented technique in a detailed APFD analysis against existing approaches under Grep benchmark function.The figure demonstrates that Greedy method accomplished the least performance with minimum APFD values.In addition,PSD technique gained slightly improved APFD values.Moreover, LBS and FA methods attained moderately closerAPFD values.However, the presented technique outperformed the existing methods with maximum APFD values under all iterations.

Fig.5 offer a detailed overview of the results from APFD analysis of MHHO-TCP model against existing methods under TCAS benchmark function.The figure shows that Greedy system accomplished the least performance with low APFD values.Also, PSD technique gained somewhat enhanced APFD values.Moreover, LBS and FA techniques reached moderately closer APFD values.However, the presented technique outperformed the existing techniques with maximum APFD values under all iterations.

Figure 3: APFD analysis of MHHO-TCP method under Gzip dataset

Table 2: Results of the analysis of MHHO-TCP techniques in terms of APFD under GREP dataset

Table 2: Continued

Figure 4: APFD analysis of MHHO-TCP method under Grep dataset

Figure 5: APFD analysis of MHHO-TCP method under TCAS dataset

Fig.6 shows the results achieved by MHHO-TCP model from a detailed APFD analysis conducted against existing methods under CS-TCAS benchmark function.The figure shows that Greedy technique accomplished a poor performancewith low APFD values.At the same time, PSD technique reached somewhat enhanced APFD values.Moreover, LBS and FA methods reached moderately closer APFD values.Finally, the presented technique outperformed all other existing techniques with the highest APFD values under all iterations.

Figure 6: APFD analysis of MHHO-TCP method under CS-TCAS dataset

Tab.3 and Fig.7 portrays the outcomes achieved byMHHO-TCP model in average execution time analysis against existing techniques under various benchmark functions.The results showcase that the proposedMHHO-TCP model achieved the least average execution time compared to other approaches under all benchmark functions.For instance, with GZIP benchmark function, MHHO-TCP model attained a low average execution time of 2.103 mts whereas Firefly, PSO, LBS, and Greedy techniques tookhigh average execution times suchas 3.053, 4.980, 2.960, and 3.637 respectively.At the sametime,with with GREP benchmark function, the presented technique attained a minimal average execution time of 2.693 mts, whereas Firefly, PSO, LBS, and Greedy techniques consumed high average execution times namely, 3.647, 5.677, 3.780, and 3.950 respectively.Moreover, with TCAS benchmark function, the proposed MHHO-TCP method achieved the least average execution time of 5.283 mts, whereas other techniques such as Firefly, PSO, LBS, and Greedy obtained the maximal average execution times such as6.460,13.293,6.627,and7.617correspondingly.Furthermore,with CS-TCASbenchmarkfunction,MHHO-TCP approach reached a lesser average execution time of 8.230 mts, whereas Firefly, PSO,LBS, and Greedy techniques accomplished superior average execution times namely, 9.627, 19.980,9.960, and 10.793 respectively.

An extensive mean APFD analysis was conducted between MHHO-TCP method and existing techniques and the results are shown in Tab.4 and Fig.8.The outcomes show that MHHO-TCP approach produced an effective outcome with increased mean APFD values.For instance, with Gzip benchmark function, MHHO-TCP model attained an increased mean APFD of 95.390, whereas firefly, PSO, LBS, and Greedy techniques resulted in reduced mean APFD of 95.004, 93.888, 94.414,and 93.046 respectively.Moreover, with CSTCAS benchmark function, the presented system attained a high mean APFD of 93.413, whereas firefly, PSO, LBS, and Greedy methodologies produced low mean APFD values such as 92.973, 92.571, 91.897, and 91.591 correspondingly.

Table 3: Execution time analysis results of MHHO-TCP technique against existing approaches

Figure 7: Average execution time analysis results of MHHO-TCP method

Table 4: Mean APFD analysis results of MHHO-TCP method against existing approaches

Figure 8: Mean APFD analysis results of MHHO-TCP method against existing approaches

5 Conclusion

In this study, a novel MHHO-TCP technique is designed for TCP on software testing.The aim of the proposed MHHO-TCP technique is to maximize APFD and minimize the overall execution time.In addition, MHHO algorithm is designed to boost both exploration and exploitation abilities of conventional HHO technique.The design of MHHO technique for TCP in software testing helps in achieving the maximum APFD and minimum execution time.In order to validate the enhanced efficiency of MHHO-TCP technique, a wide range of simulations was conducted upon different benchmark programs and the results were examined under several aspects.The experimental outcomes demonstrate the increased efficacy of MHHO-TCP technique against recent approaches under different measures.In future, HHO algorithm can be utilized replacing other metaheuristic algorithms to further boost the overall performance.

Acknowledgement:The authors would like to acknowledge the support of Prince Sultan University for paying the Article Processing Charges (APC) of this publication.

Funding Statement:The authors extend their appreciation to the Deanship of Scientific Research at King Khalid University for funding this work under Grant Number (RGP.1/127/42).Princess Nourah bint Abdulrahman University Researchers Supporting Project Number (PNURSP2022R237),Princess Nourah bint Abdulrahman University, Riyadh, Saudi Arabia.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.