News for hackers. Stuff that matters.
Re:A Hoare Logic for Rust by Jtsummers on Friday September 30, 2016 @02:29PM (#12614279)
Respectfully, I have to disagree. Design by contract is, or can be, a component of formal verification. If it's all you've got, it's probably better than nothing.

Design by contract brings the concept of using preconditions, postconditions, invariants, and other contractual objects into the design and implementation of the software. These are able (depending on implementation) to be analyzed statically by machine or by hand, or dynamically during testing (with some systems the tests can be automatically generated to exercise the contracts). This may not be the limit or ideal of formal verification, but it is certainly a part of it and a good measure forward compared to the typical approaches used in our industry.

EDIT:

Let's settle a pertinent question first: Is Hoare logic a tool/approach for formal verification? If it is, then design by contract (being largely based on the concept of Hoare logic) is also a tool/approach for formal verification.

The potential points of disagreement, as I see them, are that Hoare logic is not a tool for formal verification, or that design by contract is not based on Hoare logic. Is there something else that I've missed or are these the points of disagreement?

Re:A Hoare Logic for Rust by catnaroek on Friday September 30, 2016 @02:45PM (#12614404)
Design by contract forces you to be explicit about your intended preconditions and postconditions. But “intended” isn't the same thing as “actual”. Verification is making sure that the preconditions and postconditions actually hold, in every possible case where the statement (or procedure or whatever) could be reached.

EDIT: Hoare logic is a tool for formal verification, indeed. DbC is not, though.

Re:A Hoare Logic for Rust by Jtsummers on Friday September 30, 2016 @02:52PM (#12614462)
We're talking around each other. What is your definition of formal verification?
Re:A Hoare Logic for Rust by catnaroek on Friday September 30, 2016 @03:01PM (#12614512)
Proving that a program meets its specification.
Re:A Hoare Logic for Rust by Jtsummers on Friday September 30, 2016 @03:03PM (#12614531)
Is Hoare logic a tool in that process?
Re:A Hoare Logic for Rust by catnaroek on Friday September 30, 2016 @03:08PM (#12614562)
Yes. Hoare logic's inference rules define which Hoare triples can be “legally” derived. The programmer's task isn't only to provide a Hoare triple (which by itself is just an assertion that a program meets a specification), but also to provide a derivation of that triple (the actual proof of the assertion). Design by contract is akin to giving a Hoare triple, but never giving its derivation.
Re:A Hoare Logic for Rust by Jtsummers on Friday September 30, 2016 @03:11PM (#12614578)
Design by contract, is it based or not based on Hoare logic?
Re:A Hoare Logic for Rust by catnaroek on Friday September 30, 2016 @03:11PM (#12614583)
It's not. In DbC, you have preconditions and postconditions, but no means whatsoever to actually prove that, whenever the procedure's initial state meets the precondition, its final state will meet the postcondition.
Re:A Hoare Logic for Rust by Jtsummers on Friday September 30, 2016 @03:26PM (#12614669)
Well, I've found the point disagreement.

So design by contract, based on Hoare logic, applied in languages like SPARK Ada and Eiffel, produces statements that are unverifiable.

But Hoare logic, a thing without an executable implementation, produces statements which are verifiable.

Re:A Hoare Logic for Rust by naasking on Friday September 30, 2016 @05:09PM (#12615313)
> In DbC, you have preconditions and postconditions, but no means whatsoever to actually prove that, whenever the procedure's initial state meets the precondition, its final state will meet the postcondition.

Except many implementations of design by contract execute the postcondition check and raise an exception if it's not satisfied, so I don't think your statement is correct.

Re:A Hoare Logic for Rust by catnaroek on Friday September 30, 2016 @07:26PM (#12615823)
The very reason why you need to raise the exception is because the postcondition doesn't hold. The point to verification is to make sure the postcondition holds. So I stand by my original assertion: DbC isn't verification.
Re:A Hoare Logic for Rust by nickpsecurity on Saturday October 01, 2016 @01:59PM (#12619055)
If I were to categorize it, I'd call DbC formal specification that, combined with Eiffel or SPARK tools, can be used to verify that interfaces or code maintain those specific properties. It's a partial form of formal specification and verification that's still useful.

It doesn't have to be fully specified or proven to count as formal verification. Partial verification is a thriving field.

Re:A Hoare Logic for Rust by catnaroek on Saturday October 01, 2016 @02:59PM (#12619354)
Yep, that's perfectly reasonable.
Re:A Hoare Logic for Rust by nickpsecurity on Friday September 30, 2016 @06:08PM (#12615552)
SPARK combines those intended specs with language-level details that it feeds to a prover to show conditions hold or errors are absent. How is such Design-by-Contract not formal verification of specific properties of software?
Re:A Hoare Logic for Rust by catnaroek on Friday September 30, 2016 @07:28PM (#12615833)
I didn't say anything about SPARK, because I know nothing about it. But, if SPARK actually checks that the specs are met, it's doing more than just DbC.