MAC: Multilevel Autonomous Clustering for Topologically Distributed Anomaly Detection

摘要

Anomaly detection in networks is an important cybersecurity threat detection capability. Anomalies in networks are often not localized to a single point, but are spread over a range of nodes. In this case of distributed anomalies, the anomalies are typically too subtle to detect at an individual-node level, and so require anomaly detection over groups of nodes. But it is usually not known a priori on which subset of nodes to focus, and it is infeasible to check all 2~N subsets of nodes in a network. This renders distributed anomaly detection extremely challenging. An emerging strategy for detecting such anomalies is to apply a detection technique to a hierarchy of clusters of nodes in the network. However, developing such a hierarchy is challenging in large, decentralized networks with no central controller. In this work, we present Multilevel Autonomous Clustering (MAC), a novel local algorithm for self-organized, hierarchical clustering in distributed networks. MAC enables individual devices in a distributed system to determine their cluster membership at multiple levels using only local information, without centralized computation or information about the entire network. The result is an approach to hierarchical graph clustering that is both practical to use in large, real-world systems, as well as effective for distributed anomaly detection. The algorithm is evaluated on both synthetic and real-world networks. Its effectiveness for anomaly detection is demonstrated on various test problems.