Adversarial Distance Metrics: A Threat to Fairness in Clustering-Based Decision Systems

Abstract

: Clustering algorithms are increasingly deployed in high-stakes decision-making systems under the assumption that transparent, explainable methods using standard distance metrics are inherently trustworthy. We challenge this assumption by demonstrating a configuration-based attack exploiting ε -semimetric distance functions, which satisfy nearly all properties of a topological metric while allowing arbitrary manipulation of pairwise distances. Building on the mathematical framework of ε -semimetrics introduced in prior work, we make three novel contributions: (1) we formalize a threat model in which an insider adversary manipulates the distance function to induce discriminatory clustering outcomes against demographic groups , exposing a gap in current fairness auditing practices that focus on data integrity and algorithm transparency but overlook configuration integrity; (2) we provide empirical feasibility analysis demonstrating successful attacks on K-means, DBSCAN, and agglomerative clustering with 100% manipulation accuracy for sample sizes up to m = 130, with construction cost O ( m 6 ) , and validate the attack on real census data (UCI Adult Income), demonstrating that Demographic Parity Difference increases from 0.200 to the theoretical maximum of 1.000 under attack; and (3) we propose concrete defenses including cryptographic metric commitment and statistical detection methods. The attack is most feasible for targeted discrimination affecting small groups ( m < 50, under 30 seconds), precisely where aggregate fairness statistics lack power to detect violations. Our findings demonstrate the urgent need to expand the scope of the algorithmic audit to include distance-function verification.