  Bootstrap aggregating (bagging) is an effective ensemble protocol, which is
believed can enhance robustness by its majority voting mechanism. Recent works
further prove the sample-wise robustness certificates for certain forms of
bagging (e.g. partition aggregation). Beyond these particular forms, in this
paper, \emph{we propose the first collective certification for general bagging
to compute the tight robustness against the global poisoning attack}.
Specifically, we compute the maximum number of simultaneously changed
predictions via solving a binary integer linear programming (BILP) problem.
Then we analyze the robustness of vanilla bagging and give the upper bound of
the tolerable poison budget. Based on this analysis, \emph{we propose hash
bagging} to improve the robustness of vanilla bagging almost for free. This is
achieved by modifying the random subsampling in vanilla bagging to a hash-based
deterministic subsampling, as a way of controlling the influence scope for each
poisoning sample universally. Our extensive experiments show the notable
advantage in terms of applicability and robustness.
