Алгоритмы условного диагностирования вычислительных устройств

7. Конфиденциальность

Заголовок конфиденциальности (ESP-Encapsulating Security Payload) (рис.5) позволяет шифровать совокупность пакетов или их транспортные части. Так же как и аутентификация, конфиденциальность предполагает наличие ассоциации безопасности, включающей среди прочего ключ шифрования и индекс параметров безопасности.

Конфиденциальность имеет два режима:

— транспортный «от края до края», где информация протокола верхнего уровня (в основном транспортного протокола), включая его заголовок, шифруется;

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

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

Стандартным алгоритмом для шифрования является DES (Data Encryption Standard) [FIPS-46] и тройной DES в режиме CBC (Cipher Block Chaining) [FIPS-81]. Также предлагаются другие алгоритмы, такие как IDEA, RC5 или CAST-128.

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

8. Управление ассоциациями безопасности и ключами

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

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

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

— ISAKMP (Internet Security Association and Key Management Protocol) — доминирующее предложение на сегодняшний день. Оно определяет протокол для АБ, обеспечивающий создание, модификацию и распространение ключей. Обеспечивает также аутентификацию партнеров;

— Oakley—протокол аутентификации партнеров и управления ключами шифрования. Oakley базируется на алгоритме обмена ключей Диффи-Хеллмана;

— SKIP (Simple Key-Management for Internet Protocols) — позволяет аутентифицировать ключи. Не управляет базами данных АБ, но систематически отправляет необходимые криптографические данные в заголовке, предшествующем заголовкам AH и ESP;

— Photoris — протокол, реализующий аутентификацию и обмен публичными ключами.

Среди всех протоколов управления ключами и/ или АБ только для ISAKMP, Oakley и Photoris компрометация долговременного ключа не компрометирует предварительно обменяные ключи и, следовательно, конфиденциальность проведенного сеанса связи.

Литература: 1. Scott O. Bradner, Allison Mankin. IPng. Internet Protocol Next Generation. Addison-Wesley, Reading, Massachusetts. 1995. 307 p. 2. Huitema C. IPv6: The New Internet Protocol. Prentice Hall, Englewood Cliffs, New Jersey. 1996. 188 p. 3. Stephen A. Thomas. IPv6 and the TCP/IP Protocols. Wiley Computer Publishing. 1996. 481 p. 4. Gisele Cizault. IPv6: Theorie et pratique. O’Reilly, Paris. 1998. 285 p.

Поступила в редколлегию 09.10.98 Рецензент: д-р техн. наук Долгов В.И.

Фрадков Сергей Александрович, аспирант кафедры АПВТ ХТУРЭ. Научные интересы: сетевые технологии, защита информации, техническая диагностика. Увлечения: программирование, путешествия, иностранные языки. Адрес: Украина, 310726, Харьков, пр.Ленина, 14, тел. +38 (0572) 40-93-26.

0 8 16 24 31

Индекс параметров безопасности Синхронизирующие данные

Зашифрованные данные

Рис. 5. Формат заголовка конфиденциальности

УДК 681.325

АЛГОРИТМЫ УСЛОВНОГО ДИАГНОСТИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВ

ХАХАНОВ В.И., СЫСЕНКО И.Ю., ПОБЕЖЕНКО В.В, МОНЖАРЕНКО И.В.

Предлагаются алгоритмы условного диагностирования введенного класса макродефектов вычислительных устройств с использованием методов обратного прослеживания и половинного деления на основе выполнения

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

1. Алгоритм обратного прослеживания

Представленный ниже алгоритм условного диагностирования, не дифференцируемый строго на процедуры контроля и поиска дефектов, описывается обобщенным уравнением диагноза:

F*(F,T,D) | ВД=М (g(T,F)ng*(T,F,Di))=0, где g, g*— эталонная и экспериментальная реакции наблюдаемых линий цифрового устройства (ЦУ); F,

РИ, 1998, № 3

87

T, D — функционал, проверяющий тест, наперед заданные дефекты.

Использование сигнатурного анализа [1,2] определяет элементарную проверку Pj=g*(T,F,Dj) как получение сжатой реакции при подаче проверяющего теста T на выбранном наблюдаемом контакте i схемы. Проверка Pi считается положительной, если в точке контроля i эталонная сигнатура, вычисленная при отсутствии неисправностей в схеме, равна экспериментальной: SM = SR . Если же SM * SR, проверка Pi отрицательная. В общем случае идентификация проверки определяется выражением

P+ ^ [g * (T, F, Di) о g(T, F) = g(T, F)]; P-^[g * (T,F,Di) о g(T,F) = 0].

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

Ds = |{Do,D+I ^ Pi = P+;

[d-^ Pi = P- ,

где DS = D0 u D; D+ u D- = D; D+ о D-=0; D0 — исправное техническое состояние; D — предполагаемая область существования дефектов; D+ (D-) — область неисправностей, определяемая положительной (отрицательной) проверкой Р+ (Р—).

Поэтому алгоритм диагностирования методом обратного прослеживания является условным и зон-довым, он использует сигнатурный логический анализатор. Длительность и стоимость выполнения условного диагностического эксперимента на порядок выше, чем у безусловного. В отличие от метода половинного деления [1,3] он ориентирован на поиск не только логических дефектов, но и на обнаружение разрывов линий. Стратегия обратного прослеживания неисправности по структуре объекта, связанная с введенным классом макродефектов, изначально была ориентирована на последовательное выполнение проверок линий функциональнологического подграфа [4], в целях восстановления работоспособности цифрового модуля на стадии производства или эксплуатации при использовании в качестве средства диагностирования "ложа из гвоздей" или автоматического зонда [5].

Диагностическая модель устройства представлена графом функционально-гальванических связей контактов микросхем и ЦУ:

G = {LijeL, FktreF|,

где Lij — (дуга) гальваническое отношение одного потенциала между контактами различных конструктивов или примитивов; Ftr — (дуга или дуги Fktr k-го ПЭ) функциональное отношение между входной t и выходной r переменной. Для построения алгоритма диагностирования необходимы: полный проверяющий тест относительно одиночных константных неисправностей T, эталонные сигнатуры S^. всех внешних контактов микросхем и ТЭЗа, граф функционально-гальванических связей FG цифрового модуля:

W = {G, T, Sm|.

Чтобы приблизить модели неисправностей к реальным, введем следующие типы состояний объекта:

DS={Db Db ^ ^ ^ D51, где D0 — исправное состояние объекта, определяется совпадением SM = SR по всем выходным контактам устройства:

Do ^ [g(T,F) о g*(T,F,Di) = g(T,F)];

D1 — отсутствие гальванической связи между контактами различных микросхем:

Di ^ [Sm (Li) = SR(Li) & Sm (Lj) * Sr(Lj)];

D2 — неисправность на выходе k-го элемента или внутри его:

D2 ^ {Vt[SM (Fkt) = SR(Fkt)] & 3r[SM (Fkr) * SR(Fkr)]|; D3 — отсутствие связи между входом и шиной константы =0,=1:

D3 ^ [Sm ({=0, = 1|) = Sr({=0, =1|) &

& Sm (Lj = {=0, =1|) * SR(Lj)];

D4 — неисправность внешнего входного контакта цифрового объекта:

D4 ^ [Sm (Li) * Sr(L) & Sm (Lj) * SR(Lj)];

D5 — неисправность выходов, объединенных в монтажную логику:

D5 ^ {Vi[SM (Li) * SR(Li)] & [Sm (Lj) * SR(Lj)]|. Построим алгоритм поиска дефектов методом обратного прослеживания для схемы, изображенной на рисунке.

28

Априорно все доступные контакты идентифицируются порядковыми номерами или топологическими идентификаторами <координата микросхемы, номер ножки>. Последовательность диагностирования контактов на топологии схемы определяется двумя направлениями: справа-налево — при отрицательной проверке; снизу-вверх — при положительной. (Направления могут быть и другими.) Такая стратегия задает в качестве очередной точки контроля при отрицательной проверке P—i на выходе элемента его первый нижний входной контакт. При фиксации положительного результата P+i на входном контакте примитива очередная точка контроля задается расположенной выше входной ножкой. Если в последнем случае проверка отрицательная, очередная точка контроля определяется выходным

88

РИ, 1998, № 3

контактом элемента, связанного с рассматриваемым входом. Если в диагностическом эксперименте рассматривается очередная точка контроля Pj, не являющаяся выходным контактом схемы, то все предыдущие проверки линий-преемников имели отрицательный результат.

Для предложенного примера построенный алгоритм диагностирования представлен в таблице.

чивается областью G- (G-), получаемой пересечением (объединением) подсхем Gj, относящихся к тем наблюдаемым выходам LjY, на которых зафиксированы отрицательные результаты проверки [6]:

G- = V] {nGj ^ [Sm

j=1,m

]};

Pi 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17

Pi+ 30 29 28 D0 D1 D1 D1 23 D2 21 D2 19 D2 D1 D1

Pi- 27 26 25 15 24 22 20 18 17 5 16 16 5 14 14

Sign 21FE 31FE 41FE 51FE 21FE 31FE 41FE 11F4 1133 11F1 1110 1110 11F1 11F4 1133

Pi 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1

Pi+ D1 D1 13 12 D2 10 9 D2 D1 D1 D1 D1 D1 D1 D1

Pi- 11 11 8 7 6 3 2 1 D4 D4 D4 D4 D4 D4 D4

Sign 1110 51FE 115E 110E 133E 11HE 11PE 13FE 115E 110E 133E 11F1 11HE 11PE 13FE

Первой точкой контроля является контакт 31. Он имеет эталонную сигнатуру Sm=21FE. (Все другие контакты также имеют собственные сигнатуры.) Результат сравнения эталонной и экспериментальной сигнатур формирует точки контроля на следующем шаге диагностирования при двух альтернативах: P+ — проверка положительная; P- — проверка отрицательная.

Состояние D0 фиксируется, если все выходы дают положительную проверку; D1 — на гальванической связи зафиксирована положительная проверка при отрицательной предыдущей; D2 — при отрицательной проверке на выходе все входы имеют положительный результат сравнения сигнатур; D3 — отрицательная проверка на входе, связанном с шинами =0, =1; D4 — отрицательная проверка на внешнем входе цифрового устройства.

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

Диагностирование (см. таблицу) продемонстрируем на примере разрыва связи между контактами 8 и 14. Проверка начальной координаты 31 дает отрицательный результат, что определяет очередной точкой контроля контакт 27. Его проверка имеет отрицательное значение, следовательно, переходим на координату 24. Далее фиксируем отрицательные проверки на линиях 18, 14, после чего на контакте 8 получаем положительный результат. Вывод: техническое состояние Di — нет связи между контактами 8 и 14.

1.1. Процедура структурного анализа

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

j=1,m

]}),

где Gj — подграф внутренних точек контроля схемы, являющихся предшественниками для линии LjY; m— число внешних выходов схемы. Ограничение наличия в схеме одиночного дефекта является достаточно сильным, поэтому должны существовать весомые аргументы, чтобы его принять.

Для теста, активизирующего проверку каждого одиночного дефекта на всех выходах ЦУ, подозреваемая область при наличии одиночного (кратного) дефекта определяется разностью между подграфами с отрицательными и положительными по выходам результатами испытаний:

G = G- \Vj {uGj ^ [Sm

]=1,т]Ь

j=1,m

]}).

Поскольку проектирование теста, активизирующего каждый из дефектов до всех наблюдаемых выходов, задача дорогостоящая, на практике для уменьшения подозреваемой области следует пользоваться выражениями (1) или (2).

Пример. Пусть существует одиночный дефект D1(10,2), который при диагностировании внешних выходов проявился на линиях 28 и 30.

В случае разрыва связи между линиями 2 и 10 (см. рисунок) последовательность выполнения проверок по таблице без структурного анализа имеет стоимость

(Р 30, P 26, P^ P 2Ъ P ^ Р+1Ъ P ^, P+2) ^

D1(10,2).

С использованием структурного анализа подозреваемая область определяется подграфом линий:

G = G28 —G30 = {Lb L^ ^ ^ L11}.

Стоимость диагностирования, равная числу элемен -тарных проверок для установления диагноза на подграфе G, определяется последовательностью

(P-11, P-10, P+2) ^ D1(10,2), что в 2,6 раза меньше базового алгоритма обратного прослеживания без структурного моделирования результатов сравнения эталонных и экспериментальных сигнатур по наблюдаемым выходам схемы.

РИ, 1998, № 3

89

2. Алгоритм половинного деления

Для изложения стратегии половинного деления введем вектор моделирования неисправной области M = (Mi, M2, Mi, Mn), где n — общее число точек

контроля цифрового модуля. Подмножество наблюдаемых выходных контактов устройства обозначим

в виде MY с M, MY ф 0. Значение координаты вектора Mi є M формируется в соответствии с выражением

(Mi = 1) ^ [Sm (Li) ф Sr(L0 & Sm (LjY) ф Sr(Ljy)&

& LjY = f(Li)]; в противном случае — Mi = 0.

В результате диагностического эксперимента по наблюдаемым выходам формируется подмножество MY с M вектора моделирования:

MY

і ^ Sm(lY) ф Sr(lY); 0 ^ Sm(lY) = Sr(lY).

Для MY с M вычисляется подграф точек контроля

цифровой схемыМ' с М, неисправные сигнатуры которых могут сформировать определенное по (3) подмножество MY с M. Построение вектора моделирования неисправной области M для вычисленного подмножества MY с M с использованием графа цифровой схемы основано на следующих правилах.

2.1. Процедура структурного моделирования

1. Состояния наблюдаемых линий определяются в соответствии с выражением (1) и не могут быть модифицированы с помощью двух следующих правил (пункты 2 и 3).

2. Входные контакты примитива t подозреваются неисправными, если существует выходной дефектный контакт: (Vi(Mi(Xt) = 1) ^ (3i(Mi(Yt) = 1).

3. При различных технических состояниях (исправное и неисправное) входов одного потенциала разных примитивов t и fзначение линии разветвления подозревается дефектным: Mi = Mi(Xt) v Mi(Xf).

C учетом приведенных правил процедуры структурного моделирования и вычисленного подмножества MY с M алгоритм определения состояний невыходных координат вектора моделирования неисправной области M заключается в последовательной обработке примитивов ацикличной схемы методом обратного прослеживания от внешних выходных контактов схемы ко входным.

Для примера, представленного на рисунке, продемонстрируем выполнение процедуры структурного моделирования, исходя из условия, что

MY = {М28 = 1, М29 = 0, М30 = 1, М31 = 0}.

Результат моделирования на основе выполнения правил 2 и 3 дает вектор единичных переменных:

М = (1 2 3 5 9 10 11 15 16 21 22 26 28 30).

На подграфе G'(M), который представлен матрицей Q=||Qij||, организуется условный диагностический эксперимент с выбором точки контроля, делящей подозреваемую область пополам.

2.2. Процедура выбора контрольной точки

Чтобы изложить стратегии выбора очередного

контакта для зондирования схемы, количество единичных координат в вектор-строке предшественников для точки контроля i матрицы Q=||Qij|| достижи-

мостей обозначим через Ai = card(Qij)| j=1n ; в вектор-

столбце преемников — через Bi = card(Qji)| j =1n . Определим также множество точек контроля пред-

шественников и преемников в виде {Ai}, {Bi }. Тогда при стратегии выбора контрольной точки, делящей подозреваемую область пополам, необходимо максимизировать по параметру i выражение (Ai+Bi)/n (n— мерность матрицы Q, соответствующей подграфу G'(M)), которое показывает мощность делимого подграфа (Ai+Bi) по отношению к исходному G'(M). Кроме того, минимизация разности предшественников и преемников точки контроля i (Ai-Bi)/n показывает точность половинного деления структуры G'(M). В результате получаем функционал

f = MAX i [

= MAXi [(2/n)(Bi)].

Учитывая, что коэффициент (2/n) есть константа, ее можно исключить из выражения (4), считая при этом, что определение мощности Bi связано с выбором минимального значения из компонентов Ai, Bi:

f = MAX|i [MIN

Если существует несколько одинаковых значений функционалов f, то для однозначности выбирается точка контроля с меньшим индексом i.

В случае отрицательной проверки на линии Pk область неисправностей задается множеством предшественников {Ak} текущей матрицы достижимостей Q=||Qij||, а при положительной — разностью между исходным множеством и предшественниками для линии Pk:

({Ak}, ^ (SR ф SM);

lM

Пусть в схеме, представленной на рисунке, задана

M(Pk) =

неисправность типа "разрыв гальванической связи между контактами 2 и 10": D1(10,2). Выполним модельный условный диагностический эксперимент для поиска заданного дефекта при условии, что он сформировал неправильные реакции по наблюдаемым выходам, указанным в множестве MY. Выполним итеративную процедуру диагностирования на основе модификации матриц подграфов неисправных областей.

Вычисляя значения функционала f для каждой точки контроля исходной матрицы

1 2 3 5 9 10 11 15 16 21 22 26 28 30 1 1 2 1 3 1

5 1

9 1 1

10 1 1

Q = 11 1 1

15 1 1 1 1 1 1 1

16 1 1 1 1 1 1 1

21 1 1 1 1 1 1 1 1

22 1 1

26 1 1 1 1 1 1 1 1 1 1 1

28 1 1 1 1 1 1 1 1

30 1 1 1 1 1 1 1 1 1 1 1 1

90

РИ, 1998, № 3

заданной на векторе переменных М, который получен в результате выполнения процедуры структурного моделирования, определяем для всех строк и столбцов количество единичных координат:

Pi =

Лі 11112 2 27 7 8 2 11 8 12

Бі = 8 8 8 4 7 7 7 2 4 3 3 2 1 1

Критерию f удовлетворяет точка контроля P16. После выполнения элементарной проверки на линии P16 область подозреваемых дефектов определяется вектором переменных М(Р16) = (1 2 3 9 10 11 16), для которого подграф цифровой схемы задается уже в виде матрицы

1 2 3 9 10 11 16

1 1

2 1

3 1

9 1 1

10 1 1

11 1 1

16 1 1 1 1 1 1 1

Вычисление функционала f по данной матрице дает очередную точку контроля P9, в которой фиксируется положительная проверка, определяющая область существования дефекта в виде вектора линий: М(Р9) = М(Р16)\{Б9і =

= (1 2 3 9 10 11 16)\{1, 9} = (2 3 10 11 16).

Данной области неисправных линий соответствует матрица

2 3 10 11 16

2 1

3 1

10 1 1

11 1 1

16 1 1 1 1 1

по которой вычисление функционала f определяет следующей точку контроля P10. Элементарная проверка в P10 дает отрицательный результат, что позволяет вычислить по (6) область дефектов:

М(Рю) = {Лю}= (2, 10).

Очередная проверка на линии Р2 дает положительный результат, что является основанием для диагноза — неисправность D Д10,2).

Таким образом, процедура диагностирования наперед заданного дефекта Di(10,2) имеет стоимость, определяемую четырьмя проверками:

(P-^ P+9:> ^ P+2) ^ ^(10,2Д что только на одну больше, чем при структурном анализе, и это естественно, поскольку процедура структурного моделирования ориентирована на поиск как одиночных, так и кратных дефектов.

Предложенные алгоритмы реализуют условное диагностирование макродефектов на основе использования процедур: структурного анализа и структурного моделирования, а также методов: обратного прослеживания и половинного деления подозреваемой области, когда очередная точка контроля при анализе матрицы достижимостей вычисляется по критерию МЛХМВДа.

Выборочная статистика (на девяти схемах) числа зондирований для установления диагноза дефекта D і на одном из входов ЦУ дает среднюю оценку относительного уменьшения количества точек контроля, равную

q= еагб(АОПб)/еагб(АОПс)=2,75.

Литература: 1. Ярмолик В.Н. Контроль и диагностика цифровых узлов ЭВМ. Минск: Наука и техника, 1989. 234с. 2. Гордон Д, НадигX. Локализация неисправностей в микропроцессорных системах при помощи шестнадцатеричных ключевых кодов // Электроника. 1977. №5.C.23-33. 3. ПархоменкоП.П., СогомонянЕ.С. Основы технической диагностики (Оптимизация алгоритмов диагностирования, аппаратурные средства) / Под ред. П.П. Пархоменко. М.: Энергия, 1981. 320 с. 4. Кривуля Г.Ф., КизубВ.А., Коновалов В.Б., Хаханов В.И. Автоматизированная система диагностирования цифровых модулей // Электронное моделирование / 1987. №2. C.57-61.

5. Байда Н.П., Кузьмин И.В., Шпилевой В.Т. Микропроцессорные системы поэлементного диагностирования. М.: Радио и связь, 1987. 256 е. 6. ХахановВ.И. Техническая диагностика элементов и узлов персональных компьютеров. К.: ІЗМН. 1997. 308 с.

Поступила в редколлегию 12.10.98 Рецензент:д-р техн. наук Кривуля Г.Ф.

Хаханов Владимир Иванович, д-р техн. наук, профессор кафедры автоматизации проектирования вычислительной техники ХТУРЭ. Научные интересы: техническая диагностика вычислительных устройств, систем, сетей и программных продуктов. Увлечения: баскетбол, футбол, горные лыжи. Адрес: Украина, 310726, Харьков, пр. Ленина, 14, тел. 40-93-26.

Сысенко Ирина Юрьевна, студентка кафедры автоматизации проектирования вычислительной техники ХТУРЭ. Научные интересы: техническая диагностика вычислительных устройств. Увлечения: аэробика, музыка. Адрес: Украина, 310726, Харьков, пр. Ленина, 14, тел. 40-93-26.

Побеженко Владимир Викторович, студент кафедры автоматизации проектирования вычислительной техники ХТУРЭ. Научные интересы: техническая диагностика вычислительных устройств. Увлечения: книги, иностранные языки. Адрес: Украина, 310726, Харьков, пр. Ленина, 14, тел. 40-93-26.

Монжаренко Ирина Витальевна, канд. техн. наук, ассистент кафедры автоматизации проектирования вычислительной техники ХТУРЭ. Научные интересы: техническая диагностика вычислительных устройств. Адрес: Украина, 310726, Харьков, пр. Ленина, 14, тел. 40-93-26.

РИ, 1998, № 3

91