Thursday, April 6, 2017

Corrode update: control flow translation correctness

I've been pretty quiet about Corrode for a few months. That's partly because I was traveling some, partly because I've been busy with non-Corrode client work, partly because I've been setting up my next Rust-related contracts that I hope to get to announce soon... but mostly, I've been quiet about Corrode because I've been trying to fix some very difficult bugs since December, and it was demoralizing to fight with my code for so long.

So I'm very pleased to announce that Corrode now translates arbitrary C control flow to Rust, correctly!

One thing this has already enabled: the new rust-lzo crate on crates.io is a Rust implementation of the LZO compression algorithm, translated using Corrode from the Linux kernel's implementation. Hooray!

I last talked about the challenges around getting control flow right in November ("Go To Statement Considered (Mostly) Harmless"). At that time I mentioned that Corrode couldn't handle "irreducible" control flow, or some other cases. Later I discovered that sometimes it wasn't even producing correct answers for the cases that I thought were working.

Corrode's new control-flow algorithm is based on Emscripten's "Relooper" algorithm, as described in "Emscripten: An LLVM-to-JavaScript Compiler". I'd like to thank Brian Anderson of the Mozilla Rust team for reminding me that Emscripten exists and already solved almost exactly the problem I faced! (Unless I'm mixing people up again, in which case I'd like to thank whoever actually told me that, instead.)

The Relooper is fully general: it can handle any control flow that you can express in C, including arbitrary 'goto' statements. And I have confidence that my implementation really will handle any wacky control flow you can come up with, partly because at this point I have tested millions of randomly-generated control-flow graphs against relatively simple correctness properties using QuickCheck. I found so many bugs that way! QuickCheck then simplified each bug-triggering control-flow graph down to the smallest graph that would still trigger a bug, making it easier to figure out why it failed.

I now have Travis-CI testing 100,000 random CFGs after every build. This is not a hardship because the implementation is fast: on my 2013-era laptop, testing that many examples only takes around 20 seconds!

Some of the bugs I encountered were in cases which are not covered by the Emscripten paper. I never found the current implementation of the Relooper when I looked at the Emscripten source code, so I don't know whether those cases are covered by Emscripten's real implementation and were just left out of the paper, or even if they were covered in the paper and I just missed it. I also discovered that one of the cases in the paper can't happen because it's subsumed by the others. I intend to ping the paper's author about these surprises sooner or later...

This algorithm is tricky to get right and requires very carefully defining invariants and preconditions. Because I needed to reason about the algorithm in a very formal way to have any hope of getting it right, I thought it might be a good use case for annotating the implementation with refinement types as implemented in LiquidHaskell. Unfortunately, I had too much trouble writing types that LiquidHaskell would accept, so I gave up. Still, just making the effort to write down a semi-formal model helped my understanding a lot, so it wasn't wasted effort! I hope to find a good excuse to play with LiquidHaskell again sometime.

Although I wasn't able to formalize my reasoning for why Corrode's implementation of the Relooper is correct, I at least wrote down an English-language sketch of the correctness and termination proofs for the algorithm, as part of the Literate Haskell documentation for Corrode's CFG module. Please read it, I spent a lot of time writing it ;-)

I'm slowly evolving this algorithm beyond Emscripten's implementation, because for Corrode I want the output to be as human-readable and maintainable as possible. (Emscripten's output is only intended for a web browser to parse, and you need only glance at JavaScript that humans write to realize that nobody's much bothered if we give our web browsers massive headaches.) So far I have a simple post-processing pass to merge any "Simple" block with an immediately-following "Multiple" block, which eliminates the need to introduce an extra variable in the most common cases; and a straightforward check to avoid using labeled "break" and "continue" statements when referring to the most immediately enclosing loop. I have more clean-ups planned, inspired by trying to read the output from Corrode on real C source files.

I'm sure the question you're asking yourself by now is, "But how is the CVS Rust port coming along?" Significantly better now, thank you! There are now only five source files that Corrode refuses to translate, for various reasons, although quite a few more still won't compile after translation. And at least one source file now works fine that previously, when I tried converting it to Rust, made CVS fail its test suite. So a lot of the remaining work is just in cleaning up the output, plus a bit of handling more corner cases of C.

Corrode has many limitations left to fix. But at least control flow isn't one of them any more!

Tuesday, January 3, 2017

Which projects should convert to Rust?

Since the 1.0 release of the Rust programming language in May 2015, people have been exploring different ideas about what to use it for.
  • Does Rust make C obsolete?
  • If so, should we replace existing C programs with Rust equivalents?
  • Or should we leave existing code alone, write bindings that let us re-use it from Rust, and just write new code in this new language?
Of course, there's no one-size-fits-all answer to these questions. But I think there's enough evidence now from various experiments to put together some pretty decent guidelines, which I'll summarize here in case you're impatient:
  1. Rewriting existing software in Rust is an excellent educational exercise, worth doing if you just want to learn something.
  2. If you want your Rust version to be adopted, be prepared to give strong evidence that it's equivalent to the original implementation. This is easiest if the project has a comprehensive test suite, and if much of your translation work can be automated.
  3. Translating a project to Rust is justifiable if the bugs it has the most trouble with are the kinds of bugs Rust is most helpful on—notably, memory safety bugs.
  4. If a project's community is resistant to switching to Rust, any effort you put into porting may be wasted. Make sure you build community support around your work!
For more details, read on.

I'm taking this evidence from two kinds of projects. First, from quite a few efforts to replace pieces of C with Rust equivalents, such as:
  • rusl: an experimental musl libc incremental rewrite in Rust
  • Librsvg gets Rusty: incrementally rewriting parts of an SVG library in Rust, while maintaining binary compatibility with the fully-C version of the library
  • uutils/coreutils: rewriting GNU coreutils in Rust from scratch
  • Trust-DNS: from-scratch implementation of a DNS client and server, inspired by CVEs in BIND
A second source of evidence comes from my efforts at automatic translation from C to Rust using Corrode, and especially my Mozilla-supported experiment on translating CVS.

Education

Bear in mind that many of these porting efforts, such as rusl and librsvg, were started for educational purposes (see, for instance, rusl's goals and non-goals). I think it's safe to guess that everyone who has made a serious attempt at a project like this has learned a lot! So let's make that guideline #1:
If you want to learn a language you don't know already, one very educational way to do it is to rewrite some piece of software you already understand.
(That guideline isn't even specific to Rust. In 2002, I did an exercise in writing a run-length-encoding compressor in as many languages as I had patience to try; I picked C++, Perl, Java, Smalltalk, x86 assembly, and Haskell. It was very helpful for discovering some pros and cons of each language. I had not tried Smalltalk or Haskell before and that exercise led to my continued interest in Haskell years later.)

But what if you want more return on investment than just an educational experience? We'll have to look at the results of these projects more closely.

Correctness, safety, and security

These projects all share at least one big challenge: How can you be sure the Rust version behaves correctly? Nobody wants to replace code that works with code that has new bugs, and while Rust rules out certain classes of memory and type safety problems, it makes no guarantees about program logic. But then, how can you have any confidence that the original version is correct? Perhaps the answer to that question can answer the earlier one.

The above examples all use automated testing to gain confidence in their correctness. The musl, librsvg, and busybox projects each provide a test suite that these porting efforts adopted to test that their Rust rewrites produced the same results as the original implementations. So, assuming the tests pass for both implementations, we can be sure that the Rust version works exactly like the original, at least for those parts that are tested.

That's not as satisfying as I'd like. For example, the author of rusl points out that not only is the test suite for musl incomplete, but musl doesn't pass all of it. Still, re-using an existing test suite provides pretty good confidence.

Trust-DNS doesn't re-use an existing test suite, but its author wrote a test suite based on the relevant DNS specifications, and some of its tests query well-known public DNS servers as a simple interoperability check.

That approach has hazards as well. NASA Langley Research Center's 1990 follow up to the Knight/Leveson "Experimental Evaluation of the Assumption of Independence in Multi-Version Programming" from 1985 found that when multiple teams attempt to write separate programs implementing the same specification, their bugs are not statistically independent. When multiple implementations failed on the same inputs, they found that "lack of understanding by the programmers of key points in the specification was a major contributor".

Trust-DNS encountered an instance of this problem, in fact, related to this bit of RFC6840: "The guidance in the above paragraph differs from what has been published before but is consistent with current common practice." Different DNS developers interpreted a particular specification section in different ways, leading to non-interoperable implementations.

But if the implementation and the tests are written by the same person, then on top of the problems of incomplete test suites, any mis-interpretation of the specification will affect both the implementation and its tests, resulting in an incorrect implementation that appears to be correct because it passes its test suite.

That said, writing a test suite from a specification is far better than nothing, and I'm sure this approach has caught bugs in Trust-DNS.

Anyway, correctness isn't all that matters. The safety and security properties that Rust guarantees are not the only such properties you might care about, and test suites can't cover the gap. If some invalid input causes the C version to return an error and keep going, but causes the Rust version to panic or go into an infinite loop, that could be an exploitable denial-of-service bug. Or if the Rust version is missing an access-control check, it could disclose information that an attacker wasn't authorized for. It's not feasible to write tests to catch all of these cases.

Equivalence

I'd summarize all these concerns as guideline #2:
If you want to replace existing software with a Rust implementation, then the Rust version must behave equivalently to the original, aside from inputs that crash the original. To convince other people to adopt your new implementation, you must give them confidence that the new implementation really is equivalent.
Reusing the original implementation's test suite is a good start at providing this confidence. Demonstrating that the new implementation can interoperate with other implementations, as Trust-DNS does, is another good step.

But I think better approaches are available for demonstrating equivalence when the new implementation is supposed to match an existing one. (These don't help Trust-DNS, but do help the others.)

First, you could mechanically prove that the two implementations are equivalent. The developers of KLEE tested equivalence between busybox and GNU coreutils, for example. KLEE automatically generated test cases that maximized code coverage in both code bases, finding inputs which produced different outputs. In several cases, those differences represented significant correctness bugs; in others, just features that weren't implemented in one version or the other. The Software Analysis Workbench from Galois is also designed for this, and I suspect afl-fuzz could be used in a similar way. Each tool has different trade-offs between performance, completeness, and ease-of-use.

I'm surprised that I haven't seen any of the port-to-Rust projects use any of those tools, to be honest.

Second, and my personal favorite, is to automate as much of the porting effort as possible. If you've been following my blog posts on Corrode, then you know this is the approach I've been working on. This changes the problem from "do I trust the Rust version?" to "do I trust the translator?" Don't get me wrong: establishing trust in the automation is hard too! But so long as the translation tools can be reused across many projects, it's worth spending a lot of time on their correctness.

Any of the above techniques for establishing equivalence may be enough on its own to convince people to adopt your shiny new Rust implementation. But when the software you're converting is especially important, you may need to combine techniques. For example, in my CVS experiments, I'm using Corrode to automate much of the conversion, but I'm also relying on the extensive test suite that CVS has to check that neither Corrode nor I made mistakes. Since Corrode is still young, I've found bugs in it this way, making the test suite an excellent sanity check.

Time and resources

This suggests guideline #3:
The amount of energy you put into converting a project to Rust should be proportional to the importance of that project, and to the consequences of those bugs which Rust can help with.
A program that doesn't interact with the Internet or with files that might come from untrusted sources, like a single-player game or a scientific simulation, may not be worth spending much effort converting to Rust. To be clear, I think there are benefits to choosing Rust when starting work on scientific simulations or games! But once you have already written and debugged code for these sorts of programs, the marginal benefit of switching to Rust is much lower.

On the other hand, a small library that is used by a huge number of programs and often handles untrusted data, such as zlib or a multimedia codec, might be worth spending a lot of time on:
  1. because Rust's memory-safety guarantees address these libraries' most common sources of bugs,
  2. because the consequences of those bugs are widespread due to the number of users,
  3. and because the amount of code to translate is small enough that the effort is nicely bounded.
Widely used network programs such as NTP, SSH, web servers, etc., may be strong candidates for the same reasons.

For libraries that are not worth translating to Rust, it's probably worth at least using tools like rust-bindgen to generate Rust bindings so Rust developers can take advantage of the time and effort that have gone into those libraries.

Ideally, grant programs like the Linux Foundation's Core Infrastructure Initiative or Mozilla Open Source Support should fund efforts to translate critical open-source projects to Rust. Of course, until there's a significant example where a Rust implementation has replaced its predecessor, this may be a hard sell.

And on that note, here's guideline #4:
If you want your Rust port of a project to be adopted, you'd better make sure you have buy-in from that project's community.
This is just standard project management advice, of course, and applies to both open-source and commercial in-house projects. A project's community is deeply invested in their existing implementation, especially in projects with a long history. The larger and more established the community is, the harder it will be to convince a critical mass of their developers to learn Rust to continue working on a project that many of them probably feel is fine as-is.

You could say that the reason I chose to try converting CVS to Rust because not only does it satisfy guideline #3, but it also has too few people caring about it to complain about my attempts. 😉

I find it unlikely, for example, that the Linux kernel will ever switch to Rust. (Although that won't stop me from testing Corrode on it!) In fact, I'd expect some hypothetical new operating system to supplant Linux before Linux developers would switch programming languages. (I'm cheering for seL4, personally, perhaps together with Genode.)

On the other hand, it looks like developers working on GNOME libraries like librsvg may wind up being relatively early adopters.

The gap between "nobody wants this" and "everybody's on board" will move over time, as Rust's advantages are demonstrated in more projects. For the moment, it's still a young language: while I expect projects willing to make the switch will be relatively rare for the moment, I believe we'll see some significant early adopters soon. Naturally, I hope my work on Corrode will help make that happen sooner!

Summary

To recap:
  1. Rewriting existing software in Rust is an excellent educational exercise, worth doing if you just want to learn something.
  2. If you want your Rust version to be adopted, be prepared to give strong evidence that it's equivalent to the original implementation. This is easiest if the project has a comprehensive test suite, and if much of your translation work can be automated.
  3. Translating a project to Rust is justifiable if the bugs it has the most trouble with are the kinds of bugs Rust is most helpful on—notably, memory safety bugs.
  4. If a project's community is resistant to switching to Rust, any effort you put into porting may be wasted. Make sure you build community support around your work!
Discussion elsewhere on this post: