УДК 004.056

Нейросетевой подход к иерархическому представлению
компьютерной сети в задачахинформационной безопасностиМ. А. Басараб 1, С. В. Вельц 1
1МГТУ им. Н.Э. Баумана, Москва, 105005, Россия

Рассмотрена задача создания иерархического представления компьютерной сети. Задача сведена к задаче о покрытии множества;предложен нейросетевой подход на основе сетей Хопфилда для еерешения.

E-mail: bmic@mail.ruКлючевые слова: задача о покрытии множества, нейросетевая оптимизация, сеть Хопфилда, машина Больцмана.

Рассматриваемая задача создания иерархического представления
компьютерной сети, пригодного для проведения многомасштабного
анализа методами машинного обучения, является актуальной. Ее решение позволит эффективнее управлять сетями, повышая качествообслуживания, и обнаруживать новые типы аномалии для обеспечения информационной безопасности. Под многомасштабностью понимают применение выбранного метода машинного обучения копределенному уровню представления, что дает возможность выбирать степень обобщения информации, обнаруживать взаимосвязимежду частями системы в определенном масштабе, снижать вычислительную сложность задачи.
В качестве инструментов многомасштабного анализа могут выступать графовые нейронные сети (Graph Neural Network — GNN)
[1, 2] или иерархическая темпоральная память (HTM) [3]. И теми, идругими методами обрабатывают информацию, представленную ввиде графа. Однако нейроны в GNN получают только локальную информацию от своих соседей, что не позволяет обобщать и находитьвзаимосвязи между разными частями графа. В случае HTM необходимо сформировать структуру связей между узлами/нейронами вразных слоях. В обоих случаях встает задача выбора подмножествавершин графа для формирования следующего слоя. При этом любаявершина графа должна либо входить в выбранное подмножество, либо быть смежной хотя бы с одной вершиной из выбранного подмножества. Это приводит к задаче о вершинном покрытии, которая сводится к задаче о покрытии множества (SCP).
Поскольку задача о покрытии множества является NP-полной [4]и размер задач, требующих решения, достаточно велик, найти точноерешение с помощью вычислений сложно. Это обусловливает необходимость применения приближенных эвристических алгоритмов, среISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 20131ди которых можно отметить методы лагранжевой релаксации [5 — 7],генетические алгоритмы [8 — 11], поиск с запретами [12], алгоритмымуравьиной колонии [13], нейронные сети [14, 15]. Авторами даннойработы предлагается нейросетевой метод для решения задачи о покрытии множества. Отличие этого метода заключается в использовании машины Больцмана совместно с методом Монте-Карло дляборьбы с локальными минимумами. Также в данной работе предложена эвристика для оценки метапараметров модели.
Нейронные сети выбраны из следующих соображений. Вопервых, в качестве метода машинного обучения можно применять инейронные сети (GNN или HTM). Использование нейросетевого алгоритма и на этапе построения представления позволит получитькомплексное решение проблемы в рамках парадигмы нейрокомпьютинга. Во-вторых, нейросетевые архитектуры по своей сути обладают параллелизмом, благодаря чему возможна реализация алгоритма для параллельных вычислительных архитектур.
Постановка задачи. Перед тем как поставить задачу, неформально опишем требуемый результат.
Целью является последовательное формирование уровней иерархического представления сети. Для этого на каждом шаге необходимо выбрать подмножество элементов сети так, чтобы оно вместе со смежными элементами покрывало всю сеть. Желательно, чтобы размер этогоподмножества был минимален и количество смежных элементов, которые покрываются выбранным элементом (степень вершины), было небольшим. Последнее требование связано с тем, что возрастание степени
вершины ведет к увеличению длины вектора признаков для алгоритмовмашинного обучения и соответственно к экспоненциальному увеличению требуемого размера обучающей выборки.
Перейдем к формальной постановке задачи в виде SCP.
Пусть даны множество М, |M| = n и множество S подмножеств M
S = {S1, ..., Sm}. Пусть задана матрица A размерности n × m, aij = 1, если ai ∈ S j , иначе aij = 0.
Обозначим: ai — i-ю строку матрицы A; x — вектор-столбец, кодирующий решение, x = ( x1 , ..., xm ), где xi = 1, если Si входит в решение, и 0 — если иначе; с — вектор-столбец цен подмножеств; s —вектор-столбец размеров подмножеств, s = ( S1 , …, S m ).
Введем целевой функционал:nQ0 ( x ) = K1cx + K 2 ∑ xi Si = ( K1c + K 2 Si ) x.

(1)

i=1

Первое слагаемое задает цену решения. Второе задает штраф завыбор подмножеств с большой степенью. Коэффициенты K1, K2определяют относительное влияние штрафов на общее решение.
Задача формулируется как задача дискретной оптимизации сограничениями:2

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013

Π minQ0 ( x).
x,s.t.решение корректное(2)Решение X называется корректным, если оно покрывает все элементы множества M, т. е. M = ∑ Si .
Si∈XНейросетевой метод решения. Задача (1) — эквивалентная задача о покрытии множества. Подробный обзор методов решения
приведен в [16]. Можно выделить точные алгоритмы, жадные алгоритмы (Хватал), генетические, нейросетевые. Здесь подробнее остановимся на последних.
Исторически применение нейронных сетей для решения задачкомбинаторной оптимизации было направлено в основном на задачу
коммивояжера [17]. Подробный обзор нейросетевых методов комбинаторной оптимизации дан в [15].
Рассмотрим дискретную нейронную сеть Хопфилда из n {–1,+1}нейронов.
Состояния нейронов кодируются {–1, +1}-вектором y = ( y1 ,…, yn ).
Решение кодируется {0, 1}-вектором x = ( y + 1) / 2. Нейроны обрабатываются асинхронно и в случайном порядке (условие отсутствия осцилляций в динамике сети). Начальное состояние нейронов выбираетсяслучайным образом.
Учет ограничений в нейронных сетях при комбинаторной оптимизации заключается в модификации выражения энергии сети. Общий подход разработан в [18] для двухслойной модели Extended
Hopfield Model (EHM). Также может быть модифицирован механизмактивации нейронов [19].
Для получения корректного решения (т. е. покрывающего всеэлементы M) модифицируем целевой функционал Q0 так, чтобы онвключал дополнительный штраф за непокрытые вершины:nQ ( x ) = ( K1c + K 2 s ) x + K 3 ∑ h( ai x ),(3)i=1

где h(u) — функция штрафа за покрытие элемента u раз, например:h(u) = c0[u = 0] или h(u) = c0(u – 1)2. Далее рассмотрим эти вариантыподробнее.
Для определения значений коэффициентов используется следующая эвристика: в результате решения задачи алгоритмом (1) стоимость выбранного подмножества должна быть равна выигрышу отпокрытия вершин. Коэффициенты K1 и K2 приравнивают 1 и 0 соответственно и определяется K3.
Несмотря на пост-обработку решения, некорректные решенияпоявляются часто [15]. Для того чтобы решить эту проблему, приходится применять дополнительные шаги пост-обработки на основежадного алгоритма Хватала [20, 21]
ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 20133Алгоритм 1. Жадный алгоритм пост-обработки решения:Вход: M, SВыход: X — подмножество S
while есть непокрытые элементы:U : = M ⋅ ∑ Si — множество непокрытых элементовSi∈X⎧ S ∩U ⎫x: = argmax S ⎨ i⎬ — оптимальное множествоi⎩ ci ⎭
X:= X ∪ x
endwhile
while истина:T = { x ∈ X |X ⋅ x — корректное решение}if |T| = 0 then прервать цикл endif
x: = argmax v ∈T cii

X:= X ⋅ xendwhile
return X.
Энергия сети и функция Ляпунова. Энергию нейронной сетиХопфилда задают стандартным выражением:E=−n
1 n nwxx–∑∑ ij i j ∑ Ii xi .
2 i=1 j=1
i=1(4)

В [22] показано, что этот функционал является функцией Ляпунова, т. е. E ( xˆ ) = 0 (достаточно E ( xˆ ) = min x∈B E ( x) ), B — некотораялокальная область притяжения), E ( x ) > 0, x ≠ xˆ (знакоположительность) и dE / dt < 0 (диссипативность системы), где x̂ — устройчивое
состояние (точечный аттрактор). Из этого следует, что система стремится к устойчивому состоянию.
Замечание 1. Функция (4) является квадратичной формой, нонесмотря на это, у нее может быть несколько локальных минимумов,так как модель дискретная (в непрерывном случае есть еще интеграл)и значения x ограниченны.
Замечание 2. Функция (4) для дискретной сети, в непрерывномxjслучае еще есть интеграл ∫ φj−1 ( x)dx (см. [22]). Однако в статьях ча0сто встречается непрерывная модель, например, функции активации1
1g (u ) = (1 + th(ku ) ) или g (u ) =, при этом выражение (4)2
1 + exp( − ku )используется в качестве энергии сети и функции Ляпунова.
4

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013Определение параметров модели. Рассмотрим, как, имея целевой функционал, определить параметры модели (веса и смещениянейронов).
1. Квадратичная функция штрафа.
Пусть h( x) = C p ( x − 1) 2 , где Cp — коэффициент штрафа.
Замечание 3. Это неудачная функция, так как штрафуем двукратное покрытие так же, как и непокрытие.
Замечание 4. Квадратичная функция широко используется в статьях, так как позволяет получить удобные аналитические выражения.
Раскрывая (3) и приравнивая к (4), получаем веса и смещения:w jk = −Cp n∑ aij aik ;2 i=1nn n⎞
1⎛
I j = − ⎜ c j – 2C p ∑ a jk + C p ∑∑ aik aij ⎟.
2⎝
k=1
k=1 i=1
⎠

(5)

(6)

Отметим, что wij = w ji , но wii ≠ 0, это является необходимым условием устойчивости работы сети [20] (в случае wii ≠ 0 возможна осцилляция сети). Для того чтобы это компенсировать, можно изменитьусловие остановки процесса оптимизации с учетом возможных осцилляций.
2. Разрывная функция штрафа.
Пусть теперь h( x) = C p [ x = 0] , где Cp — коэффициент штрафа.
Проблема с данным функционалом заключается в том, что он разрывени напрямую получить выражение для параметров модели не удается.
Эту проблему можно решить двумя способами:1) использовать непрерывную аппроксимацию, напримерCphˆ( x ) =, а для получения выражений параметров сети рас1 + exp(αx )кладывать получившийся целевой функционал в ряд Тейлора в текущей точке. Поскольку текущая точка постоянно изменяется, разложение потребуется постоянно пересчитывать, что негативно влияетна быстродействие. К тому же разложение корректно в небольшой
окрестности текущей точки, а движение осуществляется по вершинам гиперкуба;2) модифицировать механизм активации нейронов — использоватьидею, похожую на машину Больцмана. В нейроне будем принимать
решение не пороговым правилом на основе локального потенциалаn∑ wij xi − θ j , а считать целевые функционалы для разных состоянийi=1

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 20135

ними ΔQi =1= Q ( xi = 1) − Q ( xi = 0) c вероятностью P[ xi = 1] =,1 + exp( − ΔQi / T )T — «температура» сети. Будем переводить нейрон в возбужденноесостояние.
Отметим, что возможность выбирать состояния, в которых целевой функционал возрастает, позволяет сети выходить из локальныхминимумов.
Результаты вычислительного эксперимента. Описанный вышеалгоритм был реализован на языке Scala (объектно-функциональноерасширение Java). Оценка эффективности предложенного алгоритмапроведена на тестовых задачах из набора OR Library. Набор включаетв себя 65 задач различной размерности.
Поскольку результат применения алгоритма зависит от случайного начального состояния нейронной сети, для каждой задачи проводили пять запусков и результаты усредняли. Результаты расчетовприведены в табл. 1.
Для задач классов E—H оптимальные решения неизвестны из-забольшой размерности задач. Для оценки были использованы предполагаемые решения, указанные в [8]. Результаты расчетов приведены втабл. 2.
В 57 задачах из 65 предложенный нейросетевой алгоритм показалрезультат лучше, чем алгоритм Хватала. Средняя цена решения алгоритмом Хватала — 207,6, предложенным алгоритмом — 204,3. Средняя предполагаемая оптимальная цена — 196,6. Среднее время расчетов — 14 с на задачу.
Построение иерархического представления. Используя решениеSCP, можно создать алгоритм построения иерархического представления. Принцип работы заключается в итерационном решении SCP.
Алгоритм 2. Построение иерархического представления на основе SCP.
Вход: граф G = (V, E), цены вершин c.
Выход: N = ((G1, A1), (G2, A2), …, (GL, AL)), где Ai — данные опринадлежности вершин.
N : = () — сначала слоев нетVc : = V
Ec : = E
while |Vc| > 1: — формируем новые слои, пока не получим однувершину в слое.
S : = SolveSCP(Vc, Ec) — S является подмножеством Vc
A : = {}
Vc : = {}Ec : = {}head : = {} — отображение множества эквивалентных вершин впредставителя
рассматриваемого6нейрона

иразность

между

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013Таблица 1Результаты вычислительного эксперимента по сравнению алгоритмовРешение

РешениеНомер
задачи

нейрон- Номероптизадачи
ноймальноесетью

жадным
алгоритмом

нейронной
сетью

131

137

136

6.5

161

178

178

539

A.1

253

271

262

510

506

A.2

252

267

261

512

519

520

A.3

232

244

239

4.6

560

594

586

A.4

234

246

242

4.7

430

449

447

A.5

236

247

240

4.8

492

502

502

B.1

69

73

71

4.9641

672

658

B.2

76

78

78

4.10

514

521

517

B.3

80

85

81

5.1

253

271

268

B.4

79

85

84

5.2

302

329

328

B.5

72

76

74

5.3

226

232

230

C.1

227

246

239

5.4

242

253

251

C.2

219

231

229

5.5

211

220

216

C.3

243

256

256

5.6

213

234

228

C.4

219

239

236

5.7

293

311

306

C.5

215

228

220

5.8

288

308

301

D.1

60

68

65

5.9

279

290

290

D.2

66

70

67

5.10

265

274

273

D.3

72

78

75

6.1

138

147

145

D.4

62

65

63

6.2

146

160

153

D.5

61

71

63

6.3

145

152

149

оптимальное

жадным
алгоритмом

4.1429

438

437

6.4

4.2

512

551

551

4.3

516

546

4.4

494

4.5

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 20137Таблица 2Результаты вычислительного экспериментадля задач большой размерностиРешение
НомерзадачиРешение
нейрон- Номероптизадачиноймальноесетьюжаднымалгоритмомнейронной
сетью

179

194

186

G.2

158

165

163

28

G.3

169

179

173

32

29G.4

172

184

178

28

31

28

G.5

168

181

179

F.1

141715

H.1

64

71

68

F.2

15

1615

H.2

64

69

68

F.3

14

1615

H.3

60

65

64

F.4

1415

15

H.4

59

66

63

F.5

1415

14H.5

5562

59

оптимальное

жаднымалгоритмом

E.1

29

31

29

G.1

E.2

303432E.3

2732E.4

28E.5

for v in S:

Ai : = v ∪ {смежные с v вершины}A : = A ∪ Ai
Vc : = Vc ∪ v
head Ai : = v

endforfor a in A, for b in A \ a: — создаем ребраif ∃vi ∈ a ∧ v j ∈ b:(vi , v j ) ∈ E then:
Ec : = Ec vi , v j ∪ (head a, head b)
endif
endfor
N := N ∪ ((Vc, Ec), A) — добавляем слойendwhile
return NконецПример работы алгоритма 2 представлен на рисунке.

8ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013Схема работы алгоритма 2В данной работе рассмотрено решение задачи о покрытии множества в рамках нейросетевой парадигмы и на его основе предложеналгоритм построения иерархического представления компьютернойсети. Описанные результаты могут найти применение при построении систем обнаружения аномалий в сетях и прогнозирования поведения трафика.
СПИСОК ЛИТЕРАТУРЫ1.

S c ars e l l i F . A short description of the Graph Neural Network toolbox.
2011. URL: http://www.dii.unisi.it/~franco/Research/GNN_DOC.pdf
2. The graph neural network model / F. Scarselli, M. Gori, A.C. Tsoi, G. Monfardini // IEEE Transactions on Neural Networks. 2009. Vol. 20. No 1.
P. 61–80.
3. D i l eep G ., B obb y J aros . The HTM learning algorithms // Numenta
Inc., 2007. URL: http://www.numenta.com
4. K arp R . M. Reducibility among combinatorial problems: Complexity ofcomputer computations. Proc. of a Symp. on the Complexity of Computer
Computations / R.E. Miller, J.W. Thatcher, eds. [The IBM Research Symposia Series]. N.-Y.: Plenum Press, 1972. P. 85–103.
5. B a l a s E., Ca rr era M. C. A dynamic subgradient-based branch and boundprocedure for set covering // Oper. Res. 1996. Vol. 44. No 6. P. 875–890.
6. B e a s le y J. E. A Lagrangian heuristic for set-covering problems // NavalRes. Logist. 1990. Vol. 37. No 1. P. 151–164.
7. C ap rar a A ., F i s che t t i M . , To th P. Algorithms for the set covering
problem // DEIS — Operations Research Group. 1998. Technical Rep.
No OR-98-3.
8. Н г у е н М инь Х а н г. Применение генетического алгоритма для задачинахождения покрытия множества // Тр. ИСА РАН. 2008. № 33. C. 206–219.
9. Ер ем е ев А.В . Генетический алгоритм для задачи о покрытии // Дискретный анализ и исследование операций. Сер. 2. 2000. Т. 7. № 1. С. 47–60.
10. Back Th., Schiiltz M., Khuri S. A comparative study of a penalty
function, a repair heuristic, and stochastic operators with the set-covering

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 20139problem // Artificial Evolution. Proc. Berlin: Springer, 1996. P. 3–20. (Lecture Notes in Comput. Sci.; Vol. 1063.)
11. B e a s le y J.E. , Chu P. C. A genetic algorithm for the set covering problem // European J. Oper. Res. 1996. Vol. 94. No. 2. P. 394–404.
12. R a m a l h inho H ., P in to R ., Por tug al R . Metaheuristics for the busdriver scheduling problem // Univ. Pompeu Fabra. Economic WorkingPapers Series. Technical Rep. 1998. No 304.
13. A l exandrov D., Koch e tov Yu. Behavior of the ant colony algorithm
for the set covering problem // Operations Research Proc. 1999 (Magdeburg,1999). Berlin: Springer, 2000. P. 255–260.
14. Gro ss m a n Т. , Wool A . Computational experience with approximation
algorithms for the set covering problem // European J. Oper. Res. 1997. Vol.
101. No 1. P. 81–92.
15. S m i t h K.A . Neural networks for combinatorial optimization: A review ofmore than a decade of research // Informs journal on Computing. 1999. Vol.
11. No 1. P. 15–34.
16. Ер ем е ев А.В ., Зао зер ск а я Л .А., Ко локо ло в А.А . Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций. 2000. Т. 7.
C. 22–46.
17. Hopf i e ld J.J ., T ank D.W. “Neural” computation of decisions in optimization problems // Biological Cybernetics. 1985. No 52. P. 141–152.
18. Ab e, K awaka m i , H ir a saw a. Solving inequality constrained combinatorial optimization problems by the Hopfield neural network // Neural Networks. 1992. Vol. 5. No 4. P. 663–670.
19. Le Gall, Zissimopoulos. Extended hopfield models for combinatorial
optimization // IEEE Transactions on Neural Networks. 1999. Vol. 10.
No 1. P. 72–80.
20. C ohen , G ros sb erg. Absolute stability of global pattern formation andparallel memory storage by competitive neural networks // IEEE transactions
on systems, man, and cybernetics. 1983. No 5. P. 815–826.
21. C hva t a l V .A. Greedy heuristic for the set-covering problem // Mathematicsof Operations Research. 1979. Vol. 4. No 3. P. 233–235.
22. Х а йк и н C . Нейронные сети: полный курс: пер. с англ. 2-е изд. М.: Вильямс, 2006. 1104 c.
Статья поступила в редакцию 25.10.2012

10ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013