PHYSICAL REVIEW LETTERS, том 86, выпуск 14, 2 апреля 2001 г.
Распространение эпидемий в безмасштабных сетях Ромуальдо Пастор-Саторрас1 и Алессандро Веспиньяни2 1Кафедра физики и ядерной инженерии, Политехнический университет Каталонии, Campus Nord, Mòdul B4, 08034 Барселона, Испания 2Международный центр теоретической физики им. Абдуса Салама (ICTP), P.O. Box 586, 34100 Триест, Италия (Получено 20 октября 2000 г.)
Интернет обладает весьма сложной структурой связности, которую в последнее время описывают классом безмасштабных сетей. Эта особенность, по-видимому очень эффективная для коммуникационной сети, одновременно способствует распространению компьютерных вирусов. Мы анализируем реальные данные о заражемниеянхнокосмппоьсоюбтсетрвнуыетмриавсипрруоссатмраиниеноипюрекдоемляпеьмютсеррендын Интернете. Предложена динамическая модель распр отсутствие эпидемического порога и связанного с н схема объясняет данные о компьютерных вирусах и пространения в коммуникационных и социальных се DOI: 10.1103/PhysRevLett.86.3200 Профессиональный перевод с английского. Формулы, нумера Многие социальные, биологические и коммуникационные системы можно адекватно описывать сложными сетями, узлы которых представляют отдельных людей или организации, а связи моделируют взаимодействия между ними [1,2]. Особенно интересными примерами являются Интернет [3,4] и Всемирная паутина [5], которые широко исследовались ввиду их технологической и экономической значимости. Эти исследования, в частности, показали, что вероятность того, что узел таких сетей имеет 𝑘 связей, подчиняется безмасштабному распределению 𝑃 (𝑘) ∼ 𝑘−𝛾, где показатель 𝛾 лежит в диапазоне от 2 до 3. Наличие узлов с очень большим числом связей (локальная кластеризация) действительно является ключевым элементом моделирования этих сетей в рамках недавно введённых безмасштабных (scale-free, SF) графов [6].
Поскольку сложные сети широко распространены в природе, большой интерес представляет влияние их особенностей на распространение эпидемий и заболеваний [7], а в более общем плане – на неравновесные фазовые переходы, характерные для этих явлений [8]. Исследование эпидемий в таких сетях имеет непосредственное практическое применение при анализе распространения компьютерных вирусов [9,10] и может быть актуально также для эпидемиологии [11] и контроля загрязнений [12].
В настоящей работе мы анализируем данные о реальных эпидемиях компьютерных вирусов и даём их статистическую характеристику, указывающую на необходимость учитывать специфическую топологию безмасштабных сетей в теоретическом описании таких заражений. С этой целью с помощью крупномасштабного моделирования и аналитических методов мы исследуем на SF-графах эпидемиологическую модель SIS (susceptible-infectedsusceptible, «восприимчивый-инфицированныйвосприимчивый») [11]. Мы обнаруживаем отсутствие эпидемического порога и связанного с ним критического поведения. Это означает, что безмасштабные сети предрасположены к распространению и длительному существованию инфекций при еввирреумсяовж. иМзыниаинаплеирзсиирсутеемнтрнеоаслтььнвыиерудсаннынхыешотазмамраожвевстранения инфекций в безмасштабных сетях; показано м критического поведения. Новая эпидемиологическая ожет способствовать пониманию других процессов расях.
PACS: 89.75.Hc, 05.50.+q, 05.70.Ln я рисунков и библиографические ссылки сохранены по оригиналу. любой, даже сколь угодно малой, скорости распространения возбудителя. Отсутствие эпидемического порога – стандартного элемента математической эпидемиологии [11] – радикально меняет многие обычные выводы эпидемического моделирования.
Полученные результаты имеют значение и для теории фазовых переходов в поглощающее состояние, а также каталитических реакций [8].
Исследование компьютерных вирусов давно привлекает постоянное внимание специалистов по информатике [10,13–15]; при этом в основном используются подходы, заимствованные из биологической эпидемиологии [11]. Стандартной моделью компьютерной вирусной инфекции служит эпидемиологическая модель SIS. Каждый узел сети представляет отдельную систему, а каждая связь – канал, по которому инфекция может перейти к другим системам.
Узел может находиться лишь в одном из двух дискретных состояний: «здоров» или «инфицирован».
На каждом временном шаге любой восприимчивый (здоровый) узел заражается со скоростью 𝜈, если он связан с одним или несколькими инфицированными узлами. Одновременно инфицированные узлы излечиваются и вновь становятся восприимчивыми со скоростью 𝛿; тем самым определяется эффективная скорость распространения 𝜆 = 𝜈/𝛿 [16]. Без ограничения общности можно положить 𝛿 = 1. Модель неявно учитывает наличие антивирусного программного обеспечения, поскольку все инфицированные узлы в конечном счёте возвращаются в восприимчивое состояние. Она соответствует ситуации, в которой пользователи после очистки компьютера не становятся более настороженными по отношению к вирусной инфекции, так что их компьютеры могут быть заражены вновь [15]. Обновление состояния узлов можно выполнять как параллельно, так и последовательно [8].
В моделях с локальной связностью (евклидовы решётки) и на случайных графах наиболее существенным результатом является общий прогноз ненулевого эпидемического порога 𝜆 [8,11]. Если 𝜆 выше 𝑐 порога, 𝜆 ≥ 𝜆, инфекция распространяется и статочке неравновесного фазового перехода. В данном случае критическая точка отделяет активную фазу со стационарной плотностью инфицированных узлов от фазы, содержащей только здоровые узлы и характеризующейся нулевой активностью. В частности, нетрудно видеть, что модель SIS является обобщением модели контактного процесса, подробно исследованной в контексте фазовых переходов в поглощающее состояние [8]. С другой стороны, статистические наблюдения за вирусными инцидентами в реальных условиях показывают, что все сохраняющиеся вирусы выходят на очень низкий уровень распространённости, затрагивая лишь ничтожную долю общего числа компьютеров [10]. Это резко противоречит теоретическим прогнозам, если не предположить крайне маловероятное: эффективная скорость распространения каждого компьютерного вируса настроена лишь бесконечно мало выше порога. Следовательно, выработанное к настоящему времени представление, хотя и весьма поучительно, не вполне адекватно описывает реальное явление.
Чтобы лучше понять свойства распространения вирусов в реальных условиях, мы проанализировали данные о распространённости, опубликованные Virus Bulletin [17] за период с февраля 1996 по март 2000 г., то есть за временное окно в 50 месяцев В частности, исследовалась вероятность выживания однородных групп вирусов, классифицированных по механизму заражения [9]. Мы учитывали общее число вирусов определённого типа, которые возникли и исчезли внутри выбранного окна наблюдения. Вероятность выживания штамма 𝑃 (𝑡) определялась как 𝑠 доля вирусов, всё ещё существующих через время 𝑡 после своего появления. На рис. 1 видно, что в первые два месяца жизни вируса вероятность выживания резко падает. Это хорошо известная особенность [10,13], означающая, что статистически лишь малая доля вирусов вызывает заметную вспышку в компьютерном сообществе. Вместе с тем при больших временах на рис. 1 отчётливо наблюдается экспоненциальный хвост, 𝑃 (𝑡) ∼ exp(−𝑡/𝜏 ), где 𝜏 – характерное 𝑠 время жизни вирусного штамма [18]. Численная аппроксимация данных даёт 𝜏 ≃ 14 месяцев для загрузочных вирусов и макровирусов и 𝜏 ≃ 6–9 месяцев для файловых вирусов. Значения 𝜏 сравнительно слабо зависят от выбранного окна наблюдения: анализ вирусов, возникших и исчезнувших за интервал менее 50 месяцев, даёт результаты, совместимые с полной выборкой, хотя из-за меньшей статистики флуктуации возрастают.
Эти характерные времена поразительно велики по сравнению с интервалом, через который антивирусное программное обеспечение появляется на рынке (обычно через несколько дней или недель после первого сообщения об инциденте), и соответствуют возникновению метастабильных эндемических состояний. Столь длительное время жизни в масштабе типичных скоростей распространения и восстановления должно было бы указывать на эффективную скорость распространения, значительно превышающую эпидемический порог. Однако это вновь не согласуРис. 1. Вероятность выживания вирусов, циркулирующих в реальных условиях. 814 проанализированных вирусов объединены в три основные группы [9]. Файловые вирусы заражают компьютер при запуске инфицированного приложения. Загрузочные вирусы также распространяются через инфицированные приложения, но копируют себя в загрузочный сектор жёсткого диска и поэтому не устраняются перезагрузкой компьютера. Макровирусы заражают файлы данных и потому не зависят от платформы. На графике отчётливо виден экспоненциальный спад с характерным временем 𝜏. ется с неизменно низкими уровнями распространённости компьютерных вирусов.
Ключ к пониманию этих парадоксальных свойств компьютерных вирусов заключается в способности многих из них распространяться посредством обмена данными через коммуникационные протоколы (FTP, электронная почта и т. п.) [10]. Вирусы преимущественно попадают на компьютеры, интенсивно связанные с внешним миром и поэтому обменивающиеся пропорционально большим объёмом данных и информации. Следовательно, естественно считать топологию Интернета той эффективной топологией, на которой происходит распространение. Безмасштабная связность Интернета означает, что каждый узел имеет статистически значимую вероятность обладать очень большим числом связей по сравнению со средней степенью сети ⟨𝑘⟩. Это противоположно обычным случайным сетям (как локальным, так и нелокальным), в которых каждый узел имеет приблизительно одно и то же число связей, 𝑘 ≃ ⟨𝑘⟩
[19]. Поэтому безмасштабные свойства необходимо включить в теорию эпидемического распространения компьютерных вирусов.
Чтобы выяснить влияние безмасштабной связности на распространение эпидемий, мы исследуем модель SIS на SF-сетях. В качестве прототипа рассматривается граф, создаваемый алгоритмом из работы
[6]. Сначала берётся небольшое число 𝑚 несвязан- 0 ных узлов. На каждом временном шаге добавляется новый узел с 𝑚 связями; каждая связь присоединяется к уже существующему узлу 𝑖 степени 𝑘 с вероятно- 𝑖 стью 𝑘 / ∑ 𝑘. После достаточно большого числа ите- 𝑖 𝑗 𝑗 раций получается сеть из 𝑁 узлов с распределением степеней 𝑃 (𝑘) ∼ 𝑘−3 и средней степенью ⟨𝑘⟩ = 2𝑚.
В настоящей работе принято 𝑚 = 3. Мы выполнили численное моделирование на графах с числом узлов от 𝑁 = 103 до 𝑁 = 8,5 × 106 и изучили временную эволюцию и стационарные свойства плотности инРис. 2. Персистентность 𝜌 как функция 1/𝜆 для различных разме ров сети: 𝑁 = 105 (знаки плюс), 𝑁 = 5 × 105 (квадраты), 𝑁 = 106 (кресты), 𝑁 = 5 × 106 (кружки) и 𝑁 = 8,5 × 106 (ромбы). Линей ность в полулогарифмическом масштабе подтверждает предска занную для 𝜌 экспоненциальную зависимость. Сплошная линия – аппроксимация выражением 𝜌 ∼ exp(−𝐶/𝜆). ях, то есть распространённость вируса. В начальный момент заражалась половина узлов сети, после чего правила SIS-модели итеративно применялись с параллельным обновлением. По окончании начального переходного режима система стабилизировалась в стационарном состоянии с постоянной средней плотностью инфицированных узлов. В этом состоянии узлы заражались повторно без заметной периодичности. Распространённость определялась усреднением как минимум по 100 различным начальным конфигурациям, рассчитанным не менее чем на 10 различных реализациях случайной сети.
Первый поразительный результат моделирования – отсутствие эпидемического порога, то есть 𝜆 = 𝑐 0. На рис. 2 показана стационарная распространённость вируса, которая при уменьшении 𝜆 убывает как 𝜌 ∼ exp(−𝐶/𝜆), где 𝐶 – константа. Следовательно, при любом конечном значении 𝜆 вирус может охватить достаточно большую сеть, сохраняя конечную распространённость. Во всех сетях с ограниченной степенью узлов стационарная распространённость ниже эпидемического порога всегда равна нулю: все заражения угасают. Дополнительным подтверждением нашего результата является полное отсутствие масштабной зависимости 𝜌 от числа узлов которая, напротив, характерна для эпидемических переходов вблизи конечного порога [8]. Это позволяет исключить артефакты, обусловленные конечным размером сети. Результат можно понять интуитивно на обычных решётках чем выше степень узла, тем ниже эпидемический порог. В SF-сети неограниченные флуктуации степени, ⟨𝑘2⟩ = ∞, играют роль бесконечной связности и тем самым обнуляют порог.
Наконец, мы анализируем распространение инфекции из локализованного источника вируса. Рост заражения со временем имеет степенной характер что согласуется с реальными данными, в которых экспоненциального роста численности циркулирующего вируса не наблюдалось. Примечательно, что применяя использованное выше определение вероятности выживания 𝑃 (𝑡), в нашей модели мы по- 𝑠 Рис. 3. (a) Вероятность выживания 𝑃 (𝑡) при скорости распростра- 𝑠 нения 𝜆 = 0,065 в безмасштабных сетях размеров 𝑁 = 5 × 105 (квадраты), 𝑁 = 2,5 × 104 (ромбы), 𝑁 = 1,25 × 104 (треугольники) и 𝑁 = 6,25×103 (кружки). Экспоненциальное поведение после резкого начального спада согласуется с анализом данных на рис. 1.
(b) Относительная плотность 𝜌 как функция 𝑘−1 в SF-сети разме- 𝑘 ра 𝑁 = 5 × 105 при 𝜆 = 0,1. График воспроизводит зависимость, предсказанную уравнением (2). мость (рис. 3a). Характерное время жизни зависит от скорости распространения и размера сети, что позволяет связать среднее время жизни вирусного штамма с эффективной скоростью распространения и размером Интернета [20]. Одновременно расходимость времён жизни при увеличении размера сети указывает, что по мере расширения Интернета вирусы живут дольше.
К системе можно подойти и аналитически, записав одноузельное уравнение, описывающее временную эволюцию 𝜌(𝑡). Для учёта флуктуаций степени введём относительную плотность 𝜌 (𝑡) инфицирован- 𝑘 ных узлов заданной степени 𝑘, то есть вероятность того, что узел с 𝑘 связями инфицирован. Динамические уравнения скоростей реакций в приближении среднего поля имеют вид [8,21] 𝜕 𝜌 (𝑡) = −𝜌 (𝑡) + 𝜆𝑘[1 − 𝜌 (𝑡)]Θ(𝜆). (1) 𝑡 𝑘 𝑘 𝑘 Член рождения инфекции учитывает вероятность того, что узел с 𝑘 связями здоров, [1 − 𝜌 (𝑡)], и заража- 𝑘 ется через соседний узел. Вероятность этого события пропорциональна скорости заражения, числу связей и вероятности Θ(𝜆) того, что произвольно выбранная связь ведёт к инфицированному узлу. Среднеполевой характер уравнения обусловлен тем, что корреляции плотностей между различными узлами не учитываются. Вместе с тем мы отказались от предположения об однородности степеней узлов, обычно используемого для регулярных сетей. Налагая условие стационарности, 𝜕 𝜌 (𝑡) = 0, получаем стацио- 𝑡 𝑘 нарные плотности 𝑘𝜆Θ(𝜆) 𝜌 =, (2) 𝑘 1 + 𝑘𝜆Θ(𝜆) то есть чем выше степень узла, тем больше вероятность его заражения. Эту неоднородность необходимо учитывать при самосогласованном вычислении Θ(𝜆). Действительно, вероятность того, что связь ведёт к узлу с 𝑠 связями, пропорциональна 𝑠𝑃 (𝑠). Ины- Θ(𝜆) = ∑ ∑ 𝑠𝑃 (𝑠). (3) 𝑘 𝑠 Поскольку 𝜌, в свою очередь, зависит от Θ(𝜆), мы по- 𝑘 лучаем уравнение самосогласования, позволяющее определить Θ(𝜆) и 𝜌. Наконец, параметр порядка 𝑘 можно вычислить из соотношения 𝜌 = ∑ 𝑃 (𝑘)𝜌 𝑘 𝑘 выражающего среднюю плотность инфицированных узлов в системе. В рассматриваемой SF-модели распределение степеней имеет вид 𝑃 (𝑘) = 2𝑚2/𝑘3, причём 𝑘 аппроксимируется непрерывной переменной
[6]. Интегрирование уравнения (3) в низшем порядке по 𝜆 даёт 𝑒−1/(𝑚𝜆) Θ(𝜆) =. 𝜆𝑚 После усреднения по 𝜌 окончательно получаем 𝑘 𝜌 ≃ 2𝑒−1/(𝑚𝜆). (4)
Этот наглядный расчёт воспроизводит численные результаты и подтверждает неожиданное отсутствие в модели какого-либо эпидемического порога или критической точки, то есть 𝜆 = 0. В качестве допол- 𝑐 нительной проверки аналитических результатов мы численно вычислили относительные плотности 𝜌 в 𝑘 модели и восстановили предсказанную уравнением (2) зависимость от 𝑘 (рис. 3b). Следует также отметить, что предложенную схему можно обобщить на сети с 2 < 𝛾 ≤ 3, получив качественно те же результаты. Лишь при 𝛾 > 4 эпидемии в SF-сетях имеют те же свойства, что и в случайных сетях. Подробный анализ различных случаев будет представлен отдельно
[22].
Возникающая картина эпидемического распространения в сложных сетях подчёркивает роль топологии в эпидемическом моделировании. В частности, отсутствие эпидемического порога и критического поведения в широком классе безмасштабных сетей является неожиданным результатом, радикально меняющим многие стандартные выводы о распространении эпидемий. Инфекции могут размножаться в таких сетях при сколь угодно малой скорости распространения. Однако эта крайне неблагоприятная особенность компенсируется экспоненциально малой распространённостью в широком диапазоне скоростей, 𝜆 ≪ 1. Данный вывод особенно важен для технологических сетей, таких как Интернет [4], чья безмасштабная связность характеризуется показателем 𝛾 ≃ 2,5. Предложенная картина, например, качественно согласуется с реальными данными о распространении компьютерных вирусов и может разрешить давнюю проблему повсеместно низкой распространённости таких вирусов без предположения о какой-либо глобальной настройке скоростей распространения.
Работа частично поддержана контрактом European Network No. ERBFMRXCT980183. Р. Пастор-Саторрас также благодарит за поддержку по гранту CICYT обсуждения.
Список литературы
[1] См. специальный раздел, посвящённый сложным системам: Science 284, 79 (1999); S. Wasserman and K. Faust, Social Network Analysis (Cambridge University Press, Cambridge, 1994).
[2] L. A. N. Amaral, A. Scala, M. Barthélémy, and H. E. Stanley, Proc.
Natl. Acad. Sci. U.S.A. 97, 11149 (2000).
[3] M. Faloutsos, P. Faloutsos, and C. Faloutsos, ACM SIGCOMM ’99, Comput. Commun. Rev. 29, 251 (1999).
[4] A. Medina, I. Matt, and J. Byers, Comput. Commun. Rev. 30, 18 (2000); G. Caldarelli, R. Marchetti, and L. Pietronero, Europhys. Lett. 52, 386 (2000).
[5] R. Albert, H. Jeong, and A.-L. Barabási, Nature (London) 401, 130 (1999).
[6] A.-L. Barabási and R. Albert, Science 286, 509 (1999); A.-L.
Barabási, R. Albert, and H. Jeong, Physica (Amsterdam) 272A, 173 (1999).
[7] C. Moore and M. E. J. Newman, Phys. Rev. E 61, 5678 (2000).
[8] J. Marro and R. Dickman, Nonequilibrium Phase Transitions in Lattice Models (Cambridge University Press, Cambridge, 1999).
[9] F. B. Cohen, A Short Course on Computer Viruses (John Wiley & Sons, New York, 1994).
[10] J. O. Kephart, G. B. Sorkin, D. M. Chess, and S. R. White, Sci. Am.
277, No. 5, 56 (1997); S. R. White, in Proceedings of the Virus Bulletin Conference, Munich, 1998. Доступно в сети: http://ww w.research.ibm.com/antivirus/SciPapers.htm.
[11] N. T. J. Bailey, The Mathematical Theory of Infectious Diseases (Griffin, London, 1975), 2nd ed.; J. D. Murray, Mathematical Biology (Springer-Verlag, Berlin, 1993).
[12] M. K. Hill, Understanding Environmental Pollution (Cambridge University Press, Cambridge, 1997).
[13] J. O. Kephart, S. R. White, and D. M. Chess, IEEE Spectr. 30, 20 (1993).
[14] W. H. Murray, Comput. Sec. 7, 130 (1988).
[15] J. O. Kephart and S. R. White, in Proceedings of the 1991 IEEE Computer Society Symposium on Research in Security and Privacy (SSP ’91) (IEEE, Washington, 1991), p. 343.
[16] Можно также определить модели, в которых скорость заражения пропорциональна числу инфицированных ближайших соседей [8]. В интересующем нас режиме малой распространённости оба определения дают в точности одинаковое поведение.
[17] Данные о распространённости вирусов доступны на вебсайте http://www.virusbtn.com/Prevalence/.
[18] Именно так вероятность выживания обычно определяется в численном моделировании процессов распространения; см.
[8].
[19] P. Erdős and P. Rényi, Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960); D. J. Watts and S. H. Strogatz, Nature (London) 393, 440 (1998); A. Barrat and M. Weigt, Eur. Phys. J. B 13, 547 (2000).
[20] Такое характеристическое масштабирование часто встречается при фазовых переходах в поглощающее состояние в системах конечного размера [8]. В общем случае ненулевая величина 𝑃 (∞) возможна только для сетей бесконечного раз- 𝑠 мера.
[21] G. Szabó, Phys. Rev. E 62, 7474 (2000).
[22] R. Pastor-Satorras and A. Vespignani (не опубликовано).
Источник: R. Pastor-Satorras and A. Vespignani, “Epidemic Spreading in ScaleFree Networks,” Physical Review Letters 86, 3200–3203 (2001). Русский перевод подготовлен по предоставленному пользователем оригиналу.