Performance Analysis of Peer-To-Peer Botnets using “The Storm Botnet” as an Exemplar by Sudhir Agarwal BEng, Siddaganga Institute of Technology, Tumkur, Karnataka, India, 2005 A Dissertation Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Science in the Department of Computer Science (cid:13)c Sudhir Agarwal, 2010 University of Victoria All rights reserved. This dissertation may not be reproduced in whole or in part, by photocopying or other means, without the permission of the author. ii Performance Analysis of Peer-To-Peer Botnets using “The Storm Botnet” as an Exemplar by Sudhir Agarwal BEng, Siddaganga Institute of Technology, Tumkur, Karnataka, India, 2005 Supervisory Committee Dr. Sudhakar Ganti, Co-Supervisor (Department of Computer Science) Dr. Stephen Neville, Co-Supervisor (Department of Electrical and Computer Engineering) Dr. Kui Wu, Departmental Member (Department of Computer Science) Dr. Issa Traore, External Examiner (Department of Electrical and Computer Engineering) iii Supervisory Committee Dr. Sudhakar Ganti, Co-Supervisor (Department of Computer Science) Dr. Stephen Neville, Co-Supervisor (Department of Electrical and Computer Engineering) Dr. Kui Wu, Departmental Member (Department of Computer Science) Dr. Issa Traore, External Examiner (Department of Electrical and Computer Engineering) ABSTRACT Among malicious codes like computer viruses and worms, botnets have attracted a significant attention and have been one of the biggest threats on the Internet. Botnets have evolved to incorporate peer-to-peer communications for the purpose of propagating instructions to large numbers of computers (also known as bot) under the botmaster’s control. The impact of the botnet lies in its ability for a bot master to execute large scale attacks while remaining hidden as the true director of the attack. One such recently known botnet is the Storm botnet. Storm is based on the Overnet Distributed Hash Table (DHT) protocol which in turn is based on the Kademlia DHT protocol. Significant research has been done for determining its operational size, behaviour and mitigation approaches. In this research, the peer-to-peer behaviour of Storm is studied by simulating its actual packet level network behaviour. The packet level simulator is developed via the simulation framework OMNET++ to determine the impact of design parame- ters on botnets performance and resilience. Parameters such as botnet size, peer list size, the number of bot masters and the key propagation time have been explored. Furthermore, two mitigation strategies are considered: a) random removal strategy (disinfection strategy), that removes selected bots randomly from the botnet; b) Sybil iv disruption strategy, that introduces fake bots into the botnet with the task of prop- agating Sybil values into the botnet to disrupt the communication channels between the controllers and the compromised machines. The simulation studies demonstrate that Sybil disruption strategies outperform random removal strategies. The simula- tion results also indicate that random removal strategies are not even effective for a small sized networks. The results of the simulation studies are particularly applicable to the Storm botnet but these results also provide insights that can be applied to peer-to-peer based botnets in general. v Contents Supervisory Committee ii Abstract iii Table of Contents v List of Tables vii List of Figures viii Acknowledgements xi Dedication xii 1 Introduction 1 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Background and Related Work 7 2.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Peer-to-Peer Overlay Network . . . . . . . . . . . . . . . . . . . . . . 7 2.2.1 Unstructured Overlay Network . . . . . . . . . . . . . . . . . 8 2.2.2 Structured overlay network . . . . . . . . . . . . . . . . . . . . 8 2.3 Overnet P2P Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Storm C&C Network Protocol . . . . . . . . . . . . . . . . . . . . . . 11 2.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.6 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3 Using OMNET++: P2P Botnet Architecture and Implementation 16 3.1 Architecture and Implementation . . . . . . . . . . . . . . . . . . . . 17 vi 3.1.1 Simulation Model Design . . . . . . . . . . . . . . . . . . . . . 17 3.1.2 Storm Network and k-bucket Details . . . . . . . . . . . . . . 21 3.1.3 Network Messages . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 Storm Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Mitigation Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4 Simulation and Analysis 36 4.1 Simulation Platform and Parameters . . . . . . . . . . . . . . . . . . 36 4.1.1 Basic Simulation Setup . . . . . . . . . . . . . . . . . . . . . . 37 4.1.2 Simulation Parameters . . . . . . . . . . . . . . . . . . . . . . 37 4.1.3 Simulation Scenarios . . . . . . . . . . . . . . . . . . . . . . . 40 4.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2.1 Analysis based on <key, value> pair count . . . . . . . . . . . 41 4.2.2 Analysis based on <key, value> pair retrieval time . . . . . . 53 4.2.3 <key, value> Retrieval Statistics . . . . . . . . . . . . . . . . 59 4.2.4 Message Count Analysis . . . . . . . . . . . . . . . . . . . . . 63 5 Conclusions and Future Work 70 5.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Bibliography 73 vii List of Tables Table 1.1 Common Storm Outbreaks . . . . . . . . . . . . . . . . . . . . . 3 Table 3.1 Server Module Attributes . . . . . . . . . . . . . . . . . . . . . . 19 Table 3.2 Kademlia Protocol Attributes . . . . . . . . . . . . . . . . . . . 20 Table 3.3 Generic Attributes . . . . . . . . . . . . . . . . . . . . . . . . . 20 Table 4.1 Attributes with Fixed Values. . . . . . . . . . . . . . . . . . . . 38 Table 4.2 Simulation Attributes with Varying Values. . . . . . . . . . . . . 39 Table 4.3 Number of bots with <key, value> pair for peer list size 200 . . 42 Table 4.4 Number of bots with <key, value> pair for peer list size 300 . . 43 Table 4.5 Percentage of bots with <key, value> pair for peer list size 200 . 44 Table 4.6 Percentage of bots with <key, value> pair for peer list size 300 . 45 Table 4.7 <key, value> pair time (minutes) for peer list size 200 . . . . . . 54 Table 4.8 <key, value> pair time (sec) for peer list size 300 . . . . . . . . 55 Table 4.9 Message Count for peer list size 200 . . . . . . . . . . . . . . . 64 Table 4.10 Message count for peer list size 300 . . . . . . . . . . . . . . . . 65 viii List of Figures Figure 3.1 Design of Storm Botnet . . . . . . . . . . . . . . . . . . . . . . 17 Figure 3.2 Structure of Storm Botnet . . . . . . . . . . . . . . . . . . . . 19 Figure 3.3 <key, value> pair Look Up parameters. . . . . . . . . . . . . . 21 Figure 3.4 Address space of k-buckets. . . . . . . . . . . . . . . . . . . . . 22 Figure 3.5 Peer List and Ping-Pong Message Flow Diagram . . . . . . . . 24 Figure 3.6 Store Message Flow Diagram . . . . . . . . . . . . . . . . . . . 25 Figure 3.7 Flow Diagram of Find Node and Find Value Message with <key, value> pair present. . . . . . . . . . . . . . . . . . . . . . . . . 28 Figure 3.8 Flow Diagram of Find Node and Find Value Message with <key, value> pair not present. . . . . . . . . . . . . . . . . . . . . . . 30 Figure 4.1 Standard Growth Model for 81000 bots: Percentage of bots with <key, value> pair for peer list size of 200. . . . . . . . . . . . . 46 Figure 4.2 Standard Growth Model for 81000 bots: Percentage of bots with <key, value> pair for peer list size of 300. . . . . . . . . . . . . 46 Figure 4.3 Standard Growth Model for 81000 bots: Percentage of bots that retrievethe<key, value>pairwithoutrandomdisinfectionstrat- egy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Figure 4.4 Standard Growth Model for 81000 bots: Percentage of bots that retrieve the <key, value> pair with random disinfection strategy. 46 Figure 4.5 Standard Growth Model for 40500 bots: Percentage of bots with <key, value> pair for peer list size of 200. . . . . . . . . . . . . 49 Figure 4.6 Standard Growth Model for 40500 bots: Percentage of bots with <key, value> pair for peer list size of 300. . . . . . . . . . . . . 49 Figure 4.7 Standard Growth Model for 40500 bots: Percentage of bots that retrievethe<key, value>pairwithoutrandomdisinfectionstrat- egy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 ix Figure 4.8 Standard Growth Model for 40500 bots: Percentage of bots that retrieve the <key, value> pair with random disinfection strategy. 49 Figure 4.9 Sybil Mitigation for 81000 bots: Percentage of bots that retrieve true <key, value> pair for peer list size of 200. . . . . . . . . . 50 Figure 4.10 Sybil Mitigation for 81000 bots: Percentage of bots with true <key, value> pair for peer list size of 300 . . . . . . . . . . . . 50 Figure 4.11 Sybil Mitigation for 81000 bots: Percentage of bots with any <key, value> pair for peer list size of 200. . . . . . . . . . . . . 50 Figure 4.12 Sybil Mitigation for 81000 bots: Percentage of bots with any <key, value> pair for peer list size of 300. . . . . . . . . . . . . 50 Figure 4.13 Sybil Mitigation for 40500 bots: Percentage of bots with true <key, value> pair for peer list size of 200. . . . . . . . . . . . . 52 Figure 4.14 Sybil Mitigation for 40500 bots: Percentage of bots with true <key, value> pair for peer list size of 300. . . . . . . . . . . . . 52 Figure 4.15 Sybil Mitigation for 40500 bots: Percentage of bots with any <key, value> pair for peer list size of 200. . . . . . . . . . . . . 52 Figure 4.16 Sybil Mitigation for 40500 bots: Percentage of bots with any <key, value> pair for peer list size of 300. . . . . . . . . . . . . 52 Figure 4.17 Standard Growth Model for 81000 bots: <key, value> pair retrieval time, with peer list size set at 200. . . . . . . . . . . . 56 Figure 4.18 Standard Growth Model for 81000 bots:: <key, value> pair retrieval time, with peer list size set at 300. . . . . . . . . . . . 56 Figure 4.19 Sybil Mitigation for 81000 bots: any <key, value> pair retrieval time, with peer list size set at 200. . . . . . . . . . . . . . . . . 58 Figure 4.20 Sybil Mitigation for 81000 bots: any <key, value> pair retrieval time, with peer list size set at 300. . . . . . . . . . . . . . . . . 58 Figure 4.21 SybilMitigationfor81000bots: true<key, value>pairretrieval time, with peer list size set at 200. . . . . . . . . . . . . . . . . 58 Figure 4.22 SybilMitigationfor81000bots: true<key, value>pairretrieval time, with peer list size set at 300. . . . . . . . . . . . . . . . . 58 Figure 4.23 Histogram of number of bots retrieving <key, value> pair per time interval for Standard growth model of Storm with peer list size of 200. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 x Figure 4.24 Histogram of number of bots retrieving <key, value> pair per time interval for Standard growth model of Storm with peer list size of 300. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Figure 4.25 Histogramofnumberofbotsretrieving<key, value>pairversus evolution of the simulation for Standard growth model of Storm with 1% inital number of bots. . . . . . . . . . . . . . . . . . . 61 Figure 4.26 Histogramofnumberofbotsretrieving<key, value>pairversus evolution of the simulation for Standard growth model of Storm with 20% inital number of bots. . . . . . . . . . . . . . . . . . . 62 Figure 4.27 Histogram of number of bots retrieving any <key, value> pair versus evolution of the simulation for Sybil Distruption strategy with 20% inital number of bots. . . . . . . . . . . . . . . . . . . 63 Figure 4.28 Standard Growth Model for 81000 bots: Mean Message count for <key, value> pair retrieval, with peer list size set at 200. . . 66 Figure 4.29 Standard Growth Model for 81000 bots: Mean Message count for <key, value> pair retrieval, with peer list size set at 300. . . 67 Figure 4.30 Sybil Mitigation for 81000 bots: Mean Message count for true <key, value> pair retrieval, with peer size set at 200. . . . . . . 69 Figure 4.31 Sybil Mitigation for 81000 bots: Mean Message count for true <key, value> pair retrieval, with peer size set at 300. . . . . . . 69 Figure 4.32 Sybil Mitigation for 81000 bots: Mean Message count for any <key, value> pair retrieval, with peer size set at 200. . . . . . . 69 Figure 4.33 Sybil Mitigation for 81000 bots: Mean Message count for any <key, value> pair retrieval, with peer size set at 300. . . . . . . 69