-
Vrification probabilisteUniversit Paris IIMichel de Rougemont
[email protected]://www.lri.fr/~mdr
Algorithmes probabilistes qui vrifient une proprit.
Vrification formelle de programmes probabilistes.
Applications des deux approches.
27 Novembre 2001
-
Vrification
Logique et ComplexitCalcul : f(x) =yVerification : x,y donns,
decider si f(x)=yPour une dfinition de f, quelle est la complexit
de la vrification?
Verification formellePour un programme (circuit, C,) qui calcule
une fonction g, comment savoir si
27 Novembre 2001
-
cf: George Boole The Laws of Thought, 1854Part I: propositional
logic, Part II: probability
cf: John von Neumann The Report on EDVAC, 1945Theory of Games
and Economic Behavior, 1944
(cf: Alan Turing On Computable Numbers, 1936Studies in Quantum
Mechanics, 1932-35)
Ref. C. Papadimitriou:
Logique et Probabilit
27 Novembre 2001
-
Vrification probabiliste
Fonctions classiques sur des matrices boolennes
Calcul probabilistetIl existe un algorithme proba. ASi f(x)=1,
Prob[ A accepte] > 2/3Si f(x)=0, Prob[ A rejette ] > 2/3
27 Novembre 2001
-
Vrification polynomialeNP
Il existe une fonction t.q. L est dans NP sil existe une
fonction g dans Pt.q. Pour la fonction :On ne connat pas de telle
fonction g!!La fonction est le complment deCest une fonction de
co-NP.
27 Novembre 2001
-
Vrification probabiliste
PV0 (1/2)1 (1/2)L admet une preuve interactive, sil existe un
protocole t.q pour tout x :Si , Prob [ P.V(x)=1] =1Si , Prob [
P.V(x)=1] < 1/2
Comment vrifier avec un protocole?
V choisit {1,2} et construit P envoit . Si , P.V=1, sinon
P.V=0
27 Novembre 2001
-
Vrification polynomiale probabiliste : IP=PSPACE
Soit
Il existe un protocole IP qui vrifie si Perm(A)=b
Soit kSAT la fonction qui dcide de la satisfaisabilit de k-
clauses:#kSAT est la fonction de comptage.SkSAT =Prob [ x
satisfait]
Perm, S2SAT, S3SAT sont #P-compltes.
27 Novembre 2001
-
Vrification probabiliste dune preuve : PCP
27 Novembre 2001
-
Checker,Testeur de Blum
Checker pour f (Blum, Kannan, ~1990)PCxyUn 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- ^kCorrectBuggy
27 Novembre 2001
-
Checker pour Graph-Iso
P (G, H) = si G iso H, (1, ) sinon 0PCG,H(1, ) ou
0CorrectBuggyC(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, BuggyAprs k essais, Correct
27 Novembre 2001
-
Auto testeurDistance 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, )=CorrectSi d(P,f) > alors T(P, )=Buggy
Correcteur. Division (x,y) : Majorit { x.r/y.r : r ala.}
27 Novembre 2001
-
Test de proprit Classe de fonctions ou de propritsGoldreich,
Golwasser, Ron ~1995
Un test pour F est un algorithme probabiliste A t.q.Si f est
dans F, A accepteSi f est loin de F, A rejetteT(A) indpendante de
n
Exemple: k-colorabilit de graphesGGi sous graphe alatoire
27 Novembre 2001
-
Tests et complexit descriptive
Quelles proprits de graphes (matrices) admettent des
testeurs?Alon et al., STOC 99: Sigma 2 testeurs
Compression.
Epsilon-equivalent
27 Novembre 2001
-
Vrification formellePreuves:Programme correct vs.
preuveModlesSystme de transition du programmeProprit vrifier :
formule fi U mod fiFunction f(x)Int x;For (0;i;j) {}Programme
nestplus une boite noire.
27 Novembre 2001
-
Vrification par modle
Systme de transition (Structure de Kripke
Formules LTL, CTL, CTL* sur U,s |= (p1 U Accept) => G |=
FVrifier : comparer les OBDDssP1P2P3Accept
27 Novembre 2001
-
OBDD : Oriented Binary Decision DiagramBranching
programsSuccinct representation of relations
Intractable for:MultiplicationConnectivity, Bipartition
v1v201R(v1,v2,.vn)vn
27 Novembre 2001
-
Vrification probabilisteProprits : LTL : p1 U p2 Prob [ p1 U p2
] > a
Espace probabiliste:Ensemble des chemins
Prob [ p1 U p2 ]=3/8p1p2
27 Novembre 2001
-
Calcul de la probabilitCalcul de Prob [ p1 U p2 ] C.Y. 95,
Hanson et Johnson 94S1= { 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, systme de taille N !!
27 Novembre 2001
-
Systme PRISMUniversit de Birmingham, Marta KwiatkowskaSMV :
proprits dterministesAX+B=C : probabilistesAX+B < C :
non-dterministes
Vrification de protocoles : Consensus de Aspnes et Herlihy, CAV
2001
27 Novembre 2001
-
Protocoles cryptographiqueshttps (SSL, Secure Socket
layer)Authentification du serveur (certificat)(Cl de
session).RSACryptage.DESImplmentationsNetscape, Open-SSL,
Apache-SSLProprit : cl de session reste secrte!!Difficile de
dcoderAuthentification correcte
27 Novembre 2001
-
Protocoles cryptographiquesProcess Equivalence Mitchell,
Scedrov, 1998,99
P= epsilon Q si pour tout programme (contexte ) C, vProb[C.P =v]
- Prob[C.P =v] < epsilon
Pn= f Qn si pour tout programme (contexte ) C, vProb[C.P =v] -
Prob[C.P =v] < 1/f(n)P= Q si Pn = f Qn pour tout polunome
fExemple : Gnrateur alatoire = Gnrateur pseudo alatoire
27 Novembre 2001
-
Abstraction ProbabilisteTest de proprit : k-colorabilit
Abstraction dun programme?
Programmme correct => U,G |= FProgram loin detre correct
=> Prob [U,G |= not F]>2/3
Collaboration F. Magniez, S. Laplante, R. Lassaigne, S.
Peyronnet.
27 Novembre 2001
-
Abstraction ProbabilisteAbstraction dun programme?
Programme C
A[i,j] B[i,j] sous-graphe alatoireVariables u, v u, v
Taille de lOBDD : 2 ,m=1/epsilon
m
27 Novembre 2001
-
ConclusionVrification de proprits:TesteursVrification de
programmes:Dterministes : Modles , OBDDProbabiliste : systmes
linairesNon dterministe : encadrementsApproximation de la
vrificationTesteurs
27 Novembre 2001
