ABSTRACT
The advent of variability management and generator technology enables users to derive individual variants from a variable code base based on a selection of desired configuration options. This approach gives rise to the generation of possibly billions of variants that, however, cannot be efficiently analyzed for errors with classic analysis techniques. To address this issue, researchers and practitioners usually apply sampling heuristics. While sampling reduces the analysis effort significantly, the information obtained is necessarily incomplete and it is unknown whether sampling heuristics scale to billions of variants. Recently, researchers have begun to develop variability-aware analyses that analyze the variable code base directly exploiting the similarities among individual variants to reduce analysis effort. However, while being promising, so far, variability-aware analyses have been applied mostly only to small academic systems. To learn about the mutual strengths and weaknesses of variability-aware and sampling-based analyses of software systems, we compared the two strategies by means of two concrete analysis implementations (type checking and liveness analysis), applied them to three subject systems: Busybox, the x86 Linux kernel, and OpenSSL. Our key finding is that variability-aware analysis outperforms most sampling heuristics with respect to analysis time while preserving completeness.
- S. Apel and C. Kästner. An Overview of Feature-Oriented Software Development. J. Object Technology, 8(5):49–84, 2009.Google Scholar
- S. Apel, C. Kästner, A. Größlinger, and C. Lengauer. Type Safety for Feature-Oriented Product Lines. Automated Software Engineering, 17(3):251–300, 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 Proc. Int. Conf. Automated Software Engineering (ASE), pages 372–375. IEEE, 2011. Google ScholarDigital Library
- S. Apel, A. von Rhein, P. Wendler, A. Größlinger, and D. Beyer. Strategies for Product-Line Verification: Case Studies and Experiments. In Proc. Int. Conf. Software Engineering (ICSE), pages 482–491. IEEE, 2013. Google ScholarDigital Library
- L. Aversano, L. Di Penta, and I. Baxter. Handling Preprocessor-Conditioned Declarations. In Proc. Working Conf. Source Code Management and Manipulation (SCAM), pages 83–92. IEEE, 2002. Google ScholarDigital Library
- T. Berger, S. She, K. Czarnecki, and A. Wasowski. Feature-to-Code Mapping in Two Large Product Lines. In Proc. Int. Software Product Line Conference (SPLC), pages 498–499. Springer, 2010. Google ScholarDigital Library
- T. Berger, S. She, R. Lotufo, A. Wasowski, and K. Czarnecki. Variability Modelling in the Real: A Perspective from the Operating Systems Domain. In Proc. Int. Conf. Automated Software Engineering (ASE), pages 73–82. ACM, 2010. Google ScholarDigital Library
- E. Bodden, M. Mezini, C. Brabrand, T. Tolˆedo, M. Ribeiro, and P. Borba. SPL LIFT — Statically Analyzing Software Product Lines in Minutes Instead of Years. In Proc. Int. Conf. Programming Language Design and Implementation (PLDI), pages 355–364. ACM, 2013. Google ScholarDigital Library
- C. Brabrand, M. Ribeiro, T. Tolˆedo, and P. Borba. Intraprocedural Dataflow Analysis for Software Product Lines. In Proc. Int. Conf. Aspect-Oriented Software Development (AOSD), pages 13–24. ACM, 2012. Google ScholarDigital Library
- M. Calder and A. Miller. Feature Interaction Detection by Pairwise Analysis of LTL Properties: A Case Study. Formal Methods in System Design, 28(3):213–261, 2006. Google ScholarDigital Library
- S. Chen, M. Erwig, and E. Walkingshaw. An Error-Tolerant Type System for Variational Lambda Calculus. In Proc. Int. Conf. Functional Programming (ICFP), pages 29–40. ACM, 2012. Google ScholarDigital Library
- E. Clarke, O. Grumberg, S. Jha, Y. Lu, and H. Veith. Counterexample-guided Abstraction Refinement for Symbolic Model Checking. Journal of the ACM, 50(5):752–794, 2003. Google ScholarDigital Library
- E. Clarke, O. Grumberg, and D. Peled. Model Checking. The MIT Press, 1999. 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. Int. Conf. Software Engineering (ICSE), pages 335–344. ACM, 2010. Google ScholarDigital Library
- K. Czarnecki and U. Eisenecker. Generative Programming: Methods, Tools, and Applications. Addison-Wesley, 2000. Google ScholarDigital Library
- B. Delaware, W. Cook, and D. Batory. Fitting the Pieces Together: A Machine-Checked Model of Safe Composition. In Proc. Int. Symp. Foundations of Software Engineering (FSE), pages 243–252. ACM, 2009. Google ScholarDigital Library
- C. Dietrich, R. Tartler, W. Schröder-Preikshat, and D. Lohmann. Understanding Linux Feature Distribution. In Proc. AOSD Workshop Modularity in Systems Software (MISS), pages 15–20. ACM, 2012. Google ScholarDigital Library
- M. Erwig and E. Walkingshaw. The Choice Calculus: A Representation for Software Variation. ACM Trans. Software Engineering and Methodology, 21(1):6:1–6:27, 2011. Google ScholarDigital Library
- B. Garvin and M. Cohen. Feature Interaction Faults Revisited: An Exploratory Study. In Proc. Int. Symp. Software Reliability Engineering (ISSRE), pages 90–99. IEEE, 2011. Google ScholarDigital Library
- Y. Hu, E. Merlo, M. Dagenais, and B. Lagüe. C/C++ Conditional Compilation Analysis using Symbolic Execution. In Proc. Int. Conf. Software Maintenance (ICSM), pages 196–206. IEEE, 2000. Google ScholarDigital Library
- M. Johansen, Ø. Haugen, and F. Fleurey. Properties of Realistic Feature Models Make Combinatorial Testing of Product Lines Feasible. In Proc. Int. Conf. Model Driven Engineering Languages and Systems (MODELS), pages 638–652. Springer, 2011. Google ScholarDigital Library
- M. Johansen, O. Haugen, and F. Fleurey. An Algorithm for Generating t-Wise Covering Arrays from Large Feature Models. In Proc. Int. Software Product Line Conference (SPLC), pages 46–55. ACM, 2012. Google ScholarDigital Library
- C. Kästner, S. Apel, and M. Kuhlemann. Granularity in Software Product Lines. In Proc. Int. Conf. Software Engineering (ICSE), pages 311–320. ACM, 2008. Google ScholarDigital Library
- C. Kästner, S. Apel, T. Thüm, and G. Saake. Type Checking Annotation-Based Product Lines. ACM Trans. Software Engineering and Methodology, 21(3):1–39, 2012. Google ScholarDigital Library
- C. Kästner, P. Giarrusso, T. Rendel, S. Erdweg, K. Ostermann, and T. Berger. Variability-Aware Parsing in the Presence of Lexical Macros and Conditional Compilation. In Proc. Conf. Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), pages 805–824. ACM, 2011. Google ScholarDigital Library
- C. Kästner, K. Ostermann, and S. Erdweg. A Variability-Aware Module System. In Proc. Conf. Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), pages 773–792. ACM, 2012. Google ScholarDigital Library
- C. Kästner, A. von Rhein, S. Erdweg, J. Pusch, S. Apel, T. Rendel, and K. Ostermann. Toward Variability-Aware Testing. In Proc. Int. Workshop Feature-Oriented Software Development (FOSD), pages 1–8. ACM, 2012. Google ScholarDigital Library
- D. Kuhn, D. Wallace, and A. Gallo. Software Fault Interactions and Implications for Software Testing. IEEE Trans. Software Engineering, 30(6):418–421, 2004. Google ScholarDigital Library
- M. Latendresse. Fast Symbolic Evaluation of C/C++ Preprocessing using Conditional Values. In Proc. European Conf. Software Maintenance and Reengineering (CSMR), pages 170–179. IEEE, 2003. Google ScholarDigital Library
- K. Lauenroth, S. Toehning, and K. Pohl. Model Checking of Domain Artifacts in Product Line Engineering. In Proc. Int. Conf. Automated Software Engineering (ASE), pages 269–280. IEEE, 2009. Google ScholarDigital Library
- J. Liebig, S. Apel, C. Lengauer, C. Kästner, and M. Schulze. An Analysis of the Variability in Forty Preprocessor-Based Software Product Lines. In Proc. Int. Conf. Software Engineering (ICSE), pages 105–114. ACM, 2010. 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. Int. Conf. Aspect-Oriented Software Development (AOSD), pages 191–202. ACM, 2011. Google ScholarDigital Library
- M. Lochau, S. Oster, U. Goltz, and A. Schürr. Model-based Pairwise Testing for Feature Interaction Coverage in Software Product Line Engineering. Software Quality Journal, 20(3-4):567–604, 2012. Google ScholarDigital Library
- M. Mendon¸ca, A. Wasowski, and K. Czarnecki. SAT-based Analysis of Feature Models is Easy. In Proc. Int. Software Product Line Conference (SPLC), pages 231–240. ACM, 2009. Google ScholarDigital Library
- C. Nie and H. Leung. A Survey of Combinatorial Testing. ACM Comput. Surv., 43(2):1–29, 2011. Google ScholarDigital Library
- S. Oster, F. Markert, and P. Ritter. Automated Incremental Pairwise Testing of Software Product Lines. In Proc. Int. Software Product Line Conference (SPLC), pages 196–2010. Springer, 2010. Google ScholarDigital Library
- G. Perrouin, S. Oster, S. Sen, J. Klein, B. Baudry, and Y. Traon. Pairwise Testing for Software Product Lines: Comparison of Two Approaches. Software Quality Journal, 20(3-4):605–643, 2012. Google ScholarDigital Library
- N. Siegmund, S. Kolesnikov, C. Kästner, S. Apel, D. Batory, M. Rosenmüller, and G. Saake. Predicting Performance via Automated Feature-Interaction Detection. In Proc. Int. Conf. Software Engineering (ICSE), pages 167–177. IEEE, 2012. Google ScholarDigital Library
- J. Sincero, H. Schirmeier, W. Schröder-Preikschat, and O. Spinczyk. Is the Linux Kernel a Software Product Line? In Proc. Int. Workshop Opens Source Software and Product Lines (OSSPL), 2007.Google Scholar
- R. Tartler, D. Lohmann, C. Dietrich, C. Egger, and J. Sincero. Feature Consistency in Compile-Time Configurable System Software. In Proc. EuroSys Conf., pages 47–60. ACM, 2011. Google ScholarDigital Library
- R. Tartler, D. Lohmann, C. Dietrich, C. Egger, and J. Sincero. Configuration Coverage in the Analysis of Large-scale System Software. SIGOPS Oper. Syst. Rev., 45(3):10–14, 2012. Google ScholarDigital Library
- S. Thaker, D. Batory, D. Kitchin, and W. Cook. Safe Composition of Product Lines. In Proc. Int. Conf. Generative Programming and Component Engineering (GPCE), pages 95–104. ACM, 2007. Google ScholarDigital Library
- T. Thüm, S. Apel, C. Kästner, M. Kuhlemann, I. Schaefer, and G. Saake. Analysis Strategies for Software Product Lines. Technical Report FIN-004-2012, University of Magdeburg, 2012.Google Scholar
- T. Thüm, I. Schaefer, S. Apel, and M. Hentschel. Family-Based Theorem Proving for Deductive Verification of Software Product Lines. In Proc. Int. Conf. Generative Programming and Component Engineering (GPCE), pages 11–20. ACM, 2012. Google ScholarDigital Library
- M. Tomita. LR Parsers for Natural Languages. In Proc. Int. Conf. Computational Linguistics (ACL), pages 354–357. ACL, 1984. Google ScholarDigital Library
- A. von Rhein, S. Apel, and F. Raimondi. Introducing Binary Decision Diagrams in the Explicit-State Verification of Java Code. In Java Pathfinder Workshop, 2011. co-located with ASE’11.Google Scholar
- H. Zhu, P. Hall, and J. May. Software Unit Test Coverage and Adequacy. ACM Comput. Surv., 29(4):366–427, 1997. Google ScholarDigital Library
Index Terms
- Scalable analysis of variable software
Recommendations
Variability-Aware Static Analysis at Scale: An Empirical Study
The advent of variability management and generator technology enables users to derive individual system variants from a configurable code base by selecting desired configuration options. This approach gives rise to the generation of possibly billions of ...
A Classification and Survey of Analysis Strategies for Software Product Lines
Software-product-line engineering has gained considerable momentum in recent years, both in industry and in academia. A software product line is a family of software products that share a common set of features. Software product lines challenge ...
Towards Efficient Analysis of Variation in Time and Space
SPLC '19: Proceedings of the 23rd International Systems and Software Product Line Conference - Volume BVariation is central to today's software development. There are two fundamental dimensions to variation: Variation in time refers to the fact that software exists in numerous revisions that typically replace each other (i.e., a newer version supersedes ...
Comments