Таныгин Максим Олегович, доктор технических наук, доцент, декан факультета фундаментальной и прикладной информатики
ул. 50 лет Октября, д. 94, г. Курск 305040
Maxim O. Tanygin, Dr. of Sci. (Engineering), Associate Professor, Dean of Fundamental and Applied Informatics Faculty
50 Let Oktyabrya str. 94, Kursk 305040
Чеснокова Алина Андреевна, ассистент кафедры информационной безопасности
ул. 50 лет Октября, д. 94, г. Курск 305040
Alina A. Chesnokova, Assistant of Information Security Department
50 Let Oktyabrya str. 94, Kursk 305040
Цель исследования. В задачах аутентификации групп сообщений, кодированных в режиме сцепления блоков, возникает необходимость формирования и обработки специфических древовидных структур. Содержимое таких структур, помимо информации о размещении данных во внутренней памяти вычислителей, описывает взаимное расположение сообщений в потоке данных между абонентами одноранговой сети. Данная информация необходима для выделения из всего потока сообщений в приёмник структурированного множества, для которого однозначно определён его источник. Использование подходов к сегментации древовидных структур позволяет распараллелить процессы добавления элементов в неё и поиска участков, соответствующих ошибке аутентификации.
Методы. В основе разбиения древовидной структуры на области, подлежащие модификации, и участки для анализа, лежит динамически формируемая из кодов аутентификации сообщений метрика – позиция конкретного сообщения в структурированном множестве сообщений, предаваемых от источника в приёмник. Значение данной метрики определяет расстояние от корня дерева, определяющее границу между двумя названными областями.
Результаты. За счёт изолирования модифицируемого и анализируемого участков древовидной структуры исключаются гонки процессов, реализующих независимые алгоритмы работы с ней. Показана возможность обнаружения ошибок аутентификации до получения последнего сообщения в структурированном множестве сообщений. В результате отпадает необходимость передачи тех сообщений группы, отправка которых предполагалась после момента обнаружения ошибки. Приведены формулы оценки среднего времени передачи множества сообщений при последовательной и параллельной реализации процедур формирования и обработки древовидной структуры, содержащей описатели поступающих в приёмник сообщений.
Заключение. В работе показано, что параллельная реализация алгоритмов добавления элементов в древовидную структуру и алгоритма поиска участков, соответствующих ошибке, позволяет уменьшить среднее время передачи группы сообщений на 5 -12% по сравнению с последовательной реализацией указанных алгоритмов. Это снижает нагрузку на канал связи для целевого класса систем, использующих для аутентификации кодирование в режиме сцепления блоков.
Purpose of reseach. In the tasks of authenticating groups of messages encoded in the mode of chaining blocks, there is a need for the formation and processing of specific tree-like structures. The contents of such structures, in addition to information about the placement of data in the internal memory of the calculators, describes the relative location of messages in the data stream between subscribers of a peer-to-peer network. This information is necessary to isolate a structured set from the entire message stream to the receiver, for which its source is uniquely determined. Using approaches to segmentation of tree structures allows you to parallelize the processes of adding elements to it and searching for areas corresponding to an authentication error.
Methods. The division of the tree structure into areas subject to modification and areas for analysis is based on a metric dynamically formed from message authentication codes – the position of a specific message in a structured set of messages transmitted from the source to the receiver. The value of this metric determines the distance from the root of the tree, which defines the boundary between the two named areas
Results. By isolating the modified and analyzed sections of the tree structure, races of processes implementing independent algorithms for working with it are excluded. The possibility of detecting authentication errors before receiving the last message in a structured set of messages is shown. As a result, there is no need to transmit those group messages that were supposed to be sent after the error was detected. Formulas for estimating the average transmission time of multiple messages with sequential and parallel implementation of procedures for the formation and processing of a tree structure containing descriptors of incoming messages to the receiver are given.
Conclusion. The paper shows that the parallel implementation of algorithms for adding elements to the tree structure and the algorithm for searching for areas corresponding to an error reduces the average transmission time of a group of messages by 5-12% compared with the sequential implementation of these algorithms. This reduces the load on the communication channel for the target class of systems using block coupling encoding for authentication.
The authors declare that there are no conflicts of interest present.