Presence-Condition Simplification in
Highly Configurable Systems

– Supplementary Website –

Overview





Uni Logo

Chair of Software Engineering

Software Systems Lab

Generative Software Development Lab, University of Waterloo

Overview

This website provides supplementary material for the ICSE 2015 paper "Presence-Condition Simplification in Highly Configurable Systems". The paper describes the problem of presence-condition simplification, a formal definition, application scenarios and an evaluation of three algorithms. We will provide the experiment results and links to the tools necessary for reproduction of the experiments on this page.

Tools

In our experiments, we used two tools: JavaBDD (version 1.0b2) and Espresso. Both can be used for presence-condition simplification as described in the paper. JavaBDD can be obtained here: http://javabdd.sourceforge.net/. For Espresso, multiple versions exist. The original version can be obtained from the University of Berkeley: http://embedded.eecs.berkeley.edu/pubs/downloads/espresso/index.htm. However, this version requires some work before it compiles and runs on modern machines. For our experiments we used the updated version Espresso-ab-1.0 obtained from ftp://ftp.cs.man.ac.uk/pub/amulet/balsa/other-software/espresso-ab-1.0.tar.gz.

Case Studies

We conducted five experiments (E1--E5) and used different sets of case studies for each experiment. The following table provides a complete list of the case studies and in which experiment they were used.

Apache http server (E1,E3)Berkeley DB (E3)Busybox (E3)Cherokee (E3)
Elevator (E2)E-mail (E1, E2)Freebsd (E3)Gimp (E3)
Gnumeric (E3)Gnuplot (E3)H264 (E1)Libxml2 (E3)
Linked list (E1)Linux v2.6.33.3 (E3, E4)Linux v3.4 (E3)Llvm (E1)
Openvpn (E3)Parrot (E3)Pkjab (E1)Postgresql (E3)
Qemu (E3)Sendmail (E3)SNW(E1)Splot models (E5)
Sqlite (E1,E3)Subversion (E3)Vim73 (E3)Xfig (E3)
Xterm (E3)Zipme (E1)

Results

This section describes where to download our results and how to interpret them We conducted five experiments (named E1--E5) for the paper. We describe the technical setup of the experiment here. For experiment E1 we also provide additional plots that did not fit in the paper. For more details on the meaning of the data please read the paper.

After publication of the paper, we found a bug in our evaluation. We re-ran the entire evaluation and provide the correct plots in the download links of this website. The bug did only have minor effect on most values in the evaluation (1-2%).

  • E1 "Classification of Variants"
  • E2 "Reporting Defect Locations"
  • E3 "Code Annotation Simplification"
  • E4 "AST Annotation Simplification"
  • E5 "Scalability"

For experiments E1, E2 and E5 we provide a log file and a CSV file each. The CSV file contains, for each simplification, the original presence condition, the context and the simplified (with BDD) condition, each in textual form. Furthermore, we list the time needed for simplification (with BDD, Espresso and Quine-McCluskey) and the size of the expressions. These are the links to the result archives: Results E1 Results E2 Results E5.
Here is the link to the additional plots for Experiment E1: Plots E1

For experiment E3, we used 21 systems with preprocessor variability. The experiment was conducted in three steps: 1) We used KBuildMiner to generate presence conditions for files in systems with KConfig build systems. 2) We used Predator to extract the conditions of preprocessor directives and the hierarchy of the directives. 3) Based on the hierarchy and the file conditions, we generated contexts for each presence condition and simplified them. Due to their size, we cannot provide the result of step 2), but we provide the result of step 3) here. The archive contains a filtered analysis file "E3_IfdefConditions_log_31_07_2014.txt" which provides information for each case study. The example below shows the time to simplify all conditions of Linux-3.4, the conditions which could not be parsed (3636), the conditions which could be parsed but were trivial (25424), the conditions which could be parsed and were non-trivial (42098), and the analyzed code files (31351). The example also shows how many of the non-trivial presence conditions could be simplified depending on the algorithm (BDD, Espresso, or Quine-McCluskey) and the size measure (literals, operations, or BDD nodes).

TypeChef-LinuxAnalysis-3.4:
Total time for simplification: 632700 ms
problemLines:3636 ok/non-trivial Lines:42098 ok/trivial Lines:25424 okFiles:31351
...
improvedLines Lits BDD (51) 0.12114589766734762% of non-trivial
improvedLines Ops BDD (17) 0.04038196588911587% of non-trivial
improvedLines Nodes BDD (2045) 4.857712955484821% of non-trivial

improvedLines Lits E (264) 0.6271081761603877% of non-trivial
improvedLines Ops E (31) 0.07363770250368189% of non-trivial
improvedLines Nodes E (264) 0.6271081761603877% of non-trivial

improvedLines Lits QC (264) 0.6271081761603877% of non-trivial
improvedLines Ops QC (31) 0.07363770250368189% of non-trivial
improvedLines Nodes QC (264) 0.6271081761603877% of non-trivial

For experiment E4, we ran a patched version of a fork of TypeChef on Linux-3.6.33. The we patched version of the fork with this patch. After TypeChef has generated an AST, the patch code scans the entire AST and prints the presence conditions and contexts in a log file. The log file has over 17GB, so we do not provide it here. We parse the log file, simplify the presence conditions and generate a CSV file which contains the presence condtion, the context, the simplified condition, and size statistics for each. We provide this CSV file here. In the paper we show the sizes of the presence conditions before and after the simplification measured as the number of literals. Here we also provide corresponding plots generated with the number of operators and the number of BDD nodes as size measure.

Contact

The paper "Presence-Condition Simplification in Highly Configurable Systems" has been written by Alexander von Rhein, Alexander Grebhahn, Sven Apel, Norbert Siegmund, Dirk Beyer, and Thorsten Berger. For questions regarding the paper, please contact the authors.