Product configuration typically makes use of declarative knowledge to model the properties of complex products. The development of such product knowledge bases is similar to the development of code bases. Key challenges include collaboration, maintainability, extensibility, and quality assurance. New features, requirements, and regulations lead to frequent and error-prone iterations. Analogous to software engineering, automated testing is critical to ensure the integrity of product knowledge. While the general NP-complete complexity of configuration problems generates much academic interest, these businessrelevant challenges receive less attention. This paper thus presents ongoing work on quality assurance in product configuration using regression testing. Therefore we first formally define a novel data structure for performing the tests. We then explore the challenges of collaboratively engineering testing knowledge in practice. Finally, we illustrate a grammar to formulate the tests with several application scenarios.
Product configuration describes a broad area that deals with the composition and
individualization of generic components. A typical example is the selection of a custom computer. Instead
of ofering a predefined set of options, for example, customers can instead assemble the exact
computer they want from components such as diferent processors, cases, and monitors. As a
result, the users are more likely to spend money. The various components are contained in a
product catalog and are subject to certain compatibilities with each other. However, Felfernig et
al. [
Some of these challenges are similar to software development. While executing code performantly is important, the real challenge is developing high-quality code in the first place and maintaining it over a long time. By having diferent parties making continuous changes to the code, bugs are easily introduced. The same applies to product configuration. However, configuration knowledge must be completely free of errors to prevent customers from ordering products that can neither be manufactured nor sold. A system for automated quality assessment of knowledge integrity is thus essential. One tool to identify newly introduced errors is regression testing. However, because NP complexity is typically associated with configuration problems, dificulties exist in developing meaningful tests at all. Unlike in software development, it is not suficient to describe a set of expected inputs and outputs. Although expected inputs are usually well defined, their amount of possible combinations is exponential to the number of feature values. This quickly exceeds the capacity of hardware and developers. To address this, our work develops a novel data structure for regression testing in product configuration to deal with this complexity. Analogous to the development of product knowledge itself, declarative formulation is a guiding principle. Often, diferent parties with diferent expertise maintain the knowledge. These parties should not be concerned with the details of a procedural, and thus technical, formulation. Test knowledge is inherently declarative: It formulates what the desired behavior of functions is, rather than knowing their details of how. This notion leads us to the idea of test-driven knowledge development. New requirements are first formulated as tests and thereby documented simultaneously. Based on this, the requirement can be understood in the long term, and arbitrary refactoring can be performed on the knowledge.
This paper therefore addresses two questions: • How can products be regressively tested despite an exponential set of possible configurations? • How does the collaborative development and maintenance of test knowledge between parties of diferent expertise work? Our work outlines a vision of a set of methods for quality assurance and collaborative development of complex product configuration knowledge bases.
For this purpose, we first briefly define product knowledge and the configuration process in general in Section 2. We then present our data structure for formulating test knowledge in Section 3. In the next Section 4, we take a look at how tests are developed in practice and their lifecycle. We illustrate this view with several application scenarios in Section 5. Finally, we conclude our work with a brief look at the related literature and an overview of future challenges.
The main idea of product configuration is the feature-based personalization of a product. There
are serveral eforts for a general ontology to model the knowledge about a product. Since the set
of possible configurations grows exponentially with the amount of selectable options, it is not
feasible to enumerate all results in a database. Instead, configuration problems are commonly
modeled as constraint satisfaction problems. Here, a set of variables and their domains exists,
i. e., components and their type, or in general, features of a product. This typically involves
the notion of customizing systems out of generic components that form a part-of-hierarchy.
We refer to this as structural knowledge. Furthermore, the interactions of the variables are
modeled with constraints. We subsequently describe this as behavioral knowledge. Finally, we
define the configuration process itself. Common extensions of a general ontology consist of
a hierarchy and dynamic activation of variables. More complex components are composed
in this way recursively from more specific components which in turn are configurable. Since
this hierarchical modeling introduces much complexity with concepts such as partonomy and
taxonomy that are beyond the scope of this work, we stick with the notion of features, i. e.,
configurable aspects of the product. To avoid the irrelevant overhead of this complexity, we
keep our definition as simple as possible to provide the basis for regression testing. We align
ourselves with the definitions in [
Definition 1 (Feature). The properties of a product are specified by features. A feature is a variable defined by its feature type. The type of a feature domain ( ) determines its non-empty domain. Primitive feature types describe numeric, boolean, and textual domains. Concrete feature types define a discrete and finite domain of selectable options.
We use typewriter font for concrete examples and write features with a capital initial letter. Domain values are completely capitalized. For example, the color of a car could be described by a feature Color, where domain (Color) = {BLACK, WHITE, RED}. One reason for using the term feature is to distinguish between diferent types that capture diferent characteristics of a product. For example, there are also primitive data types that cannot be classified under the term component. Note that this definition can give rise to a potentially infinite number of possible product configurations, e. g., by having a feature with domain ( ) = R. The implication is that in this case no finite set of configuration exists. Thus no finite set of classical test cases with expected input and output can cover the entire space of valid configurations.
Since the individual configurations cannot be explicitly enumerated, they are implicitly specified by constraints. With the previous definition, only the configurable dimensions of a product are defined. However, a large part of the knowledge is formed by the constraints on these dimensions. We call these constraints behavioral knowledge. The set of all possible configurations results from the cross product of the domains of all features. However, usually only a fraction of them form valid configurations, i.e., combinations of the components that can be produced and sold. To capture the set of all valid solutions in this space of all possible solutions, constraints are required.
Definition 2 (Constraint). A constraint is a function that maps a configuration to a boolean truth value, i. e., : → {⊤, ⊥} . (1)
While the configuration will be discussed in more detail in a moment, in our work we are mainly interested in first order and propositional as well as arithmetic constraints. Although the type of constraints is unbounded in theory, usually there are common patterns to describe the behavior of a product. Note that we abuse notation here to describe constraints as formulas for which an interpretation exists such that () evaluates to true or false. 1. Allowed or forbidden value combinations of diferent components, e. g.,
(Body = CITY ∨ (Body = SPORT ∧ Drive = FRONT_WHEEL) ∧ Drive = REAR_WHEEL) ∨ (Body = OFF_ROAD ∧ Drive = ALL_WHEEL)
This pattern lists possible feature combinations in table-like disjunctive normal form. 2. Requirements, that formulate arbitrary conditions that have to be fulfilled, e. g.,
WeightInKG <= 3500 Although these are in nature similar to combinations, they formulate more concise constraints that go beyond (in)equality. They may involve arithmetic, e. g., the “weight of of all components must not exceed a certain value”. 3. Implications which are similar to requirements. Here, a condition must first occur before the consequence must be met, e. g.,
Body = SUV → HorsePower >= 100 Other examples outside the scope of this work describe default value assignments, involve temporal conditions, or concern the presence and absence of components in the hierarchy. The combination of features, feature types, and constraints of a product forms a knowledge base. Definition 3 (Knowledge Base). A configuration knowledge base is a triple (, , ), where is the set of all features, is the set of all feature types, and is a set of constraints over .
The knowledge base is then used to ofer individual configurations to customers. Definition 4 (Configuration) . A configuration is a set of at most one value assignment to each feature ∈ in a knowledge base (, , ).
= { = | ∈ ∧ ∈ domain ( )} . is complete, if (3) holds, and valid if (4) holds.
complete () : ∀ ∈ : ∃ ∈ domain ( ) : ( = ) ∈
valid () : ∀ ∈ : () = ⊤ A complete configuration is therefore merely the finished process of feature binding where exactly one value exists for each feature. The user requirements are a partial configuration, where each feature assignment = is explicitly given by the user. Neither complete ( ) nor valid ( ) have to be true. We are interested in the set of solutions , where each solution ∈ is complete and valid. Note that ⊇ , since it is completed from . We refer to as satisfiable if ̸= ∅ and unsatisfiable otherwise. The configuration process is typically a sequence where grows incrementally. The customer starts with = ∅ and can select only valid or arbitrary values depending on the environment. (2) (3) (4)
Regression testing is commonly understood as the repeated evaluation of test cases to ensure
that modifications in already tested functions do not cause new errors [
Although various synergies exist between knowledge and software engineering, there is a
key diference for regression testing in product configuration. While it is usually possible to
develop tests to cover the entire software, NP complexity generally prevails for constraint-level
configuration problems [
A novelty here is the introduction of a reasoning mode . The two modes universal and
existential specify whether the test constraint must hold in at least one or all of the
configurations that can be derived from the user requirements. Instead of developing and executing
separate test cases for each possible configuration, eficient algorithms like CDCL can then be
used to enumerate models [
This type of reasoning is necessary for both positive and negative hard requirements. Section 5 will illustrate both reasoning modes in more detail.
Definition 7 (Existential Testing). Given a test case (, , existential ), at least one configuration ⊇ : valid () ∧ complete () must exist in which the test constraint holds. Definition 6 (Universal Testing). Given a test case (, , universal ), the test constraint must hold in all configurations ⊇ : valid () ∧ complete ().
This type of reasoning is for example important for a guided configuration process, where the user is pointed to the set of selectable valid values. Thus, it would be conceivable to implement concrete features as a dropdown menu, where the selectable options are loaded dynamically depending on the current requirements. A test case could then ensure that an option is still available. Both modes can be negated by negating the test constraint and using the opposite reasoning mode. The opposite of universal testing thus changes from ¬∀ ∈ : () = ⊤ to ∃ ∈ : () = ⊥. Correspondingly, existential testing changes from ¬∃ ∈ : () = ⊤ to ∀ ∈ : () = ⊥. The default mode tests the constraint accordingly with a configuration that complies with all satisfiable default rules. All feature assignments not derived from defaults can have a non-deterministic choice in this case. However, before discussing these modes in more detail, we define our collected test knowledge as test suite.
Definition 8 (Test Suite). A test suite is a tuple (, ), where is a knowledge base following Definition 3 and is a finite set of test cases following Definition 5.
The tests of a test suite can be executed sequentially by a portfolio of reasoning engines, but can also be fully parallelized. Since each test case is potentially associated with an NP complete evaluation, the performance of the test system plays a critical role. In addition, optimization can be performed, such as grouping several test cases with the same user requirements and the same reasoning mode.
According to Junker [
Having formally defined both product configuration and regression testing, in this section we take a look at it from a practical standpoint. For this, we outline in Section 4.1 the collaborative development of test knowledge and its challenges using a domain-specific grammar. Then, in Section 4.2, we describe the lifecycle of the test knowledge, its integration into the development process, and most importantly, the execution of the tests.
Various front ends are conceivable for developing the testing knowledge and thus setting up the data structure in Definition 8. These front ends must be adapted to the expected developers of the tests. Ideally, the front end is based on existing technology for developing product knowledge. Very technical developers, for example, could be granted direct access to a programming interface. Technically-averse actors, for instance subject matter experts, should be supported in other ways. One way would be to add a developer mode to the configuration environment. On the one hand, this allows to manually create a configuration to be tested analogous to the customer experience. On the other hand, also test constraints can be created in the developer view for each step, for example with the support of graphical editors and pre-built templates. The respective steps of the development process are then serialized into individual test cases. While this method is very convenient, it also comes with disadvantages. The linear navigation through the configuration process leads to a similar set of user requirements and thus similar test cases. This in turn leads to the many dimensions of the solution space of valid configurations possibly being insuficiently tested, while few other dimensions are redundantly tested.
A third solution would be a middle ground, such as the implementation of a Domain Specific Language (DSL). Technical details such as the diferent reasoning modes should be abstracted. A strongly declarative solution could be closely oriented to natural language. A DSL has the advantage of being able to use the synergies with text-based software development. This makes it very easy, for example, to integrate versioning with helpful diference views. Furthermore, a semantic wiki can serve as a platform for collaborative development, structuring and maintenance of test knowledge. In addition, text is a suitable interface for pointing out anomalies, for example through syntax highlighting. Ultimately, there is an integrated development environment (IDE) that combines all of these functions. The basis for this is the DSL. Such a language is briefly outlined in Listing 1.
Here, we only show the formulation of the constraints. As lines 1–3 show, a statement begins with the reasoning mode. Then, after lines 5–11, a constraint is initially a logical expression that can be evaluated to true or false according to Definition 2. Note the precedence of the rules. Essential for this is the compare rule in line 10 to evaluate constants obtained from formulas. Formulas in lines 13–23 represent calculations and functions that can be evaluated to constants. The last line refers to the hidden feature rule, which is used to query configuration-dependent values. Since typically diferent people without a computer science background develop tests, one goal of the DSL is to avoid computer science-specific concepts and terminology. For example, “&&” and “||” often serve as logical AND and OR in programming languages, but are replaced here by their natural language counterparts. Also, Unicode symbols are avoided, such as “→”, “∨”, and “∧”, which are inconvenient to type. Note that the grammar lacks operations to manipulate the configuration. However, a simple option would be to specify a serialized configuration with feature assignments for each test case, which is then loaded from a database or file. A self-contained test case, on the other hand, would start from a blank configuration and include operations to set and modify values. The written DSL code is then decomposed into a set of user requirements, where each element of the set arises after an operation to modify a value. We show examples of usage in Section 5.
c o n s t r a i n t : = i m p l i c a t i o n i m p l i c a t i o n : = d i s j u n c t i o n ( ' i m p l i e s ' d i s j u n c t i o n ) ∗ d i s j u n c t i o n : = c o n j u n c t i o n ( ' or ' c o n j u n c t i o n ) ∗ c o n j u n c t i o n : = n e g a t i o n ( ' and ' n e g a t i o n ) ∗ n e g a t i o n : = ' not ' n e g a t i o n | ' ( ' c o n s t r a i n t ' ) ' | compare compare : = f o r m u l a ( o p e r a t o r f o r m u l a ) + o p e r a t o r : = ' < ' | ' < = ' | ' > ' | ' > = ' | ' = ' | ' ! = ' Listing 1: A simplified grammar to define test cases. For simplicity, we adapt the symbols {(, ), ?, * , +} of regular expressions with the same meaning. The grammar is not functional due to a lack of terminal rules. Also, whitespaces are ignored. The terminal symbol feature is not defined, but is used to identify features ∈ . Likewise, number is not defined, but describes integer and floating point values. The start rule is test.
To detect regressions, tests must be run automatically after changes and new versions. Here,
software development can serve as inspiration. Correspondingly, a continuous integration (CI)
system can be implemented that runs the tests after each change or after manual triggering [
Regression testing is used by companies to verify that the solution space of sellable configurations is correctly defined. We separate this interest into two categories: 1. Whitelist Testing: On the one hand, the set of manufacturable configurations should be clearly defined in order to prevent profit losses by selling fewer products due to a lack of configurations. 2. Blacklist Testing: On the other hand, non-manufacturable configurations are to be prevented in order to avoid problems with the correction of erroneous orders in downstream systems such as supply chain management and more importantly, the production line. Since whitelisting explicitly describes allowed configurations, knowledge is much easier to maintain. This works, for instance, by describing allowed instead of forbidden feature combinations. For example, the list in Section 2 shows allowed combinations. The opposite — forbidden combinations — would be a negation of the entire expression. This would hide which configurations are excluded by the constraint. The situation is similar with test knowledge. It is hard to test the unknown unknowns. Whitelisting is therefore the recommended approach.
Whitelist testing is concerned with the known properties of valid configurations. In the easiest case, tests are developed for an existing product whose knowledge base is merely being expanded or maintained. In this case, test cases can be generated automatically, which, for example, ensure that the sold configurations of a past period are still sellable with the revisions. A typical test case here consists of the user requirements at that time and the feature assignments of the sold configuration. is then universally tested, since the requirements come explicitly from the user and thus must be included in any derived configuration. The assignments of the reasoning engine at that time are existentially tested to ensure that the configuration could still be derived in exactly the same way. For example, = {Body = SPORT, ExteriorColor = RED, Wheels = 21_INCH_SPIDER} , = {Seats = SPORT, InteriorColor = BLACK, . . . } .
A test case may then look like the following. / / l o a d / s e t u p c o n f i g u r a t i o n r e q u i r e Body = SPORT r e q u i r e E x t e r i o r C o l o r = RED r e q u i r e Wheels = 2 1 _INCH_SPIDER a l l o w S e a t s = SPORT AND
I n t e r i o r C o l o r = BLACK . . .
Since the tests are generated automatically, each line can easily consist of a single constraint. Otherwise, universal constraints can be linked with a logical AND to save typing. Note that for existential tests, it makes a diference, though, whether they are formulated as a single or a separate constraint. If the ontology supports defaults, then a third reasoning mode for it would be conceivable, that explicitly tests configurations that maximize all satisfiable defaults (see Section 3). For example, if Body = SPORT the implication Seats = SPORT should be tested as default instead of existentially.
However, usually it is not old knowledge that needs to be tested, but new knowledge. Instead of a set of inputs and expected outputs, the requirements of the new knowledge must then be specified as testable criteria. For example, one property of any product that is often part of the knowledge base is its price calculation. Here, prices are often dynamically composed of surcharges and price reductions. A surcharge could result if a product does not use a uniform color, but diferent colors for diferent components. This requirement is first formulated as a test. r e q u i r e e q u a l ( E x t e r i o r C o l o r , I n t e r i o r C o l o r , C o v e r C o l o r ) i m p l i e s C o l o r S u r c h a r g e = f a l s e r e q u i r e n o t e q u a l ( E x t e r i o r C o l o r , I n t e r i o r C o l o r , C o v e r C o l o r ) i m p l i e s C o l o r S u r c h a r g e = t r u e The test starts with = ∅, since it must apply universally to all derivable configurations. Then the functionality is implemented in the product knowledge itself and can be refactored as desired. Note that the derivation of ColorSurcharge here is potentially very similar to the test constraint itself. However, this redundancy documents the original requirement of the product knowledge in the event that the knowledge is changed.
Blacklist testing is concerned with the unknown properties of invalid configurations. Because of this uncertainty, blacklist tests are discouraged. However, they are often required by poor knowledge modeling practices. For example, by using combination constraints (see Section 2) to define forbidden combinations instead of allowed ones. Equivalently to tests with sold configurations, the reasoning engine can be used to generate a set of non-manufacturable configurations. To do this, is randomly generated repeatedly and ¬valid ( ) is checked in each case. However, the set of invalid configurations typically exceeds the set of valid configurations by several orders of magnitude. This severely limits the quality assurance of these blacklist tests. Much better suited are universal tests with general statements, where = ∅. As an example, consider again the price. A universal statement would be, for example, that the price must always lie in an interval that is statically calculated from the minimum and maximum prices of the components. r e q u i r e 1 2 , 5 1 7 . 3 2 <= sum ( P r i c e I n t e r i o r ,
P r i c e E x t e r i o r ,
S u r c h a r g e s ) − P r i c e R e d u c t i o n s <= 9 5 , 5 6 9 . 1 4 This computation could also be done dynamically, which would require additional operations in the DSL, e. g., to access the minimum and maximum of the feature domains.
Another problem could involve the weight of a product. For example, in the European Union, a passenger car may not exceed the weight of 3.5 tons. Therefore, to prevent configurations from exceeding this weight, a constraint exists that limits the sum of the weights of all parts accordingly. The weight must always be rounded up to the next kilogram so that the limit is not exceeded unnoticed due to rounding. A test is implemented. r e q u i r e
WeightInKG <= 3 5 0 0
Automated testing for quality assurance in all areas of computer science has a long history. This
ranges from validation and verification in knowledge engineering [ 17, 18, 19] to a complete
portfolio of testing techniques such as unit, integration, system, and acceptance tests in software
engineering [
Nevertheless, several challenges remain. One of them is the evaluation of quality assurance itself using coverage metrics of the tested knowledge. In contrast to software, there is no control flow due to declarativity of our approach, which means that existing metrics such as path or branch coverage are not applicable [20, 21]. Similar to much other work [21, 22], thus more research is needed on how to draw conclusions from our test cases about their quality and the extent of knowledge tested. Another challenge is that the presented framework for testing is itself error-prone, as the formulation of the test constraints is non-trivial. Various papers tackle the task of verifying test suites themselves for this purpose [23, 24, 25]. Finally, the performance of test case execution is a challenge that sufers from the NP complexity of configuration problems. For this, a system to automatically decide which test cases have to be executed depending on the changes made to the knowledge base is conceivable. This is to avoid executing test cases that succeed regardless of occurring regressions and are therefore irrelevant. The execution of only relevant test cases then leads to an improvement of the intended frequent and continuous integration of changes. Ultimately, regression testing represents only one of many tools to ensure knowledge quality such as those used in software engineering. We strive for a portfolio of all these methods in the future and are, at the time of writing, in the process of evaluating the presented methods with industrial partners. 2002. [16] J. Baumeister, J. Reutelshoefer, F. Puppe, Knowwe: a semantic wiki for knowledge engineering, Appl. Intell. 35 (2011) 323–344. URL: https://doi.org/10.1007/s10489-010-0224-5. doi:10.1007/s10489-010-0224-5. [17] R. Knauf, A. Gonzalez, K. Jantke, Validating rule-based systems: a complete methodology, in: IEEE SMC’99 Conference Proceedings. 1999 IEEE International Conference on Systems, Man, and Cybernetics (Cat. No.99CH37028), volume 5, 1999, pp. 744–749 vol.5. doi:10. 1109/ICSMC.1999.815644. [18] J. Baumeister, Continuous Knowledge Engineering with Semantic Wikis, habilitation,
Universität Würzburg, 2010. [19] J. Baumeister, Advanced empirical testing, Knowl. Based Syst. 24 (2011) 83–94. URL: https://doi.org/10.1016/j.knosys.2010.07.008. doi:10.1016/j.knosys.2010.07.008. [20] H. Zhu, P. A. V. Hall, J. H. R. May, Software unit test coverage and adequacy, ACM Comput. Surv. 29 (1997) 366–427. URL: https://doi.org/10.1145/267580.267590. doi:10. 1145/267580.267590. [21] F. Belli, O. Jack, Declarative paradigm of test coverage, Softw. Test. Verification Reliab. 8 (1998) 15–47. URL: https://doi.org/10.1002/(SICI)1099-1689(199803)8:115:: AID-STVR146\protect\protect\leavevmode@ifvmode\kern+.2222em\relax3.0.CO;2-D. doi:10.1002/(SICI)1099-1689(199803)8:1\<15::AID-STVR146\>3.0.CO; 2-D. [22] F. Belli, O. Jack, A test coverage notion for logic programming, in: Sixth International Symposium on Software Reliability Engineering, ISSRE 1995, Toulouse, France, October 24-27, 1995, IEEE Computer Society, 1995, pp. 133–142. URL: https://doi.org/10.1109/ISSRE. 1995.497651. doi:10.1109/ISSRE.1995.497651. [23] S. Boroday, A. Petrenko, A. Ulrich, Test suite consistency verification, in: 2008 EastWest Design & Test Symposium, EWDTS 2008, Lviv, Ukraine, October 9-12, 2008, IEEE Computer Society, 2008, pp. 235–239. URL: https://doi.org/10.1109/EWDTS.2008.5580145. doi:10.1109/EWDTS.2008.5580145. [24] P. H. Deussen, S. Tobies, Formal test purposes and the validity of test cases, in: D. A. Peled, M. Y. Vardi (Eds.), Formal Techniques for Networked and Distributed Systems - FORTE 2002, 22nd IFIP WG 6.1 International Conference Houston, Texas, USA, November 11-14, 2002, Proceedings, volume 2529 of Lecture Notes in Computer Science, Springer, 2002, pp. 114–129.
URL: https://doi.org/10.1007/3-540-36135-9_8. doi:10.1007/3-540-36135-9\_8. [25] C. Jard, T. Jéron, P. Morel, Verification of test suites, in: H. Ural, R. L. Probert, G. von Bochmann (Eds.), Testing of Communicating Systems: Tools and Techniques, IFIP TC6/WG6.1 13th International Conference on Testing Communicating Systems (TestCom 2000), August 29 - September 1, 2000, Ottawa, Canada, volume 176 of IFIP Conference Proceedings, Kluwer, 2000, pp. 3–18.