Intraprocedural Data-flow Analysis for Software Product Lines

Abstract:

Software product lines (SPLs) developed using annotative approaches such as conditional compilation come with an inherent risk of constructing erroneous products. For this reason, it is essential to be able to analyze such SPLs. However, as dataflow analysis techniques are not able to deal with SPLs, developers must generate and analyze all valid products individually, which is expensive for non-trivial SPLs.
In this paper, we demonstrate how to take any standard intraprocedural dataflow analysis and automatically turn it into a feature-sensitive dataflow analysis in five different ways where the last is a combination of the other four. All analyses are capable of analyzing all valid products of an SPL without having to generate all of them explicitly.
We have implemented all analyses using SOOT’s intraprocedural dataflow analysis framework and experimentally evaluated four of them according to their performance and memory characteristics on five qualitatively different SPLs. On our benchmarks, the combined analysis strategy is up to almost eight times faster than the brute-force approach.

Source Code

The source code of our feature-sensitive dataflow analysis implementation is available at through SVN in our Assembla space.

General Instructions

You can find some instructions about how to install our plug-in along with an architectural overview and implementation details here.

Results

This archive contains the raw data described in the paper; measured analysis time, memory, compilation estimates and other metrics.

The data for the cache experiment is in this separate archive.

Both the data for main and cache experiments are in a spreadsheet format. Every sheet on the spreadsheet files contain information collected about all the methods in each benchmark by our infrastructure for 10 separate runs.

Note: We have found that because Soot may not generate the same name for anonymous classes consistently on every execution, data for methods in anonymous classes should be inspected with when comparing data between different runs.

Benchmarks

All SPLs we used are available here.

-- TarsisToledo - 2012-07-12 -- TarsisToledo - 2012-10-16 -- TarsisToledo - 2012-11-12