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

Полный текст

Введение

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

Графические процессоры – это высокопроизводительные многоядерные процессоры. Возможность использования потенциала графического процессора в неграфических задачах привела к росту интереса пользователей и технических специалистов к графическим GPGPU и гибридным CPU+GPU вычислениям. Использование гибридных CPU+GPU систем для решения задач оптимизации систем защиты информации является перспективным направлением: при небольшом энергопотреблении обеспечивается высокая производительность – радикально сокращается время, необходимое для вычислений и получения оптимальных решений. Cложность вычислений на GPU заключается как в обработке нерегулярных структур данных, которые не очень подходят для вычислений на графическом процессоре, так и в передаче информации между группами процессоров. Простая структура, скудный набор инструкций и отсутствие кэш-памяти графических ядер накладывают свои ограничения.

Как известно, существуют следующие основные программные методы обнаружения компьютерных вирусов:

– сканирование;

– обнаружение изменений;

– резидентные "сторожа";

– эвристический анализ;

– вакцинирование программных средств.

Такие действия, как, например, сканирование программных средств с использованием известных вирусных сигнатур (или их контрольных сумм), достаточно цикличны и позволяют с высокой эффективностью реализовать частичную обработку таких данных на графическом процессоре. Таким образом, использование распределенных вычислений на комбинированных CPU+GPU системах поможет перераспределить незадействованные системой ресурсы и в перспективе увеличить общее быстродействие автоматизированной системы. Задача центрального процессора будет состоять в обработке непараллельных вычислений, требующих более сложных наборов инструкций и организации обмена данных и вычисленных решений между множеством ядер графического ускорителя. Однако организация обмена данных также может создать очередь и нивелировать все преимущества комбинированных вычислений, поэтому использование CPU+GPU систем в той или иной степени сводится к задаче составления расписания для многопроцессорных систем. В статье [1] автор на примере описывает преимущества метода ветвей и границ над полным перебором множества всех имеющихся вариантов решения задачи коммивояжера. Начиная с восьми городов в маршруте преимущества метода ветвей и границ становятся явными. В современных же моделях видеоадаптеров количество процессоров измеряется не десятками, а тысячами – GeForce RTX 2080 Ti Gaming Z Trio, например, имеет 4352 универсальных процессора [2]. Поэтому составление расписания в многопроцессорных системах будем рассматривать на основе метода ветвей и границ.

 1. Совместное использование ресурсов автоматизированной системы. Преимущества CPU+GPU систем

По результатам сравнительного исследования 18 продуктов безопасности (антивирус Касперского, Avast, AVG, McAfee, Norton Security, Total Security, Windows Defender и др.), проведенного в декабре 2019 года немецкой независимой лабораторией, специализирующейся на проверке и тестировании ведущих образцов антивирусного и защитного программного обеспечения, было выяснено: все средства защиты информации (в том числе предустановленный в Windows 10 защитник Windows Defender) в базовых настройках в среднем замедляют загрузку сайтов на 12–21 %, загрузку (запуск) приложений – на 13–30 %, установку стандартных приложений – на 18–51 %, а копирование и перенос файлов – на 5–25 % (см. таблицу). Для примера, защитник Windows Defender может замедлять установку приложений до 51 % [3]. Тестирование производилось на двух видах систем:

Среднепроизводительная система (standart) – на базе Intel i3-6100, 8 ГБ оперативной памяти, SSD-накопителем на 256 ГБ на операционной системе Windows 10 Professional 64bit;

Высокопроизводительная система (high-end) – на базе Intel i7-7770, 16 ГБ оперативной памяти, SSD-накопителем на 256 ГБ на операционной системе Windows 10 Professional 64bit.

 

Влияние средств защиты информации с базовыми настройками на скорость работы информационной системы, %

Вид замедления	Усредненные данные 18 продуктов безопасности		Антивирус Касперского
	standart	high-end	standart	high-end
Замедление загрузки веб-сайтов	17–21	12–17	18–23	16–21
Замедление загрузки файлов	1–6	1–5	0–1	0–1
Замедление загрузки (запуска) стандартных приложений	15–30	13–14	10	7–8
Замедление установки популярных приложений	18–34	12–51	11–30	12–29
Замедление копирования файлов (локально и в сети)	5–13	5–25	1–2	1–3

 

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

Для формализации описания вариантов задействования ресурсов автоматизированной системы введем следующие обозначения:

PU (Protection Unit) – подмножество необходимых ресурсов, которое необходимо задать для выполнения функции защиты информации автоматизированной системы за интервал времени .

BU (Base Unit) – подмножество необходимых ресурсов, которое необходимо задать для решения задач в интересах автоматизированной системы за интервал времени .

M (Memory) – ресурс памяти (совокупность физической и операционной памяти автоматизированной системы).

CPU (Central Processor Unit) – вычислительный ресурс центрального процессора.

GPU (Graphics Processing Unit) – вычислительный ресурс графического процессора.

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

 

Рис. 1. Совместное использование ресурсов автоматизированной системы в промежуток времени t при классическом подходе

 

Перейдем к формализованному описанию. Подмножество $PU\subset (CPU\cup M)$ и $BU\subset (CPU\cup GPU\cup M)$. Для сохранения оперативности автоматизированных систем и сохранения должного уровня информационной безопасности необходимо, чтобы $PU\cap BU=0$. Отсутствия пересечений данных множеств можно добиться двумя способами – путем увеличения времени $\Delta t$ (что недопустимо по условию оперативности) или путем приращения неиспользуемых вычислительных ресурсов системы. За счет распараллеливания логико-математических задач защиты информации и подключения GPU возможно снятие части вычислительной нагрузки с CPU (рис. 2). Тогда $PU\subset (CPU\cup GPU\cup M)$.

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

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

 

Рис. 2. Совместное использование ресурсов автоматизированной системы в промежуток времени t при использовании ресурсов GPU в интересах ЗИ

 

2. Составление оптимального расписания для гибридной многопроцессорной системы

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

Формализуем данную проблему. Разобьем условный процесс системы защиты информации на множество задач $P \left\{p_1,p_2\mathrm{...}{p}_n\right\}$. Т. к. рассматриваются параллельные вычисления, определим, что на конечный итог работы системы защиты информации не влияет последовательность выполнения задач на процессорах. Количество рассматриваемых процессоров примем равное $m$. $m$ является собственным подмножеством множества процессоров CPU и множества процессоров GPU, т. е. $m\subset (CU\cup GU)$ и $m\ne (CU\cup GU)$. Длительность выполнения задачи $p_i$ на процессоре $j$ обозначим $t_{p_{i}j}$, где $i=\overline{\mathrm{1,}n}$, $j=\overline{\mathrm{1,}m}$. $L_j$–длина задач на процессоре $j$.

Таким образом, длина расписания выражается как $\max L_j$.

Минимальную длину расписания тогда можно представить следующим образом:

$\mathrm{minmax}{L}_j$,

т. е. ищется такое распределение задач, при котором наибольшая величина $L_j$ принимает минимальное значение.

Метод ветвей и границ подразумевает решение подобных задач как разбиение множества всех допустимых решений на подмножества, для которых определяются верхние и нижние границы минимального времени выполнения задач. Если при сравнении двух подмножеств нижняя граница $F_l$ первого подмножества оказывается больше, чем верхняя граница $F_h$ второго подмножества, то первое подмножество в дальнейших расчетах игнорируется, т. к. оптимальная длина расписания там отсутствует.

Данные расчеты производятся для отдельно взятого процесса на гибридном CPU+GPU вычислителе. Следовательно, определенная часть задач этого процесса может быть уже назначена на конкретные процессоры существующими инструкциями. Обозначим часть назначенных задач – $k$. Вершина $k$ может находиться в произвольном месте дерева решений между корнем (уровнем 0) и листьями (конечным уровнем $p_n$). Для $k$ задач, соответственно, известно $L_j$. Тогда 

$F_l=(\underset{j=1}{\overset{m}{}}{L}_j+\underset{p_i=k+1}{\overset{p_n}{}}\underset{j=\overline{\mathrm{1,}m}}{\min }{t}_{p_{i}j}).$

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

 

Рис. 3. Блок-схема работы жадного алгоритма

 

Для поиска $F_h$ можно применить жадный алгоритм (рис. 3). Заполнение задачами процессоров по этому алгоритму будет выглядеть следующим образом:

1. Назначить первую из задач $p_i=\overline{k+\mathrm{1,} p_n}$ на процессор $j$ с минимальной длиной задач $min{L}_j$.
2. Перейти к следующей задаче $p_i:=p_i+1$. Если все задачи назначены, то далее следует выход из алгоритма.
3. Назначить задачу $p_i$ на процессор $u$ (с минимальной длиной задач после предыдущего назначения $Q$), $u=\overline{\mathrm{1,}m}$,  $Q_j=\max \left(L_1, \dots , L_{j-1}, L_j+t_{p_{i}j}, L_{j+1},\dots \right)$, $\underset{j=\overline{\mathrm{1,}m}}{\min }{Q}_j=Q_u$, возврат в п. 2.

Когда все задачи назначены, находим максимальную длину расписания и принимаем ее как верхнюю оценку $F_h$ для выбранной вершины уровня k:

$F_h=\underset{j=\overline{\mathrm{1,}m}}{\max }{L}_j$.

Оптимальное расписание $F_o$ находится в диапазоне $F_l\le F_o\le F_h$.

3. Выбор стратегии ветвления метода ветвей и границ. Критерий эффективности, показатели эффективности

Существуют две основных стратегии построения дерева в методе ветвей и границ – одностороннее ветвление и фронтальное ветвление.

При выборе стратегии одностороннего ветвления на каждом уровне выбирается вершина с минимальной нижней оценкой, остальные вершины этого уровня игнорируются. Ветвление происходит только из вершины вышестоящего уровня c $\min F_l$ (рис. 4).

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

 

Рис. 4. Стратегия одностороннего ветвления

 

Как известно, более компактной форме представления, содержащей меньшее количество логических операций, будет соответствовать более производительная программная и менее громоздкая аппаратная реализация [5]. Соответственно, при выборе стратегии одностороннего ветвления времени для вычислений необходимо больше, памяти – меньше, при выборе фронтальной стратегии ветвления, наоборот, времени для вычислений необходимо меньше, памяти – больше.

 

Рис. 5. Стратегия фронтального ветвления

 

Для выбора стратегии в конкретной автоматизированной системе необходимо произвести анализ физических и вычислительных возможностей системы, а также ряда требований к быстродействию и защите информации. В любом случае основным показателем эффективности работы рассматриваемых систем будет время $t$.

Критерием эффективности может быть минимальное время вычисления составления расписания: $\text{min t}$ при имеющихся ограничениях на ресурсы системы $r\to lim$. Ресурсами системы являются объем оперативной и физической памяти, тактовые частоты процессоров, количество логических элементов и т. д.

Показателем объемной эффективности будет являться отношение количества бит, используемых для хранения всех возможных вершин дерева решений $N_{фв}^{кб}$, к количеству бит, используемых для хранения вершин при одностороннем ветвлении $N_{ов}^{кб}$:

$v=\frac{N_{фв}^{кб}}{N_{ов}^{кб}}$.

Показателем эффективности по сложности вычислений примем отношение количества выполняемых действий (тактов вычислителя), необходимых для вычисления оптимального расписания при фронтальном ветвлении $N_{фв}^{т}$, к количеству выполняемых действий (тактов вычислителя), необходимых для вычисления оптимального расписания при одностороннем ветвлении $N_{ов}^{т}$:

$d=\frac{N_{фв}^{т}}{N_{ов}^{т}}$.

Обобщенным показателем эффективности тогда будет:

$с=v\cdot d$.

Критерием эффективности будет  при всех возможных вариантах расчета расписания.

4. Распределенное программирование в распределенных автоматизированных системах

Помимо параллельных вычислений существует и другой метод, позволяющий повысить эффективность использования имеющихся ресурсов. Он основан на кардинально ином подходе к самому программированию – так называемом распределенном программировании [6]. Он позволяет, в том числе, реализовать использование удаленных ресурсов иной вычислительной системы сети в интересах пользователя. Распределенное программирование в той или иной степени включает в себя сетевое программирование и подразумевает общение посредством сетевого соединения между программами клиента и сервера [7]. Т. е. существует возможность использовать для параллельных вычислений, выполняемых на машине пользователя, вычислительные возможности, например, графического ускорителя соседней машины или сервера в распределенной автоматизированной системе.

Выводы

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

Дополнительное преимущество, получаемое за счет перераспределения вычислений конкретной ЭВМ на ресурсы всей распределенной автоматизированной системы, дает распределенное программирование.

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

Об авторах

Максим Сергеевич Гнутов

Краснодарское высшее военное орденов Жукова и Октябрьской Революции Краснознаменное училище имени генерала армии С.М. Штеменко

Автор, ответственный за переписку.
Email: monk666@bk.ru

адъюнкт отдела научной работы и подготовки научно- педагогических кадров.

Россия, 350063, г.Краснодар, ул. Красина, 4

Александр Борисович Сизоненко

Краснодарское высшее военное орденов Жукова и Октябрьской Революции Краснознаменное училище имени генерала армии С.М. Штеменко

Email: siz_al@mail.ru

д.т.н., доцент, начальник кафедры «Защита информации от несанкционированного доступа»

Россия, 350063, г.Краснодар, ул. Красина, 4

Список литературы

Дополнительные файлы