Comparison of computational complexity of classification algorithms for recognizing the signs of cyber attacks

Sidel'nikov Oleg Vasil'evich Lecturer, Department of Information Security in Automated Systems, Military Academy of Communications (in Krasnodar) 350035, Rossiya, g. Krasnodar, ul. Krasina, 4 olegvsk@mail.ru

Задача классификации является одной из основных при обнаружении угроз компьютерных атак (КА) в информационной системе (ИС). Информация о признаках обнаружения КА может поступать от различных источников (датчиков) программного и аппаратного обеспечения ИС, например, антивирусных средств, логов дампов оперативной памяти, жестких дисков, журнала входа в систему и т.д. Все они содержат информацию, с помощью которой можно попытаться определить о наличии атаки в системе. В данной статье рассматривается задача логической классификации уже имеющихся данных с помощью двух алгоритмов: последовательного перебора и индуктивного прогнозирования состояний ^[1-3].

Одним из наиболее общих известных критериев сравнения трудоемкости алгоритма работы СОА является временная сложность, т.е. время, затрачиваемое на выполнение алгоритма, оценивается числом условных элементарных операций, которые необходимо выполнить при решении задачи распознавания (идентификации) КА. Эта величина зависит от объема исходных данных. Для доказательства будем использовать методику, предложенную А.Д. Закревским ^[4].

Объем исходных данных соответствует объему данных представленной матрицей взаимодействия КА с ИС в виде булевой матрицы.

Представим булеву матрицу исследуемого класса A₁ образованной n столбцами, соответствующими признакам `X_(1), X_(2), ... , X_(n)` , и m строкам, задающими выбранные объекты `x_(1), x_(2), ... , x_(m)` , – положим, что их равно m. Поскольку каждый из них выбирается случайно и независимо друг от друга из множества Ω можно считать, что матрица `A_(i)` также считается случайной: каждый элемент принимает значение 0 или 1 с одной и той же вероятностью 0,5 и независимо друг от друга. Так как число элементов матрицы равно произведению числа строк на число столбцов, то общее число различных матриц оказывается равным `2^(mn)` причем, все они равновероятны.

Выберем в данном пространстве некоторый конкретный интервал ранга r и рассмотрим событие. Обозначим это событие через i(m, n, r), где в скобках показаны параметры события: m – число элементов в случайном множестве, n – число признаков; r – ранг интервала.

В ^[3] при рассмотрении множества всех различных булевых матриц размером m × n сделаны выводы о том, что:

– доля матриц, у которых первые r позиций в первой строке заполнены нулями, составляет `2^(-r)` от общего числа матриц `2^(mn)` ;

– доля остатка равна `(1 - 2^(-r))` ;

– количество различных матриц, которые имеют хотя бы одно значение 1 в первых r позициях первой строки равно `2^(mn) ` × `(1 - 2^(-r))` ;

– количество различных матриц, которые будут иметь хотя бы одну единицу в первых r позициях равно `2^(mn)` × `(1 - 2^(-r))^m` ;

Вероятность появления `P_(i) (m, n, r)` события равна (1):

`P_(i)(m, n ,r) = (1 - 2^(-r))^m` (1)

Рассмотрим множество всех 2^тп различных булевых матриц заданного размера, а с другой – множество всех интервалов рангаr в пространстве М.Число таких интервалов равно `C^r_(n)2^r` : первый сомножитель показывает число различных сочетаний при выбореr признаков из общего их числа п, а второй – количество фиксируемых комбинаций значений для выбранных признаков. При этом (2):

`C^r_(n) = (n xx (n - 1) xx ... xx (n - r + 1)) / (1 xx 2 xx ... xx r)` (2)

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

Объем матрицы информативности признаков равен (3):

(3)

где : т – число элементов в случайном множестве, п – число признаков; r – ранг интервала.

Коэффициент показывает пространственный выигрыш при выполнении операций перебора и поиска информативных признаков, характеризуемый вычислительной сложностью алгоритма (4).

(4)

Для оценки выигрыша при распознавании признаков КА был проведен вычислительный эксперимент.

` `

` `

` `

` `

Данный эксперимент был проведен на ЭВМ со следующей аппаратной конфигурацией: Intel(R) Core(TM) i3-2120 CPU (3.30GHz), оперативная память 3 Gb. Вычислительный эксперимент проводился в среде MATLAB 7.12.0(R2011a).

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

Программа 1 (TestRecognition.m): Построение исходных матриц взаимодействия КА с ИС. Программа построение тестовых матриц информативности предназначена для оценки алгоритмов. Матрицы взаимодействия КА с ИС представляют собой случайную равновероятную выборку, в данном случае из булева пространства M – полного множества всевозможных комбинаций признаков, причем все комбинации равновероятны.

Программа 2 (MatrixAlg.m): Сравнительная оценка вычислительной сложности алгоритмов последовательного перебора и индуктивного прогнозирования состояний.

Входные данные: набор правил, представляющих из себя вектора вида {0-1--1}. Правила накладывают ограничения на проверяемые объекты, являющиеся двоичными векторами. Ноль или один в определенной позиции указывает на то, что в проверяемом векторе на этой позиции должно быть соответствующее значение 0 или 1. Прочерк на позиции указывает, что состояние неопределенное и ограничений на значение этой позиции нет. Набор проверяемых объектов, описываемых бинарными признаками вида {100101}.

Выходные данные: делается вывод о том, подходит ли объект под какое-либо правило из набора и производится оценивание количества операций сверки значений признака объекта со значением признака в правилах для оценки.

Краткое описание алгоритмов. Алгоритм последовательного перебора – последовательная сверка. Заданный объект последовательно сверяется с правилами до первого совпадения с каким-либо правилом.

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

Описание программы. Программа MatrixAlg.m: реализует оценку вычислительной сложности алгоритмов последовательного перебора и индуктивного прогнозирования состояний. Как результат работы выводит два изображения (рис.1 и рис.2). Цветом на изображениях отображается количество операций сравнения, использованных данным алгоритмом (чем краснее, тем больше). По горизонтальной оси откладывается количество правил, с которыми выполняется сверка. По вертикальной – количество используемых признаков объектов.

Программа 3 (speedtests.m и speedtests.fig): Сравнительная оценка вычислительной сложности алгоритмов последовательного перебора и индуктивного прогнозирования состояний при изменении параметров входных данных.

Программа 3 реализует возможность оценки сложности этих алгоритмов при изменении параметров входных данных. Есть возможность оценки зависимости вычислительной сложности алгоритма от количества используемых признаков (форма 1 – рис. 3), а также оценка зависимости сложности алгоритмов в зависимости от количества используемых правил (форма 2 – рис. 4). При этом возможно в форме отображаемой входные условия указать в случае 1 (форма 1) максимальное количество правил, до которого производится исследование и количество используемых признаков. В случае 2 (форма 2) указывается максимальное количество признаков, до которого производится исследование, и количество используемых правил. В формах 1 и 2 предусмотрена опция изменения параметров входных данных: изменение характеристик правил, настройка проверяемых объектов и настройка качества тестов (изменение количества проверяемых объектов и количества тестовых наборов правил). Поля из раздела «Настройка качества теста» определяют сколько различных наборов правил будет использовано при тестировании алгоритмов и сколько на каждом наборе правил будет протестировано объектов. Чем больше значения данных полей, тем дольше производится оценка. Но маленькие значения дают погрешности при вычислении (например, падение сложности алгоритма индуктивного прогнозирования состояний при 9 правилах – результат погрешности).

Рис. 3. Оценка вычислительной сложности алгоритмов от количества признаков (при количестве признаков до 9)

Рис. 4. Оценка вычислительной сложности алгоритмов от количества правил (при количестве признаков - 9, при количестве правил до 100)

На рис.5 и рис.6 представлены зависимость коэффициента выигрыша (раз) от количества правил и количества признаков.

Таким образом, можно сделать следующие выводы:

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

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

от 3 до 4,3 раз (при количестве признаков 6, среднее количество проверок на объект 200/600 и при количестве признаков 9, среднее количество проверок на объект 210/900);

от 3 до 6,8 раз (при количестве признаков 6, среднее количество проверок на объект 210/640 и при количестве признаков 15, среднее количество проверок на объект 220/1500);

от 3 до 4,5 раз (при количестве признаков 9; при количестве правил 30, среднее количество проверок на объект 60/280 и при количестве правил 100, среднее количество проверок на объект 200/900);

от 5,8 до 12,8 раз (при количестве признаков 15; при количестве правил 30, среднее количество проверок на объект 70/464; при количестве правил 100, среднее количество проверок на объект 250/1500; при количестве правил 200, среднее количество проверок на объект 260/3000).

Применение адаптированного метода индуктивного прогнозирования состояний позволило сократить объем вычислений и получить средний выигрыш K средний ≈ 9,3 (в зависимости от количества признаков и правил выигрыш от 3 до 12,86 раз) и тем самым снизить время обнаружения КА.