Huang, Cohen, Memon

Abstract

Recent advances in automated functional testing of Graphical User Interfaces (GUIs) rely on deriving graph models that approximate all possible sequences of events that may be executed on the GUI, and then use the graphs to generate test cases (event sequences) that achieve a specified coverage goal. However, because these models are only approximations of the actual events flows, the generated test cases may suffer from problems of infeasibility, i.e., some events may not be available for execution causing the test case to terminate prematurely. In this paper we develop a method to automatically repair GUI test suites, generating new test cases that are feasible. We use a genetic algorithm to evolve new test cases that increase our test suite's coverage while avoiding infeasible sequences. We experiment with this algorithm on a set of synthetic programs containing different types of constraints and for test sequences of varying lengths. Our results suggest that we can generate new test cases to cover most of the feasible coverage and that the genetic algorithm outperforms a random algorithm trying to achieve the same goal in almost all cases.

Experiment Settings

CPU: AMD 2.4GHz dual-core 64-bit processors
Memory: 16GB
Operating System: Linux 2.6.18
Java Runtime: Java 1.6 update 16
GUI Environment: Xvfb

Subjects

We designed seven synthetic programs to mimic the types of constraints found in real software. These programs have no real functionality other than to implement the constraints. The following table provides detailed descriptions for each. These benchmarks are also included on the COMET Benchmarking website along with information about the tools necessary to run and execute the experiments.

The events in each program are labeled Event1, Event2, etc. The presence of "..." indicates 0 or more other events). Click the program numbers to download the source code of the programs, and click the constraint full names to download the constraint files. View format of the constraint files.

We have also provided a simple tool for the conversion from the constraint file in our format to that in the format presented on http://www.cse.unl.edu/citportal/tools/casa/. Download the tool here.

Program	Full Name	Abbreviated	Number of Events	Constraint Description
1	Disabled Event Constraint	Disb	3	Event1 is always disabled.
2	Requires Constraint	Reqs	3	Event3 requires Event2 to occur before it.
3	Event Consecutive Constraint (2-way)	2Cons	3	A pair of events, (Event1, Event2), is infeasible when executed sequentially.
4	Excludes Constraint (2-way)	2Excl	3	A pair of events, (Event1, ..., Event2), is infeasible if they occur (possibly non-consecutively) in sequences.
5	Event Consecutive Constraint (3-way)	3Cons	4	A sequence of three events, (Event1, Event2, Event3), is infeasible when executed.
6	Excludes Constraint (3-way)	3Excl	5	A (possibly non-consecutive) sequence of three events, (Event1, ..., Event2, ..., Event3), is infeasible.
7	Compound Constraints	Cmpd	5	Includes constraints found in Subject 2, 3 and 5: sequences (Event1, Event2) and (Event2, Event3, Event4) are infeasible; Event5 requires Event3 to occur before it.

Results

We provide results for our experiments on the seven subjects. In the paper, we run each experiment five times and show the average. We have included all of the he results for each of the five runs here. We represent events using integers in the test cases. These are zero based (but the programs are one-based) so integer i means Event(i+1). The parameters used can be found in the paper. View format for the covering array models(the specific models can be found by clicking the links in the "Length" column),format for the infeasible t-sets and format for the test suite files.

Repaired test suites for 2-way criteria by genetic algorithm
Subject	Length	All t-sets	Infeasible t-sets	Feasible t-sets	Run 1		Run 2		Run 3		Run 4		Run 5
Subject	Length	All t-sets	Infeasible t-sets	Feasible t-sets	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.
Disb	5	90	50	40	0	40	20	40	20	40	10	40	10	40
	10	405	225	180	45	180	0	180	0	180	0	180	0	180
	15	945	525	420	0	420	0	420	0	420	0	420	0	420
	20	1710	950	760	0	760	0	760	0	760	0	760	0	760
Reqs	5	90	13	77	61	77	53	77	61	77	55	77	44	77
	10	405	28	377	270	377	278	377	252	377	277	377	300	377
	15	945	43	902	634	902	684	902	592	902	741	902	652	902
	20	1710	58	1652	1288	1652	1200	1652	1204	1652	1153	1652	1219	1652
2Cons	5	90	4	86	64	86	56	86	47	86	29	86	46	86
	10	405	9	396	195	396	229	396	197	396	164	396	230	396
	15	945	14	931	105	931	200	931	200	931	284	931	200	931
	20	1710	19	1691	190	1691	365	1691	359	1691	359	1691	190	1691
2Excl	5	90	10	80	46	80	45	80	54	80	46	80	48	80
	10	405	45	360	45	360	45	360	80	360	45	360	162	360
	15	945	105	840	0	835	0	838	105	838	0	838	105	836
	20	1710	190	1520	0	1516	0	1508	0	1511	0	1511	0	1509
3Cons	5	160	0	160	150	160	160	160	150	160	150	160	150	160
	10	720	0	720	641	720	655	720	674	720	660	720	678	720
	15	1680	0	1680	1513	1680	1482	1680	1448	1680	1507	1680	1464	1680
	20	3040	0	3040	2832	3040	2717	3040	2363	3040	2850	3040	2726	3040
Cmpd	5	250	27	223	100	223	113	223	110	223	90	223	120	223
	10	1125	57	1068	537	1068	462	1068	408	1068	322	1068	518	1068
	15	2625	87	2538	922	2538	844	2538	763	2538	854	2538	765	2538
	20	4750	117	4633	1667	4633	1210	4633	1202	4633	887	4633	1035	4633

Repaired test suites for 2-way criteria by random algorithm
Subject	Length	All t-sets	Infeasible t-sets	Feasible t-sets	Run 1		Run 2		Run 3		Run 4		Run 5
Subject	Length	All t-sets	Infeasible t-sets	Feasible t-sets	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.
Disb	5	90	50	40	20	40	20	40	20	40	20	40	20	40
Disb	10	405	225	180	0	123	0	129	0	142	0	127	0	113
Reqs	5	90	13	77	46	76	37	74	46	70	46	70	46	70
Reqs	10	405	28	377	251	355	251	357	251	357	251	354	251	358
2Cons	5	90	4	86	72	86	72	86	72	86	64	86	72	86
2Cons	10	405	9	396	163	343	163	365	163	357	163	349	163	351
2Excl	5	90	10	80	56	75	56	79	56	79	56	79	56	79
2Excl	10	405	45	360	45	276	45	276	45	268	45	272	45	281
3Cons	5	160	0	160	150	158	150	159	150	159	150	160	150	159
3Cons	10	720	0	720	670	715	670	712	670	717	670	710	670	711
Cmpd	5	250	27	223	110	185	110	170	110	173	110	177	110	178
Cmpd	10	1125	57	1068	437	862	437	872	437	852	437	855	437	851

Repaired test suites for 3-way criteria by genetic algorithm
Subject	Length	All t-sets	Infeasible t-sets	Feasible t-sets	Run 1		Run 2		Run 3		Run 4		Run 5
Subject	Length	All t-sets	Infeasible t-sets	Feasible t-sets	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.
Reqs	5	270	64	206	156	206	156	206	156	206	148	206	156	206
Reqs	10	3240	349	2891	2203	2891	2203	2891	2203	2891	2203	2891	2203	2891
2Cons	5	270	36	234	169	234	169	234	169	234	169	234	169	234
2Cons	10	3240	216	3024	1627	3024	1696	3024	1696	3024	1696	3024	1696	3024
2Excl	5	270	70	200	126	200	126	200	126	200	126	200	126	200
2Excl	10	3240	840	2400	640	2400	640	2400	640	2400	640	2400	640	2400
3Cons	5	640	3	637	610	637	610	637	610	637	610	637	610	637
3Cons	10	7680	8	7672	7330	7672	7330	7672	7330	7672	7306	7672	7330	7672
3Excl	5	1250	10	1240	1192	1240	1192	1240	1192	1240	1192	1240	1192	1240
3Excl	10	15000	120	14880	12386	14879	12419	14880	12419	14880	12419	14880	12419	14879
Cmpd	5	1250	263	987	598	985	598	985	598	985	598	985	598	985
Cmpd	10	15000	1388	13612	7190	13610	7190	13610	7190	13610	7130	13610	7115	13612

Repaired test suites for 3-way criteria by random algorithm
Subject	Length	All t-sets	Infeasible t-sets	Feasible t-sets	Run 1		Run 2		Run 3		Run 4		Run 5
Subject	Length	All t-sets	Infeasible t-sets	Feasible t-sets	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.	Initial Cov.	Final Cov.
Reqs	5	270	64	206	156	192	156	196	156	195	156	197	156	193
Reqs	10	3240	349	2891	2203	2712	2203	2693	2203	2728	2203	2703	2203	2716
2Cons	5	270	36	234	169	202	169	204	169	203	161	217	169	218
2Cons	10	3240	216	3024	1635	2576	1696	2592	1696	2570	1696	2629	1696	2608
2Excl	5	270	70	200	126	167	126	174	126	174	126	188	126	190
2Excl	10	3240	840	2400	640	1751	640	1747	640	1708	640	1781	640	1891
3Cons	5	640	3	637	610	624	610	625	610	624	610	632	600	633
3Cons	10	7680	8	7672	7330	7565	7304	7551	7316	7552	7330	7556	7330	7559
3Excl	5	1250	10	1240	1192	1219	1192	1217	1192	1219	1185	1221	1192	1225
3Excl	10	15000	120	14880	12419	13992	12419	13967	12419	13967	12419	13996	12419	13978
Cmpd	5	1250	263	987	598	784	598	775	598	781	598	783	598	784

Acknowledgments

We would like to thank Scott McMaster for providing us with the replayer modified for our experiments, and Mary Lou Soffa for early discussions on this work. This work was partially supported by the US National Science Foundation under grants CCF-0747009, CCF-0447864, CNS-0855139 and CNS-0855055, the Air Force Office of Scientific Research through award FA9550-09-1-0129, the Office of Naval Research grant N00014-05-1-0421 and by the Defense Advanced Research Projects Agency.