of 24 /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.

Vérification probabiliste

  • Author
    jovan

  • View
    27

  • Download
    1

Embed Size (px)

DESCRIPTION

Vérification probabiliste. Algorithmes probabilistes qui vérifient une propriété. Vérification formelle de programmes probabilistes. Applications des deux approches. Université Paris II Michel de Rougemont [email protected] http://www.lri.fr/~mdr. Vérification. Logique et Complexité - PowerPoint PPT Presentation

Text of Vérification probabiliste

  • 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