  We introduce an optimization-based reconstruction attack capable of
completely or near-completely reconstructing a dataset utilized for training a
random forest. Notably, our approach relies solely on information readily
available in commonly used libraries such as scikit-learn. To achieve this, we
formulate the reconstruction problem as a combinatorial problem under a maximum
likelihood objective. We demonstrate that this problem is NP-hard, though
solvable at scale using constraint programming -- an approach rooted in
constraint propagation and solution-domain reduction. Through an extensive
computational investigation, we demonstrate that random forests trained without
bootstrap aggregation but with feature randomization are susceptible to a
complete reconstruction. This holds true even with a small number of trees.
Even with bootstrap aggregation, the majority of the data can also be
reconstructed. These findings underscore a critical vulnerability inherent in
widely adopted ensemble methods, warranting attention and mitigation. Although
the potential for such reconstruction attacks has been discussed in privacy
research, our study provides clear empirical evidence of their practicability.
