Write a Blog >>
ICSE 2020
Wed 24 June - Thu 16 July 2020

A challenge that has gathered much attention in recent years is automated synthesis of correct-by-construction software systems from declarative specifcations. The specifcation language is typically a subset of linear temporal logic called generalized reactivity of rank 1, for which there exists an efcient synthesis algorithm. Specifications in this language model the system as the interaction between an environment and a controller, the former satisfying a set of assumptions and the latter a set of guarantees. In order for a solution to exist, a sufcient set of assumptions implying the guarantees must be provided. The assumptions must be as general as possible and small enough to be intelligible by engineers that need to assess their consistency with the true environment where the synthesized controller will operate. The search for such assumptions is generally a refinement approach driven by counterstrategies, characterizations of undesirable environment behaviors that force the violation of the guarantees; assumptions are progressively refined in order to exclude such behaviors. In this work we provide a heuristic to drive this counterstrategy-guided search towards smaller refinements. We define a concept of minimality of refinements with respect to counterstrategies and provide an algorithm that provably finds minimal refnements with little time overhead. We show experimentally that it consistently produces one or more shorter solutions than state of the art for a set of popular case studies. We also demonstrate that in a popular case study (AMBA-AHB protocol) our heuristic finds a close-to-optimal solution that cannot be found by previous fully automated approaches.