Multi Objective Test Suite Reduction for GUI Based Software Using NSGA-II

Published Online August 2016 in MECS

The widespread recognition of the usefulness of graphical user interface (GUIs) has established their importance as critical components of today’s software. Testing of GUIs systems is more difficult due to the following reasons: The event driven nature of GUIs, unsolicited events, many ways in/ many ways out, and the infinite input domain problems make it likely that the programmer has introduced errors because he could not test every path [6]. Regression testing means rerunning test cases from existing test suites to build confidence that software changes have no unintended side-effects. The ideal process for regression testing is to create a wide test suite and run it after each and every modification [7]. Regression testing is also a critical problem with GUI’s. This is because the GUI may modify significantly across versions of the application, even though the underlying application may not. A small modification in GUI may cause many of test cases to become useless. When we do regression testing huge number of test cases becomes unusable for different version of application under test. Rerunning all test cases again will be time consuming. So we require test suite reduction technique for GUI based software. There are very few existing techniques for test suite reduction of GUI based software and they are based on single objective. In this work we propose Multiobjective test suite reduction technique for GUI based software.

One of the objectives of multi objective test suite reduction is to find as many Pareto-optimal test cases as possible. This discards the requirement of assigning weight values to multiple objectives converting them in a single one. Evolutionary algorithms consider all non dominated solution in a population as similar and provide a diverse set of multiple non dominated solutions [8]. That is why EA is a preferable choice for test suite reduction it will eliminate only dominated solutions.

Pareto-optimal solutions

Pareto optimal solution exists when there is a need to optimize multiple conflicting objectives, there is trade off between one or more conflicting objectives and the relative importance of these objectives is not known.

Therefore our objective of test suite reduction of GUI based software is

• •    To find test cases which are as close as possible to the Pareto-optimal front

• •    To identify test cases as diverse as possible to cover complete test suite

A multi objective test suite minimization problem can be formulated as:

Given a test suite T for GUI based application with Events E = {e1,e2,e3,…en}, where E is the set of events.

Find the minimal test suite T’ such that T’ is a Pareto-Optimal set which satisfy a given measure. (maximum weight based event coverage and consider set of fault identified by individual test cases)

The organization of this paper is as follows: Section II discuss about previous work done by researchers. Section III demonstrates Multi Objective Test Suite Reduction and problem formulation. Test suite reduction using NSGA II is discussed in Section IV. This section also comprises experimental results. Section V comprises of threats to validity. Finally, section VI contains conclusion and future work.

• II.    Related Work

The objective of test suite minimization is to reduce the number of test cases in a given test suite which satisfy the given criteria. Many greedy algorithms are used to solve test suite reduction problems [25, 26, 27]. Harrold et al. proposed a heuristic based algorithm known as HGS for test suite reduction. That algorithm tries to minimize test suite based on program requirements.

The concept of HGS algorithm was further generalized by Von Ronne. In this work a concept of hitting factor was introduced, based on this factor every requirement could be satisfied multiple times.

The next frequently used test suite reduction techniques are based on evolutionary computation [30, 31].

The problem of test suite reduction can be formulated as NP-Hard problem [18], minimum set cover problem. For test suite minimization many heuristics are suggested in literature [20, 19]. There are few studies that report no impact of test suite reduction[21,22] and some studies shows negative impact of test suite reduction because reduce test suite will compromise the fault revealing capability of test suite [13]. That may be due to reduction criterion which is simply taken as structural coverage. Although, Rothermel et al. in their paper reveal that the fault-detection capabilities of test suites may be severely compromised by test-suite reduction. They further analyze the cost and benefit of test suite reduction. Authors specify that characteristics of programs and faults will be important parameters for test suite reduction [13].

In further research some more techniques are proposed and they have some sophisticated reduction criteria and consider program characteristics. Scott McMaster and Atif Memon present a reduction technique based on the call-stack coverage criterion. Significance of this technique is due to the context provided by call stack, which is valuable in test suite reduction [9]. Preethi Harris and Nedunchezhian Raju in their work reduce the size of the test suite based on two metrics Size and requirement coverage [10]. Rajiv Gupta and Mary Lou Soffa, presents a test suite reduction technique based on data flow testing methodology. They select a reduce test suite which provide same coverage as entire test suite by removing redundant and obsolete test cases[11]. A static analysis approach based on program slicing is proposed by Stephan Arlt et al. [12]. This approach reduces the size of test suite by removing redundant event sequences from test cases.

Previous work has considered test suite reduction problem as single objective optimization. From the last few years researchers have introduced the concept of Pareto efficiency for test suite reduction and consider multiple objectives like code coverage, past faultdetection history and execution cost [16] for reduction. Shin Yoo et al. developed a search based optimisation approach for multi objective regression test optimisation for graphics cards. Authors in the paper introduce the concept of parallel test suite minimization along with the concept of scalability [15]. Saeed Parsa and Alireza Khalilian in their paper consider test suite reduction as multi objective problem where first objective is fault detection capability and it has to be maximized. The second objective is number of test cases which should be minimized. They used greedy algorithm to solve this optimization problem.

There are very few researches which focus on test suite reduction of GUI based applications. In one of the approach reduction is based on call stack based coverage. In another research done by Wei Sun et al. a multiobjective algorithm is proposed for test cases prioritization for GUI applications. They consider statement coverage event coverage for prioritization criteria.

• III.    Multi Objective Test Suite Reduction

Most evolutionary multi objective optimization algorithms require us to find best non dominated front in the population and in our approach best non dominated front is reduced set of test cases and reduction is based on following two objectives

• 1)    Weight of test case

• 2)    Number of faults identified

In our previous work we have generated a formula for calculating weight of each test case that is based on weight value of events and event coverage.

In this work event classification is considered where events are classified according to their fault revealing capability and they are assigned a weight value (events classification and their weight value is shown in table 1).

Table 1. Event weight assignment [1]

Event type	WVs
Restricted-focus event	5
System-interaction event	4
Termination event	3
Menu-open event	2
Unrestricted-focus event	1

Then weight of each event is added and multiplied with the coverage of test case.

Finally coverage is computed by calculating (adding) number of events in the test case divided by total number of events in the application [2].

Weight of each test case is calculated according to the formula given in (1):

W tc = n / Tn * £ »j                    (1)

j = 1

Where W TC is Weight of test case, Wj is the j^th event weight, n is the number of events in test case and Tn is the total number of events in AUT.

Fig.1. NSGA II procedure [8]

• IV.    Test Suite Reduction Using Nsga II

NSGA-II uses an explicit diversity-preserving mechanism. In order to sort a population of size N according to the level of non-domination, each solution must be compared with every other solution in the population to find if it is dominated. NSGA II starts with the parent population Pt and offspring population Qt.. Procedure for algorithm is specified in fig. 1.

Various steps of algorithm are specified as follows:

• 1)    Generation of Initial Set of test suite: In our application we have taken test cases of Terp Paint 3.0’ from Event Driven Software Lab. To implement the algorithm we have randomly selected few test cases from artefacts. Test cases are represented in binary string format according to the number of fault they reveal and number of event coverage. For example test case T1 reveal fault 1 and event coverage 6 and T2 reveal fault 2 and coverage 14. Length of test case is 5 where first 5 bit represents number of faults covered by test case and last five bit represents number of events covered by test case.

Table 2. Binary representation of test cases

Test Case	Number of faults					Event		Coverage
T1	0	0	0	0	1	0	0	1	1	0
T2	0	0	0	1	0	0	1	1	1	0
T3	0	0	1	0	0	0	1	1	0	1
T4	0	0	0	1	1	1	0	0	0	0
T5	0	0	1	0	0	0	1	0	1	0
T6	0	0	1	1	1	0	1	1	0	0
T7	0	0	1	1	0	0	1	1	0	0

Table 3. Fault and Weight value of test cases

Test Case	Number of fault	Weight of test case
T1	1	1.61
T2	2	10.04
T3	4	10.04
T4	3	3.61
T5	4	3.61
T6	7	3.61
T7	6	6.43

Fig.2. Line Chart for Number of Faults and Weight of Test Case

After generation of initial population their values are calculated for both objectives. Weight of test case is calculated according to (1) and the number of faults is identified from initial testing. These values are specified in table 3:

Fig 2 shows line chart for number of faults and weight of test cases it is clearly visible from the figure that these two are conflicting objectives test cases can not be selected based on any one objective.

• 2)    Perform Non-dominated sorting on initial test suite: In our example we have used Kung et al.’s efficient method for sorting. This method is most computationally efficient method.

For the given example we require offspring population also but for the example purpose we consider only parent population. Sort the test cases according to descending order of importance of Event Weight. Now we call set of test cases as T’

T’= {T2,T3,T7,T4,T5,T6,T1}

Next we have performed non dominated sorting on T’ and we obtain following non dominated fronts:

F1 = {T3, T7, T6}

F2 = {T2,T5}

F3 = {T4}

F4 = {T1}

In this example total number of test cases is N but in the algorithm total number of test cases will be 2N and we need to identify N test cases from the initial fronts.

• 3)    Calculate the crowding distance: Once the sorting is complete, crowding distance is assigned to each test case in all fronts. Crowding distance comparison does not matter in different fronts. Test cases are selected based on rank and crowding distance [4]. Crowding distance is used to select test cases from the same front. Test cases in the boundary are assigned infinity distance so these test cases are always selected. Crowding distance is computed according to (2).

F ( k + 1). m - F ( k - 1). m

F (dk) = F (dk) + —---------——-—(2)

maxmin fm-

F (k).m is the value of the mth objective function of the kth individual in F.

This step will return solutions which are diverse in the solution space. One selected test will be less crowded compare to other solutions.

• 4)    Perform crowded tournament selection, crossover and mutation:

• 7.10. 0(R2010 a). For test suite reduction we have used two objective functions, weight of test case and number of faults identified by test case. Both functions have to be maximizing for reduction purpose.

These operations will be performed to create offspring population of test cases Qt+1 from Pt+1

A crowded tournament selection operator is used to select test cases, where a test case Ti will win the tournament if ‘i’ has a better rank or they have the same rank but ‘i’ has better crowding distance then other solution. We performed other tournaments to obtain the mating pool and then these test cases are mated pair wise and mutation is performed to generate next offspring population.

We have implemented NSGA II using MATLAB

• V.    Evaluation of Algorithm

For the evaluation of test suite reduction methods, we have considered two applications i.e. Terp Paint 3.0 and Notepad. For both applications, when we run NSGA II algorithm we get results as shown in table 4. The results of the optimization shown in table 4 containing both objective function values and the value of the Number of Events and faults. We have evaluated test cases of both applications corresponding to given values. All test cases near Pareto optimal front are selected for regression testing purpose.

Fig.3. Pareto front for Test suite minimization

Fig.4. Average Distance between Individuals

Fig.5. Score Histogram for two objectives

Fig.6. Distance between individuals

Fig. 3 represents two competing objectives. The tradeoff between these two objectives, weight of test case and number of faults is plotted in objective function space.

Fig. 4 to fig. 6 plots various aspects of the multi objective genetic algorithm its execution corresponding to different generations. In Table 4, Weight of test case and number of faults represents both objective functions. Number of Events and Faults represents input values.

Table 4. Optimal values for test suite reduction

Test Case	Objectives		Inputs
	Weight of test case	Number of Faults	Number of Events	Faults
10	13.10326	3.092452	11.1289	2.092452
1	11.24816	3.093185	11.12875	2.093185
2	9.266539	3.096041	9.592378	2.096041
8	4.454116	3.09611	6.378983	2.09611
5	3.588967	3.171592	5.638344	2.171592
11	2.862798	3.660142	5.382481	2.660142
3	2.817113	4.956395	5.335696	3.956395
4	2.724817	6.548348	5.240018	5.548348
6	2.724781	8.548256	5.23998	5.548256
9	2.724779	9.548562	5.239978	5.548562
7	2.724602	10.54852	5.239793	5.548515

To calculate the test suite size reduction and fault detection capability loss we have used (3) and (4) respectively:

%t est suite size reduction= ^{| T | - | T RED |} *100            (3)

%f ault detection loss = ^{| F | - | F RED |} *100            (4)

We have evaluated NSGA II using Application Under Test (AUT), Notepad and Terp Paint 3.0[3].

Table 5. Size Reduction and Fault Detection loss for Application Under Test

AUT	% Size Reduction	% Fault Detection loss
Terp Paint 3.0	20	84
Notepad	20	88.8

As shown in table 5, we consider small size of test suite for Terp Paint 3.0 Application, it gave 20% reduction in test suite size and its fault revealing capability is reduced to 84.4%.

Fig.7. Bar chart for Size Reduction and Fault Detection loss for Application Under Test

In another example of notepad test suite size reduction is 80% and fault revealing capability is reduced to 88.8%. Fig. 7 represents bar chart for application under test considering reduction in test suite size and fault detection loss.

• VI.    Threats to Validity

Threats to validity consider all aspects that may affect ability to generalize results in other situations. First threat considers that validation of our results is done using test cases generated for 2 applications, first is Terp Paint 3.0 and another application is Notepad. Test cases for Terp Paint are generated using Guitar tool which generates test cases by creating all possible combination of events by ripping the application. For notepad application we have generated test cases using HP-QTP version 11 [5]. Further experiments should be done with bigger size of test suites. There may be different cost associated with every test case execution and this is another threat to validity but we have considered uniform cost of execution in our research.

• VII.    Conclusion and Future Work

We have implemented NSGA II algorithm for test suite reduction. When we executed algorithm for two examples, we are able to achieve reduction in test suite size. From the analysis of results obtained from two applications this is vibrant that whenever test suite size is reduced fault revealing capability will be compromised. In case of time constraint we should reduce number of test cases other than redundant ones because fault revealing capability of test suite will be reduced. As we infer from the literature that there is no existing technique for test suite reduction of GUI based software which considers multiple objectives. This is a novel idea for future research.