Pareto fronts for privacy-utility trade-offs in multi-query systems

Multi-query systems have become a common paradigm for enabling flexible access to sensitive data. However, their openness introduces privacy risks, most especially from attribute inference attacks (AIAs), where adversaries infer sensitive attributes by analyzing strategically crafted queries. While defenses such as differential privacy (DP) and query limit help mitigate these risks, determining appropriate privacy parameters, particularly the privacy budget ϵ and the maximum query limit N , to protect privacy while maintaining data utility remains a significant challenge. To address this trade-off, we first introduce a bilevel optimization framework for multi-query systems. We construct a realistic interaction model involving a query-based system (QBS) server, users, and a QueryCheetah-based attacker to capture real-world multi-party dynamics under advanced threat scenarios. Within this framework, the upper level is formulated as a multi-objective optimization problem that seeks to defend against the attacker while satisfying utility requirements by selecting appropriate privacy configurations. The lower level simulates an attacker that optimizes its attribute inference strategy under these configurations. To solve the upper-level optimization problem, we design a task-aware adaptive Non-dominated Sorting Genetic Algorithm II (NSGA-II) to search for Pareto-optimal configurations. The algorithm leverages the monotonicity of privacy and utility metrics, and incorporates dynamic search space pruning and direction-guided mutation to enhance search efficiency and improve solution quality. Extensive experiments demonstrate that our framework can significantly enhance search efficiency and optimization precision given advanced AIA threats.