Содержание к диссертации
стр.
Введение 5
1. Формальные языки и их надежностные модели 47
-
Структура формальных языков. Управляющие и информационные структуры
-
Модели ошибок в текстах на формальных
языках 25
-
Обобщенная метрика ошибок в текстах на формальных языках 34
-
Принципы количественной оценки помехозащищенности формальных языков 45 Выводы по первой главе 56
2. Методы синтаксической защиты информационных
структур 58
2.1. Самоконтролирущиеся шифры в структурах
ввода исходных данных 5<3
2.2. Контекстно-зависимые методы исправления
ошибок в самоконтролирущихся шифрах 67
-
Синтаксическая защита идентификаторов в структурах данных языков программирования 78
-
Использование помехоустойчивого кодирования для контроля ж коррекции ошибок в структурах хранения данных Выводы по второй главе 95
3. Синтаксическая защита и анализ помехозащищен
ности управляющих структур императивных языков 96
і 00
-
Синтаксическая защита ключевых слов императивных языков 95
-
Исправление синтаксических ошибок в текстах на языках управления
-
Синтаксическая защита управляющих структур языков программирования
-
Методика анализа помехозащищенности управляющих структур языка на основе обобщенной метрики ошибок № 4 Выводы по третьей главе . 1ЪЬ
4. Практические приложения методов контроля и ди
агностики синтаксически защищенных структур в
системах управления /3 7
-
Программные методы контроля ошибок в системе АОФОР-МЭЙ ІЗ 7
-
Анализ помехозащищенности языков управления заданиями в системах АСФОР-МЗИ и
ЭКСПРЕСС І5в
-
Программная система защиты архивных наборов данных на Щ 16>&
-
Методика помехоустойчивого кодирования информации в высоконадежных системах накопителей на Щ і 75
-
Методы контроля управляющих структур алгоритмов в структурном подмножестве ПЛ/І і'8? Выводы по четвертой главе 490
Заключение 49 і
Список литературы ygj
Приложение I. Документы, подтверждающие внедрение
и использование результатов работы 2.03
Приложение 2. Комплекс автоматизированных программных средств контроля и коррекции архивных дисковых наборов данных (инструкция по эксплуатации) 212
Приложение 3. Методика подготовки архива в автомати
зированных системах АОФОР-МЭИ и ЭКШЕЕСС (руко
водство администратора) 2.Z2
Введение к работе
В "Основных направлениях экономического и социального развития СССР на I98I-I985 годы и на период до 1990 года", в решениях Пленумов ЦК КПСС и других партийных и правительственных документах поставлена задача совершенствования вычислительной техники, ее элементной базы и математического обеспечения, средств и систем сбора, передачи и обработки информации [^46,49,45 1 .
Среди проблем, связанных с совершенствованием систем управления, одно из важнейших мест занимает проблема повышения качества этих систем, тесно связанная с проблемой надежностного обеспечения происходящих в них информационных процессов.
В данной работе рассматриваются системы управления, обладающие следующими основными отличительными признаками: дискретностью; использованием при проектировании систем и при доступе к ним формальных языков; использованием баз данных; наличием коллективного доступа к системам, приводящего к необходимости обрабатывать массовые потоки запросов пользователей.
Примерами систем выделенного класса являются автоматизированные системы управления вычислительными ресурсами для обработки заданий пользователей, системы управления базами данных, автоматизированные системы обработки данных, пакеты прикладных программ и т.п.
Можно выделить такие основные виды информационных процессов в системах управления: сбор и ввод информации; хранение информации; передача и переработка информации; отображение (вывод) информации.
Сделаем краткий обзор выполненных к настоящему времени на-учных исследований в области надежностного обеспечения информационных процессов в системах управления. При сборе и вводе информации наиболее "узкими" местами являются этапы подготовки первичных документов, переноса документов на машинные носители (перфокарты, перфоленту, магнитную ленту) и их собственно ввода в вычислительную систему j_77j. Наибольшее распространение в настоящее время получили алгоритмические методы обеспечения достоверности вводимой информации, рассматривающие задачи обеспечения достоверности как самостоятельные задачи обработки данных и включающие в себя средства контроля ввода информации, а также коррекции ошибок. Этим вопросам посвящен ряд работ советских и зарубежных ученых В.М.Глушкова, С.И.Самойленко, Ю.Н. Мельникова, В.В.Липаева, В.И.Скурихина, В.А.Литвинова, Г.А.Миронова, Дж. Мартина, К. Рида, Д.Джадда и др.
Основой для разработанных методов обеспечения достоверности вводимой (исходной) информации является использование естественной или искусственной информационной избыточности. Естественная избыточность либо отражает внутренние логические связи между элементами информации, либо вводится на языковом уровне при установлении правил представления информации. Искусственная избыточность вносится в информацию специально для придания ей свойств устойчивости к ошибкам (помехоустойчивости). Обычно искусственная избыточность образуется за счет добавления к информации контрольной части. Такую операцию называют помехоустойчивым кодированием информации (или просто кодированием) , а правило получения контрольной части - помехоустойчивым кодом (или просто кодом).
В настоящее время разработано немало методов помехоустойчивого кодирования числовой [86, 20, 75, 56, 29, 64, 35, 94, IOlJ и символьной [б4, 40, 41, во] информации. Хорошим обзором таких методов является [б]. Большинство из этих методов основано на методе контроля по модулю с весовыми коэффициентами и рассчитано только на обнаружение ошибок. Недостатком методов, дозволяющих автоматизировать процесс исправления ошибок, является в первую очередь то, что применение каждого из них дает возможность исправлять лишь один тип ошибок: одиночные ошибки замещения (одиночные транскрипции) [54, 38, 31, 76, 1б], перестановки (транспозиции) соседних символов [юо], одиночные вставки и выпадения символов [зэ]. многократные ошибки замещения [15, 93, 54, 38J. Второй существенный недостаток указанных методов - это то, что они ориентированы на работу только с числовой информацией.
Вопросам надежностного обеспечения процессов хранения информации в системах управления во внешних запоминающих устройствах (ЗУ) (магнитных дисках, магнитных лентах и др.) в литературе посвящено не так много работ. Между тем специфика ошибок3 возникающих в ЗУ на магнитных дисках [48, 74, 70], не позволяет использовать для их коррекции ни один из разработанных к настоящему времени кодов. Характерное для большинства из этих ошибок сочетание пакетного асимметрического искажения информации с искажением типа выпадения - вставки символа превышает корректирующие способности,известных методов кодирования [54, 17, 47,
38, II, 22, 58, 66, 91, 9з]. Так, в работах [l7, 47, 10,
22, 58, 66, 91J предлагаются коды, исправляющие пакеты асимметрических ошибок, в работах [54, 38, 93J - коды, исправляющие -8-многократные ошибки замещения. В существующих системах управления, как правило, не разрабатывают специальных средств защиты информации при хранении ее во внешних 37, а ограничиваются теми стандартными средствами, которые входят в состав современных вычислительных систем. Эти средства, однако, либо обладают только относительно высокое обнаруживающей способностью и не могут быть применены для исправления ошибок [23, 30j, либо способны исправлять только ошибки минимальной кратности - одиночные ошибки замещения [зо].
Вопросы надежностного обеспечения процессов передачи, переработки и вывода информации в системах управления наименее изучены. Оставляя в стороне такие (тоже немаловажные) составляющие этих процессов, как хранение информации в оперативной памяти вычислительной системы (ВС), передачу информации внутри ВО и между различными ВС, вывод информации на внешние носители (бумагу, экран дисплея и др.), обработку информации процессором ВС, выделим этап составления текста, описывающего процесс переработки информации на некотором формальном языке, принятом в системе управления. Этот текст может быть, например, программой на каком-нибудь языке программирования либо заданием на командном языке системы управления. Акцентирование нашего внимания именно на этом этапе объясняется тем, что согласно последним оценкам [28j стоимость программного обеспечения вычислительных систем значительно превышает стоимость аппаратуры и продолжает расти, в то время как существующие методы оценки правильности (корректности) программ (тестирование, формальное доказательство корректности) все еще неудовлетворительны. В настоящее время около 70/6 общих затрат на создание программного обе- спечения сложных систем приходится на этап сопровождения, на котором осуществляются корректировка и модификация программ [Зб], что свидетельствует о недостаточном уровне надежности разработок.
Примерно полтора десятка лет назад начала развиваться концепция структурного программирования [96, 36, 18, 28, 9, 81, 60J, ставшая в настоящее время одной из ведущих методологий разработки программного обеспечения [бб], позволяющей получать высоконадежные и легкомодифшщруемые программы. Поскольку подавляющее большинство наиболее широко распространенных в настоящее время языков программирования, в частности Ш/І [вб], Фортран [82J, разрабатывались без учета концепций структурного программирования, весьма актуальной становится задача создания структурных подмножеств таких языков. Хотя первые опыты такого рода уже появились L95J, работа в этом направлении должна быть продолжена.
Другим важным аспектом надежностного обеспечения процессов переработки информации в системах управления является выработка методов оценки помехозащищенности формальных языков таких систем и в первую очередь языков управления, к которым относятся языки управления заданиями операционных систем, языки манипулирования данными систем управления базами данных, командные языки различных автоматизированных систем и другие подобные им виды языков. Использование этих методов совместно с всегда присутствующей в текстах на формальных языках естественной избыточностью может способствовать разработке методов автоматизации процесса исправления ошибок в таких текстах. Следует заметить, что оба эти круга вопросов практически не освещались в литера- -10-туре.
Среди отечественных и иностранных ученых, занимавшихся проблемами надежностного обеспечения процессов переработки информации в системах управления, необходимо назвать А.П.Ершова, В.В. Липаева, С.С.Лаврова, Э.Дейкстру, Н.Вирта, К.Хоора.
Резюмируя наш краткий обзор работ ш надежностному обеспечению информационных процессов, следует отметить, что большинство из них посвящено разработке и реализации методов, решающих задачи обнаружения ошибок на различных этапах информационных Фоцвссов коррекции ошибок, ~зляет,%я рт чеур1** эрсал*-' применимость их для исправления лишь определенного класса ошибок. Этот недостаток мешает их широкому практическому иепользо- .. ., СИСТв'ШХ уПрощлвНИЯ.
Следует далее отметать, что общим принципом построения методов надежностного обеспечения информационных процессов является использование избыточности, как естественной, так и искусственной. Причем естественная избыточность для целей контроля и коррекции используется существенно реже, хотя максимального эффекта можно добиться лишь применением как одного, так и другого видов избыточности. Для решения же задачи контроля и коррекции текстов на формальных языках естественная избыточность является единственным инструментом.
Наконец, к недостаткам разобранных работ можно отнести и то, что ни в одной из них вопросы надежностного обеспечения на различных этапах информационных процессов в системах управления не решаются комплексно, а охватывают лишь некоторые из них. Между тем, все виды информационных процессов в системах управления характеризуются, как правило, одной общей чертой: - II - все задействовании» в этих процессах структуры (потоки исходных данных, наборы данных на внешних носителях, тексты на формальных языках и т.п.) строятся в соответствии с некоторым правилом (кодом) либо формальной грамматикой, позволяющими разделять допустимые и не допустимые для данной системы управления структуры. Назовем это свойство синтаксической защищенностью. Будем далее называть информационными виды структур, являющиеся объектами процессов ввода, хранения, описания, передачи и вывода данных в системах управления (например, структуры ввода и хранения данных, структуры описания данных в языках программирования и т.п.). Назовем, соответственно, управляющими такие виды структур, которые задают описание процессов переработки информации в системах управления (например , программы, составленные на языках программирования, совокупности предложений командных языков и т.п.).
Целью данной работы является исследование и разработка методов контроля и диагностики информационных и управляющих структур в использованием избыточнооти на уровне формального языка, описывающего эти структуры. Для достижения указанной цели решаются следующие основные задачи:
Разработка и исследование моделей и методов анализа формальных языков с учетом их синтаксической защищенности; алгоритмизация процедур анализа.
Разработка эффективных синтаксически защищенных информационных и управляющих структур, используемых в системах управления, и принципов алгоритмизации процедур контроля и коррекции ошибок в таких структурах. -12-3. Реализация результатов исследований в рамках автоматизированной системы обработки массовых потоков студенческих заданий на ЕС ЭВМ, программной системы защиты архивной информации при хранении ее в накопителях на магнитных дисках и инструментального комплекса поддержки структурного программирования на языке
ПЛ/І.
Поставленная задача решается на базе системного подхода к разработке методов контроля и диагностики информационных и управляющих структур, основанного на: обобщенной формальной модели ошибок в информационных и управляющих структурах; обобщенной метрике ошибок; использовании при практической реализации концепций структурного программирования и проектирования "сверху - вниз" И-
В отличие от известных подходов к проблеме автоматизации контроля и диагностики информационных и управляющих структур данный подход позволил получить следующие основные результаты:
1) проанализировать формализованную модель процесса проек тирования сложных систем, рассматривающего его как разработку текста на некотором формальном языке, исследовать понятие син таксического расстояния и доказать, что оно; может являться ос новой обобщенной метрики ошибок в текстах на ФЯ; разработать общую методику анализа помехозащищенности ф# и алгоритмы ее количественной оценки; предложить общую методику кодирования самоконтролируй-щихся шифров и методы алгоритмизации процедур контроля и исправления ошибок в них с использованием структурной избыточности -13-шифра и контекстной информации; исследовать информационные модели ошибок в структурах хранения данных на внешних магнитных носителях и предложить принципы аппаратной реализации кодов с исправлением пачек асимметрических ошибок в высоконадежной системе накопителей на ВД; разработать метод програшного контроля и коррекции ар-хивннх наборов данных в НМД, позволяющий исправлять ошибки практически любых типов и основанный на каскадном кодировании информации; рассмотреть методы синтаксической защиты управляющих структур алгоритмов и разработать принципы алгоритмизации контроля структурированности программ.
На основе проведенных исследований разработаны и внедрены в автоматизированных системах обработки массовых потоков студенческих заданий АСФОР-МЭИ и ЭКСПРЕСС программы контроля и коррекции ошибок в шифрах заданий пользователей и в текстах на командных языках систем (общий объем программ составляет 30К байт). Разработаны программа сбора статистики ошибок в НВД (6К байт) и (совместно с С.Д.Захаровым) комплекс автоматизированных средств контроля ж коррекции архивных дисковых наборов данных КАСКАД (ЗбКі байт). Разработаны программы для компоненты контроля структурированности инструментального комплекса автоматизированной разработки программ ИКАР-С (37К байт, программное обеспечение системы ИКАР-С разрабатывалось автором совместно с Е.Е. Карпович и С.Б.Ивановым).
Система АС4ЮР-МЭЙ используется в учебном процессе на всех факультетах МЭИ (на кафедрах Прикладной математики и Теоретической механики) с 1979 г., система ЭКСПРЕСС используется в учеб- -14-ном процессе в МЭИ с 1984 г. Системы КАСКАД и ИКАР-С переданы для использования в ЇЇНИИММ (г.Пенза). Принципы аппаратной реализации кодов с исправлением ошибок в сочетании со средствами восстановления синхронизации использованы при создании высоконадежной системы ЦМД в организации п/я A-II78.
Работа состоит из введения, четырех глав, заключения, списка литературы, включающего 101 название, и трех приложений. Основная часть содержит 1^9 страниц машинописного текста, 29 рисунков, 10 таблиц. Приложения составляют 38 страниц.
В первой главе рассматриваются надежностные модели формальных языков систем управления. Исследуются информационная и формально-лингвистическая модели ошибок в текстах на формальных языках, а также обобщенная метрика ошибок, использующая понятие синтаксического расстояния между текстами. Формулируются утверждения о самоконтролирующихся и самокорректирующихся языках, являющиеся обобщением теорем Хэмминга о помехоустойчивых кодах. Излагаются принципа количественной оценки помехозащищенности формальных языков, используемые при их анализе и синтезе.
Вторая глава посвящена разработке методов контроля и диагностики синтаксически защищенных структур ввода, описания и хранения данных в системах управления. Излагается методика выбора метода кодирования и оценки эффективности самоконтролирующихся шифров при вводе исходных данных. Рассматриваются принципы алгоритмизации кодирования, контроля и коррекции самоконтролирующихся шифров. Описываются методы зашиты идентификаторов и имен в структурах данных языков программирования высокого уровня. Предлагается метод контроля и коррекции данных при хранении их в накопителях на магнитных дисках, основанный на статистическое -15 -модели ошибок. Излагаются принципы алгоритмизации методов защиты для оперативной и архивной информации.
В третьей главе исследуются вопросы синтаксической защиты и анализа помехозащищенности управляющих структур формальных языков. Предлагается подход к автоматизации процесса исправления ошибок в текстах на языках управления. Рассматриваются методы синтаксической защиты управляющих структур в языках программирования высокого уровня. Описывается общая методика анализа помехозащищенности формальных языков, на основе его многоуровневого иерархического представления и обобщенной метрики ошибок.
Четвертая глава посвящена изложению результатов практического приложения методов контроля и диагностики синтаксически защищенных информационных и управляющих структур. Рассматриваются программные методы контроля и коррекции ошибок в системе АСФОР-МЭИ. Даются оценки помехозащищенности командных языков систем АСФОР-МЗИ и ЭКСПРЕСС. Описывается программная система защиты архивных наборов данных в накопителях на магнитных дисках. Рассматриваются методы контроля управляющих структур алгоритмов в структурном подмножестве языка программирования ПЛ/І.
В заключении приводятся основные результаты, полученные в ходе выполнения работы.
Приложение I содержит акты о внедрении результатов диссертационной работы.
В приложении 2 помещена инструкция по эксплуатации средств контроля и коррекции архивных дисковых наборов данных.
В приложении 3 изложена методика подготовки к эксплуатации архива автоматизированных систем обработки массовых потоков студенческих заданий АСФОР-МЗИ и ЭКСПРЕСС.
Данная работа выполнена на кафедре Прикладной математики Мой. Результаты работы использовались в хоздоговорных НИР: J& 159/76 с предприятием п/я A-II78 и № 42/77 с Всесоюзным НИИ проблем организации и управления, в госбюджетных НИР по теме П.6.3.3.4 координационного плана НИР Минвуза СССР и по теме I.I2.2 координадионного плана НИР АН СССР и в работах по договорам о социалистическом содружестве с Пензенским НИИ математических машин.
Основные результаты диссертации докладывались и обсуждались на: научных семинарах кафедры Прикладной математики МЭИ в 1976-1984 гг.; ІУ Всесоюзной школе-семинаре по вычислительным сетям (г.Ташкент, 1979 г.);
Юбилейной научно-технической конференции МЭИ (г.Москва, 1980 г.);
Ш Всесоюзной конференции по теории кодирования и передачи информации (г.Куйбышев, 1981 г.).
Похожие диссертации на Разработка методов контроля и диагностики синтаксически защищенных информационных и управляющих структур в системах управления
