6 ms·

> that is why i said it depends and put "proving" within quotes I feel I need to insist on this point: a design-by-contract methodology using runtime checking

> that is why i said it depends and put "proving" within quotes I feel I need to insist on this point: a design-by-contract methodology using runtime checking may be an effective means of improving software quality, but it certainly isn't proving the correctness of a program. Using the word 'prove' here is just plain wrong. Putting it in quotation marks doesn't help. It simply does not constitute a proof. > It is a very narrow and wrong way of looking at Formal Methods (both Specification and Verification) and one of the main reasons the "ordinary" software engineer gets intimidated and overawed by formal methods and afraid to even approach the subject I'm not insisting on a narrow understanding of formal methods, I'm insisting on proper use of established terminology. I'm all for practical methodologies that benefit software quality without paying the enormous costs of fully applying formal methods. Design-by-contract with runtime checking seems like a reasonable approach. (Static typing is another. Effect-oriented programming might be another.) My point was just about the proper use of the word proof. > Proving Correctness need not be fine-grained and absolute but can be good enough done partially at a gross level at specific stages in a program as needed and done either by hand and/or using tools. A program is proven correct only when the proof is absolute, which implies fine-grained. I'm not opposed to the use of partial proofs or 'good enough' proof-sketches, both of which could be useful in producing high-quality software in the real world, but we should be clear in how we refer to them. I'm not sure about the idea of proving correctness by hand, though. Manually applying a formal model of a real programming language sounds unworkable. If code is well structured, it should be possible for the programmer to reason about it somewhat precisely, like a proof-sketch, but that's not a proof of correctness. > The Programmer plays the role of "theorem prover" when using DbC I don't find this convincing. There's nothing stopping the programmer from failing to notice some error. If you aren't actually doing a proof, just say so. There is no stand-in. > tools exist to map "Design-by-Contract" constructs to "Verified Design-by-Contract" constructs. Right, I hinted at this in my previous comment. SPARK Ada does this. In that case, correctness properties of the program are indeed formally proven. That's a quite different methodology to design-by-contract with runtime checking though, to the point that it almost seems unhelpful to refer to them both by the same name. I've had to be careful to explicitly state design-by-contract using runtime checking this whole time. The deeper distinction here is between testing and formal proof, and design-by-contract can in principle refer to either. > here is a case study Design by contract formal verification for automotive embedded software robustness Have only skim-read but seems somewhat similar to this case-study about SPARK: https://www.adacore.com/tokeneer https://www.adacore.com/tokeneer

GhosT078 1y ago
I have used SPARK Ada myself on a couple of security focused products developed by a team of 10-15 developers. For a long time, SPARK has made use of formal methods practical for real-world software. Effective use does require learning and commitment, but that's within reason. By the time the projects were nearly done, I felt that the SPARK findings always turned out to be correct and that any remaining problems could be traced back to poor or missing requirements, not the implementation itself.
rramadass 1y ago
There is a nuanced but distinct difference in my use of the word Proof as used in Program as a Proof and Proof in a Mathematical Algebraic System which you have missed. They are isomorphic but not exact (hence my using the phrase it depends and scare-quotes around "proving"). The reason is because Mathematics deals with ideal and abstract objects whereas objects in the real world (eg. a computer program) can only map to aspects of the ideal world and not in its entirety. To elaborate; a mathematical algebraic system is a set of objects and a set of operations defined on them. Axioms using those objects/operations are then defined and then inference/reasoning rules using these are defined to prove theorems in the system. There are various techniques for constructing proofs (eg. direct, induction, contradiction etc.) but all of them must map back to the domain of definition of the objects in the algebra to be considered valid and sound in the real world. As an example, the axiom of associativity w.r.t. addition holds absolutely in mathematics when applied to {N, +} where N is the infinite set of ideal integers. But in computing it is not always the case i.e. (a+b)+c =/= a+(b+c) always because a/b/c are constrained/partial finite sets (i.e. int8/int16/int32 etc.) and thus the axiom of associativity will fail when for example, we take boundary values for a/b and a negative value for c (due to overflow/underflow). Thus any proof which uses the axiom of associativity for signed integers in a computer can never be as absolute and general as its counterpart in pure mathematics i.e. everything is Partial. In general, mathematics uses exact Analytical Techniques while computers use approximate Numerical Techniques to solve a problem which is reflected in the nature of their proofs. Coming to DbC, since it is based on Hoare Logic (i.e. an algebra with axioms/inference rules), a Program is written as a series of Preconditions/Postconditions/Invariants with the Programmer acting as the Proof deriver. Thus if a series of pre/post/inv holds at a certain stage in the program (i.e. proof) the next post will hold (barring external cataclysms). The fact that the proof obligation is discharged dynamically at runtime is immaterial. But we may not want that in certain categories of real world programs since the question of what to do when the proof obligation is not met at runtime becomes a problem; Do we abort/Do we rollback to older known state etc. For a CRUD app we can abort and have the user restart but for a heart pacemaker app we don't want that. In the latter case since it is a closed system with well defined inputs/outputs we can map DbC to VDbC and then prove it through a verifier statically thus guaranteeing invalid states can never arise at runtime. But note that this is merely an incidental distinction due to the needs of the real world but the essential DbC guarantees remain the same. It should now be clear that when you map concepts from mathematical to computing domain you need to understand how the same names like "Integer", "Set/Type", "Algebra", "Axiom", "Proof" map from one to the other (though not exactly) and how you can leverage their isomorphism to use symbolic Mathematics effectively in Programming while at the same time keeping in mind their differences due to real world computation constraints and limits. References: 1) Mathematical Proof - https://en.wikipedia.org/wiki/Mathematical_proof https://en.wikipedia.org/wiki/Mathematical_proof 2) Computer-assisted Proof - https://en.wikipedia.org/wiki/Computer-assisted_proof https://en.wikipedia.org/wiki/Computer-assisted_proof In particular; see the "Philosophical Objections" section. 3) See also the book From Mathematics to Generic Programming by Alexander Stepanov and Daniel Rose to get an idea of how to map between mathematics and programming.

GhosT078 1y ago

I have used SPARK Ada myself on a couple of security focused products developed by a team of 10-15 developers. For a long time, SPARK has made use of formal methods practical for real-world software. Effective use does require learning and commitment, but that's within reason. By the time the projects were nearly done, I felt that the SPARK findings always turned out to be correct and that any remaining problems could be traced back to poor or missing requirements, not the implementation itself.

rramadass 1y ago

There is a nuanced but distinct difference in my use of the word Proof as used in Program as a Proof and Proof in a Mathematical Algebraic System which you have missed. They are isomorphic but not exact (hence my using the phrase it depends and scare-quotes around "proving"). The reason is because Mathematics deals with ideal and abstract objects whereas objects in the real world (eg. a computer program) can only map to aspects of the ideal world and not in its entirety. To elaborate; a mathematical algebraic system is a set of objects and a set of operations defined on them. Axioms using those objects/operations are then defined and then inference/reasoning rules using these are defined to prove theorems in the system. There are various techniques for constructing proofs (eg. direct, induction, contradiction etc.) but all of them must map back to the domain of definition of the objects in the algebra to be considered valid and sound in the real world. As an example, the axiom of associativity w.r.t. addition holds absolutely in mathematics when applied to {N, +} where N is the infinite set of ideal integers. But in computing it is not always the case i.e. (a+b)+c =/= a+(b+c) always because a/b/c are constrained/partial finite sets (i.e. int8/int16/int32 etc.) and thus the axiom of associativity will fail when for example, we take boundary values for a/b and a negative value for c (due to overflow/underflow). Thus any proof which uses the axiom of associativity for signed integers in a computer can never be as absolute and general as its counterpart in pure mathematics i.e. everything is Partial. In general, mathematics uses exact Analytical Techniques while computers use approximate Numerical Techniques to solve a problem which is reflected in the nature of their proofs. Coming to DbC, since it is based on Hoare Logic (i.e. an algebra with axioms/inference rules), a Program is written as a series of Preconditions/Postconditions/Invariants with the Programmer acting as the Proof deriver. Thus if a series of pre/post/inv holds at a certain stage in the program (i.e. proof) the next post will hold (barring external cataclysms). The fact that the proof obligation is discharged dynamically at runtime is immaterial. But we may not want that in certain categories of real world programs since the question of what to do when the proof obligation is not met at runtime becomes a problem; Do we abort/Do we rollback to older known state etc. For a CRUD app we can abort and have the user restart but for a heart pacemaker app we don't want that. In the latter case since it is a closed system with well defined inputs/outputs we can map DbC to VDbC and then prove it through a verifier statically thus guaranteeing invalid states can never arise at runtime. But note that this is merely an incidental distinction due to the needs of the real world but the essential DbC guarantees remain the same. It should now be clear that when you map concepts from mathematical to computing domain you need to understand how the same names like "Integer", "Set/Type", "Algebra", "Axiom", "Proof" map from one to the other (though not exactly) and how you can leverage their isomorphism to use symbolic Mathematics effectively in Programming while at the same time keeping in mind their differences due to real world computation constraints and limits. References: 1) Mathematical Proof - https://en.wikipedia.org/wiki/Mathematical_proof https://en.wikipedia.org/wiki/Mathematical_proof 2) Computer-assisted Proof - https://en.wikipedia.org/wiki/Computer-assisted_proof https://en.wikipedia.org/wiki/Computer-assisted_proof In particular; see the "Philosophical Objections" section. 3) See also the book From Mathematics to Generic Programming by Alexander Stepanov and Daniel Rose to get an idea of how to map between mathematics and programming.