Алгоритмы нахождения в ЦП НБППВ.

В [5] предложено применять РЕБ, РЧБП и РР ЦП для нахождения в нем НБППВ. При этом в [5] приведено вербальное описание данных распределений.

Поэтому далее предлагаются алгоритмы нахождения НБППВ в ЦП на основе вычисленных его РЕБ, РЧБП и РР.

Алгоритм нахождения НБППВ на основе РЕБ ЦП имеет следующие этапы:

1. Вычисление РЕБ ЦП.

2. Преобразование РЕБ ЦП.

3. Вычисление объемов и определение значений бит НБППВ, имеющихся в пакете ЦП.

Рассмотрим содержание данного алгоритма.

На этапе 1 из ЦП формируется матрица

. (19)

Количество столбцов матрицы B _LV выбирается равной величине периодичности L ЦП, характеризующей объем пакета, а количество V строк – согласно количеству пакетов объемом L в ЦП. Величина L определяется по приведенному выше алгоритму.

Для каждого столбца x _i матрицы B _LV вычисляется среднее арифметическое значение [3]

, (20)

где x_ij – j- е биты i -го столбца x _i; i = 1, 2, …, L.

Набор { F_i (x)} _L составляет РЕБ по столбцам x _i матрицы B _LV. Если F_i (x) = 1, то в x _i матрицы B _LV содержатся только биты со значением «1», а при F_i (x) = 0 – только биты со значением «0».

На этапе 2 полученные согласно (20) значения F_i (x) = 0 заменяются на F_i (x) = –1.

На этапе 3 осуществляется вычисление объемов С _u (u = 1, 2, …, U – текущий номер непрерывной битовой последовательности постоянного вида). Для этого выбирают начальные величины: u = 1; C_u = 1. После этого вычисляют объемы НБППВ по следующей формуле:

(21)

Значения для которых выполняется первое условие в выражении (21), будут определять значения бит НБППВ: при бит «x » в непрерывной битовой последовательности имеет значение «1»; при бит «x » имеет значение «0».

На основе РЕБ могут быть определены типы и объемы НБППВ в ЦП без ошибок [5]. Для определения типа непрерывной последовательности заданного объема в ЦП, принятом с битовыми ошибками, может быть использовано РЧБП – совокупность значений частотности для всех возможных битовых последовательностей заданного объема [5].

В общем смысле частотность – это показатель частоты чего-нибудь [3]. Поэтому применительно к анализу ЦП уточним определение этого термина: частотность Ĥ (Y) битовой последовательности заданного объема – это показатель частоты встречаемости этой битовой последовательности в ЦП X объемом N > .

По аналогии с известной формулой [3]

(22)

где P (A) – частота события A, m – количество появлений события A, n – общее количество выполненных опытов, частотность можно вычислить по формуле

(23)

где – встречаемость битовой последовательности Y (т. е. реальное выявленное количество раз присутствия этой последовательности в ЦП X;

– (24)

возможное количество битовых последовательностей объемом в ЦП X объемом N.

Тогда алгоритм определения типов НБППВ на основе РЧБП ЦП будет иметь этапы:

1. Выбор значения объема .

2. Вычисление встречаемости .

3. Вычисление значения W.

4. Вычисление частотности Ĥ (Y).

5. Вычисление глобального и локальных максимумов РЧБП.

6. Нахождение битовых последовательностей .

Рассмотрим содержание данного алгоритма.

На этапе 1 выбирается значение . Для этого по приведенному выше алгоритму вычисляется значение L. Если найденное значение L соответствует периодичности пакетов кадра для нескольких протоколов ПД и объемы НБППВ (например, СК) согласно этим протоколам имеют различные значения, то предлагается выбирается значение , соответствующее минимальному объему. Это позволит уменьшить вычислительные затраты при расчете РЧБП.

На этапе 2 величина определяется на основе ВКФ. Для вычисления ВКФ необходимо выполнить следующие этапы:

Этап 2.1. Вычисление разницы

(25)

между объемами анализируемого ЦП X и битовой последовательностью Y.

Этап 2.2. Сформирование последовательности Z объемом G, содержащей биты «0».

Этап 2.3. Дополнение битовой последовательности Y последовательностью Z:

(26)

где – знак операции конкатенации.

Этап 2.4. Преобразование ЦП X и последовательности путем замены в них бит со значением «0» на биты со значением «– 1».

Этап 2.5. Вычисление значений ВКФ по формуле [5]:

(27)

где x_h+j – значение (h + j)-го бита преобразованного ЦП X; y_h – значение h -го бита преобразованной битовой последовательности j = 0, 1, …, N – 1 – величина сдвига ЦП. Выполненное преобразование последовательностей X и позволяет получать значения ВКФ

(28)

Величина ВКФ Z _XŶ (j) = 1 означает, что биты последовательности совпадают с соответствующими битами ЦП X [2].

Этап 2.6. Запись в память найденных значений ВКФ.

На этапе 2.7 вычисляется встречаемость

(29)

На этапе 3 вычисляется величина W по формуле (24).

Этап 4. Вычисление значений Ĥ (q).

В анализируемом ЦП X максимально возможное количество Q битовых последовательностей объемом составит

(30)

Для удобства проведения дальнейших расчетов и отображения получаемых результатов все возможные значения битовых последовательностей объемом переводятся из битовой формы (где младший разряд слева) в десятичный вид q. Например, для битовой последовательности вида «10000000» (K = 8) имеем q = 1, а для «00000001» – q = 128. Возможные битовые последовательности объемом в десятичном виде будут принимать значения q = 0, 1, 2, …, Q – 1. Тогда вычисленные по формуле (23) значения Ĥ (q) для битовых последовательностей q = 0, 1, 2, …, Q – 1 будут составлять РЧБП объемом .

Этап 5. Вычисление глобального и локальных максимумов РЧБП.

Последовательность постоянного вида, повторяющаяся в каждом пакете кадра, для протоколов ПД c одинаковыми объемами пакетов имеет значение частотности больше, чем остальные битовые последовательности объемом . Поэтому каждой такой последовательности на РЧБП будет соответствовать свой максимум. Результаты технического анализа ЦП ПД показывают, что в структурах пакетов, сформированных по протоколам ПД c одинаковыми объемами пакетов, может быть не более двух НБППВ одинакового объема (обозначим их количество как = 2). Поэтому РЧБП такого ЦП может иметь два максимума: глобальный и локальный около него.

Зададим значение первого (ê = 1) локального максимума РЧБП как Ĥ_ê (q) при q = 0. Тогда глобальный максимум РЧБП можно вычислить по следующей формуле:

(31)

где ê = 1, 2, …, Ê – 1 – номера локальных максимумов РЧБП; q = 0, 1, …, Q – 1 – значения НБППВ; Ê – номер глобального максимума Ĥ _max(q) РЧБП.

Значения q НБППВ последнего локального максимума (ê = Ê – 1) и глобального максимума (ê = Ê) РЧБП запоминаются.

Этап 5. Нахождение битовых последовательностей путем перевода хранящихся в памяти значения q из десятичного вида в битовую форму (где младший разряд слева). Полученные битовые последовательности будут представлять собой НБППВ разных типов объемом .

В ЦП каждая из НБППВ повторяется во всех пакетах кадра данных на одном и том же месте. Поэтому для определения расстояний между последовательностями конкретного типа, находящихся в разных пакетах кадра, вычисляется РР между битовыми последовательностями объема K, с шагом равным этому объему. Данное распределение показывает, какое количество раз встречалась рассматриваемая последовательность в ЦП на расстоянии K.

Предлагается вычислять РР по алгоритму, содержащему следующие этапы:

1. Сравнение искомой битовой последовательности Y объемом с текущим фрагментом x _t объемом анализируемого ЦП X объемом N.

2. Запоминание номеров первого бита фрагмента x _t и последнего бита фрагмента x _{t -1}, если в Y и x _t (t = 2, 3, …, T – номера фрагментов X, совпавших с Y) обнаружено равенство значений бит, имеющих одинаковые номера.

3. Вычисление расстояния S_l между фрагментами x _{t -1} и x _t как разность между запомненными номерами бит этих фрагментов.

4. Определение значения частоты путем подсчета количества одинаковых значений S_ĵ (ĵ = 1, 2, …, l, …, Ĵ ) между всеми найденными фрагментами x _t анализируемого ЦП X.

5. Формирование РР из всех полученных на этапе 4 значений . При этом начальное значение S_ĵ = 0 означает, что НБППВ следуют одна за другой, а конечное значение S_Ĵ = S_max – максимальному расстоянию между ними.

6. Вычисление максимума встречаемости последовательности Y в ЦП X.

7. Вычисление расстояния

. (32)

8. Проверка выполнения условия

, (33)

где Δ _V – погрешность определения количества пакетов в кадре данных.

Выполнение условия (33) означает, что в кадре ЦП X последовательность Y объемом повторяется в пакетах объемом L водном и том же месте.

Таким образом, предложенный алгоритм вычисления РР позволяет подтвердить нахождение в ЦП X непрерывной битовой последовательности Y. Для выявления других НБППВ, которые имеются в данном ЦП, необходимо повторить выполнение алгоритма вычисления РР, выбрав другую битовую последовательность Y.