Conception Formelle en PVS Master 2 ISC Chef de Projet: M. Pierre Castéran Présenté par: Roland Atoui Xavier Dumas Sébastien Jardel Laurent Vendredi 21/05/2014

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.



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



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


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


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


%% 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



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


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



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


Les stratégies

UtilitéesGénéraliser les preuves


Point technique:

raffinementInvariant de collage



Problème rencontré: Invariant de collage

Bug dans la sémantique de PBS

N

N

Sémantique en langage B

Sémantique PVS

N



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

Documents

Conception Formelle en PVS Master 2 ISC Chef de Projet: M. Pierre Castéran Présenté par: Roland Atoui Xavier Dumas Sébastien Jardel Laurent Vendredi 21/05/2014