10 ms·
Some notes on Rust, mutable aliasing and formal verification
- Jaxan 3y agoI read the linked article by Boats and found it great. I was really amazed by the 50-years old quote by Hoare, it’s still relevant and very well put.
- Animats 3y agoThat's a good article. Having worked on program verification in the past, Rust looks like the most useful modern language to which formal methods can be applied. Rust's rules eliminate so many of the cases that are hard to formalize. Big remaining problems involve deadlock analysis, both in the thread sense and in the Rc/borrow sense. Those are somewhat equivalent. I'd like to have static deadlock analysis in Rust. If you had that, I think you could get safe back-pointers, too. If you can prove that all borrow and upgrade calls can't fail, you can eliminate most reference counts. That gives you free interior mutability when that's possible. The author's comment on provers is interesting. The big problem with theorem provers is that they're developed by people who like to prove theorems. They're in love with the formalism. This leads to a UI disconnect with programmers. You can knock off most things you have to prove with a SAT solver. But you'll need something heavier for the hard problems. Coq is too manual. The author thinks ACL2 is too functional. Not sure what to do there, but I've been out of this for decades. Machine learning may help in guiding theorem provers. Most programs aren't that original in terms of control flow and data usage. So inferring a proof plan from other code may work. ML systems can't be trusted to do the proof, but may take over guiding the process.
- rtpg 3y agoI think that Coq/Agda/Lean and friends are really going to be the winners in the proof space. Interactivity is a pretty good model for the feedback loop, and they're systems that exist and work, without a lost of asterisks. The biggest thing I think these tools are missing out of the box is, basically, "run quickcheck on my proof for me". It's too easy to have some code, and try to prove some property that isn't true, and rip your hair out thinking "why can't I get the proof working!" If halfway through your proof you end up in a thing that seems nonsensical, it would be nice for these tools to just have a "try to generate a counter-example from here" command that spits out a thing. Proofs are so path-dependent, and it's not trivial to do in general. But I think they are all very close to greatness, and every time I've gone through the effort to formally verify a thing, it's been pretty illuminating. Just... if you're trying to prove some code, the process should take into account the idea that your code might be buggy.
- pjmlp 3y agoI also quite like Idris, the problem with these languages is that they require being a Mage level 10, while most folks are still getting around magic exists.
- rtpg 3y agoI found the onboarding to be super rough… I think it’s the sort of thing where you really want to do a full day workshop on it to get started. The interactive elements really can’t be done justice in looking at readme’s or textbooks alone IMO
- Tainnor 3y agoIn my case (Lean), I've been getting a lot of help through the Zulip community. There's a dedicated #new_members stream where anybody can ask total beginner questions. It's quite humbling actually when you have someone like Kevin Buzzard answering your noob questions. I'm sure other solvers (Coq, Idris, etc.) also have online communities where you may be able to ask questions.
- Tainnor 3y agoI'll have to agree with this. In particular, there always seems to be some stage where you'll have to think carefully about how the simplifier works exactly, about different types of equality (syntactic vs. definitional vs. provable), etc. And changing internal representations of objects will also mean that old proofs might not compile anymore. And tactics are often rather opaque blackboxes. I say this as a non-expert who has been enjoying writing some Lean recently and has previously also written some Coq and Idris.
- kccqzy 3y agoMost programmers don't have enough previous experience proving things so this is unnatural for them. It is sadly impossible to require programmers to have been a math major to get them the mental facility to work with these languages.
- 3y ago
- xavxav 3y ago> You can knock off most things you have to prove with a SAT solver. But you'll need something heavier for the hard problems. Coq is too manual. The author thinks ACL2 is too functional. Not sure what to do there, but I've been out of this for decades. Agreed, though I think Lean is making big progress in the UX front of ITP verification through its extensive meta-programming facilities. My issue with these tools applied to verifying external languages like Rust, is that the proof is not written in the target language, forcing your developers to learn two languages. I have recently been thinking about what a "verification aware Rust" would look like, colored by my experience writing Creusot, the work on Verus and Aeneas and my time in the lab developing Why3. I think building such a language from the ground up could provide a step change in ease of verification even from Rust, particularly with regard to those "hard parts" of the proof.
- GregarianChild 3y ago> "verification aware Rust" ... building such a language from the ground up could Could you sketch in a few bullet point what you think is missing and how to fix the gaps? In my experience a core problem is that adding rich specifications slows down rapid evolution of programs, since the proliferate transitively along the control flow graphs. We can see this most prominently with Java's checked exceptions, but most effect annotations (to give an example of simple specification annotations) suffer from the same cancerous growth. This is probably at least partly intrinsic, but it could be improved by better automation.
- xavxav 3y ago> Could you sketch in a few bullet point what you think is missing and how to fix the gaps? Not yet, I am planning on writing some blog posts about it but there are still enough fuzzy points I don't want to share yet. > ... since the proliferate transitively along the control flow graphs. ... suffer from the same cancerous growth. This is one of the biggest and most difficult issues of verification, I fully agree. The 'promise' of verified code is that you don't need to understand the code, you can just look at the smaller, higher-level spec, but right now verified code has a specification & proof overhead > 1, it needs to drop to < 0.1 for it to become economical.
- zozbot234 3y agoThe issue with SAT/SMT for program verification is it's too much like dark magic. It's acceptable if you can have it generate a proof certificate for the properties you care about and commit these with the Rust source code - but AIUI, generating usable proof certificates for 'unsat' proofs is a hard problem where you might be better off writing out the proof interactively.
- MaxBarraclough 3y ago> Machine learning may help in guiding theorem provers Interesting idea. There would be real upside where the machine learning system gets it right and guides the prover to a valid proof, and little downside if it gets it wrong. (The prover won't derive an invalid proof, it will just fail to derive a valid one.) I don't think there are many applications of machine learning that have this property.
- eru 3y ago> (The prover won't derive an invalid proof, it will just fail to derive a valid one.) I don't think there are many applications of machine learning that have this property. Don't basically all applications of any heuristic solver to NP problems have this property? (Including problems that are only in NP, because they are also already in P.)
- MaxBarraclough 3y agoYes, sure, I could have phrased that better. There are no doubt many possible applications of the idea. The recent headline-grabbing applications of machine learning tend not to be like this.
- eru 3y agoYes, agreed. Though even amongst the recent-headline-grabbing stuff there are some areas that you can improve at by the equivalent of AlphaGo's self-play. Basically, when you have a slow and expensive option to use a weaker version of your system to produce better decisions / smarter data, and then use those to train the system.
- klabb3 3y ago> Big remaining problems involve deadlock analysis, both in the thread sense and in the Rc/borrow sense. Those are somewhat equivalent. I'd like to have static deadlock analysis in Rust. If you had that, I think you could get safe back-pointers, too. If you can prove that all borrow and upgrade calls can't fail, you can eliminate most reference counts. That gives you free interior mutability when that's possible. I’m not a formal verification guy, but I don’t think locks in the traditional sense is helpful. No compiler will give you anything useful to work with wrt locks. You just accept and live with the danger. In fact, locks and ref counts are runtime constructs in Rust. Imo it “goes against” even Rust’s own strong principles of single ownership - these things are shared mutable state. Arc broke Rusts RAII model so much that they had to remove scoped threads (which needs destructors to run before end-of-scope). Anyway, rust aside. Global refcounts have cyclic and leak issues that again are global. I don’t think we can necessarily get rid of them, but I do believe containing them is better, eg with arena-style scoping. As for locks my gut feeling is we need an asymmetric data structure, for instance a channel. In eg Go you can break a channel into sender and receiver, and have the sender goroutine do `defer close(ch)` which is guaranteed to run if the rest of thread finishes, even if there’s a panic. Doesn’t necessarily have to be channels but separating the roles (reader-writer / producer-consumer) is much easier to reason about, and that probably helps formal analysis too.
- zozbot234 3y agoScoped threads have been reintroduced to Rust since ver 1.63, released in August 2022. There's also significant interest in introducing true linear types to Rust, where destructors would be guaranteed to run - however the changes required for that are large and will probably have to be introduced in a new Rust edition.
- the_mitsuhiko 3y ago> however the changes required for that are large and will probably have to be introduced in a new Rust edition. Or more likely: never. The odds of linear types making it into the language are non existing from what I can tell.
- nextaccountic 3y agoF* is this mythical language that proves stuff automatically (with an SMT solver, more powerful than SAT), but still lets you prove manually if the automated solver fails The crypto routines in Firefox and Wireguard is actually written in F* (or more specifically Low, a low level DSL embedded in F), not in Rust, and is fully verified https://project-everest.github.io/ https://project-everest.github.io/ https://mitls.org/ https://mitls.org/
- throwaway17_17 3y agoI really like that we are now two posts deep from a quote from a ~1973 paper by Hoare. I posted a really long comment in the original boat’s article’s HN thread pointing out that skewing the quote towards a Rust-centric view (while understandable given boat’s history with the language) was an artificial narrowing of the scope of Hoare’s critique. Now Grayson has taken that narrow slice and used it as jumping off point to discuss a few interesting areas/design-points of Rust. While I still think my comment was correct, the ensuing discussion by Grayson in this blog were more than sufficient to overcome any technical gripes with the inciting article.
- throwaway17_17 3y agoMy original comment about boat’s post citing the Hoare paper: After the opening quote by Hoare and a quick intro paragraph, the author says 'What Tony Hoare was writing about when he said that references are like jumps was the problem of mutable, aliased state.' withoutboats is a well known Rust developer, so I guess this assumption about Hoare's quote should not be a surprise. However, I don't see the text of the quote as reinforcing that perspective. I can see an argument for the article's extrapolation, taking Hoare's seemingly more general lamentations about the semantic existence of references (a semantic group containing at least 'reference, pointer, or indirect address into the languageas an assignable item of data') and then applying to the Rust model of non-aliased, mutable state as an attempt to circumvent the problems Hoare is addressing. But this argument is an attempt at taking a narrowly scoped perspective on a problem, correcting that small slice of the greater problem, and then announcing the entirety of the problem no longer exists. Like I said, understandable why the article would take this direction, I just don't think it truly addresses the totality of Hoare's critique of references as an undesirable semantic abstraction. The title of the section withoutboats has quoted and the first sentence are unfortunately left out of his selection: "8. Variables One of the most powerful and most dangerous aspects of machine code programming is that each individual instruction of the code can change the content of any register, any location of store, and alter the condition of any peripheral: it can even change its neighboring instructions or itself. Worse still, the identity of the location changed is not always apparent from the written form of the instruction; it cannot be determined until run time, when the values of base registers, index registers, and indirect addresses are known." [This paragraph is essentially acknowledging that low-level machine code gains its computational power from unlimited ability to alter the state of computation] Also, the ... following the quote's second paragraph omits the following: "For example, in ALGOL 68, the assignment x : = y; always changes x , but the assignment x: = y+l; if x is a reference variable may change any other variable (of appropriate type) in the whole machine. One variable it can never change is x!" [This quote, which was removed, makes it explicit that Hoare is addressing the mere existence of references] Both of the omitted sections tend very strongly toward Hoare's actual critiques being the semantic concept of references in high level languages being problematic, not merely mutable state. There is some natural extension of Hoare's discussion of references as means of assignment, which does lead to the 'spooky action' occurances. However, following this section of Hints on Programming Language Design, Hoare talks for a bit about structured programming, scope, and parameter importance. Discussing that without references, programmers have disjoint names for semantic objects and those are only altered/mutated by passing the sole existing object to a procedure as a parameter and having it passed back. Overall, the TL;DR may be negatively stated as Rust developer gonna view things through a Rust-y lense. However, I think that is an incorrect reading. withoutboats skipped a crucial step in his going from Hoare's critique of referencs, they went directly from the text to an interpretation of the critique focused on aliased, mutable state. There is some discussion to be had about Hoare's assumptions of a single semantic object existing in a one-to-one correspondence with a disjoint source code name, especially in the context of multi-processor and networked programming prevalent in 2024. While I think that a more general solution to Hoare's problem exists and acknowledge Rust's attempts to at least tame a portion of the problem, I don't think any language has 'fixed' this issue.
- akira2501 3y ago> The typical Rust program has either no refcells, or a very small number, just as it has either no unsafe code or a very small amount Really? How are we quantifying this?
- littlestymaar 3y agoI don't think anyone has actual measurements on this, but at the same time anyone who's written and read a significant amount of Rust[1] can tell you that unsafe and RefCell aren't something you encounter every day (or even every year when it comes to RefCell). [1] for my part I've been doing it full time for the past 7 years, and also teach Rust at university.
- kalkr 3y agoWhat about Arc<Mutex<T>> ?
- roca 3y agoIn six years I wrote a lot of the 200K lines of Rust for Pernosco --- a fairly sophisticated application server for a SaaS debugger. There are 40 instances of the string 'Arc::new(Mutex::new('. A lot of them are shared caches and other innocuous things. There are 22 occurrences of 'RefCell::new('. There are other uses of Arc, and other uses of Mutex, but fundamentally the system has not collapsed into an arbitrary graph of mutable data. Of course, one's mileage can vary. Most of our system is designed to be stateless at the top level, which helps.
- littlestymaar 3y agoIt's indeed more common than RefCell, but it's not like you're using them everywhere either (as using multiple locks is a recipe for deadlocks, so you should always be very mindful about how you use shared memory between threads). I've run a quick analysis on the 1,145,666 lines of Rust code (excluding comments and blank lines) I have on my computer, which belong to several code bases I've worked on over the past few years (professional proprietary code, side projects and open source projects I just cloned to fiddle with), and here are the results: - unsafe: 8247 matches, 1 every 138 lines (though keep in mind most of those aren't about mutable aliasing at all, like FFI or SIMD intrinsic) - RefCell: 252 matches, 1 every 4546 lines - Arc<Mutex<: 199 matches, 1 every 5757 lines I think that's fair to say that “The typical Rust program has either no refcells, or a very small number, just as it has either no unsafe code or a very small amount”
- shivanshu120 3y agoThis is very good article for rust
- kzrdude 3y agoWritten on May 15th 2024 which was the 9th anniversary of Rust 1.0
- pron 3y agoI usually love Graydon's posts, but this one -- like many articles about formal methods -- may be misleading for most readers unfamiliar with the field. It's a little like reporting an order of magnitude improvement in transmuting lead into gold without mentioning that there are 29 further orders of magnitude to go before the method is cost-effective in practice. Does no aliasing make formal verification significantly easier? Absolutely! Does it mean we can expect a practical and cost-effective way to verify real world programs? Not even remotely. Yes, some programs, circuits, and program components are formally verified every day, but they are the exception rather than the rule; they are relatively very small and they are constructed in particular careful ways. Nice properties that allow local reasoning about some other properties are important but do not materially affect the way we can assure the correctness of mainstream software with sound methods. A reasonable, real-world program that would take a million years of effort to verify without such properties will only take 100,000 years of effort to verify with them. That is good and it is even useful in practice because a program that would take a year to verify could now take a month -- making it actually cost-effective -- only the number of such programs to begin with is vanishingly small in the grand scheme of things. A program in a language with no heap, no pointers, no integers -- only boolean variables -- and no loops larger than two iterations (the language is nowhere near Turing complete) cannot be practically verified (by reduction from TQBF). Not in theory, not in practice, and there aren't even heuristic methods that cover many real world instances of such programs (of course, some such programs could happen to be easily verifiable). It can be made to work for some properties (like memory safety) -- we say that we can make these invariants inductive or composable -- but it turns out that that's not nearly good enough for what software needs. Back in the seventies and eighties, and even nineties, the hope was that while the "worst case" complexity of verifying programs was known to be intractable, perhaps certain local guarantees and structures employed by programming languages could move us away from the worst case. It has since been proven to not be the case. Even the hope that programs people actually write are far enough from the worst case for good heuristic methods to emerge, and even that now seems to not be the case. Many years ago I gave a talk covering the relevant findings: https://pron.github.io/posts/correctness-and-complexity https://pron.github.io/posts/correctness-and-complexity The main result is that the verification most interesting properties that we'd like to verify does not compose. I.e. if we can prove a property for components P1...Pn, then proving that property for P1 ○ ... ○ Pn (where ○ is some composition such as a subroutine call or message passing) does not just grow super-polynomially in n (which would be good!), but super-polynomially in the size of each of the components, i.e. it would be just as hard to prove if everything was not decomposed. I.e. correctness does not decompose. Yes, some important programs can be soundly verified and various local properties can make that easier, which is useful but because of software is growing much faster than the scale of effective formal verification and because we've learned more results about the complexity of software verification, end-to-end verification of "ordinary" software appears further away today than it did 50 years ago. That is why there's a shift in research of software assurance toward unsound methods. A focus on soundness does not, I believe, help the cause of more correct software, but distracts away from more techniques that have proven more fruitful. This gap between "we can verify quite a bit" and "what we can verify is a drop in the ocean" -- both of which are true at the same time -- is something that is often missing from discussions of formal methods.
- mst 3y ago> One way to look at reference counting is as a sort of eager, optimized form of garbage collection that works in the case that you have strictly acyclic data (or can tolerate leaking cycles). It's interesting to note that python operates with the refcounting + tracing hybrid described (and I know of production deployments where they force the tracing collector to e.g. only run once every N requests because python's never got that fast either). perl, meanwhile, is pure refcounting but has weak references so you can make data acyclic from a refcounting POV at the cost of having to pay attention to which parts of the cyclic structure you keep references to (and for cyclic object graphs there are some tricks you can pull to move the weak link around so you don't have to pay such attention, but that would be a whole comment on its own). koka does refcounting in theory but tries to lift as much of it to compile time as possible in practice, plus if you do e.g. 'y = x + 1' and x has only a single reference to it and is guaranteed to not be used afterwards, it re-uses the storage for y and so can do in-place mutation. nim, meanwhile, offers something called ORC, which is automatic reference counting plus an implementation of Bacon+Rajan's Recycler algorithm which is designed to collect -only- cycles in an otherwise refcounting based system and as such is really rather fast at doing so. Coming back to Rust: There's a stop the world Recycler implementation (rather than concurrent as intended both by the original paper and the author's future plans if the itch returns) here - https://github.com/fitzgen/bacon-rajan-cc https://github.com/fitzgen/bacon-rajan-cc - released as the bacon-rajan-ccc crate from this fork - https://github.com/mbartlett21/bacon-rajan-cc https://github.com/mbartlett21/bacon-rajan-cc - and the README for those contains an Alternative section linking to other experiments in the same area. (I've yet to play with any of the rust versions but love Recycler sufficiently as a concept that I suspect if/when I encounter a situation where it might help I'll be going back and doing so) If you're having trouble finding the Recycler papers, I stashed a copy of each under https://trout.me.uk/gc/ https://trout.me.uk/gc/ (and if you're a similar sort of strange to me, you might also enjoy the ones stashed under https://trout.me.uk/lisp/ https://trout.me.uk/lisp/ ;)
- zozbot234 3y agohttps://github.com/chc4/samsara https://github.com/chc4/samsara is also worth looking into, implementing the same concurrent GC algorithm for Rust. A C++ implementation is available at https://github.com/pebal/sgcl https://github.com/pebal/sgcl .
- titzer 3y agoI don't really get the gushing over this post in the comments, it papers over entire fields of program analysis in a single breath. While I like Graydon and respect his point of view, this paragraph is hopelessly over-simplified. > Conversely, languages that have a GC have unfortunately often not felt it necessary to bother having strong local reasoning support. Java for example has a GC and also uncontrolled mutable aliasing, so weak local reasoning and consequently more-challenging formal verification. If you write to an object in Java every other variable referencing that object "sees" the change, so any logical formula that held over all those variables might be invalidated by the write unless you use some fancy method of tracking possible write-sets or separating the heap. First of all, there have been several languages that regions in their type system and are still backed by GC, so this is a strawman. Take, for example, Pony. Second, there is an entire field of pointer analysis and escape analysis that can and does infer uniqueness and reasons about whether two references can be aliases. Third, the whole point of static types is to slice apart the heap into independently non-aliasing parts using this technology called "classes" and "fields". We're not talking about JavaScript here, I think we should stop pretending like Java and C# and Scala and a bazillion GC'd languages don't have local reasoning about mutable state.
- zozbot234 3y ago> ...there is an entire field of pointer analysis and escape analysis that can and does infer uniqueness and reasons about whether two references can be aliases. You can't do this automagically in the general case, you really do need something much like separation logic. (And of course the Rust borrow checking semantics can be seen as a simplified variety of separation logic.) Classes and fields don't give you completely local reasoning about mutable state, because class/object A can end up depending on the mutable state of class/object B. And class inheritance as found in Java adds all sorts of further complexity of its own, especially as programs evolve over time.
- mrkeen 3y ago> I think we should stop pretending like Java and C# and Scala and a bazillion GC'd languages don't have local reasoning about mutable state. Pop-quiz: what does this print out? void myMethod(final Map<String, String> map) { map.remove("key"); int oldSize = map.size(); map.put("key", "val"); int newSize = map.size(); System.out.println(newSize - oldSize); } EDIT: Apologies, I misread your double negative. Nope. I reread it again and I'm still thoroughly confused. Java does have local reasoning, as opposed in particular to JavaScript, which does not?
- eggy 3y agoI just posted a relevant comment on the F* article a minute ago. I would subjectively prefer F* because of syntax over Rust, but for the show control software we are developing, we are going with Ada/SPARK2014. Rust needs a formal, published standard like the other legacy PLs to draw the same crowd currently using Ada/SPARK2014 and the formal verification tools and some real-world safety-critical, high-integrity applications in its back pocket. "I prefer F#/F* syntax, but I had to go with Ada/SPARK2014 for the safety-related control systems I am trying to verify formally and use for high-integrity applications. Rust is making some inroads with AdaCore and Ferrous Systems partnering on providing formal verification tools for Rust like they do for Ada/SPARK2014, but Rust still doesn't have a published standard like C, Common Lisp, Prolog, Fortran, COBOL, etc. Plus, the legacy is immense for Ada and SPARK2014."
- bionhoward 3y agoI just wish we could write simpler compile time type guard kind of things in a more simple way, because when the trait bounds metastasize it can get hard to read these type level programs “Where <<<T as F>::Output as G>::Output as H>::Output: HList<Head = A, Tail = B> + Z type Output = <<<T as F>::Output as G>::Output as H>::Output;” Put some Cons<Cons<Cons<U8, Nil>>>> in there and then realize numbers like U8 (from TypeNum) is itself a nesting of Cons<Cons<Cons< of binaries and it just winds up feeling like you’re looking at a massive nesting of <<<>>> Consequently you can make progress in this area and get it to verify what you want, but the error messages can be massively complicated and divergent from the way the human developer writes their code (because of the “types vs values” difference producing wildly different error messages which are hard to customize) and the implementation can be a massive pain in the ass. Developer experience here is surprising because it’s not “just functions” but rather combinations of functionalities with certain generics and associated types. You want to write a runtime style check but execute it at compile time, but to make that happen requires quite different code (in my experience) All this to say, perhaps making type level comptime rust more simple and functional and readable is ultimately what would enable a lot of these formal analysis projects to provide a good experience for their maintainers and users TLDR, wtb “comptime” Rust! P.S. are we ossified on Pin<&mut Self> Future ? I wish I could tinker with different underlying implementations of async/await but no clue how to get started
- slushy-chivalry 3y agoI never get tired of reading articles about typestate pattern
- worik 3y agoI am impatient with formal verification of programmes. Proving that a programme correctly implements a specification is interesting theoretically but of little practical use Correct specification is as hard as correct programming, so the difficult problems are not solved, they are moved. There are practical use cases for formal methods, but they are rare to encounter
- nyssos 3y ago> Correct specification is as hard as correct programming A complete specification, sure, but that's not really the goal. The things we want to prove are generally just a few key properties: this function always terminates, that one always returns a sorted array, etc. And once you can do that you can impose these things as preconditions: e.g. you must demonstrate that an array has been pre-sorted before you pass it to this function.
- worik 3y agoYes. I am not against all formal methods. Pre and post conditions for loops etcetera. When they are useful they should be used (in many cases they are built in: `for i = k; i < l; i++` has a precondition, a loop condition, and an action all in one statement.) It is the idea, that was very hot thirty or so years ago, that by using formal specifications and rules of inference we could eliminate bugs.