research-article

Public Access

On essential configuration complexity: measuring interactions in highly-configurable systems

Authors:

Christian Kästner,

Gunter SaakeAuthors Info & Claims

ASE '16: Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering

Pages 483 - 494

https://doi.org/10.1145/2970276.2970322

Published: 25 August 2016 Publication History

Abstract

Quality assurance for highly-configurable systems is challenging due to the exponentially growing configuration space. Interactions among multiple options can lead to surprising behaviors, bugs, and security vulnerabilities. Analyzing all configurations systematically might be possible though if most options do not interact or interactions follow specific patterns that can be exploited by analysis tools. To better understand interactions in practice, we analyze program traces to characterize and identify where interactions occur on control flow and data. To this end, we developed a dynamic analysis for Java based on variability-aware execution and monitor executions of multiple small to medium-sized programs. We find that the essential configuration complexity of these programs is indeed much lower than the combinatorial explosion of the configuration space indicates. However, we also discover that the interaction characteristics that allow scalable and complete analyses are more nuanced than what is exploited by existing state-of-the-art quality assurance strategies.

References

[1]

I. Abal, C. Brabrand, and A. Wasowski. 42 Variability Bugs in the Linux Kernel: A Qualitative Analysis. In ASE, pages 421–432. ACM, 2014.

Digital Library

[2]

S. Anand, C. S. Păsăreanu, and W. Visser. JPF-SE: A Symbolic Execution Extension to Java Pathfinder. In TACAS, pages 134–138. Springer, 2007.

Digital Library

[3]

F. Angerer, A. Grimmer, H. Prähofer, and P. Grünbacher. Configuration-Aware Change Impact Analysis. In ASE, pages 385–395. IEEE, 2015.

[4]

S. Apel, D. Beyer, K. Friedberger, F. Raimondi, and A. von Rhein. Domain Types: Abstract-Domain Selection Based on Variable Usage. In HVC, pages 262–278. Springer, 2013.

[5]

S. Apel, A. von Rhein, P. Wendler, A. Größlinger, and D. Beyer. Strategies for Product-Line Verification: Case Studies and Experiments. In ICSE, pages 482–491. IEEE, 2013.

Digital Library

[6]

T. H. Austin and C. Flanagan. Multiple Facets for Dynamic Information Flow. In POPL, pages 165–178. ACM, 2012.

Digital Library

[7]

T. H. Austin, J. Yang, C. Flanagan, and A. Solar-Lezama. Faceted Execution of Policy-Agnostic Programs. In PLAS, pages 15–26. ACM, 2013.

Digital Library

[8]

T. Ball, V. Levin, and S. K. Rajamani. A Decade of Software Model Checking with SLAM. Comm. ACM, 54(7):68–76, 2011.

Digital Library

[9]

D. Beyer, T. A. Henzinger, R. Jhala, and R. Majumdar. The Software Model Checker Blast: Applications to Software Engineering. STTT, 9(5):505–525, 2007.

Digital Library

[10]

C. Bocovich and J. M. Atlee. Variable-Specific Resolutions for Feature Interactions. In FSE, pages 553–563. ACM, 2014.

Digital Library

[11]

E. Bodden, T. Tolˆ edo, M. Ribeiro, C. Brabrand, P. Borba, and M. Mezini. SPLLIFT: Statically Analyzing Software Product Lines in Minutes Instead of Years. In PLDI, pages 355–364. ACM, 2013.

Digital Library

[12]

M. Böhme, B. C. d. S. Oliveira, and A. Roychoudhury. Regression Tests to Expose Change Interaction Errors. In ESEC/FSE, pages 334–344. ACM, 2013.

[13]

C. Brabrand, M. Ribeiro, T. Tolˆ edo, and P. Borba. Intraprocedural Dataflow Analysis for Software Product Lines. In AOSD, pages 13–24. ACM, 2012.

Digital Library

[14]

F. P. Brooks. No Silver Bullet: Essence and Accidents of Software Engineering. Computer, 20(4):10–19, 1987.

Digital Library

[15]

G. Bruns. Foundations for Features. In Feature Interactions in Telecommunications and Software Systems VIII, pages 3–11. IOS Press, 2005.

[16]

J. R. Burch, E. M. Clarke, K. L. McMillan, D. L. Dill, and L.-J. Hwang. Symbolic Model Checking: 10 20 States and Beyond. In LICS, pages 428–439. IEEE, 1990.

[17]

I. Cabral, M. B. Cohen, and G. Rothermel. Improving the Testing and Testability of Software Product Lines. In SPLC, pages 241–255. Springer, 2010.

Digital Library

[18]

M. Calder, M. Kolberg, E. H. Magill, and S. Reiff-Marganiec. Feature Interaction: A Critical Review and Considered Forecast. Computer Networks, 41(1):115–141, 2003.

Digital Library

[19]

I. D. Carmo Machado, J. D. McGregor, Y. a. C. Cavalcanti, and E. S. De Almeida. On Strategies for Testing Software Product Lines: A Systematic Literature Review. IST, 56(10):1183–1199, 2014.

Digital Library

[20]

A. Classen, P. Heymans, P.-Y. Schobbens, and A. Legay. Symbolic Model Checking of Software Product Lines. In ICSE, pages 321–330. ACM, 2011.

Digital Library

[21]

M. B. Cohen, M. B. Dwyer, and J. Shi. Interaction Testing of Highly-Configurable Systems in the Presence of Constraints. In ISSTA, pages 129–139. ACM, 2007.

Digital Library

[22]

M. d’Amorim, S. Lauterburg, and D. Marinov. Delta Execution for Efficient State-Space Exploration of Object-Oriented Programs. TSE, 34(5):597–613, 2008.

Digital Library

[23]

W. De Groef, D. Devriese, N. Nikiforakis, and F. Piessens. FlowFox: A Web Browser with Flexible and Precise Information Flow Control. In CCS, pages 748–759. ACM, 2012.

Digital Library

[24]

D. Devriese and F. Piessens. Noninterference Through Secure Multi-Execution. In SP, pages 109–124. IEEE, 2010.

Digital Library

[25]

M. Erwig and E. Walkingshaw. The Choice Calculus: A Representation for Software Variation. TOSEM, 21(1):6:1–6:27, 2011.

Digital Library

[26]

B. J. Garvin and M. B. Cohen. Feature Interaction Faults Revisited: An Exploratory Study. In ISSRE, pages 90–99. IEEE, 2011.

Digital Library

[27]

M. Georgiev, S. Iyengar, S. Jana, R. Anubhai, D. Boneh, and V. Shmatikov. The Most Dangerous Code in the World: Validating SSL Certificates in Non-Browser Software. In CCS, pages 38–49. ACM, 2012.

Digital Library

[28]

M. Greiler, A. v. Deursen, and M.-A. Storey. Test Confessions: A Study of Testing Practices for Plug-in Systems. In ICSE, pages 244–254. IEEE, 2012.

Digital Library

[29]

R. J. Hall. Fundamental Nonmodularity in Electronic Mail. ASE, 12(1):41–79, 2005.

Digital Library

[30]

K. Havelund and T. Pressburger. Model Checking Java Programs Using Java PathFinder. STTT, 2(4):366–381, 2000.

[31]

K. J. Hoffman, P. Eugster, and S. Jagannathan. Semantics-aware trace analysis. In PLDI, pages 453–464. ACM, 2009.

Digital Library

[32]

P. Hosek and C. Cadar. VARAN the Unbelievable: An Efficient N-version Execution Framework. In ASPLOS, pages 339–353, 2015.

Digital Library

[33]

M. Jackson and P. Zave. Distributed Feature Composition: A Virtual Architecture for Telecommunications Services. TSE, 24(10):831, 1998.

Digital Library

[34]

C. Kästner, S. Apel, T. Thüm, and G. Saake. Type Checking Annotation-Based Product Lines. TOSEM, 21(3):14:1–14:39, 2012.

Digital Library

[35]

C. Kästner, K. Ostermann, and S. Erdweg. A Variability-Aware Module System. In OOPSLA, pages 773–792. ACM, 2012.

Digital Library

[36]

C. Kästner, A. von Rhein, S. Erdweg, J. Pusch, S. Apel, T. Rendel, and K. Ostermann. Toward Variability-Aware Testing. In FOSD, pages 1–8. ACM, 2012.

Digital Library

[37]

C. H. P. Kim, D. Batory, and S. Khurshid. Reducing Combinatorics in Testing Product Lines. In AOSD, pages 57—68. ACM, 2011.

Digital Library

[38]

C. H. P. Kim, S. Khurshid, and D. Batory. Shared Execution for Efficiently Testing Product Lines. In ISSRE, pages 221–230. IEEE, 2012.

Digital Library

[39]

C. H. P. Kim, D. Marinov, S. Khurshid, D. Batory, S. Souto, P. Barros, and M. d’Amorim. SPLat: Lightweight Dynamic Analysis for Reducing Combinatorics in Testing Configurable Systems. In ESEC/FSE, pages 257–267. ACM, 2013.

Digital Library

[40]

M. Kolberg, E. Magill, D. Marples, and S. Reiff. Feature Interactions in Telecommunication Systems VI, chapter Results of the Second Feature Interaction Contest, pages 311–325. IOS Press, 2000.

[41]

J. Kramer, J. Magee, M. Sloman, and A. Lister. CONIC: An Integrated Approach to Distributed Computer Control Systems. IEE Proc. Computers and Digital Techniques, 130(1):1–, 1983.

[42]

D. R. Kuhn, D. R. Wallace, and A. M. Gallo. Software Fault Interactions and Implications for Software Testing. TSE, 30:418–421, 2004.

Digital Library

[43]

J. Liebig, A. von Rhein, C. Kästner, S. Apel, J. Dörre, and C. Lengauer. Scalable Analysis of Variable Software. In ESEC/FSE, pages 81–91. ACM, 2013.

Digital Library

[44]

M. Lillack, C. Kästner, and E. Bodden. Tracking Load-Time Configuration Options. In ASE, pages 445–456. ACM, 2014.

Digital Library

[45]

R. E. Lopez-Herrejon and D. Batory. A Standard Problem for Evaluating Product-Line Methodologies. In GCSE, pages 10–24. Springer, 2001.

Digital Library

[46]

M. Maurer and D. Brumley. Tachyon: Tandem Execution for Efficient Live Patch Testing. In USENIX Security Symposium, pages 617–630, 2012.

Digital Library

[47]

F. Medeiros, C. Kästner, M. Ribeiro, R. Gheyi, and S. Apel. A Comparison of 10 Sampling Algorithms for Configurable Systems. In ICSE, pages 664–675. ACM, 2016.

Digital Library

[48]

F. Medeiros, C. Kästner, M. Ribeiro, S. Nadi, and R. Gheyi. The Love/Hate Relationship with the C Preprocessor: An Interview Study. In ECOOP, volume 37 of LIPIcs, pages 495–518. Schloss Dagstuhl–LZI, 2015.

[49]

J. Meinicke. VarexJ: A Variability-Aware Interpreter for Java Applications. Master’s thesis, University of Magdeburg, 2014.

[50]

M. Mendon¸ ca, A. Wasowski, and K. Czarnecki. SAT-Based Analysis of Feature Models is Easy. In SPLC, pages 231–240. Software Engineering Institute, 2009.

[51]

H. V. Nguyen, C. Kästner, and T. N. Nguyen. Exploring Variability-Aware Execution for Testing Plugin-Based Web Applications. In ICSE, pages 907–918. ACM, 2014.

Digital Library

[52]

A. Nhlabatsi, R. Laney, and B. Nuseibeh. Feature Interaction: The Security Threat from within Software Systems. Progress in Informatics, pages 75–89, 2008.

[53]

C. Nie and H. Leung. A Survey of Combinatorial Testing. CSUR, 43(2):11:1–11:29, 2011.

Digital Library

[54]

M. Plath and M. Ryan. Feature Integration Using a Feature Construct. SCP, 41(1):53–84, 2001.

Digital Library

[55]

E. Reisner, C. Song, K.-K. Ma, J. S. Foster, and A. Porter. Using Symbolic Evaluation to Understand Behavior in Configurable Software Systems. In ICSE, pages 445–454. ACM, 2010.

Digital Library

[56]

M. Schäler, A. Grebhahn, R. Schröter, S. Schulze, V. Köppen, and G. Saake. QuEval: Beyond High-Dimensional Indexing à la Carte. In VLDB, pages 1654–1665. VLDB Endowment, 2013.

Digital Library

[57]

K. Sen, G. Necula, L. Gong, and W. Choi. MultiSE: Multi-Path Symbolic Execution Using Value Summaries. In FSE, pages 842–853. ACM, 2015.

Digital Library

[58]

C. Song, A. Porter, and J. S. Foster. iTree: Efficiently Discovering High-Coverage Configurations Using Interaction Trees. SE, 40(3):251–265, 2014.

Digital Library

[59]

W. N. Sumner, T. Bao, X. Zhang, and S. Prabhakar. Coalescing Executions for Fast Uncertainty Analysis. In ICSE, pages 581–590. ACM, 2011.

Digital Library

[60]

R. Tartler, C. Dietrich, J. Sincero, W. Schröder-Preikschat, and D. Lohmann. Static Analysis of Variability in System Software: The 90,000# Ifdefs Issue. In Proc. USENIX, pages 421–432, 2014.

Digital Library

[61]

T. Thüm, S. Apel, C. Kästner, I. Schaefer, and G. Saake. A Classification and Survey of Analysis Strategies for Software Product Lines. CSUR, 47(1):6:1–6:45, 2014.

Digital Library

[62]

J. Tucek, W. Xiong, and Y. Zhou. Efficient Online Validation with Delta Execution. SIGARCH, 37(1):193–204, 2009.

Digital Library

[63]

A. von Rhein, S. Apel, and F. Raimondi. Introducing Binary Decision Diagrams in the Explicit-State Verification of Java Code. In JPF Workshop, 2011.

[64]

E. Walkingshaw, C. Kästner, M. Erwig, S. Apel, and E. Bodden. Variational Data Structures: Exploring Tradeoffs in Computing with Variability. In Onward!, pages 213–226. ACM, 2014.

Digital Library

[65]

B. Xin, W. N. Sumner, and X. Zhang. Efficient Program Execution Indexing. In PLDI, pages 238–248. ACM, 2008.

Digital Library

[66]

T. Xu, J. Zhang, P. Huang, J. Zheng, T. Sheng, D. Yuan, Y. Zhou, and S. Pasupathy. Do Not Blame Users for Misconfigurations. In Proc. Symposium on Operating Systems Principles, pages 244–259. ACM, 2013.

Digital Library

[67]

Z. Yin, X. Ma, J. Zheng, Y. Zhou, L. N. Bairavasundaram, and S. Pasupathy. An Empirical Study on Configuration Errors in Commercial and Open Source Systems. In SOSP, pages 159–172. ACM, 2011.

Digital Library

[68]

P. Zave. Software Requirements and Design: The Work of Michael Jackson, chapter Modularity in Distributed Feature Composition, pages 267–290. Good Friends Publishing Company, 2009.

[69]

S. Zhang and M. D. Ernst. Automated Diagnosis of Software Configuration Errors. In ICSE, pages 312–321. IEEE, 2013.

Digital Library

[70]

X. Zhang and R. Gupta. Whole Execution Traces and Their Applications. ACM Trans. Archit. Code Optim., 2(3):301–334, 2005.

Digital Library

Cited By

Ahmmed JCohen MGazzillo PFilkov VRay BZhou M(2024)Towards Automated Configuration DocumentationProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695311(2256-2261)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695311
Bittner PSchultheiß AMoosherr BYoung JTeixeira LWalkingshaw EAtaei PThüm T(2024)On the Expressive Power of Languages for Static VariabilityProceedings of the ACM on Programming Languages10.1145/36897478:OOPSLA2(1018-1050)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689747
Mahdavi-Hezaveh RFatima SWilliams L(2024)Paving a Path for a Combined Family of Feature Toggle and Configuration Option ResearchACM Transactions on Software Engineering and Methodology10.1145/367255533:7(1-27)Online publication date: 14-Jun-2024
https://dl.acm.org/doi/10.1145/3672555
Show More Cited By

Index Terms

On essential configuration complexity: measuring interactions in highly-configurable systems
1. Software and its engineering
  1. Software creation and management
    1. Software development techniques
      1. Reusability
  2. Software organization and properties
    1. Software system structures
      1. Software system models
        Feature interaction

Recommendations

Performance-influence models for highly configurable systems
ESEC/FSE 2015: Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering

Almost every complex software system today is configurable. While configurability has many benefits, it challenges performance prediction, optimization, and debugging. Often, the influences of individual configuration options on performance are ...
VarXplorer: Lightweight Process for Dynamic Analysis of Feature Interactions
VAMOS '18: Proceedings of the 12th International Workshop on Variability Modelling of Software-Intensive Systems

Features in highly configurable systems can interact in undesired ways which may result in faults. However, most interactions are not easily detectable as specifications of feature interactions are usually missing. In this paper, we aim to detect ...
Automating Test Reuse for Highly Configurable Software
SPLC '19: Proceedings of the 23rd International Systems and Software Product Line Conference - Volume A

Dealing with highly configurable systems is generally very complex. Hundreds of different analysis techniques have been conceived to deal with different aspects of configurable systems. One large focal point is the testing of configurable software. This ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASE '16: Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering

August 2016

899 pages

ISBN:9781450338455

DOI:10.1145/2970276

General Chair:
David Lo
Singapore Management University, Singapore
,
Program Chairs:
Sven Apel
University of Passau, Germany
,
Sarfraz Khurshid
University of Texas at Austin, USA

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAI: ACM Special Interest Group on Artificial Intelligence
SIGSOFT: ACM Special Interest Group on Software Engineering
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 August 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

BMBF
NSF
Science of Security Lablet
SERC
AFRL and DARPA

Conference

ASE'16

Sponsor:

SIGAI
SIGSOFT
IEEE-CS

ASE'16: ACM/IEEE International Conference on Automated Software Engineering

September 3 - 7, 2016

Singapore, Singapore

Acceptance Rates

Overall Acceptance Rate 82 of 337 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

67
Total Citations
View Citations
713
Total Downloads

Downloads (Last 12 months)178
Downloads (Last 6 weeks)56

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ahmmed JCohen MGazzillo PFilkov VRay BZhou M(2024)Towards Automated Configuration DocumentationProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695311(2256-2261)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695311
Bittner PSchultheiß AMoosherr BYoung JTeixeira LWalkingshaw EAtaei PThüm T(2024)On the Expressive Power of Languages for Static VariabilityProceedings of the ACM on Programming Languages10.1145/36897478:OOPSLA2(1018-1050)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689747
Mahdavi-Hezaveh RFatima SWilliams L(2024)Paving a Path for a Combined Family of Feature Toggle and Configuration Option ResearchACM Transactions on Software Engineering and Methodology10.1145/367255533:7(1-27)Online publication date: 14-Jun-2024
https://dl.acm.org/doi/10.1145/3672555
Douglas Ferrari Mendonça WAssunção WVergilio S(2024)Feature-oriented Test Case Prioritization Strategies: An Evaluation for Highly Configurable SystemsProceedings of the 28th ACM International Systems and Software Product Line Conference10.1145/3646548.3672592(72-83)Online publication date: 2-Sep-2024
https://dl.acm.org/doi/10.1145/3646548.3672592
Böhm SKrieter SHeß TThüm TLochau M(2024)Incremental Identification of T-Wise Feature InteractionsProceedings of the 18th International Working Conference on Variability Modelling of Software-Intensive Systems10.1145/3634713.3634715(27-36)Online publication date: 7-Feb-2024
https://dl.acm.org/doi/10.1145/3634713.3634715
Mendonça WAssunção WVergilio S(2024)Feature-oriented test case selection and prioritization during the evolution of highly-configurable systemsJournal of Systems and Software10.1016/j.jss.2024.112157217(112157)Online publication date: Nov-2024
https://doi.org/10.1016/j.jss.2024.112157
Casaluce RBurattin AChiaromonte FLafuente AVandin A(2024)White-box validation of quantitative product lines by statistical model checking and process miningJournal of Systems and Software10.1016/j.jss.2024.111983210:COnline publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1016/j.jss.2024.111983
Mendonça WAssunção WVergilio S(2023)Feature-oriented Test Case Selection during Evolution of Highly-Configurable SystemsProceedings of the 27th ACM International Systems and Software Product Line Conference - Volume A10.1145/3579027.3608979(76-86)Online publication date: 28-Aug-2023
https://dl.acm.org/doi/10.1145/3579027.3608979
Kritikos AStamelos I(2023)A resilience‐based framework for assessing the evolution of open source software projectsJournal of Software: Evolution and Process10.1002/smr.2597Online publication date: 19-Jul-2023
https://doi.org/10.1002/smr.2597
Gazzillo PCohen MScholliers CSinger J(2022)Bringing Together Configuration Research: Towards a Common GroundProceedings of the 2022 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3563835.3568737(259-269)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3563835.3568737
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents