Formal Methods and Theorem Provers

From T-VEC Wiki
Revision as of 10:12, 15 February 2007 by Admin (Talk | contribs)

Jump to: navigation, search

T-VEC is a formal method.

Formal methods are mathematically-based techniques for the specification, development and verification of software and hardware systems.


T-VEC (behind the scenes is a Theorem Prover) - per the wiki taxonomy

Level 2: Theorem provers may be used to undertake fully formal machine-checked proofs. This can be very expensive and is only practically worthwhile if the cost of mistakes is extremely high (e.g., in critical parts of microprocessor design).

Proof versus Testing

There are many many types of "formal methods" and many types of tools that support one or more types of formal methods. However, is not likely that there is a formal methods or tools that can "prove the whole (avionics, automotive, medical) system." Those formal methods that use theorem provers are generally applied to proving specific properties about a system, usually from an abstract level. TTM/Simulink/T-VEC "proves" that the logical constraints of a Domain Convergence Paths (DCP) are consistent and have a solution in the specified input domain. It then provides a test vector as a byproduct that can be used to "demonstrate" through testing that the target code is consistent with the DCP and the computation that the DCP controls.

=Simple Proof Supporting Testing

T-VEC is for test generation and uses a theorem proving engine with a few simple goals that are implemented in rules covering all program data types and operations, including many library operations (e.g., sin, cos, asin, acos, tan, ln, abs, etc.).

The simple goal is: given a set of n variables, and a set of constraints, find a set of data point for the variables, such that each constraint (precondition) is satisfied.

What makes T-VEC "good" for testing is that it finds the data (test) points at the extreme corners of the n-dimensional space defined by the constraints of the precondition. These are points that are typically associated with program faults (or model faults - contradictions). Once it finds a set of points, it attempts to compute an expected output for the function (postcondition), which can also have contradictions through references to other functions that cannot be satisfied by the selected set of points. What further complicates the process is that constraint development (or model development) requires the use of abstraction (submodels - procedures), and T-VEC has rules to deal with hierarchies of constraint sets.


IEC61508, ISO26262 have been started to recommend Formal Method.

DO-178B discusses formal methods in a "soft" tone, but DO-178C is discussing it more directly.