Für eine korrekte Darstellung dieser Seite benötigen Sie einen XHTML-standardkonformen Browser, der die Darstellung von CSS-Dateien zulässt.

. .

ASE 2019 - Accompanying Material

Configurable N-Way Program Merging Strategies for Superimposition-based Analysis of Variant-Rich Software*

Dennis Reuling, Udo Kelter
Software Engineering Group
University of Siegen
{dreuling, kelter}@informatik.uni-siegen.de
Sebastian Ruland, Malte Lochau
Real-Time Systems Lab
TU Darmstadt
{sebastian.ruland, malte.lochau}@es.tu-darmstadt.de

*For a more detailed presentation of SiMPOSE concepts as well as extensive experimental evaluation results we refer to [RKB+19].


Modern software often exists in many different, yet similar versions and/or variants, usually derived from a common code base (e.g., via clone-and-own). In the context of product-line engineering, family-based-analysis has shown very promising potential for improving efficiency in applying quality-assurance techniques to variant-rich software, as compared to a variant-by-variant approach. Unfortunately, these strategies rely on an product-line representation superimposing all program variants in a syntactically well-formed, semantically sound and variant-preserving manner, which is manually hard to obtain in practice. We demonstrate the SiMPOSE methodology for automatically generating superimpositions of N given program versions and/or variants facilitating family-based analysis of variant-rich software. SiMPOSE is based on a novel N-way model-merging technique operating at the level of control-flow automata (CFA) representations of C programs, CFAs constitute a unified program abstraction utilized by many recent software-analysis tools. We illustrate different merging strategies supported by SiMPOSE, namely variant-by-variant, N-way merging, incremental 2-way merging, and partition-based N/2-way merging, and demonstrate how SiMPOSE can be used to systematically compare their impact on efficiency and effectiveness of family-based unit-test generation.

Tool Demonstration

Tool Download and Installation

Our presented tool is implemented in the Eclipse eco-system and can be installed locally as follows:
  • Download the Eclipse Modeling Tools:Download Page
  • Add the following update site URL to your Eclipse (copy link):
  • Install our tool using the update site above. You might need to deselect "Group items by category" for our tool feature to show up.
  • Since SiMPOSE makes use of CPAChecker for (family-based) analyses, you need to download and import the following Eclipse project: cpachecker_inclTiger.zip. Please select the project CPAChecker-incl-tiger for import, the remaining projects are unnecessary.
    You need to (re)compile CPAChecker in your Eclipse by selecting the build.xml in the imported project and select Run As -> ANT build. This will download all necessary libraries and build CPAChecker against your machine and may take some time. The output log of the process is printed in the Eclipse console.

Tool Execution

After installing the tool and importing our Example Project you can execute SiMPOSE:
  • Create a Run-configuration for starting the application. This can be done by selecting Run -> Run Configurations..., then create a new Eclipse Application (right click -> New).
  • Name the configuration SiMPOSE for easy recognition later on
  • In the tab Main select our SiMPOSE application to run:

  • Switch to the tab Arguments and choose the example project as working directory:

  • Press Apply and then execute the tool by selecting Run.
  • Errors regarding unresolved dependencies can be ignored as they are introduced by third-party software.
  • This should result in a console output similar to this:

  • The resulting output artifacts are to be found in the example project folders output and testsuites.
  • For inspecting the graphical representation of the corresponding CFA based on the DOT language we recommend the GraphViz or xdot tool.

Comparison of Merging Strategies

For analyzing the (used) merging strategies and their results, SiMPOSE offers the possibility to generate plots/charts about the generated testsuites:
  • Select the folder containing the testsuite(s) (i.e., folder CO) and generate charts by selecting the context menu entry:

  • NOTICE: The menu entry is only available in the "Package Explorer" view.
  • A subfolder /plots is created, containing all generated plots for all testsuites (of all functions).
  • For easier inspection, these plots are aggregated function-wise in a .html file, which can opened in any browser.
    For example, opening this file may look like:

  • Example Project / Subject Systems

    We extracted variable functions from BusyBox (version 1.24.2). We converted all preprocessor macros (#ifdef) into equivalent IF statements. Our selection of BusyBox consists of 42 variable C functions extracted from 312 BusyBox programs, each function having more than two variants.
    Hence, we included all these BusyBox functions and our running example in this Example Project which can be imported into Eclipse.

    Tool Configuration

    For running the tool you require an Eclipse project with the necessary configuration as well as variable code as input data.

    We recommend to download and import our Example Project and adapt it to your needs.
    This project contains our running example and busybox functions and can be used without adaptions. For tuning parameters as well as selecting the functions to process, you may want to adapt the file config/pipeline.properties.
    For more information about the detailed usage and features of SiMPOSE and its configuration we refer to the Tool Demonstration, which is based upon the example project.

    Our tool expects the following structure:
    • code: Folder that contains the source code of the respective functions. Each function requires a (unique) folder containing
      • (all) variants of the function
      • a property file which defines the set of variants to process as well as necessary information regarding the features used in this variable function
    • config: Folder that contains the configuration files for the pipeline and CPAchecker:
      • pipeline.properties: This file controls the pipeline of SiMPOSE, e.g. which files to process and what steps to execute. Furthermore we offer two default coverage criteria for test-generation, C0 and C3.
      • tiger-variants/tiger-variabilityAware.properties: These files configure the CPAChecker test-suite generation process. Although most parameters are default values, for making use of coverage criteria other than C0 and C3, the option tiger.fqlQuery in file tiger-variants needs to be defined. If this option is not defined the coverage criterium specified in pipeline.properties is used (C0 as default).
    Most of the configuration parameters are documented, please feel free to ask if questions arise via EMail.


    If an unknown error or exception is raised please do not hesitate to contact us by EMail. These errors are usually because of an (incomplete) erroneous build of CPAChecker or a missing folder/file during execution.


    • [RKB+19] D. Reuling, U. Kelter, J. Bürdek, and M. Lochau. (2019) : Automated N-way Program Merging for Facilitating Family-based Analyses of Variant-rich Software (accepted). In Proceedings of ACM Trans. Softw. Eng. Methodol. PrePrint Download