2021 · 45 citations · 34 references
ComputingComputer ScienceComputer SystemsDesign AutomationFormal MethodsOperating SystemsDeductive VerificationModel CheckingSoftware TestingSpecification LanguagesSymbolic ExecutionVerificationAutomated Bug FindingBug FixingBug TrackingConfiguration Space AnalysisKernel VulnerabilitiesSymbolic Execution EnginesSymbolic Execution Of Kernel CodeTesting
Highly-configurable software underpins much of our computing infrastructure. It enables extensive reuse, but opens the door to broken configuration specifications. The configuration specification language, Kconfig, is designed to prevent invalid configurations of the Linux kernel from being built. However, the astronomical size of the configuration space for Linux makes finding specification bugs difficult by hand or with random testing. In this paper, we introduce a software model checking framework for building Kconfig static analysis tools. We develop a formal semantics of the Kconfig language and implement the semantics in a symbolic evaluator called kclause that models Kconfig behavior as logical formulas. We then design and implement a bug finder, called kismet, that takes kclause models and leverages automated theorem proving to find unmet dependency bugs. kismet is evaluated for its precision, performance, and impact on kernel development for a recent version of Linux, which has over 140,000 lines of Kconfig across 28 architecture-specific specifications. Our evaluation finds 781 bugs (151 when considering sharing among Kconfig specifications) with 100% precision, spending between 37 and 90 minutes for each Kconfig specification, although it misses some bugs due to underapproximation. Compared to random testing, kismet finds substantially more true positive bugs in a fraction of the time.
34
Reverse engineering feature models
Steven She, Rafael Lotufo, Thorsten Berger et al. · 2011 · 297 citations
Architecture, Industrial Engineering, Feature Engineering +6
Feature consistency in compile-time-configurable system software
Reinhard Tartler, Daniel Lohmann, Julio Sincero et al. · 2011 · 190 citations
A comparison of 10 sampling algorithms for configurable systems
Flávio Medeiros, Christian Kästner, Márcio Ribeiro et al. · 2016 · 190 citations