Что такое уязвимость и надежность графа?
Впервые упомянутая еще в 1970-х годах, надежность сети имеет богатую и разнообразную историю, охватывающую множество областей техники и науки. Хотя области исследования разнообразны, они связаны общим определением, определяемым как
мера способности сети продолжать функционировать, когда часть сети естественным образом повреждена или подверглась атаке.
Изучение надежности сети является важным инструментом для описания и понимания сложных взаимосвязанных систем, таких как транспорт, инфраструктура, связь и компьютерные сети. Благодаря анализу и пониманию надежности этих сетей мы можем: (1) количественно оценить уязвимость и надежность сети, (2) расширить структуру сети для защиты от атак и восстановления от сбоев и (3) контролировать распространение сущностей в сети (например, вирусов, пропаганды).
Например, чтобы свести к минимуму способность вирусов распространяться, мы можем отслеживать (удалять) узлы в графе, чтобы уменьшить связность графа. С другой стороны, если вы хотите максимизироватьраспространение по сети, например, в рамках маркетинговой кампании, мы можем использовать методы защиты, такие как перемонтаж краев или добавление, чтобы увеличить связность графа. На рисунке 3 ниже мы выделяем модель инфекционного заболевания SIS и то, как методы защиты TIGER могут помочь сдержать смоделированную вспышку.
Здесь мы сосредоточимся на распространении сетевых объектов, которые пытаются зафиксировать лежащий в основе механизм, обеспечивающий распространение сети. Чтобы усилить процесс распространения, TIGERиспользует несколько методов защиты для использования с двумя известными моделями распространения: восприимчивость к гриппу- модель инфицированных-восприимчивых (SIS) и модель вакцинированных-восприимчивых-инфицированных-выздоровевших (SIR).
Чтобы помочь пользователям визуализировать процесс распространения, мы даем им возможность создавать изображения, подобные рисунку 1, где мы запускаем моделирование компьютерного вируса SIS в сети Oregon-1 Autonomous System. В верхней части рис. 1 показано распространение вируса при защите 5 узлов, выбранных с помощью Netshield. К 1000-му шагу вирус почти вымер. В нижней части рисунка 3 показано, что вирус остается эндемичным без защиты.
Какие инструменты доступны для изучения надежности сети?
Несмотря на то, что изучению уязвимости и надежности сетей посвящены значительные исследования, в настоящее время не существует всеобъемлющего набора инструментов с открытым исходным кодом, который мог бы помочь исследователям и практикам в этой важной теме. Это отсутствие доступных инструментов препятствует воспроизводимости и изучению существующей работы, развитию новых исследований и распространению новых идей.
Мы считаем, что унифицированная и простая в использовании программная среда является ключом к стандартизации исследований надежности сети, помогая ускорить воспроизводимые исследования и распространение идей. Поэтому мы разработали TIGER, первый набор инструментов Python с открытым исходным кодомдля оценки уязвимости сети и надежности графов . TIGER содержит 22 меры устойчивости графов, по возможности, как с исходными, так и с быстрыми приблизительными версиями; 17 механизмов отказа и атаки; 15 эвристических и оптимизационных методов защиты; и 4 инструмента моделирования. Насколько нам известно, это делает TIGER наиболее полной открытой структурой для анализа надежности сети на сегодняшний день.
Меры надежности
TIGER содержит 22 показателя устойчивости, сгруппированных в одну из трех категорий в зависимости от того, использует ли показатель граф, смежность или матрицу Лапласа. В таблице 1 мы выделяем каждую реализованную меру, категорию, к которой она принадлежит (граф, смежность, Лапласиан), и ее применение к надежности сети.
Для подробного описания и обсуждения всех 22 мер мы отсылаем читателя к документу arXiv и странице Github.
Пример показателей надежности
Мы выбираем 3 меры устойчивости, по одной из каждой из трех категорий, для подробного обсуждения.
- Среднее расстояние между вершинами (уравнение 1) графа G=(V, E),где V — множество вершин, а E — множество ребер графа, — сумма промежуточности вершин bᵥ для каждого узла u∈ V, где промежуточность вершин для узла u определяется как количество кратчайших путей, проходящих через u, из всех возможных кратчайших путей
где nₛₜ(u) — количество кратчайших путей между s и t, которые проходят через u и nₛₜ — общее количество кратчайших путей между s и t. Средняя промежуточность вершин имеет естественную связь с надежностью графа, поскольку она измеряет среднюю нагрузку на вершины в сети. Чем меньше среднее значение, тем надежнее сеть, поскольку нагрузка распределяется по узлам более равномерно.
2. Спектральное масштабирование(уравнение 2)указывает, является ли сеть одновременно разреженнойи высоко связанной, известной как “ хорошее расширение» (ГЭ). Интуитивно мы можем думать о сети с GE как о сети без мостов или узких мест. Чтобы определить, имеет ли сеть GE, вы можете комбинировать меру спектрального разрыва с центральностью нечетного подграфа SC(odd), которая измеряет количество замкнутых блужданий нечетной длины, в которых участвует узел. Формально спектральное масштабирование определяется как
Чем ближе ξ к нулю, тем лучше свойства расширения и тем надежнее сеть. Обычно считается, что сеть имеет GE, если ξ‹ 0,01.
3. Эффективное сопротивление (уравнение 3) представляет граф как электрическую цепь, где ребро (i, j) соответствует сопротивлению r(i, j). ) = 1 Ом, а узел i соответствует соединению. Таким образом, эффективное сопротивление между двумя вершинами i и j, обозначаемое R(i, j), представляет собой электрическое сопротивление, измеренное на i и j при расчете с использованием законов Кирхгофа. Распространяя это на весь граф, мы говорим, что эффективное сопротивление графаR представляет собой сумму сопротивлений для всех различных пар вершин. Кляйн и Рэндик доказали, что это можно рассчитать на основе суммы обратных ненулевых собственных значений Лапласа.
В качестве меры надежности эффективное сопротивление измеряет, насколько хорошо подключена сеть, где меньшее значение указывает на более надежную сеть. Кроме того, эффективное сопротивление обладает многими желаемыми свойствами, в том числе тем, что оно строго уменьшается при добавлении ребер и учитывает как количество путей между парами узлов, так и их длину.
Сетевые атаки
Существует два основных способа повреждения сети: (1) естественный сбой и (2) целевая атака. Естественные отказы обычно возникают, когда часть оборудования выходит из строя по естественным причинам. При изучении графов это будет соответствовать удалению узла или ребра в графе. Хотя случайные сбои в сети происходят регулярно, они обычно менее серьезны, чем целевые атаки. Напротив, целевые атаки тщательно выбирают узлы и ребра в сети для удаления, чтобы максимально нарушить функциональность сети. Поэтому основное внимание мы уделяем целенаправленным атакам.
Ниже мы рассмотрим один тип атаки, подробное описание и обсуждение всех 10 атак мы отсылаем читателя к бумаге arXiv и странице Github.
На рисунке 2 мы моделируем атаку на водопроводную сеть Кентукки KY-2. Сеть запускается в нормальных условиях (крайний слева), и на каждом этапе злоумышленник удаляет дополнительный узел (красные узлы).
После удаления только 13 из 814 узлов сеть разделяется на два отдельных региона. На шаге 27 сеть разбивается на четыре несвязанных региона. В этом моделировании и в целом стратегии атаки полагаются на меры центральности узлов и ребер для выявления кандидатов.
Сетевая защита
Те же меры сетевой центральности, которые эффективны при атаке на сеть, важны для защиты сети (например, степень, промежуточность, PageRank, собственный вектор и т. д.). На самом деле, если стратегия атаки известна априори, мониторинг узла может полностью предотвратить атаку.
Мы классифицируем методы защиты в зависимости от того, действуют ли они эвристически, модифицируют ли структуру графа независимо от меры надежности или путем оптимизации дляконкретного мера надежности. В рамках каждой категории сеть можно защитить, т. е. повысить ее надежность за счет — (1) переустановки краев, (2) добавления краев или (iii) узла. мониторинг.
Пограничная перенастройка считается недорогой, менее эффективной версией добавления периферии. С другой стороны, добавление ребра почти всегда обеспечивает более сильную защиту. Мониторинг узлов обеспечивает ортогональный механизм повышения надежности сети за счет отслеживания (или удаления) узлов в графе. Это имеет множество приложений, в том числе: (i) предотвращение целевых атак, (ii) смягчение последствий каскадных сбоев и (iii) сокращение распространения сетевых объектов.
Мы оцениваем эффективность 5 краевых защит в водопроводной сети Кентукки KY-2 (см. рис. 2), усредненную по 10 участкам. Сеть атакуют путем удаления 30 наиболее «важных» узлов с использованием стратегии атаки по степени централизации, и успех каждой защиты измеряется на основе того, как она может повторно подключить сеть, добавляя или переподключая ребра в сети (чем выше, тем лучше). . Основываясь на рисунке 2, мы выделяем три ключевых наблюдения: (i) предпочтительное добавление ребер работает лучше всего; (ii) добавление ребер, как правило, превосходит стратегии перемонтажа; и (iii) случайное переподключение соседей обычно работает лучше, чем другие стратегии переподключения.
Инструменты сетевого моделирования
TIGER содержит 4 широких и важных типа инструментов моделирования надежности: (1) распространение сетевых объектов, (2) каскадные сбои, (3) сетевые атаки и (4) сетевая защита.
Например, рассмотрим рис. 3, на котором показан пример электросетевой сети, подверженной как естественным сбоям, так и целевым атакам. Естественный отказ возникает, когда одна электрическая подстанция выходит из строя из-за эрозии частей или стихийных бедствий. Однако при выходе из строя одной подстанции дополнительная нагрузка направляется на альтернативные подстанции, что может привести к серии каскадных отказов. Однако не все сбои происходят по естественным причинам, некоторые происходят в результате целевых атак, например, когда вражеские государства взламывают сеть, чтобы саботировать ключевое оборудование, чтобы максимально повредить работу электросети.
Хотите узнать больше?
Для получения подробной информации о TIGER мы публикуем наш код на Github, а нашу статью — на arXiv.
