EmergentAndDataflow < SPG

SPG Web>SoftwareProductivityGroup>GenteAreaProjects>EmergentAndDataflow (2012-07-13, TarsisToledo) (raw view)
---++ Emergent Interfaces and Data-flow Analysis for Software Product Lines

---+++ Intra-Procedural Data-flow Analysis for Software Product Lines

*Abstract:*

Software product lines (SPLs) are commonly developed using annotative approaches such as conditional compilation that come with an inherent risk of constructing erroneous products. For this reason, it is essential to be able to analyze SPLs. However, as dataflow analysis techniques are not able to deal with SPLs, developers currently have to brute force generate all valid methods and analyze all of them 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 three different ways. All are capable of analyzing all valid methods of an SPL without having to generate all of them explicitly. We have implemented all analyses as extensions of SOOT&rsquo;s intraprocedural dataflow analysis framework and experimentally evaluated their performance and memory characteristics on four qualitatively different SPLs. The results indicate that the feature-sensitive analyses may be up to eight times faster than the brute force approach and that the analyses have different time and space tradeoffs.

---++++ Source Code

Our implementation is available at [[https://www.assembla.com/code/cide_ei_rmk/subversion/nodes][our Assembla space]].

---++++ General Instructions

You can find [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=2;filename=companion.pdf][here]] some instructions about how to install our plug-in along with an architectural overview and implementation details.

---++++ Results

---+++++ Feature-oblivious (Brute force approach) data

Consists of building all valid method variants and analyzing them one by one using a conventional data-flow analysis. The results can be found [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=1;filename=fo.rar][here]].

---+++++ Feature-sensitive (Consecutive, Simultaneous and Lazy-sharing approaches), memory data, and cache misses data.

The data collected are packed into 2 rar files:
   * [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=1;filename=fs.rar][Feature-sensitive analysis data]]
   * [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=1;filename=mem.rar][Memory consuption data]]
The cache misses numbers are also packed in 2 files: normal and full cache. More specifically, we compare cache misses of two feature-sensitive approaches: consecutive (A2) and simultaneous (A3). To collect data with respect to cache misses, we used the [[http://sosoa.inf.unisi.ch/Instruments/Overseer][Overseer]] tool.
   * [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=1;filename=cache-normal.zip][Normal Cache]]
   * [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=1;filename=cache-purge.zip][Full Cache]]
The equivalence proofs of the feature-sensitive approaches are available [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=2;filename=proof.pdf][here]].

---++++ Benchmarks

All SPLs we used are available here. Their features are annotated by using [[http://www.fosd.de/cide][CIDE]].

   * [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=1;filename=BerkeleyDb.zip][Berkeley DB]]
   * [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=1;filename=GPL.zip][Graph Product Line]]
   * [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=1;filename=Lampiro.zip][Lampiro]]
   * [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=1;filename=MM08.zip][Mobile Media 08]]
Histograms of each benchmark:

   * [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=1;filename=BKDB.png][Berkeley DB]]
   * [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=1;filename=GPL.png][Graph Product Line]]
   * [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=1;filename=Lampiro.png][Lampiro]]
   * [[http://twiki.cin.ufpe.br/twiki/bin/viewfile/SPG/EmergentAndDataflow?rev=1;filename=MM08.png][Mobile Media 08]]
<!--
---+++ Emergent Feature Modularization (SPLASH/Onward! 2010)

*Abstract:* Virtual Separation of Concerns (VSoC) reduces the drawbacks of implementing product line variability with preprocessors. Developers can focus on certain features and hide others of no interest. However, these features eventually share elements between them, which might break feature modularization, since modifications in a feature result in problems for another. The concept of emergent feature modularization aims to establish contracts between features, to prevent developers from breaking other features when performing a maintenance task. These interfaces are product-line-aware, in the sense that it only considers valid feature combinations.

In what follows, we present our prototype tool that implements the emergent concept. We implemented the tool based on [[http://www.fosd.de/cide][CIDE]]. CIDE avoids #ifdef preprocessors and use colors instead to represent features. In addition, it is possible to hide features of no interest for the particular maintenance task. For explaining purposes, we did not hide feature code.

The idea consists of establishing contracts among feature implementations. We call our approach emergent because the components and interfaces here are neither predefined nor have a rigid structure. Instead, they emerge on demand to give support for specific feature development or maintenance tasks. For example, using the emergent concept, the developer firstly selects feature code to maintain. We
associate this selection with a feature, or a combination of features, which we denote as a feature expression. Then, information with respect to the other features and their combinations emerge through an interface. The example below illustrates an emergent interface with respect to the selected code.

%ATTACHURL%/EmergentInterfaceExample.png

According to the emergent interface, the developer should be careful before maintaining the selected code (_x = 3_ statement). The interface states that products that contain feature B (orange) use _x = 3_. This way, developers must take care about this dependency. They should analyze if changes to _x_ value impact feature B (orange), specially because this feature might be hidden, according to the Virtual Separation of Concerns approach implemented by CIDE. Notice that for products that contain both features (A, yellow; and B, orange), changing the value of _x_ is not a problem for feature B (orange), since its value is redefined (see line 55). In such a case, the emergent interface would be empty.

Benefits of using Emergent Interfaces:

   * Helps on avoiding errors during feature maintenance, since the information indicates to developers which features might be impacted.
   * Abstracts feature code (we still rely on hiding feature code) but at the same time provides valuable information about dependencies between features;
   * Gives information about which feature combinations are impacted; developers now focus on testing these combinations after maintenance instead of all of them;

Emergent Interfaces are generated by using _Data-Flow Analysis for Software Product Lines_ (feature-sensitive approach).

The following figure illustrates how both projects (_Data-Flow Analysis for Software Product Lines_ and _Emergent Interfaces_) are connected. It represents the architecture of our complete tool.

%ATTACHURL%/Architecture.png
-->

---+++ Members:

---+++++ CIn-UFPE
   * [[http://www.cin.ufpe.br/~mmr3][Márcio Ribeiro]] (PhD student)
   * [[http://www.cin.ufpe.br/~twt][Társis Toledo]] (MSc student)
   * [[http://www.cin.ufpe.br/~phmb][Paulo Borba]] (Faculty)

---+++++ IT University of Copenhagen
   * [[http://www.itu.dk/~brabrand/][Claus Brabrand]] (Faculty)

---+++ Errata
   * In Figure 9 (d), BerkeleyDB has actually no methods with 8 features (x-axis) and thus no variants (y-axis).
   * The archive file linked above with the sheets for the feature-oblivious experiment do not contain the removal of the 2 outliers, as described in the paper. The data presented in the paper, however, is correct. [[%ATTACHURL%/fo-errata.tar.gz][Here]] are the updated sheets.
   * The feature-sensitive data time measurement for MobileMedia08 does not contain the removal of the outliers as described in the paper. [[%ATTACHURL%/fs-errata.tar.gz][Here]] is the updated sheet. There is little change to the final results, and the overall conclusions are the same.

-- Main.TarsisToledo - 2012-07-13 -- Main.TarsisToledo - 23 Jan 2012 -- Main.MarcioRibeiro - 26 Dec 2011 -- Main.TarsisToledo - 20 Dec 2011 -- Main.MarcioRibeiro - 11 Dec 2011 -- Main.MarcioRibeiro - 09 Dec 2011 -- Main.MarcioRibeiro - 10 Apr 2011 -- Main.MarcioRibeiro - 10 Dec 2010
Topic revision: r17 - 2012-07-13 - TarsisToledo