Rustlantis: Randomized Differential Testing of the Rust Compiler
Authors: 
Qian Wang, Ralf JungAuthors Info & Claims
Article No.: 340, Pages 1955 - 1981
Abstract
Compilers are at the core of all computer architecture. Their middle-end and back-end are full of subtle code that is easy to get wrong. At the same time, the consequences of compiler bugs can be severe. Therefore, it is important that we develop techniques to increase our confidence in compiler correctness, and to help find the bugs that inevitably happen. One promising such technique that has successfully found many compiler bugs in the past is randomized differential testing, a fuzzing approach whereby the same program is executed with different compilers or different compiler settings to detect any unexpected differences in behavior. We present Rustlantis, the first fuzzer for the Rust programming language that is able to find new correctness bugs in the official Rust compiler. To avoid having to deal with Rust’s strict type and borrow checker, Rustlantis directly generates MIR, the central IR of the Rust compiler for optimizations. The program generation strategy of Rustlantis is a combination of statically tracking the state of the program, obscuring the program state for the compiler, and decoy blocks to lead optimizations astray. This has allowed us to identify 22 previously unknown bugs in the Rust compiler, most of which have been fixed.
References
[1]
Bytecode Alliance. 2018. Cranelift Code Generator. https://github.com/bytecodealliance/wasmtime/tree/main/cranelift
[2]
Rust Fuzzing Authority. 2017. rust-fuzz. https://github.com/rust-fuzz/trophy-case
[3]
Marcel Böhme, László Szekeres, and Jonathan Metzman. 2022. On the Reliability of Coverage-Based Fuzzer Benchmarking. In Proceedings of the 44th International Conference on Software Engineering (ICSE’22). http://seclab.cs.stonybrook.edu/lszekeres/Papers/ICSE22.pdf
[4]
Junjie Chen, Jibesh Patra, Michael Pradel, Yingfei Xiong, Hongyu Zhang, Dan Hao, and Lu Zhang. 2020. A Survey of Compiler Testing. ACM Comput. Surv., 53, 1 (2020), Article 4, 2, 36 pages. issn:0360-0300 https://doi.org/10.1145/3363562
[5]
Chris Cummins, Pavlos Petoumenos, Alastair Murray, and Hugh Leather. 2018. Compiler fuzzing through deep learning. In Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2018, Amsterdam, The Netherlands, July 16-21, 2018, Frank Tip and Eric Bodden (Eds.). ACM, 95–105. https://doi.org/10.1145/3213846.3213848
[6]
Kyle Dewey, Jared Roesch, and Ben Hardekopf. 2015. Fuzzing the Rust Typechecker Using CLP (T). In 2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE). 482–493. https://doi.org/10.1109/ASE.2015.65
[7]
Eric Eide and John Regehr. 2008. Volatiles are miscompiled, and what to do about it. In Proceedings of the 8th ACM & IEEE International conference on Embedded software, EMSOFT 2008, Atlanta, GA, USA, October 19-24, 2008, Luca de Alfaro and Jens Palsberg (Eds.). ACM, 255–264. https://doi.org/10.1145/1450058.1450093
[8]
Karine Even-Mendoza, Cristian Cadar, and Alastair F. Donaldson. 2022. CsmithEdge: more effective compiler testing by handling undefined behaviour less conservatively. Empir. Softw. Eng., 27, 6 (2022), 129. https://doi.org/10.1007/S10664-022-10146-1
[9]
Diego Treviño Ferrer. 2019. LLVM-Reduce for testcase reduction. https://llvm.org/devmtg/2019-10/talk-abstracts.html##tech22 2019 LLVM Developers’ Meeting
[10]
Alex Groce, Chaoqiang Zhang, Eric Eide, Yang Chen, and John Regehr. 2012. Swarm testing. In ISSTA. ACM, 78–88.
[11]
Bevin Hansson. 2015. Random Testing of Code Generation in Compilers. Master’s thesis. Royal Institute of Technology, Stockholm. https://robcasloz.github.io/teaching/BevinHansson_2015.pdf
[12]
Ralf Jung, Hoang-Hai Dang, Jeehoon Kang, and Derek Dreyer. 2019. Stacked borrows: an aliasing model for Rust. Proc. ACM Program. Lang., 4, POPL (2019), Article 41, dec, 32 pages. https://doi.org/10.1145/3371109
[13]
Matthias Krüger. 2020. icemaker. https://github.com/matthiaskrgr/icemaker
[14]
Ramana Kumar, Magnus O. Myreen, Michael Norrish, and Scott Owens. 2014. CakeML: a verified implementation of ML. In The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’14, San Diego, CA, USA, January 20-21, 2014, Suresh Jagannathan and Peter Sewell (Eds.). ACM, 179–192. https://doi.org/10.1145/2535838.2535841
[15]
Vu Le, Mehrdad Afshari, and Zhendong Su. 2014. Compiler Validation via Equivalence modulo Inputs. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’14). Association for Computing Machinery, New York, NY, USA. 216–226. isbn:9781450327848 https://doi.org/10.1145/2594291.2594334
[16]
Vu Le, Chengnian Sun, and Zhendong Su. 2015. Finding deep compiler bugs via guided stochastic program mutation. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2015, part of SPLASH 2015, Pittsburgh, PA, USA, October 25-30, 2015, Jonathan Aldrich and Patrick Eugster (Eds.). ACM, 386–399. https://doi.org/10.1145/2814270.2814319
[17]
Xavier Leroy. 2009. A formally verified compiler back-end. JAR, 43, 4 (2009), 363–446. https://doi.org/10.1007/s10817-009-9155-4
[18]
Xavier Leroy. 2023. The CompCert C verified compiler - Documentation and user’s manual. https://compcert.org/man/manual.pdf
[19]
Xiao Liu, Xiaoting Li, Rupesh Prajapati, and Dinghao Wu. 2019. DeepFuzz: Automatic Generation of Syntax Valid C Programs for Fuzz Testing. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019. AAAI Press, 1044–1051. https://doi.org/10.1609/AAAI.V33I01.33011044
[20]
Vsevolod Livinskii, Dmitry Babokin, and John Regehr. 2020. Random testing for C and C++ compilers with YARPGen. Proc. ACM Program. Lang., 4, OOPSLA (2020), Article 196, nov, 25 pages. https://doi.org/10.1145/3428264
[21]
Michaël Marcozzi, Qiyi Tang, Alastair F. Donaldson, and Cristian Cadar. 2019. Compiler fuzzing: how much does it matter? Proc. ACM Program. Lang., 3, OOPSLA (2019), Article 155, oct, 29 pages. https://doi.org/10.1145/3360581
[22]
William M McKeeman. 1998. Differential testing for software. Digital Technical Journal, 10, 1 (1998), 100–107.
[23]
Eriko Nagai, Atsushi Hashimoto, and Nagisa Ishiura. 2014. Reinforcing Random Testing of Arithmetic Optimization of C Compilers by Scaling up Size and Number of Expressions. IPSJ Trans. Syst. LSI Des. Methodol., 7 (2014), 91–100. https://doi.org/10.2197/IPSJTSLDM.7.91
[24]
Georg Ofenbeck, Tiark Rompf, and Markus Püschel. 2016. RandIR: differential testing for embedded compilers. In Proceedings of the 7th ACM SIGPLAN Symposium on Scala, SCALA@SPLASH 2016, Amsterdam, Netherlands, October 30 - November 4, 2016, Aggelos Biboudis, Manohar Jonnalagedda, Sandro Stucki, and Vlad Ureche (Eds.). ACM, 21–30. https://doi.org/10.1145/2998392.2998397
[25]
David J. Pearce. 2021. A Lightweight Formalism for Reference Lifetimes and Borrowing in Rust. ACM Trans. Program. Lang. Syst., 43, 1 (2021), 3:1–3:73. https://doi.org/10.1145/3443420
[26]
The Rust Project. [n. d.]. Miri. https://github.com/rust-lang/miri
[27]
John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky Ellison, and Xuejun Yang. 2012. Test-case reduction for C compiler bugs. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’12, Beijing, China - June 11 - 16, 2012, Jan Vitek, Haibo Lin, and Frank Tip (Eds.). ACM, 335–346. https://doi.org/10.1145/2254064.2254104
[28]
Mayank Sharma, Pingshi Yu, and Alastair F. Donaldson. 2023. RustSmith: Random Differential Compiler Testing for Rust. In Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2023). Association for Computing Machinery, New York, NY, USA. 1483–1486. isbn:9798400702211 https://doi.org/10.1145/3597926.3604919
[29]
Chengnian Sun, Vu Le, and Zhendong Su. 2016. Finding compiler bugs via live code mutation. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2016, part of SPLASH 2016, Amsterdam, The Netherlands, October 30 - November 4, 2016, Eelco Visser and Yannis Smaragdakis (Eds.). ACM, 849–863. https://doi.org/10.1145/2983990.2984038
[30]
Ole Tange. 2023. GNU Parallel 20230822 (’Chandrayaan’). https://doi.org/10.5281/zenodo.8278274 GNU Parallel is a general parallelizer to run multiple serial command line programs in parallel without changing them.
[31]
Neven Villani. 2023. Tree Borrows. Master’s thesis. ENS Paris-Saclay. https://github.com/Vanille-N/tree-borrows/blob/eeb44c2509a6fa3f6e55f4bd75f5fd416a576676/half/main.pdf
[32]
Andy Wang. 2023. Rustlantis. https://github.com/cbeuw/rustlantis
[33]
Andy Wang and Ralf Jung. 2024. Reproduction Image for Article ‘Rustlantis: Randomized Differential Testing of the Rust Compiler’. https://doi.org/10.5281/zenodo.12670660
[34]
Haoran Xu, Yongjun Wang, Shuhui Fan, Peidai Xie, and Aizhi Liu. 2020. DSmith: Compiler Fuzzing through Generative Deep Learning Model with Attention. In 2020 International Joint Conference on Neural Networks, IJCNN 2020, Glasgow, United Kingdom, July 19-24, 2020. IEEE, 1–9. https://doi.org/10.1109/IJCNN48605.2020.9206911
[35]
Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. 2011. Finding and understanding bugs in C compilers. SIGPLAN Not., 46, 6 (2011), jun, 283–294. issn:0362-1340 https://doi.org/10.1145/1993316.1993532
Index Terms
- Rustlantis: Randomized Differential Testing of the Rust Compiler
Recommendations
RustSmith: Random Differential Compiler Testing for Rust
ISSTA 2023: Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and AnalysisWe present RustSmith, the first Rust randomised program generator for end-to-end testing of Rust compilers. RustSmith generates programs that conform to the advanced type system of Rust, respecting rules related to borrowing and lifetimes, and that ...
A Survey of Compiler Testing
Virtually any software running on a computer has been processed by a compiler or a compiler-like tool. Because compilers are such a crucial piece of infrastructure for building software, their correctness is of paramount importance. To validate and ...
Rust-twins: Automatic Rust Compiler Testing through Program Mutation and Dual Macros Generation
ASE '24: Proceedings of the 39th IEEE/ACM International Conference on Automated Software EngineeringRust is a relatively new programming language known for its memory safety and numerous advanced features. It has been widely used in system software in recent years. Thus, ensuring the reliability and robustness of the only implementation of the Rust ...
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
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 786Total Downloads
- Downloads (Last 12 months)786
- Downloads (Last 6 weeks)586
Reflects downloads up to 09 Jan 2025
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