On detection of malicious users using group testing techniques

Despite decades of research, there have not been developed concrete defense solutions for most of current attacks to Internet services, let alone new attack types. An essential problem to overcome is that malicious traffic can be similar to legitimate ones. Thus a more fundamental model which should be based on the overall performance of servers/subnets without inspecting each traffic must be remedied. Based on this observation, we propose a novel system framework, called Detection of Malicious Users (DMU) which attempts to solve various attack types. Motivated by DMU, we introduce a new theoretical model, called Size Constraint Group Testing (SCGT). Several algorithms based on SCGT for various networking scenarios are proposed. We also provide several fundamental results on SCGT, revealing some necessary conditions to obtain an O(1) detection time algorithm.