Abstract
Due to varying demands by customers, some software systems need to be configurable and need to have optional features. Customers then configure their system according to their special needs and select the features they need. A problem the developers of such systems face is the possibility of latent faults awakened by some of its set-ups. A system used by thousands, if not by millions, cannot fail for many before it becomes a major problem for the developers. Indeed, if many systems fail, the general view of the quality of the system might be beyond repair. For example, the Eclipse IDEs are popular software systems; they are also highly customizable. There are probably tens of thousands of unique set-ups of the Eclipse IDEs in use.
This is one example of product line development, and the field that studies the construction and development of product lines is product line engineering. One way of gaining confidence in the quality of a product line—and any set-ups of it—is through testing. Product line testing, the strategic exercising of the product line in order to gain confidence in the quality of the product line and any configuration of it, is the subject of this thesis.
The strategy followed today with documented results is reusable component testing, the testing of the product line’s common parts in isolation: If a common part fails in isolation because of an internal fault, it will likely cause failures in any product of which it is a part. Testing something in isolation will not, naturally, rule out interaction faults between these parts.
Combinatorial interaction testing (CIT) can test interactions and is—as of today—the technique closest to being realistically applicable in industrial settings. This technique is the starting point of the contributions of this thesis. CIT starts by sampling some products of the product line. The products are selected such that all combinations of a few features are in at least one of the products. This selection criterion is such that faults are more likely to show up in these products than in randomly selected products. As executable systems, they can be tested.
One significant problem with CIT is the lack of an efficient algorithm for the selection of products. The existing algorithms scale insufficiently for the larger product lines. This effectively rules it out in industrial settings. A contribution of this thesis is an algorithm (called ICPL) that can perform the selection process even for product lines of industrial size. A preliminary analysis of the problem was a necessary prior contribution contributed before the algorithm could be developed. These two contributions taken as a whole provides an efficient algorithm for this one bottle-neck of the application of CIT.
Having a scalable algorithm for selection enables the efficient application of CIT. To establish and demonstrate the usefulness of CIT, three advancements of CIT with applications were contributed.
Firstly, a common situation with product lines is portability across various hardware architectures, operating systems, database systems, etc. One construct that deals effectively with such situations is a homogeneous abstraction layer. It provides a uniform way of accessing these differing systems. Usually, only one implementation of a homogeneous abstraction layer can be present in a product. This deteriorates the performance of CIT. The selection criterion used by CIT is to strategically select simple combinations of features. Only being allowed to activate one and one feature is limiting to the algorithms. It was noticed that products differing only in their implementation of homogeneous abstraction layers can be tested using the same test suite. This enables a voting oracle or a gold standard oracle to be set up. This contribution thus turns the aforementioned problem into a strength.
Secondly, the selection criterion of CIT ensures all simple interactions are exercised. In some cases, this leads to redundant testing. A product line’s market situation might exclude large classes of feature combinations or indicate then some combinations are more common than others. These things can be captured in a weighted sub-product line model, which, along with associated algorithms, is another contribution of this thesis.
Thirdly, one way to fully automate the application of CIT is to create the test cases before testing and then strategically allocate and automatically run those test cases in each application of CIT. Such a technique and a full application of it on the Eclipse IDEs using its existing test cases is also a contribution of this thesis.
In summary, this thesis contributes an algorithm that enables the application of CIT in industrial settings. Further, three advancements of CIT with applications were contributed to advance and demonstrate CIT as a product line testing technique.