Crabtree: Rust API Test Synthesis Guided by Coverage and Type
Authors: 
Yoshiki Takashima, Chanhee Cho, Ruben Martins, Limin Jia, Corina S. PăsăreanuAuthors Info & Claims
Article No.: 293, Pages 618 - 647
Abstract
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 unsafe keyword. Rust libraries wrap unsafe 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. 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.
References
[1]
2018. CVE-2018-1000810. https://nvd.nist.gov/vuln/detail/CVE-2018-1000810
[2]
2022. Fuzzing Scripts For Rust libraries with afl.rs. https://github.com/Artisan-Lab/Fuzzing-Scripts original-date: 2021-03-01T05:05:18Z.
[3]
2023. The Rust community’s crate registry. https://crates.io/
[4]
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–758.
[5]
Domagoj Babic, Stefan Bucur, Yaohui Chen, Franjo Ivancic, Tim King, Markus Kusano, Caroline Lemieux, László Szekeres, and Wei Wang. 2019. FUDGE: Fuzz Driver Generation at Scale. In Proceedings of the ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (FSE). ACM, 975–985. https://doi.org/10.1145/3338906.3340456
[6]
Daniel L. Berre and Anne Parrain. 2010. The Sat4j library, release 2.2. J. Satisf. Boolean Model. Comput., 7 (2010), 59–6.
[7]
2021. Handbook of Satisfiability - Second Edition, Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh (Eds.) (Frontiers in Artificial Intelligence and Applications, Vol. 336). IOS Press. isbn:978-1-64368-160-3 https://doi.org/10.3233/FAIA336
[8]
Twain Byrnes, Yoshiki Takashima, and Limin Jia. 2024. Automatically Enforcing Rust Trait Properties. In Verification, Model Checking, and Abstract Interpretation: 25th International Conference, VMCAI 2024, London, United Kingdom, January 15–16, 2024, Proceedings, Part II. Springer-Verlag, Berlin, Heidelberg. 210–223. isbn:978-3-031-50520-1 https://doi.org/10.1007/978-3-031-50521-8_10
[9]
Kees Cook. 2022. Pull request for Rust in Linux 6.1. https://lore.kernel.org/lkml/202210010816.1317F2C@keescook/
[10]
Leonardo de Moura and Nikolaj Bjørner. 2008. Z3: An Efficient SMT Solver. In Tools and Algorithms for the Construction and Analysis of Systems, C. R. Ramakrishnan and Jakob Rehof (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 337–340. isbn:978-3-540-78800-3
[11]
Xavier Denis, Jacques-Henri Jourdan, and Claude Marché. 2022. Creusot: A Foundry for the Deductive Verification of Rust Programs. In Formal Methods and Software Engineering: 23rd International Conference on Formal Engineering Methods, ICFEM 2022, Madrid, Spain, October 24–27, 2022, Proceedings. Springer-Verlag, Berlin, Heidelberg. 90–105. isbn:978-3-031-17243-4 https://doi.org/10.1007/978-3-031-17244-1_6
[12]
K. Dewey, J. Roesch, and B. Hardekopf. 2015. Fuzzing the Rust Typechecker Using CLP (T). In Proceedings of the International Conference on Automated Software Engineering (ASE). IEEE Computer Society, 482–493. https://doi.org/10.1109/ASE.2015.65
[13]
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–612.
[14]
Jonáš Fiala, Shachar Itzhaky, Peter Müller, Nadia Polikarpova, and Ilya Sergey. 2023. Leveraging Rust Types for Program Synthesis. Proc. ACM Program. Lang., 7, PLDI (2023), Article 164, jun, 24 pages. https://doi.org/10.1145/3591278
[15]
Google. 2023. Fuchsia. https://fuchsia.dev/
[16]
Google. 2023. Honggfuzz. https://github.com/google/honggfuzz
[17]
Harrison Green and Thanassis Avgerinos. 2022. GraphFuzz: Library API Fuzzing with Lifetime-Aware Dataflow Graphs. In Proceedings of the 44th International Conference on Software Engineering (ICSE ’22). Association for Computing Machinery, New York, NY, USA. 1070–1081. isbn:9781450392211 https://doi.org/10.1145/3510003.3510228
[18]
Son Ho and Jonathan Protzenko. 2022. Aeneas: Rust verification by functional translation. Proceedings of the ACM on Programming Languages, 6, ICFP (2022), Aug., 116:711–116:741. https://doi.org/10.1145/3547647
[19]
Kyriakos Ispoglou, Daniel Austin, Vishwath Mohan, and Mathias Payer. 2020. FuzzGen: Automatic Fuzzer Generation. In Proceedings of the USENIX Security Symposium. USENIX Association, 2271–2287. isbn:978-1-939133-17-5
[20]
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–224. isbn:9781605587196
[21]
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–592. https://doi.org/10.1109/ASE51524.2021.9678813
[22]
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.
[23]
Andrea Lattuada, Travis Hance, Chanhee Cho, Matthias Brun, Isitha Subasinghe, Yi Zhou, Jon Howell, Bryan Parno, and Chris Hawblitzel. 2023. Verus: Verifying Rust Programs using Linear Ghost Types. Proceedings of the ACM on Programming Languages, 7, OOPSLA1 (2023), April, 85:286–85:315. https://doi.org/10.1145/3586037
[24]
Nico Lehmann, Adam T. Geller, Niki Vazou, and Ranjit Jhala. 2023. Flux: Liquid Types for Rust. Proc. ACM Program. Lang., 7, PLDI (2023), Article 169, jun, 25 pages. https://doi.org/10.1145/3591283
[25]
libFuzzer. [n.d.]. https://github.com/rust-fuzz/libfuzzer
[26]
Nicholas D. Matsakis and Felix S. Klock. 2014. The Rust Language. In Proceedings of the 2014 ACM SIGAda Annual Conference on High Integrity Language Technology (HILT ’14). Association for Computing Machinery, New York, NY, USA. 103–104. isbn:9781450332170 https://doi.org/10.1145/2663171.2663188
[27]
Yusuke Matsushita, Xavier Denis, Jacques-Henri Jourdan, and Derek Dreyer. 2022. RustHornBelt: a semantic foundation for functional verification of Rust programs with unsafe code. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2022). Association for Computing Machinery, New York, NY, USA. 841–856. isbn:9781450392655 https://doi.org/10.1145/3519939.3523704
[28]
Mozilla. 2020. Oxidation. https://wiki.mozilla.org/Oxidation
[29]
Mozilla. 2021. grcov v0.7.1. https://github.com/mozilla/grcov
[30]
Yannic Noller, Rody Kersten, and Corina S. Pasareanu. 2019. Badger: Complexity Analysis with Fuzzing and Symbolic Execution. In Software Engineering and Software Management, SE/SWM 2019, Stuttgart, Germany, February 18-22, 2019, Steffen Becker, Ivan Bogicevic, Georg Herzwurm, and Stefan Wagner (Eds.) (LNI, Vol. P-292). GI, 65–66. https://doi.org/10.18420/se2019-16
[31]
Carlos Pacheco, Shuvendu Lahiri, Michael D. Ernst, and Thomas Ball. 2006. Feedback-directed Random Test Generation. Massachusetts Institute of Technology, 14. https://www.microsoft.com/en-us/research/publication/feedback-directed-random-test-generation/
[32]
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–779.
[33]
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
[34]
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–407. isbn:978-3-030-45237-7
[35]
Rust Contributors. [n.d.]. What is rustdoc? - The rustdoc book. https://doc.rust-lang.org/rustdoc/what-is-rustdoc.html
[36]
Rust for Linux. 2023. https://rust-for-linux.com/
[37]
Kosta Serebryany. 2016. Continuous Fuzzing with libFuzzer and AddressSanitizer. In IEEE Cybersecurity Development, SecDev 2016, Boston, MA, USA, November 3-4, 2016. IEEE Computer Society, 157. https://doi.org/10.1109/SecDev.2016.043
[38]
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.
[39]
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
[40]
Yoshiki Takashima. 2023. PropProof: Free Model-Checking Harnesses from PBT. In Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2023). Association for Computing Machinery, New York, NY, USA. 1903–1913. isbn:9798400703270 https://doi.org/10.1145/3611643.3613863
[41]
Yoshiki Takashima, Ruben Martins, Limin Jia, and Corina S. Păsăreanu. 2021. SyRust: Automatic Testing of Rust Libraries with Semantic-Aware Program Synthesis. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2021). Association for Computing Machinery, New York, NY, USA. 899–913. isbn:9781450383912 https://doi.org/10.1145/3453483.3454084
[42]
The Rust Developers. [n.d.]. Miri. https://github.com/rust-lang/miri
[43]
Vsevolod Tymofyeyev and Gordon Fraser. 2022. Search-Based Test Suite Generation for Rust. In Search-Based Software Engineering, Mike Papadakis and Silvia Regina Vergilio (Eds.). Springer International Publishing, Cham. 3–18. isbn:978-3-031-21251-2
[44]
Alexa VanHattum, Daniel Schwartz-Narbonne, Nathan Chong, and Adrian Sampson. 2022. Verifying Dynamic Trait Objects in Rust. In Proceedings of the 44th International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP ’22). Association for Computing Machinery, New York, NY, USA. 321–330. isbn:9781450392266 https://doi.org/10.1145/3510457.3513031
[45]
Willem Visser, Corina S. Pasareanu, and Sarfraz Khurshid. 2004. Test input generation with java PathFinder. In Proceedings of the ACM/SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2004, Boston, Massachusetts, USA, July 11-14, 2004, George S. Avrunin and Gregg Rothermel (Eds.). ACM, 97–107. https://doi.org/10.1145/1007512.1007526
[46]
Fabian Wolff, Aurel Bílý, Christoph Matheja, Peter Müller, and Alexander J. Summers. 2021. Modular specification and verification of closures in Rust. Proceedings of the ACM on Programming Languages, 5, OOPSLA (2021), Oct., 145:1–145:29. https://doi.org/10.1145/3485522
[47]
Hui Xu, Zhuangbin Chen, Mingshen Sun, Yangfan Zhou, and Michael R. Lyu. 2022. Memory-Safety Challenge Considered Solved? An In-Depth Study with All Rust CVEs. ACM Trans. Softw. Eng. Methodol., 31, 1 (2022), 3:1–3:25. https://doi.org/10.1145/3466642
[48]
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.
[49]
Michał Zalewski. [n.d.]. American Fuzzy Lop. https://lcamtuf.coredump.cx/afl/
[50]
Yehong Zhang, Jun Wu, and Hui Xu. 2023. Fuzz Driver Synthesis for Rust Generic APIs. arxiv:2312.10676 arXiv:2312.10676 [cs].
Index Terms
- Crabtree: Rust API Test Synthesis Guided by Coverage and Type
Recommendations
SyRust: automatic testing of Rust libraries with semantic-aware program synthesis
PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and ImplementationRust’s type system ensures the safety of Rust programs; however, programmers can side-step some of the strict typing rules by using the unsafe keyword. A common use of unsafe Rust is by libraries. Bugs in these libraries undermine the safety of the ...
Carving UI Tests to Generate API Tests and API Specification
ICSE '23: Proceedings of the 45th International Conference on Software EngineeringModern web applications make extensive use of API calls to update the UI state in response to user events or server-side changes. For such applications, API-level testing can play an important role, in-between unit-level testing and UI-level (or end-...
RULF: rust library fuzzing via API dependency graph traversal
ASE '21: Proceedings of the 36th IEEE/ACM International Conference on Automated Software EngineeringRobustness is a key concern for Rust library development because Rust promises no risks of undefined behaviors if developers use safe APIs only. Fuzzing is a practical approach for examining the robustness of programs. However, existing fuzzing tools ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2024
2691 pages
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 October 2024
Published in PACMPL Volume 8, Issue OOPSLA2
Check for updates
Badges
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Science Foundation
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 191Total Downloads
- Downloads (Last 12 months)191
- Downloads (Last 6 weeks)171
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in