Developing Provably-Correct Software Using Formal Methods

<i>some tools such as Verum Dezyne and Quantum Leaps can generate 100% correct source code in C, C++, Java ...</i><p>The input into these tools, from which they generate source code, is therefore, the real program and the real source code. How do they prove that this real source code, from which they generate C,C++, or Java, is &quot;correct&quot;?<p>In fact, this input just constitutes a new programming language -- a DSL -- and the tool is just another compiler or scripting engine. If existing compilers are unprovable, this new compiler is for the same reasons unprovable too. In other words, they did not solve the problem.

It&#x27;s all definitely worth looking into. Anyone trying to start will find Wheeler&#x27;s page [1] much more helpful. I also included a book [2] on using dependent types for certified programming. There&#x27;s also a few examples after of verifications with [3] being pretty cutting-edge in automation &amp; thoroughness. I think we need people to put together a single resource where newcomers can see the various approaches, tools, and practical examples of how to use them. Further, we need to research more on which tools give you the most bug hunting benefit with the least time and expertise. There&#x27;s some research done already but everything in this field is scattered.<p>Another point came up in a similar discussion: we need to focus most of our energy on raising the baseline of correctness for the average programmer. This includes things such as automated test generation, design by contract, and better type systems. The developer should be able to specify his or her intention with the code while the type system or runtime catches most of the errors. Maybe we just need a version of BASIC&#x2F;Pascal with Ada-like safety built-in or similar restrictions on certain constructs. Not sure of the specifics but this is an important problem to solve.<p>[1] <a href="http:&#x2F;&#x2F;www.dwheeler.com&#x2F;essays&#x2F;high-assurance-floss.html" rel="nofollow">http:&#x2F;&#x2F;www.dwheeler.com&#x2F;essays&#x2F;high-assurance-floss.html</a><p>[2] <a href="http:&#x2F;&#x2F;adam.chlipala.net&#x2F;cpdt&#x2F;" rel="nofollow">http:&#x2F;&#x2F;adam.chlipala.net&#x2F;cpdt&#x2F;</a><p>[3] <a href="https:&#x2F;&#x2F;www.umsec.umn.edu&#x2F;sites&#x2F;www.umsec.umn.edu&#x2F;files&#x2F;hardin-icfem09-proof.pdf" rel="nofollow">https:&#x2F;&#x2F;www.umsec.umn.edu&#x2F;sites&#x2F;www.umsec.umn.edu&#x2F;files&#x2F;hard...</a><p>[4] <a href="http:&#x2F;&#x2F;se.inf.ethz.ch&#x2F;people&#x2F;morandi&#x2F;publications&#x2F;prototyping.pdf" rel="nofollow">http:&#x2F;&#x2F;se.inf.ethz.ch&#x2F;people&#x2F;morandi&#x2F;publications&#x2F;prototypin...</a><p>[5] <a href="http:&#x2F;&#x2F;compcert.inria.fr&#x2F;compcert-C.html" rel="nofollow">http:&#x2F;&#x2F;compcert.inria.fr&#x2F;compcert-C.html</a><p>[6] <a href="http:&#x2F;&#x2F;repository.readscheme.org&#x2F;ftp&#x2F;papers&#x2F;vlisp&#x2F;guide.pdf" rel="nofollow">http:&#x2F;&#x2F;repository.readscheme.org&#x2F;ftp&#x2F;papers&#x2F;vlisp&#x2F;guide.pdf</a><p>[7] <a href="http:&#x2F;&#x2F;research.microsoft.com&#x2F;pubs&#x2F;122884&#x2F;pldi117-yang.pdf" rel="nofollow">http:&#x2F;&#x2F;research.microsoft.com&#x2F;pubs&#x2F;122884&#x2F;pldi117-yang.pdf</a>

(I&#x27;m the author of the original post.) Model-checkers don’t prove that a <i>program</i> is correct, only that the logic in the program’s abstracted and simplified communications&#x2F;state <i>model</i> has no inherent race conditions, deadlocks and so forth, i.e. no typical concurrency flaws. Model-checkers don’t “prove” correctness in the mathematical sense (and maybe I should have written “verifiably-correct” instead of “provably-correct”). Rather, model-checkers search for counterexamples to the hypothesis “there are no concurrency flaws in this model”, by exhaustively tracing through all possible distinct execution paths through the model. Amazon calls their models “exhaustively testable pseudo-code”. If no counterexample is found, then we can be sure the model has none of the standard concurrency flaws, and we can be sure that the communications “housekeeping” code auto-generated from the model will have none either. This is a limited yet extremely powerful and valuable aspect of correctness, the hardest kind of correctness for humans to achieve in concurrent software.<p>I believe software engineers can and should start routinely using model-checking on concurrent logic, taking advantage of the machine’s ability to race relentlessly through enormous numbers of execution paths to uncover subtle flaws in logic. Even a small change to concurrent logic can have far-reaching consequences that are very hard for humans to envision. I believe competitiveness and sound engineering practice demand use of model-checkers on concurrent logic.

Okay, so the software is now provably correct.. now what were the costs in doing so, both in additional time pre-writing definitions and other abstractions for the software itself? Also, how does one prove that said software actually meets the business needs behind said software?<p>In an academic environment, or something tied to physical devices, this approach isn&#x27;t a bad one at all... These are settings where software is much more akin to an engineering discipline than it is a craft.<p>In <i>most</i> software development, which are in any number of business environments building&#x2F;adapting or bridging custom software that will run in any number of environments... the additional time that this will take over current approaches will be simply unacceptable. Most people don&#x27;t care if a software is provably correct.. and for that matter, most bugs aren&#x27;t critical in nature, and don&#x27;t lead to end of the world scenarios... since most systems don&#x27;t actually touch personal medical information or financial data.<p>I think on an intellectual level that approaches like this for some systems make a lot of sense... The problem is rarely do you have well defined interfaces&#x2F;algorithms for well defined problems... so, you build your system with provably correct software, then the proverbial moose&#x27;s neck breaks, because you didn&#x27;t know about the moose.