Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Единая теория восстановления деревьев процессов...

SECR 2019
November 15, 2019

Единая теория восстановления деревьев процессов Linux: огибая подводные камни checkpoint-restore

Николай Ефанов
Преподаватель/Аспирант/Разработчик, МФТИ
SECR 2019

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

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

SECR 2019

November 15, 2019
Tweet

More Decks by SECR 2019

Other Decks in Programming

Transcript

  1. Применение 1.  Живая миграция 2.  Технологии контейнерной виртуализации 3.  Восстановление

    после сбоев 4.  Отложенная отладка 5.  Обновления ядра ОС «на лету» 6.  Ускорение загрузки приложений 7.  Пауза в играх J 3
  2. Подзадача: восстановить дерево процессов… 1.  Профилировка + простота и истинность

    измерений - накладные расходы и непрозрачность 2.  Эвристики реконструкции -неполное покрытие 3.  Математическое моделирование +должно работать -а какой сложности? 6
  3. Формальные модели восстановления: Алгоритм AGTTM 1.  Препроцессинг: Восстановить завершённые процессы,

    порядок в поддеревьях (обратить все «обратные reparent’ы») 2.  Обработка 3.  Пост-обработка 8
  4. Формальные модели восстановления: Алгоритм AGTTM 1.  Препроцессинг: Восстановить завершённые процессы

    2.  Обработка: построить граф G(T) на базе анализа Т 3. Пост-обработка 9
  5. Пост-обработка графа: зачем? 14 Рассмотрим дерево (1 1 1) à(2

    3 1) à(3 2 1) Цикл на вершинах!!! T G(T) Граф действий
  6. Анализ зависимостей 16 Семантика: зависимость (u,v): для реализации u нужно

    v. Задан частичный порядок на вершинах G(T)! Для любого подмножества состояний существует единственный ближайший прародитель. Теорема 1.
  7. Где это ещё применить? Disclaimer: везде, где состояния + зависимости

    = полурешётка. •  Реинжиниринг иерархий классов в ООП: подъемы/спуски полей/методов для классов/суперклассов: •  Реверс-инжиниринг иерархий классов в ООП: •  Генерация тестов для ОС, систем виртуализации, etc 24
  8. Где это ещё применить? Disclaimer: везде, где состояния + зависимости

    = полурешётка. •  Реинжиниринг иерархий классов в ООП: подъемы/спуски полей/методов для классов/суперклассов: •  Реверс-инжиниринг иерархий классов в ООП: •  Генерация тестов для ОС, систем виртуализации, etc 25
  9. Где это ещё применить? Disclaimer: везде, где состояния + зависимости

    = полурешётка. •  Реинжиниринг иерархий классов в ООП •  Реверс-инжиниринг иерархий классов в ООП: Проект Marx: h~p://www.cs.ucy.ac.cy/~eliasathan/papers/ndss17.pdf Основная идея: эвристический анализ таблиц vtable из бинарных файлов соответствующего ABI, выстраивание частичных порядков на записях. •  Генерация тестов для ОС, систем виртуализации, etc 26
  10. Выводы: 27 1.  Обобщённая модель позволяет: •  Гарантированно восстанавливать деревья

    процессов •  Исправлять аномалии реконструкции •  Справляться с множеством различных ресурсов •  Служить генератором тестов (быстрее, чем перебор) Открытые вопросы: - Любые ли отношения между атрибутами допустимы (дисклеймер: скорее нет – затруднительно описываются файловые блокировки, другие несравнимые объекты) -  Интеграция в индустрию (Вероятно, CRIU?)