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

  • Автор:
  • Специальность ВАК РФ: 05.13.11
  • Научная степень: Кандидатская
  • Год защиты: 2015
  • Место защиты: Воронеж
  • Количество страниц: 163 с. : ил.
  • бесплатно скачать автореферат
  • Стоимость: 230 руб.
Титульный лист Математическое обеспечение оперативного обнаружения ошибок потока управления на основе обработки графов большой размерности
Оглавление Математическое обеспечение оперативного обнаружения ошибок потока управления на основе обработки графов большой размерности
Содержание Математическое обеспечение оперативного обнаружения ошибок потока управления на основе обработки графов большой размерности

Содержание
Введение
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.
Подобное представление позволяет применить к бСРв программы положений из теории цепей Маркова, одним из которых является следующая

Рекомендуемые диссертации данного раздела