  We present a new approach to automated reasoning about higher-order programs
by endowing symbolic execution with a notion of higher-order, symbolic values.
Our approach is sound and relatively complete with respect to a first-order
solver for base type values. Therefore, it can form the basis of automated
verification and bug-finding tools for higher-order programs.
  To validate our approach, we use it to develop and evaluate a system for
verifying and refuting behavioral software contracts of components in a
functional language, which we call soft contract verification. In doing so, we
discover a mutually beneficial relation between behavioral contracts and
higher-order symbolic execution.
  Our system uses higher-order symbolic execution, leveraging contracts as a
source of symbolic values including unknown behavioral values, and employs an
updatable heap of contract invariants to reason about flow-sensitive facts.
Whenever a contract is refuted, it reports a concrete counterexample
reproducing the error, which may involve solving for an unknown function. The
approach is able to analyze first-class contracts, recursive data structures,
unknown functions, and control-flow-sensitive refinements of values, which are
all idiomatic in dynamic languages. It makes effective use of an off-the-shelf
solver to decide problems without heavy encodings. The approach is competitive
with a wide range of existing tools---including type systems, flow analyzers,
and model checkers---on their own benchmarks. We have built a tool which
analyzes programs written in Racket, and report on its effectiveness in
verifying and refuting contracts.
