Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Cybernetics and programming
Reference:

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

DOI:

10.7256/2306-4196.2014.6.13306

Received:

02-11-2014


Published:

16-11-2014


Abstract: The article presents a comparison of computational complexity of two logical classification algorithms: an algorithm of sequential search (brute force) and algorithm of inductive states prediction. Logic algorithms are implemented in Matlab. For comparison of the computational complexity of classification algorithms author uses Zakrevskiy technique. Classification problem is one of the main problems in detection of threats of cyber attacks in the information system. Information about the signs of cyber attacks detection can be received from various sources (sensors) of software and hardware of the information system, for example, antivirus tools, dumps RAM logs, hard drives, user logon information, etc. Each of those sources contain information that can be used to determine the presence of an attack on the system. The article reviews the problem of logical classification of already existing data using two algorithms: an algorithm of sequential search (brute force) and algorithm of inductive states prediction. The use of the adapted method of inductive states prediction allowed to reduce amount of computation and get the average gain K ≈ 9,3 and thereby reduce time of detection of computer attacks.


Keywords:

logical classification algorithm, inductive algorithm, software, algorithm, threat, security, computational complexity, brute force, states prediction, Matlab


Введение

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

Методика оценки алгоритмов классификации

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

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

Представим булеву матрицу исследуемого класса A1 образованной 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):

81 (3)

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

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

83 (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). Цветом на изображениях отображается количество операций сравнения, использованных данным алгоритмом (чем краснее, тем больше). По горизонтальной оси откладывается количество правил, с которыми выполняется сверка. По вертикальной – количество используемых признаков объектов.

84

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

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

85

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

86

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

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

87

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

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 раз) и тем самым снизить время обнаружения КА.

References
1. Sidel'nikov, O.V. Primenenie metoda induktivnogo prognozirovaniya sostoyanii dlya obnaruzheniya komp'yuternykh atak v informatsionno-telekommunikatsionnykh sistemakh / O.V. Sidel'nikov, V.N. Laptev, V.A. Sharai // Nauchnyi zhurnal KubGAU [Elektronnyi resurs]. – Krasnodar: KubGAU, 2011. – № 72(08). – 10 s. URL: http://ej.kubagro.ru/2011/08/pdf/37.pdf.
2. Sidel'nikov, O.V. Model' obnaruzheniya i identifikatsii komp'yuternykh atak v informatsionno-telekommunikatsionnykh sistemakh na osnove metoda in-duktivnogo prognozirovaniya sostoyanii / O.V. Sidel'nikov // Informatsionnye tekhnologii v professional'noi deyatel'nosti i nauchnoi rabote. Sbornik materialov Vserossiiskoi nauchno-prakticheskoi konferentsii s mezhdunarodnym uchastiem: v 2 ch. Ch. 1. Materialy. – Ioshkar-Ola: Mariiskii GTU, 2012. – S.177-182.
3. Sidel'nikov, O.V. Algoritm obnaruzheniya i identifikatsii komp'yuter-nykh atak v informatsionno-telekommunikatsionnykh sistemakh na osnove metoda induktivnogo prognozirovaniya sostoyanii / O.V. Sidel'nikov // Perspektivy razvitiya informatsionnykh tekhnologii: sbornik materialov VII Mezhdunarodnoi nauchno-prakticheskoi konferentsii, pod obshch. red. S.S. Chernova. – Novosibirsk: NGTU, 2012. – S.267-272.
4. Zakrevskii, A.D. Logika raspoznavaniya. Izd.2-e, dop. / A.D. Zakrevskii – M.: Editorial URSS, 2003. – 144 s.