Модель распространения вирусных атак в сетях передачи данных общего пользования на основе расчета длины гамильтонова пути

Между распространением компьютерных вирусов и других вредоносных программ и эпидемиями биологических заболеваний существует много общего. Это не случайно: даже первые работы, предсказавшие возможность создания самораспространяющихся программ, проводили аналогию между компьютерными и биологическими вирусами. Естественно применить для исследования.* распространения компьютерных вирусов методики, разработанные в процессе изучения инфекционных заболеваний и борьбы с ними. Одним из таких методов является создание моделей эпидемиологических процессов. Моделирование распространения может быть использовано для различных целей. Например, его. помощью можно изучать уже начавшуюся эпидемию заболевания, исследовать влияние на нее различных факторов, таких как вакцинация. Модели могут предсказать масштабы эпидемии и ее динамику, определить при каких условиях, она возникает и так далее.

Еще в XIX веке для изучения инфекционных заболеваний были разработаны эпидемиологические модели, основанные на системах дифференциальных^ уравнений. Эти модели достаточно примитивны, однако они позволили установить ряд важных следствий, таких как теорема об эпидемиологическом пределе. В конце 80-ых-начале 90-ых годов XX века классические эпидемиологические модели были использованы исследователями из IBM для изучения распространения компьютерных вирусов [2][3][4]. Они же применили эти модели для изучения вирусных эпидемий в компьютерной сети, моделируемой ненаправленным графом. Другие работы, посвященные этому направлению, также основаны на модификациях традиционных эпидемиологических моделей, учитывающих специфику компьютерных вредоносных программ.

1.2 Классические эпидемиологические модели.

В эпидемиологии используются два основных типа моделей: стохастические и детерминистические. Стохастический подход применяется для исследования эпидемий в малых или изолированных популяциях, когда особенно важную роль в распространении заболевания играют случайные колебания вероятностей заражения индивида. Детерминистические модели описывают эпидемиологический процесс на уровне всей популяции и пригодны для больших популяций. Применение стохастических моделей для больших популяций дает такие же результаты как полученные детерминистическим подходом. Для упрощения анализа распространения инфекционного заболевания, особенности заражения и излечения индивида не учитываются. Считается, что каждый индивид в популяции может находиться только в одном из нескольких состояний. В общем случае, детерминистическая MSEIR модель выделяет в популяции пять групп:

• М (passive immunity — обладающие пассивным иммунитетом).

• S (susceptible — уязвимые).

• Е (exposed — зараженные, латентная стадия).

• I (infective — зараженные, распространяющие заболевание).

• R (recovered/removed — индивиды, неподверженные заболеванию).

Индивиды М, обладающие пассивным иммунитетом к инфекции от рождения, постепенно переходят в группу подверженных заболеванию индивидов S. Уязвимые индивиды S заражаются индивидами I с некоторой частотой |3. Новые зараженные индивиды проводят некоторое время в группе развития заболевания Е, а затем приобретают способность распространять инфекцию. Зараженные индивиды излечиваются с некоторой частотой 5 и переходят в группу R, обладающую иммунитетом. Существует множество модификаций этой модели, включающих только определенные группы: модели SI, SIR, SEIR и другие. Также существует модификация MSEIRS и производные от нее, в которой неподверженные заболеванию индивиды могут со временем терять иммунитет и переходить в группу уязвимых. Решение о том, какие группы включать в модель зависит от особенностей распространения конкретного заболевания и от цели моделирования.

В наиболее упрощенном варианте — SI модели — вся популяция разделяется на индивидов, подверженных заболеванию и зараженных индивидов. Если N число всех индивидов в популяции, a S (t) и I (t) — число уязвимых и зараженных индивидов в момент времени t соответственно, тогда.

S (t) /(t).

НО =—-, i (0 = -7-N N.

— доля уязвимых и зараженных индивидов в популяции в момент времени t соответственно. В классических эпидемиологических моделях считается, что время развития эпидемии гораздо меньше средней продолжительности жизни индивида, т. е. число индивидов в популяции остается постоянным:

N = S (i) + КО.

Простейшая SI модель описывается уравнением: г1 = piCtMt) = Д/ СО [ЛГ — /(О] at или.

Решением этого уравнения является где i0 — доля зараженных индивидов в начале эпидемии.

В классической эпидемиологической модели SIR учитывается приобретение индивидами иммунитета после излечения, число индивидов в популяции также остается постоянным:

N = S (t) + lit) + ВД Если р — частота заражения, тогда 5 = BNis N у.

— среднее число новых зараженных индивидов в единицу времени.

Классическая SIR модель описывается системой дифференциальных уравнений: rdS 81 -—s, dt N dl /?/ —5−5/, dt N dR 61 dt где 5 — частота излечения.

Рис. 1.2.2.

Подставив частоту излечения 8 равную нулю в, получим выражение для упрощенной SI модели.

Не смотря на относительную простоту традиционных эпидемиологических моделей, они имеют большое значение. В частности, Кермаком и МакКендриком установлена теорема об эпидемиологическом пределе: эпидемия может начаться только если исходное число уязвимых индивидов S0 в популяции больше эпидемиологического предела р (отношения частоты излечения и заражения).

Если число подверженных инфекции индивидов меньше, то вспышка заболевания в популяции угасает. В соответствии с этим утверждением традиционную SIR модель называют также моделью Кермака-МакКендрика.

1. D. Whyte, Е. Kranakis, P. van Oorschot. DNS-based detection of scanning worms in an enterprise network. Technical report, Carleton University, School of Computer Science, TR-04−06, August 2004.

2. Z. Chen, C. Ji. A Self-Learning Worm Using Importance Scanning. ACM CCS Workshop on Rapid Malcode (WORM'05), 2005.

3. J. Wu, S. Vangala, L. Gao, and K. Kwiat. An Effective Architecture and Algorithm for Detecting Worms with Various Scan Techniques. Network and Distributed System Security Symposium, 2004.

4. С. C. Zou, D. Towsley, W. Gong, and S. Cai. Routing Worm: A Fast, Selective Attack Worm based on IP Address Information. 19th ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation (PADS'05), June 1−3, Monterey, USA, 2005.

5. A. Ganesh, L. Massoulie, and D. Towsley. The Effect of Network Topology on the Spread of Epidemics. Proc. of INFOCOM 2005, Miami, March 2005.

6. M. Garetto, W. Gong, D. Towsley. Modeling Malware Spreading Dynamics. Proc. of INFOCOM 2003, San Francisco, April, 2003.

7. K. Rohloff and T. Basar. Stochastic Behavior of Random Constant Scanning Worms. Proc. of IEEE Conference on Computer Communications and Networks 2005 (ICCCN 2005), San Diego, CA, Oct., 2005.

8. С. C. Zou, W. Gong, D. Towsley, and L. Gao. The Monitoring and Early Detection of Internet Worms. IEEE/ACM Transactions on Networking, 13(5), 961- 974, October 2005.

9. C. Zou, L. Gao, W. Gong, and D. Towsley. Monitoring and Early Warning of Internet Worms. Proceedings of ACM Conference on Computer and Communications Security (CCS), October, 2003.

10. N. Weaver, S. Staniford, and Vern Paxson. Very Fast Containment of Scanning Worms. Proceedings of the 13th USENIX Security Symposium, August 2004.

11. C. Shannon and D. Moore. The spread of the Witty worm. Proceedings of the IEEE Symposium on Security and Privacy, May, 2004.

12. J. Van Hoogstraten. Blasting Windows: An Analysis of the W32/Blaster Worm. http://www.giac.org/practical/GCIH/John VanHoogstraten GCIH.pdf.

13. D. Moore, C. Shannon, G.M. Voelker, S. Savage. Internet Quarantine: Requirements for Containing Self-Propagating Code. Infocom 2003.

14. J. Nazario, J. Anderson, R. Wash, C. Connelly. The Future of Internet Worms. Crimelabs Research.

15. C.C. Zou, D. Towsley, W. Gong. Email virus propagation modeling and analysis. Technical Report TR-CSE-03−04 (University of Massachussets, Amherst), 2003.

16. S. Chen, Y. Tang. Slowing Down Internet Worms. University of Florida, Department of Computer & Information Science & Engineering.

17. L. Zeltser. The Evolution of Malicious Agents. April 2000.

18. A. Shulman. Web Application Worms: Myth or Reality?. iMPERVA Application Defense Center, 2004.

19. C. Wang, J.C. Knight, M.C. Elder. On computer viral infection and the effect of immunization. ACSAC, 246−256, 2000.

20. K. Rozinov. Reverse Code Engineering: An In Depth Analysis of the Bagle Virus. August 2004.

21. D.J. Daley and J. Gani. Epidemic Modelling: An Introduction. Cambridge University Press, 1999.

22. H. W. Hethcote. The Mathematics of Infectious Diseases. SIAM Review Vol. 42, No. 4, 599−653, 2000.

23. D. Moore, C. Shannon, and J. Brown. Code-Red: a case study on the spread and victims of an Internet Worm. In Proc. ACM/USENIX Internet Measurement Workshop, France, November, 2002.

24. Y. Wang, D. Chakrabarti, C. Wang and C. Faloutsos. Epidemic Spreading in Real Networks: An Eigenvalue Viewpoint. 22nd Symposium on Reliable Distributed Computing, Florence, Italy, Oct. 6−8, 2003.

25. Y. Wang, C. Wang. Modeling the Effects of Timing Parameters on Virus Propagation. ACM Workshop on Rapid Malcode, Washington, DC, Oct. 27, 2003.

26. N. Weaver, V. Paxson, S. Staniford, and R. Cunningham. A Taxonomy of Computer Worms. ACM Workshop on Rapid Malcode, Washington, DC, Oct. 27, 2003.

27. C.C. Zou, W. Gong, D. Towsley. Worm propagation modeling and analysis under dynamic quarantine defense. Proceedings of the ACM CCS Workshop on Rapid Malcode (WORM'03), 2003.

28. J. Jung, S. E. Schechter, and A. W. Berger. Fast detection of scanning worm infections. In Proceedings of the 7th International Symposium on Recent Advances in Intrusion Detection (RAID), September 2004.

29. D. Moore, V. Paxson, S. Savage, C. Shannon, S. Staniford, and N. Weaver. Inside the Slammer worm. IEEE Magazine on Security and Privacy, 1(4), July 2003.

30. N. Weaver. Warhol Worms: The Potential for Very Fast Internet Plagues, 2001.

31. S. Staniford. Containment of scanning worms in enterprise networks. Journal of Computer Security, 2003.

32. M. M. Williamson. Throttling viruses: Restricting propagation to defeat mobile malicious code. In 18th Annual Computer Security Applications Conference, December 2002.

33. C.C. Zou, D. Towsley, W. Gong. Email virus propagation modeling and analysis. Technical Report TR-CSE-03−04 (University of Massachussets, Amherst), 2003.

34. С. C. Zou, D. Towsley, and W. Gong. On the performance of Internet worm scanning strategies. Technical Report TR-03-CSE-07, Umass ECE Dept., November 2003.

35. Z. Chen, C. Ji. Spatial-Temporal Modeling of Malware Propagation in Networks. IEEE Transactions On Neural Networks, 2005.

36. Z. Chen, L. Gao, K. Kwiat. Modeling the spread of active worms. Proceedings of IEEE INFOCOM 2003,2003.

37. С. С. Zou, D. Towsley, and W. Gong. Email worm modeling and defense. In Proceedings of 13th International Conference on Computer Communications and Networks (ICCCN'04), October 2004.

38. Y. Bulygin. A spread model of flash worms. Security Evaluation Center of Excellence, Intel Corporation.

39. S. Staniford, D. Moore, V. Paxson, N. Weaver. The Top Speed of Flash Worms. In: Proceedings of ACM Workshop on Rapid Malcode (WORM). (2004).

40. M. Mannan and P.C. van Oorschot. On instant messaging worms, analysis and countermeasures. In Proceedings of the 2005 ACM Workshop on Rapid Malcode, pages 2−11, November 2005.

41. D. Moore, V. Paxson, S. Savage, C. Shannon, S. Staniford, and N. Weaver. The spread of the sapphire/slammer worm. Technical report, CAIDA, ICSI, Silicon Defense, UC Berkeley EECS and UC San Diego CSE, 2003.

42. G. Serazzi, S. Zanero. Computer virus propagation models. Tutorials of the 11th IEEE/ACM Int’l Symp. On Modeling, Analysis and Simulation of Computer and Telecom. Systems MASCOTS 2003. Springer-Verlag, 2003.

43. L. Zhou, L. Zhang, F. McSherry, N. Immorlica, M. Costa and S. Chien. A First Look at Peer-to-Peer Worms: Threats and Defenses. Peer-to-Peer Systems IV, 4th International Workshop (IPTPS), pages 24−35, February 2005.

44. C.C. Zou, W. Gong, D. Towsley. Code Red Worm Propagation Modeling and Analysis. 9th ACM Conf. on Computer and Communication Security, 2002.

45. K. Ramachandran and B. Sikdar. Modeling Malware Propagation in Gnutella Type Peer-to-Peer Networks. The Third International Workshop on Hot Topics in Peer-to-Peer Systems (Hot-P2P), Rhodes Island, Greece, April 2006.

46. W. Yu, C. Boyer, S. Chellappan and D. Xuan. Peer-to-Peer System based Active Worm Attacks: Modeling and Analysis. Communications, 2005. ICC 2005. 2005 IEEE International Conference on Volume 1, 16−20 May 2005 Page (s):295 300 Vol. 1.

47. R. Thommes and M. Coates. Epidemiological Modeling of Peer-to-Peer Viruses and Pollution. IEEE INFOCOM, April 2006.

48. J.O. Kephart, S.R. White. Directed-graph Epidemiological Models of Computer Viruses. Proceedings of the IEEE Symposimum on Security and Privacy, 343−359, 1991.

49. J.O. Kephart, D.M. Chess, S.R. White. Computers and Epidemiology. IEEE Spectrum, 1993.

50. J.O. Kephart, S.R. White. Measuring and Modeling Computer Virus Prevalence. Proceedings of the IEEE Symposimum on Security and Privacy, 1993.

51. D. Brumley, Li-Hao Liu, P. Poosankam, and D. Song. Taxonomy and effectiveness of worm defense strategies. TR CMUCS-05−156, 2005.

52. C. W. Wong, S. Bielski, J. M. McCune, and C. Wang. A Study of Mass-mailing Worms. ACM CCS 2nd Workshop on Rapid Malcode (WORM04), October 2004.

53. D. Ellis, J. Aiken, K. Attwood, and S. Tenaglia. A Behavioral Approach to Worm Detection. In Proceedings of the ACM Workshop on Rapid Malcode (WORM), Fairfax, VA, Oct. 2004.

54. S. Staniford, V. Paxson, N. Weaver. How to Own the internet in your spare time. Proceedings of the 11th USENIX Security Symposium (Security '02), 2002.

55. D.M. Kienzle, M.C. Elder. Recent worms: a survey and trends. The 2003 ACM Workshop on Rapid Malcode (WORM-03) Washington, DC, USA, 2003.

56. N.C. Weaver, V. Paxson, A worst-case worm, The Third Annual Workshop for Economics and Information Security (WEIS04), Minnesota, 2004.

57. L. Briesemeister, P. Lincoln, and P. Porras. Epidemic profiles and defense of scale-free networks. ACM CCS Workshop on Rapid Malcode (WORM'03), October 2003.

58. R. P. Satorras and A. Vespignani. Epidemic spreading in scale-free networks. Phys. Rev. E., vol. 86, no. 14, April 2001.

59. J. Leveille. Epidemic Spreading In Technological Networks. Technical Report HPL-2002;287, HP Laboratories Bristol, 2002.