[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3639477.3639714acmconferencesArticle/Chapter ViewAbstractPublication PagesicseConference Proceedingsconference-collections
research-article
Open access

Broadly Enabling KLEE to Effortlessly Find Unrecoverable Errors in Rust

Published: 31 May 2024 Publication History

Abstract

Rust is a general-purpose programming language designed for performance and safety. Unrecoverable errors (e.g., Divide by Zero) in Rust programs are critical, as they signal bad program states and terminate programs abruptly. Previous work has contributed to utilizing KLEE, a dynamic symbolic test engine, to verify the program would not panic. However, it is difficult for engineers who lack domain expertise to write test code correctly. Besides, the effectiveness of KLEE in finding panics in production Rust code has not been evaluated. We created an approach, called PanicCheck, to hide the complexity of verifying Rust programs with KLEE. Using PanicCheck, engineers only need to annotate the function-to-verify with #[panic_check]. The annotation guides PanicCheck to generate test code, compile the function together with tests, and execute KLEE for verification. After applying PanicCheck to 21 open-source and 2 closed-source projects, we found 61 test inputs that triggered panics; 59 of the 61 panics have been addressed by developers so far. Our research shows promising verification results by KLEE, while revealing technical challenges in using KLEE. Our experience will shed light on future practice and research in program verification.

References

[1]
"Why is Rust programming language so popular?" https://codilime.com/blog/why-is-rust-programming-language-so-popular/, 2021.
[2]
"Error Handling," https://doc.rust-lang.org/book/ch09-00-error-handling.html, 2022.
[3]
"Rust - Error Handling," https://www.tutorialspoint.com/rust/rust_error_handling.htm, 2022.
[4]
"Rust Error Handling In Practice," https://medium.com/coinmonks/rust-error-handling-in-practice-376d86ba12ca, 2023.
[5]
"Panics - Comprehensive Rust," https://google.github.io/comprehensive-rust/error-handling/panics.html, 2023.
[6]
M. Lindner, J. Aparicius, and P. Lindgren, "No panic! verification of rust programs by symbolic execution," in 2018 IEEE 16th International Conference on Industrial Informatics (INDIN). IEEE, 2018, pp. 108--114.
[7]
M. Lindner, N. Fitinghoff, J. Eriksson, and P. Lindgren, "Verification of safety functions implemented in rust - a symbolic execution based approach," in 2019 IEEE 17th International Conference on Industrial Informatics (INDIN), vol. 1. IEEE, 2019, pp. 432--439.
[8]
"project-oak/rust-verification-tools," https://github.com/project-oak/rust-verification-tools//, 2022.
[9]
A. Reid, L. Church, S. Flur, S. de Haas, M. Johnson, and B. Laurie, "Towards making formal methods normal: meeting developers where they are," CoRR, vol. abs/2010.16345, 2020. [Online]. Available: https://arxiv.org/abs/2010.16345
[10]
N. Tillmann and W. Schulte, "Parameterized unit tests," in Proceedings of the 10th European Software Engineering Conference Held Jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering, ser. ESEC/FSE-13. New York, NY, USA: Association for Computing Machinery, 2005, pp. 253--262. [Online].
[11]
"Rust/KLEE status update," https://project-oak.github.io/rust-verification-tools/2021/03/29/klee-status.html, 2021.
[12]
H. Sigurbjarnarson, J. Bornholt, E. Torlak, and X. Wang, "Push-Button verification of file systems via crash refinement," in 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). Savannah, GA: USENIX Association, Nov. 2016, pp. 1--16. [Online]. Available: https://www.usenix.org/conference/osdi16/technical-sessions/presentation/sigurbjarnarson
[13]
C. Cadar, D. Dunbar, and D. Engler, "Klee: Unassisted and automatic generation of high-coverage tests for complex systems programs," in Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, ser. OSDI'08. USA: USENIX Association, 2008, pp. 209--224.
[14]
"Automatic Rust verification tools (2021)," https://alastairreid.github.io/automatic-rust-verification-tools-2021/, 2021.
[15]
"Type of bugs that KLEE can find," http://mailman.ic.ac.uk/pipermail/klee-dev/2020-April/001983.html, 2020.
[16]
"Crates," https://doc.rust-lang.org/rust-by-example/crates.html.
[17]
"integer-encoding 1.1.7," https://crates.io/crates/integer-encoding/1.1.7, 2021.
[18]
"Primitive Type slice," https://doc.rust-lang.org/std/primitive.slice.html.
[19]
"syn," https://docs.rs/syn/latest/syn/, 2022.
[20]
"What's the difference between references and pointers in Rust?" https://ntietz.com/blog/rust-references-vs-pointers/, 2023.
[21]
"Basic-Topic-String-and-string-Slice," https://users.rust-lang.org/t/basic-topic-string-and-string-slice/41479, 2020.
[22]
"HashMap in std::collections - Rust," https://doc.rust-lang.org/std/collections/struct.HashMap.html, 2022.
[23]
"HashSet in std::collections - Rust," https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html, 2022.
[24]
"Strategy - Rust Design Patterns," https://rust-unofficial.github.io/patterns/patterns/behavioural/strategy.html, 2022.
[25]
"crates.io: Rust Package Registry," https://crates.io, 2022.
[26]
"Coreutils - GNU core utilities," https://www.gnu.org/software/coreutils/, 2022.
[27]
"Proptest Book," https://altsysrq.github.io/proptest-book/intro.html, 2022.
[28]
"clap - Rust," https://docs.rs/clap/latest/clap/, 2022.
[29]
""timeout" needs better error message," https://github.com/uutils/coreutils/issues/3040, 2022.
[30]
Y. Kim, M. Kim, Y. Kim, and Y. Jang, "Industrial application of concolic testing approach: A case study on libexif by using crest-bv and klee," in Proceedings of the 34th International Conference on Software Engineering, ser. ICSE '12. IEEE Press, 2012, pp. 1143--1152.
[31]
X. Wang, L. Zhang, and P. Tanofsky, "Experience report: How is dynamic symbolic execution different from manual testing? a study on klee," in Proceedings of the 2015 International Symposium on Software Testing and Analysis, ser. ISSTA 2015. New York, NY, USA: Association for Computing Machinery, 2015, pp. 199--210. [Online].
[32]
S. Dong, O. Olivo, L. Zhang, and S. Khurshid, "Studying the influence of standard compiler optimizations on symbolic execution," in 2015 IEEE 26th International Symposium on Software Reliability Engineering (ISSRE), 2015, pp. 205--215.
[33]
D. Liew, D. Schemmel, C. Cadar, A. F. Donaldson, R. Zähl, and K. Wehrle, "Floatingpoint symbolic execution: A case study in n-version programming," in Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering, ser. ASE '17. IEEE Press, 2017, pp. 601--612.
[34]
T. Kapus, M. Nowack, and C. Cadar, "Constraints in dynamic symbolic execution: Bitvectors or integers?" in Tests and Proofs: 13th International Conference, TAP 2019, Held as Part of the Third World Congress on Formal Methods 2019, Porto, Portugal, October 9--11, 2019, Proceedings. Berlin, Heidelberg: Springer-Verlag, 2019, pp. 41--54. [Online].
[35]
H. Xu, Z. Zhao, Y. Zhou, and M. R. Lyu, "Benchmarking the capability of symbolic execution tools with logic bombs," IEEE Transactions on Dependable and Secure Computing, vol. 17, no. 6, pp. 1243--1256, 2020.
[36]
F. Busse, P. Gharat, C. Cadar, and A. F. Donaldson, "Combining static analysis error traces with dynamic symbolic execution (experience paper)," in Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis, ser. ISSTA 2022. New York, NY, USA: Association for Computing Machinery, 2022, pp. 568--579. [Online].
[37]
Z. Zhang, Z. Wang, F. Yang, J. Wei, Y. Zhou, and Z. Huang, "Random or heuristic? an empirical study on path search strategies for test generation in klee," Journal of Systems and Software, vol. 188, p. 111269, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0164121222000334
[38]
E. Kurian, D. Briola, P. Braione, and G. Denaro, "Automatically generating test cases for safety-critical software via symbolic execution," Journal of Systems and Software, vol. 199, p. 111629, 2023. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0164121223000249
[39]
Z. Rakamarić and M. Emmi, "Smack: Decoupling source language details from verifier implementations," in International Conference on Computer Aided Verification. Springer, 2014, pp. 106--113.
[40]
J. Toman, S. Pernsteiner, and E. Torlak, "Crust: a bounded verifier for rust (n)," in 2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2015, pp. 75--80.
[41]
V. Astrauskas, P. Müller, F. Poli, and A. J. Summers, "Leveraging rust types for modular specification and verification," Proc. ACM Program. Lang., vol. 3, no. OOPSLA, oct 2019. [Online].
[42]
A. VanHattum, D. Schwartz-Narbonne, N. Chong, and A. Sampson, "Verifying dynamic trait objects in rust," in 2022 IEEE/ACM 44th International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP), 2022, pp. 321--330.
[43]
Facebook, "MIRAI," https://github.com/facebookexperimental/MIRAI, 2019.
[44]
"Crux-MIR," https://github.com/GaloisInc/crucible/blob/master/crux-mir, 2020.
[45]
E. Clarke, D. Kroening, and F. Lerda, "A tool for checking ansi-c programs," in Tools and Algorithms for the Construction and Analysis of Systems, K. Jensen and A. Podelski, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004, pp. 168--176.
[46]
P. Müller, M. Schwerhoff, and A. J. Summers, "Viper: A verification infrastructure for permission-based reasoning," in Verification, Model Checking, and Abstract Interpretation, B. Jobstmann and K. R. M. Leino, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016, pp. 41--62.
[47]
M. Barnett, B.-Y. E. Chang, R. DeLine, B. Jacobs, and K. R. M. Leino, "Boogie: A modular reusable verifier for object-oriented programs," in Formal Methods for Components and Objects, F. S. de Boer, M. M. Bonsangue, S. Graf, and W.-P. de Roever, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 364--387.
[48]
A. Lal, S. Qadeer, and S. K. Lahiri, "A solver for reachability modulo theories," in Computer Aided Verification, P. Madhusudan and S. A. Seshia, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 427--443.
[49]
M. Baranowski, S. He, and Z. Rakamarić, "Verifying rust programs with smack," in International Symposium on Automated Technology for Verification and Analysis. Springer, 2018, pp. 528--535.
[50]
"Seahorn," https://github.com/seahorn/seahorn, 2011.

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
ICSE-SEIP '24: Proceedings of the 46th International Conference on Software Engineering: Software Engineering in Practice
April 2024
480 pages
ISBN:9798400705014
DOI:10.1145/3639477
This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

In-Cooperation

  • Faculty of Engineering of University of Porto

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2024

Check for updates

Qualifiers

  • Research-article

Funding Sources

Conference

ICSE-SEIP '24
Sponsor:

Upcoming Conference

ICSE 2025

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 117
    Total Downloads
  • Downloads (Last 12 months)117
  • Downloads (Last 6 weeks)20
Reflects downloads up to 13 Dec 2024

Other Metrics

Citations

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media