Abstract. Semantics of description languages for complex systems are a central issue for implementing verification methods such as abstract model checking. This technique is employed to verify systems by inspecting only a small state space that represents
DOI10.1007/s00165-004-0040-y
BCS©2004
FormalAspectsofComputing(2004)16:166–193FormalAspectsofComputingAgeneralizedsemanticsofpromela
forabstractmodelchecking
Mar´ adelMarGallardo,PedroMerinoandErnestoPimentel
Dpto.deLenguajesyCienciasdelaComputaci´on,UniversityofMalaga,29071Malaga,Spain
Abstract.Semanticsofdescriptionlanguagesforcomplexsystemsareacentralissueforimplementingveri ca-tionmethodssuchasabstractmodelchecking.Thistechniqueisemployedtoverifysystemsbyinspectingonlyasmallstatespacethatrepresentsitspotentialbehaviors.Thispaperpresentsageneralizedoperationalsemanticsofthemodellinglanguagepromelathatprovidesthetheoreticalbasistointroducethispromisingmethodinthemodelcheckerspin.Thegeneralizationconsistsofidentifyinglanguageaspectsaffectedbytheabstraction.Usingtheseaspectsasparameters,itispossibletoobtainandrelatedifferentinterpretationsofthelanguage.Thenewsemanticsprovidesaframeworktoreasonabouthowtoconstructthetoolαspinasanextensionofspin.Keywords:Modelchecking;Abstraction;Structuredoperationalsemantics;promela;spin
1.Introduction
Theexistenceofaformalsemanticsforanengineeringdesignlanguageisconvenientinordertohaveanon-ambiguousdescriptionofcomplexsystems,andtoconstructtoolsforanalysis(simulationorveri cation,testing)orforcodegeneration.Nevertheless,consideringasnon-disputabletheneedforasemantics,itisreasonabletoarguethatitsstructurecouldbeorientedtoaspeci capplication.Oneparticularlyinterestingcaseisabstractmodelchecking[CGL94,DGG97],whichusesabstractionstoincreasepowerofmodelchecking[CES86,CGP00]forautomaticveri cation.
Modelcheckingtechniquesallowustodecidewhetheroneorallexecutionsproducedbyamodelofasystemsatisfyatemporallogicformula.Theyworkbygeneratingandinspectingthestatesproducedbythemodel,sotheyareonlyapplicabletosmallormediumsizesystems.Abstractiontechniquesconsistsofreplacingthemodelofthesystemwithanabstractversion,reducingthestate-spacetobeexplored.Manyworksdiscusshowthetoolssupportingabstractmodelcheckingdemandsemanticsbasedtheoreticalframeworkstoensurethattheresultsobtainedwiththeabstractmodelscanbeappliedtotheinitialmodel[CGL94,LGS95,DGG97,GrS97,BLO98,GaM99,RuS99].Mostoftheseworksbasetheconstructionoftheabstractmodelontheabstractinterpretationtheory[CoC77],whichitselfisatheorybasedonsemantics:itisnecessarytorelatethestandardmeaningofaprogramoramodelwiththemeaningoftheabstractversion.Thispaperisdevotedtoasemanticsmak-ingthestudyofthisrelationeasier,andenablingustoincludecorrectabstractionsinthemodelcheckerspin
[Hol91,Hol97,Hol03,Spin].
Themodelcheckerspinisprobablytheoneattractingmostusersinacademicandindustrialenvironments,forseveralreasons.Thetoolimplementsthemostrecentoptimizationmechanisms,anditisfreefornon-commercialuse.Theinputlanguage,promela,isrelativelysmallandsuf cientlyexpressivetorepresentrealisticconcurrentCorrespondenceandoffprintrequeststo:PedroMerino,Email:pedro@lcc.uma.es,Tel.:+34-9-52132752,fax:+34-9-52131397
WorksupportedbyprojectsTIC2002-04309-C02-02andTIC2001-2705-C03-02
更多>>Abstract. One of the current trends in model checking for the ...nition of a semantics framework which allows us to relate di?erent models ...
Model Checking for Modal Logics (Extended Abstract...The semantics of E is dual to A and the ...For timed systems the Independency is generalized ...
Abstract Model Checking of Multi-Applet JavaCard...(actually the variant of PROMELA for the dSpin ...The operational semantics of the graphs, however,...
ABSTRACT TOWARDS APPL... 暂无评价 5页 免费...The semantics of statecharts as implemented in ... to Promela/SPIN for e cient model checking. ...
Verifying properties of a TL model require...更多>>Abstract. SystemC has ... A SystemC/TLM semantics in Promela and its possible applications Claus ...
Abstract Model Checking ... 暂无评价 9页 免费... Slicing promela and its ... 暂无评价 9页 ...1-399) 2 semantics of its execution environment....
Model checking dynamic and hierarchical UML state machines Abstract. This ...The semantics of operators is the same as in PROMELA. – Instance creation...
(2006) Symmetry in temporal logic model checking....2.1. Syntax and Semantics of CTL? , CTL, ...This result is generalized [Clarke et al. 1998]...
semantics of the modeling language, and a simple...“abstract” C code into promela [9] to ...nement checking feature of the fdr model checker ...
π-calculus processes into PROMELA for SPIN veri?...Operational semantics — executions on abstract ...4 Model checking theory for processes Motivation: ...
热门文档