ML Security PapersRobustFSM: Submodular Maximization in Federated Setting with Malicious Clients
Duc A. Tran , Dung Truong , Duy Le
Published on arXiv
2511.02029
Data Poisoning Attack
OWASP ML Top 10 — ML02
Key Finding
RobustFSM improves solution quality by up to 200% over conventional federated submodular maximization when malicious clients are active, with gains depending on dataset and attack severity.
RobustFSM
Novel technique introduced
Submodular maximization is an optimization problem benefiting many machine learning applications, where we seek a small subset best representing an extremely large dataset. We focus on the federated setting where the data are locally owned by decentralized clients who have their own definitions for the quality of representability. This setting requires repetitive aggregation of local information computed by the clients. While the main motivation is to respect the privacy and autonomy of the clients, the federated setting is vulnerable to client misbehaviors: malicious clients might share fake information. An analogy is backdoor attack in conventional federated learning, but our challenge differs freshly due to the unique characteristics of submodular maximization. We propose RobustFSM, a federated submodular maximization solution that is robust to various practical client attacks. Its performance is substantiated with an empirical evaluation study using real-world datasets. Numerical results show that the solution quality of RobustFSM substantially exceeds that of the conventional federated algorithm when attacks are severe. The degree of this improvement depends on the dataset and attack scenarios, which can be as high as 200%
Key Contributions
- RobustFSM: a federated submodular maximization algorithm robust to various practical client attacks including malicious clients sharing fake local information
- Formal analysis of attack models specific to the federated submodular maximization setting, distinguishing them from standard FL backdoor/poisoning attacks
- Empirical evaluation on real-world datasets showing up to 200% improvement in solution quality over naive federated algorithms under severe attack scenarios
🛡️ Threat Analysis
Malicious clients send fake local information to degrade the federated submodular maximization result — directly analogous to Byzantine attacks in federated learning where malicious participants corrupt aggregation to degrade global model performance. RobustFSM provides robust aggregation as a defense.