Определение границ предметной области
Как сказано во врезке, мы намерены заняться криптоанализом - процессом преобразования зашифрованного текста в обычный. В общем случае процесс дешифровки является чрезвычайно сложным и не поддается даже самым мощным научным методам. Существует, например, стандарт шифрования DES (Data Encryption Standard, алгоритм шифрования с закрытым ключом, в котором используются многочисленные подстановки и перестановки), который, по-видимому, свободен от слабых мест и устойчив ко всем известным методам взлома. Но наша задача значительно проще, поскольку мы ограничимся шифрами с одной подстановкой.
В качестве первого шага анализа попробуйте решить (только честно, не заглядывая вперед!) следующую криптограмму записывая, каждый ваш шаг:
Q AZWS DSSC KAS DXZNN DASNN
Подсказка: буква w соответствует букве v исходного текста. Перебор всех возможных вариантов совершенно лишен смысла. Предполагая, что алфавит содержит 26 прописных английских букв, получим 26! (около 4.03х1026) возможных комбинаций. Следовательно, нужно искать другой метод решения, например, использовать знания о структуре слов и предложений и делать правдоподобные допущения. Как только мы исчерпаем явные решения, мы сделаем наиболее вероятное предположение и будем продвигаться дальше. Если обнаружится, что предположение приводит к противоречию или заводит в тупик, мы вернемся назад и сделаем другую попытку.
| Требования к системе криптоанализа
Криптография "изучает методы сокрытия данных от посторонних" [3]. Криптографические алгоритмы преобразовывают сообщения (исходный текст) в зашифрованный текст (криптограмму) и наоборот. Одним из наиболее общеупотребительных (еще со времен Древнего Рима) криптографических алгоритмов является подстановка. Каждая буква в алфавите исходного текста заменяется другой буквой. Например, можно циклически сдвинуть все буквы алфавита: буква A заменяется на B, B на C, a Z на A. Тогда следующий исходный текст: CLOS is an object-oriented programming language превращается в криптограмму: DMPT jt bo pckfdu-psjfoufe qsphsbnnjoh mbohvbhf Чаще всего замена делается менее тривиальным образом. Например, A заменяется на G, B на J и т.д. Рассмотрим следующую криптограмму: PDG TBCER CQ TCK AL S NGELCH QZBBR SBAJG Подсказка: буква C в этой криптограмме соответствует букве O исходного текста. Существенно упрощает задачу предположение о том, что для шифрования текста использован алгоритм подстановки, поскольку в общем случае процесс дешифровки не будет столь тривиальным. В процессе расшифровки приходится использовать метод проб и ошибок, когда мы делаем предположение о замене и рассматриваем его следствия. Удобно, например, начать расшифровку с предположения о том, что одно- и двухбуквенные слова в криптограмме соответствуют наиболее употребительным словам английского языка (I, a, or, it, in, of, on). Подставляя эти предполагаемые буквы в другие слова, мы можем догадаться о вероятном значении других букв. Например, если трехбуквенное слово начинается с литеры O, то это могут быть слова one, our, off. Знание фонетики и грамматики также может способствовать дешифровке. Например, следование подряд двух одинаковых литер с очень малой вероятностью может означать qq. Наличие в окончании слова буквы g позволяет сделать предположение о наличии суффикса ing. На еще более высоком уровне абстракции логично предположить, что словосочетание it is более вероятно, чем if is. Необходимо учитывать и структуру предложения: существительные и глаголы. Если выясняется, что в предложении есть глагол, но нет существительного, которое с ним связано, то нужно отвергнуть сделанные ранее предположения н начать поиск заново. Иногда приходится возвращаться назад, если сделанное предположение вступает в противоречие с другими предположениями. Например, мы допустили, что некоторое двухбуквенное слово соответствует сочетанию or, что в дальнейшем привело к противоречию. В этом случае мы должны вернуться назад и попытаться использовать другой вариант расшифровки этого слова, например, on. Требования к нашей системе: по данной криптограмме, в предположении, что использована простая подстановка, найти эту подстановку и (главное) восстановить исходный текст. |
Вот наше решение, шаг за шагом:
1. Используя подсказку, заменим w на v.
Q AZVS DSSC KAS DXZNN DASNN
2. Первое слово из одной буквы, вероятна, A или I; предположим, что это A:
A AZVS DSEC KAS DXZNN DASNN
3. В третьем слове должны быть гласные звуки и вероятно, что это двойные буквы. Это не могут быть UU или II, а также AA (буква A уже использована). Попробуем вариант EE.
A AZVE DEEC KAE DXZNN DAENN
4. Четвертое слово состоит из трех букв и оканчивается на E, это очень похоже на слово THE.
A HZVE DEEC THE DXZNN DHENN
5. Во втором слове нужна гласная, и здесь подходят только I, O, U (буква A уже использована). Только вариант с буквой I дает осмысленное слово.
A HIVE DEEC THE DXINN DHENN
6. Можно найти несколько слов с двойной буквой E из четырех букв (DEER, BEER, SEEN). Грамматика требует, чтобы третье слово было глаголом, поэтому остановимся на SEEN.
A HIVE SEEN THE SXINN SHENN
7. Смысл в полученном предложении отсутствует, поскольку улей (HIVE) не может видеть (SEEN), значит, где-то по дороге мы сделали ошибку. Похоже, что выбор гласной буквы во втором слове был неверен, и приходится вернуться назад, отменив самое первое предположение - первым словом должно быть I. Повторяя все остальные наши рассуждения практически без изменений мы получаем:
I HAVE SEEN THE SXANN SHENN
8. Посмотрим на два последних слова. Двойная буква S в конце не дает осмысленного значения и к тому же уже использована ранее, а вот LL дает осмысленное слово.
I HAVE SEEN THE SXALL
SHELL
9. Из грамматических соображений очевидно, что оставшееся слово - прилагательное. Анализируя шаблон S?ALL, находим SMALL.
I HAVE SEEN THE SMALL SHELL
Таким образом, решение найдено. Анализируя процесс решения, мы можем сделать три наблюдения:
Для решения применялись разнообразные знания: о грамматике, о составе слов, о чередовании согласных и гласных.
Сделанные предположения регистрировались, потом мы применяли к ним имеющиеся у нас знания и смотрели, что из этого получается.
Мы подходили к делу наугад, приспосабливаясь к обстановке. Иногда делались выводы от общего к частному (словом из трех букв, оканчивающимся на E будет, вероятно, THE), а иногда от частного к общему (?EE? может соответствовать DEER, BEER, SEEN, но глаголом из них является только SEEN).
Изложенный подход известен как метод информационной доски. Он впервые был предложен Ньюэллом в 1962 году, а позднее был использован Редди и Ерманом в проектах Hearsay и Hearsay II по распознаванию речи [4]. Эффективность метода подтвердилась, и он был использован в других областях, включая интерпретацию сигналов, трехмерное моделирование молекулярных структур, распознавание образов и планирование [5]. Метод показал хорошие результаты в представлении описательных знаний; он более эффективен с точки зрения памяти и времени по сравнению с другими подходами [6].
Информационная доска вполне подходит на роль среды разработки (см. главу 9). Попробуем теперь зафиксировать архитектуру этого метода в виде системы классов и механизмов их взаимодействия.
Система управления движением выполняет две главные функции: выбор маршрутов железнодорожных перевозок и контроль систем, обеспечивающих перевозки. Эти функции включают: планирование перевозок, контроль местонахождения поездов, контроль за перевозками, предотвращение конфликтов, прогнозирование нарушении, регистрацию всех операций. На рис. 12-1 показана схема основных элементов системы управления движением [2].
Рис. 12-1. Система управления движением
Система анализа и отображения информации на локомотиве состоит из множества дискретных и аналоговых датчиков для контроля за такими параметрами, как температура, давление масла, количество топлива, напряжение и сила тока на генераторе, число оборотов вала двигателя в минуту, температура воды, тяговая мощность. Значения параметров с датчиков поступают к машинисту через дисплейную систему, а к диспетчеру и обслуживающему персоналу вне поезда - через сеть. Предупреждение или сигнал тревоги выдается и регистрируется всякий раз, когда показания датчика выходят за пределы нормального режима. Журнал показаний датчиков используется при проведении эксплуатационных работ и для управления расходом топлива.
Система управления энергией в режиме реального времени подсказывает инженеру поезда, как наиболее эффективно использовать установку. Входными данными для этой системы являются: профиль и качество пути, ограничения по скорости, расписание, загрузка поезда, максимальная развиваемая мощность. Исходя из этих данных, система может определить оптимальный по расходу топлива режим работы двигательных установок, согласующийся с заданным расписанием и требованиями безопасности. Рекомендации системы, профиль и качество пути, местоположение и скорость поезда могут отображаться с помощью бортовой системы индикации.
Бортовая система индикации обеспечивает человеко-машинный интерфейс для машиниста. На нее может выводиться информация из системы анализа и отображения информации на локомотиве, системы управления энергией и блока управления данными.
Специальные клавиши позволяют машинисту просматривать различные данные.
Блок управления данными представляет собой шлюз между всеми бортовыми системами поезда и глобальной сетью передачи данных, к которой подключены все поезда, диспетчеры и прочие пользователи.
Отслеживание маршрутов движения поездов осуществляется с помощью подключенных к сети передачи данных ответчиков местоположения и глобальной спутниковой системы указания местоположения (GPS, Global Positioning System) Navstar. Система анализа и отображения информации на локомотиве может вычислять пройденный путь с помощью счетчика, подсчитывающего число оборотов колеса. Эта информация дополняется данными ответчиков местоположения, которые размещены через каждый километр пути или чаще (на важнейших развилках). Ответчики передают информацию о себе на проходящие поезда (используя блок управления данными), что позволяет более точно определить местоположение. Кроме того, поезд может быть оснащен приемниками GPS, с помощью которых его географическое положение может быть определено с точностью до метра.
Блок интерфейса путевых устройств размещается там, где есть какое-либо управляемое устройство (например, стрелка), или датчик (например, инфракрасный датчик для обнаружения перегрева подвесок колес). Каждый блок интерфейса получает команды (например, команды на включение и выключение сигнала) от локального наземного контроллера. Устройства могут быть переведены в ручной режим управления. Кроме того, каждое устройство может сообщать свои установочные параметры. Наземный контроллер транслирует информацию на блоки интерфейса путевых устройств и обратно, а также на проходящие мимо поезда и обратно. Контроллеры расположены вдоль железнодорожного пути через такие расстояния, чтобы любой поезд всегда находился в зоне действия хотя бы одного из них.
Каждый наземный контроллер передает свою информацию на объединенную систему управления сетью. Связь между системой управления сетью и наземным контроллером может осуществляться по радио в микроволновом диапазоне, по наземным линиям или по оптоволокну в зависимости от удаленности данного контроллера.
Система управления сетью обеспечивает функционирование всей сети. Она может автоматически направлять информацию по другому маршруту в сети, если на одном из путей произойдет отказ оборудования,
Система управления сетью, в свою очередь, подсоединяется к одному или нескольким диспетчерским центрам, которые объединены в систему управления операциями. Система управления сетью соединена и с другими пользователями. В системе управления операциями диспетчеры могут задавать маршруты поездов и отслеживать их передвижение. Для управления различными участками выделяются отдельные диспетчеры; каждая диспетчерская управляющая консоль отвечает за одну или несколько территорий. Маршрутизация поездов подразумевает выдачу инструкций для автоматического перевода поезда с пути на путь, установку ограничения скорости, управление пропуском автомобилей на переездах, разрешение и запрещение движения поезда в зависимости от занятости определенных участков пути. Диспетчеры могут наблюдать за состоянием путей впереди по маршруту поезда и передавать эту информацию машинисту. Поезда могут быть остановлены системой управления операциями (вручную диспетчерами или автоматически), когда обнаруживается опасность (выход поезда из графика, повреждение пути, возможность столкновения). Диспетчеры могут также вызвать на экран любую информацию, доступную машинистам отдельных поездов, разослать распоряжения по движению, установить параметры путевых устройств и пересмотреть план движения.
Расположение путей и путевое оборудование могут со временем меняться. Число поездов и маршруты их движения могут изменяться ежедневно. Система должна обеспечивать возможность подключения новых датчиков, сетей и оборудования, выполненных по более совершенным технологиям.
На врезке сформулированы основные требования к системе управления движением поездов. Очевидно, они сильно упрощены. На практике детальные требования к большой системе вырабатываются после демонстрации жизнеспособности программного решения проблемы. При этом анализ отменяет сотни человеко-месяцев труда с участием экспертов в данной области и пользователей системы.
В конечном счете требования к системе могут состоять из тысяч страниц документации, специфицирующей не только базовое поведение, но и такие детали, как макеты форм интерфейса.
Но даже исходя из наших упрощенных требований, мы можем сделать два замечания о разработке системы управления движением:
Архитектура должна быть открыта для развития.
Реализация должна опираться на существующие стандарты.
Наш опыт разработки больших систем показывает, что первоначальная формулировка требований никогда не бывает полной, она всегда в некоторой степени неопределенна и противоречива. Соответственно, мы должны быть готовы управлять возникающими в процессе разработки неопределенностями. Мы настоятельно рекомендуем осуществлять эволюцию подобных систем в виде пошагового, итеративного процесса. Как уже говорилось в главе 7, сам цикл разработки дает пользователям и разработчикам возможность понять, какие требования на самом деле существенны; именно процесс разработки, а не упражнения в чистописании спецификаций в отсутствии готовой частичной реализации или прототипа. Кроме того, необходимо учитывать, что на создание большой системы может быть затрачено несколько лет. За это время сильно изменится аппаратная часть [В действительности для многих систем такого уровня сложности характерно, что в них входят компьютеры самых разнообразных типов. Хорошо продуманная и стабильная архитектура смягчает риск смены техники в процессе разработки, которая сплошь и рядом происходит в быстро меняющемся компьютерном мире. Новые модели приходят и уходят, поэтому важно четко представлять границу между техникой и программами, чтобы можно было ввести в систему новые компьютеры или контроллеры, снижающие затраты или улучшающие характеристики работы, и сохранить при этом целостность архитектуры]. Поэтому требования к программе должны предусматривать адаптацию к новой технике. Бессмысленно создавать элегантную архитектуру для аппаратуры, которая гарантированно устареет за время разработки. Мы считаем, что в архитектуру программной системы следует включать только те аппаратные особенности, которые непосредственно опираются на существующие стандарты: связь, сети передачи данных, графику и протокол работы датчиков.Для совершенно новых систем иногда Приходится становиться первопроходцами аппаратных и программных средств. Это приводит к повышению риска, который для большинства систем и без того высок. Разработка программного обеспечения, особенно, когда речь идет об успешном завершении большого приложения, неизбежно связана с риском, и наша цель - снизить этот риск до минимума.
Очевидно, что мы не сможем подробно рассмотреть все вопросы анализа и проектирования описанной системы в одной главе или даже в одной книге. Так как наша задача - показать, как работают обозначения и методология, сосредоточимся на построении гибкой архитектуры изучаемой области.
