Re:DARPA: Translating All C to Rust (Tractor)
by PhilipRoman on Tuesday July 30, 2024 @05:13PM
(#41114197)
Thanks, that was really helpful. Relying on getting shadow functions right does seem icky, but I guess the improved productivity of CBMC should make up for it. Definitely going to give it another chance!
Re:DARPA: Translating All C to Rust (Tractor)
by nanolith on Tuesday July 30, 2024 @05:24PM
(#41114285)
You're welcome. I've been meaning to write a blog article on the subject, because it is a subtle thing to get working.
Think of shadow functions as the specifications that you are building. Unlike proof assistants or Frama-C, you write specifications in C itself, and they work similarly to code. Often, the same contracts you write in these specifications can be shared by both the shadow functions and the real functions they shadow.
I take a bottom-up approach to model checking. I'll start by model checking the lowest level code, then I'll shadow this code to model check code that depends on it. In this way, I can increase the level of abstraction for model checking, focusing just on the side effects and contracts of functions I shadow, and move up the stack toward more and more general code.
The biggest issue you will run into with bounded model checking is recursion and looping. In these cases, you want to refactor the code to make it easier to formally verify outside of the loop. Capture and assert on loop variants / invariants, and feed these forward in assertions on code.
There's no way I can capture all of this in an HN comment, but to get CBMC to work, you need to break down your code.