View
44
Download
0
Category
Preview:
DESCRIPTION
Conception Formelle en PVS. Présenté par : Roland Atoui Xavier Dumas Sébastien Jardel Laurent Vendredi. Chef de Projet: M. Pierre Castéran. Master 2 ISC. Plan. - PowerPoint PPT Presentation
Citation preview
Conception Formelle en PVSMaster 2 ISC
Chef de Projet: M. Pierre Castran Prsent par: Roland Atoui Xavier Dumas Sbastien Jardel Laurent Vendredi
3- PVS: Prototype Verification System 4- PBS: Support pour la mthode B en PVS 5- Le Prouveur PVS 1- Prsentation du ProjetPlan 6- Conclusion 2- La Mthode B
Prsentation du ProjetVrification de codePrsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
Similitude avec BSinitier PVSTester PBS
La Mthode BFormaliser des spcifications et des programmesPrsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
Machine abstraiteRaffinementImplentation
La Mthode BMACHINE nomSETS ENS1,...,ENS2VARIABLES x1,...,x2INVARIANT IINITIALIZATION S0OPERATIONS...END
Structure d'une Machine Abstraite
Prsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
/* nom de la machine *//* nom des ensembles *//* nom des variables *//* proprit *//* substitution *//* substitutions */
PVS: Prototype Verification SystemUn systme de vrification
Un assistant de preuve dvelopp par le laboratoire dinformatique de SRI International
Fourni une automatisation pour limiter le travail de lutilisateur humain.
Un langage de spcification
Langage expressive :
Ordre logique suprieur Un systme fortement typ (non dcidable) Fonctions rcursives totales
Prsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
Notions prliminairesSets, relations, fonctions, squences, lists, numros, induction.
Assistant de preuveCalcul bas sur les Squents, commandes de preuve primitives, procdure de prcision, arithmtique linaire, congruence[Stratgies, emacs+interface graphique, model checker]
Types Types de base: real, int, nat, boolType de construction: records, abstract data types, functions, predicates, setsType dpendant, type paramtr.
Prsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
PVS: Prototype Verification System
Exemples: person: TYPE = [# age: nat, married?: bool #] List[person] [person nat] [person bool] = pred[person] = setof[person]Proposions.pvs
Propositions : THEORY BEGIN A, B, C: bool prop: THEOREM (A IMPLIES (B IMPLIES C)) AND (A IMPLIES B) AND (A IMPLIES B) AND (A IMPLIES C) END propositions
Prsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
PVS: Prototype Verification System
PBS: Support pour la mthode B en PVSDvelopp par Csar Muoz en 1999Traduit une machine abstraite B en Thorie PVSDvelopp en utilisant lapproche du Shallow Embeddingm.pbs*.pvsm.pvsPrsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
PBS: Support pour la mthode B en PVSUne Machine PBS semblable une machine abstraite BPrsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
OPERATIONS reset = BEGIN value := 0 END;
next = PRE value < maxi THEN ANY val WHERE val : NAT & val value THEN value := val END ENDEND
MACHINE Counter(maxi)
CONSTRAINTS maxi : NAT1
VARIABLES value
INVARIANT value : NAT & value
PBS: Support pour la mthode B en PVSUne Machine PBS semblable une machine abstraite BPrsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
OPERATIONS reset = value := 0
next = PRE `value < maxi' THEN ANY val : nat WHERE `val value' THEN value := val ENDANY ENDEND counter
counter [maxi:posnat]: MACHINEBEGIN PVS `IMPORTING finite_sets@top'
VARIABLES value : `nat'
INVARIANT `value
PBS: Support pour la mthode B en PVSQuelques diffrences: Substitution: WHILE structure rcursive de PVS SELECT peut tre simils an PVS Mots Clefs: SETS TYPES Certains mots clefs nexistent pas (CONSTRAINTS, PROPERTIES) Le Raffinement La notion de raffinement existe en PVS Introduite grce 2 invariants dans une machine PBS INVARIANT et REFINE_INVARIANT Prsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
PBS: Support pour la mthode B en PVSThorie PVS de counter gnr par PBSPrsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
%% 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)
PBS: Support pour la mthode B en PVSPrsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
RaffinementIntroduite grce deux invariants :INVARIANTREFINE_INVARIANT
counterRef.pbs
counterRef [maxi:posnat]: REFINEMENT OF counterBEGIN VARIABLES value_ref : `nat'
REFINE_INVARIANT `value_ref
PBS: Support pour la mthode B en PVSPrsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
counterRef.pvs
counterRef [ maxi:posnat ]: THEORY BEGIN%% Refinement Importing IMPORTING counter[maxi]
%% Initialization init : counterRef = LET self = (# value_ref := 0 #) IN self
init_ref : counterRef_Ref = (# counterRef := counterRef.init, counter := counter.init
#)%% Operations
next(self:counterRef) : counterRef = LET self = self WITH [ value_ref := value_ref(self) + 1 ] IN self
next_ref(self_ref:counterRef_Ref | value(counter(self_ref)) < maxi) : counterRef_Ref = (# counterRef := counterRef.next(counterRef(self_ref)), counter := counter.next(counter(self_ref)) #)
END counterRef
Bas sur les squents:
Hypothses | Consquents
Prsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
Prouveur PVS3 tapes:
Vrifier la syntaxe (parser)Vrifier la smantique (typechecker)Prouver les TCCs (prover)
Gnrations de TCCs:
En utilisant les thormesEn utilisant la puissance du typagePrsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
Prouveur PVSPreuves automatiques:
Commande (GRIND)Commande (INDUCT-AND-SIMPLIFY)2 types de preuves:
Preuves itrativesPreuves par induction
Commandes de bas niveau: (CASE), (INDUCT)
Simplifie les preuvesFacilite les preuvesPrsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
Prouveur PVSLes stratgies
UtilitGnraliser les preuves
Point technique:
raffinementInvariant de collagePrsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
Prouveur PVS
Prouveur PVSProblme rencontr:Bug dans la smantique de PBSN N Machine abstraiteRaffinementN Prsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
Conclusion Rsultats de la comparaison
Difficults Rencontrs
Les OuverturesPrsentation du Projet La Mthode B Loutil PVS Loutil PBS Le prouveur PVS Conclusion
Questions ?
**************
Recommended