文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > A Generalized Semantics of Promela for Abstract Model Checking
侵权投诉

A Generalized Semantics of Promela for Abstract Model Checking

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

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email