=Paper= {{Paper |id=None |storemode=property |title=Testing Object-Oriented Configurators With ASP |pdfUrl=https://ceur-ws.org/Vol-958/paper4.pdf |volume=Vol-958 |dblpUrl=https://dblp.org/rec/conf/confws/FalknerSFR12 }} ==Testing Object-Oriented Configurators With ASP== https://ceur-ws.org/Vol-958/paper4.pdf

Testing Object-Oriented Configurators With ASP 1
Andreas A. Falkner and Gottfried Schenner 2, Gerhard Friedrich and Anna Ryabokon 3

Abstract. Testing is an important aspect of every software project. ASP solver runs this program and generates positive and negative test
For configurator applications it is equally important but often ne- cases which are translated back into test cases for the object-oriented
glected. This paper shows how to support testing object-oriented and configurator.
constraint-based configurators by automatically generating positive The following section defines necessary features of the configura-
and negative test cases using answer set programming (ASP). The tor and provides a brief introduction to the ASP systems. In Section 3
object-model of the configurator is mapped to ASP code; the con- we describe the approach in more details presenting the OO-ASP
straints to be tested are coded redundantly in ASP. Based on that, the mapping and examples for a small application. We show different
ASP solver generates appropriate test cases, which are then used for ways to reduce the number of generated test cases to a reasonable
unit testing in the object-oriented configurator. There are different size in Section 4 and conclude in Section 5.
strategies to improve this basic process, e.g. reduction of the number
of test cases with symmetry breaking.
2 Context
For this work, we used a configurator based on Generative Constraint
1 Introduction
Satisfaction (GCSP) which is a combination of object-oriented and
Testing is an important but often neglected aspect of every software constraint-based technologies. In general however, any system that
development project. Especially for object-oriented (OO) languages, complies to the definition of the following subsection can be used.
unit testing with a testing framework like JUnit [3] is well established The current target system is the Potassco ASP suite4 [12] - it could
and an integral part of development methods like Extreme Program- easily be replaced by another ASP system.
ming [4]. Unit testing frameworks are also gaining acceptance out-
side of object-oriented programming [9].
2.1 Object-oriented constraint-based configurator
A configurator is a software system that enables the user to con-
figure complex systems or services using predefined components. In The results of this paper can be applied to any existing configurator
a constraint-based configurator, constraints describe the conditions framework which complies to the following definitions.
which the configured system must satisfy. In order to test the correct-
ness of each individual constraint, the tester must provide positive Definition 1 (Knowledge Base, KB) The knowledge base of an
and negative test cases for it. A positive (negative) test case is a partial object-oriented and constraint-based configurator comprises an ob-
configuration where the constraint is satisfied (violated). Obviously, ject model and a set of constraints.
the test cases cannot be created by the solver of the configurator be-
cause one cannot use the possible faulty constraint to generate the test The KB specifies the relevant domain knowledge in a declarative
case. Therefore, the test cases currently must be created manually. way. The solver comprises a general constraint solver which reasons
There are different testing strategies such as black-box and white over that knowledge, e.g. checks consistency, searches solutions (i.e.
box testing ([16]. In black-box testing, the internal structure of the valid configurations), etc.
test object must not be known to the tester and the tests are devised
Definition 2 (Object Model) An object model contains classes,
according to the specification of the software system. In white-box
their inheritance hierarchy, attributes (Boolean, enumeration, inte-
testing, the internal structure is known and the tester designs the tests
ger), and associations (bidirectional).
to achieve a high test coverage. In practise both strategies should be
used because they tend to find different kind of errors. The object model describes the structure of the possible configu-
The basic idea of this paper is to semi-automatically generate test rations, including the multiplicities (cardinalities) of the parts. It can
cases for object-oriented configurators by first translating the con- be specified by an UML class diagram [17].
figurator’s knowledge base (without the constraints to be tested) to
an answer set programming (ASP) program. The constraints to be Definition 3 (Configuration) A configuration is an instantiation of
tested are then coded manually in ASP. Implementing the same con- the object model.
straint both in Java and ASP achieves the necessary diversity to de-
tect conceptional errors (similar to N-Version programming [1]). The Without loss of generality, only instances of leaf classes (classes
1 This work has been developed within the scope of the project RECONCILE
without subclasses) are allowed in a configuration. For the course of
(reconciling legacy instances with changed ontologies) and was funded by this paper, it is assumed that the configurator maintains one current
FFG FIT-IT (grant number 825071). configuration. In an interactive configurator, the user would manipu-
2 Siemens AG Österreich, Vienna, Austria firstname.{middleinitial.}last-
late the current configuration by adding/deleting objects and setting
name@siemens.com
3 Universität Klagenfurt, Austria firstname.lastname@aau.at 4 http://potassco.sourceforge.net
attributes and associations until a valid configuration is found. Alter- 3 Test case generation
natively the constraint solver can be used to extend a configuration
to a valid configuration. Constraints are used to describe the valid Figure 1 shows the main use-case of our approach. To generate test
configurations of the configurator. cases for a specific constraint, one identifies the fragment of the ob-
ject model relevant for the constraint. Using a generic OO-ASP map-
Definition 4 (Constraint) A constraint is a condition which every ping, described in the next section, this fragment is translated into an
valid configuration must satisfy. ASP program capable of enumerating all (up to a given upper bound)
instantiations of the object model i.e. all possible configurations.
This is a very general definition of the concept constraint. To make
our approach broadly applicable, no special constraint techniques
like domain-filtering, constraint propagation, etc. are required. A
constraint can be thought of as an invariant constraint in UML/OCL.
In its simplest form, constraints are Boolean methods of an object-
oriented language defined over the current configuration. From a
knowledge engineering view, constraints should correspond to some
requirements that the product to configure must satisfy. The scope of
a constraint can range from simple expressions like ’wheel1.size =
wheel2.size’ to ’The light-system of this vehicle is configured cor-
rectly’ (represented by some complex code accessing sub-parts and
their properties).

2.2 Answer Set Programming
Answer set programming is an approach to declarative problem
solving which has its roots in logic programming and deductive Figure 1. Generation of test cases
databases. This is a decidable fragment of first-order logic extended
with default negation, aggregation and weight constraints. ASP al-
lows modeling of a variety of search and optimization problems in a
declarative way [13, 7, 5] using model-based problem specification Since the main purpose of our approach is to detect conceptual
methodology. Efficient ASP solvers allow fast identification of solu- errors, the tester has to reimplement the constraint to be tested in
tions that correspond to answer sets of a program. Recent examples ASP, based on the requirements describing the constraint. Although
include areas such as molecular biology, decision support and plan- possible, one cannot automatically translate the constraint from the
ning. The DLV system [15] was used to plan shifts at Gioia-Tauro OO configurator to ASP because an automatic translation would also
Seaport which reduced the time required to define working teams’ translate the errors in the constraint. For the same reason the tester
assignments from hours to just a few minutes. A Potassco [12] pro- should be unaware of the implementation of the constraint in the
gram is able to detect inconsistencies in large biological networks. object-oriented configurator. This process implements a black-box
Since configuration problems are a type of combinatorial (opti- testing strategy like in traditional software engineering.
mization) problems, ASP was used by Soininen et al. [18] in their ap- The generated ASP code and the ASP definitions for the constraint
proach which was one of the earliest industrial applications of ASP. are used to compute answer sets that represent positive and negative
This first approach to the configuration problem was extended by test cases. These answer sets are then translated back into an object-
Friedrich et al. [10] to both configuration and reconfiguration cases. oriented configuration and used in unit tests for the constraint.
Recently, Gebser et al. [11] have suggested a novel ASP based mod-
eling approach to configuration support of a Linux package manage- 3.1 OO-ASP Mapping
ment system.
This work uses the following language constructs of Potassco To illustrate the approach, a simple example domain for configuring
(similar constructs are available in DLV): bicycles (Figure 2) is used. A bicycle has a frame, two wheels and
optional lights. A possible configuration can contain multiple bikes
• constant: lower-case string or number of different types, wheel sizes, etc. A valid configuration consists of a
• variable: upper-case string or collection of correctly configured bicycles as defined by the allowed
• predicate: predicatename(A1 , . . . , An ) with each Ai being a domains of the attributes (e.g. type), the given cardinalities of the
constant or variable associations (e.g. 0..1 for the lights), and two explicit constraints:
• condition: P : C (with P and C being predicates) generating a set
of ground instances for P corresponding to the existence of ground • constraintWheelsize disallows wheels of different sizes.
instances of C • constraintLights is complexer and requires that city bikes have
• (counting) aggregate: L{A1 , . . . , An }U (with L being a lower lights, that racing bikes do not have lights, that mountain bikes
bound, U an upper bound, and each Ai a predicate possibly gen- may only have battery lights, and that the Boolean attribute
erated by a condition) stating that the number of ground instances hasLights must correspond to the existence of a Lights instance.
Ai shall be within the bounds
The object model is mapped to ASP according to the following
• fact: A0 . with A0 being a predicate
schema:
• rule: A0 :-L1 , . . . , Ln . with A0 and Li being predicates or aggre-
gates, Li possibly negated • Every class C is mapped to two unary predicates
• constraint: :-L1 , . . . , Ln . with Li being predicates or aggregates, (X) and Domain(X). The do-
possibly negated main predicates are needed to describe the possible instances of a
wheelDomain(202).
wheelDomain(203).

Examples of user-defined maximum of instances and of facts gen-
erated by the solver as part of a test case like in Figure 5:

bicycle(1).
bicycle2wheel(1,201).
bicycle2wheel(1,202).
wheel(201).
wheelSize(201,24).
wheel(202).
wheelSize(202,25).
Figure 2. UML-diagram for bikeshop example In order to be able to enumerate every possible configuration, the
following additional ASP code is generated:

class - similar to variables to be activated in conditional constraint 1. For every class C, the instances up to the given maximal number
satisfaction problems. The maximal number of instances is are generated by:
defined manually via predicate MaxInstances(X).
0{(X):Domain(X)}MAX :-
Instances are identified by integers values.
MaxInstances(MAX).
• Every attribute ATTR of class C is mapped to a binary predicate
(X,Y) where X is an integer representing an in- Example:
stance of class X and Y is a possible value of attribute ATTR.
• Every association ASSOC between class C1 and C2 is mapped to 0{bicycle(X):bicycleDomain(X)}MAX :-
a binary predicate (X,Y), where X and Y are bicycleMaxInstances(MAX).
integers representing instances of class C1 and C2.
2. For every attribute ATTR of class C and possible values V1..Vn,
The mapping is controlled by an XML file. It can be used to ignore one rule is needed to ensure exactly one value:
irrelevant information, e.g. the attribute type of the frame. The fol-
lowing excerpt shows those parts of the mapping which are needed 1{(X,V1),...,
for constraintWheelsize. (X,Vn)}1 :- (X).

Example:
bikeshop.kb.Bicycle
1{wheelSize(X,20),...,wheelSize(X,28)}1 :-
bicycle
wheel(X).
...
3. For every association ASSOC between C1 and C2 and cardinality
wheels restrictions L..U, a rule is generated for the lower bound:
bikeshop.kb.Wheel
{(X,Y):
bicycle2wheel Domain(Y)} :- (X).

The upper bound of the association is checked with a constraint:

bikeshop.kb.Wheel :- (X), U+1{(X,Y):
wheel Domain(Y)}.
Example (upper bound = lower bound = 2):
size
wheelSize 2{bicycle2wheel(X,Y):wheelDomain(Y)} :-
bicycle(X).
:- bicycle(X),
3 {bicycle2wheel(X,Y):wheelDomain(Y)}.
By this mapping the Java class Bicycle is mapped to the unary
predicate bicycle, class Wheel to predicate wheel, its attribute size to 4. Especially for big domains, some basic symmetry breaking con-
the binary predicate wheelSize, and the association between Bicycle straints are required to avoid explosion of the number of generated
and Wheel to the binary predicate bicycle2wheel. test cases. Since the instances of a class are interchangeable we
Example of generated facts (for the listed part of the mapping): disallow usage of instances with a higher ID unless all instances
with a lower ID are used as well:
bicycleMaxInstances(1).
bicycleDomain(1). :- Domain(X), Domain(Y),
wheelMaxInstances(3). X(Y), not (X).
wheelDomain(201).
Example: bicycle2wheel(X,W1),
bicycle2wheel(X,W2),
:- wheelDomain(W1), wheelDomain(W2), W1!=W2,
W1> tcs; The alternative is to use advanced filtering techniques like symmetry
tcs = generateTestcases("testpositive"); breaking.
for (Set answerSet : tcs) {
createConfigurationFor(answerSet);
4.1 Symmetry breaking
Bicycle bike = getBicycles().get(0);
IConstraint c = For black-box testing in software engineering, techniques such as
bike.getConstraint(CONSTRAINTWHEELSIZE); equivalence partitioning and boundary value analysis have been de-
assertEquals(Boolean.TRUE,c.getVal()); veloped to reduce the number of test cases [16]. These techniques
} define equivalence classes for the input data and test only one value
tcs = generateTestcases("testnegative"); from every equivalence class.
for (Set answerSet : tcs) { For constraint-based systems a similar effect can be achieved by
createConfigurationFor(answerSet); defining equivalence classes over the possible configurations by us-
Bicycle bike = getBicycles().get(0); ing symmetry breaking techniques. For instance, in the positive test
IConstraint c = cases for constraintWheelsize, the actual value of the wheel size is ir-
bike.getConstraint(CONSTRAINTWHEELSIZE); relevant as long as the values are all the same (assuming a reasonable
assertEquals(Boolean.FALSE,c.getVal()); implementation). For negative test cases, at least two different values
} are needed, but it does not matter which values are actually chosen.
} Detection of the equivalence classes for an ASP program is done
by reducing it to the colored graph automorphism problem [6]. In
If an assert fails (i.e. a test case reports a discrepancy) then the this case, the grounded program is represented as a colored graph.
reason for it has still to be found. For example, consider the follow- The symmetry breaking tool is searching for such transformations
ing faulty Java implementation of the constraint. Since it returns true of the graph (permutation) that map vertices of it to vertices of the
for the counterexample, we know there is a discrepancy between the same color. The coloring schema in [6] allows to identify permuta-
ASP and the OO implementation of the constraint. Looking at the tions of graph vertices corresponding to equivalent grounded atoms,
Java code below it is easy to identify the error. Due to a typing error, e.g. wheels of different sizes, in a program. The permutations are
w2 is never referenced. used by the preprocessor SBASS5 [6] to generate symmetry break-
ing constraints that introduce a lexicographic order on elements of a
solution space. The symmetry breaking constraints are added to the
// in class Bicycle
grounded program and the result is forwarded to the solver.
public boolean constraintWheelsize() {
Roughly speaking, in the case of wheel sizes, constraints will re-
List wheels = getWheels();
quire to use wheels of size 20 first, since 20 is lexicographically the
if (wheels.size()!=2) { return false; }
smallest value. Only if it is impossible to find a configuration with
Wheel w1 = wheels().get(0);
wheels of the size 20, the solver will try the size 21 and so on.
Wheel w2 = wheels().get(1);
Inclusion of the preprocessing step in the testing tool chain reduces
return w1.getSize()==w1.getSize();
the number of possible configurations for the bicycle example (with-
}
out coding the two constraints in ASP) from 1459 to 129. For the
test case generation example for constraintWheelsize as described in
In many cases, comparing the two implementations (i.e. static Section 3.2, execution of SBASS reduces the number of positive test
analysis) is sufficient for identifying an error. If two constraint im- cases from 163 to 13. Although the number of test cases can be re-
plementations use different parts of the model this is an indication of duced drastically by symmetry breaking, one still has to ensure that
an error. For instance, if one constraint depends on an attribute value the coverage of the created test cases is enough to find potential er-
and the other does not then there is a high chance that the first is more rors.
specific than the other. For instance, consider the case where the knowledge base is mod-
Note that an OO implementation of the constraint in the configura- ified by allowing bicycles to have more than two wheels (i.e. tricy-
tor is not needed to generate test cases with our approach. Therefore, cles, etc). The following faulty constraint implementation works, if
this method can also be used for the test-first approach of Test Driven
5 http://potassco.sourceforge.net/labs.html
Development [2].
the differences in wheel sizes always occur in the first two wheels. If knowledge bases of our real-world configurators (>100 classes) into
symmetry breaking creates only such test configurations, one can no ASP. We expect that we have to refine the techniques of Section 4 in
longer detect the error in the constraint implementation. order to get sufficient performance.
The current approach cannot be used for test cases containing a
// faulty implementation, but works lot of components. For instance, the bikeshop domain already uses
// if the "first" 2 wheels are of same size more than 1GB of memory if the domain size is set to more than 50.
public boolean constraintWheelsize() { Fortunately, test cases for single constraints usually do not involve
List wheels = getWheels(); hundreds of components.
for(int i = 0 ; i