Реферат: Методы цифрового анализа текстовых сообщений для идентификации спама

Труды Научной конференции по радиофизике, ННГУ, 2006
Методы цифрового анализа текстовых сообщений для идентификации спама
С.В. Корелов, А.К. Крюков, Л.Ю. Ротков

Нижегородский госуниверситет

Рассматривается эффективность методов цифрового анализа сообщений (вычисление спектра, моментных функций и т.д.) для различения легальных рассылок от спама.

Существующие программы способны фильтровать трафик электронных писем и не допускать часть спама до почтовых ящиков. Их основные проблемы – потеря эффективности с течением времени (существует возможность приспособления к их работе) и необходимость держать алгоритм работы программы в тайне.

Сообщение может быть рассмотрено как сигнал x(n). К сигналам были применены методы цифровой обработки и определены вероятности ошибок (пропуск спама (ПЦ) и реакция на легальную рассылку как на спам (ЛТ)) для этих методов. В работе рассматривались русскоязычные сообщения. При различении использовался метод наименьших квадратов.

Методы и результаты:

1. Вычисление среднего значения. . Ошибки: pПЦ=0,32; pЛТ=0,25.

2. Вычисление дисперсии. . Ошибки: pПЦ=0,20; pЛТ=0,10.

3. Вычисление относительной частоты использования символов. . Ошибки: pПЦ=0,22; pЛТ=0,04.

4. Вычисление спектральных характеристик сигнала с занулённым средним (200 отсчётов):

4.1. Sin-преобразование. Ошибки: pПЦ=0,11; pЛТ=0,47.

4.2. Cos-преобразование. Ошибки: pПЦ=0,42; pЛТ=0,44.

4.3. – модуль спектра. Ошибки: pПЦ=0,13; pЛТ=0,15.

4.4. Сумма отсчётов в 5 выделенных спектральных диапазонах (ωmax=200): ω=0..3: Ошибки: pПЦ=0,15; pЛТ=0,66.

ω=4..15: Ошибки: pПЦ=0,17; pЛТ=0,67.

ω=16..49: Ошибки: pПЦ=0,25; pЛТ=0,69.

ω=50..99: Ошибки: pПЦ=0,5; pЛТ=0,02.

ω=100..200: Ошибки: pПЦ=0,42; pЛТ=0,02.

5. Вычисление АКФ письма как стационарного сигнала, нормированной на длину (1000 отсчётов). Усреднённые АКФ приведены на рисунках.

Ошибки: pПЦ=0,0494; pЛТ=0,0263.






На данных выборках (232 легальных письма и 204 – спамерских) наиболее эффективным методом идентификации спама оказался метод ковариационной функции. Вероятно, на других выборках легальных рассылок и спама будут эффективны другие методы (спектр …). На основании изученного может быть построен самообучающийся анти-спам фильтр, применяющий совокупность данных методов. Каждый метод в зависимости от истории эффективности работы может иметь свой вес при принятии решения о принадлежности рассылки к спаму. Данный метод не налагает ограничений на количество объектов (цифровых образцов) легальных рассылок и спама и есть основания полагать, что система не потеряет эффективность при накоплении большого количества материала для обучения из-за усреднений.

Таким образом, можно фильтровать до 96% спама с ошибочным принятием решения для 2-5% легальных рассылок.

Наиболее перспективными направлениями разработки системы являются применение новых методов обработки сигналов и создание интеллектуальной системы принятия решений о принадлежности рассылки к спаму.


Гольденберг Л.М., Матюшкин Б.Д., Поляк М.Н. Цифровая обработка сигналов. Учебное пособие, 1990, М: Радио и связь, 257с.
^ Обнаружение аномального поведения процесса на основе системы вызовов
С.В. Корелов, А.С Пуртов, Л.Ю. Ротков

Нижегородский госуниверситет

Процесс обнаружения аномального поведения Вычислительной Системы (ВС) включает в себя четыре этапа (Рис. 1).



Рис. 1

В работе мы рассмотрим первые три этапа обнаружения вторжения.

1) На этапе сбора данных, мы используем технологию перехвата системных вызовов.

2) На этапе анализа нами использованы принципы искусственных иммунных систем.

3) Режим обнаружения атаки предполагает работу СОА в реальном времени.

Разделим все возможные варианты поведения процесса на два режима: нормальный (соответствует работе системы в штатном режиме); и на аномальный (может соответствовать как атаке, вторжению, так и просто неправильной работе самого процесса).

В качестве данных, используемых для анализа поведения процесса, нами была выбрана Последовательность Системных Вызовов (ПСВ).

Перехват системной функции API заключается в изменении некоторого адреса в памяти процесса или некоторого кода в теле функции таким образом, чтобы при вызове этой самой API-функции управление передавалось не ей, а нашей функции, подменяющей системную [3]. Эта функция, работая вместо системной, выполняет какие-то запланированные нами действия (в применении к данной задаче, нас интересует лишь сам факт вызова функции). Фактически, прием заключается в замене адреса функции в таблице импорта на адрес функции-двойника. Как известно, большинство приложений вызывает функции из dll через таблицу импорта, представляющую собой после загрузки exe файла в память списки адресов функций, импортируемых из различных dll.

При перехвате API через таблицу импорта необходимо:

узнать адрес перехватываемой функции

запомнить этот адрес где-нибудь и записать на его место адрес функции-двойника.

Перехваченные функции образуют некую последовательность, каждую функцию кодируем двоичным алфавитом. Таким образом, последовательность функций превращается в бинарную строку, которую «нарезаем» плавающим окном на слова длины l. Из этих слов формируется словарь, соответствующий штатному режиму работы процесса.

На этапе обнаружения атаки мы используем иммунологические принципы [1]. Таким образом, алгоритм обнаружения состоит из четырёх основных шагов:

1) Определить множество ^ S как набор «своих » образцов (в нашей работе под S мы понимаем словарь, состоящих из слов длины l).

2) Произвести набор рецепторов R такой, что каждый рецептор Ri  R не соответствует никакому образцу s  S.

3) Применить набор R к контролю поведения процесса в реальном времени.

4) Если при этом хотя бы один рецептор активируется, это означает, что d  D является аномалией в данной системе.

Основной особенностью данного алгоритма является то, что он не требует никакой предшествующей информации об аномалии.

Наиболее эффективный алгоритм генерации детекторов предложил польский учёный Weirzchon [2]. Основной идеей любого алгоритма генерации набора детекторов является тот факт, что он состоит из слов длины l, не имеющих вхождений в набор защищаемых данных.

В нашей модели процесс активации рецептора может быть определён следующим образом. Предположим, что есть две строки Ri и x, где Ri – рецептор, а x – интересующая нас строка данных. Введём функцию match(Ri,x), такую что:



Мы будем использовать правило r-contigous сравнения строк: match(Ri,x)=TRUE, если строки Ri и x совпадают по крайней мере в r-смежных битах.

Итак, после формирования словарей и соответствующих им наборов детекторов, мы приступаем к следующему этапу построения СОА – непосредственному наблюдению за работой приложения в режиме реального времени. На этом этапе, так же как и на этапе формирования словарей, мы перехватываем функции, вызываемые приложением. Далее по тому же правилу кодируем их в бинарную строку и «нарезаем» на слова длины l (слова «нарезаются» по принципу плавающего окна). Каждое полученное слово сравнивается со сформированным ранее набором детекторов. Как и было упомянуто ранее, равенство строки (из перехваченной последовательности) строке из набора детекторов соответствует обнаружению аномалии.


Forest S., Perelson A., Allen L., Cherukuri R. Self-nonself discrimination in a computer. In: Proceedings of the 1994 IEEE Symposium on Research in Security and Privacy, 1994, pp. 202-212, Los Alamos, CA.

Weirzchon S. Generating optimal repertoire of antibody strings in an artificial immune system. // Intelligent Information Systems, 2000:119-133.

Pietrek M. Windows95 System programming secrets.
^ СтАтический анализ кода архитектуры x86
А.В.Корюкалов, Л.Ю.Ротков

Нижегородский госуниверситет

Одним из основных преимуществ статического анализа является возможность анализировать код без его исполнения. Такой анализ часто используется для обнаружения вредоносного кода в программном обеспечении и в современных программах-антивирусах представлен методом, основанном на поиске сигнатур в исполняемом коде. Суть этого метода заключается в поиске последовательности кода (сигнатуры), свойственной конкретному вирусу или другой вредоносной программе. При проверке в программах ищутся сигнатуры из базы. Данный метод анализа имеет следующие недостатки:

Сигнатура вырабатывается специалистами компании только после обращения от потерпевшего.

Для каждой вредоносной программы необходима своя сигнатура (одна или несколько).

В случае вирусов с непостоянным кодом не всегда возможно учесть все варианты кода допустимым числом сигнатур.

Невозможно распознать неизвестный вирус.

Таким образом, существует необходимость в автоматизированном решении, позволяющем идентифицировать ранее неизвестные вредоносные программы.

Статический анализ исполняемого кода включает в себя следующие задачи:

Дизассемблирование кода – преобразование машинных кодов инструкций в их мнемоническое представление.

Построение управляющего графа – наглядное графическое представление может сделать анализ существенно эффективнее и сократить затраты на определение логических связей между процедурами программы.

Ручной или автоматизированный анализ кода и/или управляющего графа исследуемой программы.

В рассмотренных работах по проблемам статического анализа исполняемого кода описаны некоторые сложности и решения вышеприведенных задач.

В [7] описываются сложности, возникающие при дизассемблировании кода архитектуры X86, и подходы к преобразованию исполняемого кода таким образом, чтобы часть его инструкций дизассемблировалась неверно. Эти подходы строятся на том, что у архитектуры X86 инструкции не имеют постоянной длины и для вычисления границ инструкции необходимо проанализировать несколько ее частей. Таким образом, если один раз неправильно вычислить начало инструкции, то несколько инструкций будут дизассемблированы неверно.

При использовании режима косвенной адресации в инструкциях передачи управления (когда адрес назначения задается с использованием регистра процессора или участка памяти) необходим дополнительный анализ объектов данных, участвующих в вычислении адреса. В [1] описывается применение метода анализа набора значений (value-set analysis) для получения переоцененного набора значений, который в каждой точке программы может содержать каждый объект данных.

Рассматривая задачу анализа исполняемого кода применительно к вредоносным программам, необходимо учитывать, что авторы вредоносного кода часто маскируют системные вызовы и границы процедур кода при помощи комбинации инструкций работы со стеком. В [5], [6] и [8] описываются методы поиска таких преобразований.

В [2], [3] и [4] описаны идеи автоматизированного поиска некого «поведения», свойственного вредоносному коду, которое представлено шаблоном. При анализе по определенным правилам сравнивается участок кода программы и шаблоны из библиотеки с учетом структуры управляющего графа, последовательностей инструкций и системных вызовов. Качество такого анализа зависит от принципов составления библиотеки шаблонов. Исследования в данной области могут быть направлены на определение этих принципов и поиск условий, при которых код может считаться удовлетворяющим шаблону.


Balakrishnan G., Reps T. Analyzing memory accesses in x86 executables. //In Proceedings of the International Conference on Compiler Construction (CC'04), volume 2985 of LNCS, pages 5—23 (2004).

Bergeron J., Debbabi M., Desharnais J., Erhioui M.M., Lavoie Y., Tawbi N. Static detection of malicious code in executable programs. //In Proceedings of the International Symposium on Requirements Engineering for Information Security (2001).

Christodorescu M., Jha S., Seshia S.A., Song D., Bryant R.E. Semantics-aware malware detection. //In Proceedings of the 2005 IEEE Symposium on Security and Privacy, pages 32—46 (2005).

Christodrescu M., Jha S. Static Analysis of Executables to Detect Malicious Patterns. //In Proceedings of the 12th USENIX Security Symposium, pages 169—186 (2003).

Lakhotia A., Kumar E. U. Abstracting Stack to Detect Obfuscated Calls in Binaries. //In Proceedings of the Fourth IEEE International Workshop on Source Code Analysis and Manipulation (SCAM'04), pages17—26 (2004).

Lakhotia A., Kumar E. U., Venable M. A Method for Detecting Obfuscated Calls in Malicious Binaries. //IEEE Transactions on Software Engineering,  Volume 31, Number 11, November 2005, pages 955—968.

Linn C., Debray S. Obfuscation of Executable Code to Improve Resistance to Static Disassembly. //In Proceedings of the 10th ACM Conference on Computer and Communications Security (CCS), pages 290—299 (2003).

Venable M., Chouchane M. R., Karim M. E., Lakhotia A. Analyzing Memory Accesses in Obfuscated x86 Executables. //In Proceedings of the Conference on Detection of Intrusions and Malware & Vulnerability Assessment (DIMVA), pages 1—18 (2005).
^ Эксперименты с моделями «простых» криптосистем
А.А.Горбунов1), К.Г.Кирьянов1), А.А.Новокрещенов2)

1)Нижегородский госуниверситет,
2)Нижегородский государственный технический университет

С помощью подхода, базирующегося на описании блоков шифратора и дешифратора криптосистем (КС) в виде q-уровневых линейных цифровых автоматов (ЛЦА) на языке ABCD-формализма [1], зачастую для целого ряда задач удается получить адекватную математическую модель (ММ), оставаясь при этом в рамках настоящих моделей простых систем. Суть указанного подхода заключается в том, что системы уравнений ЛЦА на языке ABCD-формализма для шифратора, канала связи без задержки и дешифратора представляются в виде:

. (1)

Здесь входным сигналом u(t) является открытый текст, сигналом y(t) = u*(t) – шифротекст, сигналом y*(t) – восстановленное сообщение; матрицы дешифратора однозначным образом определяются по имеющимся матрицам шифратора (если  D-1) по следующим формулам:

A* = [A-BD-1C], B* = [BD-1], C* = [-D-1C], D* = [D-1], x0* = x0 . (1a)

Подобным же образом можно учесть и наличие в канале связи задержки шифрованного сигнала на  тактов. При этом блок канала связи, наряду с блоками шифратора и дешифратора, также представляется в виде дискретной динамической системы (ДДС), с выхода которой в течение первых  тактов снимается нулевой сигнал, после чего – сигнал, тождественный входному, но задержанный во времени на  отсчетов. Соотношения (1а) для построения ММ дешифратора по модели шифратора в ABCD-формализме в этом случае обобщаются (если  D-1 и  A*-1) следующим образом:

A* = [A-BD-1C], B* = [BD-1], C* = [-D-1C], D* = [D-1], x0* = (A*-1)x0 . (1б)

В настоящей работе была реализована компьютерная программа, эмулирующая поведение блоков шифратора, канала связи и дешифратора КС как ДДС, модель которой записывается на языке ABCD-формализма, и проводились компьютерные эксперименты по моделированию частных случаев криптосистем с конкретными характеристиками с целью разработки подходов к их тестированию. Данная программная реализация КС допускает работу в различных алгебраических структурах (АС): поле вещественных чисел, на множестве целых чисел, в АС конечных полей Галуа GF(q).

Тестирование программной реализации криптосистем заключалось:

в автоматическом контроле соответствия размерностей матриц, описывающих тестируемую ММ, размерностям входного и выходного текстовых сигналов (могущих являться как скалярными, так и векторными);

в проверке правильности заполнения матриц, векторов текстовых сигналов только элементами, допустимыми в выбранной АС;

в автоматическом определении по имеющимся матрицам, описывающим ММ шифратора в ABCD-формализме, матриц, определяющих модель дешифратора в том же формализме;

в проверке соответствия текстового сигнала, поступающего на вход шифратора, текстовому сигналу, снимаемому с выхода дешифратора.

Проводилось тестирование ММ ряда КС, функционирующих в различных АС. В качестве примера далее приведены результаты моделирования в ABCD-формализме работы одной из возможных КС, функционирующей в АС GF(q=4), для которой величина задержки в канале связи выбрана равной  = 5 тактам.

Модель шифратора КС представлена в виде ЛЦА с параметрами:

. (2)

В соответствии с формулами (1б) можно построить ММ дешифратора (т.к. D-1 и A* -1) со следующими параметрами ЛЦА:

. (3)

В качестве тестовых сообщения u1 и ключа u2 , подаваемых в на векторный вход шифратора соответственно взяты изученные ранее характерные участки генетического текста длиной M = 958.

. (4)

С выхода шифрующего ЛЦА снимается векторный шифротекст, который, после задержки по времени на 5 тактов в канале передачи данных, поступает на вход дешифратора:

. (5)

Блок дешифратора восстанавливает следующий текст:

. (6)

Соответствующие компоненты сигналов (4) и (6) идентичны с точностью до сдвига по времени, что говорит о корректном функционировании рассмотренной модели КС.

Горбунов А.А., Кирьянов К.Г. Динамические модели криптосистем с закрытым ключом. Синтез дешифраторов. //Вестник ННГУ им. Н.И. Лобачевского. Серия «Радиофизика». Вып. 2. Н. Новгород: ННГУ, 2004, С.24
^ Модель стека TCP/IP на основе сетей Петри
Е.И. Кочетков, Л.Ю. Ротков

Нижегородский госуниверситет.

За последние годы протокол управления передачей TCP (transmission control protocol) в сочетании с Интернет протоколом IP стали наиболее распространенной формой организации компьютерных сетей. В связи с ведущимися разработками высокоскоростных сетей и приложений, которые используют TCP, возникающие при этом проблемы вызывают повышенный интерес.

Во многих областях исследований явление изучается не непосредственно, а косвенно, через модель. Эффективность работы данного протокола при невыполнении какого-либо условия можно анализировать на примере поведения модели протокола. При этом одной из главных задач становится создание адекватной модели исследуемого протокола.

Сети Петри является удобным инструментом исследования систем. Моделирование в сетях Петри осуществляется на событийном уровне. Определяется, какие действия происходят в системе, какие состояния предшествовали этим действиям и какие состояния примет система после выполнения действия. Выполнение событийной модели в сетях Петри описывает поведение системы. Анализ результатов выполнения может сказать о том, в каких состояниях пребывала или не пребывала система, какие состояния в принципе не достижимы.

В общем виде сеть Петри представляет собой разновидность ориентированного графа, включающего в себя вершины двух типов: позиции и переходы. Позиции символизируют состояния и обозначаются как pi, а переходы обозначают собой действия (переходы из одного состояния в другое) и обозначаются как tj. Позиции и переходы соединены направленными дугами fk, каждая из которых имеет свой вес wk. Дуги также можно разделить на два типа: дуги, направленные от позиции к переходам, (p–t) и дуги, направленные от переходов к позициям (t–p). Исходя из этого, сеть Петри может быть формально представлена как совокупность множеств: N = (P, T, F, W), где P = {p1, p2… pn} - множество всех позиций (n – количество позиций), T = {t1, t2… tm} – множество переходов (m – количество переходов), F = (Fp–t, Ft–p) – множество дуг сети: Fp–t = (p–t), Ft–p = (t–p) – множества дуг, ведущих соответственно от переходов к позициям и от позиций к переходам. W = {w1, w2… wk} – множество весов дуг (k – количество дуг). Каждая позиция может быть маркирована, т.е. содержать некоторое число фишек. Если обозначить числа фишек, находящихся в i-й позиции pi, как mi, то маркировка всей сети: M = {m1, m2… mn}. Тогда полное определение сети Петри, включая данные о начальной маркировке, можно записать в виде: PN = (N, M0), где М0 – начальная маркировка сети.

Ниже, на рисунке приведена сеть Петри, представляющая собой модель ТСР протокола для передающей станции:



Входные позиции: in1 – генерация пакета, in2 – начальный сброс окна, in3 – подтверждение приема пакета. Выходные позиции: out1 – пакет передан, out2 –пакет передан повторно. Переходы: t1 – доставка пакета в передающий буфер, t2 – начальная установка окна, t3 – текущая установка окна, t4 – рабочая передача пакета, t5 – повторная установка окна, t6 – сброс окна, t7 – сброс списка пакетов, t8 – сброс временных меток, t9 – окончание времени ожидания, t10 – повторная передача пакетов. Состояния: p1 – буфер пакетов на передачу, p2 – готовность окна, p3 – список временных меток пакетов, p4 – список пакетов для повторной передачи, p5 – коррекция списков пакетов и временных меток, p6 – коррекция окна, p7 – формирование пакета на передачу.

Данная сеть Петри отображает динамику независимых событий, происходящих в системе, и при использовании соответствующего математического аппарата (программного обеспечения) дает возможность моделировать поведение протокола при различных параметрах сети.

Котов В.Е. Сети Петри – М.: Наука, ГРФМЛ, 1984

Шварц М. Сети связи: протоколы, моделирование и анализ. В 2-х ч. Пер. с англ. – М.: Наука, 1992.

Семёнов Ю.А. (ГНЦ ИТЭФ), Модели реализации протокола TCP и его перспективы
^ Особенности компьютерных технологий при изучении радиоэлектронных устройств на базе программного пакета Electronics Workbench.
Гордяскина Т.В., Лебедева С.В.

ФГОУ ВПО «Волжская государственная академия водного транспорта»

Объектами профессиональной деятельности выпускников по специальности «Техническая эксплуатация транспортного радиооборудования» являются радиолокационные, радионавигационные и радиосвязные системы; системы и средства контроля и диагностики технического состояния эксплуатируемого оборудования; системы управления движением транспортных средств; системы предупреждения столкновений и др.

Однако современное финансовое состояние ВУЗов существенно затрудняет реализацию основной задачи – подготовку высококвалифицированных технических специалистов, в том числе, за счет снижения доли практических исследований с использованием лабораторных стендов и аппаратуры. Оборудование одного рабочего места для проведения лабораторных работ по радиотехническим специальностям обходится в десятки тысяч рублей. Поэтому большие затруднения вызывает организация однотипных рабочих мест для фронтального изучения дисциплин (вся группа делает одну и ту же работу после изложения материала на лекции). По многим дисциплинам лабораторные стенды выполняются в единичных экземплярах, поэтому студентам приходится выполнять лабораторные работы по темам, которые еще не рассматривались в лекционном курсе.

Существенно исправить положение может разумное сочетание инструментальных методов исследования и методов компьютерного моделирования с использованием современных программных пакетов. Такой подход реализован на кафедре радиоэлектроники Волжской государственной академии водного транспорта, в частности, по дисциплинам «Радиотехнические цепи и сигналы», «Радиоизмерения», «Схемотехника», «Физические основы электроники».

В лабораториях студенты осваивают пакет Electronics Workbench версия 5 (EWB), который обладает широкими возможностями, позволяющими создавать и редактировать принципиальные электрические схемы устройств; рассчитывать частотные характеристики; проводить анализ спектра и т.п. Отличительной особенностью пакета является наличие виртуальной лаборатории – контрольно-измерительных приборов, передние панели и органы управления которых похожи на промышленные аналоги, что позволяет студентам приобретать навыки практической работы с приборами (осциллографом, генератором, мультиметром, измерителем амплитудно-частотных характеристик и др.) [1].

Лабораторные занятия проводятся в подгруппах, каждый студент имеет индивидуальное рабочее место, оснащенное компьютером, методическими указаниями по выполнению лабораторных работ. Темы, изучаемые во время лабораторных занятий, тесно связаны с материалом, рассмотренным на предыдущей лекции.





.




На рисунке приведен пример исследования схемы умножителя частоты сигнала. Используя виртуальный осциллограф и анализируя спектр сигнала на входе умножителя и в цепи эмиттера транзистора, исследуются нелинейные преобразования сигнала. Подбирая параметры резонансного контура, студенты настраивают его на различные гармоники, выделяя последовательно вторую, третью гармоники спектра.

Таким образом, данный подход к изучению общепрофессиональных дисциплин позволил:

–обеспечить индивидуальным рабочим местом для проведения лабораторных работ каждого студента;

–реализовать фронтальный метод изучения материала;

–обеспечить непрерывный контроль выполнения работ и повысить объективность оценки знаний студентов;

–обеспечить более глубокий уровень усвоения материала – приобрести и закрепить навыки теоретических исследований и компьютерного моделирования параметров радиотехнических цепей и сигналов.




Кубышкина Т.В., Плющаев В.И. //Вестник ВГАВТ.: Выпуск 9. Межвузовская серия «Моделирование и оптимизация сложных систем. Информационные технологии и развитие образования». – Н. Новгород: Изд. ФГОУ ВПО ВГАВТ, 2004, c.159.
^ Использование систем синхронизации генераторов ПСП
в детекторах ошибок устройств контроля
цифровых каналов связи.
В.В.Акулов1), К.Г.Кирьянов2)

1)ФГУП ННИПИ «Кварц», 2)^ Нижегородский госуниверситет.

В работе рассмотрены уравнения динамики и примеры практического использования систем синхронизации генераторов ПСП в анализаторах ошибок (устройствах измерения верности передачи информации в цифровых трактах) при контроле каналов связи.

Детектор ошибок решает следующие задачи:

формирование внутренней тест-последовательности;

синхронизация внутренней тест-последовательности с входной внешней тест-последовательностью;

выделение ошибок из входной тест-последовательности путем сравнения входной внешней и внутренней тест-последовательностей;

подсчет количества ошибок счетчиком ошибок.

Тест-последовательность подается на объект контроля, с которого поступает на анализатор ошибок, для проверки качества работы объекта контроля. В качестве тест-последовательности наиболее часто используется псевдослучайная последовательность (ПСП) максимальной длины (М-последовательность).

Известны устройства для детектирования ошибок [1,2], в которых используются систематические свойства М-последовательностей, которые позволяют достаточно точно проводить измерение количества ошибок. Недостатком таких устройств является недостаточная помехоустойчивость – невозможность синхронизации при приеме входной внешней М-последовательности с большим средним по времени коэффициентом ошибок ош. вх. max . На основании анализа уравнений динамики систем синхронизации генераторов ПСП предложены детекторы ошибок с возможностью измерения коэффициентов ошибок от 0 до 1, повышенной надежности и минимальным временем входа в синхронизм.



Авторское свидетельство СССР № 1251335 кл. Н04В3/46, 1985 г. В. С. Балан, М.С Гроссман. Устройство для детектирования ошибок.

Заявка на изобретение СССР № 4832472/09 (059243) от 29.05.90 г., МК.5 Н04В3/46. Устройство для детектирования ошибок.

К.Г.Кирьянов, В. В. Акулов, А. С. Меднов, АС №1709542



^ Структурная идентификация объектов на основе определения базовых параметров входных и выходных процессов
К.Г.Кирьянов, А.А.Горбунов, Д.Л.Туренко

Нижегородский госуниверситет

Рассмотрена модификация способа [1] поиска оптимальных базовых параметров (БП) векторных нестационарных объектов (рис.1) на неавтономные математические модели Источников данных на основе анализа известных (полученных экспериментально) не только выходных (y(t)), но и входных (u(t)) и последовательностей данных.




^ Рис.1 Структурная схема объекта
Математическая модель (ММ) Источника данных типа “Чёрный Ящик” в форме синхронного автомата Хаффмана – Глушкова описывается следующей системой уравнений:



Здесь:

u(t) – входной векторный k-мерный сигнал автомата;

y(t) – выходной векторный r-мерный сигнал автомата;

x(t) – внутреннее n-мерное состояние автомата;

xн – начальное n-мерное состояние автомата; t  [0, 1, 2, …, М] – дискретное время. Можно показать, что уравнения (1) и (2) в ряде случаев сводятся к удобной для практики форме (3), не содержащей явно компонент внутреннего состояния x(t)

, (3)

к которым, если требуется, можно перейти от уравнения (3).

Для нас существенно, что данная форма является модификацией прогнозирующего оператора очередного векторного отсчета y(t) не только по ny выходным отсчетам [1], но и по предыдущим nu входным отсчетам. То есть оптимальные Базовые Параметры (БП) =, где n = k∙nu +r∙ny, q = qu = qy , можно определять по критерию, как и в [1], минимальной энтропии, но в изменённой форме:

(4)

путем восстановления фазовой траектории n-мерного фазового по экспериментальным данным входа и выхода.

В таблице 1 представлены результаты компьютерного моделирования предложенного способа структурной идентификации объектов с ММ рис. 1 путём экспериментального поиска БП по q в области в критерии (4) при известных входных последовательностей (генетических текстов u(t) из GenBank длиной с M=347) и соответствующих выходных процессов y(t) с идентифицируемых АРСС- автоматов в кольцах K(q).

Таблица 1




БП входных и выходных процессов идентифицируемого автомата

Размерности векторов входов и выходов k , r автомата

Найденные экспериментально оптимальные БП

эквивалентных объектов

(автоматов)

1

q = 4 ; nu = 1 ; ny = 5

k = 1 , r = 1

q = 4 ; nu = 1 ; ny = 5

2

q = 4 ; nu = 5 ; ny = 3

k = 1 , r = 1

q = 4 ; nu = 5 ; ny = 3

3

q = 4 ; nu = 2 ; ny = 7

k = 1 , r = 1

q = 2 ; nu = 11; ny = 7

q = 4 ; nu = 2 ; ny = 7*)

4

q = 22 ; nu = 3 ; ny = 4

k = 1 , r = 1

q = 2 ; nu = 8 ; ny = 7

q = 22; nu = 0; ny = 4*)

5

q = 4 ; nu = 3 ; ny = 4

k = 2 , r = 2

q = 2 ; nu = 4 ; ny = 5

q = 4 ; nu = 2 ; ny = 4*)

6

q = 22 ; nu = 1 ; ny = 3

k = 2 , r = 2

q = 3 ; nu = 0 ; ny = 5

q = 22; nu = 0; ny = 2*)

Способ даёт возможность отбирать и “имеющие смысл” БП (см. строки, отмеченные знаком *)) близкие к оптимальным по критерию (4) или его вариантам.

Другие применения предложенного способа структурной идентификации объектов рассмотрены в работах [2], [3].


Кирьянов К.Г. Труды III Международной конференции «Идентификация систем и задачи управления» SICPRO04. Москва, Институт проблем управления им. В.А.Трапезникова РАН. М.: 2004. С.187-208.

Грунина Е.А., Кирьянов К.Г. Подход к исследованию математических моделей функциональных подсистем сложных биосистем (на основе определения их базовых параметров). Статья в настоящем сборнике.

Горбунов А.А., Кирьянов К.Г. Сравнение подходов к оценке расстояния единственности криптосистем. Статья в настоящем сборнике.



^ Подход к исследованию математических моделей функциональных подсистем сложных биосистем
(на основе определения их базовых параметров)
Грунина Е.А1)., Кирьянов К.Г2).

1)Нижегородская медицинская академия,^ 2)Нижегородский госуниверситет.

Математическая модель (ММ) функциональной подсистемы сложной системы с её общепринятыми сопровождающими понятиями – это модель т.н. «Чёрного Ящика» в удобной для нас форме не автономного (нестационрного, открытого) дискретного по времени t Î [0,1,2,…,М–1] и уровню q Î [0,1,2,…,Q–1] автомата Хаффмена-Глушкова (подробнее см., например, в [1,2]):

xt+1 = g(xt,ut;p) – функция динамики, «переходов», xt,xt+1X(n); (1)

x0 = xн –начальное состояние, x0X(n);

yt = l(xt,ut;p) – функция наблюдения, «выходов», ytY(r); (2)

ut – «вход», utU(k);

yt – «выход», ytY(r);

p – «вектор свободных, рабочих параметров ММ», pP(s);

{q,n} – «вектор базовых параметров (БП) ММ»;

nu, ny– размерности подсостояний xt ,связанных с функциями g(..) и l(..);

k∙nur∙ny = n – «число скалярных компонет вектора состояния подсистемы».

Конкретизация целей исследования. Апробация теоретического подхода для возможности экспериментальной оценки влияния функционирования большой сложной системы произвольной природы (биологической, технической, социальной т.д., не имеющей как правило, строгого математического описания её работы), на менее сложные подсистемы (с целью возможного создания адекватных математических моделей (ММ) неавтономных подсистем (автономные подсистемы без связи с «окружением» рассмотрены в [1])) нового способа распознавания (оценки величины) размерности векторного изменяющегося во времени tÎ [0,1,2,…,М] и непосредственно не наблюдаемого состояния xtизучаемой (идентифицируемой) подсистемы сложной системы по отклонению оптимального БП («nopt») от значения n = 1 векторного процесса ytнеавтономной подсистемы в предположении о виде функциии наблюдения yt=l(xt,ut;p)  xt.

Результаы экспериментов по идентификации БП реальных «выходных»(yt) и модельных «входных» (ut) наборов данных кроветворной подсистемы сложной системы организма человка сведены в Таблицу. Для сокращения в ней показаны лишь некоторые характерные комбинации компонент полного экспериментально полученного вектора yt (yt1, yt2, yt3, yt4, yt5)Т = (Gt, Ert, Lt, Cpt, Rt)Т, где Gt– гемоглобин, Ert – эритроциты, Lt – лейкоциты, Cpt – цветовой показатель, Rt – РОЭ, а связь подсистемы с системой, как ранее в автономной ММ [1] либо не учитывалась совсем (столбец 1 Таблицы), либо учитывалась, как в неавтономной ММ [2] уравнениями (1) и (2) при yt = l(xt,ut;p)  xt. При этом, в качестве вектора связи ut подсистемы с самой системой (с «окружением» подсистемы) через уравнение (1) рекомендуется брать либо реальные одномоментные процессы (со входов и выходов) других подсистем, «подозреваемых в связях» с изучаемой подсистемой, либо, при отсуствии априорной информации о возможности таких связей, гипотетические модельные процессы, например, в виде постоянных уровней (столбец 2 Таблицы) и меняющихся воздействий (столбец 3). Область поиска БП: qmin=3, qmax=50; t[0,1,2,…,M=23-1]; q, nu, ny- оптимальные БП по минимуму суммы условных энтропий Eu, Ey входа и выхода подсистемы [2].





1

2

3

№

Связь изучамой подсистемы с «окружением» (самой сиcтемой)




Отсутствует, [1]

есть: ut=const [2]

есть: ut  const [2]

1

k = 0, автономная ММ

r =1, yt=Gt ,

qy=5, ny=4, Ey=9.287

k = 1, ut 0 ,

r = 1, yt=Gt ,

q=5,nu=0,ny=4, Eu=0.00, Ey=9.287

k =1, ut =sin2(t32)

r =1, yt=Gt ,

q=13, nu=1, ny=1,Eu=3.70,Ey=3.700

2

k = 0, автономная ММ

r=2, yt =(Gt ,Lt)T,

qy=4, ny=2, Ey=8.000

k = 1, ut0

r = 2, yt =(Gt ,Lt)T,

q=4,nu=0, ny=2, Eu=0.00, Ey=8.00

k =1, ut =sin2(t32)

r =2, yt =(Gt ,Lt)T,

q=4, nu=0, ny=2 Eu=0.00, Ey=8.00

3

k = 0, автономная ММ

r=3, yt=(Gt ,Lt Ert)T

qy=4, ny=2, Ey=12.000

k = 1, ut0

r=3, yt =(Gt ,Lt Ert)T

q=4,nu=0,ny=2,Eu=0.00,Ey=12.00

k = 1, ut =sin2(t32)

r = 3, yt =(Gt ,Lt Ert)T

q=4,nu=0, ny=2,Eu=0.00, Ey=12.00

4

k = 0, автономная ММ

r=3, yt=(Gt ,Lt Rt)T

qy=8, ny=1, Ey=9.000

k = 1, ut0

r = 3, yt =(Gt ,Lt Rt)T

q=8, nu=0, ny=1,Eu=0.00, Ey=9.00

k = 1, ut =sin2(t32)

r = 3, yt =(Gt ,Lt Rt)T

q=4, nu=1, ny=1,Eu=2.00,Ey=6.00

5

k=0, автономная ММ

r=4, yt=(Eri,Lt,Cpt ,Rt)T

qy=4, ny=2, Ey=16.000

k = 1, ut0

r = 4, yt =(Eri ,Lt ,Cpt ,Rt)T

q=3,nu=0,ny=2,Eu=0.00,Ey=12.67

k = 1, ut =sin2(t32)

r = 4, yt =(Eri ,Lt ,Cpt ,Rt)T

q=3,nu=1,ny=1,Eu=1.584,Ey=6.33

6

k = 0, автономная ММ

r=5, yt =(Gt ,Eri ,Lt ,Cpt ,Rt )T

qy=6, ny=1,Ey=12.924

k = 1, ut0

r = 5, yt =(Gt ,Eri ,Lt ,Cpt ,Rt )T

q=6,nu=0,ny=1, Eu=0.00,Ey=12.92

k = 1, ut =sin2(t32)

r = 5, yt =(Gt ,Eri ,Lt ,Cpt ,Rt )T

q=3,nu=1,ny=1,Eu=1.584,Ey=7.92



Выводы: 1) Предложена модификация способа, изложенного в [1], экспериментальнго определения достаточного числа и номеров наблюдаемых отведений (выходов) на случай открытой динамической подсистемы сложной системы [2] по значениям её базовых параметров nu = 0 и ny =1.

2) Минимальным полным набором проанализированных пяти компонент данных анализа крови является набор только из трёх компонент (Gt,LtRt)T.


Кирьянов К.Г., Грунина Е.А. Об определении достаточного числа отведений с изучаемой динамической системы. ННГУ, Н.Новгород: ТАЛАМ, 2005,с.__(http:// www/rf.unn.ru/rus/sci/books/05/index.html).

Кирьянов К.Г, Горбунов А.А.,Туренко Д.Л. Структурная идентификация объектов на основе определения базовых параметров входных и выходных процессов. статья в настоящем сборнике.



^ АСПЕКТЫ ПРИМЕНЕНИЯ ГЕНЕТИЧЕСКИХ КАРТ ДАННЫХ
ДЛЯ ИДЕНТИФИКАЦИИ ИСПОЛНЯЕМОГО КОДА ПРОГРАММ
Д.Л.Туренко

Нижегородский госуниверситет

Реконструкция (reverse engineering) алгоритмов программ в целом или отдельных процедур по их исполняемому коду является важной составляющей при анализе уязвимостей программного обеспечения (ПО), идентификации вредоносных программ, а также поиске ошибок при программировании.

Задачу восстановления алгоритмов можно свести к задаче идентификации их реализаций и решать с использованием средств автоматизированного анализа исполняемого кода. Например, в средствах антивирусной защиты идентификация вредоносных программ производится