{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T02:56:21Z","timestamp":1775271381234,"version":"3.50.1"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T00:00:00Z","timestamp":1728345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1901136"],"award-info":[{"award-number":["1901136"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,10,8]]},"abstract":"<jats:p>\n                    Rust type system constrains pointer operations, preventing bugs such as use-after-free. However, these constraints may be too strict for programming tasks such as implementing cyclic data structures. For such tasks, programmers can temporarily suspend checks using the\n                    <jats:monospace>unsafe<\/jats:monospace>\n                    keyword. Rust libraries wrap\n                    <jats:monospace>unsafe<\/jats:monospace>\n                    code blocks and expose higher-level APIs. They need to be extensively tested to uncover memory-safety bugs that can only be triggered by unexpected API call sequences or inputs. While prior works have attempted to automatically test Rust library APIs, they fail to test APIs with common Rust features, such as polymorphism, traits, and higher-order functions, or they have scalability issues and can only generate tests for a small number of combined APIs.\n                  <\/jats:p>\n                  <jats:p>We propose Crabtree, a testing tool for Rust library APIs that can automatically synthesize test cases with native support for Rust traits and higher-order functions. Our tool improves upon the test synthesis algorithms of prior works by combining synthesis and fuzzing through a coverage- and type-guided search algorithm that intelligently grows test programs and input corpus towards testing more code. To the best of our knowledge, our tool is the first to generate well-typed tests for libraries that make use of higher-order trait functions. Evaluation of Crabtree on 30 libraries found four previously unreported memory-safety bugs, all of which were accepted by the respective authors.<\/jats:p>","DOI":"10.1145\/3689733","type":"journal-article","created":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T03:23:04Z","timestamp":1728357784000},"page":"618-647","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Crabtree: Rust API Test Synthesis Guided by Coverage and Type"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9274-8953","authenticated-orcid":false,"given":"Yoshiki","family":"Takashima","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-6620-9070","authenticated-orcid":false,"given":"Chanhee","family":"Cho","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1525-1382","authenticated-orcid":false,"given":"Ruben","family":"Martins","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8160-349X","authenticated-orcid":false,"given":"Limin","family":"Jia","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5579-6961","authenticated-orcid":false,"given":"Corina S.","family":"P\u0103s\u0103reanu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,10,8]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"2018. CVE-2018-1000810. https:\/\/nvd.nist.gov\/vuln\/detail\/CVE-2018-1000810"},{"key":"e_1_3_1_3_2","unstructured":"2022. Fuzzing Scripts For Rust libraries with afl.rs. https:\/\/github.com\/Artisan-Lab\/Fuzzing-Scripts original-date: 2021-03-01T05:05:18Z."},{"key":"e_1_3_1_4_2","unstructured":"2023. The Rust community\u2019s crate registry. https:\/\/crates.io\/"},{"key":"e_1_3_1_5_2","first-page":"748","volume-title":"Proceedings of the International Conference on Software Engineering (ICSE)","author":"Atlidakis Vaggelis","year":"2019","unstructured":"Vaggelis Atlidakis, Patrice Godefroid, and Marina Polishchuk. 2019. RESTler: Stateful REST API Fuzzing. In Proceedings of the International Conference on Software Engineering (ICSE). IEEE Press, 748\u2013758."},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3340456"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.3233\/SAT190075"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.3233\/FAIA336"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-50521-8_10"},{"key":"e_1_3_1_10_2","unstructured":"Kees Cook. 2022. Pull request for Rust in Linux 6.1. https:\/\/lore.kernel.org\/lkml\/202210010816.1317F2C@keescook\/"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/1792734.1792766"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-17244-1_6"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2015.65"},{"key":"e_1_3_1_14_2","first-page":"599","volume-title":"Proceedings of the ACM SIGPLAN Symposium on Principles of Programming Languages (POPL)","author":"Feng Yu","year":"2017","unstructured":"Yu Feng, Ruben Martins, Yuepeng Wang, Isil Dillig, and Thomas W. Reps. 2017. Component-based synthesis for complex APIs. In Proceedings of the ACM SIGPLAN Symposium on Principles of Programming Languages (POPL). ACM, 599\u2013612."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591278"},{"key":"e_1_3_1_16_2","unstructured":"Google. 2023. Fuchsia. https:\/\/fuchsia.dev\/"},{"key":"e_1_3_1_17_2","unstructured":"Google. 2023. Honggfuzz. https:\/\/github.com\/google\/honggfuzz"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3510003.3510228"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3547647"},{"key":"e_1_3_1_20_2","first-page":"2271","volume-title":"Proceedings of the USENIX Security Symposium","author":"Ispoglou Kyriakos","year":"2020","unstructured":"Kyriakos Ispoglou, Daniel Austin, Vishwath Mohan, and Mathias Payer. 2020. FuzzGen: Automatic Fuzzer Generation. In Proceedings of the USENIX Security Symposium. USENIX Association, 2271\u20132287."},{"key":"e_1_3_1_21_2","first-page":"215","volume-title":"Proceedings of the International Conference on Software Engineering (ICSE)","author":"Jha Susmit","year":"2010","unstructured":"Susmit Jha, Sumit Gulwani, Sanjit A. Seshia, and Ashish Tiwari. 2010. Oracle-Guided Component-Based Program Synthesis. In Proceedings of the International Conference on Software Engineering (ICSE). Association for Computing Machinery, 215\u2013224."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","unstructured":"Jianfeng Jiang Hui Xu and Yangfan Zhou. 2021. RULF: Rust Library Fuzzing via API Dependency Graph Traversal. In 2021 36th IEEE\/ACM International Conference on Automated Software Engineering (ASE). 581\u2013592. https:\/\/doi.org\/10.1109\/ASE51524.2021.9678813 10.1109\/ASE51524.2021.9678813","DOI":"10.1109\/ASE51524.2021.9678813"},{"key":"e_1_3_1_23_2","first-page":"32","volume-title":"Proceedings of the ACM SIGPLAN Symposium on Principles of Programming Languages (POPL)","author":"Jung Ralf","year":"2020","unstructured":"Ralf Jung, Hoang-Hai Dang, Jeehoon Kang, and Derek Dreyer. 2020. Stacked Borrows: An Aliasing Model for Rust. In Proceedings of the ACM SIGPLAN Symposium on Principles of Programming Languages (POPL). ACM, Article 41, 32 pages."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3586037"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591283"},{"key":"e_1_3_1_26_2","unstructured":"libFuzzer. [n.d.]. https:\/\/github.com\/rust-fuzz\/libfuzzer"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2663171.2663188"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523704"},{"key":"e_1_3_1_29_2","unstructured":"Mozilla. 2020. Oxidation. https:\/\/wiki.mozilla.org\/Oxidation"},{"key":"e_1_3_1_30_2","unstructured":"Mozilla. 2021. grcov v0.7.1. https:\/\/github.com\/mozilla\/grcov"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.18420\/se2019-16"},{"key":"e_1_3_1_32_2","first-page":"14","volume-title":"Feedback-directed Random Test Generation. Technical Report MSR-TR-2006-125","author":"Pacheco Carlos","year":"2006","unstructured":"Carlos Pacheco, Shuvendu Lahiri, Michael D. Ernst, and Thomas Ball. 2006. Feedback-directed Random Test Generation. Technical Report MSR-TR-2006-125. Massachusetts Institute of Technology. 14 pages. https:\/\/www.microsoft.com\/en-us\/research\/publication\/feedback-directed-random-test-generation\/"},{"key":"e_1_3_1_33_2","first-page":"763","volume-title":"Proceedings of the ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI)","author":"Qin Boqin","year":"2020","unstructured":"Boqin Qin, Yilun Chen, Zeming Yu, Linhai Song, and Yiying Zhang. 2020. Understanding memory and thread safety practices and issues in real-world Rust programs. In Proceedings of the ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI). ACM, 763\u2013779."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","unstructured":"Alastair Reid Luke Church Shaked Flur Sarah de Haas Maritza Johnson and Ben Laurie. 2020. Towards making formal methods normal: meeting developers where they are. https:\/\/doi.org\/10.48550\/arXiv.2010.16345 10.48550\/arXiv.2010.16345","DOI":"10.48550\/arXiv.2010.16345"},{"key":"e_1_3_1_35_2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/978-3-030-45237-7_29","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"Rocha Herbert","year":"2020","unstructured":"Herbert Rocha, Rafael Menezes, Lucas C. Cordeiro, and Raimundo Barreto. 2020. Map2Check: Using Symbolic Execution and Fuzzing. In Tools and Algorithms for the Construction and Analysis of Systems, Armin Biere and David Parker (Eds.). Springer International Publishing, Cham, 403\u2013407."},{"key":"e_1_3_1_36_2","unstructured":"Rust Contributors. [n.d.]. What is rustdoc? - The rustdoc book. https:\/\/doc.rust-lang.org\/rustdoc\/what-is-rustdoc.html"},{"key":"e_1_3_1_37_2","unstructured":"Rust for Linux. 2023. . https:\/\/rust-for-linux.com\/"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/SecDev.2016.043"},{"key":"e_1_3_1_39_2","volume-title":"Proceedings of the ACM SIGPLAN Symposium on Principles of Programming Languages (POPL)","author":"Sotiropoulos Thodoris","year":"2024","unstructured":"Thodoris Sotiropoulos, Stefanos Chaliasos, and Zhendong Su. 2024. API-driven Program Synthesis for Testing Static Typing Implementations. In Proceedings of the ACM SIGPLAN Symposium on Principles of Programming Languages (POPL). Association for Computing Machinery."},{"key":"e_1_3_1_40_2","volume-title":"23rd Annual Network and Distributed System Security Symposium, NDSS 2016, San Diego, California, USA, February 21-24, 2016","author":"Stephens Nick","year":"2016","unstructured":"Nick Stephens, John Grosen, Christopher Salls, Andrew Dutcher, Ruoyu Wang, Jacopo Corbetta, Yan Shoshitaishvili, Christopher Kruegel, and Giovanni Vigna. 2016. Driller: Augmenting Fuzzing Through Selective Symbolic Execution. In 23rd Annual Network and Distributed System Security Symposium, NDSS 2016, San Diego, California, USA, February 21-24, 2016. The Internet Society. http:\/\/wp.internetsociety.org\/ndss\/wp-content\/uploads\/sites\/25\/2017\/09\/driller-augmenting-fuzzing-through-selective-symbolic-execution.pdf"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3611643.3613863"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454084"},{"key":"e_1_3_1_43_2","unstructured":"The Mutants.rs Authors. 2022. Mutants.rs. https:\/\/github.com\/sourcefrog\/cargo-mutants"},{"key":"e_1_3_1_44_2","unstructured":"The Rust Developers. [n.d.]. Miri. https:\/\/github.com\/rust-lang\/miri"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-21251-2_1"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3510457.3513031"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007512.1007526"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485522"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3466642"},{"key":"e_1_3_1_50_2","unstructured":"Zhiwu Xu Bin Zhang Bohao Wu Shengchao Qin Cheng Wen and Mengda He. 2024. RPG: Rust Library Fuzzing with Pool-based Fuzz Target Generation and Generic Support. ICSE (2024)."},{"key":"e_1_3_1_51_2","unstructured":"Michal Zalewski. [n.d.]. American Fuzzy Lop. https:\/\/lcamtuf.coredump.cx\/afl\/"},{"key":"e_1_3_1_52_2","unstructured":"Yehong Zhang Jun Wu and Hui Xu. 2023. Fuzz Driver Synthesis for Rust Generic APIs. http:\/\/arxiv.org\/abs\/2312.10676 arXiv:2312.10676 [cs]."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689733","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3689733","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T09:06:36Z","timestamp":1770195996000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689733"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,8]]},"references-count":51,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2024,10,8]]}},"alternative-id":["10.1145\/3689733"],"URL":"https:\/\/doi.org\/10.1145\/3689733","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,8]]},"assertion":[{"value":"2024-04-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}