Statistical tests for botnet detection in a network

We consider the problem of detecting the presence of a botnet in a network as a hypothesis testing problem, where we are given a single instance of a graph. The null hypothesis is considered the absence of the botnet and is modeled as a random geometric graph. The alternative hypothesis, conversely, is considered the presence of the botnet and has the same geometric structure except that there is a small number of vertices that ignore this structure and simply connect to all other vertices with a certain probability. We propose two tests, the isolated star test and the average distance test, for the hypothesis testing problem. The first test is based on the intuition that the botnet vertices form large isolated stars that are not present in the null hypothesis. The second test is based on the idea that the average graph distance becomes significantly shorter in the presence of a botnet. Under appropriate assumptions on the model parameters, the results show that both tests are asymptotically optimal as the graph size goes to infinity. We accompany our theoretical results for the asymptotic regime with a simulation study to showcase the performance of our tests on graphs of finite size. We observe that the isolated star test has higher power on moderated size networks.