12 Octobre 2001 1
Logique et Vérification probabiliste
Université Paris II
Michel de Rougemont
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
1sinon 0 alors , si ),( 21215 AAAAf
12 Octobre 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
12 Octobre 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
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
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
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