LDPDetect: Efficient Detection and Defense Against Graph Poisoning Attacks Under Local Differential Privacy

Local Differential Privacy (LDP) provides a way to analyze the personal perspectives of decentralized users while strictly protecting individual privacy. However, recent studies have highlighted the vulnerability of the LDP protocol to data poisoning attacks, where malicious users manipulate estimation results by submitting carefully crafted malicious data. In this work, we focus on graph data analysis under LDP and present LDPDetect, a lightweight and easily extensible framework for identifying malicious users without additional information or background knowledge. First, in LDPDetect, we leverage the redundancy of graph data, while taking into account the randomness introduced by LDP, to compute the ratio of inconsistent reports from users about edges to detect malicious users involved in poisoning attacks. Second, we extend LDPDetect to a degree estimation protocol and introduce a method for mitigating degree poisoning attacks, called Degree recovery. Extensive experiments demonstrate that our LDPDetect detection accuracy is very high, approaching 100% in many cases, while our Degree recovery strategy shows good efficacy in input poisoning attacks but loses efficacy in degree deflation attacks under output poisoning attacks, highlighting the complexity of the recovery mechanism.