Hahn-Klimroth, Maximilian GrischaMaximilian GrischaHahn-KlimrothKaaser, DominikDominikKaaserRau, MalinMalinRau2024-09-132024-09-132024-0744th IEEE International Conference on Distributed Computing Systems, ICDCS 20249798350386059https://hdl.handle.net/11420/49064The goal of (network) intrusion detection systems is to identify unauthorized or malicious activities within a computer network. In this work we consider the following theoretical model for intrusion detection systems in large data center networks. We assume that the network is modeled as a leaf-spine-architecture with m spine nodes and n leaves. In a sequence of observation periods, each spine node stores a snapshot of the communication graph and accumulates (an approximation of) the number of alerts caused by suspicious behavior. To identify the responsible malicious nodes, we apply a distributed reconstruction algorithm based on quantitative group testing: In quantitative group testing we are given a binary signal of Hamming weight k along with a querying method. Each query pools multiple entries of together and returns the sum of the entries in the pool. The goal is to reconstruct using as few queries as possible. Our contributions in this paper are three-fold. First we mathematically analyze a distributed reconstruction algorithm for the quantitative group testing instance induced by our intrusion detection model. In particular, we analyze the performance assuming a communication graph where each leaf sends Geom(p) many packets to the spine nodes in each time interval, where p is a parameter of the model. Second, we prove that our algorithm achieves a performance that is optimal up to logarithmic factors. Finally, we simulate our approach and provide empirical data that show that our approach works well in practice. The main novelty of our analysis is that the test-design is given by the communication graphs that are accumulated in multiple observation periods. This is in contrast to classical group testing where the algorithm is allowed to decide on the test design, and we believe that our analysis of non-standard test designs is of independent interest to the distributed group testing community.enGroup TestingIntrusion DetectionLeaf-Spine ArchitecturePooled DataReconstruction AlgorithmComputer Science, Information and General Works::005: Computer Programming, Programs, Data and SecurityNatural Sciences and Mathematics::510: MathematicsConference Paper10.1109/ICDCS60910.2024.00027Conference Paper