A Black-Box Approach for Quantifying Leakage of Trace-Based Correlated Data

Quantification of information leakage is crucial, especially for privacy-preserving systems such as location-based services (LBS) with integrated privacy mechanisms. Existing quantification mainly utilized two approaches: i) the white-box approach, precise but impractical for complex systems, and ii) the black-box approach, practical but struggles with scalability for large output spaces. Recently, Machine Learning (ML) algorithms have been integrated into the black-box approach to effectively approximate information leakage for independent observations with better scalability. However, this method does not provide precise estimates for dependent observations. Intuitively, once a correlated secret is discovered, it becomes easier for an attacker to predict related secrets, leading to an underestimation of information leakage. This paper introduces an ML-based black-box approach to improve the accuracy of information leakage estimation for systems with correlated data, particularly in trace-based scenarios. Our solution uses an ML model for rough estimation and leverages data correlations to refine inferences for more accurate quantification. Evaluation results from three real-world datasets and one collected dataset confirm our solution's effectiveness in accurately and cost-effectively quantifying system leakage for correlated observations.