Source-linked AI summary
Is Data Clustering in Adversarial Settings Secure?
Battista Biggio, Ignazio Pillai, Samuel Rota Bulò, Davide Ariu, Marcello Pelillo, Fabio Roli
TL;DR
Clustering has become common in security applications, but deliberate attacks may subvert its output. The paper presents a framework for modeling adversaries and evaluates poisoning and obfuscation attacks on single-linkage clustering. Experiments show vulnerability to attacks using a small input fraction or slight sample manipulation, though findings do not directly generalize to other algorithms.
Problem
Clustering is used in security settings, but its vulnerability to deliberate attacks that subvert clustering remains an open question.
Source: §1 · p. 1Method
The paper models attack goals, system knowledge, and data-manipulation capabilities, then develops poisoning and obfuscation attacks for single-linkage clustering.
Source: §1 · p. 1, §2.1 · p. 2, §4.1 · pp. 5–6Results
Real-world experiments show single-linkage clustering can be significantly vulnerable when attackers control a small fraction of input data or slightly manipulate attack samples.
Source: §6 · p. 10Takeaways & Limitations
Tailored attacks can significantly alter single-linkage clustering output to meet an adversary’s goal.
Source: §6 · p. 10The empirical vulnerability results cannot be directly generalized to other clustering algorithms.
Source: §6 · p. 10
Abstract
from arXiv · showhide
Clustering algorithms have been increasingly adopted in security applications to spot dangerous or illicit activities. However, they have not been originally devised to deal with deliberate attack attempts that may aim to subvert the clustering process itself. Whether clustering can be safely adopted in such settings remains thus questionable. In this work we propose a general framework that allows one to identify potential attacks against clustering algorithms, and to evaluate their impact, by making specific assumptions on the adversary's goal, knowledge of the attacked system, and capabilities of manipulating the input data. We show that an attacker may significantly poison the whole clustering process by adding a relatively small percentage of attack samples to the input data, and that some attack samples may be obfuscated to be hidden within some existing clusters. We present a case study on single-linkage hierarchical clustering, and report experiments on clustering of malware samples and handwritten digits.
1. INTRODUCTION
Clustering supports analysis of large unlabeled datasets, including security tasks, but deliberate data injection may subvert the process. This motivates security evaluation designed for targeted adversarial manipulation.
1. INTRODUCTION
- Security applications use clustering to analyze data such as malware, DNS traffic, repackaged apps, and attack sources collected in the wild.Such unsupervised collection can give attackers an opportunity to inject crafted samples and make inferred knowledge useless.Source: §1 · p. 1
- Stability analyses address stochastic noise, whereas adversarial manipulations can target the clustering algorithm specifically.The introduction notes that stability results therefore cannot directly evaluate this threat.Source: §1 · p. 1
- Earlier work described fringe-cluster hiding and bridge-based merging, but a systematic security-evaluation framework and specific countermeasures were missing.The paper proposes a framework based on assumptions about attacker goals, system knowledge, and data-manipulation capabilities.Source: §1 · p. 2
2. ATTACKING CLUSTERING
The framework represents clustering broadly and organizes attack design around the adversary’s goal, knowledge, and capabilities. It then uses those assumptions to specify an attack strategy.
2. ATTACKING CLUSTERING
- The framework models clustering as a mapping from a dataset to a result, which may be a partition or a more general family or hierarchy of subsets.This formulation is intended to apply across different clustering representations.Source: §2 · p. 2
2.1 Adversary’s goal
- Integrity attacks redirect selected samples while limiting changes to the original clustering; availability attacks worsen clustering broadly, while privacy attacks seek information about users.The framework also distinguishes targeted from indiscriminate attack specificity.Source: §2.1 · p. 2
2.2 Adversary’s knowledge
- Attacker knowledge ranges from partial data or feature knowledge to knowledge of the clustering algorithm and its initialization.A surrogate dataset may be collected from the same source as the target data.Source: §2.2 · pp. 2–3
2.3 Adversary’s capability
- The capability model allows causative manipulation of clustered data, including adding samples and bounding how much attack samples can be modified.The paper motivates these constraints with collected malware and the need to preserve malicious functionality.Source: §2.3 · p. 3
2.4 Attack strategy
- An attack strategy optimizes the adversary’s objective subject to knowledge and capability constraints, with uncertainty represented by a distribution over possible knowledge states.The framework also models feasible manipulated samples and evaluates the attack objective under that uncertainty.Source: §2.4 · p. 3
3. PERFECT KNOWLEDGE ATTACKS
Under perfect knowledge, the paper formalizes poisoning and obfuscation as distinct attack objectives. Poisoning worsens clustering, while obfuscation steers selected samples toward a target clustering while preserving the original-data clustering.
3. PERFECT KNOWLEDGE ATTACKS
- Perfect-knowledge attacks assume the adversary knows the system and include poisoning and obfuscation as worst-case integrity or availability violations.The model sets the knowledge distribution to a point mass on exact system knowledge.Source: §3 · p. 3
3.1 Poisoning attacks
- Poisoning maximizes the distance between original and attacked clusterings by adding up to m attack samples constrained to a feature-value box.With hard assignments, the proposed distance counts sample pairs grouped together in one clustering but not the other; poisoning samples need not preserve any separate malicious function.Source: §3.1 · pp. 3–4
3.2 Obfuscation attacks
- Obfuscation moves given attack samples toward a target clustering while constraining changes to those samples and preserving the clustering of the original data.The allowed change is bounded by dmax; the paper’s case study uses the largest Euclidean distance between corresponding original and manipulated samples.Source: §3.2 · p. 4
4. A CASE STUDY ON SINGLE-LINKAGE HIERARCHICAL CLUSTERING
The case study applies the attack framework to single-linkage hierarchical clustering, a method used in security-sensitive tasks. It develops heuristic approaches for poisoning and obfuscation under a worst-case attacker model.
4.1 Poisoning attacks
- The poisoning objective cannot be predicted analytically for hierarchical clustering, motivating search heuristics; even k-means variability across initializations can make perturbation outcomes difficult to predict.The stated k-means example cautions that a clearer mathematical formulation alone does not guarantee reliable prediction.Source: §4.1 · p. 5
- Bridge search tests the k −1 dendrogram cut connections as candidate attack points, and the hard approximation selects the bridge between the largest adjacent clusters.In the illustrated example, adding m = 20 attack samples fragments initial clusters into smaller groups containing points from different original clusters.Source: §4.1 · p. 5, Figure 1 · p. 5
- The soft-assignment heuristic smooths the attack objective with KDE posterior estimates, helping favor bridges that may connect larger clusters over multiple attack iterations.Bandwidths that make assignments uniformly probabilistic or equivalent to hard assignments are avoided; the paper selects bandwidth comparable to average pairwise distance.Source: §4.1 · p. 6
4.2 Obfuscation attacks
- For obfuscation, each attack sample is moved toward its nearest sample in the desired cluster, up to the maximum allowed distance.The heuristic approximates the attacked clustering while minimizing disruption to the clustering of non-manipulated samples.Source: §4.2 · p. 6
5. EXPERIMENTS
Experiments evaluate poisoning and obfuscation attacks against single-linkage hierarchical clustering under perfect knowledge, using artificial, malware, and handwritten-digit data.
5.1.1 Artificial data
- At 20% poisoning, bridge heuristics outperform random attacks; Bridge (Soft) and Bridge (Hard) split initial clusters into approximately 3.8 clusters, while final clusters merge approximately 1.2 initial clusters on average.Bridge (Best) instead induces more merging than splitting, which is not optimal for the attacker's goal.Source: Table 1 · p. 7, §5.1.1 · pp. 7–8
5.1.2 Malware clustering
- At 5% poisoning, Bridge (Soft) increasingly outperforms other approaches; Bridge (Soft) and Bridge (Hard) split each of 3 initial clusters into 2.7 and 2.4 final clusters, yielding about 20–25 clusters.Random is ineffective: each injected sample creates a new cluster without changing the objective function.Source: §5.1.2 · p. 8
5.1.3 Handwritten digits
- At 0.2% control, bridge methods fragment the initial clusters into an average of 33 final clusters, while random attacks are ineffective in the high-dimensional feature space.The final clusters remain almost pure rather than merging samples from different initial clusters.Source: §5.1.3 · pp. 8–9
- Bridge-based samples initially resemble the digits they aim to connect; later samples seek additional connections after the original clusters have been destroyed.The attack produces noisy images under random strategies, while bridge-based strategies target connections between 0 and 6 or 1 and 6.Source: Figure 3 · p. 8, §5.1.3 · p. 9
5.2.1 Handwritten digits
- At dmax approximately 3–4, the attacker's objective is almost zero and three clusters match its goal; above 4, the algorithm returns to four clusters and separates some attack samples.For dmax in [2, 4], the manipulated samples still significantly resemble the original digit 3.Source: Figure 4 · p. 9, §5.2.1 · p. 10
- The obfuscation task targets merging 100 digit-3 samples with digit 6 while preserving separate clusters for digits 0 and 1.The attacker seeks this desired clustering without significantly affecting normal system operation.Source: §5.2.1 · p. 9
6. CONCLUSIONS AND FUTURE WORK
The paper introduces a framework for evaluating clustering security and shows that tailored attacks can significantly compromise single-linkage clustering. Its findings are bounded by algorithm-specific vulnerabilities and heuristic attack strategies, with several directions left for future work.
6. CONCLUSIONS AND FUTURE WORK
- Tailored attacks can significantly compromise single-linkage clustering when an adversary controls a small fraction of the input or slightly manipulates attack samples.The experiments show that attacks can alter clustering output to meet the adversary’s goal.Source: §6 · p. 10
- Single-linkage’s closest-point inter-cluster distance enables efficient bridges; averages or density estimation may resist poisoning, but not necessarily obfuscation.The empirical results cannot be directly generalized to other algorithms.Source: §6 · p. 10
- Finding optimal attacks for arbitrary clustering algorithms is hard, so the analysis relies on algorithm-dependent heuristics; designing secure clustering algorithms remains unaddressed.The authors propose exploring black-box search and algorithms that model clustering under attack as a game.Source: §6 · p. 10
- The experiments’ feature modifications mapped directly to real attack samples, but inversion may be cumbersome for more complex feature representations and requires application-specific treatment.Future work also considers limited attacker knowledge and links between clustering stability and security.Source: §6 · p. 10
- Future directions include studying robustness to non-targeted perturbations and developing theoretical bounds on how individual attack points affect clustering output.Clustering-stability results may also support this analysis.Source: §6 · p. 11