{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T18:47:22Z","timestamp":1769107642260,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,4,12]],"date-time":"2022-04-12T00:00:00Z","timestamp":1649721600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,12]],"date-time":"2022-04-12T00:00:00Z","timestamp":1649721600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001866","name":"Fonds National de la Recherche Luxembourg","doi-asserted-by":"publisher","award":["C-PPP17\/IS\/11602677"],"award-info":[{"award-number":["C-PPP17\/IS\/11602677"]}],"id":[{"id":"10.13039\/501100001866","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001866","name":"Fonds National de la Recherche Luxembourg","doi-asserted-by":"publisher","award":["C-PPP17\/IS\/11602677"],"award-info":[{"award-number":["C-PPP17\/IS\/11602677"]}],"id":[{"id":"10.13039\/501100001866","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001866","name":"Fonds National de la Recherche Luxembourg","doi-asserted-by":"publisher","award":["C-PPP17\/IS\/11602677"],"award-info":[{"award-number":["C-PPP17\/IS\/11602677"]}],"id":[{"id":"10.13039\/501100001866","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Empir Software Eng"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Behavioral software models play a key role in many software engineering tasks; unfortunately, these models either are not available during software development or, if available, quickly become outdated as implementations evolve. Model inference techniques have been proposed as a viable solution to extract finite state models from execution logs. However, existing techniques do not scale well when processing very large logs that can be commonly found in practice. In this paper, we address the scalability problem of inferring the model of a component-based system from large system logs, without requiring any extra information. Our model inference technique, called <jats:italic>PRINS<\/jats:italic>, follows a divide-and-conquer approach. The idea is to first infer a model of each system component from the corresponding logs; then, the individual component models are merged together taking into account the flow of events across components, as reflected in the logs. We evaluated <jats:italic>PRINS<\/jats:italic> in terms of scalability and accuracy, using nine datasets composed of logs extracted from publicly available benchmarks and a personal computer running desktop business applications. The results show that <jats:italic>PRINS<\/jats:italic> can process large logs much faster than a publicly available and well-known state-of-the-art tool, without significantly compromising the accuracy of inferred models.<\/jats:p>","DOI":"10.1007\/s10664-021-10111-4","type":"journal-article","created":{"date-parts":[[2022,4,12]],"date-time":"2022-04-12T10:03:31Z","timestamp":1649757811000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["PRINS: scalable model inference for component-based system logs"],"prefix":"10.1007","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0840-6449","authenticated-orcid":false,"given":"Donghwan","family":"Shin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4854-685X","authenticated-orcid":false,"given":"Domenico","family":"Bianculli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1393-1010","authenticated-orcid":false,"given":"Lionel","family":"Briand","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,4,12]]},"reference":[{"key":"10111_CR1","doi-asserted-by":"crossref","unstructured":"Aghajani E, Nagy C, Vega-M\u00e1rquez OL, Linares-V\u00e1squez M, Moreno L, Bavota G, Lanza M (2019) Software documentation issues unveiled. In: 2019 IEEE\/ACM 41st International Conference on Software Engineering (ICSE). IEEE Press, Piscataway, pp 1199\u20131210","DOI":"10.1109\/ICSE.2019.00122"},{"key":"10111_CR2","doi-asserted-by":"crossref","unstructured":"Beschastnikh I, Brun Y, Schneider S, Sloan M, Ernst MD (2011) Leveraging existing instrumentation to automatically infer invariant-constrained models. In: Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering (ESEC\/FSE 2011). ACM, New York, pp 267\u2013277","DOI":"10.1145\/2025113.2025151"},{"key":"10111_CR3","doi-asserted-by":"crossref","unstructured":"Beschastnikh I, Brun Y, Ernst MD, Krishnamurthy A (2014) Inferring models of concurrent systems from logs of their behavior with CSight. In: Proceedings of the 36th International Conference on Software Engineering (ICSE 2014). ACM, New York, pp 468\u2013479","DOI":"10.1145\/2568225.2568246"},{"issue":"4","key":"10111_CR4","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1109\/TSE.2014.2369047","volume":"41","author":"I Beschastnikh","year":"2015","unstructured":"Beschastnikh I, Brun Y, Abrahamson J, Ernst MD, Krishnamurthy A (2015) Using declarative specification to improve the understanding, extensibility, and comparison of model-inference algorithms. IEEE Trans Softw Eng 41(4):408\u2013428","journal-title":"IEEE Trans Softw Eng"},{"issue":"6","key":"10111_CR5","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1109\/TC.1972.5009015","volume":"C-21","author":"AW Biermann","year":"1972","unstructured":"Biermann AW, Feldman JA (1972) On the synthesis of finite-state machines from samples of their behavior. IEEE Trans Comput C-21(6):592\u2013597. https:\/\/doi.org\/10.1109\/TC.1972.5009015","journal-title":"IEEE Trans Comput"},{"key":"10111_CR6","doi-asserted-by":"publisher","unstructured":"Busany N, Maoz S (2016) Behavioral log analysis with statistical guarantees. In: 2016 IEEE\/ACM 38th International Conference on Software Engineering (ICSE), pp 877\u2013887. https:\/\/doi.org\/10.1145\/2884781.2884805","DOI":"10.1145\/2884781.2884805"},{"key":"10111_CR7","doi-asserted-by":"publisher","unstructured":"Busany N, Maoz S, Yulazari Y (2019) Size and accuracy in model inference. In: 2019 34th IEEE\/ACM International Conference on Automated Software Engineering (ASE). IEEE Press, Piscataway, pp 887\u2013898. https:\/\/doi.org\/10.1109\/ASE.2019.00087","DOI":"10.1109\/ASE.2019.00087"},{"key":"10111_CR8","doi-asserted-by":"publisher","unstructured":"Chandola V, Banerjee A, Kumar V (2009) Anomaly detection: a survey. ACM Comput Surv 41(3). https:\/\/doi.org\/10.1145\/1541880.1541882","DOI":"10.1145\/1541880.1541882"},{"key":"10111_CR9","doi-asserted-by":"crossref","unstructured":"Cheng K, Krishnakumar AS (1993) Automatic functional test generation using the extended finite state machine model. In: Proceedings of the 30th Design Automation Conference (DAC 1993). ACM, New York, pp 86\u201391","DOI":"10.1145\/157485.164585"},{"key":"10111_CR10","unstructured":"Clarke Jr, EM, Grumberg O, Kroening D, Peled D, Veith H (2018) Model checking. MIT Press, Cambridge"},{"key":"10111_CR11","doi-asserted-by":"publisher","unstructured":"Cohen H, Maoz S (2015) Have we seen enough traces? (t). In: 2015 30th IEEE\/ACM International Conference on Automated Software Engineering (ASE), pp 93\u2013103. https:\/\/doi.org\/10.1109\/ASE.2015.62","DOI":"10.1109\/ASE.2015.62"},{"issue":"3","key":"10111_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/287000.287001","volume":"7","author":"JE Cook","year":"1998","unstructured":"Cook JE, Wolf AL (1998) Discovering models of software processes from event-based data. ACM Trans Softw Eng Methodol 7(3):215\u2013249. https:\/\/doi.org\/10.1145\/287000.287001","journal-title":"ACM Trans Softw Eng Methodol"},{"issue":"12","key":"10111_CR13","doi-asserted-by":"publisher","first-page":"1056","DOI":"10.1109\/TSE.2005.138","volume":"31","author":"C Damas","year":"2005","unstructured":"Damas C, Lambeau B, Dupont P, van Lamsweerde A (2005) Generating annotated behavior models from end-user scenarios. IEEE Trans Softw Eng 31(12):1056\u20131073. https:\/\/doi.org\/10.1109\/TSE.2005.138","journal-title":"IEEE Trans Softw Eng"},{"issue":"1","key":"10111_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean J, Ghemawat S (2008) Mapreduce: Simplified data processing on large clusters. Commun ACM 51(1):107\u2013113","journal-title":"Commun ACM"},{"key":"10111_CR15","doi-asserted-by":"publisher","first-page":"106276","DOI":"10.1016\/j.infsof.2020.106276","volume":"122","author":"D El-Masri","year":"2020","unstructured":"El-Masri D, Petrillo F, Gu\u00e9h\u00e9neuc Y G, Hamou-Lhadj A, Bouziane A (2020) A systematic literature review on automated log abstraction techniques. Inf Softw Technol 122:106276. https:\/\/doi.org\/10.1016\/j.infsof.2020.106276","journal-title":"Inf Softw Technol"},{"key":"10111_CR16","doi-asserted-by":"publisher","unstructured":"Emam SS, Miller J (2018) Inferring extended probabilistic finite-state automaton models from software executions. ACM Trans Softw Eng Methodol 27(1). https:\/\/doi.org\/10.1145\/3196883","DOI":"10.1145\/3196883"},{"issue":"1","key":"10111_CR17","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.scico.2007.01.015","volume":"69","author":"MD Ernst","year":"2007","unstructured":"Ernst MD, Perkins JH, Guo PJ, McCamant S, Pacheco C, Tschantz MS, Xiao C (2007) The Daikon system for dynamic detection of likely invariants. Sci Comput Program 69(1):35\u201345","journal-title":"Sci Comput Program"},{"key":"10111_CR18","doi-asserted-by":"publisher","unstructured":"Fraser G, Walkinshaw N (2012) Behaviourally adequate software testing. In: 2012 IEEE Fifth International Conference on Software Testing, Verification and Validation. IEEE Press, Piscataway, pp 300\u2013309. https:\/\/doi.org\/10.1109\/ICST.2012.110","DOI":"10.1109\/ICST.2012.110"},{"issue":"5","key":"10111_CR19","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"EM Gold","year":"1967","unstructured":"Gold EM (1967) Language identification in the limit. Inf Control 10(5):447\u2013474","journal-title":"Inf Control"},{"key":"10111_CR20","doi-asserted-by":"publisher","unstructured":"He P, Zhu J, Zheng Z, Lyu MR (2017) Drain: an online log parsing approach with fixed depth tree. In: 2017 IEEE International Conference on Web Services (ICWS). IEEE Press, Piscataway, pp 33\u201340. https:\/\/doi.org\/10.1109\/ICWS.2017.13","DOI":"10.1109\/ICWS.2017.13"},{"key":"10111_CR21","unstructured":"He S, Zhu J, He P, Lyu MR (2020) Loghub: A large collection of system log datasets towards automated log analytics. arXiv:https:\/\/arxiv.org\/abs\/2008.064482008.06448"},{"key":"10111_CR22","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1007\/s10664-012-9222-z","volume":"18","author":"MJH Heule","year":"2013","unstructured":"Heule MJH, Verwer S (2013) Software model synthesis using satisfiability solvers. Empir Software Eng 18:825\u2013856. https:\/\/doi.org\/10.1007\/s10664-012-9222-z","journal-title":"Empir Software Eng"},{"key":"10111_CR23","volume-title":"Introduction to automata theory, languages and computation","author":"JE Hopcroft","year":"2006","unstructured":"Hopcroft JE, Motwani R, Ullman JD (2006) Introduction to automata theory, languages and computation, 3rd edn. Addison-Wesley Longman Publishing Co., Inc., USA","edition":"3rd edn."},{"key":"10111_CR24","doi-asserted-by":"crossref","unstructured":"Kumar S, Khoo SC, Roychoudhury A, Lo D (2011) Mining message sequence graphs. In: Proceedings of the 33rd International Conference on Software Engineering (ICSE 2011). ACM, New York, pp 91\u2013 100","DOI":"10.1145\/1985793.1985807"},{"key":"10111_CR25","doi-asserted-by":"crossref","unstructured":"Kumar S, Khoo SC, Roychoudhury A, Lo D (2012) Inferring class level specifications for distributed systems. In: Proceedings of the 34th International Conference on Software Engineering (ICSE 2012). IEEE, Piscataway, pp 914\u2013924","DOI":"10.1109\/ICSE.2012.6227128"},{"key":"10111_CR26","doi-asserted-by":"crossref","unstructured":"Lang KJ, Pearlmutter BA, Price RA (1998) Results of the Abbadingo One DFA learning competition and a new evidence-driven state merging algorithm. In: Proceedings of the 4th International Colloquium on Grammatical Inference (ICGI 1998), LNCS, vol 1433. Springer, Berlin, pp 1\u201312","DOI":"10.1007\/BFb0054059"},{"key":"10111_CR27","unstructured":"Liu C, van Dongen B, Assy N, van der Aalst WMP (2016) Component behavior discovery from software execution data. In: Proceedings of the Symposium Series on Computational Intelligence (SSCI 2016). IEEE, Piscataway, pp 1\u20138"},{"key":"10111_CR28","doi-asserted-by":"publisher","unstructured":"Luo C, He F, Ghezzi C (2017) Inferring software behavioral models with mapreduce. Sci Comput Programm 145:13\u201336. https:\/\/doi.org\/10.1016\/j.scico.2017.04.004, http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0167642317300795","DOI":"10.1016\/j.scico.2017.04.004"},{"issue":"8","key":"10111_CR29","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1109\/TSE.2016.2623623","volume":"43","author":"L Mariani","year":"2017","unstructured":"Mariani L, Pezz\u00e8 M, Santoro M (2017) Gk-tail+ an efficient approach to learn software models. IEEE Trans Softw Eng 43(8):715\u2013738. https:\/\/doi.org\/10.1109\/TSE.2016.2623623","journal-title":"IEEE Trans Softw Eng"},{"key":"10111_CR30","doi-asserted-by":"crossref","unstructured":"Messaoudi S, Panichella A, Bianculli D, Briand L, Sasnauskas R (2018) A search-based approach for accurate identification of log message formats. In: 2018 IEEE\/ACM 26th International Conference on Program Comprehension (ICPC). IEEE Press, Piscataway, pp 167\u201316710","DOI":"10.1145\/3196321.3196340"},{"key":"10111_CR31","doi-asserted-by":"publisher","unstructured":"Palmer JD, McAddis N (2019) Documentation as a cross-cutting concern of software. In: Proceedings of the 37th ACM International Conference on the Design of Communication, SIGDOC \u201919. Association for Computing Machinery, New York. https:\/\/doi.org\/10.1145\/3328020.3353949","DOI":"10.1145\/3328020.3353949"},{"key":"10111_CR32","doi-asserted-by":"publisher","unstructured":"Polyvyanyy A, Smirnov S, Weske M (2008) Process model abstraction: A slider approach. In: 2008 12th International IEEE Enterprise Distributed Object Computing Conference, pp 325\u2013331. https:\/\/doi.org\/10.1109\/EDOC.2008.17","DOI":"10.1109\/EDOC.2008.17"},{"key":"10111_CR33","doi-asserted-by":"crossref","unstructured":"Rios N, Mendes L, Cerdeiral C, Magalh\u00e3es APF, Perez B, Correal D, Astudillo H, Seaman C, Izurieta C, Santos G, Oliveira sp\u00ednola R (2020) Hearing the voice of software practitioners on causes, effects, and practices to deal with documentation debt. In: Requirements engineering: Foundation for software quality. Springer International Publishing, Cham, pp 55\u201370","DOI":"10.1007\/978-3-030-44429-7_4"},{"key":"10111_CR34","doi-asserted-by":"crossref","unstructured":"Varrette S, Bouvry P, Cartiaux H, Georgatos F (2014) Management of an academic hpc cluster: The ul experience. In: Proc. of the 2014 intl. Conf. on high performance computing & simulation (HPCS 2014). IEEE, Bologna, pp 959\u2013967","DOI":"10.1109\/HPCSim.2014.6903792"},{"key":"10111_CR35","unstructured":"Walkinshaw N (2018) mintframework. https:\/\/github.com\/neilwalkinshaw\/mintframework, accessed: 2020-03-05"},{"key":"10111_CR36","doi-asserted-by":"crossref","unstructured":"Walkinshaw N, Bogdanov K, Damas C, Lambeau B, Dupont P (2010) A framework for the competitive evaluation of model inference techniques. In: Proceedings of the First International Workshop on Model Inference In Testing (MIIT 2010). ACM, New York, pp 1\u20139","DOI":"10.1145\/1868044.1868045"},{"issue":"4","key":"10111_CR37","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1007\/s10664-012-9210-3","volume":"18","author":"N Walkinshaw","year":"2013","unstructured":"Walkinshaw N, Lambeau B, Damas C, Bogdanov K, Dupont P (2013) Stamina: a competition to encourage the development and assessment of software model inference techniques. Empir Softw Eng 18(4):791\u2013824","journal-title":"Empir Softw Eng"},{"issue":"3","key":"10111_CR38","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1007\/s10664-015-9367-7","volume":"21","author":"N Walkinshaw","year":"2016","unstructured":"Walkinshaw N, Taylor R, Derrick J (2016) Inferring extended finite state machine models from software executions. Empir Softw Eng 21(3):811\u2013853. https:\/\/doi.org\/10.1007\/s10664-015-9367-7","journal-title":"Empir Softw Eng"},{"key":"10111_CR39","doi-asserted-by":"publisher","unstructured":"Wang S, Lo D, Jiang L, Maoz S, Budi A (2015) Scalable parallelization of specification mining using distributed computing. In: Bird C, Menzies T, Zimmermann T (eds) The Art and Science of Analyzing Software Data. https:\/\/doi.org\/10.1016\/B978-0-12-411519-4.00021-5, http:\/\/www.sciencedirect.com\/science\/article\/pii\/B9780124115194000215. Morgan Kaufmann, Boston, pp 623\u2013648","DOI":"10.1016\/B978-0-12-411519-4.00021-5"},{"key":"10111_CR40","volume-title":"Data mining: Practical machine learning tools and techniques","author":"IH Witten","year":"2016","unstructured":"Witten IH, Frank E, Hall MA, Pal CJ (2016) Data mining: Practical machine learning tools and techniques, 4th edn. Morgan Kaufmann, San Francisco","edition":"4th edn."},{"key":"10111_CR41","doi-asserted-by":"publisher","unstructured":"Zhu J, He S, Liu J, He P, Xie Q, Zheng Z, Lyu MR (2019) Tools and benchmarks for automated log parsing. In: Proceedings of the 41st International Conference on Software Engineering: Software Engineering in Practice, , ICSE-SEIP \u201910. IEEE Press, Piscataway, pp 121\u2013130. https:\/\/doi.org\/10.1109\/ICSE-SEIP.2019.00021","DOI":"10.1109\/ICSE-SEIP.2019.00021"}],"container-title":["Empirical Software Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10664-021-10111-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10664-021-10111-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10664-021-10111-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T21:02:27Z","timestamp":1654808547000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10664-021-10111-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,12]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10111"],"URL":"https:\/\/doi.org\/10.1007\/s10664-021-10111-4","relation":{},"ISSN":["1382-3256","1573-7616"],"issn-type":[{"value":"1382-3256","type":"print"},{"value":"1573-7616","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,12]]},"assertion":[{"value":"20 December 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 April 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of Interests"}}],"article-number":"87"}}