Difference between revisions of "Formal Methods and Theorem Provers"

From T-VEC Wiki
Jump to: navigation, search
Line 9: Line 9:
 
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).
 
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).
  
===Standards===
+
==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|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.
 +
 
 +
==Standards==
 
IEC61508, ISO26262 have been started to recommend Formal Method.
 
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.
 
DO-178B discusses formal methods in a "soft" tone, but DO-178C is discussing it more directly.

Revision as of 09:12, 15 February 2007