Claus Brabrand
Paulo Borba
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 must generate and analyze all valid methods 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'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 are on average 5.6 times faster than the brute force approach on our SPLs, and that they have different time and space tradeoffs.
- B. Adams, W. De Meuter, H. Tromp, and A. E. Hassan. Can we refactor conditional compilation into aspects? In Proceedings of the 8th ACM international conference on Aspect-oriented software development (AOSD'09), pages 243--254, Charlottesville, Virginia, USA, 2009. ACM. Google Scholar
Digital Library
- G. Ammons and J. R. Larus. Improving data-flow analysis with path profiles. In Programming Language Design and Implementation (PLDI'98), pages 72--84, Montreal, Canada, 1998. Google ScholarDigital Library
- S. Apel, C. Kastner, A. Grösslinger, and C. Lengauer. Type safety for feature-oriented product lines. Automated Software Engineering, 17: 251--300, September 2010. Google ScholarDigital Library
- S. Apel, H. Speidel, P. Wendler, A. von Rhein, and D. Beyer. Detection of feature interactions using feature-aware verification. In Proceedings of the 26th IEEE/ACM International Conference on Automated Software Engineering (ASE'11), Lawrence, USA, November 2011. IEEE Computer Society. Google ScholarDigital Library
- T. Ball and S. K. Rajamani. Bebop: a path-sensitive interprocedural dataflow engine. In PASTE'01, pages 97--103, Snowbird, Utah, USA. 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 Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering (ICSE '10), pages 335--344, Cape Town, South Africa, 2010. ACM. Google ScholarDigital Library
- P. Clements and L. Northrop. Software Product Lines: Practices and Patterns. Addison-Wesley, 2001. Google ScholarDigital Library
- M. D. Ernst, G. J. Badros, and D. Notkin. An empirical analysis of c preprocessor use. IEEE Transactions on Software Engineering, 28: 1146--1170, December 2002. Google ScholarDigital Library
- E. Figueiredo, N. Cacho, C. Sant'Anna, M. Monteiro, U. Kulesza, A. Garcia, S. Soares, F. Ferrari, S. Khan, F. C. Filho, and F. Dantas. Evolving software product lines with aspects: an empirical study on design stability. In Proceedings of the 30th International Conference on Software Engineering (ICSE'08), pages 261--270, Leipzig, Germany, 2008. ACM. Google ScholarDigital Library
- M. Fowler. Refactoring: Improving the Design of Existing Code. Addison-Wesley, 1999. Google ScholarDigital Library
- C. Hwan, P. Kim, D. Batory, and S. Khurshid. Reducing combinatorics in testing product lines. In Proceedings of the 10th International Conference on Aspect-oriented Software Development (AOSD'11), pages 57--68, Porto de Galinhas, Brazil, 2011. ACM. Google ScholarDigital Library
- N. D. Jones, C. K. Gomard, and P. Sestoft. Partial evaluation and automatic program generation. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1993. Google ScholarDigital Library
- K. C. Kang, S. G. Cohen, J. A. Hess, W. E. Novak, and A. S. Peterson. Feature-Oriented Domain Analysis (FODA) feasibility study. Technical report, Carnegie-Mellon University Software Engineering Institute, November 1990.Google ScholarCross Ref
- ner(2010)}kastnerthesisC. Kastner. Virtual Separation of Concerns: Toward Preprocessors 2.0. PhD thesis, University of Magdeburg, Germany, May 2010.Google Scholar
- C. Kastner and S. Apel. Type-checking software product lines - a formal approach. In Proceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering (ASE'08), pages 258--267, L'Aquila, Italy, 2008. Google ScholarDigital Library
- C. Kastner, S. Apel, and M. Kuhlemann. Granularity in software product lines. In Proceedings of the 30th International Conference on Software Engineering (ICSE'08), pages 311--320, Leipzig, Germany, 2008. ACM. Google ScholarDigital Library
- C. Kastner, 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 Proceedings of the ACM International Conference on Object-Oriented Programming Systems Languages and Applications (OOPSLA'11), pages 805--824, Portland, OR, USA, 2011. ACM. Google ScholarDigital Library
- G. A. Kildall. A unified approach to global program optimization. In Proceedings of the 1st annual ACM symposium on Principles of programming languages (POPL'73), pages 194--206, Boston, Massachusetts, 1973. ACM. Google ScholarDigital Library
- C. H. P. Kim, E. Bodden, D. Batory, and S. Khurshid. Reducing configurations to monitor in a software product line. In ph1st International Conference on Runtime Verification (RV), volume 6418 of LNCS, Malta, November 2010. Springer. Google ScholarDigital Library
- M. Krone and G. Snelting. On the inference of configuration structures from source code. In Proceedings of the 16th International Conference on Software Engineering (ICSE'04), pages 49--57, Los Alamitos, CA, USA, 1994. IEEE Computer. Google ScholarDigital Library
- J. Liebig, S. Apel, C. Lengauer, C. Kastner, and M. Schulze. An analysis of the variability in forty preprocessor-based software product lines. In Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering (ICSE'10), pages 105--114, Cape Town, South Africa, 2010. ACM. Google ScholarDigital Library
- S. Moon, M. W. Hall, and B. R. Murphy. Predicated array data-flow analysis for run-time parallelization. In Proceedings of the 12th International Conference on Supercomputing (ICS'98), pages 204--211, Melbourne, Australia, 1998. ACM. Google ScholarDigital Library
- F. Nielson, H. R. Nielson, and C. Hankin. Principles of Program Analysis. Springer-Verlag, Secaucus, USA, 1999. Google ScholarDigital Library
- K. Pohl, G. Böckle, and F. van der Linden. Software Product Line Engineering: Foundations, Principles and Techniques. Springer, 2005. Google ScholarCross Ref
- H. Post and C. Sinz. Configuration lifting: Verification meets software configuration. In phProceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering (ASE'08), pages 347--350, L'Aquila, Italy, 2008. IEEE Computer Society. Google ScholarDigital Library
- M. Ribeiro, H. Pacheco, L. Teixeira, and P. Borba. Emergent feature modularization. In Onward! 2010, affiliated with the 1st ACM SIGPLAN International Conference on Systems, Programming, Languages and Applications: Software for Humanity (SPLASH'10), pages 11--18, Reno, NV, USA, 2010. Google ScholarDigital Library
- H. Spencer and G. Collyer. #ifdef considered harmful, or portability experience with C news. In Proceedings of the Usenix Summer 1992 Technical Conference, pages 185--198, Berkeley, CA, USA, June 1992. Usenix Association.Google Scholar
- R. Vallée-Rai, P. Co, E. Gagnon, L. Hendren, P. Lam, and V. Sundaresan. Soot - a java bytecode optimization framework. In Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research (CASCON'99), pages 13--. IBM Press, 1999. Google ScholarDigital Library
- M. N. Wegman and F. K. Zadeck. Constant propagation with conditional branches. ACM Transactions on Programming Languages and Systems, 13: 181--210, April 1991. Google ScholarDigital Library
Index Terms
- Intraprocedural dataflow analysis for software product lines
Recommendations
Intraprocedural dataflow analysis for software product lines
Transactions on Aspect-Oriented Software Development XSoftware 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 ...
Static flow-sensitive & context-sensitive information-flow analysis for software product lines: position paper
PLAS '12: Proceedings of the 7th Workshop on Programming Languages and Analysis for SecurityA software product line encodes a potentially large variety of software products as variants of some common code base, e.g., through the use of #ifdef statements or other forms of conditional compilation. Traditional information-flow analyses cannot ...
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 ...
Reviews
Simon John Thompson
Computer systems of any size are unlikely to be simple programs. Extracted from some sort of source code control, they will be configured and targeted for deployment using preprocessors, configuration, and make tools. These aspects are often neglected—for example, does your favorite refactoring tool ensure that tests and makefiles are refactored in step with the code__?__ One approach to taming this complexity is to use software product lines (SPLs), which the authors of this paper describe by means of sets of features (or configurations) that (de)activate certain program artifacts. They ask the following question: Given an SPL description, how does one analyze that description, for example, in a dataflow analysis__?__ The naive approach is to analyze all the instances of the SPL, but in this paper, the authors show that a more thoughtful approach pays performance dividends, at least in the case of a number of intraprocedural analyses. The first step of the new approach is to build an analysis that is feature sensitive so that each analysis can be performed for the features enabled by the configuration of the particular instance of the SPL, rather than making the analysis on the compiled version of the configuration. The second innovation is to perform an analysis of all the configurations simultaneously, by means of a product lattice. This has the distinct advantage of performing the fixed-point calculation once and for all, rather than repeating it for each configuration. The final innovation is to share computations in the simultaneous calculation of the analysis. The paper gives a theoretical analysis of the speedups and presents data gathered in a number of real-world case studies. The simultaneous analysis performs particularly well in the case where the SPL is feature rich, producing a substantial speedup. Sharing computations can reduce the memory footprint of the analysis as well. It will be interesting to see how the results of this well-written paper scale to larger systems and to interprocedural analyses in particular. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments