Toward Applying Variability-oblivious Static Analyses to Software Product Lines

Software variability has been shown to introduce bugs which only exist in certain variations of a software product line (SPL). A SPL is formed with configuration options which change select parts of the code. These configuration options lead to exponential growth in the number of variations, causing exhaustive analysis of an SPL to be infeasible. Existing techniques to analyze SPLs have used sampling techniques, created variability-aware analyses, and systematically lifted analysis techniques. Sampling SPLs allows the use of state-of-the- art analyzers, but only a small subset of program variations can be tested, leaving blind-spots for bugs to remain in. Variability-aware analyses solve this problem by analyzing an entire SPL at once. However, since these analyses must be adapted or made from scratch, their capabilities lag behind state-of-the-art tools. Systematic lifting allows for existing techniques to operate on a SPL, but no implementation has been shown to practically lift existing tools due to limitations of analysis type or input format. This dissertation explores approaches to systematically lift existing state-of-the-art tools to work on the entirety of a SPL. Our first approach is the desugaring approach, which aims to rewrite an entire SPL as one individual piece of code, and then apply existing analyzers the result to the desugared code. This approach is split into two works. The first work discusses the process and implementation of rewriting C and C Preprocessor code into a pure C representation. Rewriting has been attempted before, but prior attempts fail to handle the complexities of real-world preprocessor usage, and how they effect constructs such as user defined objects. We improve upon these with our tool SugarC, which implements a novel syntax-directed translation approach to rewriting, and discuss new optimizations to user defined objects which allow for real-world use. We evaluate SugarC on axTLS, Toybox, and Busybox, where it was shown to scale to real-world preprocessor usage for highly configurable programs. The second work presents a framework that applies existing variability-oblivious tools to the desugared representation and extracts implicit details. The desugaring process introduces infeasible paths, renames key methods like malloc and free, duplicates warnings that appear in multiple configurations, and obscures the configuration options requires for a given path. Our framework, Sugarlyzer, enables the analysis of SugarC output by addressing these issues and using alarm reports generated by existing analyzers to intuitively deduce the presence condition and feasibility of alarms. Through the generic design of Sugarlyzer, we implement three popular bug finders, Clang static analyzer, Infer, and Phasar, and use them to analyze axTLS, Toybox, and Busybox. We explore the findings from this approach and compare them to state-of-the-art sampling and variability-aware analyses. The desugaring approach reveals inherit unsoundness in static analyzers due to the multitude of paths that are added on top of their inability to know what configuration options are mutually exclusive. The third work of this dissertation addresses this as we explore the idea of generically lifting a language through variability input interpretation. Past lifting through variability-aware interpretation work has been stifled by reliance on variability-aware data structures as input, which prevents them from truly lifting many existing tools. We devise and implement a new approach to read any variable input and combine it with simultaneous- interpretation to lift any program at the language level. To highlight the modularity we present a case study where we lift a parser to being variability-aware, thus showing the feasibility of applying our approach to replicate some of the most powerful and widely use variability-aware tools.