iccad08-tutorial-ALL [Compatibility Mode]

Chaowang

Description

Embedded Software VerificationChallenges and SolutionsShuuvendu LLahiri, MMicrosofftt, RedmmondChhhhao Waaaannnng, NECCCC Labs, PrincettttoooonDaaniel Krrooening,, Oxford UUniversisityICCAD TutorialNovember 11, 2008102Outline What programs? The Formal Basics of Program Verification Static Program Analysis Preddicate AAbstraaction Bounded Model Checking (BMC)103Motivation Software has too many state variables) State Space Explosion Graf/Saïdi 97: Predicate Abstraction Idea: Only keep track of predicates on data Abstraction function:104Predicate AbstractionConcrete States:Predicates:Abstract transitions?105Under- vs. Overapproximation How to abstract the transitions?Depends on the property we want to showTypically done in a conservative manner Existential abstraction:) Preserves safety properties106Predicate AbstractionAbstract Transitions:Property:Property holds. Ok.107Predicate AbstractionAbstract Transitions:Property:This trace is spurious!108Predicate AbstractionAbstract Transitions:New Predicates:Property:109Predicate Abstraction for Software Let’s take existential abstraction seriously Basic idea: with n predicates, there aren n2 £ 2 poossibllee absttract ttransiitionss Let’s just check them!110Existential AbstractionPredicatesBasic Block Formulai++;QQueryp p p pp’’ p’ p’’1 2 3 1 2 30 0 0 0 0 0????0 0 1 0 0 10 1 0 0 1 00 1 1 0 1 11 0 0 1 0 ...

Informations

• Publié par: Shied
• Nombre de lectures: 23
• Langue: English

Extrait

ao

ang,

 

a

s,

r nceton

Daniel Kroening, Oxford University

ICCAD Tutorial November 11, 2008

102



 

Bounded Model Checking (BMC)

103



Abstraction function:

104

Predicates:

Abstract transitions?

105

)

Preservess aefty properties

106

Property:



Property holds. Ok.

107

Property:

 This trace is spurious!

108

Property:



New Predicates:

109



 

Let’s just check them!

 

110

111

1

1

1

0

0

p 1 0 0 0

? 

1

0

1

1

p 2 0 0 1

1

1

1

1

p 3 0 1 0

1

1

1

0

1

0

0

1

1

1

0

0

1

1

0

Current Abstract State

p 1 0 0 0

Next Abstract State

1

p 2 0 0 1

1

0

0

1

1

1

1

0

1

0

0

1

1

p 3 0 1 0

p 1 0 0 0

0

1

1

1

1

p 2 0 0 1

1

0

0

1

1

p 3 0 1 0

1

0

1

0

1

 ?

Current Abstract State

p 1 0 0 0

0

1

1

1

1

p 2 0 0 1

1

0

0

1

1

p 3 0 1 0

1

0

1

0

1

Next Abstract State

… and so on …

112