Survey on Formal Verification Research for Rust Language
Author:
Affiliation:

Clc Number:

TP311

  • Article
  • | |
  • Metrics
  • |
  • Reference [90]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    As an emerging system programming language with a focus on safety, Rust ensures memory and concurrency safety through its innovative ownership model and borrowing mechanism. Despite its design for safety, existing research has identified several safety challenges that Rust still faces. Formal verification, grounded in rigorous mathematical principles, provides robust assurances for enhancing Rust’s security. By constructing precise and well-defined semantic models, it becomes possible to formally prove that programs adhering to Rust’s type system meet safety requirements. Automated verification tools for Rust further enable users to validate the safety and correctness of their programs. This study presents a comprehensive and systematic analysis of formal verification approaches for Rust. It begins by introducing Rust’s core semantics and complex features, followed by an exploration of research and verification efforts in Rust’s formal semantics, emphasizing the role and potential of Rust’s type system in formal verification. Next, the study systematically compares the capabilities, supported language features, underlying techniques, and application scenarios of various automated Rust verification tools. These comparisons are instrumental in guiding tool selection and integration within real-world Rust development workflows. In addition, this study summarizes exemplary cases of verified Rust programs, demonstrating the significant impact of formal verification in ensuring program correctness and providing practical tool usage recommendations for developers. Finally, it discusses the key challenges in the field and outlines promising directions for future research, including the verification of unsafe Rust code, concurrent code verification, trustworthy compilation, and large model-driven formal verification. This study aims to establish a strong security foundation for the Rust community and foster the broader adoption of formal verification methods in Rust development.

    Reference
    [1] Boos K, Liyanage N, Ijaz R, Zhong L. Theseus: An experiment in operating system structure and state management. In: Proc. of the 14th USENIX Conf. on Operating Systems Design and Implementation. Berkeley: USENIX Association, 2020. 1.
    [2] Redoxfs. 2017. https://gitlab.redox-os.org/redox-os/redoxfs
    [3] Lyu S, Rzeznik A. Going serverless with the Amazon AWS Rust SDK. In: Lyu S, Rzeznik A, eds. Practical Rust Projects: Build Serverless, AI, Machine Learning, Embedded, Game, and Web Applications. 2nd ed., Berkeley: Apress, 2023. 201–246. [doi: 10.1007/978-1-4842-9331-7_6]
    [4] Database drivers and ORMs for Rust that are ready for production. 2020. https://blog.logrocket.com/11-database-drivers-and-orms-for-rust-that-are-ready-for-production
    [5] Servo. 2017. https://github.com/servo/servo
    [6] Smoltcp. 2017. https://github.com/smoltcp-rs/smoltcp
    [7] Solana. https://solana.com/zh
    [8] Xu H, Chen ZB, Sun MS, Zhou YF, Lyu MR. Memory-safety challenge considered solved? An in-depth study with all Rust CVEs. ACM Trans. on Software Engineering and Methodology (TOSEM), 2022, 31(1): 3.
    [9] Mergendahl S, Burow N, Okhravi H. Cross-language attacks. In: Proc. of the 29th Network and Distributed System Security Symp. San Diego: The Internet Society, 2022. 1–17.
    [10] system-pclub. 2020. https://github.com/system-pclub/rust-study
    [11] 胡霜, 华保健, 欧阳婉容, 樊淇梁. Rust语言安全研究综述. 信息安全学报, 2023, 8(6): 64–83.
    Hu S, Hua BJ, Ouyang WR, Fan QL. A survey of Rust language security research. Journal of Cyber Security, 2023, 8(6): 64–83 (in Chinese with English abstract).
    [12] Cui M, Chen C, Xu H, Zhou Y. SafeDrop: Detecting memory deallocation bugs of Rust programs via static data-flow analysis. ACM Trans. on Software Engineering and Methodology, 2023, 32(4): 1–21.
    [13] Jung R, Jourdan JH, Krebbers R, Dreyer D. RustBelt: Securing the foundations of the Rust programming language. Proc. of the ACM on Programming Languages, 2018, 2(POPL): 66.
    [14] Bornholt J, Joshi R, Astrauskas V, Cully B, Kragl B, Markle S, Sauri K, Schleit D, Slatton G, Tasiran S, Van Geffen J, Warfield A. Using lightweight formal methods to validate a key-value storage node in Amazon S3. In: Proc. of the 28th ACM SIGOPS Symp. on Operating Systems Principles. ACM, 2021. 836–850. [doi: 10.1145/3477132.3483540]
    [15] Gäher L, Sammler M, Jung R, Krebbers R, Dreyer D. RefinedRust: A type system for high-assurance verification of Rust programs. Proc. of the ACM on Programming Languages, 2024, 8(PLDI): 192.
    [16] Ayoun SÉ, Denis X, Maksimović P, Gardner P. A hybrid approach to semi-automated Rust verification. arXiv:2403.15122, 2024.
    [17] Polonius. 2019. https://rust-lang.github.io/compiler-team/working-groups/polonius
    [18] Huet GP, Kahn G, Paulin-Mohring C. The Coq proof assistant: A tutorial: Version 6.1. 1997. https://inria.hal.science/file/index/docid/69967/filename/RT-0204.pdf
    [19] Matsushita Y, Denis X, Jourdan JH, Dreyer D. RustHornBelt: A semantic foundation for functional verification of Rust programs with unsafe code. In: Proc. of the 43rd ACM SIGPLAN Int’l Conf. on Programming Language Design and Implementation. San Diego: ACM, 2022. 841–856. [doi: 10.1145/3519939.3523704]
    [20] Weiss A, Gierczak O, Patterson D, Ahmed A. Oxide: The essence of Rust. arXiv:1903.00982, 2021.
    [21] Lehmann N, Geller AT, Vazou N, Jhala R. Flux: Liquid types for Rust. Proc. of the ACM on Programming Languages, 2023, 7(PLDI): 169.
    [22] Payet É, Pearce DJ, Spoto F. On the termination of borrow checking in featherweight Rust. In: Proc. of the 14th Int’l Symp. on NASA Formal Methods. Pasadena: Springer, 2022. 411–430. [doi: 10.1007/978-3-031-06773-0_22]
    [23] Reed E. Patina: A formalization of the Rust programming language. Technical Report, UW-CSE-15-03-02, Washington: University of Washington, 2015.
    [24] Jung R, Dang HH, Kang J, Dreyer D. Stacked borrows: An aliasing model for Rust. Proc. of the ACM on Programming Languages, 2020, 4(POPL): 41.
    [25] Wang F, Song F, Zhang M, Zhu XR, Zhang J. KRust: A formal executable semantics of Rust. In: Proc. of the 2018 Int’l Symp. on Theoretical Aspects of Software Engineering. Guangzhou: IEEE, 2018. 44–51. [doi: 10.1109/TASE.2018.00014]
    [26] Kan SL, Chen Z, Sanan D, Lin SW, Liu Y. An executable operational semantics for Rust with the formalization of ownership and borrowing. arXiv:1804.07608, 2020.
    [27] Cardelli L. Type systems. ACM Computing Surveys (CSUR), 1996, 28(1): 263–264.
    [28] Igarashi A, Pierce BC, Wadler P. Featherweight Java: A minimal core calculus for Java and GJ. ACM Trans. on Programming Languages and Systems (TOPLAS), 2001, 23(3): 396–450.
    [29] Jung R, Swasey D, Sieczkowski F, Svendsen K, Turon A, Birkedal L, Dreyer D. Iris: Monoids and invariants as an orthogonal basis for concurrent reasoning. In: Proc. of the 42nd Annual ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages. Mumbai: ACM, 2015. 637–650. [doi: 10.1145/2676726.2676980]
    [30] Jung R, Krebbers R, Jourdan JH, Bizjak A, Birkedal L, Dreyer D. Iris from the ground up: A modular foundation for higher-order concurrent separation logic. Journal of Functional Programming, 2018, 28: e20.
    [31] Dang HH, Jourdan JH, Kaiser JO, Dreyer D. RustBelt meets relaxed memory. Proc.s of the ACM on Programming Languages, 2020, 4(POPL): 34.
    [32] Sammler M, Lepigre R, Krebbers R, Memarian K, Dreyer D, Garg D. RefinedC: Automating the foundational verification of C code with refined ownership types. In: Proc. of the 42nd ACM SIGPLAN Int’l Conf. on Programming Language Design and Implementation. Virtual: ACM, 2021. 158–174. [doi: 10.1145/3453483.3454036]
    [33] Astrauskas V, Müller P, Poli F, Summers AJ. Leveraging Rust types for modular specification and verification. Proc. of the ACM on Programming Languages, 2019, 3(OOPSLA): 147.
    [34] Lattuada A, Hance T, Cho C, Brun M, Subasinghe I, Zhou Y, Howell J, Parno B, Hawblitzel C. Verus: Verifying Rust programs using linear ghost types. Proc. of the ACM on Programming Languages, 2023, 7(OOPSLA1): 85.
    [35] Denis X, Jourdan JH, Marché C. CREUSOT: A foundry for the deductive verification of Rust programs. In: Proc. of the 23rd Int’l Conf. on Formal Methods and Software Engineering: Int’l Conf. on Formal Engineering Methods. Madrid: Springer, 2022. 90–105. [doi: 10.1007/978-3-031-17244-1_6]
    [36] Matsushita Y, Tsukada T, Kobayashi N. RustHorn: CHC-based verification for Rust programs. ACM Trans. on Programming Languages and Systems (TOPLAS), 2021, 43(4): 15.
    [37] Jacobs B, Smans J, Philippaerts P, Vogels F, Penninckx W, Piessens F. VeriFast: A powerful, sound, predictable, fast verifier for C and Java. In: Proc. of the 3rd Int’l Conf. on NASA Formal Methods. Pasadena: Springer, 2011. 41–55. [doi: 10.1007/978-3-642-20398-5_4]
    [38] Toman J, Pernsteiner S, Torlak E. Crust: A bounded verifier for Rust (N). In: Proc. of the 30th IEEE/ACM Int’l Conf. on Automated Software Engineering. Lincoln: IEEE, 2015. 75–80. [doi: 10.1109/ASE.2015.77]
    [39] Baranowski M, He SB, Rakamarić Z. Verifying Rust programs with SMACK. In: Proc. of the 16th Int’l Symp. on Automated Technology for Verification and Analysis. Los Angeles: Springer, 2018. 528–535. [doi: 10.1007/978-3-030-01090-4_32]
    [40] Kani Rust verifier. 2022. https://github.com/model-checking/kani
    [41] Loom. 2021. https://github.com/tokio-rs/loom?tab=readme-ov-file
    [42] Zhang KW, Liu GJ. Automatically transform Rust source to Petri nets for checking deadlocks. arXiv:2212.02754, 2022.
    [43] Ullrich S. Simple verification of Rust programs via functional purification [MS. Thesis]. Karlsruhe: Karlsruhe Institute of Technology, 2016.
    [44] Ho S, Protzenko J. Aeneas: Rust verification by functional translation. Proc. of the ACM on Programming Languages, 2022, 6(ICFP): 116.
    [45] Reynolds JC. Separation logic: A logic for shared mutable data structures. In: Proc. of the 17th Annual IEEE Symp. on Logic in Computer Science. Copenhagen: IEEE, 2002. 55–74. [doi: 10.1109/LICS.2002.1029817]
    [46] Hoare CAR. An axiomatic basis for computer programming. Communications of the ACM, 1969, 12(10): 576–580.
    [47] de Moura L, Bjørner N. Z3: An efficient SMT solver. In: Proc. of the 14th Int’l Conf. on Tools and Algorithms for the Construction and Analysis of Systems. Budapest: Springer, 2008. 337–340. [doi: 10.1007/978-3-540-78800-3_24]
    [48] Müller P, Schwerhoff M, Summers AJ. Viper: A verification infrastructure for permission-based reasoning. In: Proc. of the 17th Int’l Conf. on Verification, Model Checking, and Abstract Interpretation. Petersburg: Springer, 2016. 41–62. [doi: 10.1007/978-3-662-49122-5_2]
    [49] Foroushaani NR, Jacobs B. Modular formal verification of Rust programs with unsafe blocks. arXiv:2212.12976, 2022.
    [50] Fragoso Santos J, Maksimović P, Ayoun SÉ, Gardner P. Gillian, part I: A multi-language platform for symbolic execution. In: Proc. of the 41st ACM SIGPLAN Conf. on Programming Language Design and Implementation. London: ACM, 2020. 927–942. [doi: 10.1145/3385412.3386014]
    [51] Nipkow T, Wenzel M, Paulson LC. Isabelle/HOL: A Proof Assistant for Higher-order Logic. Berlin: Springer, 2002.
    [52] Avigad J, De Moura L, Kong S. Theorem proving in Lean. 2024. https://leanprover.github.io/theorem_proving_in_lean/theorem_proving_in_lean.pdf
    [53] Clarke E, Kroening D, Lerda F. A tool for checking ANSI-C programs. In: Proc. of the 10th Int’l Conf. on Tools and Algorithms for the Construction and Analysis of Systems. Barcelona: Springer, 2004. 168–176. [doi: 10.1007/978-3-540-24730-2_15]
    [54] Byrnes T, Takashima Y, Jia LM. Automatically enforcing Rust trait properties. In: Proc. of the 25th Int’l Conf. on Verification, Model Checking, and Abstract Interpretation. London: Springer, 2024. 210–223. [doi: 10.1007/978-3-031-50521-8_10]
    [55] Thurrott P. Microsoft is rewriting parts of the windows kernel in Rust. 2023. https://www.thurrott.com/windows/282471/microsoft-is-rewriting-parts-of-the-windows-kernel-in-rust
    [56] Rust for Linux. 2024. https://github.com/Rust-for-Linux
    [57] Jansens D. Supporting the use of Rust in the Chromium project. 2023. https://security.googleblog.com/2023/01/supporting-use-of-rust-in-chromium.html
    [58] Stoep JV, Chrome Security Team. Memory safe languages in Android 13. 2022. https://security.googleblog.com/2022/12/memory-safe-languages-in-android-13.html
    [59] Narayanan V, Baranowski MS, Ryzhyk L, Rakamarić Z, Burtsev A. RedLeaf: Towards an operating system for safe and verified firmware. In: Proc. of the 2019 Workshop on Hot Topics in Operating Systems. Bertinoro: ACM, 2019. 37–44. [doi: 10.1145/3317550.3321449]
    [60] Brun M, Achermann R, Chajed T, Howell J, Zellweger G, Lattuada A. Beyond isolation: OS verification as a foundation for correct applications. In: Proc. of the 19th Workshop on Hot Topics in Operating Systems. Providence: ACM, 2023. 158–165. [doi: 10.1145/3593856.3595899]
    [61] Bhardwaj A, Kulkarni C, Achermann R, Calciu I, Kashyap S, Stutsman R, Tai A, Zellweger G. NrOS: Effective replication and sharing in an operating system. In: Proc. of the 15th USENIX Symp. on Operating Systems Design and Implementation. USENIX Association, 2021. 295–312.
    [62] Chen XD, Li ZF, Mesicek L, Narayanan V, Burtsev A. Atmosphere: Towards practical verified kernels in Rust. In: Proc. of the 1st Workshop on Kernel Isolation, Safety and Verification. Koblenz: ACM, 2023. 9–17. [doi: 10.1145/3625275.3625401]
    [63] Ijaz R, Boos K, Zhong L. Leveraging Rust for lightweight OS correctness. In: Proc. of the 1st Workshop on Kernel Isolation, Safety and Verification. Koblenz: ACM, 2023. 1–8. [doi: 10.1145/3625275.3625398]
    [64] LeBlanc H, Taylor N, Bornholt J, Chidambaram V. SquirrelFS: Using the Rust compiler to check file-system crash consistency. In: Proc. of the 18th USENIX Symp. on Operating Systems Design and Implementation. Santa Clara: USENIX Association, 2024. 387–404.
    [65] Jia YK, Liu S, Wang WH, Chen Y, Zhai ZD, Yan SM, He ZY. HyperEnclave: An open and cross-platform trusted execution environment. In: Proc. of the 2022 USENIX Annual Technical Conf. Carlsbad: USENIX Association, 2022. 437–454.
    [66] Dai ZY, Liu S, Sjoberg V, Li XP, Chen Y, Wang WH, Jia YK, Anderson SN, Elbeheiry L, Sondhi S, Zhang Y, Ni ZZ, Yan SM, Gu RH, He ZY. Verifying Rust implementation of page tables in a software enclave hypervisor. In: Proc. of the 29th ACM Int’l Conf. on Architectural Support for Programming Languages and Operating Systems. La Jolla: ACM, 2024. 1218–1232. [doi: 10.1145/3620665.3640398]
    [67] AMD. AMD secure encrypted virtualization (SEV). 2024. https://www.amd.com/zh-tw/developer/sev.html
    [68] Zhou ZQ, Anjali, Chen WT, Gong SS, Hawblitzel C, Cui WD. VERISMO: A verified security module for confidential VMs. In: Proc. of the 18th USENIX Symp. on Operating Systems Design and Implementation. Santa Clara: USENIX Association, 2024. 32.
    [69] Kiefer F. evercrypt-rust. 2024. https://github.com/franziskuskiefer/evercrypt-rust
    [70] Merigoux D, Kiefer F, Bhargavan K. Hacspec: Succinct, executable, verifiable specifications for high-assurance cryptography embedded in Rust. Inria: HAL, 2021.
    [71] Hax. 2023. https://github.com/hacspec/hax
    [72] Chen HB, Chen HH, Sun MS, Li K, Chen ZF, Wang XF. A verified confidential computing as a service framework for privacy preservation. In: Proc. of the 32nd USENIX Conf. on Security Symp. Anaheim: USENIX Association, 2023. 265.
    [73] Njor EJ, Gústafsson H. Static taint analysis in Rust [MS. Thesis]. Aalborg: Aalborg University, 2021.
    [74] Asterinas. 2024. https://github.com/asterinas/asterinas
    [75] Sun XD, Ma WJ, Gu JT, Ma ZC, Chajed T, Howell J, Lattuada A, Padon O, Suresh L, Szekeres A, Xu TY. Anvil: Verifying liveness of cluster management controllers. In: Proc. of the 18th USENIX Conf. on Operating Systems Design and Implementation. Santa Clara: USENIX Association, 2024. 35.
    [76] Ferrocene. 2024. https://ferrocene.dev/en/
    [77] A-mir-formality. 2022. https://github.com/rust-lang/a-mir-formality
    [78] Minirust. 2022. https://github.com/minirust/minirust
    [79] Li HY, Guo LW, Yang YX, Wang SG, Xu MW. An empirical study of Rust-for-Linux: The success, dissatisfaction, and compromise. In: Proc. of the 2024 Conf. on Usenix Annual Technical Conf. Santa Clara: USENIX Association, 2024. 27.
    [80] 汪宇霆. Rust核心语言机制的编译验证方法. 2024. https://jhc.sjtu.edu.cn/~yutingwang/files/posters/rust-hyl.pdf
    Wang YT. Compiler validation methods for Rust core language mechanisms. 2024 (in Chinese). https://jhc.sjtu.edu.cn/~yutingwang/files/posters/rust-hyl.pdf
    [81] Zheng XY, Wan ZY, Zhang Y, Chang R, Lo D. A closer look at the security risks in the Rust ecosystem. ACM Trans. on Software Engineering and Methodology, 2024, 33(2): 34.
    [82] Zhao JZ, Nagarakatte S, Martin MMK, Zdancewic S. Formalizing the LLVM intermediate representation for verified program transformations. In: Proc. of the 39th Annual ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages. Philadelphia: ACM, 2012. 427–440. [doi: 10.1145/2103656.2103709]
    [83] Blazy S, Leroy X. Mechanized semantics for the Clight subset of the C language. Journal of Automated Reasoning, 2009, 43(3): 263–288.
    [84] Song PY, Yang KY, Anandkumar A. Towards large language models as copilots for theorem proving in lean. arXiv:2404.12534, 2024.
    [85] Wu YH, Jiang AQ, Li WD, Rabe MN, Staats C, Jamnik M, Szegedy C. Autoformalization with large language models. In: Proc. of the 36th Int’l Conf. on Neural Information Processing Systems. New Orleans, 2022. 32353–32368.
    [86] Jiang AQ, Welleck S, Zhou JP, Li WD, Liu JC, Jamnik M, Lacroix T, Wu YH, Lample G. Draft, sketch, and prove: Guiding formal theorem provers with informal proofs. arXiv:2210.12283, 2022.
    [87] Sunday E. Using Kani to write and validate Rust code with ChatGPT. 2023. https://blog.logrocket.com/using-kani-write-validate-rust-code-chatgpt
    [88] Sun CY, Sheng Y, Padon O, Barrett C. Clover: Closed-loop verifiable code generation. In: Proc. of the 1st Int’l Symp. on AI Verification. Montreal: Springer, 2024. 134–155.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

张卓若,常瑞,杨申毅,陈芳.面向Rust语言的形式化验证方法研究综述.软件学报,2025,36(8):1-33

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:August 26,2024
  • Revised:October 14,2024
  • Online: December 10,2024
You are the first2044566Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063