  Software debloating can effectively thwart certain code reuse attacks by
reducing attack surfaces to break gadget chains. Approaches based on static
analysis enable a reduced set of functions reachable at a callsite for
execution by leveraging static properties of the callgraph. This achieves low
runtime overhead, but the function set is conservatively computed, negatively
affecting reduction. In contrast, approaches based on machine learning (ML)
have much better precision and can sharply reduce function sets, leading to
significant improvement in attack surface. Nevertheless, mispredictions occur
in ML-based approaches. These cause overheads, and worse, there is no clear way
to distinguish between mispredictions and actual attacks.
  In this work, we contend that a software debloating approach that
incorporates ML-based predictions at runtime is realistic in a whole
application setting, and that it can achieve significant attack surface
reductions beyond the state of the art. We develop a framework, Predictive
Debloat with Static Guarantees (PDSG). PDSG is fully sound and works on
application source code. At runtime it predicts the dynamic callee set
emanating from a callsite, and to resolve mispredictions, it employs a
lightweight audit based on static invariants of call chains. We deduce the
invariants offline and assert that they hold at runtime when there is a
misprediction. To the best of our knowledge, it achieves the highest gadget
reductions among similar techniques on SPEC CPU 2017, reducing 82.5% of the
total gadgets on average. It triggers misprediction checks on only 3.8% of the
total predictions invoked at runtime, and it leverages Datalog to verify
dynamic call sequences conform to the static call relations. It has an overhead
of 8.9%, which makes the scheme attractive for practical deployments.
