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

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

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

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

Transcript

1. Обобщённая теория восстановления деревьев процессов: подводные камни checkpoint/restore Николай Ефанов МФТИ(ГУ) So/ware Engineering Conference Russia November 14-15, 2019. Saint-Petersburg
2. Checkpoint-Restore 2 Host 1 Host 2 сохранить возобновить
3. Применение 1.  Живая миграция 2.  Технологии контейнерной виртуализации 3.  Восстановление после сбоев 4.  Отложенная отладка 5.  Обновления ядра ОС «на лету» 6.  Ускорение загрузки приложений 7.  Пауза в играх J 3
4. Подзадача: восстановить дерево процессов: 4
5. Подзадача: восстановить дерево процессов…решение: 5
6. Подзадача: восстановить дерево процессов… 1.  Профилировка + простота и истинность измерений - накладные расходы и непрозрачность 2.  Эвристики реконструкции -неполное покрытие 3.  Математическое моделирование +должно работать -а какой сложности? 6
7. Формальные модели восстановления: Алгоритм AGTTM 7 Tà G(T) à ребёрное покрытие T\{root} à список команд
8. Формальные модели восстановления: Алгоритм AGTTM 1.  Препроцессинг: Восстановить завершённые процессы, порядок в поддеревьях (обратить все «обратные reparent’ы») 2.  Обработка 3.  Пост-обработка 8
9. Формальные модели восстановления: Алгоритм AGTTM 1.  Препроцессинг: Восстановить завершённые процессы 2.  Обработка: построить граф G(T) на базе анализа Т 3. Пост-обработка 9
10. Формальные модели восстановления: Алгоритм AGTTM 1.  Препроцессинг: Восстановить завершённые процессы 2.  Обработка: 3. Пост-обработка 10 <<input
11. Формальные модели восстановления: Алгоритм AGTTM 1.  Препроцессинг: Восстановить завершённые процессы 2.  Обработка: 3. Пост-обработка 11 output>>
12. Пост-обработка графа: зачем? 12
13. Пост-обработка графа: зачем? 13 Рассмотрим дерево (1 1 1) à(2 3 1) à(3 2 1) T G(T) Граф действий
14. Пост-обработка графа: зачем? 14 Рассмотрим дерево (1 1 1) à(2 3 1) à(3 2 1) Цикл на вершинах!!! T G(T) Граф действий
15. Анализ зависимостей Давайте разбираться… Исследуем зависимости между атрибутами более формально 15
16. Анализ зависимостей 16 Семантика: зависимость (u,v): для реализации u нужно v. Задан частичный порядок на вершинах G(T)! Для любого подмножества состояний существует единственный ближайший прародитель. Теорема 1.
17. Диаграмма зависимостей 17 G(T) Диаграмма Хассе G(T).nodes
18. Диаграмма зависимостей 18 Это же не полурешётка L Надо исправлять! G(T) Диаграмма Хассе G(T).nodes
19. Промежуточный носитель 19 Теперь полурешёткаJ Единственное присваивание- SSA-форма! (привет компиляторам)
20. Обобщаем 20 Общая схема реконструкции
21. Нужно больше обобщений… 21
22. Нужно больше обобщений… 22 Кроме того… Лемма 2. Лемма 1. Лемма 3.
23. Критерий корректности дерева 23 Смысл: быстрая генерация корректных тестов Теорема 2.1. Теорема 2.2.
24. Где это ещё применить? Disclaimer: везде, где состояния + зависимости = полурешётка. •  Реинжиниринг иерархий классов в ООП: подъемы/спуски полей/методов для классов/суперклассов: •  Реверс-инжиниринг иерархий классов в ООП: •  Генерация тестов для ОС, систем виртуализации, etc 24
25. Где это ещё применить? Disclaimer: везде, где состояния + зависимости = полурешётка. •  Реинжиниринг иерархий классов в ООП: подъемы/спуски полей/методов для классов/суперклассов: •  Реверс-инжиниринг иерархий классов в ООП: •  Генерация тестов для ОС, систем виртуализации, etc 25
26. Где это ещё применить? Disclaimer: везде, где состояния + зависимости = полурешётка. •  Реинжиниринг иерархий классов в ООП •  Реверс-инжиниринг иерархий классов в ООП: Проект Marx: h~p://www.cs.ucy.ac.cy/~eliasathan/papers/ndss17.pdf Основная идея: эвристический анализ таблиц vtable из бинарных файлов соответствующего ABI, выстраивание частичных порядков на записях. •  Генерация тестов для ОС, систем виртуализации, etc 26
27. Выводы: 27 1.  Обобщённая модель позволяет: •  Гарантированно восстанавливать деревья процессов •  Исправлять аномалии реконструкции •  Справляться с множеством различных ресурсов •  Служить генератором тестов (быстрее, чем перебор) Открытые вопросы: - Любые ли отношения между атрибутами допустимы (дисклеймер: скорее нет – затруднительно описываются файловые блокировки, другие несравнимые объекты) -  Интеграция в индустрию (Вероятно, CRIU?)
28. 28 1.  Ефанов Николай, МФТИ 2.  h~ps://github.com/nefanov 3.  nefanov90@gmail.com Contact