New Tech Report on Analyzing Product Lines

Eric | November 13, 2012

I am happy to announce the availability of a new Tech Report on Transparent and Efficient Reuse of IFDS-based Static Program Analyses for Software Product Lines. This is joint work with Társis Tolêdo, Márcio Ribeiro, Claus Brabrand, Paulo Borba and Mira Mezini. In the paper, we show how an important class of program analyses designed for traditional programs can be transparently reused for software product lines.

From the abstract:

A software product line (SPL) encodes a potentially large variety of software products as variants of some common code base. Up until now, re-using traditional static analyses for SPLs was virtually intractable, as it required programmers to generate and analyze all products individually.

In this work, however, we show how an important class of existing inter-procedural static analyses can be transparently lifted to SPLs. Without requiring programmers to change a single line of code, our approach SPLLIFT automatically converts any analysis formulated for traditional programs within the popular IFDS framework for interprocedural, finite, distributive, subset problems to an SPL-aware analysis formulated in the IDE framework, a well-known extension to IFDS.

Using a full implementation based on Soot, CIDE and JavaBDD, we show that with SPLLIFT one can reuse IFDS-based analyses without changing a single line of code. Through experiments using three static analyses applied to four Java-based product lines, we were able to show that our approach produces correct results and outperforms the traditional approach by several orders of magnitude.

Much gratitude goes to to Ondrej Lhotak, who provided useful hints on optimizing BDDs. We also wish to thank the developers of CIDE, JavaBDD and Soot for making their tools available to us and for their continuing support. Thanks to Phil Pratt-Szeliga and Marc-Andre Laverdiere-Papineau, who provided help with analyzing J2ME MIDlets. Thanks also to Sven Apel who provided helpful feedback on an earlier version of this paper.

Our implementation is available for download in source, along with everything required to reproduce our experimental results. If you build on this implementation, we would appreciate if you’d let us know.