4 ms·
> how do we know the example TCP RFC English Language description isn't logically flawed? We don't, in the general case. In the specific case of TCP, the RFC h
by woodruffw 4y ago
> how do we know the example TCP RFC English Language description isn't logically flawed?
We don't, in the general case. In the specific case of TCP, the RFC has had many errata over the years[1] (many of which are logical errors).
This is a recurring problem in formal verification: you verify with respect to a particular description of the system or protocol, which itself may be either ambiguous or fail to reflect actual implementations. You can tighten that by verifying with respect to a formal definition, which can eliminate the ambiguity, but only pushes the trust as far as the proof generator and verifier themselves. You then maybe have multiple independent proof systems arrive at the same conclusion to strengthen your belief in the result, but at that point you're doing differential testing and not formal verification.
[1]: https://www.rfc-editor.org/errata/rfc793 https://www.rfc-editor.org/errata/rfc793
- sbf501 4y agoThat's what I was getting at with the second sentence in my post: we can verify the code matches the spec, but not that the spec is flawed. So this verification is what CPU designers do: they create a RTL (HDL, VHDL, Verilog) and then a circuit (gates) and then Magma or Cadence or Synopsys tools formally verify that the logic in the behavioral model matches the implementation model. However, if the microarchitect had a brain fart, the RTL is bugged to begin with. I was hoping this could go backwards one step further and give the microarchitect/RFC-editor a swift kick in the pants. :)
- drpixie 4y agoI think that's the real advantage of RISC architectures - a small spec leaves less space for problems. Not no space, but less space.
- rurban 4y agoYes, but the various HW bugs and exploits, e.g cache leaks and poisoning - Spectre, Meltdown, ..., are not handled. Also not in the mentioned and formally proven crypto libs.
- sbf501 4y agoAdvantage over what? The idea that RISC is somehow simpler went the way of the dinosaur 30 years ago. The ISA does not define performance, that is the microarchitecture, which is where all of the engineering effort is spent. You can have the classic ISA of the Turing Machine that we all learned about in comp-sci 101 classes: "Load/Store/Add/Compare/Jump" and it would be simple but dog-ass slow. Not to mention open to all sorts of attacks and exploits (buffer overflows, stack smashing), and meta attacks (side-channel), or Goedels incompleteness. The uarch is where the action happens.
- drpixie 4y agoWe were talking about correctness. RISCs by definition have simpler architectures that CISCs - that's what makes them RISCs. And simpler architectures leave less room for confusion/bugs/faults in the architecture, irrespective how they are implemented.
- deterministic 4y agoNon-proven correct code doesn’t even have specs you can test the code against. So comparing non-proven code without a formal spec with code that has a formal spec and an end-to-end proof chain from spec to machine code, and then saying they are equally likely to be buggy is frankly ridiculous.
- drpixie 4y agoYes. Looks like it's back to the 1960s, 70s, 80s, ... You found a parser that you've formally verified won't break. Great, I've heard that before. The far bigger part of the problem is the spec - writing a formal spec is (for practical purposes) a similar process to writing a program, and similarly bug-prone. It's nice to have a clearly defined spec language, but that doesn't stop bugs/fault/problems and (by Gödel) can't stop a determined fool (fools are just too ingenious)!
- Jweb_Guru 4y agoOkay, so go break it, since it's so easy :) People routinely say that "a formally verified program is only as good as its specification!" but many fewer people actually go on to demonstrate that they can break said programs, assuming that this is simply "a matter of engineering" which is not in fact the case. I'm also not sure what Gödel has to do with any of this, as most specification languages are not Turing-complete (unless this is some oblique statement about the metalogic in which case... again, show me your proof of false :)).
- jcelerier 4y agoSEL4 is formally verified and still has bugs
- Jweb_Guru 4y agoI see four issues in its issue tracker with the "bug" label. Of these, one seems not to be reproducible on real hardware, one of them looks like a feature request, one of them is a bug in deliberately non-verified code (therefore doesn't say anything about formal verification), and the remaining one involves a hardware-level timeout due to bootloader code taking too long. If you believe this is the error rate of any non formally verified software, that these are exploitable from a security perspective, or that these are indicative of some serious failure in the specification process, you have a very different understanding of software than I do. i.e., I would imagine when people talk about "software is only as good as its specification" they are imagining some dramatic flaw that undermines the guarantees of the system, rather than "I can't use the last 4 KiB in the address space."
- drpixie 4y agoAmusing and very timely https://news.ycombinator.com/item?id=31975507 https://news.ycombinator.com/item?id=31975507
- IshKebab 4y agoHowever you can use formal methods to verify general properties about the specification, so you don't have to fully trust that the specification authors didn't make any mistakes at all. Apparently anyway; I've never done it.