Содержание к диссертации
Введение
ГЛАВА 1. Среда пользователя 68
1.1.Интересы потребителя 69
1.1.1.Локальные сервисы, обслуживающие запросы пользователя 69
1.1.2. Хранениеи доступ к персональным данным 69
1.1.3.Доступ к сетевым информационным источникам 69
1.1.4.Персонализованный обмен информацией с абонентами 69
1.1.5.Обслуживание, независимое от физического нахождения потребителя 70
1.2.Мобильность сервиса как подход 70
1.2.1.Мобильность пользователя 70
1.2.2.Мобильность вычислительных ресурсов 71
1.2.3.Мобильность данных 71
1.2.4.Независимость сетевого доступа от внешних параметров 71
1.2.5.История развития компьютерных сервисов 72
1.2.5.1.Эволюция компьютерных сервисов 72
1.2.5.2.Потребитель в современной автоматизированной среде 73
1.2.5.3.Вычислительная среда потребителя 73
1.3.Требования к идеальной среде пользователя 74
1.3.1.Состав среды 75
1.3.1.1.Вычислительные ресурсы 75
1.3.1.2.Доступ к данным 78
1.3.2.Расширяемая среда 82
1.4.Мобилыюсть и виртуализация сервисов 83
1.4.1.Мобильность сервиса 83
1.4.2.Виртуализация 84
1.4.2.1.Виртуализация сервиса 84
1.4.2.2.Виртуализация хранилища 84
ГЛАВА 2. Саморегулируемая виртуальная вычислительная среда 85
2.1.Общие принципы представления данных в децентрализованном хранилище 87
2.2. Алгоритм распределенного хранения данных с регулируемой степенью избыточности - (n,k) схема представления данных 90
2.2.1.Предложенная модель распределенного представления данных 90
2.2.2.Решения задач по организации алгоритмов сборки-разборки 93
2.2.2.1.Алгоритмы над полем P=GF(N) и их производительность 94
2.2.2.2.Алгоритмы сборки/разборки файлов 98
2.3.Метод организации виртуального отказоустойчивого хранилища на базе (n,k)
схемы представления данных 100
2.3.1.Объединение серверов в группы 101
2.3.2.Подключение клиентов 106
2.3.3.Классы хранимых файлов 108
2.4.Регулируемая отказоустойчивость ПО
2.5.Оптимальность доставки данных 111
2.6.Предложенная технология реализации отказоустойчивого хранилища 113
2.6.1.Топология и техническая организация взаимодействия серверов 114
2.6.2.Клиентский сервер 117
2.6.3.Транзакционная модель изменений и хранение данных 120
2.6.4.Использование индексного дерева 124
2.6.5.Генерация уникальных идентификаторов 124
2.6.6.Директорный сервис 124
2.6.7.Файловый сервер 127
2.6.8.Топологический сервер 132
2.6.9.Сервер кэширования 137
2.6.10.3адача выбора оптимального соединения 138
2.6.10.1.Локальность задачи 138
2.6.10.2.Сущность алгоритма 138
2.6.10.3.ОЦЄНКИ 141
2.6.11.Алгоритм упорядочения идентификаторов относительно выделенного 142
2.6.12.Алгоритм кэширования данных 144
2.6.12.1.Предпосылки выбора модели 144
2.6.12.2.0писаниемодели кэширования 145
2.6.12.3.0ценка производительности 149
2.7.Модель безопасности децентрализованной системы хранения данных, базирующаяся на декларируемых полномочиях 150
2.8.Соответствие предложенного метода набору требований к хранилищу 150
2.8.1.Вычислительные ресурсы 150
2.8.1.1.Изоляция 151
2.8.1.2.Утилизация 151
2.8.1.3.Безопасность 152
2.8.1.4.Управляемость 152
2.8.2.Доступ к данным 153
2.8.2.1.Легкость выделения 153
2.8.2.2.Изоляция 154
2.8.2.3.Разделение 154
2.8.2.4.Прозрачность 155
2.8.2.5.Коммуникабельность 155
2.8.2.6.Пригодность для поиска 155
2.8.2.7.Легкость наращивания 155
2.8.2.8.Надежность и доступность 156
2.8.3.Расширяемая среда 156
2.9.Математическая модель поиска данных 156
2.9.1.Описание метода доставки 156
2.9.1.1.Предпосылки 156
2.9.1.2.Схема метода 157
2.9.2.Прогнозирование времени поиска 158
2.9.2.1.Модель для расчетов 158
2.9.2.2.0ценка времени поиска 159
2.9.2.3.Особенности практического использования выведенного 164
2.9.2.4.Пример использования 165
2.10.Анализ производительности распределенной системы 172
2.10.1.Оценка накладных расходов операций чтения и записи в системе 174
2.11.Алгоритм оптимизированного размещения данных в группах серверов 179
2.11.1.Сервер поддержки уровня избыточности 181
2.12.Выбор алгоритмов работы хранилища в разных условиях 182
2.12.1.Реализация хранилища в виде локального связанного кластера 182
2.12.2.Реализация хранилища в виде глобального кластера 183
ГЛАВА З. Система безопасности децентрализованного хранилища 185
3.1.Принципиальная децентрализованность системы 186
3.2. Декларируемые полномочия 187
З.З.Перенос защиты с серверов на клиенты 188
3.4.0тсутствие необходимости сертификации серверов и инфраструктуры системы 188
3.5.Базовые понятия математической модели средств разграничения доступа хранилища 189
3.5.1.Определения и аксиомы 189
3.5.2.«Правила вывода» 191
3.6.Математические модели контроля доступа для распределенной децентрализованной файловой системы TorFS 193
3.6.1.Используемые обозначения 193
3.6.2.Аутентификация пользователей системы 194
З.б.З.Математическая модель контроля доступа, названная «анонимной» 194
3.6.3.1.Файл 195
3.6.3.2.Структура директории 197
З.б.З.З.Структура ACL 198
3.6. ЗАКорневая директория 200
3.6.3.5.Примеры основных операций в системе 200
3.6.4.Математическая модель контроля доступа с протоколированием 208
3.6.5.Математическая модель контроля доступа, включающая «владельца» 210
ГЛАВА 4. Математические модели вычислительных ресурсов 212
4.1.Математическая модель вычислительных ресурсов компьютера и способа их
потребления 213
4.1.1.Компьютер и ресурсы операционной системы 213
4.1.2.Формализации модели 215
4.1.3. Сетевые вычислительные модели для нелинейных систем уравнений гиперболического типа 226
4.1.4.0собснности топологии графов в моделировании реальной вычислительной
системы 231
4.1.5.Пример расчета для связанных параметров 233
4.1.5.1.Модель 233
4.1.5.2.Вычислительный алгоритм 235
4.1.5.3.Аппроксимация 236
4.1.5.4.Устойчивость 237
4.1.5.5.Усиление устойчивости 238
4.1.5.6.Сходимость 238
4.1.5.7.Моделирование нагрузки на http-сервер 239
4.1.5.8.Модслирование нагрузки на ftp-сервер 241
4.1.6.Выводыпо разделу 243
4.2.0бобщенная математическая модель наложенного управления ресурсами
операционных систем 244
4.2.1 .Математическая модель наложенного управления 245
4.2.2.Классификация типов ресурсов 252
4.2.2.1.Возобновляемые ресурсы 253
4.2.2.2.Невозобновляемые и частично возобновляемые ресурсы 257
4.2.3.Выводы по разделу 259
4.3.Модель и метод наложенного управления ресурсами CPU 261
Заключение 275
Список использованных источников
- Хранениеи доступ к персональным данным
- Алгоритм распределенного хранения данных с регулируемой степенью избыточности - (n,k) схема представления данных
- Декларируемые полномочия
- Сетевые вычислительные модели для нелинейных систем уравнений гиперболического типа
Введение к работе
В. 1. Актуальность темы
Темп развития современной вычислительной техники и коммуникационных сред имеет практически экспоненциальный характер по большинству параметров (например, более 20 лет каждые 18 месяцев происходит удвоение мощности процессоров - закон Мура). Ситуация с использованием компьютеров достаточно сложна - общепризнано, что рост потребностей превышает предоставляемые средой возможности. Существенным аспектом ограничения темпа развития стала безопасность систем PI сложность управления компьютерной инфраструктурой.
Существенные изменения происходят и в алгоритмах, используемых современными операционными системами (ОС), которые являются основой для успешного использования компьютеров потребителем. Невозможно говорить о качестве обслуживания пользователя локальной или распределенной вычислительной системы, не рассматривая процессы, происходящие внутри ОС, особенно процессы выделения ресурсов. Включение в состав всех современных ОС средств виртуализации потребовало появления новых понятий и новых моделей процессов, происходящих в системах, как ключа к эффективному использованию возможностей и технологий.
Следующим шагом в эволюции технологии организации компьютеров становится их объединение в сеть. В последние годы резко возрос интерес к решению проблемы организации современных распределенных сред, призванных хоть как то решить проблемы потребителей, возникающие при использовании современной компьютерной инфраструктуры. Разрастание коммуникационной инфраструктуры, появление и активное использование одноранговых сетей доставки файлов и живого обмена аудио- и видеоданными (технологии Skype, BitTorrent, Kazaa и др), факты злоупотребления компьютерными технологиями, происходящий сдвиг в принципах использования современных компьютеров - все это заставило задуматься о сути происходящих процессов и попытаться переосмыслить применяемые в разработке компьютерных систем и программ подходы, перейдя от автономного компьютера к их объединению в виде единой распределенной среды виртуализованных вычислительных ресурсов.
Такие интенсивно развивающиеся в последние годы направления исследований, как GRID, Internet2, Web 2.0/3.0, реализация поддержки во всех современных ОС технологий аппаратной виртуализации компаний Intel и AMD подтверждают актуальность темы диссертационного исследования в области математического моделирования средств управления ресурсами и данными в распределенных и виртуализованных средах.
8.2. Цель работы и объект исследования
Цель диссертационной работы — разработка нового подхода к созданию распределенных и виртуализованных сред, ориентированных на размещение, хранение и управление ресурсами и данными, построение и анализ математических моделей, описывающих компоненты такой среды, в том числе математических моделей интегрированных средств контроля доступа для таких сред.
Задачи исследования:
- Анализ набора требований к распределенной и виртуализованной среде и их классификация;
- Разработка метода реализации и алгоритмов функционирования подсистем среды, удовлетворяющих большинству сформулированных требований;
- Разработка математических моделей, необходимых для описания поведения компонентов среды и обоснования выбора параметров и алгоритмов;
- Разработка интегрированной системы контроля доступа распределенной среды, создание ее математической модели и доказательство корректности функционирования системы в рамках сформулированных ограничений.
Объект исследования - методы и алгоритмы управления распределением ресурсов, методы и алгоритмы организации и работы распределенных систем, децентрализованные интегрированные системы контроля доступа, математические модели потребления вычислительных ресурсов, технологии виртуализации и их моделирование.
8.3. Методы исследования
В ходе научных исследований по разработке математических моделей и алгоритмов управления ресурсами и данными в распределенных и виртуализованных средах использовались методы дискретной математики и алгебры, вычислительной математики, методы математической статистики, методы теории операционных систем и системного программирования.
В А. Научная новизна
В работе впервые предложены: • Модель виртуализации объектов уровня операционной системы путем разделения их в пространстве имен; • Обобщенная математическая модель и алгоритмы группового многоуровневого управления ресурсами, необходимые для виртуализации уровня ОС и других технологий виртуализации;
• Математическая модель вычислительных ресурсов компьютера и способа их потребления, использующая алгебраические и дифференциальные уравнения в частных производных гиперболического типа;
• Технология и алгоритмы организации, а также классификация требований к новому поколению распределенных сред управления данными;
• Метод использования для построения такой среды (п,к)-схемы разделения данных и его эффективная реализация в конечных полях Галуа;
• Принципы создания и алгоритмы функционирования распределенных виртуализованных сред на несимметричных серверах и каналах связи с открытой коммуникационной инфраструктурой, ориентированных на размещение, хранение и управление ресурсами и данными;
• Математические модели децентрализованных систем контроля доступа.
В.5. Теоретическая и практическая значимость
Разработанная система хранения и управления данными может быть использована как часть программного обеспечения (ПО) центров данных предприятий и организации услуг по размещению сервисов в глобальной сети (сервисов хостинга), а также для создания децентрализованной высокомасштабируемой системы хранения данных с количеством узлов, сопоставимым с общим количеством компьютеров в мировой сети Интернет. Предложенные алгоритмы реализации (п,к)-схемы могут быть использованы как усовершенствованный вариант RAID-технологий как для локального, так и для распределенного хранения и восстановления данных. Разработанные математические модели и алгоритмы могут быть использованы в качестве самостоятельных решений задач планирования и распределения ресурсов в современных ОС и распределенных системах, включая поддержку средств виртуализации. Предложенные математические модели контроля доступа могут применяться в распределенных системах с открытой коммуникационной инфраструктурой в условиях отсутствия доверенного центра, который разрешал или запрещал бы доступ к данным.
Результаты работы внедрены в крупных компаниях - производителях ПО (SWsoft/Parallels, Acronis - в этих компаниях совокупно работает более 1000 инженеров). На основании разработок диссертанта создана новая отрасль индустрии ПО «виртуализация ОС». ПО, включающее в себя алгоритмы, разработанные диссертантом, установлено у более чем 700,000 потребителей в 125 странах на 17000 серверах (технология Virtuozzo®).
По результатам работы получено 14 патентов США и подано более 80 заявок на патенты США. Эти патенты являются международными объектами интеллектуальной собственности в странах, входящих в World Patent Organization, в том числе в России. Результаты работы могут быть использованы в учебном процессе при подготовке специалистов в области ОС, виртуализации и распределенных сред.
В.6. Публикации и апробация результатов работы
По теме диссертации опубликовано 54 работы, из них 11 статей [1-11] - в ведущих рецензируемых научных журналах и изданиях, рекомендованных ВАК РФ для публикации материалов докторских диссертаций, 7 публикаций в сборниках трудов международных конгрессов, симпозиумов, конференций [21; 25; 26; 30; 33; 36; 41].
В работах с соавторами лично соискателем выполнено следующее:
[1; 18; 19; 22] - мат. модель производительности файловой системы; [3; 31] - принцип построения децентрализованной системы безопасности без центра авторизации, требования к ней, мат. модель, доказательства безопасности; [4; 12; 23; 30; 50] - принцип использования (п,к)-технологии и алгоритмы хранения данных для обеспечения отказоустойчивости распределенной системы и способы реализации; [5; 11; 24; 29] -адаптация вычислительных схем разного типа для численного решения многомерных гиперболических уравнений для сложных моделей сред и сложной геометрии расчетной области; [14; 17] - имитационная модель пересылки информации на графе и ее применение для оценки времени поиска; [15; 16; 20] - математическая модель и алгоритм наложенного группового управления ресурсами; [35; 39; 40; 42; 49; 52; 54] - типы и модели виртуализации, области се применения, методы создания виртуальных сред; [43; 44; 45] -методика построения оптимальных высокоскоростных сетевых соединений; [46; 48] -метод и технология организации распределенных хранилищ; [47; 53] - технология онлайн миграции данных и процессов в виртуализованных средах; [51] - технология наложенного управления ресурсами ОС.
Результаты работ по диссертации докладывались и обсуждались на многочисленных научно-исследовательских семинарах и конференциях, основные из них: «Ottawa Linux Symposium» (Оттава, Канада, 2000); VE on PC 2001 virtual Environment on a PC Cluster Workshop 2001 Protvino (Протвино, Россия, 2001); научный семинар кафедры вычислительной математики МФТИ (Москва, 1989-1999); научный семинар кафедры информационных технологий Лундского университета, (Лунд, Швеция 2002); научный семинар по теории кодирования ИППИ РАН (Москва, 2002); научный семинар Института Системного Программирования РАН (Москва, 2005); научный семинар Вычислительного Центра РАН под руководством акад. А.А. Петрова (Москва, 2008); Перспективы систем информатики - Шестая международная конференция памяти академика А.П. Ершова (Новосибирск, 2006), Международная конференция "Математика, компьютер, образование" (Москва, 2001); Международная научно-практическая конференция по программированию компании Microsoft (Москва, 2003); XL - XLIX ежегодные научные конференции Московского физико-технического института (Москва-Долгопрудный, 1997-2007гг) и др.
Хранениеи доступ к персональным данным
Следующим классом сервисов являются сервисы персонализированного обмена информацией, которые, обычно, требуют доступа к сети (при желании их можно рассматривать как частный случай предыдущего пункта, но, поскольку для отправки письма доступа к собственно Интернет - источникам информации по сути своей не надо, то имеет смысл выделить эту важный тип сервисов отдельно).
Одним из самых существенных требований, выдвигаемых пользователем ко всем таким сервисам, является возможность их мобильного использования, то есть, использования в любой момент времени, находясь на любом расстоянии от дома или рабочего места с оборудованным стационарным компьютером и сетью. Важность такой мобильности подтверждает несколько примеров — несмотря на существенно большую стоимость ноутбуков (обычно в 2-3 раза по сравнению с аналогичными стационарными компьютерами), они получают сейчас большее распространение чем стационарные компьютеры типа рабочих станций, и предсказывается почти полное вытеснение вторых первыми. Аналогичная ситуация и с мобильной связью - самым последним примером успеха в области комбинирования мобильной связи, Интернета и вычислительных систем общего назначения является взрывообразный рост числа пользователей таких систем просмотра почты на мобильном телефоне как Blueberry/Blackberry (компания RIM) -количество подписчиков сервиса этой компании достигло 3 миллионов за короткое время.
Одним из способов решения проблем современного состояния компьютерного окружения потребителя может являться реализация понятия мобильности в виде мобильной компьютерной среды, дающей возможность пользователю быть мобильным, обеспечивающим мобильность вычислительных ресурсов и данных. Рассмотрим немного более подробно эти понятия.
Обычно означает, что пользователь постоянно перемешается - как географически (например, с работы в дом и обратно, в командировки, да и в конце концов внутри одного здания или комнаты), и оказываемый ему сервис не должен зависеть от доступности пользователя около компьютера (например, вам не нужно находиться около телевизора соединенного с устройством типа TiVo для того чтоб он записал передачи по вашим предпочтениям), так и от наличия у пользователя специфических устройств (например, выходя ненадолго в другую комнату пользователь обычно не берет с собой ноутбука, хотя может носить постоянно что то типа WiFi смартфона или сотового телефона). Система должна учитывать технические возможности среды по коммуникации с пользователем и оказывать соответствующий сервис с учетом таких возможностей (так, скажем, для пользователя сотового телефона наверное бесполезно будет создание сервиса, который общается с пользователем путем выдачи гигантских графических изображений со многими деталями, которые просто не видны на экране сотового телефона).
Вычислительные ресурсы должны «следовать» за пользователем и иметь возможность перемещаться от одного физического носителя к другому. Постоянное изменение физической конфигурации доступных устройств должна находить свое отражение в среде, например, если у пользователя есть календарь с напоминанием о событиях, то сервис, обеспечивающий такое напоминание, должен иметь возможность «переезжать» с одного устройства на другое, причем они могут быть самой разной сложности - от ноутбука до мобильного телефона. Причем переезд не должен требовать от пользователя каких либо действий, включая «разрешительно-конфигурационные».
Данные, так же как и вычислительные ресурсы должны «следовать» за пользователем и иметь возможность перемещаться от одного физического носителя к другому. Альтернативой «переезда данных» может служить удаленный доступ к ним через линии связи, но, тогда существенно усложняется ситуация в случае с неустойчивым соединением с внешним миром, когда доступность данных перестает быть «локальной» и понятной для пользователя и начинает зависеть от каких либо событий которые с точки зрения потребителя немногим отличаются от фаз Луны.
Особо хотелось бы отметить, что идеально если доступ к сети и сетевым источникам не зависит от состояния внешней среды, или, по крайней мере, зависит минимальным образом. Это казалось бы, внутренне противоречивое утверждение (так как источник данных обычно сервер, расположенный гдето далеко, и доступ к нему идет по сети, которая вдруг может оказаться плохо работающей), но на самом деле именно этого хочет пользователь (кому неизвестны, скажем, плохой прием сотового телефона или нестабильно работающее соединение с Интернет?), и необходимо искать возможности решения такой задачи.
Для лучшего понимания потребностей пользователей рассмотрим эволюцию компьютерных систем с точки зрения потребителя - как набора сервисов, которые он может получить при использовании компьютерной технологии, для оценки того в каком направлении движется эта эволюция сейчас.
Алгоритм распределенного хранения данных с регулируемой степенью избыточности - (n,k) схема представления данных
Рассмотрим необходимые для дальнейшего изложения особенности предложенной схемы хранения данных.
Как уже отмечалось, каждый файл предлагается хранить в виде некоторого набора частей (кусков), количество которых может меняться во времени, однако всегда в любой момент времени для существующих в системе частей выполняется условие, что из любых к частей можно полностью собрать файл. Это условие будем называть далее условием избыточности. Размер каждой части порядка 1/к от размера хранящегося файла (с точностью до округления). Количество частей файла - п, содержащихся в системе может меняться в зависимости от ее конфигурации, от количества компьютеров в ней, интенсивности работы с данным файлом и т.д. Причем, при изменении (увеличении) числа п уже существующие части никак не изменяются, то есть новые части строятся таким образом, чтобы по-прежнему выполнялось условие избыточности.
Число к будет фиксированным для каждого конкретного файла и будет зависеть от его размера. При использовании протокола TCP/IP [102], который де факто является основным в существующих сетях, скорость передачи данных максимальна, когда их размер соответствует размеру пакета протокола (message transfer unit), что составляет размер порядка 1Kb. Таким образом, каждой размер части должен быть 1Kb или чуть более (1.4Кб с учетом всех заголовков). То есть для файла размера S число к определяется по формуле k=S/Sp , где Sp - размер пакета протокола TCP/IP. По статистике, средний размер Internet ресурсов -5-7 Kb для обычных http запросов и 35 кб для файлов с изображениями. Ниже будет показано, что сложность алгоритма сборки файла пропорциональна к и размеру файла.
Для того, чтобы получить файл, пользователю необходимо получить любые к частей из существующих в данный момент в системе, из которых он сможет восстановить исходный файл. Размер каждой части будет 1/к от размера исходного файла, поэтому общий объем полученной информации будет равен объему файла, тем самым общая нагрузка на сеть не будет увеличена. Естественно, существует некоторое увеличение размера файла связанное с округлением размера последней части, а также со служебной информацией, которую надо хранить внутри частей (хотя ее размер, как будет показано далее, практически несущественен).
На рисунке 21 показано удовлетворение пользовательского запроса на чтение файла при к=3. Для удовлетворения запроса пользователь будет получать к "ближайших" с точки зрения загрузки в данный момент сети и пропускной способности каналов связи, что обеспечивает минимальное время удовлетворения запросов. Запросы на поиск кусков в системе служат для мониторинга интенсивности использования данного файла. Для этого каждый из серверов хранит историю запросов прошедших через него.
Такая модель позволяет динамически контролировать избыточность данных в системе и поддерживать ее для каждого файла на уровне, необходимом для равномерной загрузки сети и стабильного времени доступа к нему при заданной потребности пользователей. То есть при росте пользовательских запросов к данному файлу в некоторой области сети, модель представления данных позволяет системе создавать новые части данного файла, размещая их как раз на компьютерах, находящихся в той области сети, где спрос на файл возрос, тем самым разгружая ту часть сети, где спрос на файл невысок и увеличивая скорость доступа к файлу. Если потребность в некотором файле будет высока по всей сети, то части этого файла создадутся системой в достаточном количестве по всей сети, тем самым, распределяя нагрузку по всей сети. И наоборот, если спрос на файл будет уменьшаться, лишние (неиспользуемые) его части будут постепенно удаляться системой.
Алгоритмы определения оптимального расположения и количества кусков файлов, гарантирующих его доступность и максимальную скорость доступа при заданной конфигурации и производительности сети представляют собой отдельную достаточно сложную задачу. Далее будет рассмотрен для примера вариант организации поиска по графу с разбиением на пересекающиеся подгруппы, для которого будет проведена оценка времени поиска. Более подробно этот вопрос разобран в разделе, посвященному алгоритмам кэширования.
В дальнейшем делается предположение, что количество кусков в системе равно количеству потенциально доступных серверов. Тем не менее, могут существовать и другие распределения, например, можно разложить на один сервер к кусков, так, чтобы если он был доступен, то все необходимое для сборки (восстановления) файла можно было получить только с одного сервера, а на остальные к серверов мы раскладываем куски только для осуществления сборки в случае недоступности первого сервера (ассиметричная схема) - то есть для такой схемы будет задействовано (2 k + 1) серверов для хранения каждого файла. Также возможна балансировка по средней загруженности серверов (например, определить некое количество частей и их разложить в соответствие со средней загрузкой серверов - больше частей на серверы с меньшей средней загрузкой).
Можно также выдвинуть какие то априорные предположения о динамике изменения доступности серверов. Например, что если у нас в сети работает Р серверов содержащих по 1 куску файла, и в любой момент времени недоступными могут оказаться не более L процентов от их числа. Тогда для обеспечения доступа к файлу количество кусков на которые разбивается файл не может быть меньше чем k + [P L/100]. В этом случае в худшей ситуации при выключении или недоступности L процентов серверов, содержащих куски файла, мы, тем не менее, можем его восстановить из оставшихся к.
Отдельно требует рассмотрения вопрос поддержания необходимого уровня «доступности» путем контроля за количеством кусков каждого файла.
Алгоритмы разбиения файла на части, сборки файла и создания новых его частей используют теорию конечных полей Галуа и подробно описаны в следующем разделе.
Декларируемые полномочия
Автор предлагает, чтобы вся защита в системе осуществлялась на клиентских системах, которые априори считаются безопасными, тогда как серверные системы считались открытыми и небезопасными.
Почему автором сделан такой выбор?
Системе необходима «точка отсчета безопасности» (root of the trust), то есть некоторый набор безусловно «безопасных» аксиом и правил вывода, из применения которых можно сделать какие то выводы о безопасности «производной» системы в целом. Так как, априори, целью клиента является корректная работа в системе, а сервер выполняет обслуживающие функции и может быть «захвачен», то явилось бы достаточно очевидным строить систему из двух предположений - что только клиентская часть безопасна, и что любые действия легитимного пользователя по получению каких либо дополнительных «преимуществ» как на клиенте, так и на сервере не должны быть успешными.
Особенно следует отметить, что если сделать «клиентскую» часть системы маленькой и защищенной от несанкционированных изменений (например, прошив ее в ПЗУ и/или разместив ее в принципиально однозадачной системе где невозможны «резидентные» вирусы, или разместив ее в защищенной безопасной виртуальной машине), мы можем получить систему, которую невозможно сломать при существенно большем классе возможных атак.
Предположим, что система уже реализована и для нее используется набор серверного и коммуникационного оборудования (аппаратного и программного обеспечения), которое успешно функционирует и обеспечивает работу системы.
Через некоторое время возникает потребность обновить программное или аппаратное обеспечение серверов системы, их программ (как ОС самой так и непосредственно обслуживающих), а также оборудование и ПО средств коммуникаций (от пере прокладки линий и перехода от проводной связи к беспроводной и замены ПО коммутаторов).
Можно ли считать после такой замены систему по прежнему безопасной? Нужно ли сертифицировать проведенные изменения и ПО каким либо образом (как это обычно требуется для соответствующих уровней доступа по уже цитированным документам ГТК или МО США)?
Да, можно, так как при создании системы про работу серверов и средств коммуникаций не делается никаких предположений (кроме осуществления своих прямых функций), то есть смена одного оборудования и/или ПО никак не отражается на безопасности системы в целом.
Это очень существенное преимущество для систем с контролируемым и сертифицируемым доступом. Так, в реальности, цикл сертификации оборудования для обслуживания секретных линий связи иногда занимает времени больше, чем время жизни (3 года) собственно оборудования! Используя предложенный подход, можно существенно сократить это время и повысить уровень реальной безопасности.
Базовые свойства файловой системы TorFS, существенные для построения математических моделей контроля доступа, можно сформулировать в виде следующих определений и аксиом:
Аксиома 1. Компьютеры файловой системы TorFS могут взаимодействовать друг с другом через каналы связи.
Аксиома 2. В системе TorFS существует дерево директорий для преобразования текстового пути к файлу в числовой идентификатор файла (FID). Содержимое каждой директории хранится в виде файла.
Аксиома 3. Отказоустойчивость файловой системы TorFS обеспечивается за счет хранения частей файла на различных компьютерах системы. При записи файла в систему TorFS, он делится на части. Математически операцию разделения файла на части в системе TorFS можно описать следующим образом. Сначала файл F разбивается на последовательные блоки: F = (B1IB2I...IB1) (знак «I» здесь означает конкатенацию - запись одной последовательности символов в конец другой), а затем каждый из блоков при помощи некоторой функции 190 Decompose(n,k)(Bi) = {В;(1), В;(2),...В;(п)} осуществляется генерация п кусков так, что любых к из них достаточно, чтобы восстановить блок при помощи функции Compose(n,k) (Вр1\ В&\.. .В;№) = ВІ
Части (блоков) файла {В;(1), В;( \...ВІ(П)] хранятся на различных компьютерах системы. Данные компьютеры, во-первых, могут оказаться незащищенными и быть атакованы злоумышленниками, а во-вторых, администраторы этих компьютеров потенциально могут изменить полномочия доступа к хранящимся на компьютере объектам. Возникает задача обеспечения контроля доступа к файлам, хранимым в системе, которая может решаться при помощи криптографических средств.
Определение 1. Пользователь распределенной файловой системы TorFS - сущность, обладающая некоторым идентификатором U. и двумя парами открытый ключ/секретный ключ - для шифрования/расшифрования информации и проверки/генерации электронной цифровой подписи (ЭЦП).
Определение 2. Пусть U. - некоторый пользователь распределенной файловой системы TorFS. ПЭВМ с присутствующей на ней операционной системой называется компьютером пользователя U. , если одновременно выполняются следующие условия:
1. U. соответствует некоторый пользователь OS_user операционной системы;
2. Субъекты, порождаемые от имени OS_user, могут совершать криптографические преобразования информации с использованием секретных ключей пользователя U.; і
3. Невозможен доступ к объектам пользователя OS_user, не санкционированный им самим. Аксиома 4. Для каждого пользователя U. распределенной файловой системы TorFS существует его «компьютер пользователя».
Таким образом автор постулирует существование защищенной ПЭВМ для каждого пользователя системы. Обеспечить защиту ПЭВМ можно, например, воспользовавшись методом создания изолированной программной среды [123]. На этой ПЭВМ пользователь может хранить свои файлы и выполнять над ними криптографические преобразования. Автор использует категории субъектно-объектной модели компьютерной системы, часто применяемой при рассмотрении вопросов компьютерной безопасности. Более подробно см., например, [123].
Сетевые вычислительные модели для нелинейных систем уравнений гиперболического типа
Для другого класса возобновляемых ресурсов, например, для сетевой полосы пропускания, формулировка модели и модельных параметров может выглядеть так же, за исключением того факта что даже если «поток исполнения» не нуждается в этом ресурсе то он тем не менее может продвигаться вдоль оси х. Кроме того, должно быть введена кросс-зависимость Ртах от разности между желаемой полосой пропускания и полученной полосой, так как пропорционально недополученной полосы пропускания мы должны увеличить время, за которое достигается какой то этап в первой группе уравнений для доли CPU: Pcmax(x,t)= Ртах X DN I TN, (4.10) где индекс N ОТНОСИТСЯ к сетевой полосе пропускания.
Остальные, невозобновляемые ресурсы, можно описать в основном алгебраическими формулами типа РІ=РІМ (4-И) причем для большинства ресурсов зависимостью только от х, Pi = Pi(x) (4.12) так как в большей степени они являются функцией внутреннего состояния «потока исполнения» и их появление определяется алгоритмом работы конкретного «потока исполнения».
Отдельно стоит выделить ситуацию когда возможность выделения какого то конкретного ресурса ограничена его количеством (этот факт как обычно можно учесть набором алгебраических уравнений, связывающих отдельные «потоки исполнения» в отдельные моменты времени и их последовательность) или тем фактом, что конкретный экземпляр ресурса захвачен другим «потоком исполнения» и надо дожидаться его освобождения. Обычно это означает изменение поведения «потока исполнения», и появление или изменение размера зон во времени, когда «поток исполнения» находится в состоянии ожидания. Таким образом, можно выделить два класса состояния «потока исполнения» - вынужденное ожидание, связанное с обработкой системой запроса на неудовлетворенный ресурс, и «врожденное» ожидание, связанное с его алгоритмом работы.
Также, используя подобный подход, можно смоделировать последовательность работы разных «потоков исполнения», когда результат работы одного «потока исполнения» может быть использован как начальное условие для другого «потока исполнения». Другим вариантом может быть ситуация, когда текущее состояние «потоков исполнения» связывают более сложные алгебраические уравнения, описывающие, например, обмен данными между параллельными нитями, используемыми в одной расчетной программе.
Рассмотрим общий подход к решению гиперболических уравнений, заданных на графе. Этот подход описан, например, в [5; 128; 7; 8; 9; 10; 11; 24; 29] и использовался автором для моделирования процессов, происходящих в средах со сложной многомерной геометрией и реологией. Его адаптация для работы на графах изложена по описанию в [128; 129; 130].
Пусть на каждом ребре к направленного графа (сети, дерева, других вариантов графа - рис. 58) необходимо найти решение одномерной системы уравнений гиперболического типа v/+Avit=0, t 0,-X -X ,k = l,...,K. (4.13) Здесь v = {v1,...,v/} вектор искомых параметров, А = {а }, i, j = 1,...,/ матрица, которая может быть разной на каждой из ветвей, / - размерность системы уравнений (4.1). К- число ветвей (ребер) графа. Эта система может быть линейной или нелинейной, дивергентной, иметь ненулевую правую часть и т.д., что не принципиально для последующего изложения.
Из предположения о гиперболичности (4.13) следует, что матрица А имеет только действительные собственные значения (возможно и кратные) Л = {Л.} (г = 1,...,/), определяемые как корни уравнения Pl(A) = Det(A-AE)=0 (414) (Е - единичная матрица) и базис П = } Detl 0 (4.15) из левых собственных векторов Щ,і = \,...,І (являющихся строками матрицы О.), для каждого Я, с точностью до длины определяемых из однородных линейных систем уравнений
Такая характеристическая форма уравнений (4.13) (или ее модификации с использованием инвариантов Римана, если удается найти соответствующее точное решение (4.18), часто используется для построения эффективных разностных схем для решения (4.13)), а в граничных точках она необходима для замыкания граничных условий.
Как известно, корректная постановка краевых условий для (4.13) заключается в задании начальных условий v(0,xk) = v\xk) (420) и граничных условий при -= 0 и хк=Хк в узлах графа l = l,...,L,L + l,...,L + L,L + L +1,...,L + L +L Здесь L число внутренних узлов графа (с которыми связано более одной ветви), L" - число узлов - входов графа (из которых исходит только одна ветвь графа), L - число узлов - выходов графа (в которые входит только одна ветвь графа). На рис. 58 приведен пример нумерации ветвей (к = 1,...,К) и узлов ( / = 1,...,L,L + 1,...,L + L\L + L + 1,...,L + L + L) направленного графа. Эта нумерация может быть и любой другой. Чтобы подчеркнуть тот факт, что для определения искомых параметров wt во внутренних узлах графа = 1 — - могут привлекаться самые разные математические модели (алгебраические или обыкновенные дифференциальные уравнения, уравнения в частных производных и т.д.), часть таких узлов обозначена точками (I 1 3), а остальные - прямоугольниками ( — 2,L — 1,L)
На свободных концах ветвей (ребер) графа (в узлах l = L+\,...,L+E - входах графа, для которых хк =0 и в узлах / = L+L+1,...,L+L + L - выходах графа для которых хк = Хк) постановка краевых условий ничем не отличается от обычной постановки краевых условий одномерной гиперболической системы, а именно, в каждый момент времени число граничных условий ( гк - для входов, гк - для выходов) должно быть равно
числу уходящих за область интегрирования характеристик (4.19) и, вместе с условиями совместности (4.18) вдоль идущих внутрь области интегрирования характеристик, они должны составлять линейно-независимую дифференциально-алгебраическую систему.
