  Although state-of-the-art PDF malware classifiers can be trained with almost
perfect test accuracy (99%) and extremely low false positive rate (under 0.1%),
it has been shown that even a simple adversary can evade them. A practically
useful malware classifier must be robust against evasion attacks. However,
achieving such robustness is an extremely challenging task.
  In this paper, we take the first steps towards training robust PDF malware
classifiers with verifiable robustness properties. For instance, a robustness
property can enforce that no matter how many pages from benign documents are
inserted into a PDF malware, the classifier must still classify it as
malicious. We demonstrate how the worst-case behavior of a malware classifier
with respect to specific robustness properties can be formally verified.
Furthermore, we find that training classifiers that satisfy formally verified
robustness properties can increase the evasion cost of unbounded (i.e., not
bounded by the robustness properties) attackers by eliminating simple evasion
attacks.
  Specifically, we propose a new distance metric that operates on the PDF tree
structure and specify two classes of robustness properties including subtree
insertions and deletions. We utilize state-of-the-art verifiably robust
training method to build robust PDF malware classifiers. Our results show that,
we can achieve 92.27% average verified robust accuracy over three properties,
while maintaining 99.74% accuracy and 0.56% false positive rate. With simple
robustness properties, our robust model maintains 7% higher robust accuracy
than all the baseline models against unrestricted whitebox attacks. Moreover,
the state-of-the-art and new adaptive evolutionary attackers need up to 10
times larger $L_0$ feature distance and 21 times more PDF basic mutations
(e.g., inserting and deleting objects) to evade our robust model than the
baselines.
