> This allows us to (1) elide modelling the semantics of the high level programming language, we can instead model the semantics of the machine--presumably simpler semantics
ISAs are pretty complicated and reasoning about programs in that context is hard which is why we have high level languages.
> This distinction in terminology used to be a colloquially accepted notion, when we heard "CompCert is a formally verified compiler" or "seL4 is a formally verified microkernel" we assumed the authors did not verify vacuous or trivial properties, because the work of verification itself was held to a high standard that highly affected the reputation of the researcher.
> As of early 2011, the under-development version of CompCert is the only compiler we have tested for which Csmith cannot find wrong-code errors. This is
not for lack of trying: we have devoted about six CPU-years to the task. The apparent unbreakability of CompCert supports a strong
argument that developing compiler optimizations within a proof framework, where safety checks are explicit and machine-checked,
has tangible benefits for compiler users.
At my work we've extended this to CPU millennia. I hasten to add this of course doesn't rule out the possibility of poorly formed assumptions in the semantics etc (it's empirical after all) but it helps to build evidence that we have the theorems and semantic design right. More generally differential testing of this sort offers a possible way forward to build evidence in favor of theorem statements beyond expert examination.
> Every discussion of formal verification must come with a list of caveats, a precise understanding of what is trusted, what is proven and what is not.
Anyone that seriously participates in this work practices this. The whole community. More importantly this is precisely the point of writing down a theorem so that we can closely examine the assumptions. To abuse the CompCert example yet further it's now entirely possible to draw the envelope of assumptions, which are many for a non-toy compiler: https://arxiv.org/html/2201.10280v2.
Last note, I like the kiki bouba diagram if only because it evinces the problematic "round cow" assumption and how that doesn't pan out for real software.
Almost all of the ISA modeling I have seen is done on Arm where there is a published model, or occasionally Risc-V. No one seems to formally model x86!
As best I can tell the article wrongly conflates Rices Theorem with the idea that one can’t prove something about the small program generated by Yedidiya and Aaronson but that’s not what Rices Theorem tells us. Instead it tells us that we can’t come up with a general method to determine yes or no correctly for all programs whether a program reaches a given point.
For a given program and a one off proof one can prove many things or if we over approximate by assuming loops terminate we can prove many things soundly with the risk of rejecting programs that are sometimes correct (eg type systems).
This may have been a quirk of language or my interpretation though.
Yes, moreover - nobody in practice creates programs that are close to be undecidable, just like no engineer uses nonmeasurable functions, they just assume everything is nicely integrable. (It might be close to true for things like cryptographic functions or pseudorandom generators, but even about these we can usually prove the things we need to know.)
No, no one believes that. Everyone can see that AI is going to change how many industries work completely. The parent is constructing a strawman argument "the reasoning is motivated and that motivation is nostalgia (or similar)".
Lamport’s book and or Hillel Wayne’s are both good. State machines as a specification language has always been pretty approachable and also relatively deep. If you want to get in to proof assistants Software Foundations is great and the delta to understanding Lean from Rocq is pretty small.
A key problem is that compilation operates on an implicit (compiler writers have this in the back of their heads) notion of correctness which is very roughly “preservation of observable behaviors” where “observable” is sequences of system calls and then return value. That is, the final output of a compiler should never add new sequences of observable behaviors.
Security properties on the other hand are very often about the relationship between these sequences. For example we like to say that an external observer/attacker can’t distinguish internal state by the external observations (confidentiality) which requires that two observable traces given different hidden values don’t have different observations from the same starting observable state.
If you’re an LTS nerd you know this difference as trace properties vs hyper properties. Compilers try to preserve the former but not the latter.
Separately there is the problem of “what is observable?” For example, if you include timing in your observable behaviors suddenly the kinds of compiler passes that are able to preserve observations tends to zero rather quickly.
ISAs are pretty complicated and reasoning about programs in that context is hard which is why we have high level languages.
> This distinction in terminology used to be a colloquially accepted notion, when we heard "CompCert is a formally verified compiler" or "seL4 is a formally verified microkernel" we assumed the authors did not verify vacuous or trivial properties, because the work of verification itself was held to a high standard that highly affected the reputation of the researcher.
CompCert has also had extensive empirical evaluation to vet the theorems. Famously the CSmith paper (https://users.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf) has this rather choice quote:
> As of early 2011, the under-development version of CompCert is the only compiler we have tested for which Csmith cannot find wrong-code errors. This is not for lack of trying: we have devoted about six CPU-years to the task. The apparent unbreakability of CompCert supports a strong argument that developing compiler optimizations within a proof framework, where safety checks are explicit and machine-checked, has tangible benefits for compiler users.
At my work we've extended this to CPU millennia. I hasten to add this of course doesn't rule out the possibility of poorly formed assumptions in the semantics etc (it's empirical after all) but it helps to build evidence that we have the theorems and semantic design right. More generally differential testing of this sort offers a possible way forward to build evidence in favor of theorem statements beyond expert examination.
> Every discussion of formal verification must come with a list of caveats, a precise understanding of what is trusted, what is proven and what is not.
Anyone that seriously participates in this work practices this. The whole community. More importantly this is precisely the point of writing down a theorem so that we can closely examine the assumptions. To abuse the CompCert example yet further it's now entirely possible to draw the envelope of assumptions, which are many for a non-toy compiler: https://arxiv.org/html/2201.10280v2.
Last note, I like the kiki bouba diagram if only because it evinces the problematic "round cow" assumption and how that doesn't pan out for real software.
reply