A mathematical exploitation of simulated uniform scanning botnet propagation dynamics for early stage detection and management
Tóm tắt
The contribution of this paper is two-fold. Firstly, we propose a botnet detection approach that is sufficiently timely to enable a containment of the botnet outbreak in a supervised network. Secondly, we show that mathematical models of botnet propagation dynamics are a viable means of achieving that level of defense from bot infections in a supervised network. Our approach is built on the idea of processing network traffic such as to localize a weakly connected subgraph within a graph that models network communications between hosts, and thus consider that subgraph as representative of a suspected botnet. We devise applied statistics to infer the propagation dynamics that would characterize the suspected botnet if this latter were indeed a botnet. The inferred dynamics are materialized into a model graph. A subgraph isomorphism search determines whether or not there is an approximate match between the model graph and any subgraph of the weakly connected subgraph. An approximate match between the two leads to a timely identification of infected hosts. We have implemented this research in the Matlab and Perl programming languages, and have validated it in practice in the Emulab network testbed. In the paper, we describe our approach in detail, and discuss experiments along with experimental data that are indicative of the effectiveness of our approach.
Tài liệu tham khảo
Anderson, R.M., May, R.M., Anderson, B.: Infectious Diseases of Humans: Dynamics and Control. Oxford University Press, USA (1992)
Andersson, H., Britton, T.: Stochastic Epidemic Models and Their Statistical Analysis, ser. Lecture Notes in Statistics, vol. 151. Springer-Verlag, New York (2000)
Bonfante, G., Kaczmarek, M., Marion, J.Y.: Architecture of a morphological malware detector. J. Comput. Virol. 5(3), 263–270 (2009)
Calvet, J., Davis, C.R., Fernandez, J.M., Marion, J.Y., St-Onge, P.L., Guizani, W., Bureau, P.M., Somayaji, A.: The case for In-the-lab botnet experimentation: creating and taking down a 3000-node botnet. In: Proceedings of the 2010 Annual Computer Security Applications Conference. Orlando, Florida (2010)
Cho, C.Y., Caballero, J., Grier, C., Paxson, V., Song, D.: Insights from the inside: a view of botnet management from infiltration. In: Proceedings of the 3rd USENIX Conference on Large-Scale Exploits and Emergent Threats: Botnets, Spyware, Worms, and More (2010)
Collins, M.P., Reiter, M.K.: Hit-list worm detection and bot identification in large networks using protocol graphs. In: Proceedings of the 10th International Symposium on Recent Advances in Intrusion Detection, pp. 276–295. Queensland, Australia (2007)
Coskun, B., Dietrich, S., Memon, N.: Friends of an enemy: identifying local members of peer-to-peer botnets using mutual contacts. In: Proceedings of the 2010 Annual Computer Security Applications Conference. Orlando, Florida (2010)
Crandall, J.R., Su, Z., Wu, S.F., Chong, F.T.: On deriving unknown vulnerabilities from zero-day polymorphic and metamorphic worm exploits. In: Proceedings of the 12th ACM Conference on Computer and Communications Security, pp. 235–248. Virginia (2005)
Dagon, D., Zou, C., Lee, W.: Modeling botnet propagation using time zones. In: Proceedings of the 13th Annual Network and Distributed System Security Symposium. San Diego, CA (2006)
Daley, D.J., Gani, J.: Epidemic Modelling: An Introduction. Cambridge University Press, Cambridge (1999)
Edwards, B., Moore, T., Stelle, G., Hofmeyr, S., Forrest, S.: Beyond the blacklist: modeling malware spread and the effect of interventions. In: Proceedings of the 2012 Workshop on New Security Paradigms, pp. 53–66. Italy (2012)
Ellis, D.R., Aiken, J.G., Attwood, K.S., Tenaglia, S.D.: A behavioral approach to worm detection. In: Proceedings of the ACM Workshop on Rapid Malcode, pp. 43–53. Washington DC (2004)
Ferrante, J., Ottenstein, K.J., Warren, J.D.: The program dependence graph and its use in optimization. ACM Trans. Program. Lang. Syst. 9(3), 319–349 (1987)
Ferrie, P.: Attacks on virtual machines. In: Proceedings of the Association of Anti-Virus Asia Researchers Conference, France (2007)
Filiol, E., Franc, E., Gubbioli, A., Moquet, B., Roblot, G.: Combinatorial optimisation of worm propagation on an unknown network. Intern. J. Comput. Sci. 2(2), 124–130 (2007)
Foggia, P., Sansone, C., Vento, M.: A performance comparison of five algorithms for graph isomorphism. In: Proceedings of the 3rd IAPR-TC15 Workshop on Graph-Based Representations in, Pattern Recognition, pp. 188–199 (2001)
Forrest,S., Balthrop, J., Glickman, M., Ackley, D.: Computation in the wild. In: Park, K. ,Willins, W. (eds.) The Internet as a Large-Scale Complex System. Oxford University Press, Oxford (2005)
Gagnon, M.N., Taylor, S., Ghosh, A.K.: Software protection through anti-debugging. IEEE Sec. Privacy 5(3), 82–84 (2007)
Gopalan, P., Jamieson, K., Mavrommatis, P., Poletto, M.: Signature metrics for accurate and automated worm detection. In: Proceedings of the 4th ACM Workshop on Recurring Malcode, pp. 65–72. Virginia (2006)
Heubach, S., Mansour, T.: Combinatorics of compositions and words. CRC Press, USA (2009)
Hsu, C.H., Huang, C.Y., Chen, K.T.: Fast-flux bot detection in real time. In: Proceedings of the 13th International Conference on Recent Advances in Intrusion Detection, pp. 464–483. Ottawa, Ontario (2010)
Jacob, G., Hund, R., Kruegel, C., Holz, T.: JACKSTRAWS: picking command and control connections from bot traffic. In: Proceedings of the 20th USENIX Conference on, Security (2011)
Kachitvichyanukul, V., Schmeiser, B.W.: Binomial random variate generation. Commun. ACM 31(2), 216–222 (1988)
Kim, K., Moon, B.R.: Malware detection based on dependency graph using hybrid genetic algorithm. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, pp. 1211–1218. Portland (2010)
Kolbitsch, C., Kirda, E., Kruegel, C.: The power of procrastination: detection and mitigation of execution-stalling malicious code. In: Proceedings of the 18th ACM Conference on Computer and Communications Security, pp. 285–296. Chicago, Illinois (2011)
Liljenstam, M., Nicol, D.M., Berk, V.H., Gray, R.S.: Simulating realistic network worm traffic for worm warning system design and testing. In: Proceedings of the ACM Workshop on Rapid Malcode, pp. 24–33. Washington (2003)
Livshits, B., Cui, W.: Spectator: detection and containment of javascript worms. In: Proceedings of the USENIX Annual Technical Conference, pp. 335–348. Massachusetts (2008)
Martignoni, L., Paleari, R., Roglia, G.F., Bruschi, D.: Testing CPU emulators. In: International Symposium on Software Testing and, Analysis, USA (2009)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, USA (1995)
Nagaraja, S., Mittal, P., Hong, C.-Y., Caesar, M., Borisov, N.: Botgrep: finding bots with structured graph analysis. In: Proceedings of the 19th USENIX Security Symposium, pp. 95–110. California (2010)
Newsome, J., Karp, B., Song, D.: Polygraph: automatically generating signatures for polymorphic worms. In: Proceedings of the IEEE Symposium on Security and Privacy, pp. 226–241. California (2005)
Opdyke, J.D.: A unified approach to algorithms generating unrestricted and restricted integer compositions and integer partitions. J. Math. Model. Algorithm 9(1), 53–97 (2009)
Porras, P., Saidi, H., Yegneswaran, V.: A multi-perspective analysis of the storm (peacomm) worm. In: SRI Computer Science Laboratory Technical Note. California (2007)
Porras, P., Saidi, H., Yegneswaran, V.: A foray into conficker’s logic and rendezvous points. In: Proceedings of the 2nd USENIX Workshop on Large-Scale Exploits and Emergent Threats. Massachusetts (2009)
Rohloff, K.R., Basar, T.: Stochastic behavior of random constant scanning worms. In: Proceedings of the 14th International Conference on Computer Communications and Networks, pp. 339–344. California (2005)
Rrushi, J.L., Mokhtari, E., Ghorbani, A.A.: A statistical approach to botnet virulence estimation. In: Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security (short paper). Hong Kong (2011)
Sellke, S., Shroff, N.B., Bagchi, S.: Modeling and automated containment of worms. IEEE Trans. Depend. Secur. Comput. 5(2), 71–86 (2008)
Staniford, S., Paxson, V., Weaver, N.: How to own the internet in your spare time. In: Proceedings of the 11th USENIX Security Symposium, pp. 149–165. California (2002)
Stover, S., Dittrich, D., Hernandez, J., Dietrich, S.: Analysis of the Storm and Nugache Trojans: P2P is Here. LOGIN, vol. 32, p. 6 (2007)
Stringhini, G., Holz, T., Stone-Gross, B., Kruegel, C., Vigna, G.: BOT MAGNIFIER: locating spambots on the internet. In: Proceedings of the 20th USENIX Conference on, Security, USA (2011)
Ullmann, J.R.: An algorithm for subgraph isomorphism. J. Assoc. Comput. Mach. 23(1), 31–42 (1976)
White, B., Lepreau, J., Stoller, L., Ricci, R., Guruprasad, S., Newbold, M., Hibler, M., Barb, C., Joglekar, A.: An integrated experimental environment for distributed systems and networks. In: Proceedings of the Fifth Symposium on Operating Systems Design and Implementation, pp. 255–270. USENIX Association, Boston (2002)