1. Анализ защищенности TCP. Атаки на TCP (пассивные и активные).
При данном типе атак злоумышленники никаким образом не обнаруживают себя и не вступают напрямую во взаимодействие с другими системами. Фактически все сводится к наблюдению за доступными данными или сессиями связи. Для осуществления подслушивания злоумышленнику необходимо иметь доступ к машине, расположенной на пути сетевого потока, который необходимо анализировать. Если крэкеру удастся получить достаточные права на этой машине, то с помощью специального программного обеспечения он сможет просматривать весь трафик, проходящий через заданный интерфейс.
2-ой вариант – злоумышленник получает доступ к машине, к-рая расположена в одном сегменте сети с системой, к-рой имеет доступ к сетевому потоку. Н-р, в сети "тонкий ethernet" сетевая карта м.б. переведена в режим, в к-ром она будет получать все пакеты, циркулирующие по сети, а не только адресованной ей конкретно (крэкеру не требуется доступ к UNIX, достаточно иметь PC с DOS или Windows (частая ситуация в университетских сетях)).
Поскольку TCP/IP-трафик, как правило, не шифруется, злоумышленник, используя соотв-щий инструментарий, может перехватывать TCP/IP-пакеты, например, telnet-сессий и извлекать из них имена пользователей и их пароли.
Следует заметить, что данный тип атаки невозможно отследить, не обладая доступом к системе злоумышленника, поскольку сетевой поток не изменяется. Единственная надежная защита от подслушивания -- шифрование TCP/IP-потока или использование одноразовых паролей.
Др. вариант решения – исп-ие интеллектуальных коммутаторов (свитчей), в результате чего каждая машина получает только тот трафик, что адресован ей.
Подслушивание может быть и полезно. Так, данный метод используется большим количеством программ, помогающих администраторам в анализе работы сети (ее загруженности, работоспособности и т.д.). Один из ярких примеров net watcher. Активные атаки на уровне TCP. При данном типе атак злоумышленник взаимодействует с получателем информации, отправителем и/или промежуточными системами, возможно, модифицируя и/или фильтруя содержимое TCP/IP-пакетов. Данные типы атак часто кажутся технически сложными в реализации, однако для хорошего программиста не составляет труда реализовать соотвествующий инструментарий. К сожалению, сейчас такие программы стали доступны широким массам пользователей (например, см. раздел про SYN-затопление).
Активные атаки можно разделить на две части:
1. В 1-ом случае злоумыш-к предпринимает опред-ые шаги для перехвата и модификации сетевого потока или попыток "притвориться" другой системой.
2. Во 2-ом случае протокол TCP/IP используется для того, чтобы привести систему-жертву в нерабочее состояние.
Обладая достаточными привилегиями в Unix, злоумышленник может вручную формировать IP-пакеты и передавать их по сети. Естественно, поля заголовка пакета могут быть сформированы произвольным образом. Получив такой пакет, невозможно выяснить, откуда реально он был получен, поскольку пакеты не содержат пути их прохождения. Конечно, при установке обратного адреса, не совпадающего с текущим IP-адресом, злоумышленник никогда не получит ответ на отосланный пакет. Однако, как мы увидим, часто это и не требуется. Возможность формирования произвольных IP-пакетов является ключевым пунктом для осуществления активных атак.
2. Угрозы, характерные для Internet. Удаленные атаки, алг-м работы, м-ды защиты.
Информационная атака на компьютерную систему представляет собой действие, предпринимаемое злоумышленником через сеть Internet, которое заключается в поиске и использовании той или иной уязвимости данной системы.
Internet как и другие распределённые вычислительные системы имеет определённую особенность: сетевые системы характерны тем, что, наряду с обычными (локальными) атаками, осуществляемыми в пределах одной компьютерной системы, к ним применим специфический вид атак, обусловленный распределенностью ресурсов и информации в пространстве. Эти атаки называются сетевыми (или удаленными). Они характерны, во-первых, тем, что злоумышленник может находиться за тысячи километров от атакуемого объекта, и, во-вторых, тем, что нападению может подвергаться не конкретный компьютер, а информация, передающаяся по сетевым соединениям.
- По характеру воздействия:пассивное, активное
- По цели воздействия:нарушение конфиденциальности информации либо ресурсов системы, нарушение целостности информации, нарушение работоспособности (доступности) систем
- По условию начала осуществления воздействия: Атака по запросу от атакуемого объекта. Важно отметить, что данный тип удаленных атак наиболее характерен для Internet`a. Атака по наступлению ожидаемого события на атакуемом объекте. Безусловная атака. Примером атаки данного вида может служить «Навязывание ложного маршрута в сети Internet».
- По наличию обратной связи с атакуемым объектом: с обратной связью, без обратной связи (однонаправленная атака)
- По расположению субъекта атаки относительно атакуемого объекта:внутрисегментное, межсегментное
Удаленная атака через Интернет:
Пусть мы проводим атаку с хоста, находящегося в одном сегменте с атакуемой сетью фирмы. => существует возможность с атакующего хоста подвергать анализу любой пересылаемый пакет в сегменте. В сети Internet для получения доступа к серверу пользователю необходимо пройти на нем процедуру идентификации и аутентификации. В кач-ве инф-ии, идентифицирующей пользователя, выступает его идентификатор (имя), а для аутентификации используется пароль. Подключаемся к серверу и входим в сеть Internet, затем запускаем специальную программу-анализатор, которая осуществляет анализ сетевого трафика. Данная программа, запустившись, будет перехватывать каждый пакет в данном сегменте сети и выделять среди них те, в к-рых передаются идентификатор пользователя и его пароль, Отсортировав полученную инф-ию, останется только распознать имя и пароль интересующего нас хоста. Если координаты пользователя получены без каких-либо проблем, в незашифрованном виде, то следует сказать о слабом уровне защиты данной сетевой системы от сетевых проникновений. Если же координаты закодированы и не поддаются распознаванию, то следует применить программы дешифрации. И в зависимости от результатов, сделать вывод о степени безопасности системы и уровне доступа к хранящейся информации.
3. Защита от атак из Интернет. Прокси - серверы, брандмауэры.
Основные схемы сетевой защиты на базе межсетевых экранов
При подключении корпоративной или локальной сети к глобальным сетям администратор сетевой безопасности должен решать следующие задачи:
· защита корпор. или лок. сети от несанкц-ого доступа со стороны глоб. сети;
· скрытие инф-ии о стр-ре сети и ее компонентов от польз-лей глоб. сети;
· разграничение доступа в защищаемую сеть из глоб. сети и из защищаемой сети в глобальную сеть.
Необходимость работы с удаленными пользователями требует установки жестких ограничений доступа к информационным ресурсам защищаемой сети. При этом часто возникает потребность в организации в составе корпорационной сети нескольких сегментов с разными уровнями защищенности
· свободно доступные сегменты (например, рекламный WWW-сервер),
· сегмент с ограниченным доступом (н-р, для доступа сотрудникам организации с удаленных узлов),
· закрытые сегменты (например, локальная финансовая сеть организации).
Административные методы защиты от удаленных атак в сети Internet
Они вкл-ют: выбор тех или иных ОС под которыми будет функционировать РВС, определение используемых протоколов, установление уровней доступа к ресурсам системы и осуществление их контроля, и т.д. В принципе, приемлемых способов защиты от отказа в обслуживании в существующем стандарте сети Internet нет. Это связано с тем, что в данном стандарте невозможен контроль маршрута сообщений. Поэтому невозможно обеспечить надежный контроль сетевых соединений, так как у одного субъекта сетевого взаимодействия существует возможность занять неограниченное число каналов связи с удаленным объектом и при этом остаться анонимным. Поэтому, для повышения надежности работы системы в данных условиях можно предложить исп-ть как можно более мощные компы. Чем > число и частота работы процессоров, чем больше объем оперативной памяти, тем более надежной будет работа сетевой ОС, когда на нее обрушится направленный "шторм" ложных запросов на создание соединения, что и приводит к отказу в обслуживании. Кроме того, необходимо исп-ие соответствующих операционных систем с внутренней очередью, способной вместить большое число запросов на подключение.
· аппаратные шифраторы сетевого трафика;
· установка прокси – сервера;
· методика Firewall (брандмауэр), реализ-ая на базе программно-аппаратных средств;
· защищенные сетевые криптопротоколы;
· программно-аппаратные анализаторы сетевого трафика.
Для организации такого шлюза необходим компьютер с двумя сетевыми интерфейсами. Один из этих интерфейсов (назовем его внешним) подключен к Internet, а другой (назовем его внутренним) – к локальной сети. В качестве внешнего интерфейса можно использовать модем. Компьютер, на котором будет установлен прокси - сервер, должен удовлетворять требованиям, указанным разработчиками этого шлюза. Прокси - сервер выполняет две функции: кэширование трафика и зеркалирование локальной сети. За счет кэширования ускоряется повторный доступ ко внешним ресурсам (так как на самом деле ранее запомненная информация выбирается из кэша, а не перечитывается с удаленных сайтов). Это может вызвать следующую проблему: пользователи работают с устаревшими данными. Администратор сети должен следить за периодическим обновлением кэша, очищать кэш по мере необходимости. Зеркалирование сети происходит за счет того, что во внешнюю сеть выходит только компьютер с прокси - сервером, а не клиенты сети. Из этого следует, что компьютер с прокси – сервером не должен содержать никаких важных данных!
· Фильтрация сетевого трафика, позволяет администратору безопасности сети централизованно осуществлять необходимую сетевую политику безопасности в выделенном сегменте IP-сети. Здесь в качестве субъектов взаимодействия будут выступать IP-адреса хостов пользователей, а в качестве объектов, доступ к которым необходимо разграничить, - IP-адреса хостов, используемые транспортные протоколы и службы предоставления удаленного доступа.
· Proxy-схема с доп. идентификацией пользователей, позволяет при доступе к защищенному Firewall сегменту сети осуществить на нем дополнительную идентификацию и аутентификацию удаленного пользователя. Смысл proxy-схемы состоит в создании соединения с конечным адресатом через промежуточный proxy-сервер на хосте Firewall. На этом proxy-сервере и может осуществляться дополнительная идентификация абонента. Применение методики Firewall для обеспечения сетевой безопасности является необходимым, но отнюдь не достаточным условием, и не нужно считать, что, поставив Firewall, можно разом решить все проблемы с сетевой безопасностью и избавиться от всех возможных удаленных атак из сети Internet.
4. Квантовая криптография.
Квантово-криптографические сис-мы - это побочный продукт разрабатываемого в настоящее время так наз-ого квантового компа. Основной строительной ед-цей квантового компа явл-ся кубит. Классический бит имеет, как известно, лишь два состояния - 0 и 1, тогда как множество состояний кубита значительно больше. Это означает, что кубит в одну единицу времени равен и 0, и 1, а классический бит в ту же единицу времени равен либо 0, либо 1. Так если квантовая память состоит из двух кубитов, то мы параллельно работаем со всеми ее возможными состояниями: 00, 01, 10, 11. За счет возможности параллельной работы с большим числом вариантов квантовому компу необходимо гораздо < времени для решения задачи разложения числа на простые множители, поиск в большой базе данных и др. Вот здесь и прослеживается основное свойство квантовой криптографии. Мы могли бы просто использовать, например, алгоритм RSA, не прибегая к квантовой криптографии, но ведь квантовая физика несет нам не только квантовую криптографию, но и новый квантовый криптоанализ.
В квантово-криптограф-ом аппарате применим принцип неопределенности Гейзенберга, согласно которому попытка произвести измерения в квантовой системе вносит в нее нарушения, и полученная в результате такого измерения информация определяется принимаемой стороной как дезинформация. Квантовая криптография использует этот факт для обеспечения возм-ти двум сторонам, к-рые ранее не встречались и не обменивались никакой предварительной секретной инф-цией, осуществлять между собой связь в обстановке полной секретности без боязни быть подслушанными злоум-ком.
Осн. применение квантовой криптографии - быстрое и безопасное получение общего (для адресата и отправителя) секретного ключа. Используя этот секретный ключ, уч-ки обмена могут абсолютно спокойно общаться по откр. (незащищенному) каналу связи. За относит-но недолгое время сущ-ия квантовой криптографии разработано несколько алг-мов выработки общего секретного ключа (ОСК) с помощью квантов и квантовых каналов связи (ККС).
Алгоритмическая часть ККС состоит из стека протоколов, реализация которого позволяет законным пользователям обеспечить формирование общего ключа при условии утечки к злоумышленнику не более заданного количества информации или отказ от данного сеанса при невыполнении этого условия. В стек протоколов входят следующие элементы: Протокол первичной квантовой передачи. Протокол исправления ошибок в битовых последовательностях, полученных в результате квантовой передачи. Протокол оценки утечки к злоумышленнику информации о ключе. Протокол усиления секретности и формирования итогового ключа.
5. Биометрические средства защиты.
Биометрический контроль доступа – автоматизированный м-д, с помощью которого путем проверки (исследования) уникальных физиологических особенностей или поведенческих характеристик человека осущ-ся идентификация личности. Физиологические особенности, н-р, папилярный узор пальца, геометрия ладони или рисунок (модель) радужной оболочки глаза, являются постоянными физическими хар-ми человека. Данный тип измерений (проверки) практически неизменен также как и сами физиологические хар-ки.
В отличие от пароля или персонального идентификационного номера (ПИН), биометрическая характеристика не может быть забыта, потеряна, или украдена. Поскольку биометрические характеристики каждой отдельной личности уникальны, они могут использоваться для предотвращения воровства или мошенничества. Сегодня существует > 10,000 компьютеризированных мест, хранилищ, исследовательских лабораторий, банков крови, банкоматов, военных сооружений, доступ к которым контролируется устройствами, которые сканируют уникальные физиологические или поведенческие характеристики индивидуума.
Биометрические сис-мы идентификации, доступные в наст. время или нах-ся в стадии разработки вкл. в себя сис-мы доступа по отпеч. пальца, аромату, ДНК, форме уха, геометрии лица, клавиатурному почерку, отпечатку ладони, сетчатке глаза, рисунку радужной оболочки глаза, подписи и голосу.
Отпечаток пальца. Преим-ва доступа по отпечатку пальца – простота исп-ия, удобство и надежность. Весь процесс идентификации занимает мало времени и не требует усилий от тех, кто использует данную систему доступа. Исслед-ия показали, что исп-ие отпечатка пальца для идентификации личности является наиболее удобным из всех биометрических методов. Вер-ть ошибки при идентификации польз-ля намного < в сравнении с др. биометрич-ми м-дами. Устройство идентификации по отпечатку пальца не требует много места на клавиатуре или в механизме. В наст. время уже производятся подобные системы размером меньше колоды карт.
Радужная оболочка глаза. Преим-во сканеров для радужной оболочки: они не требуют, чтобы польз-ль сосредоточился на цели, потому что образец пятен на радужной оболочке нах-ся на поверхности глаза. Фактически, видео изображение глаза может быть отсканировано на расстоянии трех футов, что делает возможным использование сканеров для радужной оболочки в банкоматах.
Сетчатка глаза. Сканирование сетчатки происходит с исп-ем инфракрасного света низкой интенсивности направленного через зрачок к кровеносным сосудам на задней стенке глаза. Сканеры для сетчатки глаза получили большое распространение в сверхсекретных системах контроля доступа, так как у них один из самых низких процентов отказа доступа зарегистрированных пользователей, и почти 0 % ошибочного доступа. Однако изображение радужной оболочки должно быть четким на задней части из глаза, поэтому катаракта может отрицательно воздействовать на качество изображения радужной оболочки глаза.
Геометрия лица. Идентификация по чертам лица – одно из наиболее быстро растущих направлений в биометрической индустрии. Привлекательность данного метода основана на том, что он наиболее близок к тому, как мы идентифицируем друг друга. Развитие этого направления связано с быстрым ростом мультимедийных видеотехнологий, благодаря которым можно увидеть все больше видеокамер, установленных дома и на рабочих местах. Однако большинство разработчиков пока испытывают трудности в достижении высокого уровня исполнения данных устройств. Тем не менее, можно ожидать появление в ближайшем будущем специальных устройств идентификации личности по чертам лица в залах аэропортов для защиты от террористов и т.п.
Подпись. Статическое закрепление подписи становится весьма популярным взамен росписи ручкой на банковской кредитной карточке, бланке службы доставки (например, FedEx). В основном, устройства идентификации подписи используют специальные ручки, чувствительные к давлению столы, или комбинацию обоих. Устройства, использующие специальные ручки менее дороги и занимают меньше места, но в тоже время имеют меньший срок службы.
Понятие отказоустойчивости тесно связано с понятием надежности. Можно перечислить некоторые наиболее важные аспекты надежности: доступность, безотказность, безопасность, ремонтопригодность, защищенность.
Доступность - это свойство системы находиться в правильном состоянии. Обычно доступность рассчитывают как вер-ть того, что в данный момент времени сис-ма будет правильно работать и окажется в состоянии выполнить свои ф-ии, если польз-ль того потребует. То есть доступная сис-ма - это сис-ма, к-рая в произвольный момент времени находится в работоспособном состоянии.
Безотказность – св-во сис-мы непрерывно работать без отказов в течение продолжит-ого времени. Безотказность обычно измеряется интервалом времени правильной работы системы.
Безопасность хар-ет, насколько катастрофичен временный отказ системы. Системы упр-ия опасными объектами д. обладать высокой степенью безотк-ти.
Ремонтопригодность - очень важная характеристика, так как даже, если отказ произошел, то жизнь еще не кончена, а следовательно надо вернуть систему в правильное состояние. Св-во системы, определяющее, насколько сложно определить причину отказа (возможно, автоматически) и исправить систему.
Защищенность - свойство, описывающее, насколько система защищена от умышленного вредного воздействия, от несанкционированного доступа.
Система отказывает, если она не в состоянии выполнить свои функции. Ошибкой называют такое состояние системы, которое может привести к тому, что система откажет. Причиной ошибки могут неправильные действия компонент системы или внешние факторы. Причиной ошибки называют отказ (обратите внимание на неудачный перевод с английского, в результате которого появилась неоднозначность понятий!). Построение надежных систем связано с упр-ем отказами. Упр-ие в данном случае - нечто среднее между предотвращением, исправлением и предсказанием отказов. Под отказоуст-тью будем понимать способность сис-мы предоставлять услуги даже при наличии отказов.
Передаваемые по сети сообщения часто портятся из-за различного рода помех и сбоев в работе оборудования. Для того, чтобы получатель смог сделать заключение о правильности полученного кадра, ему требуется некая избыточная (дополнительная информация). Метод формирования из исходных данных сообщения с дополнительными контрольными данными называется кодированием. Другими словами, кодированием называется способ преобразования информации из одного вида в другой, основная цель преобразования - обеспечение надежного хранения и передачи информации.
То, что получено после добавления контрольных данных называется кодом или кодовым словом.
Различают коды, обнаруживающие ошибку, и коды, исправляющие ошибку. Если код позволяет хотя бы обнаруживать ошибку, такой способ преобразования информации называют помехоустойчивым кодированием.
Пусть есть два кодовых слова. Кодовым расстоянием в смысле Хэмминга называется количество несовпадающих бит. Кодовое расстояние легко посчитать при помощи операции XOR .
Кратность ошибки - количество инвертированных бит по сравнению с правильным состоянием. Код называется кодом, обнаруживающим однократную ошибку, если он гарантированно различает сообщения, отличающиеся одним битом, то есть сообщения кодовое расстояние между которыми равно 1, и не различает сообщения, кодовое расстояние между которыми равно двум.
Пусть кадр состоит из m бит, к нему добавляется r контрольных бит, тогда длина кодового слова равна n = m + r. Пусть исходные данные могут быть совершенно любыми, то есть любые из 2m комбинаций битов являются возможными. Так как существует некоторое правило формирования контрольных бит, то не все из 2 n комбинаций возможны. А, следовательно, можно посчитать кодовые расстояния между всеми возможными парами кодовых слов и найти минимум по этому множеству. Этот минимум называется кодовым расстоянием кода в смысле Хэмминга.
Применяют три вида избыточности: информационная избыточность, временная избыточность и физическая избыточность.
В случае информационной избыточности к сообщению добавляют дополнительные биты, с помощью которых можно произвести исправление ошибок в сообщении. Мы рассматривали такой способ – код Хэмминга.
В случае временной избыточности уже выполненное действие при необходимости осуществляется еще раз. В качестве примера можно привести транзакции. Если транзакция была прервана, ее можно без опасений повторить. Временная избыточность особенно полезна при наличии перемежающихся или проходных отказов.
В случае физической избыточности мы добавляем в систему дополнительное оборудование или процессы, которые делают систему работоспособной при утрате или неработоспособности отдельных компонент. Таким образом физическая избыточность может быть и аппаратной и программной. Физическая избыточность – широко применяемый и в биологии (два глаза!), и в самолетостроении, и в радиотехнике.
Рассмотрим схему, называемую тройным модульным резервированием. Пусть есть последовательно обрабатывающие сигнал три устройства А, Б, В. В схеме каждое устройство присутствует в трех экземплярах, Кроме того, после каждого устройства стоит устройство тройного голосования. На вход устройства голосования подается сигнал со всех трех копий. Если на двух или трех входах устройства голосования одинаковый сигнал, то на выходе (выход один) повторен этот сигнал, иначе сигнал на выходе не определен. Допустим, что элемент А2 отказал. Тогда Г1, Г2, Г3 получат два правильных (одинаковых!) и один неправильный сигнал и примут решение в пользу правильного. Так что ошибка А2 тут же замаскируется. Допустим, что одновременно с А2 отказали Б3 и В1. Легко видеть, проведя расчет для устройств голосования Г4, Г5, Г6, Г7, Г8, Г9, что эти ошибки тоже окажутся замаскированными! А зачем устройства голосования в тройном экземпляре после каждого из А, Б и В, кажется, достаточно по одному. Дела в том, что устройство голосования также может выйти из строя. Пусть отказало устройство Г1. Входной сигнал для Б1 будет неверным, но далее уже эта ошибка не распространится, так как Г4, Г5 и Г6 примут верное решение.
Почти все компьютеры имеют физические часы - встроенные периодические процессы для подсчета времени. Таймер компьютера - это особым образом обработанный кристалл кварца. Находясь под напряжением, этот кристалл колеблется с постоянной частотой, которая зависит от свойств кристалла (способ разрезания, величина напряжения). С кристаллом ассоциированы два регистра: счетчик и регистр хранения. Каждое колебание кристалла уменьшает значение счетчика на 1, а когда это значение становится равным нулю, генерируется прерывание и счетчик перезагружается. Таким образом, можно запрограммировать таймер так, чтобы он выдавал прерывания один раз в секунду или с любой другой частотой. Когда система загружается, она запрашивает время у пользователя, затем переводит это время в количество «тиков», начиная с некоторой жестко установленной в микросхеме датой, и сохраняет это время.
2 сп-ба синхронизации: реальное время, синхронизация (соотношение)
Алгоритм Кристиана.
Периодически каждая машина посылает серверу времени сообщение, запрашивая текущее время. Сервер как можно быстрее отвечает сообщением, содержащим текущее время. Кристиан предложил измерять это время на стороне клиента и использовать рассчитанные значения. Если клиент засекает время отправки запроса и время получения ответа, то он может достаточно неплохо приблизиться к истинному времени, добавив к серверному времени половину измеренного интервала. Если же известно примерное время работы сервера (ответа на запрос), то можно точнее определить время хождения по сети, вычитая из времени оборота время работы сервера. Хуже обстоят дела, если прохождение запроса и ответа занимает разное время, так как сигналы идут разными маршрутами. Для повышения точности Кристиан предложил делать серию измерений и использовать среднее время. Причем, если попадается измерение, которое выходит за рамки некоторого принятого ранее порога в сторону увеличения, то такое измерение отбрасывается, как недостоверное. Наоборот, наиболее быстрый ответ можно считать содержащим самое точное время.
Алгоритм Беркли.
Здесь сервер времени активен. Он опрашивает клиентов о том, какое у них время. На основании ответов вычисляет среднее время и предлагает всем машинам выставить часы в соответствии с этим средним временем. Этот алгоритм приемлем для систем, не имеющих связи с внешним источником точного времени.
Усредняющие алгоритмы.
Оба описанные алгоритма сильно централизованы (с вытекающими отсюда недостатками). Один из классов децентрализованных алгоритмов работает на основе деления интервала на синхронизационные участки одинаковой продолжительности. В начале каждого интервала каждая машина делает широковещательную рассылку своего времени. Это происходит не одновременно, так как часы на машинах идут по-разному. После рассылки машина запускает таймер и начинает собирать все широковещательные пакеты. Затем запускается алгоритм вычисления усредненного времени, возможно, отбрасывая сильно отличающиеся, учитывая время прохождения сигнала по сети и т.п.
Лампорт предложил изменять время при общении так, чтобы сохранилась разумная очередность. Не м.б. одновременных процессов. Все процессы должны проходить в разное время. При этом:
1) все процессы будут иметь одну и ту же копию локальной очереди;
2) каждое сообщение рассылается всем процессам, включая подтверждение;
3) предполагает ответ ото всех процессов;
4) сообщения принимаются в порядке их отправки;
5) процесс может доставить поставленное сообщение приложению, которое работает только если это сообщение находится на вершине очереди и его получение подтверждено всеми остальными процессами;
6) теперь процесс может быть удален из очереди и обрабатывается приложением, а соответствующие ему подтверждения просто удаляются;
7) т.к. каждый процесс имеет такую же копию очереди, то все сообщения достаются повсюду в одинаковом порядке.
1) Алг-м забияки
Дано: у каждого узла есть хар-ка (знач-я не повтор-ся). Треб-ся: выбрать координ-ра, т.е. узел с максим. хар-ой. доп. предпис-е:
− каждый узел знает о знач-ях хар-к других узлов
− по некоторым причинам одному из узлов (или нескольким) стан-ся известно, что нет координ-ра
1. Пусть узел обнаружил, что коорд-ра нет, след-но формирует пакет голос-ия к рассылке узлам с большей хар-ой
2. Если узел -отправитель не получил ответа, след-но он коорд-р
3. Рассылка младшим сообщ-я (извещ-я) о коорд-ре.
4. Каждый получивший отправляет пакет – подтвержд-е с указанием себя как возможного коорд-ра, и отправитель сообщ-я голос-я ожидает (п.3)
5. Каждый получивший начинает процесс голосования
2) Кольцевой алг-м
Предполож-ие: каждый узел знает кольцо,=> знает последователей
− усть узел обнаружил пропажу коорд-ра. Он отпр-ет пакет голос-я: н-р,
+ имя инициатора + метка времени
− каждый получивший добавляет себя в список кандидатов и отпр-ет по кольцу
− инициатор, получив этот пакет делает 2 вещи:
формирует пакет извещ-ия
− получив извещ-е, удаляет его.
Разделяемый рес-с – это общий для неск. процес-ов рес-с. Крит. секция – часть прогр-го кода проц-са, в к-ой осущ-ся работа с разделяемыми рес-ми. Взаимное исключ-е – способ, обеспечивающий в каждый момент времени нахожд-е только одного проц-са в крит-ой секции, связ-го с несколькими разделяемыми рес-ми. Монитор – выбираемый в рез-те голос-ия комп-р, реализующий взаимн. искл-е всех проц-ов по всем разделяемым рес-ам. Монитор располагает списком раздел-ых рес-ов и с каждым рес-ом из этого списка связано имя процесса занимающего и имя процесса ожидающего.
1) Централизованный алг-м
1. процесс делает запрос на занятие монитора: ждет разреш-я либо получает подтв-е и ждет разреш-я
2. монитор по своим данным либо разрешает доступ, либо устан-ет в очередь
3. процесс, прекративший работу с раздел. рес-ом, отпр-ет сообщ-е об освобожд-и
4. монитор, получив сообщ-е об освобожд-и, выбирает из очереди первого ожидающего и отпр-ет ему разреш-е.
Сис-ма с централиз. алг-ом плоха тем, что если сломался комп-р, то вся сис-ма не работает.
2) Децентрализ-ый алг-м
Предполаг-ся, что фун-ии коорд-ра на себя берет то один узел, то другой. Т.е. каждый может в опред-ое время стать сервером взаимн-го искл-ия.
Треб-ия:
− Надежная доставка сооб-ий (на каждое сообщ-е есть подтвержд-е)
− Должна быть полная упорядоченность сообщ-ий (н-р, с помощью отметок времени Лампорта)
Алг-м:
1. Проц-с, к-ый хочет войти в крит-ую обл-ть, сначала должен спросить разреш-я. Формир-ет сообщ-е – запрос: имя проц-са, имя крит-ой обл-ти, время по локальным часам. Останавливается и ждет сообщ-я ото всех.
2. Процесс, получивший запрос, должен либо разрешить, либо не разрешить занять крит-ую обл-ть.
а) если процесс-получатель не собирается занимать эту крит-ую обл-ть и не нах-ся в ней, то он отпр-ет разреш-е
б) если процесс-получатель находится в крит-ой обл-ти, то он заносит процесс – отправитель в локальную очередь
в) если процесс-получатель собирается войти в крит-ую обл-ть, то он сравнив-ет время отправки своего сообщ-я – запроса с временем, полученным в сообщ-и. Если у него время мин-ое, то он занимает рес-с и пункт б. Иначе отпр-ет разреш-е и пункт а.
3. Проц-с, вышедший из крит-ой обл-ти, должен сообщить об этом всем из локальной очереди, шлет разреш-е и удаляет очередь.
3) Маркерное кольцо
Треб-ия:
− Логич-ое кольцо
− Сущ-ет спец-ый пакет (маркер), циркулирующий по кольцу
Алг-м:
1. Процесс, желающий занять крит-ую обл-ть, ждет маркер
2. Получив марке, процесс входит в крит-ую обл-ть и работает там
3. Выйдя из крит-ой обл-ти, отправляет маркер дальше Недостаток: один маркер, повторно маркер не исп-ся
4. Если процесс не требует никакого рес-са, то он отпр-ет маркер дальше по кольцу как можно быстрее.
Для более эфф-ой работы маркеров: кол-во маркеров = кол-ву раздел-ых рес-ов
Сравнение алг-ов (n узлов)
|
Алг-м |
Сколько сооб-ий на вход – выход |
Время ожид-я |
Проблемы |
|
Централиз-ый |
3 |
2 |
Крах сервера взаимн-го искл-ия |
|
Децентрализованный |
2 * (n-1,(т.к. себе не посылает)) |
2 * (n-1) |
Крах любого из комп-ов |
|
Маркерное кольцо |
От 0 до n-1, мат. ожид-е n/2 |
n/2 |
Крах комп-ра, крах маркера |
Вывод: централиз-ый алг-м лучше. Но его нельзя применить к мобильной сети. Он хорош для статической сети. А для динамической можно применять как децентрализ-ый, так и маркерное кольцо: для больших сетей – децетрализ-ый, для маленьких – маркерное кольцо.
22. Непротиворечивость, транзакции, репликации
Транзакции. Свойства: атомарность, непротиворечивость, изолированность, долговечность.
Плоские транзакции - транзакции, имеющие полный набор свойств. Недостатки - невозможность сохранить промежуточные результаты. Из-за этого: либо нет возможности даже увидеть эти результаты, либо требуется недопустимо много времени на выполнение транзакции.
Вложенные транзакции – св-во долговечности закрепляется только на верхнем уровне, работают с одними и теми же данными (последовательно).
Распределенные транзакции – св-во долговечности закрепляется только на верхнем уровне, работают с разными данными (параллельно).
Реализация атомарности и долговечности. Есть 2 способа реализации с точки зрения реализации: 1) закрытое рабочее пространство, предполагает копир-ие всех данных, недостаток – потребность в доп. данных, объем которых велик; журнал с упреждающей записью, предполагает запись изменений.
Реализация непротиворечивости и изолированности. Цель управления параллельными транзакциями состоит в том, чтобы позволить параллельным транзакциям выполняться одновременно, но т.о., чтобы набор обрабатываемых данных (например, записей базы данных или целых файлов) оставался непротиворечивым. Непротиворечивость достигается в результате того, что доступ транзакций к элементам данных организуется в определенном порядке так, чтобы конечный результат был таким же, как и при выполнении всех транзакций последовательно. Важно: любой порядок транзакций в последоват-ти допустим. Алг-мы упр-ия параллельными транзакциями обычно классифицируют по способу синхронизации операций чтения и записи.
Существует 2 способа управления транзакциями:
- пессимистический, сначала производится синхронизация процесса в том или ином смысле, а потом выполнение транзакции. Недостаток: требует > времени и ресурсов, но работает в загруженной распределенной системе.
- оптимистический, сначала выполняются транзакции, отслеживаются изменения общих данных и если не было конфликтов, транзакции успешно завершаются. Иначе – откат и все начинается заново. Недостаток: min затрат, но в загруженной РС не работает.
Двухфазная блокировка. Процесс, которому требуется выполнить операцию чтения или записи, обращается к планировщику с просьбой заблокировать для него данные. По окончании работы с данными процесс извещает об этом планировщик. Работа выполняется в соответствии с тремя правилами:
- Когда планировщик получает операцию oper(T,x), он проверяет, не конфликтует ли эта операция с другими операциями, уже получившими блокировку. Если есть конфликт, операция откладывается, иначе планировщик блокирует данные для этой операции.
- Планировщик снимает блокировку только после получения уведомления об окончании операции.
- После того, как планировщик снимает с данных блокировку, установленную по требованию транзакции Т, он никогда не делает другую блокировку, при этом неважно, на какой элемент данных транзакция Т требует установить блокировку. Любое требование новой блокировки являются ошибкой программирования и приводят к прерыванию транзакции Т. Двухфазная блокировка может привести к тупикам. применяются обычные методы борьбы с тупиками: устанавливается порядок данных на блокирование, либо возникновение тупика обнаруживается путем проверки графа транзакций на цикличность. Кроме того, когда заранее известно, что никакая блокировка не может превышать некоторое время, при нарушении этого правила виновная транзакция прерывается.
Строгая двухфазная блокировка – фаза спада не начинается до тех пор, пока транзакция не окончится подтверждением или не будет прервана. Преимущества: изолированность (транзакция всегда считывает значения, уже подтвержденные другой транзакцией), упрощается алгоритм наложения и снятия блокировок. В этом случае исключаются каскадные прерывания, возникающие при прерывании одной транзакции, так как никакая транзакция не использует промежуточные данные другой транзакции.
Пессимистическое упорядочение по отметкам времени. Каждой транзакции присваивается время ts(T). Это время в соответствии с алгоритмом Лампорта уникально. Каждая операция транзакции тоже получает отметку времени ts(T). Кроме того, каждый элемент данных х в системе получает две отметки времени: отметку времени чтения tsRD(x) и отметку времени записи tsWR(x). Отметка времени чтения соответствует отметке времени транзакции, которая последняя считывала данные х. А отметка времени записи равна отметке времени транзакции, которая последняя записывала данные х.
Если две операции конфликтуют, менеджер данных выбирает сначала операцию с наименьшей отметкой времени. Если транзакция запоздала, то есть ее отметка времени меньше отметки времени у данных, то транзакция прерывается. Иначе транзакция выполняется, а у данных изменяется соответствующая отметка времени. Прерванная транзакция может получить новую отметку времени и начать все сначала.
Оптимистическое упорядочение по времени. Конфликты бывают нечасто, но тем не менее требуется способ их обнаружения разрешения. Оптимистическое управление отслеживает случаи чтения и записи данных. В момент подтверждения транзакции проверяется, не были ли какие-нибудь данные, нужные другим транзакциям, изменены с момента начала транзакции. Если нет, то транзакция подтверждается, иначе - прерывается.
Оптимистическое управление параллельными транзакциями можно реализовать при помощи закрытого рабочего пространства. В этом случае каждая транзакция изменяет свои данные в частном порядке. По окончании эти измененные данные либо принимаются либо отбрасываются. Очевидно, что чем больше загрузка, тем больше возникает конфликтов.
Репликации. Выгода репликации – повышение производительности и надежности. Можно обеспечить повышение отказоустойчивости в результате ведения зеркальных копий, производительности за счет приближения места хранения данных к клиенту, обнаружение и исправление ошибок в результате хранения трех копий. Но при оценке выгоды репликации стоит оценить затраты на ее проведение: это стоимость дополнительных хранилищ и стоимость поддержания непротиворечивости реплик.
В распределенной системе существует проблема одновременного доступа к объектам нескольких процессов. У этой проблемы существует два основных решения: 1) одновременные вызовы обрабатывает сам объект; 2) ответственность за выполнение параллельных обращений несет сервер. В 1-ом случае сам объект устанавливает некоторый порядок. Во 2-ом случае обычно применяется некоторый адаптер объектов, который сериализует доступ к объектам, которыми он управляет.
Репликация может происходить 2-мя способами: 1) сам объект осведомлен о том, что он реплицирован, и отвечает за непротиворечивостью реплики. Примеры систем, не нуждающихся в централизованной поддержке репликации, SOS, Globe. Преим-ва систем, в которых сам объект отвечает за репликацию, состоит в том, что объект может реализовать специфическую стратегию репликации, зависящую от прикладной обл-ти, вида объектов и т.п.; 2) за репликацию ответственна распределенная сис-ма (CORBA). При этом обычно используются средства для помехоустойчивых, полностью упорядоченных и причинно упорядоченных обращений к объектам. Репликация и кэширование, увеличивающие производительность, часто исп-ся в качестве способа масштабирования, которое может вызвать проблемы с производительностью. Это легко видеть, если рассмотреть случай, когда частота обращений к реплике намного меньше частоты обновления данных.
Непротиворечивость. Модели непротиворечивости.
1. Ориентированные на данные, имеется хранилище данных, все процессы и пишут, и читают и работают только со свежими данными.
1.1 Строгая, предполагает, что каждый процесс в РС видит все операции (чтение, запись), которые делаются последовательно (очень строгая упорядоченность). Все процессы знают, что делают другие процессы. Хранилище данных при чтении некоторого разделяемого данного каждым процессом возвращает последнее значение, возможно измененное любым процессом.
1.2 Линеаризуемая, результат всякого действия над общими данными как если бы эти действия выполнялись бы в некоторой последовательности, причем: все операции одного процесса выполняются в последовательности, заданной ему программой и если время операции1 1-го процесса < времени операции2 2-го процесса , то операция1 вып-ся 1-ой, т.е. в соотв-ии с лок. отметками времени.
1.3 Последовательная, та же Линеаризуемая, но без отметок времени.
1.4 Причинная, ослабленный вариант последовательной, при которой проводится разделение между событиями, потенциально обладающими причинно-следственной связью, и событиями, ею не обладающими. Если событие В вызвано предшествующим событием А или находится под его влиянием, то причинно-следственная связь требует, чтобы все окружающие наблюдали сначала событие А, а затем В.
1.5 FIFO (PRAM), операции записи, осуществляемые единичным процессом, наблюдаются всеми остальными процессами в том порядке, в котором они осуществляются, но операции записи, происходящие в различных процессах, могут наблюдаться разными процессами в разном порядке.
1.6 Слабая
1.7 Свободная
1.8 Поэлементная.
2. Ориентированные на клиента, много процессов читает по сравнению с пишущими и соглашаются работать с не самыми последними данными.
2.1. Потенциальная, если изменений делается мало и процессы готовы работать с несвежими данными, то производительность будет высокая, но издержки в том, что данные не очень свежие.
2.2 Монотонное чтение, если процесс в момент времени t видит некое значение х, то позже он никогда не увидит более старого значения x.
2.3 Монотонная запись, процесс1 должен видеть на любой реплике свои записи только в той последовательности, в которой он их делал.
2.4 Чтение собственных записей, если что-то записали, то пока до конца система не выполнит операцию записи, нельзя прочитать старые данные.
2.5 Запись за чтением, записать что-либо можно только после окончания операции чтения. Недостаток: не видно частично испорченных данных.
23. Алгоритм замены
|
Алг-м замены |
|
|
|
экзамен |
шаг=4 |
алф-т |
|
болдрйс |
|
а...я |
Sub shifr1() 'кодирование
'алгоритм замены циклический (алгоритм цезаря)
tekst = inputbox( "Введите кодируемый текст")
shifr = ""
sh = InputBox("Введите шаг шифрования")
'делаем введенный шаг в интервале [0,223]
sh = sh - 224 * Int(sh / 224)
For i = 1 To Len(tekst)
'к коду i-ой буквы + шаг sh и вычитаем 32(начало печатаемых символов)
'чтобы не выйти за конец интервала берем остаток от деления
'на длину интервала (224)
'получим порядковый номер символа в интервале печатаемых символов
'для получения кода символа прибавляем 32
sled_b = (Asc(Mid(tekst, i, 1)) + sh - 32) Mod 224 + 32
shifr = shifr + Chr(sled_b) 'прибавляем зашифрованную букву
Next
Msgbox shifr
End Sub
Sub rasshifr1() 'раскодирование
'алгоритм замены циклический (алгоритм цезаря)
shifr = inputbox ("Введите зашифрованный текст")
sh = InputBox("Введите шаг шифрования")
tekst = ""
For i = 1 To Len(shifr)
'к коду i-ой буквы + шаг sh и вычитаем 32(начало печатаемых символов)
'чтобы не выйти за начало интервала прибавляем 224
'для получения кода символа прибавляем 32
sled_b = (Asc(Mid(shifr, i, 1)) - sh - 32 + 224) Mod 224 + 32
tekst = tekst + Chr(sled_b)
Next
msgbox tekst
End Sub
'алгоритм замены с изменяющимся шагом
'полиалфавитный алгоритм
alf1 = "эждлорпавыфячсмитьбю.ъхзщшгнекуцй "
alf2 = "qwertyuiop[]asdfghjkl;'zxcvbnm,./2"
24. Алгоритм гаммирования
|
Алг-м гаммир-я |
|
|
|
|
экзамен |
пять |
алфавит |
а ... я |
|
|
|
|
|
|
30 |
00011110 |
|
|
|
16 |
00010000 |
|
|
|
xor |
00001110 |
|
|
|
14 |
н |
|
|
|
11 |
00001011 |
|
|
|
32 |
00100000 |
|
|
|
xor |
00101011 |
|
|
|
43 |
|
|
|
|
43mod32+1 |
12 |
л |
43-32+1=12 |
|
8 |
00001000 |
|
|
|
19 |
00010011 |
|
|
|
xor |
00011011 |
|
|
|
27 |
ъ |
|
|
|
... |
|
|
|
Sub shifr1() 'кодирование
'алгоритм гаммирования с заданной гаммой
tekst = inputbox( "Введите кодируемый текст")
gamma = InputBox("Введите гамму")
shifr = ""
For i = 1 To Len(tekst)
'введенный текст соединяется с гаммой операцией Xor
shifr = shifr + Format(Asc(Mid(tekst, i, 1)) Xor Asc(Mid(gamma, (i - 1) Mod Len(gamma) + 1, 1)), "000")
Next
Msgbox shifr
End Sub
Sub rasshifr1() 'раскодирование
'алгоритм гаммирования с заданной гаммой
tekst = ""
shifr = inputbox( "Введите зашифрованный текст")
gamma = InputBox("Введите гамму")
For i = 1 To Len(shifr) Step 3
tekst = tekst + Chr(Val(Mid(shifr, i, 3)) Xor Asc(Mid(gamma, (i \ 3) Mod Len(gamma) + 1, 1)))
Next
Msgbox tekst
End Sub
25. Алгоритм RSA
Рассмотрим небольшой пример, иллюстрирующий применение алгоритма RSA. Зашифруем сообщение “САВ”. Для простоты будем использовать маленькие числа (на практике применяются гораздо большие).
1. Выберем p=3 и q=11.
2. Определим n=3*11=33.
3. Найдем (p-1)(q-1)=20. Следовательно, в качестве d, взаимно простое с 20, например, d=3.
4. Выберем число е. В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение (е*3) (mod 20) = 1, например 7.
5. Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А®1, В®2, С®3. Тогда сообщение принимает вид (3,1,2). Зашифруем сообщение с помощью ключа {7,33}.
ШТ1 = (37) (mod 33) = 2187 (mod 33) = 9,
ШТ2 = (17) (mod 33) = 1 (mod 33) = 1,
ШТ3 = (27) (mod 33) = 128 (mod 33) = 29.
6. Расшифруем полученное зашифрованное сообщение (9,1,29) на основе закрытого ключа {3,33}:
ИТ1 = (93) (mod 33) = 729 (mod 33) = 3,
ИТ2= (13) (mod 33) = 1 (mod 33) = 1,
ИТ3 = (293) (mod 33) = 24389 (mod 33) = 2.
Sub RSA_shifr()
tekst = inputbox( "Введите кодируемый текст")
e = 53 'открытый ключ
n = 299
shifr = ""
For i = 1 To Len(tekst)
pr = Asc(Mid(tekst, i, 1)) 'произведение
mnoz = 2 'количество множителей ch в произведении pr
ost = 1
Do While mnoz <= e
If e Mod mnoz >= mnoz / 2 Then ost = (pr * ost) Mod n
pr = (pr * pr) Mod n
mnoz = mnoz * 2
Loop
otv = (pr * ost) Mod n
shifr =shifr + Format(otv, "000")
Next
Msgbox shifr
End Sub
Sub RSA_rasshifr()
shifr = inputbox( "Введите зашифрованный текст")
d = 5 'закрытый ключ
n = 299
tekst= ""
For i = 1 To Len(shifr) Step 3
pr = Val(Mid(shifr, i, 3)) 'произведение
mnoz = 2 'количество множителей ch в произведении pr
ost = 1
Do While mnoz <= d
If d Mod mnoz >= mnoz / 2 Then ost = (pr * ost) Mod n
pr = (pr * pr) Mod n
mnoz = mnoz * 2
Loop
otv = (pr * ost) Mod n
tekst = tekst + Chr(otv)
Next
Msgbox tekst
End Sub
26. Алгоритмы проверки числа на простоту
Проверяются числа в интервале от 2 до √N делителями заданного числа. Задача состоит в поиске всех множителей с указанием кратности каждого множителя, например, число 2*2*3*7=84.
Sub prostoe_ch1()
ch = InputBox("Введите число")
prost = True
If ch > 3 Then
If ch Mod 2 = 0 Then prost = False
If ch Mod 3 = 0 Then prost = False
mnoz = 5
k = 2
Do While mnoz <= Sqr(ch) And prost
If ch Mod mnoz = 0 Then prost = False
mnoz = mnoz + k
k = 6 - k
Loop
End If
If prost Then MsgBox "Число простое" Else MsgBox "Число составное"
End Sub
27. Алгоритм формирования открытого и закрытого ключа
Выбрать простые P и Q из некоторого заданного интервала. Для определения простоты числа воспользоваться программой из "Э.З. №2". Интервал должен задавать пользователь. Затем посчитать N=P*Q, M=(P-1)(Q-1). В кач-ве D м. взять любое число, взаимно простое с M, но < N. В качестве числа E может быть взято любое число, для которого удовлетворяется соотношение (E*D) mod M = 1. Для поиска всех D предлаг-ся реализовать один из описываемых ниже м-дов. Для поиска Е следует восп-ся усл-ми: (E*D) mod M = 1 и 1<E<M. Из этих условий следует, что E*D= М-1 или E*D=М+1. Можно учитывать и только 1-ое усл-ие, тогда E*D=к*М-1 или E*D=к*М+1, где к–произв. целое, к>1.
Метод 1.Просматривать все числа от M-1 (с шагом -1), находя НОД рассм-ого числа и M. НОД можно искать по алг-му Евклида. Пусть m и n – числа. Если m<n обменяем их значения. Если m на n делится без остатка, то n – наибольший общий делитель. Иначе mi=ni-1, ni=mi-1-ni-1 и повторяем деление снова, пока n>1.
Function prostoe(ch) As Boolean
x = Int(Sqr(ch))
y = 0
x1 = 2 * x + 1
y1 = 2 * y + 1
r = x ^ 2 - y ^ 2 - ch
Do While r <> 0
If r < 0 Then
r = r + x1
x1 = x1 + 2
Else
r = r - y1
y1 = y1 + 2
End If
Loop
u = (x1 - y1) / 2
v = (x1 + y1) / 2 - 1
If u = 1 Or v = 1 Then prostoe = True Else prostoe = False
End Function
Function al_ev(a, b)
Dim u(3), v(3), t(3)
u(1) = 1
u(2) = 0
u(3) = a
v(1) = 0
v(2) = 1
v(3) = b
Do While v(3) <> 0
Q = Int(u(3) / v(3))
For i = 1 To 3
t(i) = u(i) - v(i) * Q
u(i) = v(i)
v(i) = t(i)
Next
Loop
al_ev = (u(1) Mod b + b) Mod b
End Function
Sub otkr_zakr_kluch1()
With Sheets(1)
lev_gr = InputBox("Левая граница", "Инт-л для нахожд-я прост.чисел P и Q")
prav_gr = InputBox("Правая граница", "Инт-л для нахожд-я прост.чисел P и Q")
P = lev_gr + (1 - lev_gr Mod 2)
Do While Not prostoe(P)
P = P + 2
Loop
Q = prav_gr - (1 - prav_gr Mod 2)
Do While Not prostoe(Q)
Q = Q - 2
Loop
N = P * Q
M = (P - 1) * (Q - 1)
D = M - 1
j = 2
Do While D > 1
If nod(D, M) = 1 Then
.Cells(j, 1) = D
.Cells(j, 2) = al_ev(D, M)
j = j + 1
End If
D = D - 1
Loop
End With
End Sub
28. Код Хэмминга
Пусть исх. данные - битовая строка 11100011. Кодовое слово включает биты четности, расположенные на местах, порядковый № к-рых явл-ся степенью двойки. Таких бит будет s = int (log2 d)+1, где d – длина исходной строки часть.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Теперь в биты данных заносим исходную строку:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
|
1 |
|
1 |
1 |
0 |
|
0 |
0 |
1 |
1 |
Считаем контр. биты по правилу: контр. бит с № n явл-тся битом четности тех бит кодового слова, в двоичное разложение номеров которых входит n.
Н-р, 7=1*20+1*21+1*22+0*23 , 6=0*20+1*21+1*22+0*23. Дополним снизу формируемое кодовое слово вспомогат. таблицей, в к-рой представим в двоич. виде порядковые номера бит кодового слова (читать число снизу вверх!).
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
|
2 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
|
4 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
|
8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
Первый бит - бит четности по битам 1, 3, 5, 7, 9, 11. Кол-во единичек в этих битах до заполнения равно 3. Это нечетное число, поэтому в контр. бит ставим 1, чтобы общее количество единиц было четным. Второй бит - бит четности по битам с номерами 2, 3, 6, 7, 10, 11. Тут тоже общее кол-во 1 нечетное (равно 3), поэтому ставим в 2 единицу. Аналогично 4-ый бит - бит четности по битам 4, 5, 6, 7, 12, он тоже равен 1. Восьмой бит - бит четности по битам 8, 9, 10, 11, 12, а здесь, наконец, получилось количество бит четным (3), поэтому контр. бит = 0.
Полученное кодовое слово отправитель передает в сеть. Получатель проверяет целостность данных, пересчитывая контр. биты. Если все биты верные, значит сообщение дошло не искаженным. Данный код исправляет однократную ошибку: перед просчетом контр. бит полагаем номер контр. бита, содержащего ошибку, равным нулю N=0. А затем, вычисляя очередной контр. бит с номером K, в случае, если он окажется неправильным, добавляем к вычисляемому номеру неверного бита порядковый номер контр. N=N+K. Н-р, пусть в процессе передачи инвертировался 11 бит (вместо 1 стал 0).
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
Получатель полагает N=0. Затем считает первый контр. бит (количество единичек равно трем, - нечетное), он неверный, следовательно N=N+K=0+1=1. Считает второй контр. бит, он оказался тоже неверным, => N=N+K=1+2=3. Считает четвертый контр. бит, он правильный, => N остается неизменным. Считает восьмой контр. бит, он тоже неверный, поэтому N=N+K=3+8=11. Все! Можно исправить 11-тый бит!
29. Циклический избыточный код
CRC выбирается некоторый хороший полином, называемый образующим полиномом. Коэффициенты полинома могут быть только 0 и 1, причем коэффициенты перед старшим и младшим членом полинома обязательно равны ед-це. Двоичное число, составленное из коэффициентов образующего полинома - это то число, на которое делится исходная двоичная строка.
|
10000111100010000 |
10101 |
|
10101 |
10100000111111 |
|
1011 |
|
|
00000 |
|
|
10111 |
|
|
10101 |
|
|
10110 |
|
|
10101 |
|
|
11001 |
|
|
10101 |
|
|
11000 |
|
|
10101 |
|
|
11010 |
|
|
10101 |
|
|
11110 |
|
|
10101 |
|
|
10110 |
|
|
10101 |
|
|
11 |
|
Пусть полином x4+ x2 +1. Тогда соответствующее двоичное число 10101. Пусть исходная строка, которую отправляет отправитель, 1000011110001. К исходной строке добавляется N нулей справа, где N - степень образующего многочлена. А затем делится полученное число на двоичное число, соответствующее образующему многочлену, то есть 10101, отыскивается остаток. Затем остаток вычитается из исходной (дополненной в конце) строки. Полученное сообщение-строка делится на образующий многочлен без остатка. Это сообщение передается, а поделив его на образующий многочлен, получатель определяет целостность пакета, затем отбрасывает контрольную сумму. Сложение и вычитание по модулю 2 представляют собой операцию исключающего или. Умножение: умножая на 0, получаем строку нулей, умножая на 1 - исходную строку (первый сомножитель). При делении строка меньшей длины считается <, а => осуществляется перенос очередной цифры из делимого, в частное при этом ставится ноль. Н-р, дополним исх. данные четырьмя нулями (соответственно степени образующего многочлена), при делении левые (незначащие нули не пишем). Частное нас не интересует, поэтому его можно не выписывать.
Полученный остаток отнимаем (фактически переносим) от исходной строки, дополненной нулями, получаем 10000111100010011. Это кодовое слово отправитель отправляет получателю.
30. Надежная групповая рассылка на основе меток времени Лампорта
|
A |
B |
C |
||||||
|
время |
события |
очередь |
время |
события |
очередь |
время |
события |
очередь |
|
2 |
|
|
0 |
Отправляет Sb всем |
|
1 |
|
|
|
4 |
Отправляет Sa всем |
|
1 |
Получает Sb |
Sb 0 010 |
2 |
|
|
|
5 |
Получает Sa |
Sa 4 100 |
2 |
|
|
|
Получает Sa |
Sa 4 100 |
|
7 |
|
|
|
Получает Sa |
Sb 0 010 Sa 4 100 |
6 |
Отправляет подтверждение Sa всем |
Sa 4 101 |
|
9 |
Получает Sb |
Sb 0 010 Sa 4 100 |
6 |
Отправляет подтверждение Sa всем |
Sb 0 010 Sa 4 110 |
7 |
Получает Sb |
Sb 0 010 Sa 4 101 |
|
11 |
Отправляет подтверждение Sb всем |
Sb 0 110 Sa 4 100 |
7 |
|
|
8 |
Отправляет подтверждение Sb всем |
Sb 0 011 Sa 4 101 |
|
13 |
Получает подтверждение Sa от C |
Sb 0 110 Sa 4 101 |
8 |
Получает подтверждение Sa от C |
Sb 0 010 Sa 4 111 |
9 |
|
|
|
15 |
Получает подтверждение Sa от B |
Sb 0 110 Sa 4 111 |
9 |
|
|
10 |
Получает подтверждение Sa от B |
Sb 0 011 Sa 4 111 |
|
17 |
Получает подтверждение Sb от C |
Sb 0 111 Sa 4 111 |
10 |
Получает подтверждение Sb от C |
Sb 0 011 Sa 4 111 |
|
Получает подтверждение Sb от A |
Sb 0 111 Sa 4 111 |
|
19 |
Выполняется Sb |
Sa 4 111 |
|
Получает подтверждение Sb от A |
Sb 0 111 Sa 4 111 |
13 |
Выполняется Sb |
Sa 4 111 |
|
21 |
Выполняется Sa |
|
13 |
Выполняется Sb |
Sa 4 111 |
14 |
Выполняется Sa |
|
|
23 |
|
|
14 |
Выполняется Sa |
|
15 |
|
|