Construction of abstract state graphs with PVS-英文文献.pdf

Construction of abstract state graphs with PVS Susanne Graf and Hassen Saidi VERIMAG Centre Equation Avenue de la Vignate GrenobleGieres fgrafsaidi gimagfr contact author Susanne Graf app eared in the Pro ceedings of CAV LNCS Abstract We describ e in this pap er a metho d based on abstract interpretation which from a theoretical p oint of view is similar to the splitting metho ds prop osed in DGG Dam but the weaker abstract transition relation we use allows us to construct automatically abstract state graphs paying a reasonable price We consider a particular set of abstract states the set of the monomials on a set of state predicates The successor of an abstract state m for a transition 1 of the program is the least monomial satised by all successors via of concrete states 0 satisfying m This successor m can b e determined exactly if for each predicate it i can b e determined if or is a p ostcondition of m for In order to do this we i i use the Pvs theorem prover SOR and our Pvsinterface dened in GS If the tactic used for the pro of of the verication conditions is not p owerful enough only an upp er approximation of the abstract successor m is constructed This allows us to compute upp er approximations of the set of reachable states which is sucient for the verication of in