Formal Verification Is Not Verifiable

(alperenkeles.com)

29 points | by zdw 2 days ago

3 comments

  • mjb 3 minutes ago
    > For any first-order universally quantified property of a program we can write as a property-based test, I think we will be able to generate proofs at the binary level, against architecture models that have themselves been validated by millions of hours of testing. The challenge of extending this to multi-threaded programs, distributed systems, [..] will be years more of work we must conduct across thousands of verification engineers and researchers.

    I expect the distributed and concurrent version of this will come more quickly. In fact, I would be willing to bet that by EOY 2030 the bar mentioned here of single threaded software will be met for multi-threaded and distributed systems under non-adversarial failure modes. This is significantly more aggressive than most in the field (and I'm field-adjacent at best), but given the rate of progress I think it's actually a rather conservative bet (the really aggressive bet would be "July 2027").

    > The more "bouba" a piece of software or a given layer is, the harder it is to talk about what makes it correct. We can always talk about some correct attributes, but to talk about a uniform notion of correctness is not possible in my opinion.

    I largely agree with this, although I do think we're going to see more progress than expected in quantifying (and therefore verifying) usability and "look and feel" aspects of software. The risk is that this happens in a "narrow" way that forces all 'correct' software to look and feel the same, because that sameness correlates with the learned definition of 'correct'.

    > In solving these challenges, I think random testing and random exploration in general will prove to be invaluable tools. A test execution is a measurement, so it produces information about the real underlying system that we can leverage to falsify, harden and validate the models we use for verification. The verifiability of testing will continue to be a huge driving force of its adoption as well as a gateway into the rest of formal methods, and maybe it will even help us trust when we hear software is "formally verified" instead of wondering what was left out or when someone will find a bug in there.

    Strongly agree with this.

  • alpaylan 33 minutes ago
    Author here, happy to chime in!
  • ky3 48 minutes ago
    > It is normal for software to have bugs!

    "... [B]egin with cleaning up our language by no longer calling a bug a bug but by calling it an error. It is much more honest because it squarely puts the blame where it belongs, viz. with the programmer who made the error. The animistic metaphor of the bug that maliciously sneaked in while the programmer was not looking is intellectually dishonest as it disguises that the error is the programmer's own creation."

    EWD 1036: On the cruelty of really teaching computing science [0]

    > [That it is normal to have bugs] is not an indictment of software engineers but the result of the inherent complexity of software; a complex software system deals with not millions or billions, but trillions of different types of events.

    To which Dijkstra has this to say about the source of the complexity:

    "Many software projects carried out in the past have been overly complex and, consequently, full of bugs and patches. Mainly the following two circumstances have been responsible for this:

    1. dramatical increase of processor speeds and memory sizes, which made it seem as if the sky were the limit; only after the creation of a number of disastrously complicated systems it dawned upon us, that our limited thinking ability was the bottleneck;

    2. a world that in its desire to apply those wonderful new machines became over-ambitious; many programmers have yielded to the pressure to stretch their available programming technology beyond its limits; this was not a very scientific behaviour, but perhaps stepping beyond the limit was necessary for discovering that limit's position."

    EWD 648: "Why is software so expensive?" An explanation to the hardware designer. [1]

    I hazard a third: a receiving population geewhized and subsequently hoodwinked into accepting low standards as an inevitable trade-off for all the societal benevolence that software has wrought.

    [0] https://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD103...

    [1] https://www.cs.utexas.edu/~EWD/transcriptions/EWD06xx/EWD648...