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 inter-procedural, 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 Heros, 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.
- S. Guarnieri, M. Pistoia, O. Tripp, J. Dolby, S. Teilhet, and R. Berg, "Saving the world wide web from vulnerable JavaScript," in Proc. 2011 int. symp. on Software Testing and Analysis, ser. ISSTA'11, 2011, pp. 177--187. Google ScholarDigital Library
- S. J. Fink, E. Yahav, N. Dor, G. Ramalingam, and E. Geay, "Effective typestate verification in the presence of aliasing," ACM Trans. Softw. Eng. Methodol., vol. 17, no. 2, pp. 9:1--9:34, May 2008. Google ScholarDigital Library
- N. A. Naeem and O. Lhotak, "Typestate-like analysis of multiple interacting objects," in OOPSLA, 2008, pp. 347--366. Google ScholarDigital Library
- V. Sundaresan, L. Hendren, C. Razafimahefa, R. Vallée-Rai, P. Lam, E. Gagnon, and C. Godin, "Practical virtual method call resolution for Java," in OOPSLA, 2000, pp. 264--280. Google ScholarDigital Library
- T. Reps, S. Horwitz, and M. Sagiv, "Precise interprocedural dataflow analysis via graph reachability," in Proc. 22nd ACM SIGPLAN-SIGACT symp. on Principles of programming languages, ser. POPL'95, 1995, pp. 49--61. Google ScholarDigital Library
- E. Bodden, "Efficient hybrid typestate analysis by determining continuation-equivalent states,"in ICSE 2010, May 2010, pp. 5--14. Google ScholarDigital Library
- N. A. Naeem and O. Lhoták, "Efficient alias set analysis using SSA form," in Proc. 2009 int. symp. on Memory Management, ser. ISMM ’09, 2009, pp. 79--88. Google ScholarDigital Library
- S. Shoham, E. Yahav, S. Fink, and M. Pistoia, "Static specification mining using automata-based abstractions," IEEE TSE, vol. 34, no. 5, pp. 651--666, 2008. Google ScholarDigital Library
- N. Rinetzky, M. Sagiv, and E. Yahav, "Interprocedural shape analysis for cutpoint-free programs," in Static Analysis, ser. Lecture Notes in Computer Science, C. Hankin and I. Siveroni, Eds. Springer Berlin / Heidelberg, 2005, vol. 3672, pp. 284--302. Google ScholarDigital Library
- H. Yang, O. Lee, J. Berdine, C. Calcagno, B. Cook, D. Distefano, and P. O'Hearn, "Scalable shape analysis for systems code," in CAV, 2008, pp. 385--398. Google ScholarDigital Library
- M. Sagiv, T. Reps, and S. Horwitz, "Precise interprocedural dataflow analysis with applications to constant propagation," in TAPSOFT'95, 1996, pp. 131--170. Google ScholarDigital Library
- C. Kästner and S. Apel, "Virtual separation of concerns - a second chance for preprocessors," Journal of Object Technology, vol. 8, no. 6, pp. 59--78, 2009.Google ScholarCross Ref
- C. Kästner, S. Apel, and M. Kuhlemann, "Granularity in Software Product Lines," in Proc. 30th int. conf. on Software Engineering (ICSE'08), 2008, pp. 311--320. Google ScholarDigital Library
- E. Bodden, "Inter-procedural data-flow analysis with ifds/ide and soot," in SOAP 2012, Jul. 2012, pp. 3--8, heros website: http://sable.github.com/heros/. Google ScholarDigital Library
- R. Vallée-Rai, L. Hendren, V. Sundaresan, P. Lam, E. Gagnon, and P. Co, "Soot - a Java optimization framework," in Proceedings of CASCON 1999, 1999, pp. 125--135. {Online}. Available: www.sable.mcgill.ca/publications\BIBentrySTDinterwordspacingGoogle Scholar
- C. Kästner, "Virtual separation of concerns," Ph.D. dissertation, Universit\"at Magdeburg, 2010.Google Scholar
- "The Eclipse IDE," http://eclipse.org/.Google Scholar
- E. Bodden, "Position Paper: Static flow-sensitive & context-sensitive information-flow analysis for software product lines'" in PLAS 2012, Jun. 2012, pp. 6:1--6:6. Google ScholarDigital Library
- D. Batory, "Feature models, grammars, and propositional formulas,"; in Software Product Lines (SPLC) 2005, ser. LNCS, vol. 3714, 2005, pp. 7--20. Google ScholarDigital Library
- J. Liebig, C. Kästner, and S. Apel, "Analyzing the discipline of preprocessor annotations in 30 million lines of c code,"; in Proc. 10th int. conf. on Aspect-oriented software development, ser. AOSD '11, 2011, pp. 191--202. Google ScholarDigital Library
- R. Drechsler and B. Becker, phBinary decision diagrams: theory and implementation Springer, 1998.Google Scholar
- C. Kästner, P. G. Giarrusso, T. Rendel, S. Erdweg, K. Ostermann, and T. Berger, "Variability-aware parsing in the presence of lexical macros and conditional compilation," in Proc. 2011 ACM int. conf. on Object oriented programming systems languages and applications, ser. OOPSLA"11, 2011, pp. 805--824. Google ScholarDigital Library
- E. Bodden, A. Sewe, J. Sinschek, H. Oueslati, and M. Mezini, "Taming reflection: Aiding static analysis in the presence of reflection and custom class loaders," in ICSE 2011, May 2011, pp. 241--250. Google ScholarDigital Library
- T. Reps, S. Schwoon, and S. Jha, "Weighted pushdown systems and their application to interprocedural dataflow analysis," in Static Analysis, ser. Lecture Notes in Computer Science, R. Cousot, Ed. Springer Berlin / Heidelberg, 2003, vol. 2694, pp. 1075--1075. Google ScholarDigital Library
- C. Brabrand, M. Ribeiro, T. Tolêdo, and P. Borba, "Intraprocedural dataflow analysis for software product lines," in phProc. 11th annual int. conf. on Aspect-oriented Software Development, ser. AOSD'12, 2012, pp. 13--24. Google ScholarDigital Library
- S. Apel, C. Kästner, A. Grösslinger, and C. Lengauer, "Type safety for feature-oriented product lines," Automated Software Eng., vol. 17, no. 3, pp. 251--300, Sep. 2010. Google ScholarDigital Library
- "Typechef analysis engine," http://ckaestne.github.com/TypeChef/.Google Scholar
- T. Thüm, S. Apel, C. Kästner, M. Kuhlemann, I. Schaefer, and G. Saake, "Analysis strategies for software product lines'" School of Computer Science, University of Magdeburg, Tech. Rep. FIN-004--2012, Apr. 2012.Google Scholar
- C. Kästner and S. Apel, "Type-checking software product lines - a formal approach," in Proc. 2008 23rd IEEE/ACM int. conf. on Automated Software Engineering, ser. ASE'08, 2008, pp. 258--267. Google ScholarDigital Library
- A. Classen, P. Heymans, P.-Y. Schobbens, A. Legay, and J.-F. Raskin, "Model checking lots of systems: efficient verification of temporal properties in software product lines," in Proc. 32nd ACM/IEEE int. conf. on Software Engineering - Volume 1, ser. ICSE'10, 2010, pp. 335--344. Google ScholarDigital Library
- A. Classen, P. Heymans, P.-Y. Schobbens, and A. Legay, "Symbolic model checking of software product lines," in Proc. 33rd int. conf. on Software Engineering, ser. ICSE'11, 2011, pp. 321--330. Google ScholarDigital Library
- H. Post and C. Sinz, "Configuration lifting: Verification meets software configuration," in Proc. 2008 23rd IEEE/ACM int. conf. on Automated Software Engineering, ser. ASE'08, 2008, pp. 347--350. Google ScholarDigital Library
- C. H. P. Kim, E. Bodden, D. Batory, and S. Khurshid, "Reducing configurations to monitor in a software product line," in Proc. First int. conf. on Runtime verification, ser. RV'10, 2010, pp. 285--299. Google ScholarDigital Library
- S. Apel, H. Speidel, P. Wendler, A. von Rhein, and D. Beyer, "Detection of feature interactions using feature-aware verification," in Proc. 2011 26th IEEE/ACM int. conf. on Automated Software Engineering, ser. ASE'11, 2011, pp. 372--375. Google ScholarDigital Library
- C. Hwan, P. Kim, D. Batory, and S. Khurshid, "Reducing combinatorics in testing product lines," in Proc. 10th int. conf. on Aspect-oriented Software Development (AOSD'11), 2011, pp. 57--68. Google ScholarDigital Library
- J. Shi, M. Cohen, and M. Dwyer, "Integration testing of software product lines using compositional symbolic execution," in Fundamental Approaches to Software Engineering, ser. Lecture Notes in Computer Science, J. de Lara and A. Zisman, Eds. Springer Berlin / Heidelberg, 2012, vol. 7212, pp. 270--284. Google ScholarDigital Library
- V. Stricker, A. Metzger, and K. Pohl, "Avoiding redundant testing in application engineering," in Software Product Lines: Going Beyond, ser. Lecture Notes in Computer Science, J. Bosch and J. Lee, Eds. Springer Berlin / Heidelberg, 2010, vol. 6287, pp. 226--240. Google ScholarDigital Library
- T. Ball and S. K. Rajamani, "Bebop: a path-sensitive interprocedural dataflow engine," in Proc. 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, ser. PASTE'01, 2001, pp. 97--103. Google ScholarDigital Library
- G. Ammons and J. R. Larus, "Improving data-flow analysis with path profiles," SIGPLAN Not., vol. 39, no. 4, pp. 568--582, Apr. 2004. Google ScholarDigital Library
- M. N. Wegman and F. K. Zadeck, "Constant propagation with conditional branches," ACM Trans. Program. Lang. Syst., vol. 13, no. 2, pp. 181--210, Apr. 1991. Google ScholarDigital Library
- S. Moon, M. W. Hall, and B. R. Murphy, "Predicated array data-flow analysis for run-time parallelization," in Proc. 12th int. conf. on Supercomputing, ser. ICS'98, 1998, pp. 204--211. Google ScholarDigital Library
- M. Ribeiro, H. Pacheco, L. Teixeira, and P. Borba, "Emergent feature modularization," in Proc. ACM int. conf. companion on Object oriented programming systems languages and applications companion, ser. SPLASH'10, 2010, pp. 11--18. Google ScholarDigital Library
Index Terms
- SPLLIFT: statically analyzing software product lines in minutes instead of years
Recommendations
SPLLIFT: statically analyzing software product lines in minutes instead of years
PLDI '13A 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 ...
Reviser: efficiently updating IDE-/IFDS-based data-flow analyses in response to incremental program changes
ICSE 2014: Proceedings of the 36th International Conference on Software EngineeringMost application code evolves incrementally, and especially so when being maintained after the applications have been deployed. Yet, most data-flow analyses do not take advantage of this fact. Instead they require clients to recompute the entire ...
Static data-flow analysis for software product lines in C: Revoking the preprocessor’s special role
AbstractMany critical codebases are written in C, and most of them use preprocessor directives to encode variability, effectively encoding software product lines. These preprocessor directives, however, challenge any static code analysis. SPLlift, a ...
Comments