CADOS: Configurability-Aware Development of Operating Systems (DFG: LO 1719/3-2)

Todays operating systems (as well as other system software) offer a great deal of static configurability to tailor them with respect to a specific application or hardware platform. Linux 4.2, for instance, provides (via its Kconfig models and tools) more than fifteen thousand configurable features for this purpose. Technically, the implementation of all these features is spread over multiple levels of the software generation process, including the configuration system, build system, C preprocessor, compiler, linker, and more. This enormous variability has become unmanageable in practice; in the case of Linux it already has led to thousands of variability defects within the lifetime of Linux. With this term, we denote bugs and other quality issues related to the implementation of variable features. Variability defects manifest as configuration consistency and configuration coverage issues.

In the CADOS project, we investigate scalable methods and tools to grasp the variability on every layer within the configuration and implementation space, visualize and analyze it and, if possible, adjust it while maintaining a holistic view on variability.

Our findings have already led to more than 100 accepted patches in the Linux mainline kernel (see our EuroSys '11 and SPLC '12 papers) and an approach for the automatic tailoring of Linux server systems in order to reduce the exploitable code base (see our HotDep '12 paper). The issue of configuration coverage is addressed in our USENIX '14 paper. Our scalable AST-based hashing method to detect relevant changes in C-source files got a best paper award at USENIX '17.

CADOS in the Wild

Tools

Various tools assist our analysis of the variability in the Linux kernel and other software projects. Our most important tool is called the undertaker, which searches and reports dead and undead conditional CPP blocks. Since its inception within VAMOS, it has matured to a toolbox of utilities for answering various research questions related to variability in general. For further details, please look into the undertaker trac.

Tailoring of Shared Libraries

Shared libraries are generally designed as reusable, general-purpose collections of related functionality which can be accessed by application programs. However, in a strictly defined deployment scenario - like an embedded device - only a small part of the entire functionality might actually be required by the applications present on the device. As it is often impossible to customize shared libraries in a fine-grained manner during the build process, and as we might not have access to their original source code, we developed a lightweight binary tailoring method to detect and remove unneeded code from shared libraries. By combining static and dynamic analysis, we determine which functions are needed in the deployment scenario, delete unused functions from the binary files and shrink the library files by compressing the memory layout on disk. Our tools and the evaluation data for the paper presented at EMSOFT 2019 are available in our GitLab repository.

PaStA: Patch-Stack Analysis

PaStA quantitatively analyses the evolution of patch stacks by mining git repositories and produces data that can serve as input for statistical analysis. It compares different releases of stacks and groups similar patches (patches that lead to similar modifications) into equivalence classes. This allows us to compare those classes against the base project to measure integrability and influence of the patch stack on the base project. PaStA is furthermore able to map mails from mailboxes (e.g., dumps of mailing lists or public inboxes) to commit hashes of repositories. This makes it possible to trace the evolution of patches on mailing lists, like the LKML.

Multiverse

While static variability can be completely resolved at compile time, dynamic variation points come at a cost arising from extra tests and branches in the control flow. Multiverse is an approach to handle dynamic variability efficiently by means of binary patching. It provides an extension to the C programming language that enables the developer to express dynamic variability in performance-critical paths. With specially annotated config variables, multiverse can generate multiple versions of a function and dynamically binary patch the running system to use the version of the current configuration. The goal is to narrow the gap between dynamic and static variability by allowing the developer to easily employ run-time configurability at zero or low cost.

vampyr

This tool is a wrapper for undertaker to do coverage analysis or variability-aware static analysis on source files. For the static analysis compilers such as gcc or clang are employed. Please refer to the USENIX '14 paper for detailed information.

undertaker-checkpatch

This tool reports changes to defects such as newly introduced or fixed defects. Defects can also be correlated to changes in Kconfig and the build system (Make, Kbuild) and vice versa. Additionally, undertaker-checkpatch ships the functionality to further analyze the causes of defects, displaying contradictory Kconfig items, a block's precondition or the defect causing formula. Since version 1.6, undertaker is able to minimize defect formulas (thanks to the PicoMUS-Tool which is part of PicoSAT). This functionality can be used in undertaker-checkpatch to further analyze and understand the cause of defects.

Flipper: Lightweight Kernel Tailoring

Configuring Linux is hard. With over 14,000 options to choose from, making an informed decision about every single one of them takes a very long time. While distributions for standard day-to-day use simply enable as many features (drivers, supported platforms, ...) as possible, this is not a practical solution for embedded systems, where memory is scarce and must not be wasted. To make it easier for an engineer to derive a small starting point to configure the system, we developed Flipper. Flipper provides a lean method to trace which functionality was exerted in the kernel. Using the Tailor tool from the undertaker package, a small, use-case specific configuration for Linux can be generated from the collected data. Flipper is part of undertaker release (v1.6) and can be downloaded here, for detailed usage instructions please read the README file provided in the tailor/flipper subdirectory.

Wundertaker

Wundertaker is a Web GUI visualizing #ifdefs and undertaker's defect reports in Linux code files. The source including installation instructions can be downloaded here. A detailed description of the tool and its implementation can also be found in the Bachelor's thesis of Patrick Plagwitz.

People

Latest News

Publications

ICSOFT Conference B Best Student Paper
TASTING: Reuse Test-case Execution by Global AST Hashing

Tobias Landsberg, Christian Dietrich, Daniel LohmannProceedings of the 17th International Conference on Software Technologies - ICSOFTSciTePress2022Best Student Paper.
PDF 10.5220/0011139200003266 [BibTex]

×

BibTex Entry

@inproceedings{landsberg:22:icsoft,
 address = {Lisbon, Portugal},
 author = {Landsberg, Tobias and Dietrich, Christian and Lohmann, Daniel},
 booktitle = {Proceedings of the 17th International Conference on Software Technologies - ICSOFT},
 doi = {10.5220/0011139200003266},
 entrysubtype = {Conference},
 isbn = {978-989-758-588-3},
 issn = {2184-2833},
 month = {July},
 organization = {INSTICC},
 pages = {33-45},
 publisher = {SciTePress},
 title = {TASTING: Reuse Test-case Execution by Global AST Hashing},
 userc = {CORE21:B},
 userd = {ICSOFT 2022},
 year = {2022}
}

Close

OSDI Conference A*
From Global to Local Quiescence: Wait-Free Code Patching of Multi-Threaded Processes

Florian Rommel, Christian Dietrich, Daniel Friesel, Marcel Köppen, Christoph Borchert, Michael Müller, Olaf Spinczyk, Daniel Lohmann14th Symposium on Operating System Design and Implementation (OSDI '20)2020.
PDF Details Video [BibTex]

×

BibTex Entry

@inproceedings{rommel:20:osdi,
 author = {Florian Rommel and Christian Dietrich and Daniel Friesel and Marcel K{\"o}ppen and Christoph Borchert
and Michael M{\"u}ller and Olaf Spinczyk and Daniel Lohmann},
 booktitle = {14th Symposium on Operating System Design and Implementation (OSDI '20)},
 entrysubtype = {Conference},
 month = {November},
 pages = {651-666},
 title = {From Global to Local Quiescence: Wait-Free Code Patching of Multi-Threaded Processes},
 userc = {CORE18:A*},
 userd = {OSDI '20},
 year = {2020}
}

Close

CCSW Workshop
The Sound of Silence: Mining Security Vulnerabilities from Secret Integration Channels in Open-Source Projects

Ralf Ramsauer, Lukas Bulwahn, Daniel Lohmann, Wolfgang MauererProceedings of the 12th Cloud Computing Security Workshop (CCSW '20)ACM2020.
PDF Video 10.1145/3411495.3421360 [BibTex]

×

BibTex Entry

@inproceedings{ramsauer:20:ccs-ccsw,
 author = {Ralf Ramsauer and Lukas Bulwahn and Daniel Lohmann and Wolfgang Mauerer},
 booktitle = {Proceedings of the 12th Cloud Computing Security Workshop (CCSW '20)},
 doi = {10.1145/3411495.3421360},
 entrysubtype = {Workshop},
 month = {11},
 numpages = {9},
 publisher = {ACM},
 title = {The Sound of Silence: Mining Security Vulnerabilities from Secret Integration Channels in Open-Source
Projects},
 userd = {CCSW},
 venue = {Virtual Event},
 year = {2020}
}

Close

EMSOFT Journal A
Honey, I Shrunk the ELFs: Lightweight Binary Tailoring of Shared Libraries

Andreas Ziegler, Julian Geus, Bernhard Heinloth, Timo Hönig, Daniel LohmannACM Transactions on Embedded Computing Systems18.5sACM Press2019.
PDF Raw Data 10.1145/3358222 [BibTex]

×

BibTex Entry

@article{ziegler:19:emsoft,
 acmid = {3358222},
 address = {New York, NY, USA},
 articleno = {102},
 author = {Andreas Ziegler and Julian Geus and Bernhard Heinloth and Timo H{\"o}nig and Daniel Lohmann},
 doi = {10.1145/3358222},
 entrysubtype = {Journal},
 issn = {1539-9087},
 journal = {ACM Transactions on Embedded Computing Systems},
 keywords = {Shared Libraries; Binary Tailoring; Linux},
 month = {October},
 number = {5s},
 numpages = {23},
 pages = {102:1--102:23},
 publisher = {ACM Press},
 title = {Honey, {I} Shrunk the {ELFs}: Lightweight Binary Tailoring of Shared Libraries},
 userc = {CORE18:A},
 userd = {EMSOFT '19},
 volume = {18},
 year = {2019}
}

Close

EuroSys Conference A
Multiverse: Compiler-Assisted Management of Dynamic Variability in Low-Level System Software

Florian Rommel, Christian Dietrich, Michael Rodin, Daniel LohmannFourteenth EuroSys Conference 2019 (EuroSys '19)ACM Press2019.
PDF Slides 10.1145/3302424.3303959 [BibTex]

×

BibTex Entry

@inproceedings{rommel:19:eurosys,
 address = {New York, NY, USA},
 author = {Florian Rommel and Christian Dietrich and Michael Rodin and Daniel Lohmann},
 booktitle = {Fourteenth EuroSys Conference 2019 (EuroSys '19)},
 doi = {10.1145/3302424.3303959},
 entrysubtype = {Conference},
 isbn = {978-1-4503-6281-8},
 publisher = {ACM Press},
 title = {Multiverse: Compiler-Assisted Management of Dynamic Variability in Low-Level System Software},
 userc = {CORE18:A},
 userd = {EuroSys '19},
 venue = {Dresden, Germany},
 year = {2019}
}

Close

ICSE Conference A*
The List is the Process: Reliable Pre-Integration Tracking of Commits on Mailing Lists

Ralf Ramsauer, Daniel Lohmann, Wolfgang MauererProceedings of the 41st International Conference on Software Engineering (ICSE '19)2019.
PDF Raw Data 10.1109/ICSE.2019.00088 [BibTex]

×

BibTex Entry

@inproceedings{ramsauer:19:icse,
 author = {Ralf Ramsauer and Daniel Lohmann and Wolfgang Mauerer},
 booktitle = {Proceedings of the 41st International Conference on Software Engineering (ICSE '19)},
 doi = {10.1109/ICSE.2019.00088},
 entrysubtype = {Conference},
 month = {May},
 pages = {807--818},
 title = {The List is the Process: Reliable Pre-Integration Tracking of Commits on Mailing Lists},
 userc = {CORE18:A*},
 userd = {ICSE '19},
 venue = {Montreal, QC, Canada},
 year = {2019}
}

Close

PLOS Workshop B
Wait-Free Code Patching of Multi-Threaded Processes

Florian Rommel, Lennart Glauer, Christian Dietrich, Daniel LohmannProceedings of the 10th SOSP Workshop on Programming Languages and Operating Systems (PLOS '19)ACM2019.
PDF 10.1145/3365137.3365404 [BibTex]

×

BibTex Entry

@inproceedings{rommel:19:plos,
 acmid = {3365404},
 address = {New York, NY, USA},
 author = {Rommel, Florian and Glauer, Lennart and Dietrich, Christian and Lohmann, Daniel},
 booktitle = {Proceedings of the 10th SOSP Workshop on Programming Languages and Operating Systems (PLOS '19)},
 doi = {10.1145/3365137.3365404},
 entrysubtype = {Workshop},
 isbn = {978-1-4503-7017-2},
 location = {Huntsville, ON, Canada},
 numpages = {7},
 pages = {23--29},
 publisher = {ACM},
 title = {Wait-Free Code Patching of Multi-Threaded Processes},
 userc = {CORE18:B},
 userd = {PLOS '19},
 year = {2019}
}

Close

USENIX Conference A Best Paper Award
cHash: Detection of Redundant Compilations via AST Hashing

Christian Dietrich, Valentin Rothberg, Ludwig Füracker, Andreas Ziegler, Daniel LohmannProceedings of the 2017 USENIX Annual Technical Conference (USENIX '17)USENIX Association2017Best Paper Award.
PDF Details Slides Raw Data [BibTex]

×

BibTex Entry

@inproceedings{dietrich:17:usenix,
 address = {Berkeley, CA, USA},
 author = {Christian Dietrich and Valentin Rothberg and Ludwig Füracker and Andreas Ziegler and Daniel Lohmann},
 booktitle = {Proceedings of the 2017 USENIX Annual Technical Conference (USENIX '17)},
 entrysubtype = {Conference},
 location = {Santa Clara, CA, USA},
 month = {July},
 publisher = {USENIX Association},
 title = {{cHash:} Detection of Redundant Compilations via {AST} Hashing},
 url = {https://www.usenix.org/conference/atc17/technical-sessions/presentation/dietrich},
 userc = {CORE18:A},
 userd = {USENIX '17},
 venue = {Santa Clara, CA, USA},
 year = {2017}
}

Close

VAMOS Workshop
Analyzing the Impact of Feature Changes in Linux

Andreas Ziegler, Valentin Rothberg, Daniel LohmannProceedings of the Tenth International Workshop on Variability Modelling of Software-intensive Systems2016.
PDF 10.1145/2866614.2866618 [BibTex]

×

BibTex Entry

@inproceedings{ziegler:16:vamos,
 address = {New York, NY, USA},
 author = {Andreas Ziegler and Valentin Rothberg and Daniel Lohmann},
 booktitle = {{Proceedings of the Tenth International Workshop on Variability Modelling of Software-intensive Systems}},
 doi = {10.1145/2866614.2866618},
 editor = {Ina Schaefer and Vander Alves and Eduardo Santana de Almeida},
 entrysubtype = {Workshop},
 isbn = {978-1-4503-4019-9},
 keywords = {CADOS, Linux},
 location = {Salvador, Brazil},
 pages = {25--32},
 title = {{Analyzing the Impact of Feature Changes in Linux}},
 userd = {VAMOS '16},
 year = {2016}
}

Close

VAMOS Workshop
Feature Models in Linux - From Symbols to Semantic

Valentin Rothberg, Nicolas Dintzner, Andreas Ziegler, Daniel LohmannProceedings of the Tenth International Workshop on Variability Modelling of Software-intensive Systems2016.
PDF 10.1145/2866614.2866624 [BibTex]

×

BibTex Entry

@inproceedings{rothberg:16:vamos,
 address = {New York, NY, USA},
 author = {Valentin Rothberg and Nicolas Dintzner and Andreas Ziegler and Daniel Lohmann},
 booktitle = {Proceedings of the Tenth International Workshop on Variability Modelling of Software-intensive Systems},
 doi = {10.1145/2866614.2866624},
 editor = {Ina Schaefer and Vander Alves and Eduardo Santana de Almeida},
 entrysubtype = {Workshop},
 isbn = {978-1-4503-4019-9},
 keywords = {CADOS, Linux},
 location = {Salvador, Brazil},
 pages = {65--72},
 title = {Feature Models in {Linux} - From Symbols to Semantic},
 userd = {VAMOS '16},
 year = {2016}
}

Close

OpenSym Conference
Observing Custom Software Modifications: A Quantitative Approach of Tracking the Evolution of Patch Stacks

Ralf Ramsauer, Daniel Lohmann, Wolfgang MauererProceedings of the 12th International Symposium on Open Collaboration (OpenSym '16)2016.
PDF 10.1145/2957792.2957810 [BibTex]

×

BibTex Entry

@inproceedings{ramsauer:16:opensym,
 address = {New York},
 author = {Ralf Ramsauer and Daniel Lohmann and Wolfgang Mauerer},
 booktitle = {Proceedings of the 12th International Symposium on Open Collaboration (OpenSym '16)},
 doi = {10.1145/2957792.2957810},
 editor = {Tony Wassermann},
 entrysubtype = {Conference},
 keywords = {CADOS; patch stacks; collaboration; Linux; maintenance},
 location = {Berlin},
 title = {Observing Custom Software Modifications: A Quantitative Approach of Tracking the Evolution of Patch Stacks},
 userd = {OpenSym '16},
 year = {2016}
}

Close

GPCE Conference B
Towards Scalable Configuration Testing in Variable Software

Valentin Rothberg, Christian Dietrich, Andreas Ziegler, Daniel LohmannProceedings of the 2016 International Conference on Generative Programming: Concepts and Experiences (GPCE '16)2016.
PDF 10.1145/2993236.2993252 [BibTex]

×

BibTex Entry

@inproceedings{rothberg:16:gpce,
 author = {Valentin Rothberg and Christian Dietrich and Andreas Ziegler and Daniel Lohmann},
 booktitle = {{Proceedings of the 2016 International Conference on Generative Programming: Concepts and Experiences (GPCE '16)}},
 doi = {10.1145/2993236.2993252},
 editor = {Bernd Fischer and Ina Schaefer},
 entrysubtype = {Conference},
 isbn = {978-1-4503-4446-3},
 location = {Amsterdam},
 title = {{Towards Scalable Configuration Testing in Variable Software}},
 userc = {CORE18:B},
 userd = {GPCE '16},
 year = {2016}
}

Close

OSR Journal
The dataref versuchung

Christian Dietrich, Daniel LohmannACM SIGOPS Operating Systems Review: Special Issue on Repeatability and Sharing of Experimental ArtifactsACM Press2015.
PDF 10.1145/2723872.2723880 [BibTex]

×

BibTex Entry

@article{dietrich:15:acmosr,
 address = {New York, NY, USA},
 author = {Christian Dietrich and Daniel Lohmann},
 doi = {10.1145/2723872.2723880},
 entrysubtype = {Journal},
 journal = {ACM SIGOPS Operating Systems Review: Special Issue on Repeatability and Sharing of Experimental Artifacts},
 numpages = {10},
 pages = {51--60},
 publisher = {ACM Press},
 title = {The {dataref} {versuchung}},
 userd = {OSR 49.1},
 year = {2015}
}

Close

GPCE Conference B
Automatic Feature Selection in Large-Scale System-Software Product Lines

Andreas Ruprecht, Bernhard Heinloth, Daniel LohmannProceedings of the 13th International Conference on Generative Programming and Component Engineering (GPCE '14)ACM Press2014.
PDF 10.1145/2658761.2658767 [BibTex]

×

BibTex Entry

@inproceedings{ruprecht:14:gpce,
 address = {New York, NY, USA},
 ar = {34\% (16/47)},
 author = {Andreas Ruprecht and Bernhard Heinloth and Daniel Lohmann},
 booktitle = {Proceedings of the 13th International Conference on Generative Programming and Component Engineering (GPCE '14)},
 doi = {10.1145/2658761.2658767},
 editor = {Matthew Flatt},
 entrysubtype = {Conference},
 isbn = {978-1-4503-3161-6},
 keywords = {CADOS,VAMOS, Linux, Tailoring, optimiziaton, experimentation},
 month = {September},
 pages = {39--48},
 publisher = {ACM Press},
 title = {Automatic Feature Selection in Large-Scale System-Software Product Lines},
 userc = {CORE18:B},
 userd = {GPCE '14},
 venue = {V{\"a}ster{\r{a}}s, Sweden},
 year = {2014}
}

Close

USENIX Conference A
Static Analysis of Variability in System Software: The 90,000 #ifdefs Issue

Reinhard Tartler, Christian Dietrich, Julio Sincero, Wolfgang Schröder-Preikschat, Daniel LohmannProceedings of the 2014 USENIX Annual Technical Conference (USENIX '14)USENIX Association2014.
PDF Raw Data [BibTex]

×

BibTex Entry

@inproceedings{tartler:14:usenix,
 address = {Berkeley, CA, USA},
 ar = {18\% (44/241)},
 author = {Reinhard Tartler and Christian Dietrich and Julio Sincero and Wolfgang Schr{\"o}der-Preikschat and Daniel Lohmann},
 booktitle = {Proceedings of the 2014 USENIX Annual Technical Conference (USENIX '14)},
 category = {L4},
 entrysubtype = {Conference},
 isbn = {978-1-931971-10-2},
 month = {June},
 pages = {421--432},
 publisher = {USENIX Association},
 title = {Static Analysis of Variability in System Software: The 90,000 \#ifdefs Issue},
 url = {https://www.usenix.org/conference/atc14/technical-sessions/presentation/tartler},
 userc = {CORE18:A},
 userd = {USENIX '14},
 venue = {Philadelphia, PA, USA},
 year = {2014}
}

Close

Theses

Currently Running

Finished Theses