軟件理論基礎(chǔ)電子教案slide

BüchiautomatonModelCheckingM3CModelBüchiautomatonModelCheckingM3CModel?finite?pushdown?Turing?counter?timed?hybrid?Petri?messagesequence?Modelsfor?Systemsunder ysisarerepresentedbytransitionsystems.TimedExamplesofAnumericalcodedoorAvendingAtime-Themodel,Themodel,Timedautomaton:Finiteautomatonenrichedwithclocks.TransitionsareequippedwithguardsX={x,yTransitionsareequippedwithguardsandsetsofresetclocksTimedautomata:AtimedautomatonisaA=(L,L0,Lacc,Σ,X,ELfinitesetof L0?Linitial Lacc?Lsetofaccepting ΣfiniteXfinitesetof E?L×G×Σ×2X×Lsetof whereG={?x?c|xX,cN}isthesetofLL={l0,l1,l2L0=Lacc={l2Σ={a,X={x,Valuation:vRxassignstoeachclockaclock-State:(l,v)L×RxcomposedofalocationandTransitionsbetweenstatesofA:Delaytransitions:(l,v)τ(l,v+τ)if?(l,g,a,Y,l’)Ewithv|=gandv'(x)RunofA(l0,v0)→(l0,v0+τ1)→(l1,v1)→(l1,v1+τ2)→···→(lk,vorsequenceoverR+.Timedword:w=(σ,t)=(ai,ti)1≤i≤k,whereaiΣandtimew=(a0,t0)(a1,t1)···(ak,isacceptedinA,ifthereisa01(l,vk1kwithl0L0,lk+1Lacc,andtiL(A)={w|wacceptedbyBacktotheNB:Intheexamples,we?theguardwhenitisequivalenttott,?theresetsetwhenitisw=(b,0.1)(b,0.3)(a,1.3)(b,1.5)(a,1.5)(b,isanacceptedtimedword.AnacceptingrunforwL(A)={(a,t1)···(a,tk)|?i<j,tj?ti=actionb?BüchiautomatonModelCheckingM3CModelBüchiBüchiAutomatonwhichacceptsinfinitetracesABüchiautomatonisA=(S,,,L,I,Sisafinitesetofstates SSisatransitionL:S→2AP ISisasetofinitialstates FSisasetofacceptingBüchiAofAisacceptediffitcontainsacceptingstatesinfini yoften.WeassociatewithAthe-L(A)={L()|isanacceptingrunofwisacceptedbyAifw……TimedBüchiM3CModelCheckerEmbeddedEmbeddedSystemsBugsareFormalModelCheckingWhen,Why,How?EmbeddedSystemsBugsareFormalModelCheckingWhen,Why,How?SoftwareSoftwareis SoftwareSoftwareisFullofBugsIntheNASAcriticalmissionsoftwareerrorstatistics,0.025errorswith0.4errorswith6.3errorswith1Mb100missioncriticalerrorswith10Mb.Clearly,itpresentsanunacceptableWhysomanySoftwareEngineeringisverycomplexComplicatedalgorithmsFromtherecentNASA’sthesizeofsoftwarecodeisdoublingevery3-4years.Becauseofthisincreaseincomplexity,thelikelihoodofsubtleerrorsismuch 。BugsareBugsareSomeerrorsmaycauselossofY2KEstimatedcost:>$500BillionNortheastBlackoutof2003Estimatedcost:$6-$10BillionTestingonlyshowspresenceofbugs,nottheirImprovementsintestingcanreducethecostofsoftwarebugsbyathird,butwillnoteliminatethemcompley WhySoEmbeddedSystemsBugsareFormalModelCheckingWhen,Why,How?Amajorgoalofsoftwareistoenabledeveloperstoconstructthiscomplexitydealwiththiscomplexity!WhatSoftwareEngineersNeedToolsthatgivebetterconfidencethanfullyautomaticapplyeffectivelyapplytorealsoftwareFormalFormalFormalmethodsaremathematicallybasedandverifyingsuchsystems.UseofformalmethodscangreatlyincreaseourunderstandingofasystembyFormalVerificationCompletewithrespecttoagivenpropertyCorrectnessisguaranteedNoneedtogenerateexpectedoutputsequences.CangenerateashorttraceifapropertyfailsFormalverificationisusefultofindbugsindesignConsiderationofallcasesisimplicitinformalEmbeddedSystemsBugsareFormalModelCheckingWhen,Why,How?示系統(tǒng)的行為，用模態(tài)／時序邏輯(F)描 表示為S╞F．ModelsystemGeneratepossiblestatesfromthemodelthencheckwhethergivenpropertiesaresatisfiedwithintheModel ModelModel界．許多大公司，如In、HP、Phillips等成立了專E.M.E.A.J.WhenWhendoweuseToverifyfinitestateconcurrentsystemssequentialcircuitdesignProtocolverificationProgramverificationsoftware,trafficlights,..Whymodelcheckdecisionsmade…andwhereAdvantageofAdvantageofModelFindandcorrecterrorsearlyinthedevelopmentGainbetterunderstandingofthesystemGainhigh-levelofconfidenceincorrectnessofHowdoesit(desiredcheckrealAllAllMCsspecificationlanguage–tobehaviourof–logicfore.g.LTL,CTL,TCTL,PCTL,semanticmodel(usuallyaKripkeorMarkovMCbuildsagraph(statespace)relatingtheKS,whichmustbesearchedModelexpressedasabooleanformulaandrepresentedasBDDModelExampleSPIN(SimplePromelaInterpreter)HolzmannSMV(SymbolicModelVerifier)McMillanUppaal(UPPsalaandAALborg)今）。NASA的PVS定理證明庫（1999至今）。微軟研發(fā)MODIST系統(tǒng)，用于分布式系英國：牛津大學(xué)計(jì)算提出PRISM系統(tǒng)，用 Logic:Searchstrategy:DFSExplicitstateProcessescommunicateviasynchronous/asynchronouschannels.HasbeenusedtoOperatingsystems,railwaysignallingsystems,featureinctionysis,flightsoftware,MarsExplorationRovers(MER) Logic:Searchstrategy:BFSusedtoAvionicstriplesensorvoter,channel,T9000NuSMV:Cimattietal,AddedGUIandLTLmodel Uppaal–LarsonetRealtimemodelcheckerSpecificationlanguage:TimedautomataLogic:Uppaallogic(subsetofTCTL)Searchstrategy:BFSofsymbolicstateCombinationofexplicitFinitecontrolstructure+realvaluedHasbeenusedtopowercontroller,gearboxcontroller,TDMAprotocolstartupmechanism protocol,QoSalarea reactivemoduleslanguage,likeSMV)Logic:PCTLorCSLCommunicationviasharedSupports3typesofDiscretetimeMarkovchains(DTMCs)ContinuoustimeMarkovchains(CTMCs)Markovdecisionprocesses(MDPs) ysisusingcosts/rewardsCanrunHasbeenusedtoverifysignallingpathwaysinsystemsbiology,PINblockattacks,communicationsprotocols(e.g.bluetooth,SMAC),aviationsecurity EmbeddedSystemsBugsareFormalM