Математическое обеспечение оперативного обнаружения ошибок потока управления на основе обработки графов большой размерности

• Автор: Рожков, Максим Владимирович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Воронеж
• Количество страниц: 163 с. : ил.

Содержание
Введение
1 Обоснование возможности исследования оперативности обнаружения ошибок потока управления на основе графовых моделей программ
1.1 Общие принципы обнаружения ошибок потока управления встроенными в программу средствами
1.2 Особенности современных программных методов обнаружения ошибок потока управления
1.3 Обоснование возможности исследования оперативности на графовых моделях
1.4 Выводы и постановка задач исследования
2 Разработка алгоритмов построения графовых моделей выполнения программ после возникновения ошибок потока управления для исследования оперативности их обнаружения
2.1 Разработка обобщённого алгоритма построения и анализа графовых моделей выполнения программ после возникновения ошибок потока управления
2.2 Пример построения и анализа графовой модели выполнения программы после возникновения ошибок потока управления
2.3 Детализация алгоритма построения и анализа графовых моделей для средств обнаружения ошибок по методу CEDA
3 Разработка программного комплекса для построения и исследования больших графовых моделей выполнения программ после возникновения ошибок потока управления
3.1 Разработка подсистемы эмуляции на базе эмулятора Qemu
3.2 Разработка подсистемы построения и анализа графовых моделей
3.3 Разработка подсистемы имитационного моделирования
4 Обоснование предложений по повышению оперативности построенных по методу CEDA средств обнаружения ошибок потока управления

4.1 Построение и исследование графовых моделей для группы тестовых программ из Phoronix Test Suite
4.2 Предпосылки повышения оперативности обнаружения ошибок потока управления
4.3 Построение и исследование графовых моделей для преобразованных согласно усовершенствованному методу CEDA тестовых программ
5 Разработка и экспериментальное исследование метода оперативного обнаружения ошибок потока управления
5.1 Алгоритмизация метода оперативного обнаружения ошибок потока управления
5.2 Реализация метода оперативного обнаружения ошибок потока управления для процессоров архитектуры х
5.3 Экспериментальное исследование разработанного метода оперативного обнаружения ошибок потока управления
Заключение

Введение
Актуальность темы. Современные средства проектирования программных продуктов, хотя и постоянно совершенствуются, не гарантируют [1] полного отсутствия ошибок программирования. Вместе с этим, цифровая аппаратура подвержена воздействию разнообразных сбоев, что, в совокупности, негативно влияет на надежность функционирования и безопасность применения цифровых систем с программным управлением. Для обеспечения требуемого уровня надёжности и безопасности, применяют специальные средства, которые обнаруживают и соответствующим образом обрабатывают возникающие во время работы программы ошибки. Одним из классов ошибок, существенным образом влияющих на безопасность систем управления, являются [2] ошибки потока управления (Control-Flow Errors или CFE [3]), которые приводят к тому, что система управления теряет управляемость, так как начинает реализовывать некоторую псевдопрограмму. Эффективность средств обнаружения CFE принято [4] оценивать по четырём параметрам: задержка обнаружения (ошибок) -определяет оперативность средств обнаружения; покрытие ошибок; избыточность по памяти и избыточность по процессорному времени.
Начиная с 60-х годов прошлого века, разрабатываются и используются аппаратные [5-18], программные [3, 19-28] и гибридные (программно-аппаратные) [29-33] средства обнаружения ошибок потока управления, однако в настоящее время, из-за существенного усложнения архитектуры микропроцессоров [34-36], бурно развиваются программные средства обнаружения CFE. Этому способствует постоянное увеличение быстродействия микропроцессоров и объёма программной памяти. Основополагающая суть процедуры построения программных средств обнаружения CFE, т.е. суть методов обнаружения CFE, заключается в эквивалентном преобразовании рабочей программы в защищенную программу путём представления программы в виде графа потока управления, состоящего из базовых блоков и связей между ними, нумерации этих блоков и

узлу из Уа. со,, при этом, является совокупностью ру: ] е1 чисел из диапазона р е[0;1], сумма которых равна единице: ®г ^ Ри—' , и представляет собой

нормированное на диапазоне от 0 до 1 частотное распределение значений } функции w1(Y), получаемое для достаточно длинной подаваемой на вход программы тестовой последовательности. При такой замене модель и объект эквивалентны с точки зрения частоты переходов между узлами, для случая проведения большого числа экспериментов, представляющих собой процесс: 1) начинающийся с начального узла бСРО, 2) заключающийся в последовательном вычислении значения функций у,(У) — в случае объекта (значения случайной величины ^, распределённой согласно вероятностной мере со, — в случае модели), для определения следующего узла (и соответственно, следующей вычисляемой функции) и 3) заканчивающегося при достижении узла а. Применение описанной замены детерминированных переходов в графе потока управления на вероятностные также обеспечивает соблюдение требования на независимость вероятности переходов между состояниями цепи Маркова от маршрута попадания в эти состояния, поскольку вероятностные меры со, являются безусловными. Подобный подход представления программы в виде графовой модели широко используется [65, С. 41] при анализе времени выполнения различных участков программ.
Тогда графовую модель программы, образованную из бСРв, для каждого узла 1 которого задана вероятностная мера со, на I и задан начальный узел, можно рассматривать [66, С. 56] как цепь Маркова с дискретным временем (далее просто цепь Маркова). Вероятностная мера со, при этом представляет собой 1-ю строку переходной матрицы Р , содержащей частоты переходов из состояния 1 в каждое из остальных состояний — узлов с1СК1.
Подобное представление позволяет применить к бСРв программы положений из теории цепей Маркова, одним из которых является следующая