Logique et Vérification probabiliste

12 Octobre 2001 1

Logique et 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.

4. Vérification et jeux

12 Octobre 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

12 Octobre 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é

12 Octobre 2001 4

Vérification probabiliste

Fonctions classiques sur des matrices booléennes

)det()(2 AAf

11 )( AAf ))(,( )()(3 iiaApermAf i

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


12 Octobre 2001 5

Vérification polynomialeNP



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

12 Octobre 2001 6


P V


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

12 Octobre 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

12 Octobre 2001 8

Vérification probabiliste d’une preuve : PCP

preuve

i V0 (1/2)1 (1/2)

L est dans PCP(r(n),q(n)), s’il existe un vérificateur V tel que pour tout x :

1. Si , Prob [V(x, )=1] =1

2. Si , Prob [V(x, )=1] < 1/2

Lx' , Lx

,

' ,

12 Octobre 2001 9

Caractérisations PCP

Théorème (Arora et al.): NP =PCP(log n , 1)

Théorème : NEXP =PCP(poly , poly)

Passer d’une preuve classique à une preuve transparente (holographique) ?

•O(n^2) mais….• intérêt théorique

12 Octobre 2001 10

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

12 Octobre 2001 11

Checker pour Graph-Iso

P (G, H) = si , (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

HG

12 Octobre 2001 12

• 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

12 Octobre 2001 13

• 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

12 Octobre 2001 14

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

– Alon et al., STOC 99: testeurs

• Compression.

Tests et complexité descriptive

?)( gsatisfiesU

?)( gsatisfiesV -equivalent

2

12 Octobre 2001 15

Vérification formelle

• Preuves:– Programme correct vs. preuve

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

Function f(x)

Int x;

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

Programme n’estplus une boite noire.

12 Octobre 2001 16

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

12 Octobre 2001 17

• 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

12 Octobre 2001 18


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

Prob [ p1 U p2 ] > a

• Espace probabiliste:

Ensemble des chemins

Prob [ p1 U p2 ]=3/8

p1p2

12 Octobre 2001 19

Calcul de la probabilité

• Calcul de Prob [ p1 U p2 ] – Problème #P (comptage)

• 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 !!

12 Octobre 2001 20

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

12 Octobre 2001 21

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– ……

12 Octobre 2001 22

Protocoles cryptographiques

Equivalence de processus

Mitchell, Scedrov, 1998,99

si pour tout programme (contexte ) C, v Prob[C.P =v] - Prob[C.P =v] <

si pour tout programme (contexte ) C, v Prob[C.P =v] - Prob[C.P =v] < 1/f(n)

pour tout polynome f

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

QP

nfn QP

nfn QPQP si

12 Octobre 2001 23

Abstraction Probabiliste

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

• Abstraction d’un programme?

• Programme correct => U,G |= F

• Programme loin d’être correct => Prob [U,G |= not F]>2/3

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

12 Octobre 2001 24

Verification et Jeux

• Définissabilité et jeux– F.O. : Ehrenfeucht Fraisse– LFP : Pebble games– Mu-calcul : 1 Pebble– S.O: Jeux de coloriage

• Jeux en Economie– Existence d’un équilibre de

Nash ?– Jeux à somme non nulle, à

information incomplète.– Quel est le jeu de TCP/IP ?

12 Octobre 2001 25

Verification et Jeux

SODA: January 8, 2001 8

Games, games…

randominformationset

strategies

strategies3,-2

payoffs

• C. Papadimitriou

12 Octobre 2001 26

Equilibre de Nash

C D

C 3,3 0,4

D 4,0 1,1

Dilemme des prisonniers

(C,D) produit un gain de 0 pour I et 4 pour II

Def: (x,y) est un équilibre (pur) de Nash si aucun joueur ne peut augmenter son gain.

Une stratégie mixte est une distribution sur les stratégies pures. Il existe toujours un couple (p,q), en équilibre de Nash. ( P calculable ?)

12 Octobre 2001 27

Jeux et Complexité

• Stratégie de l’adversaire n’est pas arbitraire.– Définie par un automate (P.Y. 2000)– Stratégie P– Stratégie BPP

• Equilibre de Nash est modifié.

• Rationalité (dilemme itéré des prisonniers.)

• Quel est le jeu pour un protocole qui atteint un équilibre? TCP/IP ?

12 Octobre 2001 28

Vérification et Equilibres

• Protocole de consensus (Aspnes et Herlihy)

Condition de consensus= condition d’équilibre.

• Quel est le jeu?– Information incomplète

– Somme non-nulle

• Quelle est la correspondance entre logique et Jeux?

• Sécurité, « privacy », conduisent à d’autres conditions d’ équilibre.

• Equilibre approximatif

12 Octobre 2001 29

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

• Vérification et jeux

Documents

Logique et Vérification probabiliste