Методологические основы моделирования
 Скачать 2.94 Mb.
|
|
Лекция 11 МОДЕЛИ И МЕТОДЫ ОЦЕНКИ РАЗВЕДЗАЩИЩЕННОСТИ СЕТЕЙ СВЯЗИ 1.Показатели разведзащищенности сетей связи. Известно, что деятельность органов управления с точностью до замысла выполнения задач возможно представить с помощью описания составаорганов управления, а также пространственной, временной и информационной структур. Эти же структуры при описании деятельности разведки (радиоразведки) выполняют роль системных демаскирующих признаков, по которым можно вскрыть деятельность ОУ. Там же показано, что наиболее информативным системным демаскирующим признаком является структура информационной сети и что по структуре информационной сети при соответствующих ограничениях на пространственную и временную, радиоразведка может вскрыть элементы замысла, решения и плана. Это объясняется тем, что при ограниченном числе средств планирование сводится к тому, чтобы структура информационной сети в наибольшей степени соответствовала характеру задач, решаемых органом управления, замыслу их применения. Благодаря этому свойству структуры информационной сети возможен переход от показателя скрытности деятельности органов управления по работе связи к показателю разведзащищенности сети связи. Показателем скрытности деятельности органов управления является вероятность распознавания варианта замысла выполнения задач к заданному моменту времени по работе средств связи, а показателем разведзащищенности является вероятность распознавания состава и структуры информационной сети, соответствующей данному варианту замысла выполнения задач. 2.Модель оценки разведзащищенности сети связи. В качестве математической модели сети выберем вероятностно взвешеный граф, вершинам которого соответствуют узлы и комплексы связи, а ребрам- каналы связи, их соединяющие. В качестве весовых коэффициентов вершин используются накопленные к заданному времени вероятности обнаружения единичных сообщений, исходящих из узла, соответствующего данной вершине.  (1)где Рi (t)-накопленная вероятность обнаружения i-го объекта (узла); ri- число излучающих средств на i- м объекте ; ij(t)- интенсивность передач от i-го к j-ому объекту (узлу); р1(t)- вероятность обнаружения единичного сообщения, в общем случае зависящая от времени (места, дистанции, условий, диапазона работы i-го средства riи.т.д). Распознавание структуры сводится к отнесению конкретно наблюдаемой сети к одному из заранее известных эталонов. В качестве эталонов используется набор типовых структур, применяемых в системах связи и АСУ, каждая структура задается детерминированным графом-эталоном. Для определения влияния только структурных свойств, индивидуальные демаскирующие признаки объектов, определяющие вероятность их распознавания, здесь учитывать не будем, поскольку это существенно упрощает задачу. Для оценки структурной скрытности сети используется показатель- вероятность распознавания структуры сети к заданному моменту времени при заданной интенсивности обмена сообщениями ij(t) в заданных условиях ведения разведки, определяемых вероятностью обнаружения единичного сообщения р1(t) . Процесс обнаружения будем рассматривать как обобщенный, позволяющий установить факт передачи сообщения и адресат, если он не скрывается, либо установить, что адресат скрывается, т.е. принимаются специальные меры по скрытию структуры сети. Для получения численного значения показателя используется имитационная модель. Обобщенный моделирующий алгоритм приведен на рис.4.1. Блок 1- ввод исходных данных: матрицы эталонов ||A||, размерности [nxn]; матрицы интенсивностей исследуемой структуры ||ij||; способов организации: аj =1 адресат j не скрывается, аj =0 адресат скрывается; характеристик радиоразведки р1(t); общего числа реализаций N* на шаге моделирования; шага моделирования Δt. Блок 2. Вычисление текущих значений накопленных вероятностей для каждого i-го узла. Блок 3. Розыгрыш графа- реализации по текущему значению Рi (t) с учетом <аj>. Блок 4. Определение принадлежности графа-реализации к одному из графов-эталонов. Блок 5. Расчет показателя структурной скрытности:  , где mi(k) - число случаев, когда граф-реализация относится к i-му эталону при фактическом розыгрыше k-го эталона.Блок 6. Вывод результатов в виде зависимости вероятности распознавания от времени. Таким образом Pi/ k(t) при i≠k характеризует эффективность маскировки, т.е. вероятность распознавания k-ой структуры как i-й , а при i=k как вероятность правильного распознавания k-ой структуры.  Рис.1. Блок-схема алгоритма оценки структурной скрытности. Центральным в алгоритме является блок распознавания изоморфности (изоморфного вложения) графа реализации и графа- эталона, поэтому алгоритмы распознавания изоморфности рассмотрим более детально. 3.Алгоритмы распознавания изоморфности графов. В методе распознавания деятельности по работе связи применен алгоритм распознавания случайных структур, позволяющий ускорить процесс распознавания структуры за счет информации о распознавании вершин ( объектов). Однако этот алгоритм не позволяет отделить структурную составляющую скрытности от неструктурной, определяемой вероятностью распознавания вершин, а следовательно не позволяет сравнивать скрытность “чистых” структур, выявлять наиболее скрытные, а также параметры чистых структур, от которых зависит их скрытность. Именно с целью устранения этих недостатков метода были предложены алгоритмы распознавания изоморфности графов и определены условия их наиболее эффективного применения. Здесь рассматривается способ, основанный на теореме о том, что в изоморфных графах циклы одного графа соответствуют циклам другого. При таком способе используется не только информация о совпадении полустепей исхода и захода, но и о порядке следования вершин в цикле. Если графы содержат по одному гамильтонову циклу, то задача решается практически за одну проверку, если графы содержат по одной вершине, отличающейся от всех остальных, и максимум за N проверок, если все вершины однородны. При отсутствии гамильтоновых циклов и большом количестве простых циклов, количество операций переборов подстановок вершин и проверок сохранения отношения смежности существенно возрастает. Этим определяется условие применения этого алгоритма. Обобщенный алгоритм распознавания изоморфности графов представлен на рис.2. Пример приведен для графов, представленных на рис.3. Задача формулируется следующим образом: Имеются матрицы смежности графа- эталона и графа- реализации. Требуется найти подстановки между вершинами графа-эталона и графа – реализации, сохраняющие отношения смежности или доказать обратное. Матрицы смежностей имеют размерности (n,n), где n- число вершин Задача решается следующим образом: 1. Вводятся матрицы графов-эталонов и реализации размерностью nxn: А(n,n)-матрица смежности графа- эталона В(n,n)-матрица смежности графа- реализации Перечисляются возможные пути(циклы) в каждом графе. Результаты сохраняются в матрицах СЕ(s,n), CR(s,n) соответственно для обоих графов где s- число путей(циклов) в графе. Нахождение путей осуществляется методом прямого поиска в глубину; 3. Определяются составные степени каждой вершины в графах. Результаты сохраняются в e(n) для графа-эталона и f(n) для графа реализации. 4. Вычисляется число вершин в каждом пути (цикле) в матрицах CE(s,n), CR(s,n) и результаты сохраняются в матрицах К1(n), K2(n) соответственно.  Рис.2. Обобщенный алгоритм определения изоморфности графов 5. Сравнивается число вершин в каждом пути(цикле) графа-эталона с графом-реализацией . В случае равенства числа вершин, проверяется равенство их степеней. В противном случае проверяется следующий путь (цикл). При отсутствии такого равенства принимается решение “графы не изоморфны”. 6.В генерируемой матрице смежности добавляются единицы в соответствии с вершинами исследуемых циклов. Проверка удовлетворения условия равенства степеней и сохранения смежности вершин, не вошедщих в циклы, в противном случае выполнять 5. В случае выполнения пункта 7 добавлять соответственно к тем вершинам единицы в матрицу смежности. 9. получение перестановочной матрицы, в каждой строке и столбце которой содержится одна единица, т.е. элементы строк - это вершины графа-эталона, а элементы столбцов - соответствующие им вершины графа-реализации. Рассмотрим пример реализации алгоритма “вручную” и на ЭВМ.  a) б) Рис.4.3. Исследуемые графы а)граф G(X,F), б) граф H(Y,P) Пусть заданы два графа G(X,F) и H(Y,P) , изображенных на рис.4.3.(а, б). Задача – определить, являются ли они изоморфными. При производстве перебора подстановок понадобятся некоторые структурные характеристики обоих графов. Эти характеристики приведены в таблице(4.1) Известна формула Эйлера для определения числа независимых циклов в связном графе M=B-N+1, (4.2) где M-количество независимых циклов; N- количество вершин в графе B- количество ребер(ветвей) в графе.
В графах G(X,F) и H(Y,P) таких независимых циклов 3, например: x1 x2 x9 x5 x6 x3 x1 y1 y2 y5 y6 y7 y4 y1 x1 x3 x6 x7 x8 x4 x1 y1 y3 y9 y10 y7 y4 y1 x5 x9 x10 x8 x7 x6 x5 y5 y8 y9 y10 y7 y6 y5 Идентифицируем 1 цикл графа G(X,F) с одним из циклов графа H(Y,P), используя соответственно отображения F и P. Подстановки, входящие и не входящие в циклы, разделены вертикальной чертой: x1 x2 x9 x5 x6 x3 x4 x7 x8 x10 y1 y2 y5 y6 y7 y4y3 y10 y9 y8 (3) x1y1 →F(x1) = {x2, x3, x4 },P(y1) ={y2,y3,y4}⇒x2y2, x3y4 входят в подстановку (4.3),а x4y3 добавляем к ней x2y2 → F(x2) = {x1, x9},P(y2) ={y1,y5}→x1y1,x9y5 входят в подстановку(3) x5y6 →F(x5) = {x9, x6},P(y6) ={y5,y7}→x9y5, x6y7 входят в подстановку(3)x6y7→F(x6) = {x3, x5, x7 },P(y1) ={y4,y6,y10}→ x3y4, x5y6 входят в подстановку (3)а x7y10 добавляем к ней x3y4→F(x3) = {x1, x6},P(y4) ={y1,y7}→ x1y1, x6y7 входят в подстановку (3) x4y3→F(x4) = {x1, x8},P(y3) ={y1,y9}→ x1y1 входят в подстановку (3),а x8y9 добавляем к ней x7y10 →F(x7) = {x6, x8},P(y10) ={y7,y9}→ x6y7, x8y9 входят в подстановку (3) x8y9→F(x8) = {x4, x7, x10 },P(y9) ={y3,y8,y10}→x4y3, x7y10 входят в подстановку (3),а x10y8 добавляем к ней. Окончательно имеем подстановку: x1y1, x2y2,x3y4, x4y3, x5y6, x6y7, x7y10, x8y9, x9y5, x10y8, которая удовлетворяет условию сохранеия смежности. Рассмотрим подстановку по 2-ым циклам: x1 x3 x6 x7 x8 x4 x2 x5 x10 x9 y1 y2 y5 y6 y7 y4y2 y8 y6 y5 (4) x1y1 →F(x1) = {x2, x3, x4 },P(y1) ={y2,y3,y4}→x3y3, x4y4 входят в подстановку (4) x2y2, добавляем к ней x3y3 →F(x3) = {x6},P(y3) ={y9}→ x6y9 входит в подстановку (4) x6y9→F(x6) = {x3, x5,x7},P(y9) ={y3,y8,y10}→x3y3, x7y10 входят в подстановку (4) , x5y8 добавляем к ней x7y10 →F(x7) = {x6, x8 },P(y10) ={y7,y9}→ x6y9, x8y7 входят в подстановку (4) x8y7 →F(x8) = {x4, x7,x10},P(y7) ={y4,y6,y10}→x4y4, x7y10 входят в подстановку (4), а x10y6 добавляем к ней x4y4→F(x4) = {x1, x8},P(y4) ={y1,y5}→x1y1 , x8y9 входят в подстановку (4) x2y2→F(x2) = {x9, x1},P(y2) ={y1,y5}→x1y1, x9y5 входят в подстановку (4) x5y8→F(x5) = {x6, x9},P(y8) ={y5,y9}→x6y9, x9y5 входят в подстановку (4) x10y6 →F(x10) = {x8, x9},P(y6) ={y5,y7}→ x8y7, x9y5 входят в подстановку (4) окончательно имеем еще одну подстановку x1y1, x2y2,x3y3, x4y4, x5y8, x6y9, x7y10, x8y7, x9y5, x10y6
Графы изоморфны, в чем можно убедиться по идентичности матриц смежности. Аналогичным образом можно получить подстановку и для третьих циклов: окончательно имеем подстановку x1y1, x2y2,x3y4, x4y3, x5y6, x6y7, x7y10, x8y9, x9y5, x10y8 Это подстановка также сохраняет отношение смежности, следовательно, графы G(X,F) и H(Y,P) изоморфны. Таким образом, все три подстановки установлены с первого раза, что как минимум иллюстрирует возможность использования дополнительной информации о порядке следования вершин в циклах для распознавания изоморфности. Результат решения примера показал, во-первых, работоспособность и сходимость алгоритма и, во-вторых, что существует несколько таких подстановок, свидетельствующих о наличии группы автоморфизмов. Наличие группы автоморфизмов, характеризующих симметрию графов, видно из их графического изображения. Так, граф G(X,F) можно вращать по и против часовой стрелки относительно неподвижной вершины x6 на 120˚ и 240˚ , граф H(Y,P) поворачивать на ±180˚ относительно неподвижной оси y1 y3 y6 y9. Кроме того, можно осуществлять повороты на 120˚ и 240˚ вершин циклов x1 x2 x9 x5 x6 x3 x1; x1 x3 x6 x7 x8 x4 x1; и x6 x7 x8 x10 x9 x5 x6 и поскольку графы G(X,F) и H(Y,P) изоморфны, то аналогичные автоморфизмы существуют для обоих графов. Понятие автоморфизма нам понадобиться при установлении зависимости между типовыми и конкретными структурами. Алгоритм работает эффективно при достаточно больших значениях t, когда обнаружено и распознано большинство вершин. При малых значениях t, а следовательно и Pi(t) чаще наблюдаются «осколки» разыгрываемого графа и алгоритм работает неэффективно. Более эффективным в таких условиях является алгоритм, приведённый ниже. Суть алгоритма заключается в том, что кроме стандартной процедуры сравнения полустепеней исхода и захода конкретной вершины используется информация о характеристиках вершин, смежных с исследуемой для каждого входящего и исходящего ребра, что существенно сокращает число операций при переборе, а следовательно и ускоряет решение всей задачи. Это объясняется тем, что процедура распознавания изоморфного вложения используется на каждом шаге розыгрыша N* раз. В блок-схеме алгоритмапринимается, что матрицы A, B и C являются соответственно матрицами смежности эталонного графа, исследуемого графа (меньшей или равной размерности относительно эталонного) и матрицей возможных подстановок. Переменная Mirage «закрывает» ненужные варианты подстановок. Ниже дано краткое описание назначения процедур блок-схемы. Prioritet - процедура, нахождения строки с наименьшим числом возможных подстановок, присвоения этой строке текущего приоритета, изменение переменной Mirage; (под приоритетом здесь понимается целое число, присваиваемое строке матрицы. Изначально все строки имеют нулевой приоритет. Строка с наибольшим приоритетом является активной, т.е. все корректировки матрицы производятся относительно этой строки). Prov_0_str - процедура проверки наличия нулевых строк в матрице С, если такие строки есть то Pr_0=1, иначе Pr_0=0, а также заполнение массива C_Kol (Pr_0 -признак “нулевой” строки, C_Kol - копия столбца “количество возможных подстановок”); Prov_1_str - процедура проверки того, что все элементы массива равны единицам, т.е. выполняется условие, когда графы изоморфны; Mirage1 - процедура получения координат активной ячейки, “обнуления” активных столбца и строки; Mirage2 - процедура нахождения строки с единственным элементом ‘1’, после нахождения – обнуление столбца, если последнее производилось то PrMir:=1 (PrMir - признак того, что матрица С корректировалась процедурой Mirage2); Mirage3 - процедура корректировки таблицы по правилу: Если C[i,j]=’1’ and B[i,FocB]=’1’ and A[i,FocA]’1’ то C[i,j]=Mirage Если C[i,j]=’1’ and B[FocB,j]=’1’ and A[FocA,j]’1’ то C[i,j]=Mirage ExitToHome - процедура возврата (приведения матрицы С к виду, предшествующему последней серии преобразований); ZapolnMatrCM - процедура заполнения модифицированной матрицы вариантами решения; ProvEnd - процедура окончательной проверки изоморфного вложения графов. Далее приведено текстуальное описание работы блок-схемы алгоритма на примере решения задачи нахождения изоморфного вложения. Матрицы смежности графов А и В, а также матрица возможных подстановок С представлены на рис.5. Используя метод полного перебора вариантов подстановок для этого примера необходимо проверить 576 вариантов. Разработанный алгоритм позволяет найти решение этой задачи уже на третьем цикле процедуры.  Рис.5 Пример графа-эталона (А) и графа-реализации (В). Матрица смежности графа А
Матрица смежности графа В
Матрица возможных подстановок (С)
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||