Распространение эпидемий в безмасштабных сетях

Пастор-Саторрас Р., Веспиньяни А.

Университет Политехника де Каталунья, Барселона, Испания,
Международный центр теоретической физики им. Абдуса Салама, Триест, Италия

Аннотация

Интернет, а также многие другие сети, обладают очень сложной связностью, которая недавно была описана с помощью класса безмасштабных сетей (SF). Эта особенность, которая, с одной стороны, оказывается очень эффективной для коммуникационной сети, одновременно способствует распространению компьютерных вирусов. Мы анализируем реальные данные об инфекциях, вызванных компьютерными вирусами, и находим среднее время жизни и распространенность вирусных штаммов в Интернете. Мы определяем динамическую модель для распространения инфекций в безмасштабных сетях и обнаруживаем отсутствие эпидемического порога и соответствующего критического поведения. Эти новые эпидемиологические рамки позволяют рационально объяснить данные о компьютерных вирусах и могут помочь в понимании других явлений распространения в коммуникационных и социальных сетях.

1. Введение

Многие социальные, биологические и коммуникационные системы можно корректно описать с помощью сложных сетей, в которых узлы представляют отдельных лиц или организации, а связи имитируют взаимодействия между ними. Особенно интересными примерами являются Интернет и Всемирная паутина (WWW), которые были подробно изучены из-за их технологической и экономической значимости. Эти исследования выявили, среди прочего, безмасштабную природу этих сетей. Это приводит к степенному распределению P(k) ~ k^-γ для вероятности того, что узел сети имеет k связей с другими узлами, где показатель степени γ лежит в диапазоне от 2 до 3.

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

В данной работе мы анализируем данные реальных эпидемий компьютерных вирусов, предоставляя их статистическую характеристику, которая указывает на важность учета особой топологии безмасштабных сетей в теоретическом описании этих инфекций. С этой целью мы изучаем модель восприимчиво-инфицированно-восприимчиво (SIS) на безмасштабных графах с помощью крупномасштабного моделирования и аналитических методов. Мы обнаруживаем отсутствие эпидемического порога и связанного с ним критического поведения, что означает, что безмасштабные сети склонны к распространению и сохранению инфекций независимо от скорости распространения эпидемического агента. Отсутствие эпидемического порога — стандартного элемента математической эпидемиологии — кардинально меняет многие стандартные выводы, сделанные при моделировании эпидемий.

2. Стандартная модель и проблема с данными

Эпидемиологический анализ компьютерных вирусов является предметом постоянного интереса в сообществе специалистов по информатике и в основном следует подходам, заимствованным из биологической эпидемиологии. Стандартной моделью, используемой при изучении инфекций, вызванных компьютерными вирусами, является эпидемиологическая модель SIS (Susceptible-Infected-Susceptible). Каждый узел сети представляет собой индивидуума, а каждая связь — это канал, по которому инфекция может распространяться на другие системы.

Эта модель опирается на грубое описание индивидуумов в популяции. Индивидуумы могут находиться только в двух дискретных состояниях: «здоровый» или «инфицированный». На каждом временном шаге каждый восприимчивый (здоровый) узел заражается с вероятностью ν, если он связан с одним или более инфицированными узлами. В то же время инфицированные узлы излечиваются и снова становятся восприимчивыми с вероятностью δ, что определяет эффективную скорость распространения λ = ν/δ.

Без потери общности мы можем положить δ = 1. В моделях с локальной связностью (евклидовы решетки и модели среднего поля) наиболее значимым результатом является общее предсказание ненулевого эпидемического порога λ_c. Если значение λ выше порога (λ ≥ λ_c), инфекция распространяется и становится устойчивой. Ниже порога (λ < λ_c) инфекция экспоненциально быстро исчезает. Эпидемический порог, по сути, эквивалентен критической точке в неравновесном фазовом переходе, отделяя активную фазу (с устойчивой плотностью инфицированных узлов) от фазы, в которой присутствуют только здоровые узлы.

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

3. Анализ реальных данных

Чтобы лучше понять свойства распространения вирусов в реальных условиях, мы проанализировали данные о распространенности, опубликованные в Virus Bulletin с февраля 1996 по март 2000 года. Мы изучили вероятность выживания однородных групп вирусов, классифицированных по их механизму заражения.

Мы рассмотрели общее количество вирусов данного штамма, которые появились и исчезли в нашем окне наблюдения. Таким образом, мы рассчитали вероятность выживания P_s(t) штамма как отношение количества вирусов, все еще активных во время t после их появления, к общему количеству наблюдаемых вирусов.

На рисунке 1 показано, что вероятность выживания резко падает в первые два месяца жизни вируса. Это хорошо известная особенность, указывающая на то, что статистически только небольшой процент вирусов вызывает значительную вспышку в компьютерном сообществе. С другой стороны, на рисунке 1 для больших времен наблюдается чистый экспоненциальный хвост, P_s(t) ~ exp(-t/τ), где τ представляет собой характеристическое время жизни штамма вируса. Численное соответствие данных дает τ ≃ 14 месяцев для загрузочных и макровирусов и τ ≃ 6–9 месяцев для файловых вирусов.

Эти характеристические времена впечатляюще велики по сравнению с интервалом, в течение которого антивирусное программное обеспечение становится доступным на рынке (обычно в течение нескольких дней или недель после первого отчета об инциденте), и указывают на то, что временная шкала сохранения вирусов больше связана с реализацией профилактических мер безопасности, чем со своевременной доступностью конкретного антивируса. Эти внешние факторы, однако, не могут конкурировать на короткой временной шкале распространения вирусов (дни или недели), и мы снова сталкиваемся с загадочным вопросом: почему вирусы, по-видимому, имеют доступ к устойчивым уровням с низкой распространенностью, но никогда не растут экспоненциально?

4. Ключевая роль топологии сети

Ключевой момент для понимания загадочных свойств компьютерных вирусов заключается в способности многих из них переноситься по электронной почте в виде, казалось бы, безобидного вложения. Имея это в виду, легко понять, что топология связей между индивидуумами не может быть корректно представлена евклидовой решеткой или моделью среднего поля. Эти связи, скорее, должны иметь топологию Интернета, по которому проходит электронная почта.

Безмасштабная связность Интернета означает, что каждый узел имеет статистически значимую вероятность обладать очень большим количеством связей по сравнению со средней связностью <k> сети. Это противоположно обычным случайным сетям (локальным или нелокальным), в которых каждый узел имеет примерно одинаковое количество связей k ≃ <k>. Тот факт, что все вирусные штаммы качественно демонстрируют одни и те же статистические особенности, указывает на то, что, вероятно, все они распространяются по сетям со свойствами связности, аналогичными свойствам Интернета. Следовательно, естественно предположить, что безмасштабные свойства должны быть включены в теорию распространения эпидемий компьютерных вирусов.

5. Моделирование на безмасштабных сетях и отсутствие порога

Чтобы изучить влияние безмасштабной связности на распространение эпидемий, мы исследовали модель SIS на безмасштабной сети. Мы рассматривали граф, сгенерированный с использованием алгоритма, предложенного в работах Барабаши и Альберт. Мы начинаем с небольшого числа m₀ несвязанных узлов; на каждом временном шаге добавляется новый узел с m связями, которые соединяются со старым узлом i с вероятностью k_i/∑_jk_j.

После достаточного числа итераций мы получаем сеть, состоящую из N узлов, с распределением связности P(k) ~ k^-3 и средней связностью <k>= 2m. В данной работе мы принимаем m=3. Мы провели численное моделирование на графах с числом узлов от N=10³ до N=8,5×10⁶ и изучили изменение во времени и стационарные свойства плотности инфицированных узлов ρ при выживших инфекциях.

Первым поразительным свидетельством из моделирования является отсутствие эпидемического порога, то есть λ_c=0. На рисунке 2 показано, что распространенность вируса в стационарном состоянии убывает с уменьшением λ как ρ ~ exp(-C/λ), где C — постоянная. Это означает, что при любом конечном значении λ вирус может проникнуть в систему с конечной распространенностью в достаточно больших сетях. Во всех сетях с ограниченной связностью стационарная распространенность всегда равна нулю ниже эпидемического порога, то есть все инфекции исчезают.

Мы также проанализировали распространение инфекций, начиная с локализованного источника вируса. Мы наблюдали, что рост распространения во времени имеет алгебраическую форму, что согласуется с реальными данными, в которых никогда не наблюдалось экспоненциального роста вируса в дикой природе. Примечательно, что, применив определение вероятности выживания P_s(t), использованное для анализа реальных данных, мы воспроизводим в нашей модели то же самое экспоненциальное поведение во времени (см. рис. 3a). Характеристическое время жизни зависит от скорости распространения и размера сети, что позволяет нам связать среднее время жизни вирусного штамма с эффективной скоростью распространения и размером Интернета.

6. Аналитическое рассмотрение

Мы также можем подойти к системе аналитически, записав уравнение среднего поля, управляющее временной эволюцией ρ(t). Чтобы учесть флуктуации связности, мы рассматриваем относительную плотность ρ_k(t) инфицированных узлов с заданной связностью k, то есть вероятность того, что узел с k связями инфицирован. Уравнения динамики среднего поля можно записать как:

∂_tρ_k(t) = -ρ_k + λk(1 - ρ_k(t))Θ(λ).

Слагаемое рождения учитывает вероятность того, что узел с k связями здоров и получает инфекцию через связанный узел. Эта вероятность пропорциональна скорости заражения, числу связей и вероятности Θ(λ) того, что любая заданная связь указывает на инфицированный узел.

Наложив условие стационарности (∂_tρ_k(t) = 0), мы находим стационарные плотности:

ρ_k = kλΘ(λ) / (1 + kλΘ(λ)).

Это означает, что чем выше связность узла, тем выше вероятность быть инфицированным. Эта неоднородность должна быть учтена при самосогласованном расчете Θ(λ). Действительно, вероятность того, что связь указывает на узел с s связями, пропорциональна sP(s). Другими словами, случайно выбранная связь с большей вероятностью будет соединена с узлом с высокой связностью. Таким образом, мы получаем самосогласованное уравнение, которое позволяет найти Θ(λ), а затем и среднюю плотность инфицированных узлов ρ.

В рассматриваемой безмасштабной модели мы имеем распределение связности P(k) = 2m²k^-3. Интегрирование приводит к следующему результату для ρ при малых λ:

ρ = 2e^-1/(mλ) + ...

Это очень интуитивное вычисление подтверждает численные результаты и подтверждает удивительное отсутствие какого-либо эпидемического порога или критической точки в модели, то есть λ_c=0.

7. Заключение

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

Эти «очень плохие новости» смягчаются экспоненциально малой распространенностью для широкого диапазона скоростей распространения (λ << 1). Этот момент особенно важен в случае технологических сетей, таких как Интернет и Всемирная паутина, которые демонстрируют безмасштабную связность с показателями степени γ ≃ 2.5. Например, данная картина прекрасно соответствует наблюдениям за реальными данными о распространении компьютерных вирусов и может решить давнюю проблему общей низкой распространенности компьютерных вирусов без предположения о какой-либо глобальной настройке скоростей распространения.