Language-based Lifting of Analyses to Software Product Lines

Software Product Lines (SPLs) allow software engineering teams to develop families of products together using a common set of artifacts. The goal is to maximize reuse of artifacts (requirements, design models, source code, test cases, etc...) across related products. Many of the analysis tools (e.g., static analysis, model checking, test-case generation) used throughout the engineering process are designed to analyze one product at a time. Several attempts have been made to \emph{lift} some of those analysis tools to analyze the whole product line at once, leveraging the amount of commonality between individual products to avoid the intractability of analyzing each product instance by itself in a brute-force fashion. In this thesis, we address the problem from a different angle. Instead of lifting an analysis, we lift languages used to implement analyses. Since a given analysis is a program written in some programming language, extending that language with variability-aware constructs would allow for reinterpreting the original analysis program to process a product line instead of a single product. We presented the lifting of two languages: Datalog, and an extended version of Programming Computable Functions (PCF). Datalog combines relational data definition and manipulation, together with logical inference. It has been used to implement different categories of declarative, succinct, and easy to understand software analyses. We present syntactic extensions to Datalog to allow variability annotations of facts, and a variability-aware inference algorithm. In addition, we present two approaches to automatic variability-aware lifting of software analyses written in a functional language (PCF+). A light-weight, black-box approach (shallow lifting) wraps an analysis in its variability-aware version. The second approach (deep lifting) is an automatic program-rewriting mechanism that translates an analysis program into a semantically equivalent variability-aware analysis. We evaluated the lifted versions of Datalog and PCF+ on a set of Java and C-language benchmarks, comparing their performance against brute-force analysis. Our evaluation results validate our assumption that variability-aware analysis is in general orders of magnitude faster than brute-force analysis. Also in the case of Datalog analyses, variability-aware analysis resulted in similar savings in fact database size.Ph.D