Logic in Computer Science (LICS 2001)

Invited Talk: Successive Approximation of Abstract Transition Relations (at LICS 2001)

Authors: Satyaki Das David L. Dill

Abstract

Recently we have improved the efficiency of the predicate abstraction scheme presented in [7]. As a result the number of validity checks needed to prove the necessary verification condition has been reduced. The key idea is to refine an approximate abstract transition relation based on the counter-example generated. The system starts with an approximate abstract transition relation on which the verification condition (in our case this is a safety property) is model checked. If the property holds then the proof is done. Otherwise the model checker returns an abstract counter-example trace. This trace is used to refine the abstract transition relation if possible and start anew. At the end of the process the system either proves the verification condition or comes up with an abstract counter-example trace which holds in the most accurate abstract transition relation possible (with the user provided predicates as a basis). If the verification condition fails in the abstract system then either the concrete system does not satisfy it or the abstraction predicates chosen are not strong enough. This algorithm has been used on a concurrent garbage collection algorithm and a secure contract signing protocol. This method improved the performance on the first problem significantly and allowed us to tackle the second problem which the previous method could not handle.

BibTeX

  @InProceedings{DasDill-SuccessiveApproxima,
    author = 	 {Satyaki Das and David L. Dill},
    title = 	 {Successive Approximation of Abstract Transition Relations},
    booktitle =  {Proceedings of the Sixteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2001},
    year =	 2001,
    editor =	 {Joseph Halpern},
    month =	 {June}, 
    pages =      {51--60},
    location =   {Boston, MA, USA}, 
    note =       {Invited Talk},
    publisher =	 {IEEE Computer Society Press}
  }