Схема реализации параллельных вычислений как инструмент защиты обрабатываемых данных

УДК 004.056.53:004.272

Р.Т. Файзуллин, Е.В. Щерба, Д.А. Волков

Схема реализации параллельных вычислений как инструмент защиты обрабатываемых данных

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

Проблема защиты распределенных вычислений. Консолидация обработки и хранения больших массивов информации в центрах обработки данных - одно из самых перспективных направлений совершенствования корпоративных систем. Применение и внедрение ЦОД позволяют наиболее эффективно использовать коллективные вычислительные ресурсы, уменьшают общее число оборудования, снижают расходы на их поддержку [1, 2].

Необходимым элементом ЦОД является гарантированная защита информации. Основными направлениями защиты информации являются: защита от вирусных атак, обеспечение безопасности процесса взаимодействия информационных систем ЦОД с внешними источниками информации и, что наиболее важно, защита информации от несанкционированного доступа. Несмотря на все усилия у пользователей имеется определенная и обоснованная степень недоверия к уровню защиты ЦОД и к облачным вычислениям, основанная на угрозе атаки сговором (collusion attack). Даже наличие криптографических средств защиты информации и требуемых лицензий у поставщика облачных услуг не является для потенциальных потребителей достаточной гарантией защищенности процессов хранения и обработки информации.

Указанная практическая задача реализации защищенных распределенных вычислений (secure multi party computation, MPC) может быть решена с помощью различных схем разделения секрета (СРС). Традиционно в данных схемах присутствует постановщик задачи (клиент, input party, IP), распределяющий данные по вычислительным кластерам (computation parties, CP), и получатель результата (result party, RP) - зачастую клиент (IP). Классические СРС имеют ряд недостатков (высокие накладные расходы на коммуникации, отсутствие гарантии защищенности). Представляется возможным предложить такие СРС, в которых малая, но определяющая информативность часть секрета хранится или обрабатывается у клиента [3-5]. Данный подход позволяет добиться того, что в ЦОД хранятся данные, но не сама информация, и в каждом случае можно привести прозрачное для клиента доказательство того, что по большему массиву данных нельзя в принципе восстановить значимую информацию.

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

Предлагаемые схемы параллелизации. Рассмотрим задачу решения большой системы линейных алгебраических уравнений GX = F, где квадратная матрица G не вырождена. Предположим, что некий достаточно большой главный минор A матрицы G также не вырожден. Тогда можно записать:

и привести систему к виду

Б - СА-1В

Р2 - СА-1^

Если размерность матрицы Б намного меньше, чем размерность А , клиент может получать значения Х2 на своей вычислительной системе, а наиболее трудоемкие операции по вычислению

А-1, СА-1В передавать на общедоступные вычислительные ресурсы.

Обратим внимание, что это далеко не искусственная задача. Например, расчет сложных гидравлических систем сводится к решению систем нелинейных алгебраических уравнений, которые описывают два закона Кирхгофа применительно к графу системы: закон сохранения массы в узлах и закон сохранения энергии вдоль цикла. Размерность Б в этом случае равна числу линейно независимых циклов в графе, что намного меньше числа узлов [6]. Расчет А-1, А 1В, А %1 можно произвести только один раз, если граф не изменяется во время эксплуатации системы, так как нелинейность системы определяется матрицами С и Б и правой частью . В случае массовых расчетов распараллеливание происходит по вариантам, определяемым различными С, Б, ^2 , т.е. заданием регуляторов расхода и давления и напорами.

Другая массовая задача - вычисление обратной матрицы - может быть решена с помощью формулы Фробениуса [7]:

^А-1 + А-1ВН-1СА-1 - АВН

-Н-1СА-1 Н

где Н = Б - СА-1В и А-1 существует.

Можно предложить много схем жесткого распараллеливания, но представляется возможным ввести простые правила:

Обратим внимание, что в этом случае мы получаем выигрыш в вычислениях в отличие от предыдущего случая, так как число операций для вычисления обратной матрицы 0{Ы4), и, начиная с некоторого Ь , сравнимого с N, получается, что 0((Ы - Ь)4) + 0((N - Ь)3) < 0(N4).

Исходная область

Разделение области

Рис. 1. Распределение вычислений

Расчёт на СР2

Если обратиться к итерационным методам и системам уравнений, ассоциированным с эллиптическими задачами, полученными с помощью метода конечных разностей или методом конечных элементов, то решение задачи разделения секрета можно получить с помощью альтернирующего метода Шварца. В этом случае на вычислительной системе клиента (1Р) будут осуществляться операции, ассоциированные с границами подобластей (рис. 1). Основные вычислительные операции, например вычисления в областях сгущения расчетных точек, возлагаются на арендуемые кластеры (СР), а обмен осуществляется пересылкой граничных данных [8].

Общая организация схемы вычислений представлена на рис. 2. Обратим внимание на то, что в качестве управляющего сервера может и должен выступать компьютер клиента (ТР/ЯР).

^Декомпозиция^

^Распределение^

Отклонения

Перехлёсты

Вычисления

Передача

Передача

Передача <М/

^Вычисления^

Критерий

завершения

Рис. 2. UML-диаграмма управления вычислениями

Каким образом разделять области по вычислительным устройствам? На рис. 3 приведена постановка модельной задачи обтекания профиля с заданной линией разрыва потенциала.

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

Реализация предложенной схемы возможна на базе вычислительной Грид-системы. Указанная Грид-система должна включать удаленные арендуемые кластеры (CP), сеть хранения данных SAN (Fibre Channel / 10 Gb Ethernet), сервер доступа и управления Грид-системой (IP/RP), а также вспомогательный локальный кластер для завершающих вычислений. Основную роль в такой системе играет сервер доступа и управления Грид-системой, отвечающий за постановку, декомпозицию,

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

Рис. 3. Постановка задачи обтекания профиля в трубе

Рис. 4. Разделение областей ответственности между ІР/ИР (1, 2) и СР (3-7)

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

Рис. 5. Решение задачи Дирихле для уравнения Лапласа на расчетной сетке размера

Оценка трудоёмкости восстановления секрета. Естественным образом возникает вопрос о том, насколько надежно защищает предложенный способ разделения секрета от восстановления

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

Указанный тезис можно пояснить на простейшем примере. Рассмотрим две односвязные области: О,ЕсП и задачу Дирихле для уравнения Лапласа:

Дм (х, у) = 0, (х, у) еП — Е , и| 5П = ф(х, у), и\\дЕ = у(х, у).

Решение этой задачи существует и единственно при достаточно слабых условиях на границы и рассматриваемые классы граничных функций. Предположим, что задача решается численно с помощью альтернирующего метода Шварца, где итерации последовательно проводятся на двух подобластях 0Р 02, ©1 и© 2 = П — Е , представляющих собой вложенные кольца. Кольцо 01 примыкает к Е и контролируется вычислительным устройством А, а остальная часть П контролируется вычислительным устройством В. Возникает вопрос, можно ли обладая информацией о решении в области П - (01 и Е) , получить информацию о границе Е и значениях функции или ее производных на

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

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

Рассмотрим задачу Коши для уравнения Лапласа:

Ди(х,у) = 0, (х,у)еП —Е ,

где П - односвязная область, Е строго включена в П и ее граница не пересекается с границей П . Заданы

и|дП = Ф(х,У), ип |дП = У(У).

Задача заключается в нахождении неизвестных функций ^С?) и области Е :

МдЕ =С (5), ЕсП.

Если выполнятся условия Неймана | ип = 0 , то область Е может быть пустым множеством, точдП

нее, если сужение решения задачи Неймана на границу равно заданному значению: у|дП = ип |дП = Ф .

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

Как поступать в более сложном случае, когда согласования между граничными условиями нет? Рассмотрим логарифмический потенциал по неизвестной площади и два нелинейных уравнения, выполняющихся на границе П , обозначим их А :

стЯ1п

ж =ф( х, у), ст^П Ц 1п

^/cX—хЯо2+(у—уЯ)2) дп е 1ч-\\/(х—~у^У2

ж = V х, у),

где ст - это неизвестная константа. Второе уравнение при выборе конкретного ст хорошо известно, это обратная задача гравиметрии определения формы области. Предположим, что решение второго уравнения единственно. Тогда, подставляя решение в первое уравнение, мы в общем случае не получим равенство. Надо будет подобрать такое ст и соответствующее ему решение, например, методом деления пополам, так, что оба уравнения обратятся в тождество. Таким образом, мы можем найти область и функцию идЕ =С(5). Но обратим внимание на то, что, рассматривая разложения: Ф = Ф1 + ф2, V = У1 +У2, где слагаемые с индексом 1 отвечают согласованным краевым условиям задачи Неймана, мы можем получить решение в виде и = щ + и2, где индекс 1 отвечает решению ранее

рассмотренной задачи Неймана, а индекс 2 отвечает решению задачи с помощью логарифмического потенциала. Рассматривая в качестве Н любую область Ні, такую, что асаі сП, мы получим функцию, удовлетворяющую уравнению Лапласа в П-Н и заданным краевым условиям, что доказывает неединственность решения задачи.

Рассмотрим задачу продолжения функции, заданной на некоторой области K, гомеоморфной кольцу, через внутреннюю границу в область П, считая, что Ди(х,у) = 0, (х,у)єК, П-Н, где П -односвязная область, Н включена в П, и ее граница не пересекается с границей П . Значения функции в кольце известны: и(x,у),(x,у) є K.

Задача заключается в нахождении неизвестной области Н и неизвестной нормальной производной на границе этой области:

границы е , удовлетворяющую условию Неймана на границе Vn ад = g (x, у) .

Для любых двух замкнутых кривых в K, окаймляющих О, можно составить два интегральных уравнения первого рода, связывающих известные значения u(x,у), (x,у)е K и значения, индуцированные логарифмическим потенциалом простого слоя. Предположим, что решение этих уравнений существует и единственно вне зависимости от выбора кривых. Рассмотрим область Е1,ЕсЕ1 с О. Функция V задает нормальную производную Vn |дн1 , с помощью которой можно также построить

гармоническую функцию W вне и внутри Е1. В самом деле, из-за отсутствия источников | Vndl = 0 и в качестве плотности можно взять Vn |дд1. Внутри кольца Е1 — Е и вне его функция

W совпадает с индуцированной ранее, так как их разность является гармонической функцией с нулевыми условиями Дирихле и Неймана на границе Е1. В итоге мы получим неединственность Е при принятом допущении, что решение системы интегральных уравнений единственно задает Е . Предположим, что на границе Е задано условие непротекания un |дЕ = 0,ЕсО . В этом случае

построение потенциала V с помощью логарифмического потенциала простого слоя, как в предыдущем случае, невозможно. Как поступить в этом случае? Рассмотрим u решение смешанной задачи Неймана в кольце О — Е

и покажем, что выбор е не единствен. Функции u можно поставить в соответствие сопряженную гармоническую функцию v так, что f = u + ^ будет голоморфной. Если мы отступим от ЭЕ и выберем некоторую точку (xo,уо), лежащую во внутренности О — Е, то через нее проходит Г , линия уровня V , на которой также будет выполняться условие непротекания. Область, ограниченную Г , можно рассматривать как Е1, и и будет гармонической функцией в О — Е1.

Таким образом, практическая задача сводится только к методу подбора, который можно организовать, обладая некоторой априорной информацией и выбирая вид ЭЕ так, чтобы на внешней границе О происходила наиболее гладкая склейка с известным вне О решением и его производными. Оценим трудоемкость такого подхода. Если, например, сетка в подобласти Ю 2 представляет собой образ прямоугольной сетки размера К • N, где К - число шагов сетки по нормали от Е , а N - число шагов сетки по поверхности, то число выборов «гладкой функции», описывающей ЭЕ, будет равно К • 2 . Отсюда следует, что уже при N«80 возникает комбинаторный взрыв и решение

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

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

йъ задает гармоническую функцию вне

Ди(х,у) = 0, (х,у)єП-н , и |зп = ф(х,у), ип |5н = 0

Заключение. Предложенные схемы организации защищенных параллельных вычислений (MPC), а также введенные простые правила позволяют решить вопрос о правомерности передачи массовых вычислений во внешние ЦОДы и об использовании неконтролируемых вычислительных ресурсов. Показано, что задача восстановления информации в этом случае сводится к задаче аналитического продолжения с неединственным решением. Реализация разработанных схем возможна на базе типовой Грид-системы и специализированного программного обеспечения.

Литература

Файзуллин Рашит Тагирович

Д-р техн. наук, профессор, зав. каф. комплексной защиты информации Омского государственного технического университета (ОмГТУ)

Тел.: 8 (381-2) 21-77-02 Эл. почта: r.t.faizullin@mail.ru

Щерба Евгений Викторович

Канд. техн. наук, доцент каф. комплексной защиты информации ОмГТУ

Тел.: 8 (381-2) 21-77-02

Эл. почта: evscherba@gmail.com

Волков Данил Андреевич

Студент Омского государственного университета им. Ф.М. Достоевского Эл. почта: volkovdanil91@gmail.com

Faizullin R.T., Shcherba E.V., Volkov D.A.

A scheme for the implementation of parallel computing as a protection mechanism of processed data

In this paper we propose a scheme of separation of computing and storage in data centers. The scheme guarantees the impossibility of restoring the matrix system of linear equations on individual compute nodes. The applicability of this approach in the case of numerical solution of some boundary value problems for equations of mathematical physics has been proved.