4 ms·
My favourite part: > our verification work resulted in uncovering and fixing a bug in Rust’s standard library, demonstrating that our model of Rust is realisti
by chrismorgan 9y ago
My favourite part:
> our verification work resulted in uncovering and fixing a bug in Rust’s standard library, demonstrating that our model of Rust is realistic enough to be useful.
The bug was https://github.com/rust-lang/rust/issues/41622 https://github.com/rust-lang/rust/issues/41622.
- dmix 9y agoOne thing about formal verification, and a lesser extent automated testing, is that you often end up spending the majority of the time adapting the program or language to work with verification rather than actually solving a real-world problem or fixing a real bug. His third comment fits this category well. The problem set he describes was that the code is designed in a way that's ill suited for formal verification. But he never mentions any other benefits or justification for changing how it works. So I'm not sure it's necessarily a 'bug' in a traditional sense that supports the use of formal verification, except in some self-serving way. That said, I'm very much in support of formal verification in these types of languages.
- rntz 9y agoWe regard "this program is hard to test" as a problem that's worth refactoring to fix; why shouldn't we regard "this program is hard to verify" the same way?
- phkahler 9y agoBut "this language is hard to verify" should not trump the usability of the language. The verification only needs to be done once, while the language will be used to write code again and again. If it doesn't negatively affect the language users then sure, change it to make verification easier.
- monocasa 9y agoYou need to reverify when you change the code too. Otherwise you could make the same arguments about testable code.
- nine_k 9y agoIt depends on the cost of a defect. A language used for aircraft control software is going to have much stricter requirements for static analysis that a language used to create a website with cute pictures of kittens — even if happens to be the very same language.
- emn13 9y agoYou're not verifying a language, you're verifying a program (or some part of one). Sure- that part in this instance may be implementing a language standard library, but who cares? That program also has tests, docs, types and all the other things people use to convince themselves of correctness. It really is like unit testing. There too you could make the argument that in some cases untestable code might be worth it if the alternative is an api that's hard to use. And there too an api may well be used many orders of magnitudes more frequently than it is changed. I think you have to decide that on a case by case basis (at least, I can't think of any convincing general argument there).
- weberc2 9y agoThis is a good question. I'm inclined to say that the value proposition for testing is better than for verification. First of all, if your unit is hard to test, it is likely to cause other issues, but probably more importantly, testing finds a lot more bugs per unit effort than formal verification. That last point is based exclusively on my intuition and it could well be wrong--it would be good to hear from people with more experience with both testing and formal verification. Also, now that I think about it, the value proposition isn't fixed for all applications. Testing is the better value proposition if you need to catch the easiest 95% of your bugs (arbitrary number for example purposes), but if you need to catch 99.999% of your bugs, the testing effort may likely be much greater than the formal verification effort. That said, open source projects like Rust get tons of testing for free by virtue of being very, very popular, so I'm not sure how to weigh one against the other.
- currymj 9y agopeople often mention forcing refactoring/rewrites as a benefit of unit testing, that you end up with code that is actually better in testing-unrelated ways. this is true in my experience. i wonder how true this is of formal verification? especially in a language like Rust that has a fairly fancy type system?
- zerb 9y agoYeah, I'd say there's a huge overlap in attributes of testable code and reasonable code.
- monocasa 9y agoThat's sort of the trend of the industry for the past 50 some odd years, towards design for verification. First re-entrant code, then removing globals entirely, then splitting your dependencies out for testing, and recently there's been a bigger push towards formal verification.
- tom_mellior 9y ago> But he never mentions any other benefits or justification for changing how it works. I read "it lets me write a program that has a data race", accompanied by a program that has a data race, as saying that the bug is that a language feature meant to provide mutual exclusion does not provide mutual exclusion. In a language one of whose main selling points is "you always get mutual exclusion". How is this not a bug? The benefit of changing this bug is that the guarantees Rusts makes to programmers are actually guaranteed.
- khuey 9y agoIt's absolutely a legitimate bug.
- dmix 9y agoI was specifically referring to the 3rd comment on the Github issues page, not the first comment which mention a race condition which the eventual commit addressed > His third comment fits this category well. And even then I was only talking about the language he used, aka the justifications and rationale he proposed, which seemed entirely around being difficult to verify formally, rather than mentioning any real hypothetical 'bug', security flaw, or architectural downside.
- tom_mellior 9y agoFair enough about the particular Github comment, but even there I think you are wrong. The architectural downside is being unable to understand a program you have written: "However, if the type does not have an explicit impl for Send/Sync, I don't know how to even figure this out -- I would have to chase all types (including safe ones, and across all abstractions) of all fields recursively and then check when they are Send/Sync... that's way too error-prone." This doesn't just talk about his particular proof tool being unable to understand this. It's about any Rust developer being unable to easily understand the types used by their programs, using only standard library constructs. (If anything, this should be easier for tools than for humans.)