An Interpreter-based Framework for Static Analysis of Variability in Space and Time
Resumo
Software Product Lines (SPLs) enable the systematic development of configurable software systems by organizing products as families that share commonalities and differ in selected features. However, static analysis in SPLs poses scalability challenges due to variability in space (across configurations) and variability in time (across software revisions). This paper presents an interpreter-based framework that combines variational lifting and memoization to support scalable and reusable static analysis of evolving SPLs. Analyses are implemented as PCF+ programs and executed over variational representations of object programs, annotated with presence conditions. Memoization mechanisms allow the reuse of previously computed results across object program evolutions, reducing redundant computations and contributing to performance improvements. The framework is evaluated using benchmarks simulating software evolution scenarios. Results indicate that the combined use of variational lifting and memoization effectively reduces execution time, suggesting the advantages of addressing both dimensions of variability. This work contributes a reusable infrastructure for control-flow-based analyses in SPLs and provides empirical evidence supporting its efficiency.
Referências
Eric Bodden, Társis Tolêdo, Márcio Ribeiro, Claus Brabrand, Paulo Borba, and Mira Mezini. 2013. SPLLIFT: statically analyzing software product lines in minutes instead of years. SIGPLAN Not. 48, 6 (June 2013), 355–364. DOI: 10.1145/2499370.2491976
Randal Bryant. 1986. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Trans. Comput. C-35, 8 (1986), 677–691. DOI: 10.1109/TC.1986.1676819
Aleksandar S. Dimovski, Claus Brabrand, and AndrzejWąsowski. 2015. Variability Abstractions: Trading Precision for Speed in Family-Based Analyses (Extended Version). arXiv:1503.04608 [cs.PL] [link]
Christian Kröher, Lea Gerling, and Klaus Schmid. 2023. Comparing the intensity of variability changes in software product line evolution. Journal of Systems and Software 203 (2023), 111737. DOI: 10.1016/j.jss.2023.111737
André Lanna, Thiago M. Castro, Vander Alves, Genaína Nunes Rodrigues, Pierre-Yves Schobbens, and Sven Apel. 2018. Feature-family-based reliability analysis of software product lines. Inf. Softw. Technol. 94 (2018), 59–81. DOI: 10.1016/J.INFSOF.2017.10.001
Donald Michie. 1968. “Memo” Functions and Machine Learning. Nature 218, 5136 (1968), 19–22. DOI: 10.1038/218019a0
Anders Møller and Michael I. Schwartzbach. 2018. Static Program Analysis. Department of Computer Science, Aarhus University, [link].
Flemming Nielson, Hanne R. Nielson, and Chris Hankin. 2010. Principles of Program Analysis. Springer Publishing Company, Incorporated.
G.D. Plotkin. 1977. LCF considered as a programming language. Theoretical Computer Science 5, 3 (1977), 223–255. DOI: 10.1016/0304-3975(77)90044-5
Ramy Shahin and Marsha Chechik. 2020. Automatic and efficient variabilityaware lifting of functional programs. Proceedings of the ACM on Programming Languages 4, OOPSLA (Nov. 2020), 1–27. DOI: 10.1145/3428225
SPLC. 2024. Software Product Line Conference - Hall of Fame. [link]. Accessed: 2024-10-02.
Thomas Thüm, Sven Apel, Christian Kästner, Martin Kuhlemann, Ina Schaefer, and Gunter Saake. 2012. Analysis Strategies for Software Product Lines. Technical Report FIN-004-2012. School of Computer Science, University of Magdeburg, Germany.
Thomas Thüm, Sven Apel, Christian Kästner, Ina Schaefer, and Gunter Saake. 2014. A Classification and Survey of Analysis Strategies for Software Product Lines. Comput. Surveys 47, 1 (July 2014), 1–45. DOI: 10.1145/2580950
Thomas Thüm, Leopoldo Teixeira, Klaus Schmid, Eric Walkingshaw, Mukelabai Mukelabai, Mahsa Varshosaz, Goetz Botterweck, Ina Schaefer, and Timo Kehrer. 2019. Towards Efficient Analysis of Variation in Time and Space. In Proceedings of the 23rd International Systems and Software Product Line Conference - Volume B. ACM, Paris France, 57–64. DOI: 10.1145/3307630.3342414
Eric Walkingshaw, Christian Kästner, Martin Erwig, Sven Apel, and Eric Bodden. 2014. Variational Data Structures: Exploring Tradeoffs in Computing with Variability. In Proceedings of the 2014 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software. ACM, Portland Oregon USA, 213–226. DOI: 10.1145/2661136.2661143
Simon Wimmer, Shuwei Hu, and Tobias Nipkow. 2018. Verified Memoization and Dynamic Programming. In Interactive Theorem Proving, Jeremy Avigad and Assia Mahboubi (Eds.). Vol. 10895. Springer International Publishing, Cham, 579–596. DOI: 10.1007/978-3-319-94821-8_34 Series Title: Lecture Notes in Computer Science.
