  We introduce heap automata, a formalism for automatic reasoning about
robustness properties of the symbolic heap fragment of separation logic with
user-defined inductive predicates. Robustness properties, such as
satisfiability, reachability, and acyclicity, are important for a wide range of
reasoning tasks in automated program analysis and verification based on
separation logic. Previously, such properties have appeared in many places in
the separation logic literature, but have not been studied in a systematic
manner. In this paper, we develop an algorithmic framework based on heap
automata that allows us to derive asymptotically optimal decision procedures
for a wide range of robustness properties in a uniform way. We implemented a
protoype of our framework and obtained promising results for all of the
aforementioned robustness properties. Further, we demonstrate the applicability
of heap automata beyond robustness properties. We apply our algorithmic
framework to the model checking and the entailment problem for symbolic-heap
separation logic.
