research-article

Open access

SyRust: automatic testing of Rust libraries with semantic-aware program synthesis

Authors:

Yoshiki Takashima,

Corina S. PăsăreanuAuthors Info & Claims

PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

Pages 899 - 913

https://doi.org/10.1145/3453483.3454084

Published: 18 June 2021 Publication History

Abstract

Rust’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 entire Rust program. Therefore, it is crucial to thoroughly test library APIs to rule out bugs. Unfortunately, such testing relies on programmers to manually construct test cases, which is an inefficient and ineffective process.

The goal of this paper is to develop a methodology for automatically generating Rust programs to effectively test Rust library APIs. The main challenge is to synthesize well-typed Rust programs to account for proper chaining of API calls and Rust’s ownership type system and polymorphic types. We develop a program synthesis technique for Rust library API testing, which relies on a novel logical encoding of typing constraints from Rust’s ownership type system. We implement SyRust, a testing framework for Rust libraries that automatically synthesizes semantically valid test cases. Our experiments on 30 popular open-source Rust libraries found 4 new bugs.

References

[1]

2018. Built In Rust. https://www.rust-lang.org/what/

[2]

2018. CVE-2018-1000810. https://nvd.nist.gov/vuln/detail/CVE-2018-1000810

[3]

2020. Built In Rust. https://doc.rust-lang.org/nomicon/lifetime-elision.html

[4]

2020. Rust’s Unsafe Code Guidelines Reference. https://rust-lang.github.io/unsafe-code-guidelines/

[5]

2020. Trait and lifetime bounds. https://doc.rust-lang.org/reference/trait-bounds.html

[6]

2020. Undefined Behavior in bounded channel. https://github.com/RustSec/advisory-db/blob/main/crates/crossbeam-channel/RUSTSEC-2020-0052.md

[7]

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.

Digital Library

[8]

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

Digital Library

[9]

Suguman Bansal, Kedar S. Namjoshi, and Yaniv Sa’ar. 2018. Synthesis of Asynchronous Reactive Programs from Temporal Specifications. In Proceedings of the International Conference on Computer Aided Verification (CAV). Springer International Publishing, 367–385. isbn:978-3-319-96145-3

[10]

D. L. Berre and Anne Parrain. 2010. The Sat4j library, release 2.2. J. Satisf. Boolean Model. Comput., 7 (2010), 59–6.

[11]

D.L. Bowen, L.H. Byrd, and William Clocksin. 1983. A portable Prolog compiler. In D.A.I. research paper. 9.

[12]

Christoph Csallner and Yannis Smaragdakis. 2004. JCrasher: An Automatic Robustness Tester for Java. Journal of Software: Practice and Experience (SPE), 34, 11 (2004), Sept., 1025–1050. issn:0038-0644 https://doi.org/10.1002/spe.602

Digital Library

[13]

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

Digital Library

[14]

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.

[15]

Zheng Guo, Michael James, David Justo, Jiaxiao Zhou, Ziteng Wang, Ranjit Jhala, and Nadia Polikarpova. 2019. Program Synthesis by Type-Guided Abstraction Refinement. In Proceedings of the ACM SIGPLAN Symposium on Principles of Programming Languages (POPL). ACM, 12:1–12:28. https://doi.org/10.1145/3371080

Digital Library

[16]

HyungSeok Han, DongHyeon Oh, and Sang Kil Cha. 2019. CodeAlchemist: Semantics-Aware Code Generation to Find Vulnerabilities in JavaScript Engines. In Proceedings of the Network and Distributed System Security Symposium (NDSS). The Internet Society.

[17]

Christian Holler, Kim Herzig, and Andreas Zeller. 2012. Fuzzing with Code Fragments. In Proceedings of the USENIX Security Symposium. USENIX Association, USA. 445–458.

[18]

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

[19]

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

Digital Library

[20]

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.

Digital Library

[21]

Ralf Jung, Jacques-Henri Jourdan, Robbert Krebbers, and Derek Dreyer. 2018. RustBelt: Securing the Foundations of the Rust Programming Language. In Proceedings of the ACM SIGPLAN Symposium on Principles of Programming Languages (POPL). ACM, Article 66, 34 pages. https://doi.org/10.1145/3158154

Digital Library

[22]

Y. Kim, Y. Kim, Taeksu Kim, Gunwoo Lee, Y. Jang, and M. Kim. 2013. Automated unit testing of large industrial embedded software using concolic testing. In Proceedings of the International Conference on Automated Software Engineering (ASE). IEEE, 519–528.

[23]

Linux Test Project. 2020. lcov 1.15. https://github.com/linux-test-project/lcov

[24]

L. Ma, C. Artho, C. Zhang, H. Sato, J. Gmeiner, and R. Ramler. 2015. GRT: An Automated Test Generator Using Orchestrated Program Analysis. In Proceedings of the International Conference on Automated Software Engineering (ASE). IEEE Computer Society, 842–847.

[25]

Mozilla. 2021. grcov v0.7.1. https://github.com/mozilla/grcov

[26]

Scott Olson. [n.d.]. Miri. https://github.com/rust-lang/miri

[27]

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/

[28]

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.

Digital Library

[29]

Eric Reed. 2015. Patina: A formalization of the Rust programming language. University of Washington.

[30]

Rust Foundation. 2020. cargo 1.47.0.

[31]

Takehide Soh, Daniel Le Berre, Stéphanie Roussel, Mutsunori Banbara, and Naoyuki Tamura. 2014. Incremental SAT-Based Method with Native Boolean Cardinality Handling for the Hamiltonian Cycle Problem. In Proceedings of the European Conference on Logics in Artificial Intelligence (JELIA). 8761, Springer, 684–693.

Digital Library

[32]

Yoshiki Takashima, Ruben Martins, Limin Jia, and Corina Pasareanu. 2021. SyRust: Automatic Testing of Rust Libraries with Semantic-Aware Program Synthesis–Technical Report. Carnegie Mellon University. https://doi.org/10.1184/R1/14356949

[33]

O. Tange. 2011. GNU Parallel - The Command-Line Power Tool. ;login: The USENIX Magazine, 36, 1 (2011), Feb, 42–47. http://www.gnu.org/s/parallel

[34]

John Toman, Stuart Pernsteiner, and Emina Torlak. 2015. CRUST: A Bounded Verifier for Rust. In Proceedings of the International Conference on Automated Software Engineering (ASE). IEEE Press, 6 pages. isbn:9781509000241

Digital Library

[35]

F. Wang, F. Song, M. Zhang, X. Zhu, and J. Zhang. 2018. KRust: A Formal Executable Semantics of Rust. In Proceedings of the International Symposium on Theoretical Aspects of Software Engineering (TASE). IEEE Computer Society, 44–51.

[36]

Aaron Weiss, Daniel Patterson, Nicholas D. Matsakis, and Amal Ahmed. 2019. Oxide: The Essence of Rust. CoRR, abs/1903.00982 (2019), arxiv:1903.00982. arxiv:1903.00982

[37]

Maverick Woo, Sang Kil Cha, Samantha Gottlieb, and David Brumley. 2013. Scheduling Black-Box Mutational Fuzzing. In Proceedings of the ACM SIGSAC Conference on Computer & Communications Security (CCS). Association for Computing Machinery, 511–522. isbn:9781450324779

Digital Library

[38]

Hui Xu, Zhuangbin Chen, Mingshen Sun, and Yangfan Zhou. 2020. Memory-Safety Challenge Considered Solved? An Empirical Study with All Rust CVEs. arxiv:2003.03296. arxiv:2003.03296

[39]

Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. 2011. Finding and understanding bugs in C compilers. In Proceedings of the ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI). ACM, 283–294.

Digital Library

[40]

Andreas Zeller, Rahul Gopinath, Marcel Böhme, Gordon Fraser, and Christian Holler. 2019. Fuzzing APIs. In The Fuzzing Book. Saarland University. https://www.fuzzingbook.org/html/APIFuzzer.html Retrieved 2019-12-17 16:45:28+01:00.

Cited By

Hassnain MStanford CFilkov VRay BZhou M(2024)Counterexamples in Safe RustProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering Workshops10.1145/3691621.3694943(128-135)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691621.3694943
Takashima YCho CMartins RJia LPăsăreanu C(2024)Crabtree: Rust API Test Synthesis Guided by Coverage and TypeProceedings of the ACM on Programming Languages10.1145/36897338:OOPSLA2(618-647)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689733
Yin XFeng YShi QLiu ZLiu HXu BChristakis MPradel M(2024)FRIES: Fuzzing Rust Library Interactions via Efficient Ecosystem-Guided Target GenerationProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680348(1137-1148)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680348
Show More Cited By

Index Terms

SyRust: automatic testing of Rust libraries with semantic-aware program synthesis
1. Security and privacy
  1. Software and application security
    1. Software security engineering
2. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
      1. Semantics
    2. Software maintenance tools
  2. Software organization and properties
    1. Extra-functional properties
      1. Software reliability
      2. Software safety

Recommendations

How do programmers use unsafe rust?

Rust’s ownership type system enforces a strict discipline on how memory locations are accessed and shared. This discipline allows the compiler to statically prevent memory errors, data races, inadvertent side effects through aliasing, and other errors ...
Understanding memory and thread safety practices and issues in real-world Rust programs
PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation

Rust is a young programming language designed for systems software development. It aims to provide safety guarantees like high-level languages and performance efficiency like low-level languages. The core design of Rust is a set of strict safety rules ...
Crabtree: Rust API Test Synthesis Guided by Coverage and Type

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

June 2021

1341 pages

ISBN:9781450383912

DOI:10.1145/3453483

General Chair:
Stephen N. Freund
Williams College, USA
,
Program Chair:
Eran Yahav
Technion, Israel

Copyright © 2021 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

PLDI '21

Sponsor:

SIGPLAN

PLDI '21: 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

June 20 - 25, 2021

Virtual, Canada

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
2,702
Total Downloads

Downloads (Last 12 months)584
Downloads (Last 6 weeks)74

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hassnain MStanford CFilkov VRay BZhou M(2024)Counterexamples in Safe RustProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering Workshops10.1145/3691621.3694943(128-135)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691621.3694943
Takashima YCho CMartins RJia LPăsăreanu C(2024)Crabtree: Rust API Test Synthesis Guided by Coverage and TypeProceedings of the ACM on Programming Languages10.1145/36897338:OOPSLA2(618-647)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689733
Yin XFeng YShi QLiu ZLiu HXu BChristakis MPradel M(2024)FRIES: Fuzzing Rust Library Interactions via Efficient Ecosystem-Guided Target GenerationProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680348(1137-1148)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680348
Sotiropoulos TChaliasos SSu Z(2024)API-Driven Program Synthesis for Testing Static Typing ImplementationsProceedings of the ACM on Programming Languages10.1145/36329048:POPL(1850-1881)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632904
Qin BChen YLiu HZhang HWen QSong LZhang Y(2024)Understanding and Detecting Real-World Safety Issues in RustIEEE Transactions on Software Engineering10.1109/TSE.2024.338039350:6(1306-1324)Online publication date: 25-Mar-2024
https://dl.acm.org/doi/10.1109/TSE.2024.3380393
Fiala JItzhaky SMüller PPolikarpova NSergey I(2023)Leveraging Rust Types for Program SynthesisProceedings of the ACM on Programming Languages10.1145/35912787:PLDI(1414-1437)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591278
Guo YXiao XLin YLi HWu XZhou T(2023)Fuzz Testing for Rust Library Functions2023 IEEE 22nd International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)10.1109/TrustCom60117.2023.00139(990-997)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TrustCom60117.2023.00139
Blair WMambretti AArshad SWeissbacher MRobertson WKirda EEgele M(2022)HotFuzz: Discovering Temporal and Spatial Denial-of-Service Vulnerabilities Through Guided Micro-FuzzingACM Transactions on Privacy and Security10.1145/353218425:4(1-35)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3532184
Hu SHua BWang Y(2022)Comprehensiveness, Automation and Lifecycle: A New Perspective for Rust Security2022 IEEE 22nd International Conference on Software Quality, Reliability and Security (QRS)10.1109/QRS57517.2022.00102(982-991)Online publication date: Dec-2022
https://doi.org/10.1109/QRS57517.2022.00102
Tymofyeyev VFraser G(2022)Search-Based Test Suite Generation for RustSearch-Based Software Engineering10.1007/978-3-031-21251-2_1(3-18)Online publication date: 17-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-21251-2_1

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents