Classification Tree Method with Parameter Shielding

Abstract

The Classification Tree Method (CTM) is a structured and diagrammatic modeling technique for combinatorial testing. CTM can express the notion of “parameter shielding”, the phenomenon that some system parameters become invalidated depending on another system parameter. The current form of CTM, however, is limited in its expressiveness: it can only express parameter shielding that depends on a single parameter. In this paper, we extend CTM with parameter shielding that depends on multiple parameters, proposing CTM$_{\textit{shield}}$. We evaluate the proposed extension on several industrial systems. The evaluation finds that parameter shielding often depends on multiple parameters in real systems, and the effectiveness of the extension.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Testing is an important and often a necessary system development process for assuring system quality in current industrial practice. Combinatorial testing is a system testing technique, that effectively tests the interactions of parameters in a system under test. Combinatorial testing derives, typically from specification, a test model, which consists of a list of parameter-values and constraints over them. Based on such test models, test suites are designed, that consider various coverage criteria, such as t-way testing [1, 2].

Figure 1 shows an example test model, which specifies an IC card system with six parameters, each having two to three values: the $\mathrm {\textit{Age}}$ of the card owner, the $\mathrm {\textit{Balance}}$ that is already charged in the card, whether $\mathrm {\textit{Credit Card (C.C.)}}$ information is available or not, the $\mathrm {\textit{Charge Method (C.M.)}}$ and $\mathrm {\textit{Charge Amount (C.A.)}}$ the owner specifies to the system, and the $\mathrm {\textit{Monthly Total (M.T.)}}$ amount of usage. The model also indicates constraints in logic formula, specifying valid (and invalid) value combinations. The two constraints in the example model specify the following specifications:

• “An IC card owned by a child cannot have Credit Card information.”

• “The Charge Method can be by credit card only if a Credit Card information is available.”

Table 1 shows, as a test suite example, a 2-way test suite of the test model.

Fig. 1.

A test model example for an IC card system; it consists of a parameter-values list (left) and a set of constraints (right).

Table 1. A 2-way test suite for the test model of Fig. 1, which covers all valid value pairs but avoids invalid ones, e.g. $\langle$ $\mathrm {\textit{C.C.}}$=$\mathrm {\textit{with}}$, $\mathrm {\textit{Age}}$=$\mathrm {\textit{child}}$ $\rangle$, specified by the constraints.

A key challenge in applying combinatorial testing in real-world development is modeling, a. k. a. Input Parameter Modeling [2] or Input Domain Modeling [3]. Models in real-world systems often involve complex constraints on parameter-values. This makes modeling a time-consuming and error-prone task that requires experience and creativity of test experts.

Classification Tree Method (CTM) [4,5,6] is a structured and diagrammatic approach for the modeling problem. The main characteristic of CTM is that, using a tree-structured modeling language called Classification Trees (CTs), is to be able to describe the notion of “Parameter shielding” concisely, which is a phenomenon that some parameters become invalided (i.e., shielded) if some specific values are (or are not) assigned to another parameter.

Suppose, for instance, the following specification SPEC1 is added to the system:

SPEC1: “Charging is allowed only if the $\mathrm {\textit{Balance}}$ is below 190€.”

Figure 2 shows a CTM model that expresses this specification using a tree structure. The tree structure expresses not only that (1) the relation between parameters and values, but also (2) compositions of parameters and (3) parameter shielding. The rounded rectangle node $\mathrm {\textit{Charge}}$ combines $\mathrm {\textit{Charge Method}}$ and $\mathrm {\textit{Charge Amount}}$ of the previous example, and appears under value $\le$190€ of $\mathrm {\textit{Balance}}$. This expresses that the two parameters become valid only when the $\mathrm {\textit{Balance}}$ is below 190€, and become invalid (shielded) otherwise. Table 2 shows a 2-way test suite for the CTM model. Note that some parameters are assigned the vain value “—” when they are invalid. Note also that the test suite of Table 1 is not a valid 2-way test suite for the current model anymore, since, e.g., test case No. 1 in Table 1 is not executable under SPEC1.

Fig. 2.

A CTM test model for the IC card system that expresses SPEC1.

Table 2. A 2-way test suite for the model of Fig. 2 under SPEC1, where parameters C.M. and C.A. are shielded (as assigned the vain value ‘—’) when $\mathrm {\textit{Balance}}$ is >190€.

Parameter shielding expressed in a tree structure is a unique and useful feature of CTM; however, its limitation is that it can only describe parameter shielding that depends on a single parameter-value. The reason is obvious: the dependencies of parameter shielding are expressed within the tree structure, and hence a parameter can only have one parent. In our case studies applying combinatorial testing and CTM to industrial systems, however, we often encountered a demand to express parameter shielding that depends on multiple parameter-values.

Table 3. A valid 2-way test suite under SPEC2, where parameters C.M. and C.A. are shielded when either $\mathrm {\textit{Balance}}$ is >190€ or $\mathrm {\textit{M.T.}}$ is >390€.

Fig. 3.

A CTM test model for the IC card system uner SPEC2, which expresses a test model of the test suite in Table 3.

For instance, suppose SPEC1 is refined as in the following specification SPEC2:

SPEC2: “Charging is allowed only if the $\mathrm {\textit{Balance}}$ is below 190€ and $\mathrm {\textit{Monthly Total}}$ usage is below 390€.”

As the node $\mathrm {\textit{Charge}}$ should be shielded depending on two (i.e., multiple) parameter-values, this is a typical example of the multi-dependent parameter shielding. Note this time that the test suite of Table 2 is not a valid 2-way test suite anymore, since, e.g., test case No. 2 is not executable under the refined specification SPEC2. A valid 2-way test suite under SPEC2 is as shown in Table 3. Further, it is now difficult to model SPEC2 concisely in CTM. The reason is, as explained, a tree node cannot have multiple parents.

A possible solution that CTM can do is to explicitly handle the vain values and complex constraints involving them as in Fig. 3. However, we assume such manipulations on test models makes themselves too complex and busy, losing conciseness, for engineers to creates and maintain, especially in dealing with industrial-scaled large systems.

In this paper, we propose CTM$_{\textit{shield}}$, by extending CTM with parameter shielding that can depend on multiple parameter-values, or more generally an arbitrary logic formula. Figure 4 shows the basic idea of the extension, by showing an test model example in CTM$_{\textit{shield}}$ which expresses SPEC2. Observe that CTM$_{\textit{shield}}$ is extended with the additional description called (parameter) shielding conditions. Observe also that the shielding condition in Fig. 4 specifies SPEC2 directly, using the notation “$P \leftarrow _{\textit{shield}} V$” to mean parameter-value V shields parameter P. In such a way, we aim to avoid explicitly handling the vain values and complex constraints to express parameter shielding, and thus to retain test models concise and readable. To evaluate the effectiveness of the proposed extension, we conduct experiments via case studies, where we applied combinatorial testing to test industrial systems in the railway domain, using CTM$_{\textit{shield}}$. As summary, the experimental results showed that parameter shielding was used in 72% of the cases; CTM$_{\textit{shield}}$ was able to reduce the tree size by 7.13% and the length of constraints by 22.9% on average, compared with CTM of [7, 8]. Therefore, CTM$_{\textit{shield}}$ contributes to saving human effort on modeling.

The paper is organized as follows. Section 2 mentions related studies. Section 3 clarifies the design of CTM$_{\textit{shield}}$. Section 4 reports our experimental study to evaluate the effectiveness of the proposed extension. Section 5 states our plan for future work.

Fig. 4.

A CTM$_{\textit{shield}}$ test model that expresses SPEC2 and hence is a test model of the test suite in Table 3.

2 Related Work

CTM has been recognized as a key technique in the field of combinatorial testing [2], and has been studied on various aspects. For example, Lehmann and Wegener [5] introduced constraints to the original CTM [7] to extend its expressiveness. Prioritizing test cases was studied for effective test design in the setting of CTM [6]. A test generation algorithm dedicated to CTM was developed in [8]. Also, experimental data in [8] indicate that the structured aspect of CTM reduces the lengths of constraints to be described. For industrial aspects, CTM has been used in industries of safety-critical domains: e. g., it is used in a standard test documentation in automotive industry [9]. Driven by industrial demand, tools to support CTM have been developed by several vendors [10].

The notion of parameter shielding in combinatorial testing has been studied in several different approaches. To our knowledge, the earliest work that is relevant for CTM is by Grochtmann [4]; however, its focus does not seem on parameter shielding but on diagrammatic approaches, as the phenomenon of parameter shielding was not mentioned. Chen et al. [11] first clarified and defined the notion of parameter shielding in the setting of Covering Arrays. which considers only unconstrained and unstructured models. They provided test generation algorithms for this special kind of Covering Arrays. Segall et al. take yet another approach of “common patterns” [12]. They identified several recurring properties in modeling as patterns, which are often hard to capture correctly, and supply solutions for them. The notion of parameter shielding is captured by one of their patterns, called “Conditionally-Excluded-Values” pattern. Zhao et al. developed a test generation tool of combinatorial testing, called Cascade, which can handle shielding parameters explicitly [13] and its handling mechanism is basically same as the proposed solution in [12].

Our work differs from these works in that our contributions are to propose a modeling language by extending CTM with parameter shielding to advance CTM and evaluate its effectiveness via case studies.

3 Classification Tree Method with Parameter Shielding

This section proposes the modeling language CTM$_{\textit{shield}}$, which extends CTM with the notion of parameter shielding. To be conscious about the extension, we first define the language for combinatorial testing, next that for CTM, and finally that for CTM$_{\textit{shield}}$.

The definition of combinatorial testing, whose example is in Fig. 1, is as follows:

Definition 1

(Combinatorial testing). A combinatorial testing model is a tuple $m = {\langle P, V, \varPhi \rangle }$, where P is a set of parameters, $V = \{V_{p}\}_{p \in P}$ is a family of parameter-values, where $V_{p}$ is the value domain of p, and constraints $\varPhi$ are a set of Boolean formula over parameter-values.

A test case is a value assignment to parameters in test model m. Formally, it can be defined as a function $\gamma : P \rightarrow V$ such that $\gamma (p) \in V_p$ for every $p \in P$. Note that a test case $\gamma$ must satisfy all the constraints $\varPhi$ (noted as $\forall \phi \in \varPhi . \gamma \models \phi$ or $\gamma \models \varPhi$).

A CTM test model consists of a Classification Tree (CT) and constraints. A CT consists of three kinds of nodes: classifications, which correspond to parameters in combinatorial testing; classes, which correspond to values; and compositions, a notion that does not appear in combinatorial testing.

Definition 2

(CTM). A test model of CTM is a tuple $m = {\langle r, P, V, C, \mathord {\uparrow }, \varPhi \rangle } \in M$, where ${\langle P, V, \varPhi \rangle }$ forms a test model of combinatorial testing, C is a set of compositions, $r \in C$ is a root node, and $\mathord {\uparrow }$ is a function from $P \cup C \backslash \{r\}$ to $V \cup C$ that expresses a part of the child-parent relation of the tree structure of CT.

As some parameters are shielded and assigned the vain value “—”, a test case of CTM extends that of combinatorial testing as $\gamma : P \rightarrow \{\text {{---}}\} \cup V$, while inheriting $\gamma \models \varPhi$. A parameter p is shielded, assigned “—”, in a test case $\gamma$, if its nearest ancestor value is not chosen for the parameter in $\gamma$. For example, parameter $\mathrm {\textit{C.M.}}$ is shielded in test case No. 3 in Table 2, since its nearest ancestor value “>190€” is not chosen for the parameter $\mathrm {\textit{Balance}}$ in the test case.

Now, the definition of CTM$_{\textit{shield}}$ is given as follows:

Definition 3

(CTM $_{\varvec{shield}}$ ). A CTM$_{\textit{shield}}$ model is a tuple $m = {\langle r, P, V, C, \mathord {\uparrow }, \varPhi , \varPhi _{\textit{s}}\rangle } \in M_s$, where ${\langle r, P, V, C, \mathord {\uparrow }, \varPhi \rangle }$ is a CTM model and $\varPhi _{\textit{s}}$ is a function from $P \cup C$ to Boolean formulas. We denote $\varPhi _{\textit{s}}(n)$ as the (parameter) shielding condition of $n \in P \cup C$.

The definition of CTM$_{\textit{shield}}$ extends that of CTM by the shielding conditions $\varPhi _{\textit{s}}$. A test case of CTM$_{\textit{shield}}$ also inherits that of CTM, including the condition of parameter shielding specified by the tree structure. Moreover, in CTM$_{\textit{shield}}$ a parameter p in a test case is shielded by $\varPhi _{\textit{s}}$ when its shielding condition $\varPhi _{\textit{s}}(p)$ is satisfied by the test case.

In order to express $\varPhi _{\textit{s}}$ in practice, we take a list of pairs of form $p \leftarrow _\text {shields} \phi$ indicating that $\varPhi _{\textit{s}}(p) = \phi$, and assume $\varPhi _{\textit{s}}(q) = \textsc {False}$ when q is not specified in the list. Note that a CTM model is a CTM$_{\textit{shield}}$ model with an empty list of such specifications. Figure 4 is an example of CTM$_{\textit{shield}}$, and Listing 1.1 shows a formulation of the test model in Fig. 4 according to Definition 3.

4 Case Studies and Evaluations

This section reports our empirical studies to evaluate the effectiveness of the proposed extension, i.e., CTM$_{\textit{shield}}$ extending CTM with parameter shielding, through case studies with industrial systems.

We determine the “effectiveness” of CTM$_{\textit{shield}}$ by the conciseness of test models in CTM$_{\textit{shield}}$ compared to those in CTM (the one dealt in [5, 8]). More specifically, we measure the conciseness of models on their description complexity in terms of the number of parameter-values and the length of constraints needed to describe the models. Our evaluation poses the following three research questions:

• RQ1: How often is the parameter shielding condition used? What is its usage rate?

• RQ2: How many tree nodes can CTM$_{\textit{shield}}$ reduce, compared with CTM?

• RQ3: How much length of constraints can CTM$_{\textit{shield}}$ reduce, compared with CTM?

4.1 Setting

In the case studies, we applied combinatorial testing to functional testing of 25 system-level functions of the following two distinct industrial systems in railway domain, and in doing so we used CTM$_{\textit{shield}}$ for modeling the functions: 19 functions from a ticket gate system (system A) and 7 functions from a payment system (system B).

Table 4. Summary of experimental results.

For comparison between CTM$_{\textit{shield}}$ and CTM, we also prepared test models in CTM. We prepare a program to translate test models in CTM$_{\textit{shield}}$ to equivalent ones in CTM; i.e., it handles complex manipulation of constraints and dummy nodes. For example, it inputs the CTM$_{\textit{shield}}$ test model in Fig. 4, and outputs the CTM test model in Fig. 3.

Next, we measure the following metrics of the test models in CTM$_{\textit{shield}}$ and CTM:

• 1. P / V: The size of parameter-values; this is expressed as $g_1^{k_1}g_2^{k_2}...g_n^{k_n}$, which means that for each i there are $k_i$ parameters that have $g_i$ values, following [14, 15].

• 2. $\#N$: The number of nodes; this is the summation of the numbers of compositions, parameters, and values.

• 3. $l(\phi )$: The length of constraints $\phi$, which is defined in a similar way as [16] as follows: $l(a) = 1$ for all atoms a, $l(\lnot P) = 1 +l(P)$, and $l(P * Q) = 1 +l(P) +l(Q)$ where $*$ is a binary operator of $\wedge , \vee , \Rightarrow$, and $\Leftrightarrow$. E.g., $l(\underline{\lnot }_1 \underline{P_2=v_1}_2 \underline{\vee }_3 \underline{P_3=v_1}_4) = 4$.

Since CTM$_{\textit{shield}}$ has an additional description component of parameter shielding conditions, we also measure the following two metrics for test models of CTM$_{\textit{shield}}$:

• 4. $l(\varPhi _{\textit{s}})$: The length of parameter shielding conditions $\varPhi _{\textit{s}}$. As mentioned in Sect. 3 and exemplified in Fig. 4, a shielding condition is expressed using “$\leftarrow _{\textit{shield}}$” in practice; e. g., “$P_1 \leftarrow _ shield \lnot P_2=v_1 \vee P_3=v_1$” to mean $\varPhi _{\textit{s}}(P_1) = \lnot P_2=v_1 \vee P_3=v_2$”, where $P_1,P_2,P_3$ expresses parameters and $v_1$ and $v_2$ values. Thus, we define the length of a shielding condition for parameter n by $l(\varPhi _{\textit{s}}(n))+2$, regarding $\leftarrow _ shield$ as a binary operator. For example, $l(\varPhi _{\textit{s}}(P_1)) = l( \underline{\lnot }_1 \underline{P_2=v_1}_2 \underline{\vee }_3 \underline{P_3=v_1}_4) +2 = 6$

• 5. $|\varPhi _{\textit{s}}|$: The size of $\varPhi _{\textit{s}}$ in the form $1^{k_1}2^{k_2}...n^{k_i}$, which this time means there are $k_i$ conditions whose length is n for each $n \in \textit{Nat}$ while $n^{k_i}$ are omitted if $k_i = 0$.

In order to quantitatively answer the research questions, from data about the test model of CTM ($m_c$) and that of CTM ($m_s$) for each function, we retrieve the following:

• the reduction rate of the number of nodes $\varDelta _{\%}^N$:

  $$\begin{aligned} \varDelta _{\%}^N = : \dfrac{\#N^{m_c} - \#N^{m_s}}{\#N^{m_c}} \end{aligned}$$

  (1)

• the reduction rate of constraint length $\varDelta _{\%}^\varPhi$:

  $$\begin{aligned} \varDelta _{\%}^\varPhi = :\dfrac{l(\varPhi ^{m_c}) - (l(\varPhi ^{m_s}) + l(\varPhi _{\textit{s}}^{m_s}))}{l(\varPhi ^{m_c})} \end{aligned}$$

  (2)

where $\#N^{m}$, $l(\varPhi ^{m})$, and $l(\varPhi _{\textit{s}}^{m})$ respectively mean the number of nodes, length of constraints, length of shielding conditions in test model m.

Note that $\varDelta _{\%}^\varPhi$ considers not only the length of constraints, but also the length of shielding conditions for test model in CTM$_{\textit{shield}}$ $m_s$. This is for a fair comparison. We expect (and will see) CTM$_{\textit{shield}}$ can in fact reduce the length of the constraints. However, this is achieved at the cost of describing the shielding conditions. To avoid such an unfair comparison, we designed in $\varDelta _{\%}^\varPhi$ to consider not only constraints length but also the length of shielding conditions in test models of CTM$_{\textit{shield}}$.

4.2 Results and Observations

Table 4 summarizes the experimental results. The first column shows retrieved data from the test model example in CTM$_{\textit{shield}}$ in Fig. 4 and an equivalent test model in CTM in Fig. 3, whose main points are read as follows:

• 1. The CTM$_{\textit{shield}}$ test model in Fig. 4 has five parameters for two values and one parameter for three values, hence its P / V is expressed as $2^{5}3^1$. On the other hand, the CTM test model in Fig. 3 has three parameters for two values, two for three values, and one for four values, hence its P / V is expressed as $2^{3}3^{2}4^{1}$.

• 2. The number of nodes in the CT in CTM is 24, while that in CTM$_{\textit{shield}}$ is 22. Thus, the number of nodes is reduced by $2~(= 24-22)$, and the node reduction rate ($\varDelta _{\%}^{N}$) is $8.3\% (=\frac{2}{24})$.

• 3. The constraint length of the CTM test model is 11, while that of CTM$_{\textit{shield}}$ is 6. We also take the description cost of shielding conditions for CTM$_{\textit{shield}}$ into account, as the length of shielding conditions which is 3. Thus, according to the definition, the reduction rate of constraint length ($\varDelta _{\%}^\varPhi$) is $47.1\% (= \frac{(17 - (3+6))}{17} = \frac{8}{17})$.

From the summary of the experimental results shown in Table 4, we answer the research questions as follows:

• Answer for RQ1: The shielding conditions were not necessarily used for all the cases; instead, they are used in 12 out of 19 cases (63.1%) for system A and in all the six cases (100%) for system B; hence 72% (= 18/25) in total of systems A and B.

• Answer for RQ2: For the cases where parameter shielding are used, the reduction rate of the number of tree nodes by CTM$_{\textit{shield}}$ ($\varDelta _{\%}^N$) is on average 4.2% for system A and 11.0% for system B; 7.13% on the total average.

• Answer for RQ3: For the cases where parameter shielding are used, CTM$_{\textit{shield}}$ reduces the constraint length, compared with CTM, (i.e., $\varDelta _{\%}^\varPhi$) on average by 14.7% for system A, by 39.4% for system B; by 22.9% on the total average.

Note that all the test models for the functions in both systems are expressed as trees, from which we can consider structured and diagrammatic modeling approach of CTM is useful and effective in practice. Also, CTM$_{\textit{shield}}$ shows a higher effectiveness in system B than system A, from which we may consider that the effectiveness of using CTM$_{\textit{shield}}$ differs between systems. As shorter and simpler constraints reduce the human effort on modeling, we consider CTM$_{\textit{shield}}$ to be effective in real-world settings.

5 Conclusion and Future Work

This work tackled a modeling problem in combinatorial testing, which is a main concern for its use in real developments. We extend CTM, which have been studied and used as a practical modeling language in combinatorial testing, with parameter shielding, and proposed CTM$_{\textit{shield}}$. Our experiments via case studies confirmed its effectiveness.

We plan to conduct more empirical studies to evaluate the effectiveness of CTM$_{\textit{shield}}$ when used to model industrial systems. We leave to future work a theoretical analysis of the proposed extension, such as consistency arguments with different formalisms for parameter shielding [11], theoretical analysis of effectiveness of the extension such as the maximum reduction of the number of nodes, the size of constraints per shielding condition, etc. We also plan to extend our combinatorial testing tool Calot [8, 17, 18] with this feature of parameter shielding.