Введение к работе
Актуальность проблемы. Одной из особенностей нашего времени является грандиозный бум информационных технологий. Использование вычислительных систем становится повсеместным, качество их неуклонно возрастает (постоянный рост производительности микропроцессоров, объемов и быстродействия оперативной и внешней памяти); стоимость всех вычислительных ресурсов неизменно снижается, а число пользователей увеличивается — вот лишь несколько основных признаков этого информационного взрыза. Естественным следствием происходящих процессов является: постоянное увеличение объемов информации, хранимой на носителях (магнитных, оптических и др.) и передаваемой по каналам связи, что ужесточает требования к процедурам контроля целостности данных - последние должны выявлять как можно.большее число искажений а информационных последовательностях, обеспечивая при этом максимальную производительность; появление нового программного обеспечения (ПО) и постоянное совершенствование уже выпущенных программных продуктов требует ускорения процессов vix тестирования и отладки без снижения качества тестирования; неизменное совершенствование элементной базы компьютеров и сокращение размеров элементов предъявляет жесткие требования к средствам их тестового диагностирования, которые должны обеспечивать высокую достоверность контроля, иметь высокое быстродействие, регулярную структуру, высокую надежность и низкую стоимость; рост объемов информации, хранимой в базах данных, требует высокопроизводительных средств добавления, поиска и удаления элементов.
Традиционно проблемы контроля информации и обработки таблиц для систем управления базами данных решаются при помощи алгоритмов хэширования и генерации псевдослучайных последовательностей (ПСП), а значит, задача разработки новых классов таких алгоритмов, отличающихся от используемых в настоящее время большим быстродействием, более эффективной программной и аппаратной реализацией и не уступающим им с точки зрения достоверности, является весьма актуальной.
В настоящее время известно немало различных алгоритмов хэширования и генерации псевдослучайных последовательностей. Недостатком большинства из них является отсутствие эффективных методов наращивания разрядности. Эта проблема становится особенно острой сейчас, когда происходит переход на 64-х разрядную обработку данных, а большинство существующих алгоритмов, реализованных программно, - 32-х разрядные. Алгоритмы сигнатурного анализа, отличающиеся высокой достоверностью контроля и широко применяемые при контроле ЦИФОСВЫ/
устройств, оказываются неэффективными при тестировании ПО вследствие неудобства их программной реализации.
Предлагаемые в настоящей работе алгоритмы хэширования и генерации ПСП свободны от этих недостатков. Достоверность разработанных алгоритмов хэширования аналогична алгоритмам сигнатурного анализа или алгоритмам CRC (циклические избыточные коды), а производительность оказывается существенно большей (см. далее). Предлагаемые алгоритмы генерации ПСП характерны хорошими статистическими характеристиками и удобны как для программных, так и для аппаратных приложений.
Целью диссертационной работы является разработка и исследование новых алгоритмов хэширования и генерации ПСП для задач контроля и обработки таблиц, которые позволяли бы создание генераторов ПСП и хэш-функций, с заданными характеристиками (период генерируемой последовательности, число коллизий), характеризовались высокопроизводительной программной реализацией, допускали легкую, недорогую и надежную аппаратную реализацию, выгодно отличаясь от используемых ныне аналогов. -
Методы исследования. В диссертационной работе используются методы математической логики, теории множеств, теории групп, теории конечных полей и математической статистики.
і Научная новизна. Разработаны и описаны в виде рекуррентных соотношений
и блок-схем три класса алгоритмов хэширования и генерации ПСП; предложенные алгоритмы автор подразделяет на базовые и производные, выявлен ряд свойств разработанных алгоритмов, в частности, доказано, что доля обнаруживаемых ошибок во входных последовательностях для предложенных алгоритмов соответствует таковой для алгоритмов сигнатурного анализа и алгоритмов CRC, получена зависимость периода последовательности, порождаемой генераторами базового класса от разрядности и ряда параметров алгоритма генерации, исследованы статистические характеристики генерируемых последовательностей. Показано, что трудоемкость программной реализации разработанных алгоритмов характеризуется линейной зависимостью от разрядности обрабатываемых последовательностей и параметров алгоритма. Также показаны преимущества предлагаемых алгоритмов перед аналогами в различных областях применения.
Основными положениями работы, выносимыми на зашиту, являются:
-
Три класса алгоритмов хэширования и генерации последовательностей. * -
-
Исследование хэш-функций, реализующих разработанные алгоритмы.
+
-
Исследование периода и статистических характеристик генерируемых последовательностей
-
Прикладные аспекты (исследование трудоемкости программной реализации, методики проектирования хэш-функций для контроля целостности и обработки таблиц, методика тестирования ПО)
Практическая значимость работы. Предложено два способа программной реализации разработанных алгоритмов хэширования и генерации ПСП (приведены примеры кода на языках Паскаль, С и Ассемблер). Разработана методика тестирования программного обеспечения, основанная на применении предлагаемых алгоритмоа генерации и хэширования. В рамках фанта Российского фонда фундаментальных исследований написана программа для контроля целостности файлов SIGNER. EXE. Предложена методиха проектирования устройств, реализующих разработанные алгоритмы хэширования и генерации, которые по сравнению с аналогами имеют меньшую стоимость, большее быстродействие и простоту наращивания разрядности; устройства, реализующие-некоторые алгоритмы хэширования, защищены патентом России на изобретение №2087030. Также предложена логическая схема многофункционального секционируемого устройства для систем тестового диагностирования цифровых устройств.
Степень обоснованности и достооорность научных положений, выводов и рекомендаций, сформулированных в диссертационной работе подтверждена математически строгим доказательством основных свойств разработанных алгоритмов, достоверностью результатов экспериментальных исследований свойств, не поддающихся априорной оценке (например, статистических характеристик генерируемых последовательностей), а также практической реализацией предложенных алгоритмов хэширования и генерации псевдослучайных последовательностей.
Реализация результатов исследования. Исследования проводились в рамках ряда научно-исследовательских работ по разработке алгоритмоа хэширования и генерации ПСП для контроля, выполняемых на кафедре "Компьютерные системы и технологии" МИФИ и в Центре новых информационных технологий МИФИ.
Некоторые алгоритмы хэширования и генерации ПСП были приняты к использованию Особым конструкторским бюро систем автоматизированного проектирования (ОКБ САПР) для применения в подсистемах контроля целостности. С конца 1997 гг. предложенные алгоритмы используются в некоторых разработках АОЗТ "Всесоюзный институт аолоконно-оптических систем саяэи и обработки информации" Кроме того, ряд положений работы был использован в учебном процессе кафедры
-S-
"Компьютерные системы и технологии" МИФИ по курсам "Надежность, контроль и диагностика ЭВМ", "Системы ввода-вывода ЭВМ".
. Апробация. Отдельные результаты диссертационной работы излагались на следующих научных конференциях: Студенческая научная осень-94 (1994 г.), Микроэлектроника и информатика (1995 г.), Международный конгресс студентов, аспирантов и молодых ученых "Молодежь и наука - третье тысячелетие" (YSTM-96) (1996 г.), Научная сессия МИФИ - 98 (1998 г:). Несколько докладов были удостоены различных дипломов и премий, в том числе диплома первой степени и премии конгресса YSTM-96. Также некоторые положения работы обсуждались на научных семинарах, проводимых на кафедре 12 МИФИ.
Научные публикации. По теме диссертации автор имеет 5 печатных работ, результаты исследований отражены в 2 отчетах по НИР.
Структура и объем работы. Диссертационная работа вхлючает введение, четыре главы, заключение, список литературы и два приложения, помещенные во втором томе работы. Общий объем работы: первый том - 160 листов, второй - 92 листа. Работа содержит 34 рисунка, 17 таблиц и 74 наименований библиографии.
