 Open Access
 Authors : Najneen
 Paper ID : IJERTCONV9IS04021
 Volume & Issue : NREST – 2021 (Volume 09 – Issue 04)
 Published (First Online): 10032021
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Rafi: Parallel Dynamic TestSuite Reduction for Software
Najneen
Rajasthan Technical University Kota, Rajasthan
Abstract: A trend in software testing is reducing the size of a test suite while preserving its overall quality. For software, requirements and a set of test cases are given. Each test case is covering some requirements. In this paper, our goal is to find the method for testsuite reduction (TSR) to calculate the minimal subset of test cases that cover all the requirements across versions. While this problem has gained significant attention, it is still difficult to find the smallest subset of test cases and widely used methods to solve this problem with only approximate solutions. In this paper, our goal is to find the greedy method for testsuite reduction (TSR) to calculate the minimal subset of test cases that cover all the requirements across versions. There are already existing exponentialtime algorithms and greedy algorithms to find the TRS in a versionspecific and across versions. We proposed a new parallel greedy heuristic method RAFI to find minimal test sets in across versions. Our approach shows that: (i) RAFI is much faster than the exponential time algorithms and approximately 1000x time faster than the traditional greedy method. (ii) RAFI method achieves roughly the same reduction rate compared to the traditional greedy method
Keywords: TestSuite Reduction, Traditional Greedy, Traditional Greedy parallel, TestCoverage graph, Dynamic Reduction, Flower, RAFI, Reduced test set.
1 INTRODUCTION
We can testify the quality of software products is a massive problem for the software industry, and software failure is a significant loss for a software company. Software testing is an essential technique for software quality solace, and it is a challenging but necessary process of growth information technology. If we increase software size, then we increase the number of test cases, and automatically cost will be increased. If we design software test cases, then we have to fulfill the demand of the software quality. So a cardinal set of the test cases is redundancy. We are selecting a minimum cardinal subset for selecting a test case of requirements. Test Suite Reduction(TSR) [3 – 5] can solve the problem of the condition and decrease the activity load, so automatically reduce the cost of software testing. Test Suite Reduction[6 – 8] comes under regression testing [1, 2]. In this paper, we can satisfy how we select a minimum number of test cases and fulfill all the requirements. It is the key to this topic test casereduction.
Next, every software has some defect, less feature and some BUGs, So we are releasing the new version of software with BUG fix or additional feature. Before releasing the feature again we have to test our software for quality and correctness purposes. For this, the normal way is again to find the minimal test set to execute our software. Then it will become more costly to again find the reduced test set. In this paper we propose a RAFI method to find the reduced test set across the versions by using the information of added features and previous versions reduced test set.
Now we will understand what the test suite reduction problem is? We will define the test suite reduction problem [10, 11] as:

If T = {r1, r2, r3, r4, r5, …… rn} are the requirements of the software.

If R = {t1, t2, t3, t4, t5,…… tn} are the test cases of software.

If S = {(t,r)} R is the relationship between test cases and the requirements.
Each requirement is covered by some test cases and each test case will cover some requirements. In the example (see Fig. 1), * indicates that there is a relationship between the corresponding requirement and the test case [9]. The above notation we can say the array representation of the coverage graph. Coverage Graph is the graph which will show the relationship between the test cases and the requirements. We can also represent this relation by bipartite graphs [11 – 13].
Fig. 1. Test Cases Cover the Requirements
In the above, there are a lot of test cases which are covering all the requirements. For example {t1, t2, t4, t5}, {t1, t2, t4}, etc. But we observe that the second subset is minimal than the first one. So we can say that subset
{t1, t2, t4} is the minimal subset which is covering all the requirements. In this t1 is covering {r1,r3}, t2 is covering
{r2, r4, r5, r8} and t3 is covering {r3, r5, r7}. So, we can say that {t1, t2, t4} is covering all the requirements and hence the reduced test set. There are many approaches for TSR, some are exponential and some are polynomialtimeapproaches.
2 BACKGROUND AND RELATED WORK
In this section, we talked about some existing methods of implementing Test Suite Reduction techniques. For some of them are, Flower method and the Traditional greedy method.

Exponential Time Algorithms
There are so many algorithms for Test Suite reduction whose time complexity is exponential and giving the exact result, Flower method is one of the methods.
FLOWER Method
Flower method [14] comes under the exact approach. We can get the optimal solution by using this method. In this method, we solve a problem as a flow network [15] and use the Ford Fulkerson algorithm [15]. The flower method represents a flow network where every edge has a capacity. Also, given two vertices source S and sink D, in the graph, find out the maximum possible flow from S to D. Flow on edge doesnt exceed the given capacity of the edge. Inflow is equal to outflow for every vertex except S to D. time complexity of this algorithm is exponential which is equal to O((2^test cases)*edges *
requirements) which seems an exponential time approach. This Flower method is an integer linear programming (ILP) [16 – 18]

Polynomial Time Algorithms
There are so many algorithms for Test Suite reduction whose time complexity is polynomial and giving the approximate result, traditional greedy method is one of the methods.
Tradition greedy method
Traditional greedy [19] is a heuristic approach to find the reduced test set that covers all requirements. In this, we will not get the exact result that we are expecting but we can get the approximate solution for this. In this approach, we iteratively select a test case that will cover all the maximum number of remaining requirements. We performed this iteratively until all requirements got not covered. A traditional Greedy method is a heuristic approach, so time complexity is polynomial. Its time complexity depends on the number of requirements, the number of test cases, and the relationship between the test case and requirements. Time complexity of Basic Greedy method is O(r * t * minimum(r, t)) where t is the number of test cases and r is the number of requirements.

OUR APPROACH: RAFI SEQUENTIAL METHOD
In every software we are releasing the new version of that software. So before releasing the new version of that software, that software must pass all the test cases for the quality purpose. Due to the new version of software our old coverage got changed. Some edges can be added or deleted. If the edges are added then we can say that some test cases are now covering the more requirements and if edges got deleted then we can say that some tests are not covering the requirement which they previously covered. Now we have to find the reduced test set in the new coverage graph. In this section, we Implemented the RAFI method to find the Reduced test set in the new Coverage graph. In the RAFI mthod we are using some information and those informations are 1) a reduced test set of the old coverage graph 2) edges got modified (added and deleted).
There are two types of edge modification in the old coverage graph.

Edge deletion

Edge addition

In this we will see how we are handling the edge modification to find the reduced test set and how we are taking the advantage of the old reduced test set.

Handel edge deletion:
There are two type of edge deletion are possible

Deleted edge belongs to old reduced test set

Deleted edge not belongs to old reduced test set
Deleted edge belongs to old reduced test set
Below graph shows an example of edge deletion which belongs to the old reduced test set. When we ran the old coverage graph in a traditional greedy method then we found that the reduced test was {t1, t2}. After deletion of the edge {t1, r1}. We found that t1 belongs to the old reduced test set and r1 is now uncovered by the old reduced test set so we have to cover the r1. For this first we will check whether r1 is covered by the current old reduced test set or not. In the below example r1 is not covered by any selected test case {t1, t2} so we will add a test case which will cover this r1 requirement, because t3 is covering the r1 requirement so added this t3 test case in the old reduced test case now reduced test case will become {t1, t2, and t3}. Now we try to optimize the reduced test set. We had added the t3 test case because t1 is not covering the r1 so we try to cover all requirements without the presence of t1 test case in the new reduced test set. In this case we can cover all the requirements by {t2 , t3}. So new reduced test set will be {t2 and t3}
Fig. 2. new coverage graph after after deletion {t1, r1} edge
Deleted edge not belongs to old reduced test set
Below graph shows an example of edge deletion which does not belong to the old reduced test set. When we ran the old coverage graph in a traditional greedy method then we found that the reduced test was {t1, t2}. Now we deleted the edge {t3, r1}. We know that t1 does not belong to the old reduced test set. We found that r1 still got covered by the old reduced test set so nothing will be affected. The new reduced test set will be {t2 and t3} as the old reducedtest set.
Fig. 3. new coverage graph after after deletion {t3, r1} edge
Algorithm
Reduced test set as ReducedSet ;Delete the edge as DeletedEdge;
delete DeletedEdge from CoverageGraph ;
if DeletedEdge belongs in TestCase(t1) which is in ReducedSet thennothing to do for DeletedEdge ;
else if DeletedEdge belongs in Requirement(r1) which iscovered by TestCase(ti) which is in ReducedSet then nothing to do for DeletedEdge ;
else
Add one TestCases which satisfy that Requirement(r1);end
if all requirements that covered by TestCase(t1)canbe covered by ReducedSet – { TestCase(t1) } then
ReducedSet = ReducedSet – { TestCase(t1) } ;end
end
return Reduced test set as ReducedSet ;
Line1 In the ReducedSet set we will store the final reduced test set. Line2 deleted edge we store the test case and the requirement relationship. Line45 If the deleted edge does not belong to the reduced test set then we will do nothing. Line67
If the deleted edge belongs to the reduced test set and r1 is still covered by another test case which belongs to the reduced test set then we will do nothing. Line9 If not then we will add the test case which covered r1. Line 11 12 if all requirements which are covered by t1, get covered by the current reduced test set except t1 then we can remove t1 form the reduced test set. Line15 return reduced test set.


Handel edge addition:
There are two type of edge addition are possible

Added edge belongs to old reduced test set

Added edge not belongs to old reduced test set
Added edge belongs to old reduced test set
Below graph shows an example of edge addition which belongs to the old reduced test set. When we ran the old coverage graph in a traditional greedy method then we found that the reduced test was {t1, t2}. After addition of the edge {t2, r1}. We found that t2 belongs to the old reduced test set and r1 is now covered by the other test case which belongs to the old reduced test set so try to optimize the reduced test set. For this first we will check the cardinality of the test case which was covering the r1. If that cardinality is one then we can remove that test case form the old reduced test set. In the below example the cardinality of t1 is one so we will remove the t1 form the old reduced test set. In this case we can cover all the requirements by {t3} only. So new reduced test set will be {t3}
Fig. 4. new coverage graph after after adding {t2, r1} edge
Added edge not belongs to old reduced test set
Below graph shows an example of edge addition which does not belong to the old reduced test set. When we ran the old coverage graph in a traditional greedy method then we found that the reduced test was {t1, t2}. Now we added the edge {t3, r2}. We know that t3 does not belong to the old reduced test set. We found that r1 is not covered by another test case which belongs to the old reduced test set so nothing will be affected. The new reduced test set will be {t2 and t3} as the old reduced test set.
Algorithm
Fig. 5. new coverage graph after after adding {t3, r2} edge

Reduced testSet as ReducedSet ;

Add edge as AddEdge(e1) ;

Add AddEdge(e1) ( connected by Requirement(r1) and TestCase(t1) ) in CoverageGraph ;

if AddEdge(e1) belongs to TestCase(t1) which is not in Reduced_Setthen

do nothing for AddEdge(e1) ;

else

if AddEdge(e1) belongs to Requirement(r1) that is coveredby ReducedSet – { TestCase(ti) } and degree of TestCase(ti) is
one then

ReducedSet = ReducedSet – { TestCase(ti) }

else

do nothing for AddEdge(e1) ;

end

end

return Reduced testSet as ReducedSet ;
Line1 In the ReducedSet set we will store the final reduced test set. Line2 deleted edge we store the test case and the requirement relationship. Line45 If the added edge does not belong to the reduced test set then we will do nothing. Line78 If the added edge belongs to the reduced test set and cardinality of the test case which was covering the requirement in the old reduced test set is one then we will remove that test case. Line13 return reduced test set.



EXPERIMENT EVALUATION
In this, we evaluated Flower Method, Traditional greedy sequential method, and Traditional greedy parallel method, parallel RAFI method. We evaluated different factors in different benchmarks.

RQ1: Which method is the timeefficient Traditional greedy method or the Flower method.

RQ2: How much can we reduce the size of the test suite?

RQ3: Is the RAFI method is time efficient in the term to find the reduced test set compared with traditionalgreedy across versions?

RQ4: Is the RAFI method efficient in the term of reduction compared with traditional greedy across versions?

Experiment Subject
In this, we will evaluate our experiment in the set of standard benchmarks (SIR). In this there are a total of eight benchmarks. tcas, totinfo, schedule, printtokens, printtokens2, replace, schedule2, space. From the below benchmarks, we can say that the requirements are between 58 to 1515. Total test cases are between 1052 to 13585. The total numbers of edges are between 12825 to 5713638. We will run our Flower method, traditional greedy method sequential and parallel method in these standard benchmarks. We can see the property of each benchmark from the below table.
Table 1. Standard Benchmarks


EXPERIMENT SETUP
Our aim is 1) Find the minimal test suite such that it can cover all the requirements. 2) Find the time taken to compute the minimal test suite for Flower, Traditional greedy sequential. 3) Speedup for RAFI when we vary the number of threads 5) Speedup for RAFI when we vary the percentage of adding edges 4) Reduction rate for RAFI when we vary the percentage of adding edges 5) Speedup for RAFI when we vary dynamic changes in edges 6) Reduction rate for RAFI when we vary dynamic changes in edges. We will run our all implemented methods in the standard benchmarks(SIR). For evaluating the RAFI, there are three parameters on which the performance can be varied. The parameters are

The number of threads on which we run the RAFI.

Structural change in the old coverage graph, mena percentage of edges got modified.

In edge modification how much percentage edges are added and remaining percentage edges deleted We will evaluate our RAFI for these parameters, we will fix two parameters and will vary the remaining oneparameter.
We are using the machine as Operating System as Linux version 4.4.0159generic, Operating SystemType: 64bit processor, RAM: 4 GB and Processor: Intel 2.60GHz*4

Result and analysis
In this, we will explore the result of the Flower method, traditional greedy sequential for finding the Reduced test setand RAFI parallel method for finding the reduced test set in the modified coverage graph.
Time Efficient
We run Flower and traditional greedy methods to find the minimal test set which can cover all the requirements. We run our experiment in the benchmarks given in the table1. We found the time complexity of the Flower method is exponential so it is
taking the exponential time and failing to find the Reduced test set in a reasonable time. On the other hand, the traditional greedy method has a polynomialtime algorithm. So we were able to find the reduced test set in a few milliseconds. Hence we can say that the traditional greedy algorithm is capable of finding the reduced test set in a reasonable time while the Flower method fails to do this. We can refer to the below figure to find how much the traditional greedy method is taking to find the reduced test set for different benchmarks.
Fig. 6. Time taken by the traditional greedy method to find the reduced set size of the test cases for different benchmarks.
Reduced size of the test set
We ran our traditional greedy method for different benchmarks and found how much they are reducing the test set tofind the reduced test set to cover all the requirements. From the below image we can find the reduced set size of all benchmarks which we are using for evaluation.
Fig. 7. Reduced set size of the test cases for different benchmarks.
Rate Of Speedup when we vary the number of threads
In this we will vary the number of threads from 1 to 8, percentage of dynamic changes in edges will be fixed which is 10% and fixed the 25% of edges added and 75% deleted. Now we calculated the speedup which is the ratio of time taken by Greedy and time taken by RAFI. We found that the maximum speedup we got when the number of threads is 4.
Fig. 8. Speedup of the Rafi method with comparison of traditional greedy parallel to find the reduced set size of the test cases fordifferent benchmarks.
From these two graphs, we can see that as we are increasing the number of threads we are getting speedup but after a certain time speedup got reduced. Because when the number of threads got increased then the most time we were wasting scheduling of the thread instead of doing required work.
Rate of speedup when we vary the percentage of adding edges
In this we will vary the percentage of edge addition from 0% to 100% and rest will be edge deletion, we fixed the number of threads to 4 and fixed percentage dynamic change to 1%. Now we calculated the speedup which is the ratio of time taken by Greedy and time taken by RAFI. We found the maximum speed 489 for schedule2 benchmarks. The maximum speedup we got when the percentage of adding edges was 100%.
Fig. 9 Speedup of the Rafi method with comparison of traditional greedy parallel to find the reduced set size of the test cases for different benchmarks.
From these two graphs, we can see that as we are increasing the percentage of edge edition then speedgetting increased except the tcas benchmarks.
Reduction rate when we vary the percentage of adding edges
In this we evaluated the normalized reduced set size for the above three parameter parameters. Now we calculated the reduction rate which is the ratio of reduced test set size of traditional Greedy and reduced set size of RAFI method.
Fig. 10. Reduction rate of the Rafi method with comparison of traditional greedy parallel for different benchmarks.
From these two graphs, we can see that the reduction rate varies from 0.52 to 1. Still there is a possibility that we can get a reduction rate greater than one. The maximum speedup of reduction rate we are getting when the percentage of adding edges is 0% and deleting edges is 100%
Rate of speedup when we vary dynamic changes in edges
In this we will vary the percentage of dynamic changes in edges from 0.1 to 15%, we fixed the number of threads to 4 and fixed the 25% of edges added and 75% deleted. Now we calculated the speedup which is the ratio of time taken by Greedy and time taken by RAFI. We found that the maximum speedup we got when dynamic changes in edges is 0.1%.
Fig. 11. Speedup of the Rafi method with comparison of traditional greedy parallel to find the reduced set size of the test
cases for different benchmarks.
From these two graphs, we can see that maximum speedup we get for benchmark tcas, which is equal to1590 and maximum speedup when the percentage of dynamic changes is 0.1%.
Reduction rate when we vary dynamic changes in edges
In this we evaluated the normalized reduced set size for the above three parameter parameters. Now we calculated the reduction rate which is the ratio of reduced test set size of traditional Greedy and reduced set size of RAFI method.
Fig. 12. Reduction rate of the Rafi method with comparison of traditional greedy parallel for different benchmarks.
From these two graphs, we can see that the reduction rate varies from 0.34 to 1. Still there is a possibility that we can get a reduction rate greater than one. The maximum speedup of reduction rate we are getting when the percentage of dynamic changes is 0.1%.


CONCLUSION AND FUTURE WORK
Given a set of test cases and the requirement of the software. Our aim was to find the reduced test such that it covers all the requirements. For this, we implemented some existing exponential methods such as Flower and some polynomial methods such as the Traditional greedy method. We run these methods in some standard benchmarks(SIR) and found that the traditional greedy method is able to find the reduced test set in a reasonable time but the Flower method failed to do this in a reasonable time. Further, we found that the traditional greedy method is able to reduce the test set up to 0.07%. Further we implemented the RAFI method to find the reduced test set in the modified coverage graph. Our aim was to find the reduced test set by using the old reduced test set and edges got modified such that it covers all the requirements. We run RAFI method and for comparison we run Traditional greedy method. We found that RAFI gives a reduced test set in very less time compared to Traditional Greedy, we got speedup up to 1590X. In the term of reduction rate, it varies from 0.38 to 1 for the RAFI method.
In future work, we can test different data structures like trees and adjacency lists to store the graph to reduce the time for memory access and space. Further, Adding the notion of test case execution time. If edges are weighted, weighted means that some test cases may take longer to execute. Then in this situation how we will find the reduced test set. Because if test cases are weighted then there is a possibility that the reduced test set whose cardinality is more can give better results.
REFERENCES

Lin, ChuTi, KaiWei Tang, JiunShiang Wang, and Gregory M. Kapfhammer. "Empirically evaluating Greedybased test suite reduction methods at different levels of test suite complexity." Science of Computer Programming 150 (2017): 125.

Kapfhammer, G. M., Regression testing. In Encyclopedia of Software Engineering ThreeVolume Set (Print). Auerbach Publications, 2010, 893 915.

Rothermel, G., & Harrold, M. J. (1997). A safe, efficient regression test selection technique. ACM Transactions on Software Engineering and Methodology (TOSEM), 6(2), 173210.

Rothermel, Gregg, et al. "An empirical study of the effects of minimization on the fault detection capabilities of test suites." Proceedings. International Conference on Software Maintenance (Cat. No. 98CB36272). IEEE, 1998.

Wong, W. Eric, et al. "Effect of test set minimization on fault detection effectiveness." Software: Practice andExperience 28.4 (1998): 347369.

Gligoric, Milos, Lamyaa Eloussi, and Darko Marinov. "Practical regression test selection with dynamic file dependencies." Proceedings of the 2015 International Symposium on Software Testing and Analysis. 2015.

Marchetto, Alessandro, et al. "A multiobjective technique to prioritize test cases." IEEE Transactions on Software Engineering 42.10 (2015): 918940.

Wong, W. Eric, et al. "Effect of test set minimization on fault detection effectiveness." Software: Practice andExperience 28.4 (1998): 347369.

Zhang, Lingming, et al. "An empirical study of junit testsuite reduction." 2011 IEEE 22nd International Symposium on Software Reliability Engineering. IEEE, 2011.

Lin, JunWei, and ChinYu Huang. "Analysis of test suite reduction with enhanced tiebreaking techniques."
Information and Software Technology 51.4 (2009): 679690.

Jeffrey, Dennis, and Neelam Gupta. "Improving fault detection capability by selectively retaining test cases during test suite reduction." IEEE Transactions on software Engineering 33.2 (2007): 108123.

Qu, Xiao, Myra B. Cohen, and Gregg Rothermel. "Configurationaware regression testing: an empirical study of sampling and prioritization."
Proceedings of the 2008 international symposium on Software testing and analysis. 2008.

Jeffrey, Dennis, and Neelam Gupta. "Test suite reduction with selective redundancy." 21st IEEE International Conference on Software Maintenance (ICSM'05). IEEE, 2005.

Gotlieb, Arnaud, and Dusica Marijan. "FLOWER: optimal test suite reduction as a network maximum flow."
Proceedings of the 2014 International Symposium on Software Testing and Analysis. 2014.

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms.MIT press, 2009.

Black, Jennifer, Emanuel Melachrinoudis, and David Kaeli. "Bicriteria models for alluses test suite reduction." Proceedings. 26th International Conference on Software Engineering. IEEE, 2004.

Chen, Z., Zhang, X., & Xu, B. (2008, July). A Degraded ILP Approach for Test Suite Reduction. In SEKE
(pp. 494499).

Hao, D., Zhang, L., Wu, X., Mei, H., & Rothermel, G. (2012, June). Ondemand test suite reduction. In 201234th International Conference on Software Engineering (ICSE) (pp. 738748). IEEE.

Li, Zheng, Mark Harman, and Robert M. Hierons. "Search algorithms for regression test caseprioritization." IEEE Transactions on software engineering 33.4 (2007): 225237.