  Local differential privacy (LDP), which enables an untrusted server to
collect aggregated statistics from distributed users while protecting the
privacy of those users, has been widely deployed in practice. However, LDP
protocols for frequency estimation are vulnerable to poisoning attacks, in
which an attacker can poison the aggregated frequencies by manipulating the
data sent from malicious users. Therefore, it is an open challenge to recover
the accurate aggregated frequencies from poisoned ones.
  In this work, we propose LDPRecover, a method that can recover accurate
aggregated frequencies from poisoning attacks, even if the server does not
learn the details of the attacks. In LDPRecover, we establish a genuine
frequency estimator that theoretically guides the server to recover the
frequencies aggregated from genuine users' data by eliminating the impact of
malicious users' data in poisoned frequencies. Since the server has no idea of
the attacks, we propose an adaptive attack to unify existing attacks and learn
the statistics of the malicious data within this adaptive attack by exploiting
the properties of LDP protocols. By taking the estimator and the learning
statistics as constraints, we formulate the problem of recovering aggregated
frequencies to approach the genuine ones as a constraint inference (CI)
problem. Consequently, the server can obtain accurate aggregated frequencies by
solving this problem optimally. Moreover, LDPRecover can serve as a frequency
recovery paradigm that recovers more accurate aggregated frequencies by
integrating attack details as new constraints in the CI problem. Our evaluation
on two real-world datasets, three LDP protocols, and untargeted and targeted
poisoning attacks shows that LDPRecover is both accurate and widely applicable
against various poisoning attacks.
