Для обнаружения несанкционированных записей и искажений в программах и данных, хранящихся в памяти ЭВМ, можно применять методы, основанные на использовании циклических кодов, исправляющих и обнаруживающих ошибки. Предложены некоторые возможные методы организации контроля целостности программ и других видов информации и дана оценка их достоверности.
Для обнаружения неисправностей в цифровых устройствах (ЦУ) в настоящее время используют циклические и укороченные циклические коды [1-6] обычно с небольшим кодовым расстоянием d = 3. Такие коды обнаруживают все однократные и все двукратные ошибки и большое количество ошибок более высокой кратности.
Перед передачей ЦУ в эксплуатацию на входы полностью исправного устройства подают случайный тест достаточно большой длины, а с выходных контрольных точек этого ЦУ снимают реакции на тест, представляющие собой последовательности двоичных символов, которую принято называть эталонной сигнатурой. Эталонные сигнатуры запоминаются ( например, записываются на структурной схеме ЦУ рядом с контрольной точкой, или записываются в памяти специального прибора - сигнатурного анализатора). После этого ЦУ передается в эксплуатацию.
В процессе эксплуатации для контроля исправности ЦУ на его входы подают тот же самый тест и для каждой контрольной точки находят последовательность контрольных символов. Эту последовательность сравнивают с эталонной сигнатурой и если они совпадают, то делается заключение об исправности ЦУ по данному выходу. Если для всех контрольных точек контрольные последовательности совпали с соответствующими эталонными сигнатурами, то считают, что ЦУ исправно в целом.
Для обнаружения несанкционированных записей (программ-закладок, вирусов и т.п.), а также неисправностей в ячейках памяти запоминающего устройства (ЗУ), можно использовать, как и при сигнатурном анализе, циклические коды. Основной алгоритм кодирования для получения кодовых векторов циклического кода имеет вид:
si(x) x m = qi(x) g(x) + ri(x) (9.1)
si(x) x m + ri(x) = qi(x) g(x) = fi (x) (9.2)
где si(х) - информационный многочлен, si(х) хm - информационный многочлен, сдвинутый на m разрядов влево (в сторону старших разрядов), g(x) - порождающий многочлен степени m, qi(х) - частное от деления si(x) xm на g(x), ri(x) - остаток от деления Si(x) xm на g(x), fi(х) - кодовый многочлен.
В соответствии с выражением (9.2) информационный многочлен si(х) сдвигается на m разрядов влево и делится на порождающий многочлен g(x), в результате чего получают частное qi(х) и остаток ri(х). Далее для получения кодового многочлена необходимо перенести остаток в левую часть выражения (9.1) и сложить с si(x) xm , в результате чего получают кодовый многочлен fi (х), делящийся на g(x) без остатка (9.2).
В дальнейшем двоичные изображения многочленов условимся записывать без символа (х) и называть векторами и последовательностями:
fi - кодовый вектор или кодовая последовательность;
si - информационный вектор или информационная последовательность;
qi - вектор частного;
g - порождающий вектор;
ri - вектор остатка или просто остаток.
Введем более полную классификацию остатков, которая нам потребуется в дальнейшем: rэki - эталонный остаток от деления si на g, rki - остаток от деления si на g. rni - остаток от деления fi на g, который получают при контроле ЗУ. Эталонный остаток rэki в теории кодирования называют синдромом.
Все остатки имеют одну и ту же длину m, равную степени порождающего многочлена g(x).
Приведем описание некоторых возможных методов организации контроля целостности программ и данных, записанных в ЗУ ЭВМ и оценим их основные характеристики. С этой целью введем дополнительно следующие обозначения:
k - длина si , равная количеству двоичных символов в si;
n- длина fi ,
М - количество контролируемых слов в блоке,
l - длина слова ,
m - длина остатков, причем
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.