24
QSL, 27 Novembre 2001 1 Vérification probabiliste Université Paris II Michel de Rougemont [email protected] http:// www.lri.fr/~mdr 1.Algorithmes probabilistes qui vérifient une propriété. 2.Vérification formelle de programmes probabilistes. 3.Applications des deux approches.

QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont [email protected] mdr 1.Algorithmes probabilistes qui

Embed Size (px)

Citation preview

Page 1: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 1

Vérification probabiliste

Université Paris II

Michel de Rougemont

[email protected]

http://www.lri.fr/~mdr

1. Algorithmes probabilistes qui vérifient une propriété.

2. Vérification formelle de programmes probabilistes.

3. Applications des deux approches.

Page 2: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 2

Vérification

Logique et Complexité•Calcul : f(x) =y•Verification : x,y donnés, decider si f(x)=y•Pour une définition de f, quelle est la complexité de la vérification?

Verification formelle•Pour un programme (circuit, C,…) qui calcule une fonction g, comment savoir si

?))()()( (ex. )( yxgygxgg

Page 3: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 3

cf: George Boole The Laws of Thought, 1854

Part I: propositional logic, Part II: probability

cf: John von Neumann The Report on EDVAC, 1945

Theory of Games and Economic Behavior, 1944

(cf: Alan Turing On Computable Numbers, 1936

Studies in Quantum Mechanics, 1932-35)

Ref. C. Papadimitriou:

Logique et Probabilité

Page 4: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 4

Vérification probabiliste

Fonctions classiques sur des matrices booléennes

)det()(2 AAf

11 )( AAf )()(3 ApermAf

0sinon 1 alors , si ),( 21214 AAAAf

BPPf Calcul probabilistet

Il existe un algorithme proba. A

1. Si f(x)=1, Prob[ A accepte] > 2/32. Si f(x)=0, Prob[ A rejette ] > 2/3

1sinon 0 alors , si ),( 21215 AAAAf

Page 5: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 5

Vérification polynomialeNP

0sinon 1 alors , si ),( 21214 AAAAf

1sinon 0 alors , si ),( 21215 AAAAf

Il existe une fonction t.q. 0sinon 1alors))(),((ji, si ),,( 2121 (i,j)AjiAAAg

L est dans NP s’il existe une fonction g dans Pt.q.

Pour la fonction :

On ne connaît pas de telle fonction g!!La fonction est le complément deC’est une fonction de co-NP.

P g

1 ),,(g n ssi 1 ),( 21214 k AAAAf 5f

5f NPf 4

Page 6: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 6

Vérification probabiliste

P V

1sinon 0 alors , si ),( 21215 AAAAf

0 (1/2)1 (1/2)

L admet une preuve interactive, s’il existe un protocole t.q pour tout x :1. Si , Prob [ P.V(x)=1] =12. Si , Prob [ P’.V(x)=1] < 1/2

Comment vérifier avec un protocole?

2. V choisit {1,2} et construit 2. P envoit . 3. Si , P.V=1, sinon P.V=0

r )( AH

LxP' , Lx

Page 7: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 7

Vérification polynomiale probabiliste : IP=PSPACE

•Soit

Il existe un protocole IP qui vérifie si Perm(A)=b

•Soit kSAT la fonction qui décide de la satisfaisabilité de k- clauses:#kSAT est la fonction de comptage.SkSAT =Prob [ x satisfait]

•Perm, S2SAT, S3SAT sont #P-complètes.

)()(3 ApermAf

Page 8: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 8

Vérification probabiliste d’une preuve : PCP

Page 9: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 9

Checker,Testeur de Blum

Checker pour f (Blum, Kannan, ~1990)

P

C

x y

Un checker est un programme probabiliste avec oracle P t. q pour tout x,k :

Si P=f, C(x,k) = Correct

Si P(x)!=f(x), Prob[ C(x,k) =Buggy] >1- ½^k

CorrectBuggy

Page 10: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 10

Checker pour Graph-Iso

P (G, H) = si G iso H, (1, ) sinon 0

P

C

G,H (1, ) ou 0

CorrectBuggy

C(G,H, k):Si P (G, H)=(1, ), verifier que G= (H)Si P (G, H)=0, choisir Si =1, G’= (G). Si P(G,G’)=0 , BuggySi =2, H’= (H), Si P(G,H’)=1, BuggyAprès k essais, Correct

et [1,2} r

Page 11: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 11

• Distance d(f,g) = | {x : f(x) != g(x)}| / | D|

• Un auto-testeur pour f est un programme T(P, ) t.q.

– Si d(P,f)=0, alors T(P, )=Correct– Si d(P,f) > alors T(P, )=Buggy

• Correcteur. Division (x,y) : Majorité { x.r/y.r : r aléa.}

Auto testeur

Page 12: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 12

• Classe de fonctions ou de propriétés• Goldreich, Golwasser, Ron ~1995

• Un test pour F est un algorithme probabiliste A t.q.– Si f est dans F, A accepte– Si f est loin de F, A rejette– T(A) indépendante de n

• Exemple: k-colorabilité de graphes

Test de propriété

G Gi sous graphe aléatoire

Page 13: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 13

• Quelles propriétés de graphes (matrices) admettent des testeurs?

– Alon et al., STOC 99: Sigma 2 testeurs

• Compression.

Tests et complexité descriptive

?)( gsatisfiesU

?)( gsatisfiesV Epsilon-equivalent

Page 14: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 14

Vérification formelle

• Preuves:– Programme correct vs. preuve

• Modèles– Système de transition du programme– Propriété à vérifier : formule fi– U mod fi

Function f(x)

Int x;

For (0;i;j) {……}

Programme n’estplus une boite noire.

Page 15: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 15

Vérification par modèle

• Système de transition (Structure de Kripke

• Formules – LTL, CTL, CTL* sur

• U,s |= (p1 U Accept) => G |= F

• Vérifier : comparer les OBDDs

)....,,( 1 kPPRSU

Acceptpp k,....1

sP1P2P3Accept

Page 16: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 16

• Branching programs

• Succinct representation of relations

• Intractable for:

– Multiplication

– Connectivity, Bipartition

OBDD : Oriented Binary Decision Diagram

v1

v2

0 1

R(v1,v2,….vn)

vn

Page 17: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 17

Vérification probabiliste

• Propriétés : LTL : p1 U p2

Prob [ p1 U p2 ] > a

• Espace probabiliste:

Ensemble des chemins

Prob [ p1 U p2 ]=3/8

p1p2

Page 18: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 18

Calcul de la probabilité

• Calcul de Prob [ p1 U p2 ] – C.Y. 95, Hanson et Johnson 94

• S1= { s : M |= P1(s) } S+= { s : M |= E(p1 U p2 )} , S0=S-S+

• Soit xi = Prob [ p1 U p2 ] depuis i xi = 1 si i dans S1 xi= 0 si i dans S0 xi= Somme p(i,j) xj

X= A.X +B, système de taille N !!

Page 19: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 19

Système PRISM

• Université de Birmingham, Marta Kwiatkowska

• SMV : propriétés déterministes• AX+B=C : probabilistes• AX+B < C : non-déterministes

• Vérification de protocoles : Consensus de Aspnes et Herlihy, CAV 2001

Page 20: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 20

Protocoles cryptographiques

• https (SSL, Secure Socket layer)– Authentification du serveur (certificat)

– (Clé de session).RSA

– Cryptage.DES

• Implémentations– Netscape, Open-SSL, Apache-SSL

• Propriété :– clé de session reste secréte!!– Difficile de décoder– Authentification correcte– ……

Page 21: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 21

Protocoles cryptographiques

Process Equivalence

Mitchell, Scedrov, 1998,99

P= epsilon Q si pour tout programme (contexte ) C, v

Prob[C.P =v] - Prob[C.P =v] < epsilon

Pn= f Qn si pour tout programme (contexte ) C, v

Prob[C.P =v] - Prob[C.P =v] < 1/f(n)

P= Q si Pn = f Qn pour tout polunome f

Exemple : Générateur aléatoire = Générateur pseudo aléatoire

Page 22: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 22

Abstraction Probabiliste

• Test de propriété : k-colorabilité

• Abstraction d’un programme?

• Programmme correct => U,G |= F

• Program loin d’etre correct => Prob [U,G |= not F]>2/3

• Collaboration F. Magniez, S. Laplante, R. Lassaigne, S. Peyronnet.

Page 23: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 23

Abstraction Probabiliste

• Abstraction d’un programme?

• Programme C

A[i,j] B[i,j] sous-graphe aléatoire

Variables u, v u’, v’

Taille de l’OBDD : 2 ,m=1/epsilonm

Page 24: QSL,27 Novembre 20011 Vérification probabiliste Université Paris II Michel de Rougemont mdr@lri.fr mdr 1.Algorithmes probabilistes qui

QSL, 27 Novembre 2001 24

Conclusion

• Vérification de propriétés:– Testeurs

• Vérification de programmes:– Déterministes : Modèles , OBDD– Probabiliste : systèmes linéaires– Non déterministe : encadrements

• Approximation de la vérification– Testeurs