Transcript FVerification

Formal Verification
Background Information
• Formal verification methods based on theorem proving techniques and
modelchecking
–
–
To prove the absence of errors (in the formal model)
To reason about the behaviors of programs
• No known generic software verification
–
–
Involves complicated proving
Generally cannot be easily and cost-effectively integrated to software and hardware
development cycles
Major Verification Topics
• Specification verification
• Architecture verification
• General practical issues
Architecture Verification
• Correctness of architecture refinement
– A methodology for the correct stepwise refinement of software
architectures
– Using the approach of architecture refinement patterns that are
correctness preserving and compositional
Common Architecture Issues
• From abstract level to concrete level
• Simple architecture: Box - arrows, representing data
component and connections
• Large architecture: Hierarchical approach
Common Architecture Problem
• Limited utility of architecture hierarchy results from the
current level of informality
• Ambiguity in architecture allows unintended
interpretations. May cause erroneous interpretation
Architecture Refinement
• From a abstract architecture to a concrete (lowerlevel) architecture
– Lead to:
• Fewer architectural design errors
• Extensive and systematic reuse of design knowledge and proofs
Refinement Pattern Approach
• A pair architecture schemas (homogenous or heterogeneous)
• Proven to be relatively correct with respect to the given mapping
schema
Refinement Pattern
• Requires a special correctness criterion
– A special mapping between architectures
– Extensive translation:
• The representation of components, interfaces, and
connections
• Aggregated, decomposed, or eliminated
Completeness Assumption
• Prove that a concrete architecture has all required
properties
– No new properties can be inferred from the concrete architecture
• All components, interfaces, and connections intended to be
true of the architecture at its level of detail
– If a fact is not explicit in the architecture, assume that it is not
intended to be true
Completeness Assumption
• Standard way to proof relative correctness
– Show that the concrete specification logically implies the abstract
specification under a given mapping
– Allow additional and specified behaviors, as long as the specified
behavior is implemented
– No guarantee that negative properties are preserved under
refinement
• Alternative:
– Faithful interpretation
– Hard and no general proof technique
• Use preproved refinement patterns
Example
• Use only logical theories for simplicity
• To show how to systematically and
incrementally transform a abstract
architecture to its lower-level form
• Approach: Combining small and local
refinement to form the larger composite
Example
chars
Lexical
Analyzer
toks
Lexical
Parser
bindings
ast
Analyzer
Optimizer
ast
Code
Generator
code
Architecture as Theories
• Architecture styles
– Operations and axioms
• Translation to logic
– Patterns  logic (theory generation rules)
• Mapping
– Name mapping
– Style mapping
– Interpretation mapping
Architecture Styles
Dataflow style:
Axioms example -- Every function must at least have one port:
Translation to Logic
• An instance of function declaration schema:
– f: Functional_Style!Function [  op: t]
• The underlying theory contains the same instance of first order
sentences:
Mapping
• Name mapping:
– c | m
– op | w
• Style mapping:
– Accepts (_, _) | Gets (_, _)
– Connects (_, _, _) | Writes (_,_) ^ Reads(_,_)
• Interpretation mapping = name + style mapping
Proving
• Criterion
– All intended to do
– Not intended to do
Composition
• Horizontal
– Compose instances of refinement patterns to
form one large composite refinement
• Vertical
– Most concrete architecture in a hierarchy is
correct with respect to the most abstract
– Justified since faithful interpretation is
transitive
Problem Example
• Concrete architecture 1
– A  B (dataflow connection)
• Concrete architecture 2
– B  C (dataflow connection)
• The composition of 1 and 2 is not faithful!
– Need new abstract dataflow from A to C
Specification
• Correctness issue
• Complete specification of program is in terms of
hierarchical structure of module specifications
• Module external specifications are abstract, about module
behavior
• Module internal specifications are descriptions of internal
implementations
Concurrent System Verification
•
•
•
•
Program is a set of events
Interpreted and verified with a formal proof system
Internal specification classified as composite or simple
Composite: Composed of linked sub-modules, each with
external and internal specification
External Specification
External specification consist of three parts:
• Behavior: Module delivers to the environment
• Provide: How modules synchronizes with the environment?
• Require: Synchronization cooperation the module expects
from environment
Composite Internal Specification
Internal specification of a composite module associates events
described in the external specification of the module with
events described in the external specifications of the submodules
• Ports: A set of single direction communication channels
between the module and its environment
• Network link: Sub module ports are connected together to
form communication channels
Composite Module Verification
Verification of composite module:
1. External behaviors of the sub-modules plus the network
and interface links must imply the external behavior of
composite module
2. Provides and requires of the sub modules and composite
module must be mutually supportive and complete
Mutual support: Sub module provides imply the submodule requires
Complete: Composite require and provide represent the
sub-module requires and provides accurately and
completely
Simple Module Specification
Verification
Internal specification of a simple system consists of three
parts:
• Program: Internal specification as example
• Performance: Whether the program is cyclic or terminates
and contains an assert statement that describe the history
• Interpret: Identify ports with subsequences on the history
Simple Module Specification
Verification
Verification of specifications of a simple module:
1. Performance and interpret statements must imply the
external behavior
2. Performance and external provide must be established
using following axioms:
–
–
–
History sequence axiom
Statement block axiom
Process history axiom
Discussion
• Task of analyzing programs is easier if the program is
composed of modules
• Key importance is to establish specifications
• Automated verification system can be based on verification
rules
Related Works
• Automatic program verifications - verification condition
generator
• EBS, Chen, Yeh, Reed et al
• Concurrent programs, Hailpern,Owicki, Lamport and
Schneider
General Discussion
• Abstract logic component decomposition verification and
efficiency analysis
• Practical tools, such as UML