An SMT-based Approach to Coverability Analysis

ABSTRACT. Model checkers based on Petri net coverability have been used successfully in recent years to verify safety properties of concurrent shared-memory or asynchronous message-passing software. We revisit a constraint approach to the problem based on classical Petri net analysis techniques. We show how to utilize an SMT solver to implement the constraint approach, and additionally, to generate a minimized inductive invariant from a safety proof. We empirically evaluate our procedure on a large set of existing Petri net benchmarks. Even though our technique is incomplete, it can quickly discharge all safe instances. Additionally, the inductive invariants computed are usually orders of magnitude smaller than those produced by existing solvers.