{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T10:16:29Z","timestamp":1770977789487,"version":"3.50.1"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031572586","type":"print"},{"value":"9783031572593","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T00:00:00Z","timestamp":1712361600000},"content-version":"vor","delay-in-days":96,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Maintaining software is cumbersome when method argument constraints are undocumented. To reveal them, previous work learned preconditions from exemplary valid and invalid method arguments. In practice, it would be highly beneficial to know class invariants, too, because functionality added during software maintenance must not break them. Even more so than method preconditions, class invariants are rarely documented and often cannot completely be inferred automatically, especially for objects exhibiting complex state such as dynamic data structures.<\/jats:p><jats:p>This paper presents a novel dynamic approach to learning class invariants, thereby complementing related work on learning method preconditions. We automatically synthesize assertions from an adjustable assertion grammar to distinguish valid and invalid objects. While random walks generate valid objects, a combination of bounded-exhaustive testing techniques and behavioral oracles yield invalid objects. The utility of our approach for code comprehension and software maintenance is demonstrated by comparing our learned invariants to documented invariant validation methods found in real-world Java classes and to the invariants detected by the Daikon tool.<\/jats:p>","DOI":"10.1007\/978-3-031-57259-3_7","type":"book-chapter","created":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T13:01:39Z","timestamp":1712322099000},"page":"143-164","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Comprehending Object State via Dynamic Class Invariant Learning"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6816-8393","authenticated-orcid":false,"given":"Jan H.","family":"Boockmann","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0925-4870","authenticated-orcid":false,"given":"Gerald","family":"L\u00fcttgen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,4,6]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","unstructured":"Albarghouthi, A., Gulwani, S., Kincaid, Z.: Recursive program synthesis. In: Sharygina, N., Veith, H. (eds.) Computer Aided Verification (CAV). LNCS, vol.\u00a08044, pp. 934\u2013950. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-642-39799-8_67","DOI":"10.1007\/978-3-642-39799-8_67"},{"key":"7_CR2","doi-asserted-by":"publisher","unstructured":"Astorga, A., Madhusudan, P., Saha, S., Wang, S., Xie, T.: Learning stateful preconditions modulo a test generator. In: McKinley, K.S., Fisher, K. (eds.) Conference on Programming Language Design and Implementation (PLDI). pp. 775\u2013787. ACM (2019). https:\/\/doi.org\/10.1145\/3314221.3314641","DOI":"10.1145\/3314221.3314641"},{"key":"7_CR3","doi-asserted-by":"publisher","unstructured":"Boyapati, C., Khurshid, S., Marinov, D.: Korat: Automated testing based on Java predicates. In: Frankl, P.G. (ed.) International Symposium on Software Testing and Analysis (ISSTA). pp. 123\u2013133. ACM (2002). https:\/\/doi.org\/10.1145\/566172.566191","DOI":"10.1145\/566172.566191"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Cheng, D.Y., Deutsch, J.T., Dutton, R.W.: \u201cDefensive programming\u201d in the rapid development of a parallel scientific program. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 9(6), 665\u2013669 (1990), https:\/\/doi.org\/10.1109\/43.55196","DOI":"10.1109\/43.55196"},{"key":"7_CR5","doi-asserted-by":"publisher","unstructured":"Claessen, K., Hughes, J.: Quickcheck: A lightweight tool for random testing of haskell programs. In: Odersky, M., Wadler, P. (eds.) International Conference on Functional Programming (ICFP). pp. 268\u2013279. ACM (2000). https:\/\/doi.org\/10.1145\/351240.351266","DOI":"10.1145\/351240.351266"},{"key":"7_CR6","doi-asserted-by":"publisher","unstructured":"Coppit, D., Yang, J., Khurshid, S., Le, W., Sullivan, K.J.: Software assurance by bounded exhaustive testing. IEEE Trans. Software Eng. 31(4), 328\u2013339 (2005). https:\/\/doi.org\/10.1109\/TSE.2005.52","DOI":"10.1109\/TSE.2005.52"},{"key":"7_CR7","unstructured":"Ernst, M.D., Griswold, W.G., Kataoka, Y., Notkin, D.: Dynamically discovering program invariants involving collections. In: University of Washington Department of Computer Science and Engineering technical report UW-CSE-99-11-02, (Seattle, WA), November 16, 1999. Revised March 17, 2000. (2000)"},{"key":"7_CR8","doi-asserted-by":"publisher","unstructured":"Ernst, M.D., Perkins, J.H., Guo, P.J., McCamant, S., Pacheco, C., Tschantz, M.S., Xiao, C.: The Daikon system for dynamic detection of likely invariants. Sci. Comput. Program. 69(1-3), 35\u201345 (2007). https:\/\/doi.org\/10.1016\/j.scico.2007.01.015","DOI":"10.1016\/j.scico.2007.01.015"},{"key":"7_CR9","doi-asserted-by":"publisher","unstructured":"Fink, G., Bishop, M.: Property-based testing: A new approach to testing for assurance. ACM SIGSOFT Softw. Eng. Notes 22(4), 74\u201380 (1997). https:\/\/doi.org\/10.1145\/263244.263267","DOI":"10.1145\/263244.263267"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Fraser, G., Arcuri, A.: Evosuite: Automatic test suite generation for object-oriented software. In: Gyim\u00f3thy, T., Zeller, A. (eds.) Symposium on the Foundations of Software Engineering and European Software Engineering Conference (FSE\/ESEC). pp. 416\u2013419. ACM (2011), https:\/\/doi.org\/10.1145\/2025113.2025179","DOI":"10.1145\/2025113.2025179"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Gligoric, M., Gvero, T., Jagannath, V., Khurshid, S., Kuncak, V., Marinov, D.: Test generation through programming in UDITA. In: Kramer, J., Bishop, J., Devanbu, P.T., Uchitel, S. (eds.) International Conference on Software Engineering (ICSE). pp. 225\u2013234. ACM (2010), https:\/\/doi.org\/10.1145\/1806799.1806835","DOI":"10.1145\/1806799.1806835"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Guttag, J.V., Horowitz, E., Musser, D.R.: Abstract data types and software validation. Commun. ACM 21(12), 1048\u20131064 (1978), https:\/\/doi.org\/10.1145\/359657.359666","DOI":"10.1145\/359657.359666"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Hierons, R.M., Bogdanov, K., Bowen, J.P., Cleaveland, R., Derrick, J., Dick, J., Gheorghe, M., Harman, M., Kapoor, K., Krause, P.J., L\u00fcttgen, G., Simons, A.J.H., Vilkomir, S.A., Woodward, M.R., Zedan, H.: Using formal specifications to support testing. ACM Comput. Surv. 41(2), 9:1\u20139:76 (2009), https:\/\/doi.org\/10.1145\/1459352.1459354","DOI":"10.1145\/1459352.1459354"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Jackson, D.: Alloy: A language and tool for exploring software designs. Commun. ACM 62(9), 66\u201376 (2019), https:\/\/doi.org\/10.1145\/3338843","DOI":"10.1145\/3338843"},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"Jahangirova, G., Clark, D., Harman, M., Tonella, P.: Oasis: Oracle assessment and improvement tool. In: Tip, F., Bodden, E. (eds.) International Symposium on Software Testing and Analysis (ISSTA). pp. 368\u2013371. ACM (2018), https:\/\/doi.org\/10.1145\/3213846.3229503","DOI":"10.1145\/3213846.3229503"},{"key":"7_CR16","doi-asserted-by":"publisher","unstructured":"Leavens, G.T., Baker, A.L., Ruby, C.: Preliminary design of JML: A behavioral interface specification language for Java. ACM SIGSOFT Softw. Eng. Notes 31(3), 1\u201338 (2006). https:\/\/doi.org\/10.1145\/1127878.1127884","DOI":"10.1145\/1127878.1127884"},{"key":"7_CR17","doi-asserted-by":"publisher","unstructured":"Man\u00e8s, V.J.M., Han, H., Han, C., Cha, S.K., Egele, M., Schwartz, E.J., Woo, M.: The art, science, and engineering of fuzzing: A survey. IEEE Trans. Software Eng. 47(11), 2312\u20132331 (2021). https:\/\/doi.org\/10.1109\/TSE.2019.2946563","DOI":"10.1109\/TSE.2019.2946563"},{"key":"7_CR18","doi-asserted-by":"publisher","unstructured":"Marinov, D., Khurshid, S.: Testera: A novel framework for automated testing of Java programs. In: International Conference on Automated Software Engineering (ASE). p.\u00a022. IEEE Computer Society (2001). https:\/\/doi.org\/10.1109\/ASE.2001.989787","DOI":"10.1109\/ASE.2001.989787"},{"key":"7_CR19","doi-asserted-by":"publisher","unstructured":"Meyer, B.: Eiffel: A language and environment for software engineering. J. Syst. Softw. 8(3), 199\u2013246 (1988). https:\/\/doi.org\/10.1016\/0164-1212(88)90022-2","DOI":"10.1016\/0164-1212(88)90022-2"},{"key":"7_CR20","doi-asserted-by":"publisher","unstructured":"Meyer, B.: Class invariants: concepts, problems, solutions. CoRR abs\/1608.07637 (2016). https:\/\/doi.org\/10.48550\/arXiv.1608.07637","DOI":"10.48550\/arXiv.1608.07637"},{"key":"7_CR21","doi-asserted-by":"publisher","unstructured":"Milicevic, A., Misailovic, S., Marinov, D., Khurshid, S.: Korat: A tool for generating structurally complex test inputs. In: International Conference on Software Engineering (ICSE). pp. 771\u2013774. IEEE Computer Society (2007). https:\/\/doi.org\/10.1109\/ICSE.2007.48","DOI":"10.1109\/ICSE.2007.48"},{"key":"7_CR22","doi-asserted-by":"publisher","unstructured":"Miltner, A., Padhi, S., Millstein, T.D., Walker, D.: Data-driven inference of representation invariants. In: Donaldson, A.F., Torlak, E. (eds.) International Conference on Programming Language Design and Implementation (PLDI). pp. 1\u201315. ACM (2020). https:\/\/doi.org\/10.1145\/3385412.3385967","DOI":"10.1145\/3385412.3385967"},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Molina, F., d\u2019Amorim, M., Aguirre, N.: Fuzzing class specifications. In: International Conference on Software Engineering (ICSE). pp. 1008\u20131020. ACM (2022), https:\/\/doi.org\/10.1145\/3510003.3510120","DOI":"10.1145\/3510003.3510120"},{"key":"7_CR24","doi-asserted-by":"crossref","unstructured":"Molina, F., Degiovanni, R., Ponzio, P., Regis, G., Aguirre, N., Frias, M.F.: Training binary classifiers as data structure invariants. In: Atlee, J.M., Bultan, T., Whittle, J. (eds.) International Conference on Software Engineering (ICSE). pp. 759\u2013770. IEEE \/ ACM (2019), https:\/\/doi.org\/10.1109\/ICSE.2019.00084","DOI":"10.1109\/ICSE.2019.00084"},{"key":"7_CR25","doi-asserted-by":"crossref","unstructured":"Molina, F., Ponzio, P., Aguirre, N., Frias, M.F.: Evospex: An evolutionary algorithm for learning postconditions. In: International Conference on Software Engineering (ICSE). pp. 1223\u20131235. IEEE Computer Society (2021), https:\/\/doi.org\/10.1109\/ICSE43902.2021.00112","DOI":"10.1109\/ICSE43902.2021.00112"},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"Pacheco, C., Lahiri, S.K., Ernst, M.D., Ball, T.: Feedback-directed random test generation. In: International Conference on Software Engineering (ICSE). pp. 75\u201384. IEEE Computer Society (2007), https:\/\/doi.org\/10.1109\/ICSE.2007.37","DOI":"10.1109\/ICSE.2007.37"},{"key":"7_CR27","doi-asserted-by":"publisher","unstructured":"Padhi, S., Sharma, R., Millstein, T.D.: Data-driven precondition inference with learned features. In: Krintz, C., Berger, E.D. (eds.) Conference on Programming Language Design and Implementation (PLDI). pp. 42\u201356. ACM (2016). https:\/\/doi.org\/10.1145\/2908080.2908099","DOI":"10.1145\/2908080.2908099"},{"key":"7_CR28","doi-asserted-by":"publisher","unstructured":"Peleg, H., Polikarpova, N.: Perfect is the enemy of good: Best-effort program synthesis. In: Hirschfeld, R., Pape, T. (eds.) European Conference on Object-Oriented Programming (ECOOP). LIPIcs, vol.\u00a0166, pp. 2:1\u20132:30. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ECOOP.2020.2","DOI":"10.4230\/LIPIcs.ECOOP.2020.2"},{"key":"7_CR29","doi-asserted-by":"crossref","unstructured":"Pham, L.H., Sun, J., Le, Q.L.: Compositional verification of heap-manipulating programs through property-guided learning. In: Lin, A.W. (ed.) Asian Symposium on Programming Languages and Systems (APLAS). LNCS, vol. 11893, pp. 405\u2013424. Springer (2019), https:\/\/doi.org\/10.1007\/978-3-030-34175-6_21","DOI":"10.1007\/978-3-030-34175-6_21"},{"key":"7_CR30","doi-asserted-by":"publisher","unstructured":"Pham, L.H., Thi, L.T., Sun, J.: Assertion generation through active learning. In: Duan, Z., Ong, L. (eds.) International Conference on Formal Engineering Methods (ICFEM). LNCS, vol. 10610, pp. 174\u2013191. Springer (2017). https:\/\/doi.org\/10.1007\/978-3-319-68690-5_11","DOI":"10.1007\/978-3-319-68690-5_11"},{"key":"7_CR31","doi-asserted-by":"crossref","unstructured":"Ponzio, P., Bengolea, V.S., Brida, S.G., Scilingo, G., Aguirre, N., Frias, M.F.: On the effect of object redundancy elimination in randomly testing collection classes. In: Galeotti, J.P., Gorla, A. (eds.) International Workshop on Search-Based Software Testing (ICSE). pp. 67\u201370. ACM (2018), https:\/\/doi.org\/10.1145\/3194718.3194724","DOI":"10.1145\/3194718.3194724"},{"key":"7_CR32","doi-asserted-by":"crossref","unstructured":"Pugh, W.W.: Skip lists: A probabilistic alternative to balanced trees. In: Dehne, F.K.H.A., Sack, J., Santoro, N. (eds.) Workshop on Algorithms and Data Structures (WADS). LNCS, vol.\u00a0382, pp. 437\u2013449. Springer (1989), https:\/\/doi.org\/10.1007\/3-540-51542-9_36","DOI":"10.1007\/3-540-51542-9_36"},{"key":"7_CR33","doi-asserted-by":"crossref","unstructured":"Sankaranarayanan, S., Chaudhuri, S., Ivancic, F., Gupta, A.: Dynamic inference of likely data preconditions over predicates by tree learning. In: Ryder, B.G., Zeller, A. (eds.) International Symposium on Software Testing and Analysis (ISSTA). pp. 295\u2013306. ACM (2008), https:\/\/doi.org\/10.1145\/1390630.1390666","DOI":"10.1145\/1390630.1390666"},{"key":"7_CR34","doi-asserted-by":"crossref","unstructured":"Smith, C., Albarghouthi, A.: Program synthesis with equivalence reduction. In: Enea, C., Piskac, R. (eds.) International Conference on Verification, Model Checking and Abstract Interpretation (VMCAI). LNCS, vol. 11388, pp. 24\u201347. Springer (2019), https:\/\/doi.org\/10.1007\/978-3-030-11245-5_2","DOI":"10.1007\/978-3-030-11245-5_2"},{"key":"7_CR35","doi-asserted-by":"crossref","unstructured":"Terragni, V., Jahangirova, G., Tonella, P., Pezz\u00e8, M.: Evolutionary improvement of assertion oracles. In: Devanbu, P., Cohen, M.B., Zimmermann, T. (eds.) Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC\/FSE). pp. 1178\u20131189. ACM (2020), https:\/\/doi.org\/10.1145\/3368089.3409758","DOI":"10.1145\/3368089.3409758"},{"key":"7_CR36","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134\u20131142 (1984), https:\/\/doi.org\/10.1145\/1968.1972","DOI":"10.1145\/1968.1972"},{"key":"7_CR37","unstructured":"Weiss, M.A.: Data structures and algorithm analysis in Java, vol.\u00a02. Addison-Wesley (2007)"},{"key":"7_CR38","doi-asserted-by":"crossref","unstructured":"Zeller, A.: Why programs fail - A guide to systematic debugging, 2nd ed. Academic Press (2009)","DOI":"10.1016\/B978-0-12-374515-6.00006-X"}],"container-title":["Lecture Notes in Computer Science","Fundamental Approaches to Software Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-57259-3_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T13:03:38Z","timestamp":1712322218000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-57259-3_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031572586","9783031572593"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-57259-3_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"6 April 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FASE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Fundamental Approaches to Software Engineering","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 April 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fase2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2024\/conferences\/fase\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"14","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"34% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3-4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}