Hierarchical GUI Test Case Generation Using Automated Planning.
AbstractThe widespread use of GUIs for interacting with software is leading to the construction of more and more complex GUIs. With the growing complexity come challenges in testing the correctness of a GUI and its underlying software. We present a new technique to automatically generate test cases for GUIs that exploits planning, a well-developed and used technique in artificial intelligence. Given a set of operators, an initial state, and a goal state, a planner produces a sequence of the operators that will transform the initial state to the goal state. Our test case generation technique enables efficient application of planning by first creating a hierarchical model of a GUI based on its structure. The GUI model consists of hierarchical planning operators representing the possible events in the GUI. The test designer defines the preconditions and effects of the hierarchical operators, which are input into a plan-generation system. The test designer also creates scenarios that represent typical initial and goal states for a GUI user. The planner then generates plans representing sequences of GUI interactions that a user might employ to reach the goal state from the initial state. We implemented our test case generation system, called Planning Assisted Tester for grapHical user interface Systems (PATHS) and experimentally evaluated its practicality and effectiveness. We describe a prototype implementation of PATHS and report on the results of controlled experiments to generate test cases for Microsoft's WordPad.
Introduction
G RAPHICAL User Interfaces (GUIs) have become an
important and accepted way of interacting with to-
day's software. Although they make software easy to use
from a user's perspective, they complicate the software development
process [1], [2]. In particular, testing GUIs is
more complex than testing conventional software, for not
only does the underlying software have to be tested but the
GUI itself must be exercised and tested to check whether it
confirms to the GUI's specifications. Even when tools are
used to generate GUIs automatically [3], [4], [5], these tools
themselves may contain errors that may manifest themselves
in the generated GUI leading to software failures.
Hence, testing of GUIs continues to remain an important
aspect of software testing.
Testing the correctness of a GUI is difficult for a number
of reasons. First of all, the space of possible interactions
with a GUI is enormous, in that each sequence of GUI commands
can result in a different state, and a GUI command
may need to be evaluated in all of these states. The large
number of possible states results in a large number of input
The authors are with the Department of Computer Science, University
of Pittsburgh, Pittsburgh, PA 15260, USA. The second author
is also in the Intelligent Systems Program. E-mail: fatif, pollack,
soffag@cs.pitt.edu.
permutations [6] requiring extensive testing, e.g., Microsoft
released almost 400,000 beta copies of Windows95 targeted
at finding program failures [7]. Another problem relates to
determining the coverage of a set of test cases. For conventional
software, coverage is measured using the amount
and type of underlying code exercised. These measures do
not work well for GUI testing, because what matters is not
only how much of the code is tested, but in how many different
possible states of the software each piece of code is
tested. An important aspect of GUI testing is verification
of its state at each step of test case execution. An incorrect
GUI state can lead to an unexpected screen, making further
execution of the test case useless since events in the
test case may not match the corresponding GUI components
on the screen. Thus, the execution of the test case
must be terminated as soon as an error is detected. Also,
if verification checks are not inserted at each step, it may
become difficult to identify the actual cause of the error.
Finally, regression testing presents special challenges for
GUIs, because the input-output mapping does not remain
constant across successive versions of the software [1]. Regression
testing is especially important for GUIs since GUI
development typically uses a rapid prototyping model [8],
[9], [10], [11].
An important component of testing is the generation of
test cases. Manual creation of test cases and their mainte-
nance, evaluation and conformance to coverage criteria are
very time consuming. Thus some automation is necessary
when testing GUIs. In this paper, we present a new technique
to automatically generate test cases for GUI systems.
Our approach exploits planning techniques developed and
used extensively in artificial intelligence (AI). The key idea
is that the test designer is likely to have a good idea of the
possible goals of a GUI user, and it is simpler and more
effective to specify these goals than to specify sequences
of events that the user might employ to achieve them.
Our test case generation system, called Planning Assisted
Tester for grapHical user interface Systems (PATHS) takes
these goals as input and generates such sequences of events
automatically. These sequences of events or "plans" become
test cases for the GUI. PATHS first performs an automated
analysis of the hierarchical structure of the GUI
to create hierarchical operators that are then used during
plan generation. The test designer describes the preconditions
and effects of these planning operators, which are
subsequently input to the planner. Hierarchical operators
enable the use of an efficient form of planning. Specifically,
to generate test cases, a set of initial and goal states is input
into the planning system; it then performs a restricted
form of hierarchical plan generation to produce multiple
hierarchical plans. We have implemented PATHS and we
demonstrate its effectiveness and efficiency through a set
of experiments.
The important contributions of the method presented in
this paper include the following.
ffl We make innovative use of a well known and used technique
in AI, which has been shown to be capable of
solving problems with large state spaces [12]. Combining
the unique properties of GUIs and planning, we are
able to demonstrate the practicality of automatically
generating test cases using planning.
ffl Our technique exploits structural features present in
GUIs to reduce the model size, complexity, and to improve
the efficiency of test case generation.
ffl Exploiting the structure of the GUI and using hierarchical
planning makes regression testing easier.
Changes made to one part of the GUI do not affect
the entire test suite. Most of our generated test cases
are updated by making local changes.
ffl Platform specific details are incorporated at the very
end of the test case generation process, increasing the
portability of the test suite. Portability, which is important
for GUI testing [13], assures that test cases
written for GUI systems on one platform also work on
other platforms.
ffl Our technique allows reuse of operator definitions that
commonly appear across GUIs. These definitions can
be maintained in a library and reused to generate test
cases for subsequent GUIs.
The next section gives a brief overview of PATHS using
an example GUI. Section III briefly reviews the fundamentals
of AI plan generation. Section IV describes how planning
is applied to the GUI test case generation problem. In
Section V we describe a prototype system for PATHS and
give timing results for generating test cases. We discuss
related work for automated test case generation for GUIs
in Section VI and conclude in Section VII.
II.

Overview

In this section we present an overview of PATHS through
an example. The goal is to provide the reader with a high-level
overview of the operation of PATHS and highlight the
role of the test designer in the overall test case generation
process. Details about the algorithms used by PATHS are
given in Section IV.
GUIs typically consist of components such as labels, but-
tons, menus, and pop-up lists. The GUI user interacts with
these components, which in turn generate events. For ex-
ample, pushing a button Preferences generates an event
(called the Preferences event) that opens a window. In
addition to these visible components on the screen, the user
also generates events by using devices such as a mouse or
a keyboard. For the purpose of our model, GUIs have two
types of windows: GUI windows and object windows. GUI
windows contain GUI components, whereas object windows
do not contain any GUI components. Object windows are
used to display and manipulate objects, e.g., the window
used to display text in MS WordPad.
Up
Select
Fig. 1. The Example GUI.

Figure

presents a small part of the MSWordPad's GUI.
This GUI can be used for loading text from files, manipulating
the text (by cutting and pasting) and then saving
the text in another file. At the highest level, the GUI has
a pull-down menu with two options (File and Edit) that
can generate events to make other components available.
For example the File event opens a menu with New, Open,
Save and SaveAs options. The Edit event opens a menu
with Cut, Copy, and Paste options, which are used to cut,
copy and paste objects respectively from the main screen.
The Open and SaveAs events open windows with several
more components. (Only the Open window is shown; the
SaveAs window is similar.) These components are used to
traverse the directory hierarchy and select a file. Up moves
up one level in the directory hierarchy and Select is used
to either enter subdirectories or select files. The window is
closed by selecting either Open or Cancel.
The central feature of PATHS is a plan generation sys-
tem. Automated plan generation has been widely investigated
and used within the field of artificial intelligence.
The input to the planner is an initial state, a goal state,
and a set of operators that are applied to a set of objects.
Operators, which model events, are usually described in
terms of preconditions and effects: conditions that must
be true for the action to be performed and conditions that
will be true after the action is performed. A solution to
a given planning problem is a sequence of instantiated operators
that is guaranteed to result in the goal state when
executed in the initial state. 1 In our example GUI, the
operators relate to GUI events.
Consider Figure 2(a), which shows a collection of files
stored in a directory hierarchy. The contents of the files
We have described only the simplest case of AI planning. The
literature includes many techniques for extensions, such as planning
under uncertainty [14], but we do not consider these techniques in
this paper.
(a)
This is the text that must be modified.
This is the text that must be modified.
This needs to be modified.
This needs to be modified.
This is the text.
This is the text.
(b)
This is the text that must be modified.
This is the text that must be modified.
This needs to be modified.
This needs to be modified.
This is the text.
This is the text.
This is the final text.
This is the final text.
new.doc
Fig. 2. A Task for the Planning System; (a) the Initial State, and
(b) the Goal State.
are shown in boxes, and the directory structure is shown
as an Exploring window. Assume that the initial state
contains a description of the directory structure, the location
of the files, and the contents of each file. Using these
files and WordPad's GUI, we can define a goal of creating
the new document shown in Figure 2(b) and then storing it
in file new.doc in the /root/public directory. Figure 2(b)
shows this goal state that contains, in addition to the
old files, a new file stored in /root/public directory. Note
that new.doc can be obtained in numerous ways, e.g., by
loading file Document.doc, deleting the extra text and typing
in the word final, or by loading file doc2.doc and inserting
text, or by creating the document from scratch by
typing in the text.
Our test case generation process is partitioned into two
phases, the setup phase and plan-generation phase. In the
first step of the setup phase, PATHS creates a hierarchical
model of the GUI and returns a list of operators from the
model to the test designer. By using knowledge of the GUI,
the test designer then defines the preconditions and effects
of the operators in a simple language provided by the planning
system. During the second or plan-generation phase,
the test designer describes scenarios (tasks) by defining a
set of initial and goal states for test case generation. Fi-
nally, PATHS generates a test suite for the scenarios. The
test designer can iterate through the plan-generation phase
any number of times, defining more scenarios and generat-

I
Roles of the Test Designer and PATHS During Test Case
Generation.
Phase Step Test Designer PATHS
Hierarchical
GUI Operators
Preconditions
and Effects of
Operators
Plan
Generation
3
4 Generate Test
Cases for T
Iterate 3 and 4 for Multiple Scenarios
ing more test cases. Table I summarizes the tasks assigned
to the test designer and those automatically performed by
PATHS.
For our example GUI, the simplest approach in step 1
would be for PATHS to identify one operator for each GUI
event (e.g., Open, File, Cut, Paste). (As a naming conven-
tion, we disambiguate with meaningful prefixes whenever
names are the same, such as Up.) The test designer would
then define the preconditions and effects for all the events
shown in Figure 3(a). Although conceptually simple, this
approach is inefficient for generating test cases for GUIs
as it results in a large number of operators. Many of these
events (e.g., File and Edit) merely make other events pos-
sible, but do not interact with the underlying software.
An alternative modeling scheme, and the one used in this
work, models the domain hierarchically with high-level operators
that decompose into sequences of lower level ones.
Although high-level operators could in principle be developed
manually by the test designer, PATHS avoids this inconvenience
by automatically performing the abstraction.
More specifically, PATHS begins the modeling process by
partitioning the GUI events into several classes. The details
of this partitioning scheme are discussed later in Section
IV. The event classes are then used by PATHS to create
two types of planning operators - system-interaction
operators and abstract operators.
The system-interaction operators are derived from those
GUI events that generate interactions with the underlying
software. For example, PATHS defines a system-
interaction operator EDIT CUT that cuts text from the
example GUI's window. Examples of other system-
interaction operators are EDIT PASTE and FILE SAVE.
The second set of operators generated by PATHS is a
set of abstract operators. These will be discussed in more
detail in Section IV, but the basic idea is that an abstract
operator represents a sequence of GUI events that invoke a
window that monopolizes the GUI interaction, restricting
the focus of the user to the specific range of events in the
window. Abstract operators encapsulate the events of the
restricted-focus window by treating the interaction within
that window as a separate planning problem. Abstract
operators need to be decomposed into lower level operators
by an explicit call to the planner. For our example GUI,
New, Open, Save, SaveAs,
Cut, Copy, Paste,
Open.Up, Open.Select, Open.Cancel, Open.Open,
Planning Operators = {
File_New, File_Open, File_Save, File_SaveAs,
Edit_Cut, Edit_Copy, Edit_Paste}.
(a)
(b)
Fig. 3. The Example GUI: (a) Original GUI Events, and (b) Planning
Operators derived by PATHS.


II
Operator-event Mappings for the Example GUI.
Operator Name Operator Type GUI Events
FILE NEW Sys. Interaction !File, New?
FILE OPEN Abstract !File, Open?
FILE SAVE Sys. Interaction !File, Save?
FILE SAVEAS Abstract !File, SaveAs?
EDIT CUT Sys. Interaction !Edit, Cut?
EDIT COPY Sys. Interaction !Edit, Copy?
Sys. Interaction !Edit, Paste?
abstract operators include File Open and File SaveAs.
The result of the first step of the setup phase is that the
system-interaction and abstract operators are determined
and returned as planning operators to the test designer.
The planning operators returned for our example are shown
in

Figure

3(b).
In order to keep a correspondence between the original
GUI events and these high-level operators, PATHS also
stores mappings, called operator-event mappings, as shown
in

Table

II. The operator name (column 1) lists all the
operators for the example GUI. Operator type (column
classifies each operator as either abstract or system-
interaction. Associated with each operator is the corresponding
sequence of GUI events (column 3).
The test designer then specifies the preconditions and
effects for each planning operator. An example of a planning
operator, EDIT CUT, is shown in Figure 4. EDIT CUT
is a system-interaction operator. The operator definition
contains two parts: preconditions and effects. All the conditions
in the preconditions must hold in the GUI before
the operator can be applied, e.g., for the user to generate
the Cut event, at least one object on the screen should
be selected (highlighted). The effects of the Cut event are
that the selected objects are moved to the clipboard and
removed from the screen. The language used to define each
operator is provided by the planner as an interface to the
planning system. Defining the preconditions and effects is
not difficult as this knowledge is already built into the GUI
structure. For example, the GUI structure requires that
Cut be made active (visible) only after an object is selected.
This is precisely the precondition defined for our example
operator (EDIT CUT) in Figure 4. Definitions of operators
Pfr.h#'. ))@9DUf8VU
9@G 'Tp.rr#Piw#
9@G Tryrp#rq#Piw#
Hr"
File Edit
Cut
Fig. 4. An Example of a GUI Planning Operator.
representing events that commonly appear across GUIs,
such as Cut, can be maintained in a library and reused for
subsequent similar applications.
The test designer begins the generation of particular test
cases by inputing the defined operators into PATHS and
then identifying a task, such as the one shown in Figure 2
that is defined in terms of an initial state and a goal state.
PATHS automatically generates a set of test cases that
achieve the goal. An example of a plan is shown in Figure
5. (Note that TypeInText() is an operator representing
a keyboard event.) This plan is a high-level plan that
must be translated into primitive GUI events. The translation
process makes use of the operator-event mappings
stored during the modeling process. One such translation
is shown in Figure 6. This figure shows the abstract operators
contained in the high-level plan are decomposed by (1)
inserting the expansion from the operator-event mappings,
and (2) making an additional call to the planner. Since the
maximum time is spent in generating the high-level plan,
it is desirable to generate a family of test cases from this
single plan. This goal is achieved by generating alternative
sub-plans at lower levels. These sub-plans are generated
much faster than generating the high-level plan and can be
substituted into the high-level plan to obtain alternative
test cases. One such alternative low-level test case generated
for the same task is shown in Figure 7. Note the use of
nested invocations to the planner during abstract-operator
decomposition.
The hierarchical mechanism aids regression testing, since
changes made to one component do not necessarily invalidate
all test cases. The higher level plans can still be re-
#Fig. 5. A Plan Consisting of Abstract Operators and a GUI Event.
Low-level Test Case
Fig. 6. Expanding the Higher Level Plan.
tained and local changes can be made to sub-plans specific
to the changed component of the GUI. Also, the steps in the
test cases are platform independent. An additional level of
translation is required to generate platform-dependent test
cases. By using a high-level model of the GUI, we have the
advantage of obtaining platform-independent test cases.
III. Plan Generation
We now provide details on plan generation. Given an
initial state, a goal state, a set of operators, and a set of
objects, a planner returns a set of steps (instantiated op-
erators) to achieve the goal. Many different algorithms for
plan generation have been proposed and developed. Weld
presents an introduction to least-commitment planning [15]
and a survey of the recent advances in planning technology
[16].
Formally, a planning problem is a 4-tuple,
where   is the set of operators, D is a finite set of objects,
I is the initial state, and G is the goal state. Note that an
operator definition may contain variables as parameters;
typically an operator does not correspond to a single executable
action but rather to a family of actions: one for
each different instantiation of the variables. The solution
Low-level Test Case
Fig. 7. An Alternative Expansion Leads to a New Test Case.
to a planning problem is a plan: a tuple !
where S is a set of plan steps (instances of operators, typically
defined with sets of preconditions and effects), O is
a set of ordering constraints on the elements of S, L is a
set of causal links representing the causal structure of the
plan, and B is a set of binding constraints on the variables
of the operator instances in S. Each ordering constraint
is of the form S meaning
that step S i
must occur sometime before step S j
(but not
necessarily immediately before). Typically, the ordering
constraints induce only a partial ordering on the steps in
S. Causal links are triples
are elements of S and c is both an effect of S i and a pre-condition
for S j . 2 Note that corresponding to this causal
link is an ordering constraint, i.e.,
. The reason for
tracking a causal link is to ensure that no step
"threatens" a required link, i.e., no step S k
that results in
:c can temporally intervene between steps S i
As mentioned above, most AI planners produce partially-ordered
plans, in which only some steps are ordered with
respect to one another. A total-order plan can be derived
from a partial-order plan by adding ordering constraints.
Each total-order plan obtained in such a way is called a
linearization of the partial-order plan. A partial-order plan
is a solution to a planning problem if and only if every
consistent linearization of the partial-order plan meets the
solution conditions.

Figure

8(a) shows the partial-order plan obtained to realize
the goal shown in Figure 2 using our example GUI.
generally, c represents a proposition that is the unification
of an effect of S i
and a precondition of S j
DeleteText
("needs to be modified")
TypeInText
("is the final text")
FILE_OPEN
("Samples", "report.doc")
FILE_SAVEAS
("public", "new.doc")
(a)
(c)
DeleteText
("needs to be modified")
TypeInText
("is the final text")
FILE_OPEN
("Samples", "report.doc")
FILE_SAVEAS
("public", "new.doc")
DeleteText
("needs to be modified")
TypeInText
("is the final text")
FILE_OPEN
("Samples", "report.doc")
FILE_SAVEAS
("public", "new.doc")
l
Ordering Constraints
(b)
Fig. 8. (a) A Partial-order Plan, (b) the Ordering Constraints in the
Plan, and (c) the Two Linearizations.
In the figure, the nodes (labeled S i
, and S l
the plan steps (instantiated operators) and the edges
represent the causal links. The bindings are shown as
parameters of the operators. Figure 8(b) lists the ordering
constraints, all directly induced by the causal links
in this example. In general, plans may include additional
ordering constraints. The ordering constraints specify
that the DeleteText() and TypeInText() actions can
be performed in either order, but they must precede the
FILE SAVEAS() action and must be performed after the
FILE OPEN() action. We obtain two legal orders, both of
which are shown in Figure 8(c), and thus two high-level
test cases are produced that may be decomposed to yield
a number of low-level test cases.
In this work, we employ recently developed planning
technology that increases the efficiency of plan generation.
Specifically, we generate single-level plans using the Interference
Progression Planner (IPP) [17], a system that
extends the ideas of the Graphplan system [18] for plan
generation. Graphplan introduced the idea of performing
plan generation by converting the representation of a planning
problem into a propositional encoding. Plans are then
found by means of a search through a graph. The planners
in the Graphplan family, including IPP, have shown
increases in planning speeds of several orders of magnitude
on a wide range of problems compared to earlier planning
systems that rely on a first-order logic representation
and a graph search requiring unification of unbound variables
[18]. IPP uses a standard representation of actions in
which preconditions and effects can be parameterized: subsequent
processing performs the conversion to the propositional
form. 3 As is common in planning, IPP produces
partial-order plans.
IPP forms plans at a single level of abstraction. Techniques
have been developed in AI planning to generate
plans at multiple levels of abstraction called Hierarchical
Task Network (HTN) planning [19]. In HTN planning, domain
actions are modeled at different levels of abstraction,
and for each operator at level n, one specifies one or more
"methods" at level n \Gamma 1. A method is a single-level partial
plan, and we say that an action "decomposes" into
its methods. HTN planning focuses on resolving conflicts
among alternative methods of decomposition at each level.
The GUI test case generation problem is unusual in that, in
our experience at least, it can be modeled with hierarchical
plans that do not require conflict resolution during decom-
position. We are thus able to make use of a restricted form
of hierarchical planning, which assumes that all decompositions
are compatible. Hierarchical planning is valuable
for GUI test case generation as GUIs typically have a large
number of components and events and the use of a hierarchy
allows us to conceptually decompose the GUI into
different levels of abstraction, resulting in greater planning
efficiency. As a result of this conceptual shift, plans can
be maintained at different abstraction levels. When subsequent
modifications are made to the GUI, top-level plans
usually do not need to be regenerated from scratch. In-
stead, only sub-plans at a lower level of abstraction are af-
fected. These sub-plans can be regenerated and re-inserted
in the larger plans, aiding regression testing.
IV. Planning GUI Test Cases
Having described AI planning techniques in general, we
now present details of how we use planning in PATHS to
generate test cases for GUIs.
A. Developing a Representation of the GUI and its Operation

In developing a planning system for testing GUIs, the
first step is to construct an operator set for the planning
problem. As discussed in Section II, the simplest approach
of defining one operator for each GUI event is inefficient,
resulting in a large number of operators. We exploit certain
structural properties of GUIs to construct operators
at different levels of abstraction. The operator derivation
process begins by partitioning the GUI events into
several classes using certain structural properties of GUIs.
Note that the classification is based only on the structural
properties of GUIs and can thus be done automatically by
PATHS using a simple depth-first traversal algorithm. The
GUI is traversed by opening menus and windows by clicking
on buttons; for convenience the names of each operator
are taken off the label of each button/menu-item it repre-
sents. Note that several commercially available tools also
3 In fact, IPP generalizes Graphplan precisely by increasing the expressive
power of its representation language, allowing for conditional
and universally quantified effects.
perform such a traversal of the GUI, e.g., WinRunner from
Mercury Interactive Corporation.
The classification of GUI events that we employ is as
follows:
Menu-open events open menus, i.e., they expand the set
of GUI events available to the user. By definition,
menu-open events do not interact with the underlying
software. The most common example of menu-open
events are generated by buttons that open pull-down
menus, e.g., File and Edit.
Unrestricted-focus events open GUI windows that do
not restrict the user's focus; they merely expand the
set of GUI events available to the user. For exam-
ple, in the MS PowerPoint software, the Basic Shapes
are displayed in an unrestricted-focus window. For
the purpose of test case generation, these events can
be treated in exactly the same manner as menu-open
events; both are used to expand the set of GUI events
available to the user.
Restricted-focus events open GUI windows that have the
special property that once invoked, they monopolize
the GUI interaction, restricting the focus of the user
to a specific range of events within the window, until
the window is explicitly terminated. Preference setting
is an example of restricted-focus events in many GUI
systems; the user clicks on Edit and Preferences, a
window opens and the user then spends time modifying
the preferences, and finally explicitly terminates
the interaction by either clicking OK or Cancel.
System-interaction events interact with the underlying
software to perform some action; common examples
include cutting and pasting text, and opening object
windows.
The above classification of events are then used to create
two classes of planning operators.
System-interaction operators represent all sequences of
zero or more menu-open and unrestricted-focus events
followed by a system-interaction event. Consider a
small part of the example GUI: one pull-down menu
with one option (Edit) which can be opened to give
more options, i.e., Cut and Paste. The events available
to the user are Edit, Cut and Paste. Edit is
a menu-open event and Cut and Paste are system-
interaction events. Using this information the following
two system-interaction operators are obtained.
The above is an example of an operator-event mapping
that relates system-interaction operators to GUI
events. The operator-event mappings fold the menu-
open and unrestricted focus events into the system-
interaction operator, thereby reducing the total number
of operators made available to the planner, resulting
in greater planning efficiency. These mappings
are used to replace the system-interaction operators by
their corresponding GUI events when generating the
final test case.
In the above example, the events Edit, Cut and
Paste are hidden from the planner and only the
system-interaction operators namely, EDIT CUT and
EDIT PASTE, are made available. This abstraction prevents
generation of test cases in which Edit is used
in isolation, i.e., the model forces the use of Edit either
with Cut or with Paste, thereby restricting attention
to meaningful interactions with the underlying
software. 4
Abstract operators are created from the restricted-focus
events. Abstract operators encapsulate the events of
the underlying restricted-focus window by creating a
new planning problem, the solution to which represents
the events a user might generate during the focused
interaction. The abstract operators implicitly
divide the GUI into several layers of abstraction, so
that test cases can be generated for each GUI level,
thereby resulting in greater efficiency. The abstract
operator is a complex structure since it contains all
the necessary components of a planning problem, including
the initial and goal states, the set of objects,
and the set of operators. The prefix of the abstract operator
is the sequence of menu-open and unrestricted-
focus events that lead to the restricted-focus event.
This sequence of events is stored in the operator-event
mappings. The suffix of the abstract operator represents
the restricted-focus user interaction. The abstract
operator is decomposed in two steps: (1) using
the operator-events mappings to obtain the abstract
operator prefix, and (2) explicitly calling the planner
to obtain the abstract operator suffix. Both the prefix
and suffix are then substituted back into the high-level
plan. For example, in Figure 6, the abstract operator
FILE OPEN is decomposed by substituting its prefix
using a mapping and suffix (ChDir,
Select, Open) by invoking the planner.

Figure

9(a) shows a small part of the example GUI:
a File menu with two options, namely Open and
SaveAs. When either of these events is generated, it
results in another GUI window with more components
being made available. The components in both windows
are quite similar. For Open the user can exit
after pressing Open or Cancel; for SaveAs the user
can exit after pressing Save or Cancel. The complete
set of events available is Open, SaveAs, Open.Select,
Open.Up, Open.Cancel, Open.Open, SaveAs.Select,
SaveAs.Up, SaveAs.Cancel and SaveAs.Save. Once
the user selects Open, the focus is restricted to
Open.Select, Open.Up, Open.Cancel and Open.Open.
Similarly, when the user selects SaveAs, the focus
is restricted to SaveAs.Select, SaveAs.Up,
SaveAs.Cancel and SaveAs.Save. These properties
lead to the following two abstract operators:
File
File
In addition to the above two operator-event map-
4 Test cases in which Edit stands in isolation can be created by (1)
testing Edit separately, or (2) inserting Edit at random places in the
generated test cases.
SaveAs
Save
File
File_Open
File_SaveAs
(a)
Abstraction
Abstraction
(c)

Abstract

Operator Template
Operator Name: File_Open
Initial State: determined at run time
Goal State: determined at run time
Operator List:

Abstract

Operator Template
Operator Name: File_SaveAs
Initial State: determined at run time
Goal State: determined at run time
Operator List:
(b)
Fig. 9. (a) Open and SaveAs Windows as Abstract Operators, (b)

Abstract

Operator Templates, and (c) Decomposition of the Abstract
Operator Using Operator-event Mappings and Making a
Separate Call to the Planner to Yield a Sub-plan.
pings, an abstract operator definition template
is created for each operator as shown in Figure 9(b).
This template contains all the essential components of
the planning problem, i.e., the set of operators that
are available during the restricted-focused user inter-
action, and initial and goal states, both determined
dynamically at the point before the call. Since the
higher-level planning problem has already been solved
before invoking the planner for the abstract opera-
tor, the preconditions and effects of the high-level abstract
operator are used to determine the initial and
goal states of the sub-plan. At the highest level of
abstraction, the planner will use the high-level oper-
ators, i.e., File Open and File SaveAs to construct
plans. For example, in Figure 9(c), the high-level plan
contains File Open. Decomposing File Open requires
(1) retrieving the corresponding GUI events from the
stored operator-event mappings (File, Open), and (2)
invoking the planner, which returns the sub-plan (Up,
Select, Open). File Open is then replaced by the sequence
The abstract and system-interaction operators are given
as input to the planner. The operator set returned for the
running example is shown in Figure 3(b).
Initial State:
contains(root private)
contains(private Figures)
contains(private Latex)
contains(Latex
contains(private Courses)
contains(private Thesis)
contains(root public)
contains(public html)
contains(html gif)
containsfile(gif doc2.doc)
containsfile(private
Document.doc)
containsfile(Samples
report.doc)
currentFont(Times Normal
in(doc2.doc This)
in(doc2.doc is)
in(doc2.doc the)
in(doc2.doc text.)
after(This is)
after(is the)
after(the text.)
font(This Times Normal 12pt)
font(is Times Normal 12pt)
font(the Times Normal 12pt)
font(text. Times Normal
Similar descriptions for
Document.doc and report.doc
Goal State:
containsfile(public new.doc)
in(new.doc This)
in(new.doc is)
in(new.doc the)
in(new.doc final)
in(new.doc text.)
after(This is)
after(is the)
after(the final)
after(final text.)
font(This Times Normal 12pt)
font(is Times Normal 12pt)
font(the Times Normal 12pt)
font(final Times Normal
font(text. Times Normal
Fig. 10. Initial State and the changes needed to reach the Goal State.
B. Modeling the Initial and Goal State and Generating Test
Cases
The test designer begins the generation of particular test
cases by identifying a task, consisting of initial and goal
states (see Figure 2). The test designer then codes the
initial and goal states or uses a tool that automatically
produces the code. 5 The code for the initial state and
the changes needed to achieve the goal states is shown in

Figure

10. Once the task has been specified, the system
automatically generates a set of test cases that achieve the
goal. The algorithm to generate the test cases is discussed
next.
C. Algorithm for Generating Test Cases
The test case generation algorithm is shown in Figure 11.
The operators are assumed to be available before making
a call to this algorithm, i.e., steps 1-3 of the test case generation
process shown in Table I must be completed before
making a call to this algorithm. The parameters (lines
include all the components of a planning problem and
a threshold (T) that controls the looping in the algorithm.
The loop (lines 8.12) contains the explicit call to the planner
(\Phi). The returned plan p is recorded with the operator
set, so that the planner can return an alternative plan in
the next iteration (line 11). At the end of this loop, plan-
List contains all the partial-order plans. Each partial-order
plan is then linearized (lines 13.16), leading to multiple linear
plans. Initially the test cases are high-level linear plans
5 A tool would have to be developed that enables the user to visually
describe the GUI's initial and goal states. The tool would then
translate the visual representation to code, e.g., the code shown in

Figure

10.
Lines
Algorithm :: GenTestCases(
Operator Set;
Fig. 11. The Complete Algorithm for Generating Test Cases
(line 17). The decomposition process leads to lower level
test cases. The high-level operators in the plan need to be
expanded/decomposed to get lower level test cases. If the
step is a system-interaction operator, then the operator-
event mappings are used to expand it (lines 20.22). How-
ever, if the step is an abstract operator, then it is decomposed
to a lower level test case by (1) obtaining the GUI
events from the operator-event mappings, (2) calling the
planner to obtain the sub-plan, and (3) substituting both
these results into the higher level plan. Extraction functions
are used to access the planning problem's components
at lines 24.27. The lowest level test cases, consisting of
GUI events, are returned as a result of the algorithm (line
33).
As noted earlier, one of the main advantages of using
the planner in this application is to automatically generate
alternative plans for the same goal. Generating alternative
plans is important to model the various ways in which different
users might interact with the GUI, even if they are
all trying to achieve the same goal. AI planning systems
typically generate only a single plan; the assumption made
there is that the heuristic search control rules will ensure
that the first plan found is a high quality plan. In PATHS,
we generate alternative plans in the following two ways.
1. Generating multiple linearizations of the partial-order
plans. Recall from the earlier discussion that the ordering
constraints O only induce a partial ordering,
so the set of solutions are all linearizations of S (plan
steps) consistent with O. We are free to choose any linear
order consistent with the partial order. All possible
linear orders of a partial-order plan result in a family
of test cases. Multiple linearizations for a partial-order
plan were shown earlier in Figure 8.
2. Repeating the planning process, forcing the planner
to generate a different test case at each iteration.
V. Experiments
A prototype of PATHS was developed and several sets
of experiments were conducted to ensure that PATHS is
practical and useful. These experiments were executed on a
Pentium based computer with 200MB RAM running Linux
OS. A summary of the results of some of these experiments
is given in the following sections.
A. Generating Test Cases for Multiple Tasks
PATHS was used to generate test cases for Microsoft's
WordPad. Examples of the generated high-level test cases
are shown in Table III. The total number of GUI events in
WordPad was determined to be approximately 325. After
analysis, PATHS reduced this set to 32 system-interaction
and abstract operators, i.e., roughly a ratio of
This reduction in the number of operators is impressive
and helps speed up the plan generation process, as will be
shown in Section V-B.
Defining preconditions and effects for the 32 operators
was fairly straightforward. The average operator definition
required 5 preconditions and effects, with the most
complex operator requiring 10 preconditions and effects.
Since mouse and keyboard events are part of the GUI, three
additional operators for mouse and keyboard events were
defined.

Table

IV presents the CPU time taken to generate test
cases for MS WordPad. Each row in the table represents
a different planning task. The first column shows the task
the second column shows the time needed to generate
the highest-level plan; the third column shows the
average time spent to decompose all sub-plans; the fourth
column shows the total time needed to generate the test
case (i.e., the sum of the two previous columns). These
results show that the maximum time is spent in generating
the high-level plan (column 2). This high-level plan is then
used to generate a family of test cases by substituting alternative
low-level sub-plans. These sub-plans are generated
relatively faster (average shown in column 3), amortizing
the cost of plan generation over multiple test cases. Plan 9,
which took the longest time to generate, was linearized to
obtain 2 high-level plans, each of which was decomposed
to give several low-level test cases, the shortest of which
consisted of 25 GUI events.
The plans shown in Table III are at a high level of ab-
straction. Many changes made to the GUI have no effect
on these plans, making regression testing easier and less
expensive. For example, none of the plans in Table III
I
Some WordPad Plans Generated for the Task of Figure 2.
Plan Plan Plan
No. Step Action
contain any low-level physical details of the GUI. Changes
made to fonts, colors, etc. do not affect the test suite in
any way. Changes that modify the functionality of the
GUI can also be readily incorporated. For example, if the
WordPad GUI is modified to introduce an additional file
opening feature, then most of the high-level plans remain
the same. Changes are only needed to sub-plans that are
generated by the abstract operator FILE-OPEN. Hence the
cost of initial plans is amortized over a large number of test
cases.
We also implemented an automated test execution sys-
tem, so that all the test cases could be automatically executed
without human intervention. Automatically executing
the test cases involved generating the physical
mouse/keyboard events. Since our test cases are represented
at a high level of abstraction, we translate the high-level
actions into physical events. The actual screen coordinates
of the buttons, menus, etc. were derived from the
layout information.
B. Hierarchical vs. Single-level Test Case Generation
In our second experiment, we compared the single-level
test case generation with the hierarchical test case generation
technique. Recall that in the single-level test case


IV
Time Taken to Generate Test Cases for WordPad.
Task Plan Sub Total
No. Time Plan Time
(sec) Time (sec)
3 3.17 0.00 3.17
9 40.47 0.04 40.51
generation technique, planning is done at a single level of
abstraction. The operators have a one-to-one correspondence
with the GUI events. On the other hand, in the
hierarchical test case generation approach, the hierarchical
modeling of the operators is used.
Results of this experiment are summarized in Table V.
We have shown CPU times for 6 different tasks. Column 1
shows the task shows the length of the
test case generated by using the single-level approach and
Column 3 shows its corresponding CPU time. The same
task was then used to generate another test case but this
time using the hierarchical operators. Column 4 shows the
length of the high-level plans and Column 5 shows the time
needed to generate this high-level plan and then decompose
it. Plan 1 obtained from the hierarchical algorithm expands
to give a plan of length 18, i.e., exactly the same plan obtained
by running its corresponding single-level algorithm.
The timing results show the hierarchical approach is more
efficient than the single-level approach. This results from
the smaller number of operators used in the planning problem

This experiment demonstrates the importance of the hierarchical
modeling process. The key to efficient test case
generation is to have a small number of planning operators
at each level of planning. As GUIs become more com-
plex, our modeling algorithm is able to obtain increasing
number of levels of abstraction. We performed some exploratory
analysis for the much larger GUI of Microsoft
Word. There, the automatic modeling process reduced the
number of operators by a ratio of 20 : 1.
VI. Related Work
Current tools to aid the test designer in the testing process
include record/playback tools [20], [21]. These tools
record the user events and GUI screens during an interactive
session. The recorded sessions are later played back
whenever it is necessary to recreate the same GUI states.
Several attempts have been made to automate test case
generation for GUIs. One popular technique is programming
the test case generator [22]. For comprehensive test-
ing, programming requires that the test designer code all
Comparing the single level with the hierarchical approach.
'-' indicates that no plan was found in 1 hour.
Single level Hierarchical
Task Plan Time Plan Time
No. Length (sec.) Length (sec.)
4 26 3312.72 6 7.18
possible decision points in the GUI. However, this approach
is time consuming and is susceptible to missing important
GUI decisions.
A number of research efforts have addressed the automation
of test case generation for GUIs. Several finite-state
machine models have been proposed to generate test
cases [23], [24], [25], [26]. In this approach, the software's
behavior is modeled as a FSM where each input triggers
a transition in the FSM. A path in the FSM represents a
test case, and the FSM's states are used to verify the soft-
ware's state during test case execution. This approach has
been used extensively for test generation for testing hardware
circuits [27]. An advantage of this approach is that
once the FSM is built, the test case generation process is
automatic. It is relatively easy to model a GUI with an
FSM; each user action leads to a new state and each transition
models a user action. However, a major limitation of
this approach, which is an especially important limitation
for GUI testing, is that FSM models have scaling problems
[28]. To aid in the scalability of the technique, variations
such as variable finite state machine (VFSM) models have
been proposed by Shehady et al. [28].
Test cases have also been generated to mimic novice users
[7]. The approach relies on an expert to manually generate
the initial sequence of GUI events, and then uses genetic
algorithm techniques to modify and extend the sequence.
The assumption is that experts take a more direct path
when solving a problem using GUIs whereas novice users
often take longer paths. Although useful for generating
multiple test cases, the technique relies on an expert to
generate the initial sequence. The final test suite depends
largely on the paths taken by the expert user.
AI planning has been found to be useful for generating
focused test cases [29] for a robot tape library command
language. The main idea is that test cases for command
language systems are similar to plans. Given an initial
state of the tape library and a desired goal state, the planner
can generate a "plan" which can be executed on the
software as a test case. Note that although this technique
has similarities to our approach, several differences exist: a
major difference is that in [29], each command in the language
is modeled with a distinct operator. This approach
works well for systems with a relatively small command
language. However, because GUIs typically have a large
number of possible user actions, a hierarchical approach is
needed.
VII. Conclusions
In this paper, we presented a new technique for testing
GUI software, and we showed its potential value for the
test designer's tool-box. Our technique employs GUI tasks,
consisting of initial and goal states, to generate test cases.
The key idea of using tasks to guide test case generation is
that the test designer is likely to have a good idea of the
possible goals of a GUI user, and it is simpler and more
effective to specify these goals than to specify sequences
of events that achieve them. Our technique is unique in
that we use an automatic planning system to generate test
cases from GUI events and their interactions. We use the
description of the GUI to automatically generate alternative
sequences of events from pairs of initial and goal states
by iteratively invoking the planner.
We have demonstrated that our technique is both practical
and useful by generating test cases for the popular MS
WordPad software's GUI. Our experiments showed that the
planning approach was successful in generating test cases
for different scenarios. We developed a technique for decomposing
the GUI at multiple levels of abstraction. Our
technique not only makes test case generation more intu-
itive, but also helps scale our test generation algorithms for
larger GUIs. We experimentally showed that the hierarchical
modeling approach was necessary to efficiently generate
test cases.
Hierarchical test case generation also aids in performing
regression testing. Changes made to one part of the GUI
do not invalidate all the test cases. Changes can be made
to lower level test cases, retaining most of the high-level
test cases.
Representing the test cases at a high level of abstraction
makes it possible to fine-tune the test cases to each implementation
platform, making the test suite more portable.
A mapping is used to translate our low-level test cases to sequences
of physical actions. Such platform-dependent mappings
can be maintained in libraries to customize our generated
test cases to low-level, platform-specific test cases.
We note some current limitations of our approach. First,
the test case generator is largely driven by the choice of
tasks given to the planner. Currently in PATHS, these
tasks are chosen manually by the test designer. A poorly
chosen set of tasks will yield a test suite that does not provide
adequate coverage. We are currently exploring the
development of coverage measures for GUIs. Second, we
depend heavily on the hierarchical structure of the GUI for
efficient test case generation. If PATHS is given a poorly
structured GUI then no abstract operators will be obtained
and the planning will depend entirely on primitive opera-
tors, making the system inefficient. Third, our approach
must be used in conjunction with other test case generation
techniques to adequately test the software as is generally
the case with most test case generators.
One of the tasks currently performed by the test designer
is the definition of the preconditions and effects of the op-
erators. Such definitions of commonly used operators can
be maintained in libraries, making this task easier. We are
also currently investigating how to automatically generate
the preconditions and effects of the operators from a GUI's
specifications.
VIII.

Acknowledgments

This research was partially supported by the Air Force
Office of Scientific Research (F49620-98-1-0436) and by
the National Science Foundation (IRI-9619579). Atif
Memon was partially supported by the Andrew Mellon Pre-doctoral
Fellowship.
We thank the anonymous reviewers of this article for
their comments and Brian Malloy for his valuable sugges-
tions. A preliminary version of the paper appeared in the
Proceedings of the 21st International Conference on Software
Engineering, Los Angeles, May 1999 [30].



--R

"Why are human-computer interfaces difficult to design and implement?,"
"Integrating the MVC paradigm into an object-oriented framework to accelerate GUI application development,"
"User interface software tools,"

"ADDI: A tool for automating the design of visual interfaces,"
"Regression testing of GUI event interactions,"
"Toward automatic generation of novice user test scripts,"
"User interface design in the trenches: Some tips on shooting from the hip,"
"Iterative user-interface design,"
"Interactive scenarios for the development of a user interface prototype,"
"User interface design and evaluation - application of the rapid prototyping tool EMSIG,"
"The role of domain-specific knowledge in the planning as satisfiability framework,"
"Java GUI testing,"
"Conditional nonlinear planning,"
"An introduction to least commitment planning,"
"Recent advances in AI planning,"
"Ex- tending planning graphs to an ADL subset,"
"Fast planning through planning graph analysis,"
"HTN planning: Complexity and expressivity,"
"Stress Tests For GUI Programs,"
"Inte- grated data capture and analysis tools for research and testing an graphical user interfaces,"
"The black art of GUI testing,"
"Automated test generation from a behavioral model,"
"Testing software design modeled by finite-state machines,"
"Automated test generation, execution, and reporting,"
"A reduced test suite for protocol conformance testing,"
"Redundancy identifi- cation/removal and test generation for sequential circuits using implicit state enumeration,"
"A method to automate user interface testing using variable finite state machines,"
"Test case generation as an AI planning problem,"
"Using a goal-driven approach to generate test cases for GUIs,"
--TR

--CTR
Yanhong Sun , Edward L. Jones, Specification-driven automated testing of GUI-based Java programs, Proceedings of the 42nd annual Southeast regional conference, April 02-03, 2004, Huntsville, Alabama
Christoph Csallner , Yannis Smaragdakis, JCrasher: an automatic robustness tester for Java, SoftwarePractice & Experience, v.34 n.11, p.1025-1050, September 2004
Atif M. Memon , Mary Lou Soffa , Martha E. Pollack, Coverage criteria for GUI testing, ACM SIGSOFT Software Engineering Notes, v.26 n.5, Sept. 2001
Fevzi Belli , Christof J. Budnik, Test minimization for human-computer interaction, Applied Intelligence, v.26 n.2, p.161-174, April     2007
Atif M. Memon , Mary Lou Soffa, Regression testing of GUIs, ACM SIGSOFT Software Engineering Notes, v.28 n.5, September
Jessica Chen , Suganthan Subramaniam, Specification-based Testing for Gui-based Applications, Software Quality Control, v.10 n.3, p.205-224, November 2002
Avik Sinha , Carol Smidts, An experimental evaluation of a higher-ordered-typed-functional specification-based test-generation technique, Empirical Software Engineering, v.11 n.2, p.173-202, June      2006
Anneliese K. Amschler Andrews , Chunhui Zhu , Michael Scheetz , Eric Dahlman , Adele E. Howe, AI Planner Assisted Test Generation, Software Quality Control, v.10 n.3, p.225-259, November 2002
model-based test design technique for enhanced testing of domain-specific applications, ACM Transactions on Software Engineering and Methodology (TOSEM), v.15 n.3, p.242-278, July 2006
Qing Xie , Atif M. Memon, Designing and comparing automated test oracles for GUI-based software applications, ACM Transactions on Software Engineering and Methodology (TOSEM), v.16 n.1, p.4-es, February 2007
Manish Gupta , Jicheng Fu , Farokh B. Bastani , Latifur R. Khan , I. -Ling Yen, Rapid goal-oriented automated software testing using MEA-graph planning, Software Quality Control, v.15 n.3, p.241-263, September 2007
Atif Memon , Adithya Nagarajan , Qing Xie, Automating regression testing for evolving GUI software: Research Articles, Journal of Software Maintenance and Evolution: Research and Practice, v.17 n.1, p.27-64, January 2005
Atif Memon , Adithya Nagarajan , Qing Xie, Automating regression testing for evolving GUI software, Journal of Software Maintenance: Research and Practice, v.17 n.1, p.27-64, January 2005
GUI regression testing;automated test case generation;software testing;generating alternative plans;GUI testing;application of AI planning