Test-Case Design by Feature Trees
Takashi Kitamura, Ngoc Thi Bich Do, Hitoshi Ohsaki,
Ling Fang, Shunsuke Yatabe
National Institute of Advanced Industrial Science and Technology (AIST){t.kitamura,do.ngoc,hitoshi.ohsaki,fang-ling,shunsuke.yatabe}@aist.go.jp

Abstract. This paper proposes a test-case design method for black-box
testing, called “Feature Oriented Testing (FOT)”. The method is realized by applying Feature Models (FMs) developed in software productline engineering to test-case designs. We develop a graphical language
for test-case design called “Feature Trees for Testing (FTT)” based on
FMs. To firmly underpin the method, we provide a formal semantics
of FTT, by means of test-cases derived from test-case designs modelledwith FTT. Based on the semantics we develop an automated test-suite
generation and correctness checking of test-case designs using SAT, as
computer-aided analysis techniques of the method. Feasibility of themethod is demonstrated from several viewpoints including its implementation, complexity analysis, experiments, a case study, and an assistanttool.

Key words: black-box testing, combination testing, SAT-based analysis

1

Introduction

In black-box testing (BBT) test cases are designed by analysing the input domainof the system under test (SUT) often according to the system’s speciﬁcation. The
Classiﬁcation Tree Method (CTM) [5, 9–11] is one of the-state-of-the-art test-casedesign methods for BBT. It is a model-based and combination testing method; i.e.,
test cases are designed as a visual model with a given diagram-based language,
and test cases are generated automatically from such a model using combination
techniques. Due to its nice characteristics as a testing method, CTM is often used
in industry including automotive industries [19]. However, for a better testing
method improvements can be considered from several perspectives such as its
theory, higher computer-aided analysis, eﬃciency of automated technologies, andmodelling paradigms.
Feature-Oriented Domain Analysis/Feature Models (FODA/FMs) is an analysis
method for software product lines (SPLs), ﬁrst proposed by Kang et al. [14]. Thismethod takes a model-based approach; i.e., an SPL is modelled with extended
and-or logical trees called “Feature Models (FMs)”, which enable systematic analysis in a top-down manner, together with their graphical representations of “Feature Diagrams”. In addition, useful information about the SPL can be derived
by applying analysis techniques to the models. A main characteristic of FMs is2

T. Kitamura, N.T.B. Do, H. Ohsaki, L. Fang, and S. Yatabe

its compact and visual representations by diagrams to capture SPLs as well as avariety of analysis techniques. So far fruitful research results of FMs have been
made in research and industry, including various model designs [20], semantics[3, 17, 20, 21], various analysis operations such as consistency checking, diagnosis,
validations, refactoring, and so on (as summarized in [2, 17]). Also such analysis operations are carried out on various logic paradigms such as propositional
logic [1, 13, 16, 22], description logic [8] or constraint programming [3] as well as
algorithmic approaches [4, 23].
In this work, we propose a test-case design method by applying FMs, called“Feature Oriented Testing (FOT)”, identiﬁed as a model-based and combination
testing method for BBT. The aims of the work are three-fold: (1) to develop a testcase design language based on the model designs of FMs, which are characterizedwith the compact and visual representations by diagrams of extended and-or
logical trees, (2) to apply rich theories of FMs to the test-case design method
focusing on semantics, and (3) to apply computer-aided analysis techniques of
FMs to the test-case design method, to retrieve useful information for test-casedesigns.
The main contributions of this paper are two-fold: (A) to realize these aims as
a test-case design method, and (B) to demonstrate the method’s feasibility fromseveral viewpoints. For (A), ﬁrst we analyze the requirements for developinga test-case design language, and design such a language as “Feature Tree for
Testing (FTT)” that suits the test-case design purpose based on various designsof FMs proposed in the literature [20]. Then we build a theoretical foundationof FTT by providing its formal syntax and semantics; which makes a basis ofreliability and computer-aided analysis. Further, we develop two kinds of logicbased automated analysis techniques for FTT using a SAT solver: a test-suite
generation and correctness checking of test-case designs by FTT.
For (B), ﬁrst feasibility is shown from the viewpoint of reliability, which is an
important property as a testing method, by building formal semantics and proving the correctness of the test-case generation algorithm w.r.t. the semantics.
Feasibility is demonstrated from the viewpoint of computational cost on the automated analysis, by analyzing the computational complexity and by providing
experimental results. A case study is presented, where we apply FOT to test-casedesign for OSEK/VDX-OS (OSEK-OS), a standard real-time OS for automotives [18].
We also explain our GUI-based assistant tool for FOT. This show not only how
the method can be assisted by a tool, but also some essential techniques fortest-case designs of FOT using this tool.

2

A motivating example

Borrowing an example in [5], we design test cases for BBT for a computer visionsystem. As seen in Fig. 1, this system determines the size of various blocks
passing the camera of the system on a belt-conveyor. Fig. 2 shows a test-casedesign for BBT for the system by FOT. In FOT, an FM is used to design test
cases; i.e, analysis for test-case design proceeds using FTT by splitting up theTest-Case Design by Feature Trees

3

large

Fig. 1. Computer vision system for determining the size of building blocks
Blocks
size

large

small

color

blue
<<requires>>

green

shape

red

circletrianglesquare<<mutex>>equilateralisosceles

scaleneFig. 2. A simple and small test-case design using an FTT

input/(output) domain of the SUT with various test-relevant aspects, which we
also refer to as features.
The analysis of the input domain, i.e., the test-case design for the SUT, proceeds in a top-down manner with its root as the input domain of SUT, whichis “Blocks” here. First, “Blocks” are decomposed into features of their “size”,“color” and “shape”. In decompositions (decomp.), we distinguish them with
two kinds of orthogonal and alternative decomp. The “block” is decomposedwith an orthogonal decomp., as we regard its three sub-features are orthogonal
notions. We may also call such decomp. and-decomp., following the conventionof and-or trees and FMs. We clarify such decomp. explicitly in the diagram by
the dot on top of each feature.
Next these three decomposed sub-features are further decomposed into smaller
sub-features. For example, the “size” feature is decomposed into two sub-features:“small” and “large”. In this case, it is done with an alternative decomp., which
may be also called xor-decomp., by regarding the sub-features as alternatives to
one another. Compositions of this kind are clariﬁed in the diagram in the waythat the edges of a decomp., are tied up with a string. Similarly, the “color”
features are decomposed into “blue”, “green” and “red”, and “shape” into “circle”, “triangle” and “square” with alternative-decomp. The “triangle” feature isfurther decomposed into “equilateral”, “isosceles” and “scalene” alternatively, todesign test cases in a detailed way and hence inspect the system in more details.
Besides such decomp. relations between features, which form the parent-childrelations of trees, “mutex ” and “requires” relations drawn globally in the tree(i.e., crossing the tree) are found in the model in Fig 2. These represent constraints between features in the tree globally, which we call cross-tree constraints(CTCs), to exclude nonsense or undesired test cases according to given speciﬁcations. For example, assume in the above example, the following speciﬁcations are
given: (1) “There are no blocks whose color is red and whose shape is a triangle.”

4

T. Kitamura, N.T.B. Do, H. Ohsaki, L. Fang, and S. Yatabe

1. small, red, circle
2. small, blue, circle
3. large, green, circle
4. small, green, circle
5. small, blue, square
6. small, red, square

7. small, green, square
8. large, green, square
9. large, green, equilateral
10. small, blue, equilateral
11. small, green, equilateral
12. large, green, isosceles

13. small, green, isosceles
14. small, blue, isosceles
15. small, blue, scalene
16. large, green, scalene
17. small, green, scalene

Table 1. The test suite obtained from test-case design of Fig. 2(2) “If the size of blocks is small, then the color of the blocks is green.”. Dueto these speciﬁcations, it is nonsense and undesirable to prepare test cases forsuch cases. The CTCs clarify such nonsense test cases. The mutex (an abbr. for“mutually exclusive with”) constraint between the “red” and “triangle” featuresin Fig. 2 is drawn to cover speciﬁcation (1), and requires between the “small”
to “circle” feature to cover speciﬁcation (2). Note that each CTC aﬀects all thefeatures in the sub-tree of the features it involves. E.g., the mutex constraint
stipulates that “red” is mutex not only with “triangle” but also with all the
sub-features of the sub-tree: “equilateral”, “isosceles” and “scalene”.
The test-case design, shown as a diagram in Fig. 2, captures a set of test
cases; i.e., we can obtain a set of test cases (i.e., test suite) from the diagram.
Here, a test case is deﬁned as a set of features in the tree. Table 1 shows the test
suite obtained from the test-case design of Fig. 2. That is, the test suite derived
from the test-case design consists of ﬁfteen test cases; for example, test-case 1
indicates blocks whose size is “small”, color is “red”, is shape “circle”. Roughly,
test cases are derived from such test-case designs by recursively applying thefollowing standard interpretation of and-or logical tree; i.e., all the sub-featuresof and -decomp. or its descendants have to be in any test case, and exactly oneof the sub-features of xor -decomp. or its descendants have to be in any test case.
Besides, the test cases the CTCs are applied to are excluded. The rules to derive
test cases from the diagrams should be more detailed in an exact way, and weformally explain these rules in Section 4.

3

Feature Trees for TestingThis section develops a test-case design language based on FMs, called Feature
Tree for Testing (FTT), which we regard as the modelling language for test-casedesign in FOT. First we analyze requirements for such a language as a modelbased and combination testing method for BBT. According to them we design
such a language as FTT based on FMs, showing its design choices. Then based on
the design of FTT, the syntax and semantics of FTT are provided formally.
3.1

Requirements and design choices

Requirements Though the basic idea of FTT was seen in the previous section,
here we brieﬂy summarize the requirements analysis for developing a test-casedesign language for our test-case design purpose of model-based and combination
testing method for BBT, as follows:Test-Case Design by Feature Trees

5

1. The basic structure of FTT is designed as a tree; i.e., the tree structure isformed by an input-domain analysis of SUT by repeatedly decomposing itwith features from the root, which facilitates systematic test-case design in
a top-down manner.
2. Each decomp. of a feature (i.e., the input domain of SUT) should be distinguished by two kinds: orthogonal decomp., i.e., all the sub-features are
orthogonal notions to one another, and alternative decomp., i.e., all the subfeatures are alternative notions to one another.
3. Some kinds of constraint operators, imposed on globally (between any features crossing a tree), are equipped to exclude non-sense and undesired test
cases according to given speciﬁcations.
Design choices We design a language for test-case design as FTT to meet therequirements based on various variants of FMs proposed in the literature [20]. By
following [20] for a scheme of design choices of FMs, FTT is characterized as:
1. FTT are trees (, but not DAGs: Directed Acyclic Graphs).
2. FTT have the following two-kinds of decomp. operators:(a) and -decomp., to express orthogonal -decomp.
(b) xor -decomp., to express alternative-decomp.
3. FTT have the following constraint representations drawn globally in a tree:(a) requires; if a feature f requires a feature g, the inclusion of f in a test
case implies the inclusion of g in such a test case.
(b) mutex ; the two features related by the relation cannot be present simultaneously in a test-case.
Some other relations, often common in FMs such as “optional ”, “or -decomp.”
and “cardinality”, are not included in FTT, since straightforward interpretations
can not be given on the operators in our test-case design setting. The same is true
for other relations such as “generalization”, “specialization” and “implementedby” found in [15]. The language design of FTT is not same as any of the FMs listed
in [20], but similar to the original FM developed by Kang et al. [14]3.2

Syntax of Feature Trees for Testing

We give a formal syntax of FTT as a basis for the formal developments:
req mex

Definition 1. A feature tree is a tuple (F, r, L, ⇀, @, →, ←→) such that
– (F, r, ⇀) is a tree, where F is a set of features (as the nodes of a tree), r is
the root, and ⇀ is the parent-child relation on F ,• we say “feature f is the parent of g” and “g is a child of f ” if f ⇀ g,
– L(⊂ F ) is a set of leaf features,– @ is a function from F \ L to {and, xor},mex– ←→ is a symmetric and irreﬂexive binary relation over F ,req– −→ is an asymmetric and irreﬂexive binary relation over F .
2

6

T. Kitamura, N.T.B. Do, H. Ohsaki, L. Fang, and S. Yatabe

FTT are trees (F, r, ⇀) extended with several notions. First FTT are a variantof and-or logical trees. We realize this with “node-based design”, where eachfeature (i.e., node) of the tree except for leaf features is labeled with “and” or“xor”. The function @ : F \L → {and, xor}, which labels each (non-leaf) featureswith and or xor, is equipped for this. We call features “and-feature“ or “xorfeature” if it is associated with “and” and “xor” by @ respectively. Note that,
due to the design, “and ” and “xor”-edges shall not be mixed among the edges
out-going from a feature. The two kinds of CTCs of mutex and requires, whichmex
are another extension of FTT, are expressed by the binary relations “ ↔ ” andreq“ →” on F .

3.3

Semantics

An FTT captures a set of test cases. In other words, the semantics of an FTT isdeﬁned by way of a set of test cases derived from it; i.e., given an FTT, we
formally understand what it means by way of a set of test cases.
Definition 2 (Pre-model). A pre-model M ′ (∈ M′ ) of an FTT t is a subset ofits features: M ′ ∈ PF , where PX denotes the power set of X.
2Definition 3 (Model). A model M (∈ M) of an FTT t is a pre-model thatsatisﬁes the following conditions, and is noted as M |=′ t:
1. The root feature is in the model: r ∈ M ,2. If a feature is in a model, its parent is in the model too: f ∈ M ⇒ parent(f ) ∈ M ,3. If an and-feature is in a model, all its children are in the model too: f ∈M ∧ @(f ) = and ⇒ (∀g.f ⇀ g → g ∈ M ),4. If an xor-feature is in a model, exactly one of its children is in the model
too; f ∈ M ∧ @(f ) = xor ⇒ (∃!g.f ⇀ g ∧ g ∈ M ),reqmex
5. The model must satisfy all formulas from the CTCs set Φ(= ↔ ∪ →): ∀ϕ ∈mex
Φ.M |=′ ϕ, where “M |=′ f ←→ g” if f and g are not both in M , andreq“M |=′ f −→ g” if f is in M , g is in M too.
2
The deﬁnition of test case and test suite are given by way of the model.
Definition 4 (Test case and test suite). 1. A test case c is a subset of leaves:c ∈ PL. 2. A test case of the model M , noted M ◦ , is M ∩ L. 3. A test suite s
is a set of test cases: s = Pc ∈ PPL. 4. The test suite derived from an FTT t is
the set of test cases of models M satisfying t: JtK = {M ◦ | M |=′ t}2

4

SAT-based automated analysis of FTTThis section explains several SAT-based automated analysis techniques of FTT, as
computer-aided analysis techniques of FOT. An epoch in the research of FMs is theprovision of encoding FMs to a propositional (prop.) formula, which brings many
interesting logic-based analysis on FMs, often using technologies of SAT-solvers.
Applying these techniques to our setting, we develop SAT-based automated testsuite generation and correctness checking of test-case designs by FTT.

Test-Case Design by Feature Trees
Feature model relation

Corresponding formula(a) r is the root feature(b) p ⇀ c1(c) @(p) = and and p ⇀ crc1 → pp⇀c (c1 ∧ ¬c2 ∧ · · · ∧ ¬cn )

···
p→ 
(¬c1 ∧ ¬c2 ∧ · · · ∧ cn )¬(p ∧ q)p→q∨(d) @(p) = xor and p ⇀ c1 , · · · , p ⇀ cn
(e)
(f)

7

mex

p ←→ qreq
p −→ q

Table 2. The encoding rules trans of an FTT into prop. formulas
miniSat

An FTT

1.encord

Prop.
formula2.translate

Prop.
formulain CNF

3.ALLSAT

A set ofmodels

4. process

Test-suites

Fig. 3. The system for test-case generation

4.1

Propositional formulas encoding

Table 2 shows the encoding rules (trans) of an FTT to a prop. formula. Lemma 1
shows the rules are correct w.r.t. the semantics in Deﬁnition 4. The proof of thislemma is obvious, but it plays a critical role for guaranteeing the correctness of
our automated analysis techniques.
Lemma 1. For any FTT t, M |=′ t iﬀ M |= trans(t)4.2

2

A SAT-based automated test-suite generation

An algorithm design and early implementation First we derive the following theorem from Lemma 1:
Theorem 1. For any FTT t, JtK = {M ◦ | M |= trans(t)}.

2This theorem indicates that in order to obtain the test suite of a given FTT t
according to Deﬁnition 4, it suﬃces to follow the procedures of: (1) to derive
all the models that satisfy the prop. formula encoded from the FTT t i.t.o theclassical logic, and (2) to process each of the models by taking one that intersects
with the leaf nodes of the FTT and (3) to take the union of the processed models.
And the algorithm design follows this scheme.
The test-suite generation algorithm is displayed in Fig. 3. The input is an
FTT and the output is a set of corresponding test cases (i.e., a test suite). The
algorithm mainly consists of the following four components.
1. The ﬁrst component encodes an FTT to a prop. formula according to theencoding rules in Table 2.
2. The second is a conjunctive normal form (CNF) translator, which translates
a prop. formula into it in a CNF.

8

T. Kitamura, N.T.B. Do, H. Ohsaki, L. Fang, and S. Yatabe

3. The third is an all-solutions SAT-solver (ALLSAT), inputting the encoded formula of FTT in CNF, ﬁnds all models for it. We have implemented an ALLSAT using the blocking algorithm (which ﬁnds all models by iteratively callinga SAT solver while at each call blocking clauses which block ﬁnding a model
already found is added) by extending MiniSAT[6].
4. The fourth processes a set of models obtained from the ALLSAT, by taking
one that intersects with the leaf nodes of the FTT, and produces the test
suite by collecting the processed models (i.e., test cases).
Computational complexity To analyze the complexity of the test-case generation algorithm, we analyze the complexity of each component 1-4. Given an
FTT t, we denote the number of features as n.
1. The length of a formula derived by trans is the sum of sub-formulas byapplying each rule of (a)–(f). Thus it suﬃces to analyze rule (d), whichmakes the longest sub-formula among of (a)–(f) in Table 2. The length of a
sub-formula by (d) for an xor-decomp. with k-children is bound by O(k × k).
Both the number of children of any feature and that of xor-decomp. in t arebound by n − 1. Hence the length of a formula by trans is bound by O(n2 ).
2. We have implemented an algorithm to transform a prop. formula using thestandard laws of logical equivalences, and have produced a clause set that is
exponential w.r.t. the size of the original formula in the worst case.
3. The SAT-problem is NP-complete, and the worst time complexity of thealgorithm we use (i.e., MiniSAT[6, 12]) is O(2n ) where n indicates the numberof the prop. variables. Also the number of models for a given formula is boundby 2n . Hence, the complexity of ALLSAT is bound by 2n × O(2n ) ∈ O(4n ).
4. The complexity of the set intersection of two sets with size k is O(k 2 ). The
number of nodes and the leaf nodes of an FTT are bound by n. There are at
most 2n models. Hence, the complexity is bound by 2n ×O(n2 ) ∈ O(2n ×n2 ).
Hence the bottleneck of the algorithm is the component of CNF-transformation
and ALLSAT, whose complexity are exponential to the input FTT t.
Experimental results Besides the complexity analysis, we provide experimental results to show feasibility of the implementation from the viewpoint ofcomputational cost of FOT. According to the above analysis of computational
cost of the test-suite generation algorithm, we know that its bottleneck lies on
computing all the models using ALLSAT, which takes exponential time w.r.t. thesize of FTT. But in practice the computational cost is cheaper than the theoretical analysis. One reason is that the oﬀ-the-shelf SAT-solver we use, i.e., MiniSAT,
runs faster than the above analysis. Second, the number of the models for theformula encoded from an FTT is much less than 2n in real settings. Also, thenumber of test cases varies depending on the structures of FTT. The ratio of
and/xor -decomp. and the ratio of CTCs in an FTT mainly aﬀect the number oftest cases; i.e., the more and -decomp. and CTCs there are in an FTT, the less test
cases are derived. Table 3 shows an experimental result, presenting the time andTest-Case Design by Feature Trees

ctcr(%)
0
10
20
30
40

20
time (s)# test cases
time (s)# test cases
time (s)# test cases
time (s)# test cases
time (s)# test cases

0.09
120
0.04
92
0.03
75
0.01
26
0.01
13

Size of an FTT (n)
30
40
50
0.67
960
0.35
432
0.09
238
0.07
120
0.06
45

2.04
6912
0.82
2464
0.53
916
0.17
288
0.06
96

9.65
19008
3.65
8580
1.52
2710
0.51
880
0.12
122

9

60
20.43
43200
4.71
9160
2.01
4244
0.93
1666
0.14
168

Table 3. Experimental results

the number of test cases, where ctcr stands for the CTCs ratio (i.e., the ratio of
CTCs w.r.t the size of FTT). The experiments were conducted on a machine withan Intel Core2 Duo CPU P8700 @2.53 GHz, 2.96 GB of RAM and Windows 7.
4.3

SAT-based correctness checking of test-case designs

An important class of various computer-aided analysis techniques on FMs is correctness checking. Generally, correctness checking includes consistency checking
and detecting dead/common features. These notions are interpreted in the setting of test-case design as follows: an FTT, i.e., a test-case design, is inconsistent
if no test case can be derived from it; a feature is dead in an FTT if it does notappear in any of the test cases of the model derived from it; and a feature iscommon in an FTT if it appears in all the test cases derived from it.
Interestingly, these analysis operations on correctness checking can be reduced to a simple satisﬁability checking problem of a prop. formula. The consistency of a test-case design by a FTT can be examined by checking the satisﬁabilityof the formula ϕ encoded from the FTT (t), i.e., ϕ = trans(t). Existence of a deadfeature f in an FTT can be examined by checking the satisﬁability of the formulaϕ ∧ f ; i.e., f is a dead feature if ϕ ∧ f is unsatisﬁable. Similarly, existence of acommon feature f in a model can be examined by checking the satisﬁability ofϕ ∧ ¬f ; i.e., f is a common feature if the formula is unsatisﬁable.
We have introduced these analysis operations on correctness checking of testcase designs in FOT, which help validation of test-case designs by FTT. As shownin the next section, the consistency checking, especially detecting dead features,are quite useful for ﬁnding defects in test-case designs since they often entertest-case designs and their existences are undesirable.

5

A case study : A test-case design for OSEK-OS

To demonstrate feasibility of FOT in real practice, we show a case study where
we applied FOT to test case design for the OSEK-OS[18, 19], a real-time OS for10

T. Kitamura, N.T.B. Do, H. Ohsaki, L. Fang, and S. Yatabe

activateTask

Execution
level

Task

<<mutex>><<mutex>>
Task ID

Task

ISR2

<<mutex>><<mutex>><<mutex>>type

statusmax
activation

priorityvalid
No
constraints

Priemptive

invalid
ISR3

basic

extended

high

equiv

not
reachedreachedreadysuspend
Yes

No

Yes

No

run

wait

low

<<mutex>>

Fig. 4. A test-case design by FTT for API “activateTask” in OSEK-OS

automotives. Speciﬁcally, using FTT we make a test-case design for an API function “activateTask ”, which transfers a task speciﬁed with parameter “TaskID”
from the “suspended ” state into the “ready” state. We analyzed the speciﬁcation[18], and made its test-case design as in Fig. 4. The ﬁgure shows the test-casedesign with an FTT that consists of 30 features and 6 CTCs, and 192 test cases
are obtained from it.
Several observations obtained from the case-study are as follows:
1. Test-case designs with a variant of and-or tree are easily accepted by developers in practice because and-or trees are a common analysis techniqueand close to human thinking. Also this analysis technique using and-or trees
can allow them to focus on designing test cases released from direct edits onlogical formulas, which are often error-prone.
2. Eﬃciency of the automated analysis techniques of FOT, i.e, automated testsuite generation and correctness checking, whose experimental results areshown in Tab. 3, is practical enough in our case studies.
3. Unfortunately, FTT is not expressive enough to express any desired test suitein any settings, because test-case designs in real development are sometimes
extremely detailed and beyond the expressiveness of FTT. As a result, manual
arrangements of test cases such as to add, delete and modify test cases are
required to cover some detailed cases. But this should not be taken as a
critical defect of FOT, since CTM, which is the state-of-the-art method oftest-case design for BBT often used in real developments, also inherently has
this aspect of expressiveness. (See related discussions in Section 8.)
4. Detecting dead features for correctness checking of test-case designs by FTT isquite useful in practice. Test-case designs are often complex, and hence prone
to contain deﬁciencies. In the test-case design in Fig. 4, the “invalid ” and“No” (under “Preemptive”) features are the dead features. Existence of deadfeatures indicates that some errors may be contained in the test-case design,or these dead features may have to be taken care of by manual arrangements.
5. Test-case designs by FTT can be used for test documentations such as asystem speciﬁcation for testing. These designs can also be used as communication media among developers, and as evidence for certiﬁcation. The high

Test-Case Design by Feature Trees

11

Test-case 3 consists of the “ISR2”, “Valid”, “ready”,“basic”, “high” and “not_reached” feature

CTCs are expressed as attachments to afeature; e.g, the 5 CTCs related to the“invalid” feature are listed under the feature

Test-case design by an FTT

An automaticallygenerated test-suite

Fig. 5. The GUI tool for FOT

readability of FTT, achieved by the compact and visual representation by
diagrams, and by the formal semantics to unify interpretation of FTT contributes to the aspect of documentations.
6. The readability of the diagram representations of FTT can be preserved, evenwith many CTCs drawn all over the tree, together with the GUI-based assistanttool. We explain the tool’s support for readability in the next section.

6

Tool development

We have developed a GUI tool to assist FOT. This section will brieﬂy explain thistool. The tool development shows not only our current status of the developmentof FOT, but is also essential in the test-case design method of FOT.
Describing FTT via the GUI. Fig. 5 shows the main GUI of the tool. It is separated
into two panels: the left-hand-side panel where users describe and input an FTT,
and the right-hand-side panel which displays the automatically generated test
cases in a matrix form.
In designing test cases by describing an FTT via the GUI, several advantages
ascribed to the properties of FTT become possible. First, the GUI prevents inputting illegitimate FTT w.r.t. the deﬁned syntax in Deﬁnition 1. That is, theGUI lets users input only a legitimate FTT, which then allows them to concentrate on the logic of test-case designs. The second advantage centers on scalability
w.r.t. the readability of the diagram representations of FTT. As shown in Fig. 5in the FTT description of in the GUI, each CTC is expressed as an attachment tofeatures involved in the description. Due to the GUI design, even with a numberof CTCs, the diagram representation keeps readability.

12

T. Kitamura, N.T.B. Do, H. Ohsaki, L. Fang, and S. Yatabe

Folding/Unfolding of sub-trees by double-clicking

Fig. 6. The number of test-cases can be controlled by folding/unfolding sub-trees

Controlling the number of test cases ﬂexibly In general, the system quality guaranteed by testing and its cost is a trade-oﬀ. That is, the more the cost for detailed
testing is allowed, the higher the quality of the system is guaranteed. On theother hand, the resources for testing are limited in real developments. Therefore,
it is desirable for a testing method to be able to ﬂexibly control system quality
guaranteed by testing by depending on its aﬀordable resources.
FOT is equipped with such a mechanism; i.e., it is equipped with a device
to ﬂexibly control the number of test cases. The device is realized by using a
notion of abstraction on tree structures in the FTT such as folding and unfolding
sub-trees. Fig. 6 demonstrates this device in the tool, using the example of thecomputer vision system. The left side in Fig. 6 shows the test-case design forthe computer vision system in Section 2 using the tool, where 17 test cases
are obtained. The number can be ﬂexibly reduced, for instance, by abstracting
the “triangle” feature by folding its sub-tree; i.e., the number of the test cases
obtained from the tree whose “triangle” sub-tree is folded, can be reduced to 11.

7

Discussions and Related WorkCTM (Classiﬁcation Tree Method ) [5, 9–11] is a model-based and combination-

based test-case design method for BBT; i.e., a test case is designed as a modelof a tree diagram, and test cases are obtained automatically from it using a
combination technique. In CTM, the model to represent a test-case design consistsof the three separate description components: (1) a “classiﬁcation-tree diagram”,
which is a tree-based diagram to represent the basic structure of test-case design,(2) “combination rules” to deﬁne combination rules based on the classiﬁcationtree diagram, and (3) “dependency rules”, written in prop. logic, to exclude
nonsense test cases. Fig. 7 shows a descriptive example of a test-case design forthe computer vision system using CTM to produce the same test suite in Tab.
1. FOT can be seen as a comparable test-case design method to CTM, but its
advantages over CTM are the following:Test-Case Design by Feature Trees

13

Classification diagram

Combination rule

Dependency ruleFig. 7. Test-case design for the computer vision system in CTM

The ﬁrst advantage is on the modelling paradigm for test-case designs. In
FOT, a test-case design is represented as an FTT in a single diagram based on

and-or logical trees. We inherit the single and compact design of FMs, often recognized as a characteristic of FMs, in FTT, which brings higher readability. The
model design of FTT requires less complex descriptions than CTM, bringing higher
productivity; i.e., complex descriptions together with direct edits of the logicalformula is often a main barrier preventing wider adoption of such methods inreal developments. Also, the single representations of FTT achieve higher maintainability; the separate descriptions in CTM often require eﬀorts because suchchanges in a description component may aﬀect the others. Also, the model design
based on and-or trees achieves higher availability as a common and traditional
analysis technique. In fact, the model design is highly inspired by Fault Tree
Analysis (FTA) [7], which is an established analysis technique based on and-or
trees in reliability engineering. Also, the logic-based model of FTT facilitates thelogic-based analysis in FOT.
On the other hand, theoretically CTM is more expressive than FTT. The difference lies on the expressiveness of a description device to exclude nonsense test
cases: i..e, CTCs in FTT, which consists of the two operators mutex and requires,and the dependency rules in CTM, which deals with a full prop. formula. But
from our case studies, the advantage of the expressiveness of CTM is mostly intheory. From the case studies, we learned only simple rules are needed to realize such devices, and CTCs are expressive enough for this purpose. In place of
expressiveness, FTT realizes the above-mentioned nice properties such as readability, productivity, and maintainability, etc. We have mentioned in Section 6that FTT may not be expressive enough for some settings. But this is due to thetree structure of FTT rather than due to the expressiveness of CTCs, and hence
CTM also has this aspect.
Second, FOT has a formal semantics, which is missing in CTM. The semantics
makes a basis for reliability by preventing the “ambiguity problem” which causes
faulty developments. In addition, FOT has the advantage that due to its compact
model design it can be formalized with a small set of constructs. Conciseness is14

T. Kitamura, N.T.B. Do, H. Ohsaki, L. Fang, and S. Yatabe

not only important in a scientiﬁc sense, but also in an engineering sense since it
requires less cost to learn the method and makes the method easy to extend.
Third, a SAT-based algorithm is designed and implemented for automatedtest-suite generation. An obvious advantage of the design is eﬃciency. The design
can beneﬁt from recent advances in theory and in the techniques of SAT-solvers[6]. For instance, FOT takes only about 20 seconds to generate 64200 test cases,
while CTM tool[10, 11] takes 73 minutes in a similar setting. Another advantage isthat the correctness of the algorithm is easy to prove as we did, making FOT morereliable; i.e., it is guaranteed the test suite generated by the algorithm is always
correct (i.e., the test suite generated by the algorithm is sound and complete
w.r.t a test-case design and the semantics in Deﬁnition 3.).
Fourth, FOT is equipped with several automated analysis operations for correctness checking for test-case designs such as consistency checking and detecting
dead /common features, which are absent in CTM. These analysis operations arequite useful, and we ﬁnd them in several case-studies for ﬁnding deﬁciencies intest-case designs by FTT, and validating test-case designs.

8

Conclusion and Future Research

Conclusion In this paper, we have developed a test-case design method for
BBT called “FOT (Feature Oriented Testing)”, by applying analysis and design

methods of FMs originally developed for SPLs. We designed a test-case design
language as a model-based and combination testing method for BBT based on
FMs. A formal semantics of FTT is developed by means of test-cases; this makes
a ﬁrm underpinning of the method. Also we have develop and implemented an
automated test-suite generation and correctness checking of test-case designs using SAT, as computer-aided analysis techniques of the method. Furthermore, wehave demonstrated feasibility of FOT with several dimensions of implementation,
analysis of computational cost, experiments, a case study, and an assistanttool development. We have also clariﬁed the technical and practical advances of
FOT to CTM, which is the-state-of-the-art testing method for BBT.
Future Research There are many directions for further research on the method.
The ﬁrst is to introduce to FOT other theories and computer-aided techniques ofFMs, including refactoring, diagnosis and eﬃciency analysis. Another direction
is to extend FOT with useful notions for test-case design such as the notion ofpriority. In addition, incorporating other testing methods for BBT such as combination testing methods (e.g., n-wise testing, etc) and input-domain analysis
techniques (e.g., equivalent partitioning, boundary value analysis, etc) to FOT are
important directions for our future research.

References
1. D. S. Batory. Feature models, grammars, and propositional formulas. In SPLC,
pages 7–20, 2005.

Test-Case Design by Feature Trees

15

2. D. Benavides, A. R. Cortes, P. Trinidad, and S. Segura. A survey on the automatedanalyses of feature models. In XV Jornadas de Ingenieria del Software y Bases deDatos, 2006.
3. D. Benavides, P. T. Martı́n-Arroyo, and A. R. Cortés. Automated reasoning on
feature models. In CAiSE, pages 491–503, 2005.
4. F. Cao, B. R. Bryant, C. C. Burt, Z. Huang, R. R. Raje, A. M. Olson, and M. Auguston. Automating feature-oriented domain analysis. In Software Engineering
Research and Practice, pages 944–949, 2003.
5. T. Y. Chen, P. L. Poon, and T. H. Tse. An integrated classification-tree methodology for test case generation. International Journal of Software Engineering andKnowledge Engineering, pages 647–679, 2000.
6. N. Eén and N. Sörensson. An extensible SAT-solver. In SAT, pages 502–518,
2003.
7. C. Ericson. Fault tree analysis - a history. In The 17th International Systems
Safety Conference, 1999.
8. S. Fan and N. Zhang. Feature model based on description logics. In KES, pages
1144–1151, 2006.
9. M. Grochtmann. Test case design using classification trees. In The International
Conference on Software Testing Analysis, 1994.
10. M. Grochtmann, K. Grimm, J. Wegener, and M. Grochtmann. Tool-supported
test case design for black-box testing by means of the classification-tree editor. In
The 1st European International Conference on Software Testing Analysis, pages
169–176, 1993.
11. M. Grochtmann and J. Wegener. Test case design using classification trees andthe classification-tree editor cte. In QW, 1995.
12. R. Impagliazzo and R. Paturi. On the complexity of k-SAT. Comput. Syst. Sci.,
62(2):367–375, 2001.
13. M. Janota. Do SAT solvers make good configurators? In ASPL, pages 191–195,
2008.
14. K. C. Kang, S. G. Cohen, J. A. Hess, W. E. Novak, and A. S. Peterson. Featureoriented domain analysis (FODA) feasibility study. Technical report, CarnegieMellon University Software Engineering Institute, November 1990.
15. K. C. Kang, S. Kim, J. Lee, and K. Kim. FORM: a feature-oriented reuse method,
annals of software engineering. Annals of Software Engineering, 5:143–168, 1998.
16. M. Mannion. Using first-order logic for product line model validation. In SPLC,
pages 176–187, 2002.
17. M. Mendonca, A. Wsowski, and K. Czarnecki. SAT-based analysis of featuremodels is easy. In SPLC, pages 231–240, 2009.
18. OSEK/VDX operating system specification 2.2.3 http://www.osek-vdx.org/, 2005.
19. OSEK/VDX operating system test plan, version 2.0, 1999.
20. P. Schobbens, P. Heymans, J. Trigaux, and Y. Bontemps. Generic semantics offeature diagrams. Computer Networks, 51(2):456–479, Feb 2007.
21. P. Schobbens, P. Heymans, and J. C. Trigaux. Feature diagrams: A survey and aformal semantics. RE, pages 139–148, 2006.
22. J. Sun, H. Zhang, Y.F. Li, and H. H. Wang. Formal semantics and verification forfeature modeling. In ICECCS, pages 303–312, 2005.
23. W. Zhang, H. Zhao, and H. Mei. Binary-search based verification of feature models.
In ICSR, pages 4–19, 2011.