Methodology for distributing information protection tasks between computer devices of automated systems based on the branch and border method

Cover Page

Abstract


The influence of software protection on various information systems is analyzed. Using set theory, the use of computational resources for the joint solution of direct tasks and information protection tasks in an automated system is described. A hybrid implementation of computing in a CPU + GPU system is proposed. The relevance of using the branch and bound method to compile a minimum schedule of information security tasks in a hybrid multiprocessor system is considered. The features of processing data structures by various types of calculators are indicated. The computational strategies of the branch and bound method with the greatest possibility of acceleration with limited resources are analyzed. The efficiency criterion is selected, the performance indicators are considered when applying the frontal and one-sided branching strategies depending on the complexity of the calculations and the amount of occupied memory. The generalized indicator of efficiency is defined. The prospects of applying the considered method in distributed systems through distributed programming are emphasized.


Full Text

Введение

В составе современных автоматизированных систем используются сложные средства вычислительной техники, обеспечивающие обработку задач и выработку решений в разнообразных сферах жизнедеятельности человека. Для графических вычислений в данных системах традиционно используются графические процессоры (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(CPUM) и BU(CPUGPUM). Для сохранения оперативности автоматизированных систем и сохранения должного уровня информационной безопасности необходимо, чтобы PUBU=0. Отсутствия пересечений данных множеств можно добиться двумя способами – путем увеличения времени Δt (что недопустимо по условию оперативности) или путем приращения неиспользуемых вычислительных ресурсов системы. За счет распараллеливания логико-математических задач защиты информации и подключения GPU возможно снятие части вычислительной нагрузки с CPU (рис. 2). Тогда PU(CPUGPUM).

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

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

 

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

 

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

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

Формализуем данную проблему. Разобьем условный процесс системы защиты информации на множество задач P p1,p2...pn. Т. к. рассматриваются параллельные вычисления, определим, что на конечный итог работы системы защиты информации не влияет последовательность выполнения задач на процессорах. Количество рассматриваемых процессоров примем равное m. m является собственным подмножеством множества процессоров CPU и множества процессоров GPU, т. е. m(CUGU) и m(CUGU). Длительность выполнения задачи pi на процессоре j обозначим tpij, где i=1,n¯, j=1,m¯. Lj–длина задач на процессоре j.

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

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

minmaxLj,

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

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

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

Fl=(j=1mLj+pi=k+1pnminj=1,m¯tpij).

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

 

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

 

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

  1. Назначить первую из задач pi=k+1, pn¯ на процессор j с минимальной длиной задач minLj.
  2. Перейти к следующей задаче  pi:=pi+1. Если все задачи назначены, то далее следует выход из алгоритма.
  3. Назначить задачу pi на процессор u (с минимальной длиной задач после предыдущего назначения Q), u=1,m¯,  Qj=maxL1, , Lj1, Lj+tpij, Lj+1,, minj=1,m¯Qj=Qu, возврат в п. 2.

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

Fh=maxj=1,m¯Lj.

Оптимальное расписание Fo находится в диапазоне FlFoFh.

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

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

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

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

 

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

 

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

 

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

 

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

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

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

v=NфвкбNовкб.

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

d=NфвтNовт.

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

с=vd.

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

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

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

Выводы

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

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

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

About the authors

Maxim S. Gnutov

Krasnodar higher military school

Author for correspondence.
Email: monk666@bk.ru

Russian Federation, 4, Krasina str. Krasnodar, 350063

adjunct

Alexander B. Sizonenko

Krasnodar higher military school

Email: siz_al@mail.ru

Russian Federation, 4, Krasina str. Krasnodar, 350063

Dr. Sci. Techn., Associate Professor

References

  1. Resheniye zadachi kommivoyazhera algoritmom Littla s vizualizatsiyey na ploskosti [Solving the traveling salesman problem using the Little algorithm with visualization on the plane]. https://habr.com/en/post/332208 (accessed May 28, 2020).
  2. Videokarta MSI GeForce RTX 2080 Ti Gaming Z Trio poluchila boleye bystruyu pamyat' GDDR6 [The MSI GeForce RTX 2080 Ti Gaming Z Trio graphics card received faster GDDR6 memory]. https://www.hardwareluxx.ru/index.php/news/hardware/grafikkarten/49422 - videokarta - msi - geforce - rtx - 2080 - ti - gaming - z - trio - poluchila - bolee-bystruyu - pamyat - gddr6.html (accessed June 03, 2020).
  3. Antivirus & Securuty software Test. http://spkurdyumov.ru/economy/informacionnye-texnologii-sostoyanie-i-perspektivy (accessed October 02, 2020).
  4. Sravneniye sertifitsirovannykh sredstv zashchity informatsii ot nesanktsionirovannogo dostupa dlya serv-erov i rabochikh stantsiy (SZI ot NSD) [Comparison of certified means of protecting information from unau-thorized access for servers and workstations (SZI from NSD)]. https://www.anti-malware.ru/compare/information-protection-unauthorized-access-fstek-certified#part1 (accessed February 05, 2020)
  5. Sizonenko A.B. Logiko-matematicheskoye modelirovaniye i sintez algoritmov funktsionirovaniya sredstv i sistem zashchity informatsii: [Logical-mathematical modeling and synthesis of algorithms for the functioning of means and systems of information protection]. Krasnodar, Institute of the Ministry of the Interior of Rus-sia, 2013.146 p. (In Russian).
  6. Cameron H., Tracy H. Parallel'noye i raspredelennoye programmirovaniye na C++ [Parallel and distributed programming in C ++]. Williams, 2004. 672 p.
  7. Dostoinstva i nedostatki parallel'nogo programmirovaniya [Advantages and disadvantages of parallel pro-gramming]. http://web.snauka.ru/issues/2016/06/69538 (accessed June 06, 2020).
  8. Informatsionnaya tekhnologiya. Metody i sredstva obespecheniya bezopasnosti. Menedzhment riska infor-matsionnoy bezopasnosti GOST R ISO/MEK 27005-2010 [Information technology. Security methods and tools. Information Security Risk Management GOST R ISO / IEC 27005-2010]. Standartinform, 2011. 47 p. (In Russian).
  9. Kumar Jain A., Singh Y., Updhyay S. Information systems security: A review. Ind Jour Math & Comp Sc. Jhs., 2013, no. 2. Pp. 26-30.
  10. Boreskov A.V., Sadovnichiy V.A. Parallel'nyye vychisleniya na GPU. Arkhitektura i programmnaya model' CUDA : ucheb. Posobiye [GPU parallel computing. Architecture and software model CUDA] Publishing house of Moscow University, 2012. 336 p. (In Russian).
  11. Nvidia’s Next Generation CUDA Compute Architecture: KeplerTM GK110. http://www.nvidia.ru/content/PDF/kepler/NVIDIA-Kepler-GK110-Architecture-Whitepaper.pdf (accessed June 06, 2020).
  12. Doktrina informatsionnoy bezopasnosti Rossiyskoy Federatsii, utv. Ukazom Prezidenta Rossiyskoy Feder-atsii [The doctrine of information security of the Russian Federation, approved. Decree of the President of the Russian Federation No. 646 dated 12.05.2016] http://www.consultant.ru (accessed June 10, 2020).
  13. Sizonenko A.B. Modeli i algoritmy sinteza logikovychislitel'nykh podsistem zashchity informatsii sistem kriticheskogo primeneniya [Models and algorithms for the synthesis of logic-computing subsystems of in-formation protection of critical application systems]. Voronezh, 2016. 32 p. (In Russian).
  14. Informatsionnaya tekhnologiya. Metody i sredstva obespecheniya bezopasnosti. Menedzhment riska infor-matsionnoy bezopasnosti. Kriterii otsenki bezopasnosti informatsionnykh tekhnologiy. Chast' 1 - Vvedeniye i obshchaya model' [Information technology. Security methods and tools. Information Security Risk Man-agement. Criteria for assessing the security of information technology. Part 1 - Introduction and general model. GOST R ISO / IEC 15408-1-2012] Standartinform, 2013. 75 p. (In Russian).
  15. Informatsionnaya tekhnologiya. Metody i sredstva obespecheniya bezopasnosti. Kriterii otsenki bezopasnosti informatsionnykh tekhnologiy. Chast' 2 – Funktsional'nyye komponenty bezopasnosti [Information technol-ogy. Security methods and tools. Criteria for assessing the security of information technology. Part 2 – Functional safety components. GOST R ISO / IEC 15408-2-2013] Standartinform, 2014. 224 p. (In Rus-sian).
  16. Informatsionnaya tekhnologiya. Metody i sredstva obespecheniya bezopasnosti. Kriterii otsenki bezopasnosti informatsionnykh tekhnologiy. Chast' 3 – Komponenty doveriya k bezopasnosti [Information technology. Security methods and tools. Criteria for assessing the security of information technology. Part 3 – Security Trust Components. GOST R ISO / IEC 15408-3-2013] Standartinform, 2014. 214 p. (In Russian).

Supplementary files

Supplementary Files Action
1.
Fig. 1. Sharing the resources of the automated system in the time interval t with the classical approach

Download (41KB) Indexing metadata
2.
Fig. 2. Sharing the resources of the automated system in the time interval t when using GPU resources in the interests of ZI

Download (40KB) Indexing metadata
3.
Fig. 3. Block diagram of the greedy algorithm

Download (96KB) Indexing metadata
4.
Fig. 4. One-way branching strategy

Download (74KB) Indexing metadata
5.
Fig. 5. Frontal Branching Strategy

Download (86KB) Indexing metadata

Statistics

Views

Abstract - 26

PDF (Russian) - 12

Cited-By


Article Metrics

Metrics Loading ...

PlumX

Dimensions

Refbacks

  • There are currently no refbacks.

Copyright (c) 2020 Samara State Technical University

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies