Диссертация (1143658), страница 13
Текст из файла (страница 13)
При этом возможны два варианта, в первом случае90злоумышленник находится на пути легитимного маршрута от узла, чейидентификатор он подделал, до получателя; во втором случае злоумышленник ненаходится на этом пути.Первый случай представлен на рисунке 4.3. Здесь узел с идентификатором«daa» отправляет сообщение от имени узла «ddc» узлу «abb». Основной маршрутсовпадает и выделен жирным черным цветом, но при этом дополнительныймаршрут, построенный злоумышленником (выделен красным цветом), на первомшаге попадает в узел «dac», который гарантированно верно может судить о том,может ли через него проходить легитимный дополнительный маршрут от узла«ddc» к узлу «abb» (выделен зеленым цветом).
Таким образом, на первом шагедополнительного маршрута выявляется злоумышленник.Рисунок 4.3 – Обнаружение узлом «dac» злоумышленника «daa»Второй случай представлен на рисунке 4.4. Здесь узел с идентификатором«bcb» отправляет сообщение от имени узла «ddc» узлу «abb». Основной и91дублирующий маршрут не совпадают с легитимными, выделеными жирнымчерным и зеленым цветом. Таким образом, и основной и дополнительный маршрут,построенные злоумышленником (выделены красным цветом), на первом шагепопадают в узел «bca» и «bcc» соответственно. Эти узлы гарантированно верноможгут судить о том, может ли через них проходить легитимный основной идополнительный маршрут от узла «ddc» к узлу «abb».
Таким образом,злоумышленник выявляется на первом шаге построенных основного идополнительного маршрута.Рисунок 4.4 – Обнаружение узлами «bca» и «bcc» злоумышленника «daa»4.1.4Механизм обеспечения безопасности от угрозы «Пересылкасообщений по выделенному каналу»Угроза «Пересылка сообщений по выделенному каналу» (англ.
Wormhole)заключается в том, что внутренний нарушитель, контролирующий более одногоузла, способен получить контроль над путём передачи сообщений за счёт92использования более быстрого и менее загруженного выделенного канала связимежду подконтрольными узлами с целью получения предпочтения приформировании пути в динамических протоколах маршрутизации либо связи впротоколах построения VANET.Данная угроза неактуальна в VANET-сетях с предфрактальной топологиейввидупримененияалгоритмамаршрутизации,описанногов3.1.3,оптимизирующего маршруты, опираясь на фрактальные свойства топологии, а нена скорость передачи данных в отдельных каналах связи.4.1.5Механизм обеспечения безопасности от угрозы «Фальсификацияпараметров маршрутизации»Угроза «Фальсификация параметров маршрутизации» (англ.
AlterationAttack) заключается в том, что внутренний нарушитель способен производитьпередачу поддельной информации, используемой в качестве параметров выбораоптимального пути в протоколах маршрутизации. Например, нарушитель способенизменять информацию о длине пути до других узлов сети, либо заменятьинформацию о своих географических координатах. Реализуя данную уязвимость,нарушитель способен повлиять на построения маршрута передачи сообщений всети с целью их дальнейшего перехвата, изменения либо сброса.Данная угроза не может быть реализована в VANET-сетях с фрактальнойтопологией в связи с тем, что единственной необходимой для построенияоптимального маршрута информацией является индекс источника и получателя.Таким образом, угроза фальсификации параметров маршрутизации сводится кугрозе имперсонации, механизм защиты от которой описан в 4.2.3.4.2Оценка минимальной и максимальной длины маршрута в VANETсети c предфрактальной топологиейФГn – Предфрактальный граф n-го порядка.Определение: Максимальная конфигурация графа – вид ФГn, при которомраскрыты все возможные подграфы-затравки (рисунок 4.5).93Рисунок 4.5 – ФГ4 максимальной конфигурацииОпределение: Минимальная конфигурация графа - вид ФГn, которыйполучается рекурсивным схлопыванием сегментов графа одного порядка (рисунок4.6).Минимальная конфигурация определеяется так же тем, что еще одно любоеупрощение структуры графа приведет к понижению порядка, т.е.
в графеминимальной конфигурации содержится минимально возможное число вершиндля ФГn.Рисунок 4.6 – ФГ4 минимальной конфигурации.Теорема:94Кратчайший путь между максимально удаленными вершинами в ФГnминимальной конфигурации содержит не более n ребер.Доказательство:ФГn предфрактальный граф максимальной конфигурации. Как следует изпредыдущей теоремы, длина оптимального пути в таком графе не превышает 2 n –1. Схлопнем в вершины три сегмента из четырех, которые представляют собой ФГn1.
Рассмотрим, как теперь изменится верхняя оценка оптимального пути: т.к. изграфа был фактически удален подграф, то так же были удалены все возможныемаршруты, которые через него проходили (они стянулись к одной вершине, вкоторую был схлопнут сегмент), т.е. теперь длина оптимального пути в новомграфе (который все еще остается ФГn) равна = 2 − 1 − (2−1 − 1) = 2−1Возьмем оставшийся сегмент, и так же схлопнем в нем три из четырехсегментов, которые представляют собой ФГn-2. И продолжим так делать с каждымнесхлопнувшимся сегментом на каждом шаге.Данную операцию можно выполнить только n-1 раз, т.к. на каждом i-м шагеиз длины пути S будет вычитаться число, равное 2n-i – 1, и тогда на n-м шаге мыполучим2− − 1 = 1 − 1 = 0т.е. на n-м шаге мы фактически попытаемся схлопнуть вершину в саму себя,что никак не повлияет на вид графа.
Исходя из этих рассуждений, после n-1итерации мы получим следующий граф: подграф-затравка, который являетсясегментом подграфа ФГ2, который является сегментом подграфа ФГ3 и так далее,т.е. мы будем иметь граф минимальной конфигурации.Определим максимальную длину оптимального пути для него. Как известноиз теории целых чисел:−2 = 2−1 = ∑ 2 + 1.=095На каждой итерации схлопывания сегментов в вершины, как было сказано,мы будем вычитать из S число, равное 2n-i – 1. Тогда в целом дойдя до n-го шага мывычтем из S число P, равное−1−1 = ∑(2− − 1) = ∑ 2− − ( − 2)=2=2Таким образом, кратчайший путь между максимально удаленнымивершинами в ФГn минимальной конфигурации не превышает−2−1 ′ = − = ∑ 2 − ∑ 2− + 1 + − 2 = 1 + 1 + − 2 = =0=2Теорема доказана.Теперь предположим, что вершина сети хочет отправить сообщение другойвершине, зная только свой адрес и нужно оценить расстояние, которое пройдетсообщение.Обозначим индекс отправителя за X и индекс получателя за Y.
Еслиотправитель не знает всей топологии сети, то он может только оценить возможнуюдлину пути, т.к. вся информация, которой располагает отправитель – вид сегмента,в котором состоит он сам и вид сегмента, в котором состоит получатель.Для начала сделаем предположение, что отправитель и получательнаходятся максимально удаленно в графе, тогда в худшем случае, если граф имеетмаксимальную конфигурацию, сообщение пройдет M = 2n – 1 ребер и в лучшемслучае, если граф имеет минимальную конфигурацию, сообщение пройдет m = nребер.Таким образом, первичная оценка пути: ≤ ≤ 2 − 1Однако данная оценка носит обобщенный характер.
Для того, чтобы ееулучшить, необходимо использовать принцип алгоритма маршрутизации в даннойсети: сообщение будет двигаться внутри сегмента отправителя, потом черезединственное соединительное ребро переместится в сегмент получателя и в данном96сегменте будет двигаться к получателю. Учитывая это, а так же тот факт, чтотопология неизвестна отправителю, стоит рассмотреть путь как совокупность путив сегменте отправителя до соединительного ребра и пути в сегменте получателя досоединительногоребра(путиполучатель–соединительноереброисоединительное ребро – получатель эквивалентны друг другу).
В таком случае,оценка будет следующей: = 2−1 − 1 + 2−1 − 1 + 1 = 2 − 1 = ( − 1) + ( − 1) + 1 = 2 − 12 − 1 ≤ ≤ 2 − 1Можно заметить, что оценка максимальной длины пути в графеминимальной конфигурации оказалась почти вдвое больше, чем утверждаеттеорема, это происходит потому, что мы рассматриваем сегменты как дванезависимых подграфа минимальной конфигурации. Так, например, если у насграф, который изображен на рисунке 2, и мы вычислим m по формуле, приведеннойвыше (сумма длин путей в двух сегментах), то мы получим = (4 − 1) + (0) + 1 = 4как и утверждает теорема.Теперь, учитывая то, что мы знаем (благодаря индексам) точное положениеполучателя и отправителя в топологии сети, мы можем улучшить наши оценки.Рассмотрим следующее следствие из доказанной ранее теоремы: путь от даннойвершины до вершины своего сегмента, связанной с другим сегментом (сегментом,которому принадлежит второй индекс) :а)уменьшится на 2i-1;б)i для нижней оценки m, где i количество нулевых разрядов в индексевершины;Таким образом, можно дополнить оценку следующим образом: = 2 − 1 − − , = 2 − 1, где i - количество нулевых разрядов в индексе первой вершины; = 2 − 1, где j - количество нулевых разрядов в индексе первой вершины; = 2 − 1 − ′ − ′97′ = , где i - количество нулевых разрядов в индексе первой вершины;′ = , где j - количество нулевых разрядов в индексе первой вершины;2 − 1 − ′ − ′ ≤ ≤ 2 − 1 − − Рассмотрим следующее свойство алгоритма маршрутизации, применяемогов сети с системой индексации: если все разряды индекса получателя одинаковы (несчитая возможных нулей), то маршрут от отправителя до получателя сокращаетсяв зависимости от количества разрядов индекса отправителя, раных ненулевомуразряду индекса получателя (т.к.