  Software contracts allow programmers to state rich program properties using
the full expressive power of an object language. However, since they are
enforced at runtime, monitoring contracts imposes significant overhead and
delays error discovery. So contract verification aims to guarantee all or most
of these properties ahead of time, enabling valuable optimizations and yielding
a more general assurance of correctness. Existing methods for static contract
verification satisfy the needs of more restricted target languages, but fail to
address the challenges unique to those conjoining untyped, dynamic programming,
higher-order functions, modularity, and statefulness. Our approach tackles all
these features at once, in the context of the full Racket system---a mature
environment for stateful, higher-order, multi-paradigm programming with or
without types. Evaluating our method using a set of both pure and stateful
benchmarks, we are able to verify 99.94% of checks statically (all but 28 of
49, 861).
  Stateful, higher-order functions pose significant challenges for static
contract verification in particular. In the presence of these features, a
modular analysis must permit code from the current module to escape permanently
to an opaque context (unspecified code from outside the current module) that
may be stateful and therefore store a reference to the escaped closure. Also,
contracts themselves, being predicates wri en in unrestricted Racket, may
exhibit stateful behavior; a sound approach must be robust to contracts which
are arbitrarily expressive and interwoven with the code they monitor. In this
paper, we present and evaluate our solution based on higher-order symbolic
execution, explain the techniques we used to address such thorny issues,
formalize a notion of behavioral approximation, and use it to provide a
mechanized proof of soundness.
