Disproving Inductive Entailments in Separation Logic via Base Pair Approximation

Abstract. We give a procedure for establishing the invalidity of logi-cal entailments in the symbolic heap fragment of separation logic with user-defined inductive predicates, as used in program verification. This disproof procedure attempts to infer the existence of a countermodel to an entailment by comparing computable model summaries, a.k.a. bases (modified from earlier work), of its antecedent and consequent. Our method is sound and terminating, but necessarily incomplete. Experiments with the implementation of our disproof procedure indi-cate that it can correctly identify a substantial proportion of the invalid entailments that arise in practice, at reasonably low time cost. Accord-ingly, it can be used, e.g., to improve the output of theorem provers by returning “no ” answers in addition to “yes ” and “unknown ” answers to entailment questions, and to speed up proof search or automated theory exploration by filtering out invalid entailments.