skip to main content
research-article

On software component co-installability

Published: 22 October 2013 Publication History

Abstract

Modern software systems are built by composing components drawn from large repositories, whose size and complexity is increasing at a very fast pace. A fundamental challenge for the maintainability and the scalability of such software systems is the ability to quickly identify the components that can or cannot be installed together: this is the co-installability problem, which is related to boolean satisfiability and is known to be algorithmically hard. This article develops a novel theoretical framework, based on formally certified semantic preserving graph-theoretic transformations, that allows us to associate to each concrete component repository a much smaller one with a simpler structure, that we call strongly flat, with equivalent co-installability properties. This flat repository can be displayed in a way that provides a concise view of the co-installability issues in the original repository, or used as a basis for various algorithms related to co-installability, like the efficient computation of strong conflicts between components. The proofs contained in this work have been machine checked using the Coq proof assistant.

References

[1]
Abate, P., Boender, J., Di Cosmo, R., and Zacchiroli, S. 2009. Strong dependencies between software components. In Proceedings of the ESEM. IEEE Press, 89--99.
[2]
Abate, P., Di Cosmo, R., Treinen, R., and Zacchiroli, S. 2011. MPM: A modular package manager. In Proceedings of the 14th international ACM SIGSOFT Symposium on Component Based Software Engineering (CBSE'11). ACM, New York, 179--188.
[3]
Abate, P., Di Cosmo, R., Treinen, R., and Zacchiroli, S. 2012a. Dependency solving: A separate concern in component evolution management. J. Syst. Softw. 85, 10, (Special Issue: Automated Software Evolution), 2228--2240.
[4]
Abate, P., Di Cosmo, R., Treinen, R., and Zacchiroli, S. 2012b. Learning from the Future of Component Repositories. In Proceedings of the 15th International ACM SIGSOFT Symposium on Component Based Software Engineering (CBSE-2012). ACM.
[5]
Ajmani, S., Liskov, B., and Shrira, L. 2006. Modular software upgrades for distributed systems. In Proceedings of the ECOOP, D. Thomas, Ed., Lecture Notes in Computer Science Series, vol. 4067, Springer, 452--476.
[6]
Argelich, J., Le Berre, D., Lynce, I., Marques-Silva, J., and Rapicault, P. 2010. Solving Linux upgradeability problems using boolean optimization. In LoCoCo: Logics for Component Configuration, EPTCS Series, vol. 29, 11--22.
[7]
Ausiello, G., D'Atri, A., and Saccà, D. 1983. Graph algorithms for functional dependency manipulation. J. ACM 30, 4, 752--766.
[8]
Ausiello, G., D'Atri, A., and Saccá, D. 1986. Minimal representation of directed hypergraphs. SIAM J. Comput. 15, 2, 418--431.
[9]
Baader, F. and Nipkow, T. 1998. Term Rewriting and All That. Cambridge University Press.
[10]
Buning, H. K. and Lettmann, T. 2002. Propositional logic: Deduction and algorithms. Studia Logica 71, 247--258.
[11]
The Coq Development Team. 2008. The Coq Proof Assistant Reference Manual -- Version V8.2.
[12]
Crameri, O., Knezevic, N., Kostic, D., Bianchini, R., and Zwaenepoel, W. 2007. Staged deployment in mirage, an integrated software upgrade testing and distribution system. SIGOPS Oper. Syst. Rev. 41, 6, 221--236.
[13]
de Alfaro, L. and Henzinger, T. A. 2001. Interface automata. In Proceedings of the ESEC/SIGSOFT FSE.
[14]
Di Cosmo, R. and Boender, J. 2010. Using strong conflicts to detect quality issues in component-based complex systems. In Proceedings of the 3rd India Software Engineering Conference (ISEC'10). ACM, New York, 163--172.
[15]
Di Cosmo, R., Durak, B., Leroy, X., Mancinelli, F., and Vouillon, J. 2006a. Maintaining large software distributions: New challenges from the FOSS era. In Proceedings of the FRCSS'06 Workshop. EASST Newsletter.
[16]
Di Cosmo, R., Lhomme, O., and Michel, C. 2011. Aligning component upgrades. In Proceedings of the 2nd Workshop on Logics for Component Configuration, C. Drescher, I. Lynce, and R. Treinen, Eds., EPTCS 65, 1--11.
[17]
Di Cosmo, R., Mancinelli, F., Boender, J., Vouillon, J., Durak, B., Leroy, X., Pinheiro, D., Trezentos, P., Morgado, M., Milo, T., Zur, T., Suarez, R., Lijour, M., and Treinen, R. 2006b. Report on formal mangement of software dependencies. Tech. rep., EDOS. Apr. EDOS project Deliverable 2.2. http://www.edos-project.org/xwiki/bin/download/Main/Deliverables/edos-wp2d2.pdf.
[18]
Di Cosmo, R. and Vouillon, J. 2011. On software component co-installability. In Proceedings of the SIGSOFT/FSE'11 19th ACM SIGSOFT Symposium on the Foundations of Software Engineering (FSE-19) and the 13rd European Software Engineering Conference (ESEC-13). T. Gyimóthy and A. Zeller, Eds., ACM, 256--266.
[19]
Di Cosmo, R. and Zacchiroli, S. 2010. Feature diagrams as package dependencies. In Proceedings of SPLC. J. Bosch and J. Lee, Eds, Lecture Notes in Computer Science Series, vol. 6287, Springer, 476--480.
[20]
Dowling, W. F. and Gallier, J. H. 1984. Linear-time algorithms for testing the satisfiability of propositional horn formulae. J. Log. Program. 1, 3, 267--284.
[21]
Ellson, J., Gansner, E., Koutsofios, L., North, S., Woodhull, G. 2001. Graphviz: Open source graph drawing tools. In Lecture Notes in Computer Science, Springer-Verlag, 483--484.
[22]
Gebser, M., Kaminski, R., and Schaub, T. 2011. aspcud: A linux package configuration tool based on answer set programming. In Proceedings of LoCoCo. C. Drescher, I. Lynce, and R. Treinen, Eds., EPTCS Series, vol. 65, 12--25.
[23]
Graves, T. L., Karr, A. F., Marron, J. S., and Siy, H. 2000. Predicting fault incidence using software change history. IEEE Trans. Softw. Eng. 26, 7, 653--661.
[24]
Hanneman, R. A. and Riddle, M. 2005. Introduction to Social Network Methods. University of California, Riverside.
[25]
Inverardi, P., Wolf, A. L., and Yankelevich, D. 2000. Static checking of system behaviors using derived component assumptions. ACM Trans. Softw. Eng. Methodol. 9, 3, 239--272.
[26]
Le Berre, D. and Parrain, A. 2008. On SAT technologies for dependency management and beyond. In Proceedings of SPLC (2). S. Thiel and K. Pohl, Eds., Lero International Science Centre, University of Limerick, Ireland, 197--200.
[27]
Mancinelli, F., Boender, J., Di Cosmo, R., Vouillon, J., Durak, B., Leroy, X., and Treinen, R. 2006. Managing the complexity of large free and open source package-based software distributions. In Proceedings of the ASE. IEEE Computer Society, 199--208.
[28]
McCamant, S. and Ernst, M. D. 2003. Predicting problems caused by component upgrades. In Proceedings of ESEC/SIGSOFT FSE. ACM, 287--296.
[29]
McCamant, S. and Ernst, M. D. 2004. Early identification of incompatibilities in multi-component upgrades. In Proceedings of ECOOP. M. Odersky, Ed., Lecture Notes in Computer Science, vol. 3086, Springer, 440--464.
[30]
Nagappan, N. and Ball, T. 2007. Using software dependencies and churn metrics to predict field failures: An empirical case study. In Proceedings of ESEM'07, 364--373.
[31]
Neuhaus, S., Zimmermann, T., Holler, C., and Zeller, A. 2007. Predicting vulnerable software components. In Proceedings of the ACM Conference on Computer and Communications Security (CCS'07). P. Ning, S. D. C. di Vimercati, and P. F. Syverson, Eds., ACM, 529--540.
[32]
Pei-Breivold, H., Crnkovic, I., Land, R., and Larsson, S. 2008. Using dependency model to support software architecture evolution. In Proceedings of, EVOL'08.
[33]
Tivoli, M. and Inverardi, P. 2008. Failure-free coordinators synthesis for component-based architectures. Sci. Comput. Program. 71, 3, 181--212.
[34]
Treinen, R. and Zacchiroli, S. 2008. Solving package dependencies: From EDOS to Mancoosi. In Proceedings of 9th Annual Conference of the Debian Project (DebConf8). 18--43.
[35]
Trezentos, P., Lynce, I., and Oliveira, A. L. 2010. APT-PBO: Solving the software dependency problem using pseudo-Boolean optimization. In Proceedings of ASE. C. Pecheur, J. Andrews, and E. D. Nitto, Eds., ACM, 427--436.
[36]
Tucker, C., Shuffelton, D., Jhala, R., and Lerner, S. 2007. Opium: Optimal package install/uninstall manager. In Proceedings of ICSE. IEEE Computer Society, 178--188.
[37]
Winskel, G. 1987. Event structures. In Petri Nets: Applications and Relationships to Other Models of Concurrency, W. Brauer, W. Reisig, and G. Rozenberg, Eds., Lecture Notes in Computer Science, vol. 255, Springer Berlin, 325--392.
[38]
Yoon, I.-C., Sussman, A., Memon, A., and Porter, A. 2007. Direct-dependency-based software compatibility testing. In Proceedings of ASE'07. ACM, New York, 409--412.
[39]
Yoon, I.-C., Sussman, A., Memon, A., and Porter, A. 2008. Effective and scalable software compatibility testing. In Proceedings of ISSTA'08. ACM, New York, 63--74.
[40]
Zimmermann, T. and Nagappan, N. 2008. Predicting defects using network analysis on dependency graphs. In Proceedings of ICSE'08. ACM, 531--540.

Cited By

View all
  • (2024)Diagnosis of package installation incompatibility via knowledge baseScience of Computer Programming10.1016/j.scico.2024.103098(103098)Online publication date: Mar-2024
  • (2024)What is an app store? The software engineering perspectiveEmpirical Software Engineering10.1007/s10664-023-10362-329:1Online publication date: 2-Jan-2024
  • (2023)On the Efficiency of Building Large Collections of Software: Modeling, Algorithms, and Experimental ResultsSoftware Technologies10.1007/978-3-031-37231-5_7(145-168)Online publication date: 19-Jul-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Software Engineering and Methodology
ACM Transactions on Software Engineering and Methodology  Volume 22, Issue 4
Testing, debugging, and error handling, formal methods, lifecycle concerns, evolution and maintenance
October 2013
387 pages
ISSN:1049-331X
EISSN:1557-7392
DOI:10.1145/2522920
Issue’s Table of Contents
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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 October 2013
Accepted: 01 October 2012
Revised: 01 July 2012
Received: 01 November 2011
Published in TOSEM Volume 22, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Component
  2. co-installability
  3. conflicts
  4. dependencies
  5. open source
  6. package management

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)6
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Diagnosis of package installation incompatibility via knowledge baseScience of Computer Programming10.1016/j.scico.2024.103098(103098)Online publication date: Mar-2024
  • (2024)What is an app store? The software engineering perspectiveEmpirical Software Engineering10.1007/s10664-023-10362-329:1Online publication date: 2-Jan-2024
  • (2023)On the Efficiency of Building Large Collections of Software: Modeling, Algorithms, and Experimental ResultsSoftware Technologies10.1007/978-3-031-37231-5_7(145-168)Online publication date: 19-Jul-2023
  • (2022)NufixProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510118(1545-1557)Online publication date: 21-May-2022
  • (2021)A Quantitative Assessment of Package Freshness in Linux Distributions2021 IEEE/ACM 4th International Workshop on Software Health in Projects, Ecosystems and Communities (SoHeal)10.1109/SoHeal52568.2021.00008(9-16)Online publication date: May-2021
  • (2021)Package Management System in Linux2021 Asian Conference on Innovation in Technology (ASIANCON)10.1109/ASIANCON51346.2021.9544805(1-6)Online publication date: 27-Aug-2021
  • (2019)A formal framework for measuring technical lag in component repositories - and its application to npmJournal of Software: Evolution and Process10.1002/smr.2157(e2157)Online publication date: 19-Mar-2019
  • (2018)Negative trust for conflict resolution in software managementWeb Intelligence10.3233/WEB-18039316:4(251-271)Online publication date: 31-Oct-2018
  • (2018)A Real-Time Container Architecture for Dependable Distributed Embedded Applications2018 IEEE 14th International Conference on Automation Science and Engineering (CASE)10.1109/COASE.2018.8560546(1367-1374)Online publication date: Aug-2018
  • (2018)Intercomponent Dependency Issues in Software EcosystemsSoftware Technology: 10 Years of Innovation in IEEE Computer10.1002/9781119174240.ch3(35-57)Online publication date: 3-Sep-2018
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media