Optimized L*-based Assume-Guarantee Reasoning

Sagar Chaki, Ofer Strichman, Proceedings of the 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), LNCS 4424, page 276-291, March 26-30, 2007

Abstract: In this paper, we suggest three optimizations to the L*-based automated Assume-Guarantee reasoning algorithm for the compositional verification of concurrent systems. First, we use each counterexample from the model checker to supply multiple strings to L*, saving candidate queries. Second, we observe that in existing instances of this paradigm, the learning algorithm is coupled weakly with the teacher. Thus, the learner ignores completely the details about the internal structure of the system and specification being verified, which are available already to the teacher. We suggest an optimization that uses this information in order to avoid many unnecessary -- and expensive, since they involve model checking -- membership and candidate queries. Finally, and most importantly, we develop a method for minimizing the alphabet used by the assumption, which reduces the size of the assumption and the number of queries required to construct it. We present these three optimizations in the context of verifying trace containment for concurrent systems composed of finite state machines. We have implemented our approach and experimented with real-life examples. Our results exhibit an average speedup of over 12 times due to the proposed improvements.

PDF / Online © Springer