  Modern machine learning pipelines leverage large amounts of public data,
making it infeasible to guarantee data quality and leaving models open to
poisoning and backdoor attacks. However, provably bounding model behavior under
such attacks remains an open problem. In this work, we address this challenge
and develop the first framework providing provable guarantees on the behavior
of models trained with potentially manipulated data. In particular, our
framework certifies robustness against untargeted and targeted poisoning as
well as backdoor attacks for both input and label manipulations. Our method
leverages convex relaxations to over-approximate the set of all possible
parameter updates for a given poisoning threat model, allowing us to bound the
set of all reachable parameters for any gradient-based learning algorithm.
Given this set of parameters, we provide bounds on worst-case behavior,
including model performance and backdoor success rate. We demonstrate our
approach on multiple real-world datasets from applications including energy
consumption, medical imaging, and autonomous driving.
