Conception Formelle en PVS Master 2 ISC Chef de Projet: M. Pierre Castéran Présenté par: Roland...

Conception Formelle en PVS

Master 2 ISC

Chef de Projet: Chef de Projet: M. Pierre CastéranM. Pierre Castéran

Présenté par: Roland Atoui Xavier Dumas

Sébastien Jardel Laurent Vendredi

11/04/23

3- PVS: Prototype Verification System PVS: Prototype Verification System

4- PBS: Support pour la méthode B en PVS PBS: Support pour la méthode B en PVS

5- LeLe Prouveur PVSProuveur PVS

1- Présentation du ProjetPrésentation du Projet

PlanPlan

6- ConclusionConclusion

2- La Méthode B La Méthode B

Présentation du ProjetPrésentation du Projet

Vérification de code

Présentation du ProjetPrésentation du ProjetLa Méthode BL’outil PVSL’outil PBSLe prouveur PVSConclusion

Similitude avec B

S’initier à PVS

Tester PBS

La Méthode BLa Méthode B

Formaliser des spécifications et des programmes

Présentation du ProjetLa Méthode BLa Méthode BL’outil PVSL’outil PBSLe prouveur PVSConclusion

Machine abstraite

Raffinement

Implantation

La Méthode BLa Méthode B

Présentation du ProjetLa Méthode BLa Méthode BL’outil PVSL’outil PBSLe prouveur PVSConclusion

OPERATIONS reset = BEGIN value := 0 END;

next = PRE value < maxi THEN ANY val WHERE val : NAT & val <= maxi & val > value THEN value := val END ENDEND

MACHINE Counter(maxi)

CONSTRAINTS maxi : NAT1

VARIABLES value

INVARIANT value : NAT & value <= maxi

INITIALISATION value := 0

Counter.mch

PVS: Prototype Verification SystemPVS: Prototype Verification System

Un système de vérification

Un assistant de preuve développé par le laboratoire d’informatique de SRI International aux Etats-Unis

Fournit une automatisation pour limiter le travail de l’utilisateur

Un langage de spécification

Un langage expressif:

Logique d’ordre supérieur Un système fortement typé (Le TypeCheck est non décidable) Fonctions récursives totales

Présentation du ProjetLa Méthode BL’outil PVSL’outil PVSL’outil PBSLe prouveur PVSConclusion

Notions préliminairesEnsembles, relations, fonctions, séquences, inductions.

Assistant de preuvesCalcul de Sequents, commandes de preuves primitives, procédure de décision, arithmétique linéaire…[Stratégies, model checker]

Types Types de base : real, int, nat, bool…Types de construction : records, abstract data types, functions, predicates, sets…Types dépendants, types paramétrés.

Présentation du ProjetLa Méthode BL’outil PVSL’outil PVSL’outil PBSLe prouveur PVSConclusion

PVS: Prototype Verification SystemPVS: Prototype Verification System

Exemples : person : TYPE = [# age : nat, married ?: bool #] List[person] [person nat] [person bool] = pred[person] = setof[person]

Propositions.pvs

Propositions : THEORY BEGIN A, B, C: bool prop: THEOREM (A IMPLIES (B IMPLIES C)) AND (A IMPLIES B) AND (A IMPLIES C) END propositions

Présentation du ProjetLa Méthode BL’outil PVSL’outil PVSL’outil PBSLe prouveur PVSConclusion

PVS: Prototype Verification SystemPVS: Prototype Verification System

PBS: Support pour la méthode B en PVSPBS: Support pour la méthode B en PVS

Développé par César Muñoz en 1999

Traduit une machine abstraite B en Théorie PVSm.pbsm.pbs

*.pvs*.pvs

m.pvsm.pvs

Présentation du ProjetLa Méthode BL’outil PVSL’outil PBSL’outil PBSLe prouveur PVSConclusion

Une Machine PBS semblable à une machine abstraite B

Présentation du ProjetLa Méthode BL’outil PVSL’outil PBSL’outil PBSLe prouveur PVSConclusion

OPERATIONS reset = value := 0

next = PRE `value < maxi' THEN ANY val : nat WHERE `val <= maxi AND val > value' THEN value := val ENDANY ENDEND counter

counter [maxi:posnat]: MACHINEBEGIN PVS `IMPORTING finite_sets@top'

VARIABLES value : `nat'

INVARIANT `value <= maxi'

INITIALIZATION value := 0

PBS: Support pour la méthode B en PVSPBS: Support pour la méthode B en PVS

Quelques différences:

Substitutions: WHILE structure récursive de PVS SELECT peut être simulée en PVS

Mots Clefs: SETS TYPES Certains mots clefs n’existent pas (CONSTRAINTS, PROPERTIES…)

Présentation du ProjetLa Méthode BL’outil PVSL’outil PBSL’outil PBSLe prouveur PVSConclusion PBS: Support pour la méthode B en PVSPBS: Support pour la méthode B en PVS

Théorie PVS de counter générée par PBS

Présentation du ProjetLa Méthode BL’outil PVSL’outil PBSL’outil PBSLe prouveur PVSConclusion

%% Theory: Counter Machinecounter [ maxi:posnat ]: THEORY BEGIN%% PVS CommandsIMPORTING finite_sets@top%% General Type counter_Type : TYPE = [# value:nat #]%% Invariant Type counter : TYPE = { self: counter_Type | value(self) <= maxi }%% Initialization init : counter = LET self = (# value := 0 #) IN self

%% Operations reset(self:counter) : counter = LET self = self WITH [ value := 0 ] IN self next(self:counter | value(self) < maxi) : counter = LET self = LET val = choose! (val:nat) : ( val <= maxi AND val > value(self) ) IN LET self = self WITH [ value := val ] IN self IN selfEND counter

PBS: Support pour la méthode B en PVSPBS: Support pour la méthode B en PVS

Présentation du ProjetLa Méthode BL’outil PVSL’outil PBSL’outil PBSLe prouveur PVSConclusion

Raffinement introduit:

Dans une machine PBS par deux invariants:1.INVARIANT2.REFINE_INVARIANT

Dans une théorie PVS: grâce au mécanisme d ’importation

counterRef [maxi:posnat]: REFINEMENT OF counterBEGIN VARIABLES value_ref : `nat'

REFINE_INVARIANT `value_ref <= value' INITIALIZATION value_ref := 0

OPERATIONSnext = value_ref := `value_ref + 1'

END counterRef

counterRef.pbs

PBS: Support pour la méthode B en PVSPBS: Support pour la méthode B en PVS

Basé sur les séquents:

Hypothèses |– Conséquents

Présentation du ProjetLa Méthode BL’outil PVSL’outil PBSLe prouveur PVSLe prouveur PVSConclusion

Prouveur PVSProuveur PVS

3 étapes:

Vérifier la syntaxe (parser)Vérifier la sémantique (typechecker)Prouver les TCCs (prover)

Générations de TCCs:

En utilisant les théorèmesEn utilisant la puissance du typage

Présentation du ProjetLa Méthode BL’outil PVSL’outil PBSLe prouveur PVSLe prouveur PVSConclusion

Prouveur PVSProuveur PVS

Preuves automatiques:

Commande (GRIND)Commande (INDUCT-AND-SIMPLIFY)

2 types de preuves:

Preuves itérativesPreuves par induction

Commandes de bas niveau: (CASE), (INDUCT)

Simplifient les preuvesFacilitent les preuves

Présentation du ProjetLa Méthode BL’outil PVSL’outil PBSLe prouveur PVSLe prouveur PVSConclusion

Les stratégies

UtilitéesGénéraliser les preuves

Prouveur PVSProuveur PVS

Point technique:

raffinementInvariant de collage

Présentation du ProjetLa Méthode BL’outil PVSL’outil PBSLe prouveur PVSLe prouveur PVSConclusion

Prouveur PVSProuveur PVS

Problème rencontré: Invariant de collage

Bug dans la sémantique de PBS

N

N

Sémantique en langage B

Sémantique PVS

N

Présentation du ProjetLa Méthode BL’outil PVSL’outil PBSLe prouveur PVSLe prouveur PVSConclusion

Prouveur PVSProuveur PVS

ConclusionConclusion

Résultats de la comparaison

Difficultés Rencontrées

Les Ouvertures

Présentation du ProjetLa Méthode BL’outil PVSL’outil PBSLe prouveur PVSConclusionConclusion