Теория процессов
 Скачать 1.62 Mb.
|
|
(t [j] = 1) ? timeout ! j t [j] := 0 (8.33) Правую стрелку в этой диаграмме следует понимать как со- кращённое обозначение для совокупности из n переходов, метка каждого из которых получается заменой в метке этой стрелки символа j на любое из значений из множества Z n Отметим, что в данном процессе наряду с операторами за- пуска таймеров и посылки ими сигнала тайм-аута присутствует также оператор stop ? i, выполнение которого досрочно заверша- ет работу соответствующего таймера. ПСО с возвратом имеет следующие особенности. • Когда заканчивается лимит времени ожидания подтвер- ждения какого-либо пакета, агент начинает передавать по- вторно все пакеты из своего окна. • Когда поступает подтверждение получения какого-либо па- кета, все предыдущие пакеты в окне тоже считаются под- твержденными (даже если их подтверждения не дошли). Каждый кадр f , пересылаемый каким-либо из агентов этого протокола, содержит пакет x и два целых числа: s и r, где 280 • s – номер, сопоставленный пакету x (который по определе- нию равен номеру кадра f ), • r – номер последнего полученного неискажённого кадра. Для формирования кадров используется функция ϕ. Для из- влечения пакетов и номеров из кадров используются функции info, seq и ack, обладающие следующими свойствами: info(ϕ(x, s, r)) = x seq(ϕ(x, s, r)) = s ack (ϕ(x, s, r)) = r Описание процесса, представляющего поведение агента дан- ного ПСО, мы даём в блок-схемном виде, по которому несложно построить блок–схему этого процесса. В данном описании мы используем следующие обозначения. • Символы + n и − n обозначают сложение и вычитание по мо- дулю n. • Символ r обозначает переменную с множеством значений Z n . Значение переменной r равно номеру ожидаемого кад- ра. Агент посылает своему СУ пакет, извлечённый только из такого кадра f , у которого номер seq(f ) совпадает со зна- чением этой переменной r. Пакеты из кадров с другими значениями seq(f ) игнориру- ются, у таких кадров учитывается лишь компонента ack(f ). • Знакосочетание send является сокращённым обозначением следующей группы операторов: send = C ! ϕ(x[s], s, r − n 1) start ! s s := s + n 1 • Знакосочетание between(a, b, c) является сокращённым обо- значением формулы a ≤ b < c ∨ c < a ≤ b ∨ b < c < a (8.34) 281 • Знакосочетание enable := (w < n−1) является сокращённой записью оператора if (w < n − 1) then enable := 1 else enable := 0 Процесс, представляющий поведение агента данного ПСО, имеет следующий вид: ' & $ % start enable = 1 w, b, s, r = 0 timeout ? i s := b i := 1 enable = 1 In ? x[s] send w := w + 1 send i := i + 1 i ≤ w Out ! info(f ) r := r + n 1 w := w − 1 stop ! b b := b + n 1 between (b, ack(f ), s) seq(f ) = r f = ∗ C ? f enable := (w < n − 1) - ? ? ? ? - - 6 ? ? ? ? - - - + − − − − + + + + Читателю предлагается самостоятельно • определить процесс “канал” для этого протокола (канал может содержать несколько кадров, которые могут не только искажаться и пропадать, но ещё и переупорядо- чиваться) • определить спецификацию Spec этого протокола • доказать соответствие этого протокола спецификации Spec • исследовать этот протокол на наличие аномальных эффек- тов, аналогичных эффекту (8.32), который был изложен в параграфе 8.4.7 282 (если аномальные эффекты присутствуют, то модифициро- вать этот протокол так, чтобы таких эффектов не было, и доказать корректность модифицированного протокола) В заключение отметим, что данный ПСО неэффективен при большом количестве ошибок при передаче кадров. 8.4.10 Протокол скользящего окна с выбороч- ным повтором Второй ПСО отличается от предыдущего тем, что у агента этого ПСО имеется не одно, а два окна. 1. Первое окно имеет те же функции, которые имеет окно первого ПСО (данное окно называется посылающим ок- ном). Максимальный размер посылающего окна равен m def = n/2, где число n имеет тот же статус, который описан в парагра- фе 8.4.8 (в частности, номера кадров являются элементами Z n ). 2. Второе окно (называемое принимающим окном) предна- значено для размещения пакетов, поступивших от другого агента, которые пока не могут быть переданы СУ, потому что ещё не пришли некоторые пакеты с меньшими номера- ми. (агент-получатель должен передавать принятые пакеты сво- ему СУ в том же самом порядке, в котором они поступили к агенту-отправителю от его СУ) Принимающее окно имеет фиксированный размер m = n/2. Каждый кадр f , пересылаемый каким-либо из агентов этого протокола, содержит 4 компоненты: 1. k – вид кадра, данная компонента может принимать одно из трёх значе- ний: • data (информационный кадр) 283 • ack (кадр, содержащий лишь подтверждение) • nak (кадр, содержащий запрос на повторную переда- чу) 2. x – пакет 3. s – номер этого кадра 4. r – номер последнего полученного неискажённого кадра. Если значение первой компоненты кадра равно ack или nak, то вторая и третья компоненты этого кадра имеют фиктивный характер. Для формирования кадров используется функция ϕ. Для извлечения компонентов из кадров используются функ- ции kind, info, seq и ack, обладающие следующими свойствами: kind (ϕ(k, x, s, r)) = k info(ϕ(k, x, s, r)) = x seq(ϕ(k, x, s, r)) = s ack (ϕ(k, x, s, r)) = r Процесс, описывающий поведение агента данного ПСО, имеет следующие переменные. 1. Массивы x[m] и y[m], предназначенные для размещения по- сылающего окна и принимающего окна соответственно. 2. Переменные enable, b, s, w, имеющие • те же множества значений, и • тот же смысл которые они имеют в предыдущем протоколе. 3. Переменные, связанные с принимающим окном: • r – нижняя граница принимающего окна • u – верхняя граница принимающего окна 284 значения переменных r и u принадлежат множеству Z n Если в принимающем окне присутствует пакет, номер ко- торого равным нижней границе принимающего окна (r), то агент • передаёт этот пакет своему СУ, и • увеличивает на 1 (по модулю n) значения r и u. 4. Булевский массив arrived[m], компоненты которого имеют следующий смысл: arrived[i] = 1 тогда и только тогда, ко- гда в i–й компоненте принимающего окна содержится па- кет, пока ещё не переданный СУ. 5. Булева переменная no_nak, используемая в следующих це- лях. Если агент получает • искажённый кадр, или • кадр, номер которого отличен от нижней границы при- нимающего окна (r) то он посылает своему коллеге запрос на повторную пере- дачу кадра, номер которого равен r. Данный запрос называется NAK (Negative Acknowledgement). Булева переменная no_nak используется для того, чтобы избежать нескольких запросов на повторную передачу од- ного и того же кадра: эта переменная имеет значение 1, если NAK для кадра с номером r еще не был послан. Когда агент получает неискажённый кадр f вида data, он выполняет следующие действия. • Если номер seq(f ) попадает в прнинимающее окно, т.е. ис- тинна формула between(r, seq(f ), u) где предикатный символ between имеет тот же смысл, что и в предыдущем протоколе (см. (8.34)), то агент 285 – извлекает из этого кадра пакет, и – помещает этот пакет в своё принимающее окно. • Если условие из предыдущего пункта не выполнено (т.е. номер seq(f ) кадра f не попал в принимающее окно), то – пакет в таком кадре игнорируется, и – у такого кадра учитывается лишь компонента ack(f ). В данном протоколе участвуют следующие таймеры. 1. Массив из m таймеров, поведение которых представляет- ся процессом T imers (см. (8.33), с заменой n на m), каж- дый таймер из этого массива предназначен для оповещения агента о том, что • время ожидания подтверждения пакета с соответству- ющим номером из посылающего окна закончилось, и • необходимо послать кадр с этим пакетом ещё раз 2. Дополнительный таймер, поведение которого представля- ется следующим процессом: Init = (t = 0) 6 stop_ack_timer ? t := 0 - start_ack_timer ? t := 1 (t = 1) ? ack_timeout ! t := 0 Этот таймер используется со следующей целью. Посылка агентом подтверждений кадров, поступивших от другого агента, может производиться двумя способами: (a) подтверждение посылается в составе информационно- го кадра (т.е. кадра вида data), или (b) подтверждение посылается отдельным кадром вида ack. 286 Когда агенту необходимо послать такое подтверждение a, он • включает вспомогательный таймер (т.е. выполняет дей- ствие start_ack_timer !), • если до сигнала тайм-аута от вспомогательного тайме- ра агент получил новый пакет от своего СУ, он – формирует кадр вида data с этим пакетом, – включает в этот кадр подтверждение a как ком- поненту ack этого кадра, и – посылает этот кадр своему коллеге • если после истечения работы вспомогательного тайме- ра (т.е. после получения от него сигнала ack_timeout) агент так и не получил новый пакет от своего СУ, он посылает подтверждение a отдельным кадром вида ack. Описание процесса, представляющего поведение агента дан- ного ПСО, мы даём в блок-схемном виде, по которому несложно построить блок–схему этого процесса. В данном описании мы используем следующие обозначения и соглашения. 1. Если i – целое число, то знакосочетание i%m обозначает остаток от деления i на m. 2. Если • mass – имя массива из m компонентов (т.е. x, y, arrived, и т.д.), и • i – целое число, то знакосочетание mass[i] следует понимать как mass[i%m]. 3. Знакосочетание вида send(kind, i) является сокращённым обозначением следующей группы операторов: send(kind, i) = C ! ϕ(kind, x[i], i, r − n 1) if (kind = nak) then no_nak := 0 if (kind = data) then start ! (i%m) stop_ack_timer ! 287 4. Знакосочетания between(a, b, c) и enable := (w < m) имеют тот же смысл, что и в описании предыдущего про- токола. 5. Если в каком-либо овале присутствуют не одна, а несколько формул, то мы предполагаем, что эти формулы связаны символом конъюнкции. 6. В целях экономии места некоторые выражения вида f (e 1 , . . . , e n ) написаны в две строки (в первой строке – f , а во второй – список (e 1 , . . . , e n )). Процесс, представляющий поведение агента данного ПСО, имеет следующий вид: ' & $ % start enable = 1 w, b, s, r = 0 u = m = n/2 no_nak = 1 arrived = (0 . . . 0) timeout ? i send(data, i) ? enable = 1 In ? x [s] send(data, s) s := s + n 1 w := w + 1 ack_timeout ? send(ack, 0) @ @ @ @ R ? f = ∗ ? f rame processing ? no_nak = 1 send(nak, 0) - 6 ? C ? f enable := (w < m) ? ? - - - ? ? + + − − + Фрагмент frame processing в этой диаграмме выглядит следу- ющим образом. 288 ? ? - ? 6 ? ? 6 6 ? @ @ @ @ @ R @ @ @ @ R - ? ? - + − + − + − − + + − + − kind(f ) = data ' & $ % kind(f ) = nak between (b, ack(f ) + n 1, s) ' & $ % between (b, ack(f ), s) send (data, ack(f ) + n 1) w := w − 1 stop ! (b%m) b := b + n 1 seq(f ) 6= r no_nak = 1 send(nak, 0) start_ack_timer ! ' & $ % between (r, seq(f ), u) arrived [seq(f )] = 0 arrived [seq(f )] := 1 y [seq(f )] := info(f ) arrived [r] = 1 Out ! y [r] no_nak := 1 arrived [r] := 0 r := r + n 1 u := u + n 1 start_ack_timer ! Читателю предлагается самостоятельно исследовать для дан- ного протокола все вопросы, которые были перечислены в конце предыдущего параграфа. 8.5 Криптографические протоколы Важным примером процессов с передачей сообщений являются криптографические протоколы. 8.5.1 Понятие криптографического протокола Криптографический протокол (КП) – это распределённый алгоритм (т.е. совокупность нескольких взаимодействующих про- 289 цессов), предназначенный для безопасной передачи, обработки и хранения информации или материальных объектов в небезопас- ной среде. В работе КП принимают участие несколько агентов, кото- рыми могут быть люди, вычислительные процессы, компьюте- ры, сети связи, базы данных, банковские карточки, банкоматы, и т.д. Каждый из агентов КП функционирует в соответствии с неко- торым последовательным алгоритмом. Действия, исполняемые агентами, могут иметь следующий вид. • Посылка сообщения другому агенту или группе агентов. В качестве сообщения в КП может выступать как информа- ционный, так и материальный объект. Например это может быть набор банкнот или товар. • Приём сообщения от другого агента. • Внутреннее действие, которое заключается в преобразо- вании агентом имеющихся у него информационных и мате- риальных объектов. Главное отличие КП от остальных распределённых алгорит- мов заключается в том, что • при функционировании КП допускается высокая вероят- ность некоторых угроз безопасности сообщений, передава- емых агентами этого КП, и • КП должен содержать механизмы противодействия этим угрозам. Под угрозой безопасности сообщения понимается возмож- ность выполнения с этим сообщением какой-либо из следующих операций. 1. Нарушение конфиденциальности сообщения, т.е., напри- мер, перехват этого сообщения (т.е. получение его копии), и 290 • полное или частичное ознакомление с содержанием это- го сообщения субъектами, не имеющими для этого со- ответствующих полномочий, или • извлечение из сообщения новой информации, напри- мер, – извлечение из шифртекстов фрагмента криптогра- фического ключа, используемого при создании этих шифртекстов, или – извлечение из сообщений о покупках какого-либо лица предположений о его финансовом положении или о его предпочтениях. 2. Нарушение целостности сообщения, т.е., например, иска- жение передаваемого текста в процессе передачи. 3. Кража сообщения (например, кража денег или товара в процессе их доставки от одного агента другому агенту). 4. Подмена сообщения, т.е. • изъятие сообщения, которое агент A послал агенту B, и • посылка агенту B другого сообщения вместо изъятого. Ниже под угрозами безопасности мы будем понимать угрозы безопасности сообщений, передаваемых между агентами какого- либо КП. Угрозы безопасности могут быть внешними и внутренними. 1. Внешние угрозы связаны с вторжением в работу агентов КП других агентов, не входящих в этот КП (их называют противниками). Противники делятся на следующие два класса. (a) Пассивные противники, которые могут лишь пере- хватывать сообщения, пересылаемые другими агента- ми, и анализировать их. (b) Активные противники, которые могут 291 • перехватывать сообщения, пересылаемые другими агентами, и анализировать их • модифицировать или удалять пересылаемые сооб- щения • создавать новые сообщения и посылать их другим агентам • и т.д. 2. Внутренние угрозы связаны с наличием среди агентов КП нечестных агентов (их называют мошенниками), ко- торые могут • неправильно выполнять действия, которые им полага- ется выполнять в ходе работы КП, • выдавать себя за других агентов, • объединятьтся в коалиции и совместно использовать сообщения, получаемые ими в ходе работы КП, в зло- намеренных целях • и т.д. Свойства безопасности КП представляют собой описание видов угроз безопасности, которым может быть оказано проти- водействие во время функционирования этого КП. Наиболее надёжными считаются такие КП, для которых име- ется математическое доказательство утверждения о том, что реа- лизованные в этих КП механизмы противодействия угрозам без- опасности действительно выполняют поставленные перед ними задачи. 8.5.2 Шифрование сообщений Для противодействия угрозам нарушения конфиденциальности некоторые из пересылаемых сообщений могут передаваться от одних агентов КП другим агентам в зашифрованном виде. Шифрование сообщения m представляет собой применение некоторого алгоритма к паре (K, m), где K – объект, называе- мый ключом шифрования. Результат применения алгоритма шифрования к паре (K, m) обозначается знакосочетанием K(m). 292 Операция извлечения исходного сообщения из зашифрован- ного сообщения m 0 называется дешифрованием. Данная опе- рация тоже представляет собой применение некоторого алгорит- ма к паре (K 0 , m 0 ), где K 0 – объект, называемый ключом де- шифрования. Результат применения алгоритма дешифрования к паре (K 0 , m 0 ) обозначается знакосочетанием K 0 (m 0 ). Ключи шиф- рования K и дешифрования K 0 должны быть связаны соотноше- нием для каждого сообщения m K 0 (K(m)) = m (8.35) Если символ K обозначает некоторый ключ шифрования, то знакосочетание K −1 обозначает ключ дешифрования K 0 , удовле- творяющий условию (8.35). Системой шифрования (СШ) называется пара, состоя- щая из алгоритма шифрования и алгоритма дешифрования. Ис- пользуемые в настоящее время на практике СШ подразделяются на два класса: • симметричные СШ, в которых каждый ключ шифрова- ния K совпадает с соответствующим ему ключом дешиф- рования K −1 , и • СШ с открытым ключом, в которых ключи шифрова- ния и дешифрования сопоставлены конкретным агентам: если символ A обозначает некоторого агента, использую- щего СШ с открытым ключом, то знакосочетания K |