Математическое обеспечение оперативного обнаружения ошибок потока управления на основе обработки графов большой размерности тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Рожков, Максим Владимирович

• Рожков, Максим Владимирович
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Рожков, Максим Владимирович

Содержание

Введение

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 Реализация метода оперативного обнаружения ошибок потока управления для процессоров архитектуры х86-64

5.3 Экспериментальное исследование разработанного метода оперативного обнаружения ошибок потока управления

Заключение

Введение диссертации (часть автореферата) на тему «Математическое обеспечение оперативного обнаружения ошибок потока управления на основе обработки графов большой размерности»

Введение

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

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

последующего добавления в каждый блок следящих и проверяющих операций, обеспечивающих обнаружение неправильных переходов между этими блоками. В работах Oh М. [22], Голубевой О. [23] следящие операции размещались только в начале базовых блоков, а у Furtado Р. [20], Venkatasubramanian R. [24], Vemu R. [3] — ещё и в их конце, что позволило достичь высоких показателей покрытия ошибок. У Vemu R. в методе Control-Flow Error Detection Using Assertions (CEDA) дополнительно предложено размещать проверяющие операции не в каждом базовом блоке, а через определённое количество узлов в графе потока управления, вплоть до их размещения только в базовых блоках с инструкциями возврата из функций и вывода данных, что позволило существенно сократить уровень вносимой избыточности без ущерба для покрытия ошибок. Но такое размещение проверяющих операций неизбежно приводит к увеличению задержки обнаружения, численное значение которой во многом определяет безопасность применения систем с программным управлением. Представленные в доступной литературе методы и средства, обладают ограниченными возможностями по целенаправленному размещению проверяющих операций, что может быть обусловлено как большой размерностью формальных модельных представлений решаемой задачи, так и отсутствием соответствующего математического обеспечения, оперирующего с такими модельными представлениями. Таким образом, актуальность темы определяется необходимостью разработки средств для формального исследования задержки обнаружения с целью обеспечения оперативного обнаружения CFE и повышения тем самым безопасности применения систем с программным управлением.

Тематика диссертационной работы соответствует одному из научных направлений ФГБОУ ВПО «Воронежский государственный технический университет» «Вычислительные комплексы и проблемно-ориентированные системы управления».

Цели и задачи исследования. Цель диссертационной работы — разработать математическое обеспечение оперативного обнаружения ошибок

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

Задачи исследования:

1) обоснование возможности исследования оперативности обнаружения ошибок потока управления на основе графовых моделей программ;

2) разработка алгоритмов построения графовых моделей выполнения программ после возникновения ошибок потока управления для исследования оперативности их обнаружения;

3) разработка программного комплекса для построения и исследования больших графовых моделей выполнения программ после возникновения ошибок потока управления;

4) обоснование предложений по повышению оперативности построенных по методу CEDA средств обнаружения ошибок потока управления;

5) разработка и экспериментальное исследование метода оперативного обнаружения ошибок потока управления.

Методы исследования. В диссертационной работе использовались: методы теории компиляторов, теории цепей Маркова, теории графов, математической статистики и теории вероятностей, методы хранения и обработки данных.

Соответствие диссертации паспорту специальности. Работа соответствует следующим пунктам паспорта специальности 05.13.11 — «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»:

- п.1: «Модели, методы и алгоритмы проектирования и анализа программ и программных систем, их эквивалентных преобразований, верификации и тестирования»;

- п. 8: «Модели и методы создания программ и программных систем для параллельной и распределенной обработки данных, языки и инструментальные средства параллельного программирования».

Научная новизна работы. В диссертационной работе получены следующие основные результаты, характеризующиеся научной новизной:

— алгоритм построения и анализа графовых моделей выполнения программ после возникновения ошибок потока управления, отличающийся тем, что включает в модели все возможные в программе ошибочные переходы и пути последующего выполнения программы, и позволяющий получать численные значения средней задержки обнаружения и доли пропускаемых ошибок потока управления;

— алгоритм вычисления достижимости в направленном графе заданного узла, отличающийся тем, что учитывает частичную регулярность матриц смежности, обрабатывая множество узлов с одинаковой структурой связей как один узел, и позволяющий производить параллельную обработку больших графовых моделей выполнения программ;

— усовершенствованный формат хранения разреженных матриц, учитывающий частично регулярную структуру матриц, возникающих при построении больших графовых моделей выполнения программ после возникновения ошибок потока управления, и позволяющий сократить занимаемую матрицей память и количество выполняемых операций при умножении матрицы на вектор с возможностью их распараллеливания;

— алгоритм преобразования программ для обеспечения оперативного обнаружения ошибок потока управления, отличающийся тем, что проверяющие операции формируются из набора инструкций вызова исключительной ситуации, а их размещение производится на наиболее критических путях потока управления программы, и позволяющий обнаруживать все одиночные межузловые ошибки потока управления с ожидаемой задержкой.

Практическая значимость работы заключается в: создании программного комплекса, позволяющего строить и исследовать большие графовые модели выполнения программ после возникновения СБЕ для анализа средних задержек обнаружения СБЕ ещё на этапе проектирования средств обнаружения СБЕ на вычислительной системе общего назначения с 2-4 Гб оперативной памяти и с восьмью потоками исполнения; в разработке и реализации средств оперативного

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

Реализация и внедрение результатов работы. Алгоритмы и формат хранения матриц, предложенные в диссертации, реализованы в виде программного комплекса для построения и исследования больших графовых моделей выполнения программ после возникновения CFE, а так же в виде плагина ЕССВТ plug-in к компоновщику объектных файлов для преобразования программы во время компиляции с целью обеспечения оперативного обнаружения CFE.

Программный комплекс внедрен и используется в учебном процессе Воронежского государственного технического университета.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на одной международной и двух всероссийских конференциях: Всероссийская научно-техническая конференция «Перспективные исследования и разработки в области информационных технологий и связи» (II «Воронежский межрегиональный форум инфокоммуникационных технологий 2012»), г. Воронеж; Х-я международная научно-практическая конференция «Актуальные проблемы профессионального образования: подходы и перспективы» г. Воронеж; XII Всероссийская научно-техническая конференция «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (НТ ВГТУ-2013), г. Воронеж.

Работа выполнена при финансовой поддержке Фонда содействия развитию малых форм предприятий в научно-технической сфере (проекты №14035, №16871).

Публикации. По результатам исследования опубликовано 9 [37-45] научных работ, в том числе 3 [38, 42, 43] - в изданиях, рекомендованных ВАК РФ, получено 2 [37, 45] патента на способ, 3 [39, 40, 44] свидетельства на программы для электронных вычислительных машин. В работах, опубликованных в соавторстве и приведенных в конце автореферата, вклад лично соискателя

состоит: в [39, 40] — в разработке программ для построения и исследования графовых моделей и имитационного моделирования процесса выполнения программ после возникновения ошибок потока управления; в [38, 37, 45] — в разработке способов формирования и размещения операций проверки для обеспечения оперативного обнаружения ошибок потока управления; в [44] — в разработке плагина к компоновщику объектных файлов .

Структура и объем работы. Диссертация состоит из введения, пяти глав и заключения. Основная часть работы изложена на 163 страницах машинописного текста, включая 10 таблиц и 64 рисунка. Список литературы содержит 95 наименований.

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

В первой главе проведено обоснование возможности исследования оперативности обнаружения ошибок потока управления на основе графовых моделей программ. Рассмотрены основные понятия, применяемые в программных средствах обнаружения СБЕ. Описываются два наиболее эффективных метода обнаружения СЕЕ. Проанализированы известные способы исследования задержки программных средств обнаружения СЕЕ и обоснована возможность применения нового способа, основанного на сводимости процесса выполнения программы после возникновения СЕЕ к Марковским процессам. Выполнена постановка цели и задач исследования.

Во второй главе диссертации разработаны алгоритмы построения графовых моделей выполнения программ после возникновения ошибок потока управления для исследования оперативности их обнаружения. Предложен обобщённый алгоритм построения и анализа графовых моделей выполнения программы после возникновения СЕЕ. Приведён пример построения и анализа графовой модели

выполнения программы после возникновения CFE. Обобщённый алгоритм детализирован применительно к построенным по методу CEDA средствам обнаружения CFE.

В третьей главе диссертации описан разработанный программный комплекс для построения и исследования больших графовых моделей выполнения программ после возникновения CFE. В подсистемах комплекса реализованы разработанные: алгоритм построения графовых моделей выполнения программ после возникновения ошибок потока управления, алгоритм вычисления достижимости в направленном графе заданного узла и задействован усовершенствованный формат хранения разреженных матриц.

В четвёртой главе диссертации для обоснования предложений по повышению оперативности построенных по методу CEDA средств обнаружения CFE с использованием разработанного программного комплекса производится построение, согласно разработанному во второй главе детализированному алгоритму, графовых моделей для тестовых программ со встроенными средствами обнаружения CFE по методу CEDA. На основе результатов моделирования выдвигаются предложения по повышению оперативности построенных по методу CEDA средств обнаружения CFE. Посредством построения графовых моделей выполнения программ после возникновения CFE и проведения исследования этих моделей подтверждается эффективность выдвинутых предложений.

В пятой главе разработан на основе метода CEDA и комплекса проверенных предложений по повышению оперативности построенных согласно методу CEDA средств обнаружения CFE метод оперативного обнаружения ошибок потока управления. Предложен алгоритм этого метода. Разработана программная реализация алгоритма метода для процессоров архитектуры х86-64 в виде плагина к компоновщику объектных файлов, работающего в окружении компиляторной инфраструктуры LLVM. Для тестовой программы со встроенными, посредством разработанного плагина к компоновщику, средствами обнаружения CFE произведено экспериментальное исследование задержки

обнаружения СБЕ под управлением подсистемы имитационного моделирования разработанного программного комплекса. Для этой же тестовой программы оценена степень избыточности по используемой памяти и процессорному времени. Результаты экспериментов согласуются с полученными из анализа графовой модели и подтверждают работоспособность разработанного метода оперативного обнаружения СБЕ.

В заключении излагаются основные результаты диссертации.

1 Обоснование возможности исследования оперативности обнаружения ошибок потока управления на основе графовых моделей программ

1.1 Общие принципы обнаружения ошибок потока управления встроенными в

программу средствами

Согласно [3] под ошибкой потока управления понимают расхождение в последовательности инструкций, исполняемых после возникновения сбоя, с рабочей последовательностью инструкций. Большинство известных методов обнаружения СРЕ реализуются за счёт контроля последовательности исполняемых инструкций посредством той или иной вариации сигнатурного мониторинга. В целом, сигнатурный мониторинг основывается на том, что предварительно (до выполнения программы) некоторым образом выделенным из программы непересекающимся множествам инструкций ставятся в соответствие уникальные числа (эталонные значения сигнатуры), а во время выполнения программы текущее значение сигнатуры постоянно специальным образом обновляется, чтобы при отсутствии СБЕ всегда соответствовать эталонному значению, а при возникновении СРЕ — всегда отличаться от него. При обеспечении указанных требований, для контроля последовательности исполняемых инструкций достаточно сравнивать текущее значение сигнатуры с эталонным и, при их несовпадении, сигнализировать об обнаружении СРЕ. Обычно, в качестве множеств инструкций, которым назначаются уникальные эталонные сигнатуры, выбирают уже существующие структурные единицы, из которых состоит программа на этапе компиляции, например, функции или базовые блоки.

В зависимости от уровня вычислительной системы, средствами которого реализуется обновление текущего значения сигнатуры и сравнение её с эталонным значением, методы обнаружения СРЕ разделяют на программные, аппаратные и гибридные. Программные методы обнаружения СРЕ обычно

заключаются в реализации этих операций посредством встраивания в основной поток управления программы дополнительных инструкций, называемых в случае реализации операции обновления — следящие (англ. tracking), а в случае реализации операции сравнения — проверяющими (англ. checking) [20].

Процесс выполнения программы со средствами обнаружения CFE можно разделить во времени на три интервала (рисунок 1.1): (0; to), (to; t0+k) и (>t0+k). На отрезке (0; to) программа находится в исправном состоянии, а средства обнаружения CFE, производя следящие операции, обновляют текущее значение сигнатуры. В момент времени to происходит возникновение CFE. На отрезке (to; to+k) в программе начинает выполняться последовательность инструкций, отличная от рабочей, при этом могут также исполняться инструкции проверяющих операций средств обнаружения CFE. В том случае, если одна из таких операций обнаруживает факт возникновения CFE, то в момент времени t0+k управление передаётся в обработчик CFE, реализующий некоторую процедуру восстановления, которая работает на интервале >to+k. Поскольку большинство программных средств обнаружения CFE проектируются таким образом, чтобы ошибка обнаруживалась при первом достижении операции проверки, под срабатыванием средств обнаружения CFE будем понимать переход в обработчик

ошибки из этой операции проверки.

Возникновение Обнаружение CFE CFE

I-1-1-►

0 Исправное ^ Задержка t+k t состояние 0 ^

Рисунок 1.1 — Задержка обнаружения CFE Для исключения расхождений в интерпретации понятия задержки обнаружения относительно ошибок потока управления примем, по аналогии с [46], её равной времени к между моментом (to) возникновения CFE и моментом (to+k) попадания управления в обработчик CFE (рисунок 1.1). Поскольку, в случае программных методов обнаружения CFE, подразумевается их реализация в виде дополнительных инструкций, задержка обнаружения CFE принимает только

дискретные значения, кратные времени исполнения инструкции. Поэтому при анализе программных средств обнаружения CFE будем оперировать задержкой, выраженной в количестве исполненных инструкций от момента возникновения CFE до момента попадания в обработчик CFE. Используя известные из спецификации микропроцессора граничные значения времени исполнения каждой из инструкций, при необходимости, можно перейти от величины задержки, выраженной в количестве инструкций, к величине, выраженной в секундах.

Программные средства обнаружения CFE не могут гарантировать обнаружение любых CFE, что позволяет предположить, что средняя задержка обнаружения будет зависеть от а) среднего времени обнаружения CFE, в случае срабатывания средств; б) среднего времени обнаружения CFE, в случае несрабатывания средств; в) степени покрытия возможных CFE. Среднее значение задержки обнаружения ошибок вносит вклад в среднее время восстановления системы, являющееся одним из показателей надёжности [47]. Также обнаружение CFE с минимальной задержкой необходимо для построения подсистемы восстановления из-за необходимости обеспечения обнаружения ошибки до достижения лимита модификаций контекста [48], [49 С. 248-249].

Описанный процесс выполнения программы фактически протекает в микропроцессоре. Тем не менее, при разработке средств обнаружения CFE, для его представления часто используют граф потока управления. Граф потока управления (англ. Control-Flow Graph или CFG [3]), так же ещё называемый в русскоязычных источниках просто как граф потока [50, С. 644-647], определяет рабочую последовательность инструкций, по отношению к которой и рассматривается наличие или отсутствие CFE. Узлы Ni, N2, ... ,Na, образующие множество V, графа потока управления P={V, Е} соответствуют базовым блокам, а рёбра ei, е2, ..., еп, образующие множество Е, представляют возможные в программе переходы между базовыми блоками (рисунок 1.2). Определяют множество приемников узла N, succ(yV), состоящее из узлов, в которые можно непосредственно перейти из узла N, и множество предшественников узла N,

pred(Ar), состоящее из узлов, из которых можно непосредственно перейти в узел N. На уровне представления программы в виде графа потока управления CFE можно представить как переход из М bN$ в случае отсутствия в CFG программы ребра из N\ в Nj (на рисунке 1.2 CFE показана пунктирной линией из N2 в N5). Но CFE может вполне заключатся и в переходе, представленном в CFG, например, в случае перехода из N3 в N5 при истинности условия if(cond2).

c=a+b; if(cond){

а=с; }else { b=c;

a=a+l; if(cond2){ c=a*b;

}

c=10; do{

С C+1 f

}while(a!=c) return с;

Рисунок 1.2 — Представление потока управления программы в виде графа Каждый базовый блок [50 С. 642] (англ. Basic Block или ВВ) представляет собой последовательность инструкций с одной точкой входа (т.е. только первая инструкция последовательности может быть назначением инструкций передачи управления), одной точкой выхода и не содержащую инструкций передачи управления ранее точки выхода [51]. Поэтому базовый блок N\ можно представить как линейный ориентированный граф Pn(M)={v, е}, узлы v={ni, гь, пп} которого соответствуют инструкциям базового блока, а рёбра е — допустимым переходам между ними. Точка входа базового блока будет соответствовать входному узлу (п„) графа PN(Wi), точка выхода — выходному узлу (nout) графа РкСЭД), а остальные

инструкции базового блока будут соответствовать узлам n¡ графа PN(W¡), лежащим на пути из пь в nout- Инструкцию, соответствующую nout, называют терминатором.

Особенность современных компиляторов [52, 53] заключается в том, что в виде CFG в них представляется не вся программа или модуль, а отдельная функция. Сложность представления всей программы в виде единого CFG обусловлена наличием в программе косвенных вызовов функций, поскольку для содержащих их базовых блоков сложно определить множество приемников. Известен [54] подход к определению множества вызываемых функций, в том числе и для косвенных вызовов. Тем не менее, на практике далеко не для всех программ с его помощью удаётся построить единый CFG программы. Известные методы обнаружения CFE обычно работают именно с CFG функций. Корректность вызовов и возвратов из функций при этом обеспечивается отличным от сигнатурного мониторинга методом.

Поскольку CFG представляет рабочую последовательность инструкций лишь на уровне крупных фрагментов — базовых блоков, — с его помощью невозможно представить любые CFE т. к. они могут заключатся, в том числе, в переходе не на начало базового блока. Для такого представления используется детализированный граф потока управления (англ. detailed Control Flow Graph или dCFG). dCFG будем называть такой граф Pd={Vd, Ed}, который получается в результате операции над графом потока управления Р, заключающейся в замене всех узлов Ni графа Р на графы Pn(7Ví). При этом для всех входящих в N\ рёбер конечный узел заменяется с Ni на узел n¡n графа Pn(AV), а для всех исходящих из yV¡ рёбер начальный узел заменяется на узел nout графа PN(M).

На рисунке 1.3 приведён фрагмент dCFG для функции с рисунка 1.2. Связи между узлами графов РN(jV¡) не представлены в виде линий для повышения наглядности. Символами 7V¡ обозначены узлы CFG, из которых получились относящиеся к одному графу Pn(ÍVí) узлы dCFG. Пунктирной линией обозначена CFE, заключающаяся в переходе с инструкции muí узла N4 на инструкцию стр узла N6.

Рисунок 1.3 — Фрагмент представления потока управления программы в виде

dCFG

Детализированный граф потока управления позволяет представлять любые CFE для микропроцессоров с фиксированной длиной инструкций, но для микропроцессоров с переменной длиной инструкции, а это большинство микропроцессоров CISC архитектуры, в том числе и х86-64, его уровня детализации недостаточно из-за возможности попадания в результате ошибочного перехода не на начало инструкции, после которого микропроцессор начинает интерпретировать операнды правильных инструкций как коды операций или операнды новых инструкций. Возможность совершения ошибочного перехода не на начало инструкции в программах для микропроцессоров с переменной длиной инструкций возникает по причине того, что для них минимальная адресуемая единица при обращении к инструкциям в памяти обычно составляет один байт, а длина инструкции может составлять от одного байта до двадцати байт.

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

Для обеспечения возможности представления CFE, заключающихся в переходах не на начало инструкций, и последующего процесса выполнения программы введём представление программы в виде расширенного графа потока управления (англ. extended Control Flow Graph или eCFG). eCFG представляет собой граф Ре — {Ve, Ее}, узлами Ve которого являются возможные в программе начала инструкций, а связями Ее — возможные при нормальной работе микропроцессора маршруты выполнения, которые могут возникнуть при произвольной интерпретации содержимого сегмента кода как инструкций. При этом множества Ve и Ес состоят из двух подмножеств: Ve = {Vt, Vf} и Ее = {Ет, EF}. Узлы VT соответствуют началам правильных инструкций, составляющих поток управления программы, а узлы VF — соответствуют началам неправильных инструкций. Ет содержит связи между узлами VT, a EF — связи, идущие из узлов VF. Поскольку переход не на начало инструкции возможен только в результате CFE, и не может содержаться в рабочей последовательности инструкций, очевидно, что eCFG не может содержать связи из VT в VF. А вот наличие связей из VF в Vt возможно, ввиду возможности такой ситуации, когда следом за последним байтом неправильной инструкции будет располагаться начало правильной инструкции.

Список литературы диссертационного исследования кандидат наук Рожков, Максим Владимирович, 2015 год

Библиография

1. Липаев В.В. Надёжность программных средств / В.В. Липаев. - Синтег, 1998.-232с.

2. ГОСТ Р 61508-2- 2007. Функциональная безопасность систем электрических, электронных, программируемых электронных, связанных с безопасностью , 2007, 65с.

3. Vemu R., Abraham J.A. CEDA: Control-Flow Error Detection Using Assertions // IEEE Trans, on Computers. - 2011. - V. 60, No. 9. - C. 1233-1245.

4. Saxena N. Control-Flow Checking Using Watchdog Assists and Extended-Precision Checksums // IEEE Transactions on Computers. - 1990. - V. 39 Iss. 4. - C. 554-559.

5. Daniels S. A Concurrent Test Technique for Standard Microprocessors // Dig. of Papers CornpconSpring. - IEEE, 1983. - C. 389-394.

6. Lu D. Watchdog Processors and Structural Integrity Checking // IEEE Transactions on Computers. - 1982. - C-31, 7. - C. 681-685.

7. Mahmood A. McCluskey E. J. Concurrent Fault Detection Using a Watchdog Processor and Assertions // Proc.1983 Int. Test Conf.. - Philadelphia, PA, 1983. - C. 14.

8. Mahmood A. McCluskey E. J. Concurrent Error Detecion Using Watchdog Processors - A Survey // IEEE Transactions on Computers. - 1988. - 37, 2. - C. 160174.

9. Wilken K. Shen J. Continuous signature monitoring: low-cost concurrent detection of processor control errors // IEEE Tran. on Computer-Aided Design of Integrated Circuits and Systems. - 1990. - V. 9, No. 6. - C. 629-641.

10. Namjoo M. Techniques for concurrent testing of VLSI processor operation // Dig. 1982 Int. Test Conf.. - Philadelphia, PA, 1982. - C. 461-468.

11. Shen J. Schuette M. On-line Self-Monitoring Using Signatured Instruction Streams // Proc. Int'l Test Conf. proceedings. - Philadelphia, PA, 1983. - C. 275-282.

12. Systems and methods for control flow error detection in reduced instruction

set computer processors: pat. 5974529 United States: G06F9/30, G06F11/36, G06F11/28 / John F. Zumkehr, Amir A. Abouelnaga; Pat. Assignee Mcdonnell Douglas Corp., Trw, Inc.. — № US 09/076,361; Filed May 12, 1998; Pub. Date October 26, 1999.

13. Hardware flow control monitor: pat. 7644322 United States: G06F11/00 / Albert Dye; Pat. Assignee Atmel Corporation. — № US7644322 B2; Filed November 21, 2006; Pub. Date January 5, 2010.

14. Method and system for hardware based program flow monitor for embedded software: pat. 7861305 United States: G06F12/14 / Suzanne Mcintosh, Daniel Brand, Matthew Kaplan, Paul A. Karger, Michael G. Mcintosh, Elaine R. Palmer, Amitkumar M. Paradkar, David Toll, Samuel M. Weber; Pat. Assignee International Business Machines Corporation. — № US7861305 B2; Filed February 7, 2007; Pub. Date December 28, 2010.

15. Method and apparatus for testing execution flow of program: pat. 8015553 United States: G06F9/44 / Myung-june Jung, Hyun-Jin Choi, Kyung-im Jung; Pat. Assignee Samsung Electronics Co., Ltd.. — № US8015553 B2; Filed January 22, 2007; Pub. Date September 6, 2011.

16. Устройство для контроля хода программы управляющей вычислительной машины: пат. 2059287 Рос. Федерация: МПК G06F 11/00 / Иванов А.И., Кладов В.Е., Забродский В.Б.; заявитель и патентообладатель Иванов А.И., Кладов В.Е., Забродский В.Б.. — № 4920501/09; заявл. 19.03.1991; опубл. 27.04.1996.

17. Устройство для контроля электронной вычислительной машины: пат. 2066877 Рос. Федерация: МПК G06F 11/00 / Храмов В.В.; Губарев O.K.; заявитель и патентообладатель Серпуховское высшее военное командно-инженерное училище ракетных войск им.Ленинского комсомола. — № 5020927/09; заявл. 03.01.1992; опубл. 20.09.1996.

18. Устройство для контроля управляющей вычислительной машины: пат. 2094842 Рос. Федерация: МПК G06F11/28 / Кладов В.Е., Орлов Д.В.; заявитель и патентообладатель Уфимский государственный авиационный технический уни-

верситет. — № 95112296/09; заявл. 18.07.1995; опубл. 27.10.1997.

19. Miremadi G. Two software techniques for on-line error detection // Fault-Tolerant Computing. - 1992. - FTCS-22. Digest of Papers.. - C. 328-335.

20. Furtado P., Madeira H. Fault Injection Evaluation of Assigned Signatures in a RISC Processor // Dependable Computing — EDCC-2. - Springer Berlin Heidelberg. -Springer, 1996.- C. 55-72.

21. Alkhalifa Z. Design and evaluation of system-level checks for on-line control flow error detection // Parallel and Distributed Systems, IEEE Transactions on. - 1999. -V. 10 , Iss. 6.-C. 627-641.

22. Oh N. Shirvani P. McCluskey E. J. Control Flow Checking by Software Signatures//IEEE Trans, on Reliability.-2000.-V. 51, No. 1. -C. 111-122.

23. Goloubeva O. Soft-error detection using control flow assertions // Defect and Fault Tolerance in VLSI Systems, 2003. Proceedings. 18th IEEE International Symposium on. - 2003. - 3-5 Nov.. - C. 581-588.

24. Venkatasubramanian R. Hayes J. Murray B. Low-cost on-line fault detection using control flow assertions // IEEE 9th Intl. On-Line Testing Symp.. - 2003. -IOLTS 2003.-C. 137.

25. Borin E. et al. Software-Based Transparent and Comprehensive Control-Flow Error Detection // Proc. of the Intl. Symposium on Code Generation and Optimization. -IEEE Computer Society Washington, DC, USA, 2006. - C. 333-345.

26. Fazeli M. et. al A software-based concurrent error detection technique for power PC processor-based embedded systems // 20th IEEE Intl. Symp. on Defect and FaultTolerance in VLSI System. - IEEE, 2005. - C. 266-274.

27. Farhady N., et al Software-based Control Flow Error Detection and Correction Using Branch Triplication // Proc. 17th Intl. On-Line Testing Symp.. - IEEE Computer Society Washington, DC, USA, 2011. - C. 214-217.

28. Apparatus and method for software-based control flow checking for soft error detection to improve microprocessor reliability: pat. 7506217 United States: G06F11/00 / Edson Borin, Cheng C. Wang, Youfeng Wu; Pat. Assignee Intel Corporation. — №

US7506217 В2; Filed December 30, 2005; Pub. Date March 17, 2009.

29. Reis G. A. et al. Design and Evaluation of Hybrid Fault-Detection Systems // Proc. 32nd Intl. Sym. on Computer Architecture. — IEEE Computer Society Washington, DC, USA, 2005. - C. 148 -159.

30. Bergaoui S. et al. IDSM: An improved control flow checking approach with disjoint signature monitoring // Proc. Conf. on Design of Circuits and Integrated Systems (DCIS). - Zaragoza, Spain, 2009. - C. 249-254.

31. Azambuja J. R. et al. Detecting SEEs in microprocessors through a non-intrusive hybrid technique // Nuclear Science, IEEE Trans, on. - 2011. - V. 58. - Iss. 3.. -C. 993-1000.

32. Ragel R., Parameswaran S. Hardware Assisted Pre-emptive Control Flow Checking for Embedded Processors to improve Reliability // Proc. of the 4th intl. conf. on Hardware/software codesign and system synthesis. - ACM, 2006. - C. 100-105.

33. Chao W. et al. CFCSS without Aliasing for SPARC Architecture // IEEE 10th Intl. Conf. on Computer and Information Technology. - IEEE Computer Society Washington, DC, USA, 2011. - C. 2094 -2100.

34. Siewiorek D., Swarn R. The Theory and Practice of Reliable System Design / D. Siewiorek, R. Swarn. - Digital Press, 1982. - 772c.

35. Гассельберг B.C., Синелыциков A.B. Применение микроконтроллеров в устройствах с повышенной надежностью // Вестн. Астрахан. гос. техн. ун-та. Сер. управление, вычисл. техн. информ.. - 2011. - № 1. - С. 108-113.

36. Ravishankar I., Kalbarczyk Z. Hardware And Software Error Detection / I. Ravishankar, Z. Kalbarczyk. - University of Illinois at Urbana-Champaign, 2008. -47c.

37. Способ обнаружения случайных "блужданий" в микроЭВМ: пат. 2461051 Рос. Федерация: МПК G06F 11/00 / C.B. Тюрин, М.В. Рожков; заявитель и патентообладатель ГОВПО "Воронежский государственный технический университет". — №2010131651/08; заявл. 27.07.2010 опубл. 10.09.2012 Бюл. №25. Решение о выдаче патента от 28.03.2012.

38. Рожков M. Тюрин С. Перспективные подходы к повышению эффективности программного метода обнаружения ошибок потока управления // Системы управления и информационные технологии. - 2013. - № 1 (51). - С. 65-71.

39. Свидетельство о государственной регистрации программы для ЭВМ CFEstimates № 2013617841 / C.B. Тюрин, М.В. Рожков , дата государственной регистрации в реестре программ для ЭВМ 26.08.2013 .

40. Свидетельство о государственной регистрации программы для ЭВМ WalkingManager № 2013617842 / C.B. Тюрин, М.В. Рожков дата государственной регистрации в реестре C.B. Тюрин, М.В. Рожков программ для ЭВМ 26.08.2013 .

41. Рожков М. Подход к построению модели работы процессора после ошибок потока управления // Новые технологии в научных исследованиях, проектировании, управлении, производстве: труды Всерос. конф.. - Воронеж: ВГТУ, 2013. -С. 54-56.

42. Рожков М. Математическая модель исполнения программы микропроцессором после возникновения ошибок потока управления // Системы управления и информационные технологии. - 2014. - №1.1(55). - С. 190-198.

43. Рожков М. Решение систем линейных алгебраических уравнений большой размерности с матрицами коэффициентов частично регулярной структуры // Вестник Воронежского государственного технического университета. - 2014. - Т. 10. №3-1.-С. 32-36.

44. Свидетельство о государственной регистрации программы для ЭВМ ECCBI plug-in № 2014618783 / C.B. Тюрин, М.В. Рожков дата государственной регистрации в реестре программ для ЭВМ 28.08.2013 .

45. Способ повышения надежности микроЭВМ: пат. 2530325 Рос. Федерация: МПК G06F11/10 / М.В. Рожков, C.B. Тюрин; заявитель и патентообладатель ГОВПО "Воронежский государственный технический университет". — №2012116018; заявл. 19.04.2012 опубл. 10.10.2014 Бюл. №28 Решение о выдаче патента от 21.05.2014.

46. Печинкин А. В., Френкель С. Л. Вероятностный анализ времени прояв-

ления неисправности в сети автоматов // Информ. и её примен.. - 2009. - 3:2. - С. 2-14.

47. ГОСТ 27.002-89 Надёжность в технике , 1989, 39с.

48. Yu J. Efficient Software Checking for Fault Tolerence. DISSERTATION / Jing Yu. - University of Illinois at Urbana-Champaign, 2008. - 132c.

49. Арсеньев Ю., Журавлев В. Проектирование систем логического управления на микропроцессорных средствах / Ю.Н. Арсеньев., В.М. Журавлев. - М. Высшая школа, 1991. - 319с.

50. Ахо А. Компиляторы: принципы, технологии, инструментарий / А. Ахо, М. Лам, Р. Сети, Д. Ульман. - М. Вильяме, 2008. - 1184с.

51. Базовый блок. Материал из Википедии — свободной энциклопедии, 2014, http://ш.wikipedia.org/wiki/Бaзoвый_блoк

52. GCC internals. Control Flow Graph, 2014, http://gcc.gnu.org/onlinedocs/gccint/Control-Flow.html

53. LLVM Language Reference Manual,, http://llvm.org/docs/LangRef.html

54. Lattner C., Lenharth A., Adve V. Making context-sensitive points-to analysis with heap cloning practical for the real world // Proc. of the 2007 ACM SIGPLAN conf. on Programming language design and implementation. - 2007. - PLDI '07. - C. 278289.

55. What is this AT&T syntax,, http://asm.sourceforge.net/howto/gas.html

56. MicroBlaze Processor Reference Guide , 2009, c.

57. Intel 64 and IA-32 Architectures Software Developer's Manual (в пяти томах) vol. 2a&b. Instruction Set Reference A-Z, 2011, 1643c.

58. Mukherjee S. Architecture Design For Soft Errors / S. Mukherjee. - Morgan Kaufmann Publisher, 2008. - 360c.

59. Fault injection, 2014, https://en.wikipedia.org/wiki/Fault_injection

60. Kanawati G. A., Kanawati N. A., Abraham J. A. FERRARI: A tool for the validation of system dependability properties // Fault-Tolerant Computing. - IEEE, 1992.- C. 336-344.

61. Hsueh M. С., Tsai Т. К., Iyer R. К. Fault injection techniques and tools // Computer. - 1997. - V. 30 Iss. 4. - C. 75-82.

62. Rajabzadeh A., Vosoughifar M. A Dependable Microcontroller-based Embedded System // The Fourth International Conference on Dependability. -Nice/Saint Laurent du Var, France: IARIA, 2011. - C. 24-29.

63. Стефанюк В.JI. Детерминированные цепи Маркова // Информационные процессы. - 2011. - Том 11, No 4. - С. 423-427.

64. Moore Е. F. Gedanken-experiments on sequential machines // Automata studies.. - 1956. - V. 34. - C. 129-153.

65. Асафьев Ю. Липаев В. Технология проектирования комплексов программ АСУ / Ю. В. Асафьев, В. В. Липаев. - Радио и связь, 1983. - 261с.

66. Конструирование аппаратуры на БИС и СБИС / В. Ф. Борисов, [и др.]. -М. : Радио и связь, 1989. - 272с.

67. Кельберт М. Я., Сухов Ю. М. Вероятность и статистика в примерах и задачах. / М. Кильберт, Ю. Сухов. - М.: МЦНМО, 2010. - 560с.

68. Разработка аппаратно-программных средств оперативного обнаружения блужданий микроЭВМ по этапу 3: Отчёт о отчёт о НИОКР(промежуточ.) / ВГТУ: рук. Тюрин С. В.; исполн.: Рожков М.В. — Воронеж., 2011. 20с. — № ГР 01201164112. —Инв.№ 16..

69. Кнут Д. Искусство программирования. Том 1. Основные алгоритмы / . -Вильяме, 2007. - 720с.

70. Разработка аппаратно-программных средств оперативного обнаружения блужданий микроЭВМ по этапу 1 : Отчёт о отчёт о НИОКР(промежуточ.) / ВГТУ: рук. Тюрин С. В.; исполн.: Рожков М.В. — Воронеж., 2011. 28с. — № ГР 01201164112 . —Инв.№ 16..

71. Разработка аппаратно-программных средств оперативного обнаружения блужданий микроЭВМ по этапу 4: Отчёт о отчёт о НИОКР(заключ.) / ВГТУ: рук. Тюрин С. В.; исполн.: Рожков М.В. — Воронеж., 2012. 25с. — № ГР 01201164112 . —Инв. № 16..

72. Qemu open source processor emulator,, http://wiki.qemu.org/Main_Page

73. RFC 4627 - The application/json Media Type for JavaScript Object Notation (JSON), 2006, 10c.

74. Брайант Р.Э. Компьютерные системы: архитектура и программирование. Взгляд программиста / Э. Брайант, Д. О'Халларон. - БХВ-Петербург, 2005. -1186с.

75. Dongarra J., Luszczek P. Linpack benchmark // Encyclopedia of Parallel Computing. - 2011. - V.0. - С. 1033-1036.

76. TOP500 Lists,, http://www.top500.org/lists/

77. Richard Barrett, et al Templates for the solution of linear systems : building blocks for iterative methods / Richard Barrett, et al. - Philadelphia : SIAM, 1994. -107c.

78. Van der Vorst H. A. Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems // SIAM J. Sci. and Stat. Comput.. — 1992. - V.13 No 2. — C. 631-644.

79. Кормен Т. X. и др. Алгоритмы: построение и анализ / Т. Кормен, Ч.И. Лейзерсон, РЛ. Ривест, К. Штайн. - М.: Вильяме, 2006. - 1296с.

80. Левитин А. В. Алгоритмы: введение в разработку и анализ / . - М: Издательский дом Вильяме, 2006. - 575с.

81. Phoronix Test Suite - Linux Testing & Benchmarking Platform, Automated Testing, Open-Source Benchmarking,, http://www.phoronix-test-suite.com/

82. Разработка аппаратно-программных средств оперативного обнаружения блужданий микроЭВМ по этапу 2: Отчёт о отчёт о НИОКР(промежуточ.) / ВГТУ: рук. Тюрин С. В.; исполн.: Рожков М.В. — Воронеж., 2011. 41с. — № ГР 01201164112 . —Инв. № 16.

83. Разработка аппаратно-программных средств оперативного обнаружения блужданий микроЭВМ по этапу 1.1: Отчёт о отчёт о НИОКР(промежуточ.) / ВГТУ: рук. Тюрин С. В.; исполн.: Рожков М.В. — Воронеж., 2012. 16с. — No ГР 01201164112. — Инв. № 16..

84. Разработка аппаратно-программных средств оперативного обнаружения блужданий микроЭВМ по этапу 1.2: Отчёт о отчёт о НИОКР(промежуточ.) / ВГТУ: рук. Тюрин С. В.; исполн.: Рожков М.В. — Воронеж., 2012. 16с. —No ГР 01201164112. —Инв.№ 16..

85. Lattner С. LLVM // The Architecture of Open Source Applications. —2011. — vol.1.-C. 155-170.

86. Разработка аппаратно-программных средств оперативного обнаружения "блужданий" микроЭВМ» Подэтап № 2.1 этапа №2: Отчёт о отчёт о НИОКР(промежуточ.) / ВГТУ: рук. Тюрин С.В.; исполн.: Рожков М.В. — Воронеж., 2013.19с. — №ГР 01201269643. — Инв. № 21.

87. Gold_(Linker),, http://en.wikipedia.org/wiki/Gold_(linker)

88. Clang: а С language family frontend for LLVM,, http://clang.llvm.org/

89. Разработка аппаратно-программных средств оперативного обнаружения "блужданий" микроЭВМ» Подэтап № 3.2 этапа №3: Отчёт о отчёт о НИОКР(промежуточ.) / ВГТУ: рук. Тюрин С.В.; исполн.: Рожков М.В. — Воронеж., 2013.15с. —№ГР 01201269643. — Инв. №21.

90. Разработка аппаратно-программных средств оперативного обнаружения "блужданий" микроЭВМ» Подэтап № 3.1 этапа №3: Отчёт о отчёт о НИОКР(промежуточ.) / ВГТУ: рук. Тюрин С.В.; исполн.: Рожков М.В. — Воронеж., 2013.15с. —№ГР 01201269643. —Инв. №21.

91. Allen F. Е., Cocke J. A program data flow analysis procedure // Communications of the ACM. - 1976. -V. 19, № 3. - C. 137-147.

92. Разработка аппаратно-программных средств оперативного обнаружения "блужданий" микроЭВМ» Подэтап № 2.2 этапа №2: Отчёт о отчёт о НИОКР(промежуточ.) / ВГТУ: рук. Тюрин С.В.; исполн.: Рожков М.В. — Воронеж., 2013.14с. —№ГР 01201269643. — Инв. №21.

93. Calling convention,, http://en.wikipedia.org/wiki/Calling_convention

94. Linux Objdump Command Examples (Disassemble a Binary File), 2012, http://www.thegeekstuff.com/2012/09/objdump-examples/

95. Разработка аппаратно-программных средств оперативного обнаружения "блужданий" микроЭВМ» Подэтап № 4.2 этапа №4: Отчёт о отчёт о НИОКР(за-ключ.) / ВГТУ: рук. Тюрин C.B.; исполн.: Рожков М.В. — Воронеж., 2013. 15с. — № ГР 01201269643. — Инв. № 21.