{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T18:37:45Z","timestamp":1760985465021,"version":"build-2065373602"},"reference-count":52,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2016,8,3]],"date-time":"2016-08-03T00:00:00Z","timestamp":1470182400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In a Software Product Line (SPL), the central notion of implementability provides the requisite connection between specifications and their implementations, leading to the definition of products. While it appears to be a simple extension of the traceability relation between components and features, it involves several subtle issues that were overlooked in the existing literature. In this paper, we have introduced a precise and formal definition of implementability over a fairly expressive traceability relation. The consequent definition of products in the given SPL naturally entails a set of useful analysis problems that are either refinements of known problems or are completely novel. We also propose a new approach to solve these analysis problems by encoding them as Quantified Boolean Formulae (QBF) and solving them through Quantified Satisfiability (QSAT) solvers. QBF can represent more complex analysis operations, which cannot be represented by using propositional formulae. The methodology scales much better than the SAT-based solutions hinted in the literature and were demonstrated through a tool called SPLAnE (SPL Analysis Engine) on a large set of SPL models.<\/jats:p>","DOI":"10.3390\/e18080269","type":"journal-article","created":{"date-parts":[[2016,8,3]],"date-time":"2016-08-03T10:10:31Z","timestamp":1470219031000},"page":"269","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Traceability Analyses between Features and Assets in Software Product Lines"],"prefix":"10.3390","volume":"18","author":[{"given":"Ganesh","family":"Narwane","sequence":"first","affiliation":[{"name":"Homi Bhabha National Institute, Anushakti Nagar, Mumbai 400042, India"}]},{"given":"Jos\u00e9","family":"Galindo","sequence":"additional","affiliation":[{"name":"Inria Rennes\u2014Bretagne Atlantique, Campus de Beaulieu, 263 Av. G\u00e9n\u00e9ral Leclerc, Rennes 35042, France"}]},{"given":"Shankara","family":"Krishna","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Bombay, Powai, Mumbai 400076, India"}]},{"given":"David","family":"Benavides","sequence":"additional","affiliation":[{"name":"Department of Computer Languages and Systems, Escuela T\u00e9cnica Superior de Ingenier\u00eda Inform\u00e1tica, Universidad de Sevilla, Av. Reina Mercedes s\/n, Seville 41012, Spain"}]},{"given":"Jean-Vivien","family":"Millo","sequence":"additional","affiliation":[{"name":"Inria Sophia Antipolis\u2014M\u00e9diterran\u00e9e, Route des Lucioles, Valbonne 06902, France"}]},{"given":"S.","family":"Ramesh","sequence":"additional","affiliation":[{"name":"General Motors Global R&amp;D, Warren, Michigan 49084, USA"}]}],"member":"1968","published-online":{"date-parts":[[2016,8,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Czarnecki, K., and Wasowski, A. (2007, January 10\u201314). Feature diagrams and logics: There and back again. Proceedings of the 11th International Software Product Line Conference (SPLC 2007), Kyoto, Japan.","DOI":"10.1109\/SPLINE.2007.4339252"},{"key":"ref_2","unstructured":"Berg, K., Bishop, J., and Muthig, D. (2005, January 20\u201322). Tracing software product line variability: From problem to solution space. Proceedings of the 2005 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists on IT Research in Developing Countries, White River, South Africa."},{"key":"ref_3","unstructured":"Czarnecki, K., and Eisenecker, U.W. (2000). Generative Programming: Methods, Tools, and Applications, Addison-Wesley Publishing."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Pohl, K., B\u00f6ckle, G., and van der Linden, F.J. (2005). Software Product Line Engineering\u2014Foundations, Principles, and Techniques, Springer.","DOI":"10.1007\/3-540-28901-1"},{"key":"ref_5","unstructured":"Clements, P.C., and Northrop, L.M. (2001). Software Product Lines: Practices and Patterns, Addison-Wesley."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1016\/j.is.2010.01.001","article-title":"Automated analysis of feature models 20 years later: A literature review","volume":"35","author":"Benavides","year":"2010","journal-title":"Inf. Syst."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Pohl, K., and Metzger, A. (2006, January 20\u201328). Variability management in software product line engineering. Proceedings of the 28th International Conference on Software Engineering, Shanghai, China.","DOI":"10.1145\/1134285.1134499"},{"key":"ref_8","unstructured":"Anquetil, N., Grammel, B., Galvao Lourenco da Silva, I., Noppen, J.A.R., Shakil Khan, S., Arboleda, H., Rashid, A., and Garcia, A. (2008, January 12). Traceability for model driven, software product line engineering. Proceedings of the ECMDA Traceability Workshop, Berlin, Germany."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/j.scico.2003.04.005","article-title":"Variability management with feature models","volume":"53","author":"Beuche","year":"2004","journal-title":"Sci. Comput. Program."},{"key":"ref_10","unstructured":"Czarnecki, K., and Antkiewicz, M. (October, January 29). Mapping features to models: A template approach based on superimposed variants. Proceedings of the 4th International Conference on Generative Programming and Component Engineering, Tallinn, Estonia."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Czarnecki, K., and Pietroszek, K. (2006, January 22\u201326). Verifying feature-based model templates against well-formedness OCL constraints. Proceedings of the 5th International Conference on Generative Programming and Component Engineering, Portland, OR, USA.","DOI":"10.1145\/1173706.1173738"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"DeBaud, J.M., and Schmid, K. (1999, January 16\u201322). A systematic approach to derive the scope of software product lines. Proceedings of the 21st International Conference on Software Engineering, Los Angeles, CA, USA.","DOI":"10.1145\/302405.302409"},{"key":"ref_13","unstructured":"Eisenbarth, T., Koschke, R., and Simon, D. (2002, January 9\u201313). A formal method for the analysis of product maps. Proceedings of the Requirements Engineering for Product Lines Workshop, Essen, Germany."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Satyananda, T.K., Lee, D., Kang, S., and Hashmi, S.I. (2007, January 26\u201329). Identifying traceability between feature model and software architecture in software product line using formal concept analysis. Proceedings of the International Conference on Computational Science and its Applications (ICCSA 2007), Kuala Lumpur, Malaysia.","DOI":"10.1109\/ICCSA.2007.59"},{"key":"ref_15","unstructured":"Zhu, C., Lee, Y., Zhao, W., and Zhang, J. (2006, January 26\u201329). A feature oriented approach to mapping from domain requirements to product line architecture. Proceedings of the 2006 International Conference on Software Engineering Research and Practice, Las Vegas, NV, USA."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/s10270-009-0120-9","article-title":"A model-driven traceability framework for software product lines","volume":"9","author":"Anquetil","year":"2010","journal-title":"Softw. Syst. Model."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Cavalcanti, Y.A.C., do Carmo Machado, I., da Mota, P.A., Neto, S., Lobato, L.L., de Almeida, E.S., and de Lemos Meira, S.R. (2011, January 27\u201329). Towards Metamodel Support for Variability and Traceability in Software Product Lines. Proceedings of the 5th Workshop on Variability Modeling of Software-Intensive Systems, Namur, Belgium.","DOI":"10.1145\/1944892.1944898"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Ghanam, Y., and Maurer, F. (2009, January 24\u201328). Extreme product line engineering: Managing variability and traceability via executable specifications. Proceedings of the 2009 Agile Conference, Chicago, IL, USA.","DOI":"10.1109\/AGILE.2009.12"},{"key":"ref_19","unstructured":"Riebisch, M., and Brcina, R. (April, January 31). Optimizing design for variability using traceability links. Proceedings of the 15th Annual IEEE International Conference and Workshop on the Engineering of Computer Based Systems, Belfast, Northern Ireland."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Metzger, A., Heymans, P., Pohl, K., Schobbens, P.Y., and Saval, G. (2007, January 15\u201319). Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis. Proceedings of the 15th IEEE International Requirements Engineering Conference (RE 2007), Delhi, India.","DOI":"10.1109\/RE.2007.61"},{"key":"ref_21","unstructured":"SAT4J-Solver. Available online: http:\/\/www.sat4j.org\/."},{"key":"ref_22","unstructured":"MiniSAT-Solver. Available online: http:\/\/minisat.se\/."},{"key":"ref_23","unstructured":"PicoSAT. Available online: http:\/\/fmv.jku.at\/picosat\/."},{"key":"ref_24","unstructured":"CirQit. Available online: http:\/\/www.cs.utoronto.ca\/~alexia\/cirqit\/."},{"key":"ref_25","unstructured":"RAReQS-NN. Available online: http:\/\/sat.inesc-id.pt\/~mikolas\/sw\/rareqs-nn\/."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Mohalik, S., Ramesh, S., Millo, J.V., Krishna, S.N., and Narwane, G.K. (2012, January 2\u20137). Tracing SPLs precisely and efficiently. Proceedings of the 16th International Software Product Line Conference\u2013Volume 1, Salvador, Brazil.","DOI":"10.1145\/2362536.2362562"},{"key":"ref_27","unstructured":"Benavides, D., Segura, S., Trinidad, P., and Cort\u00e9s, A.R. (2007, January 16\u201318). FAMA: Tooling a framework for the automated analysis of feature models. Proceedings of the First International Workshop on Variability Modelling of Softwareintensive Systems, Limerick, Ireland."},{"key":"ref_28","unstructured":"SPLAnE. Available online: http:\/\/www.cse.iitb.ac.in\/~splane\/."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Kang, K.C., Cohen, S.G., Hess, J.A., Novak, W.E., and Peterson, A.S. (1990). Feature-Oriented Domain Analysis (FODA) Feasibility Study, Software Engineering Institute of Carnegie Mellon University. Technical Report CMU\/SEI-90-TR-21.","DOI":"10.21236\/ADA235785"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1016\/j.comnet.2006.08.008","article-title":"Generic semantics of feature diagrams","volume":"51","author":"Schobbens","year":"2007","journal-title":"Comput. Netw."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Batory, D. (2005, January 26\u201329). Feature models, grammars, and propositional formulas. Proceedings of the 9th International Conference on Software Product Lines, Rennes, France.","DOI":"10.1007\/11554844_3"},{"key":"ref_32","unstructured":"The Yices SMT Solver. Available online: http:\/\/yices.csl.sri.com\/."},{"key":"ref_33","unstructured":"BDDSolve. Available online: http:\/\/www.win.tue.nl\/~wieger\/bddsolve\/."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","article-title":"The polynomial-time hierarchy","volume":"3","author":"Stockmeyer","year":"1976","journal-title":"Theor. Comput. Sci."},{"key":"ref_35","unstructured":"SPLAnE-TR. Available online: http:\/\/www.cse.iitb.ac.in\/~krishnas\/tr2012.pdf."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Roos-Frantz, F., Galindo, J.A., Benavides, D., and Ruiz-Cort\u00e9s, A. (2012, January 2\u20137). FaMa-OVM: A tool for the automated analysis of OVMs. Proceedings of the 16th International Software Product Line Conference, Salvador, Brazil.","DOI":"10.1145\/2364412.2364456"},{"key":"ref_37","unstructured":"Galindo, J.A., Benavides, D., and Segura, S. (2010, January 20). Debian packages repositories as software product line models. Towards automated analysis. Proceedings of the 1st International Workshop on Automated Configuration and Tailoring of Applications, Antwerp, Belgium."},{"key":"ref_38","unstructured":"Seidl, M. The qpro Input Format: A Textual Syntax for QBFs in Negation Normal Form. Available online: http:\/\/qbf.satisfiability.org\/gallery\/qpro.pdf."},{"key":"ref_39","unstructured":"Gallery, Q. QCIR-G14: A Non-Prenex Non-CNF Format for Quantified Boolean Formulas. Available online: http:\/\/qbf.satisfiability.org\/gallery\/qcir-gallery14.pdf."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Peschiera, C., Pulina, L., Tacchella, A., Bubeck, U., Kullmann, O., and Lynce, I. (2010, January 11\u201314). The Seventh QBF Solvers Evaluation (QBFEVAL\u201910). Proceedings of the 13th International Conference (SAT 2010), Edinburgh, UK.","DOI":"10.1007\/978-3-642-14186-7_20"},{"key":"ref_41","unstructured":"Mendonca, M., Branco, M., and Cowan, D. (2009, January 25\u201329). SPLOT: Software product lines online tools. Proceedings of the 24th ACM SIGPLAN Conference Companion on Object Oriented Programming Systems Languages and Applications, Orlando, FL, USA."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Segura, S., Galindo, J.A., Benavides, D., Parejo, J.A., and Ruiz-Cort\u00e9s, A. (2012, January 25\u201327). BeTTy: Benchmarking and testing on the automated analysis of feature models. Proceedings of the Sixth International Workshop on Variability Modeling of Software-Intensive Systems, Leipzig, Germany.","DOI":"10.1145\/2110147.2110155"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Th\u00fcm, T., Batory, D.S., and K\u00e4stner, C. (2009, January 16\u201324). Reasoning about edits to feature models. Proceedings of the 31st International Conference on Software Engineering (ICSE 2009), Vancouver, BC, Canada.","DOI":"10.1109\/ICSE.2009.5070526"},{"key":"ref_44","unstructured":"SPLAnE. Available online: http:\/\/www.cse.iitb.ac.in\\~splane."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1094","DOI":"10.1016\/j.jss.2010.02.017","article-title":"Automated diagnosis of feature model configurations","volume":"83","author":"White","year":"2010","journal-title":"J. Syst. Softw."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Bagheri, E., di Noia, T., Ragone, A., and Gasevic, D. (2010, January 13\u201317). Configuring software product line feature models based on stakeholders\u2019 soft and hard requirements. Proceedings of the 14th International Conference on Software Product Lines: Going Beyond, Jeju Island, Korea.","DOI":"10.1007\/978-3-642-15579-6_2"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Soltani, S., Asadi, M., Hatala, M., Gasevi\u0107, D., and Bagheri, E. (2011, January 6\u201310). Automated planning for feature model configuration based on stakeholders\u2019 business concerns. Proceedings of the 26th IEEE\/ACM International Conference on Automated Software Engineering, Lawrence, KS, USA.","DOI":"10.1109\/ASE.2011.6100118"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.tcs.2012.01.031","article-title":"A theory of software product line refinement","volume":"455","author":"Borba","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"ref_49","unstructured":"Mendonca, M., Wasowski, A., and Czarnecki, K. (2009, January 24\u201328). SAT-based analysis of feature models is easy. Proceedings of the 13th International Software Product Lines (SPLC 2009), San Francisco, CA, USA."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"She, S., Lotufo, R., Berger, T., Wasowski, A., and Czarnecki, K. (2011, January 21\u201328). Reverse engineering feature models. Proceedings of the 33rd International Conference on Software Engineering (ICSE 2011), Waikiki, HI, USA.","DOI":"10.1145\/1985793.1985856"},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Janota, M., and Kiniry, J. (2007, January 10\u201314). Reasoning about feature models in higher-order logic. Proceedings of the 11th International Software Product Lines (SPLC 2007), Kyoto, Japan.","DOI":"10.1109\/SPLINE.2007.36"},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Acher, M., Collet, P., Lahire, P., and France, R.B. (2012, January 25\u201330). Separation of concerns in feature modeling: Support and applications. Proceedings of the 11th International Conference on Aspect-Oriented Software Development (AOSD 2012), Potsdam, Germany.","DOI":"10.1145\/2162049.2162051"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/18\/8\/269\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:27:38Z","timestamp":1760210858000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/18\/8\/269"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,3]]},"references-count":52,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2016,8]]}},"alternative-id":["e18080269"],"URL":"https:\/\/doi.org\/10.3390\/e18080269","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2016,8,3]]}}}