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

На правах рукописи

РОЖКОВ Максим Владимирович

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ОПЕРАТИВНОГО ОБНАРУЖЕНИЯ ОШИБОК ПОТОКА УПРАВЛЕНИЯ НА ОСНОВЕ ОБРАБОТКИ ГРАФОВ БОЛЬШОЙ РАЗМЕРНОСТИ

Специальность: 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Воронеж - 2015

005560975

005560975

Работа выполнена в ФГБОУ ВПО «Воронежский государственный технический университет»

Научный руководитель Тюрин Сергей Владимирович,

кандидат технических наук, старший научный сотрудник,

ФГБОУ ВПО «Воронежский государственный технический университет», профессор кафедры «Автоматизированные и

вычислительные системы»

Официальные оппоненты: Егоров Сергей Иванович, доктор технических

наук, доцент, ФГБОУ ВПО «Юго-Западный государственный университет», профессор кафедры «Вычислительная техника»;

Каладзе Владимир Александрович, доктор технических наук, старший научный сотрудник, НОУ ВПО «Международный институт компьютерных технологий», профессор-исследователь кафедры «Информатика и вычислительной техника».

Ведущая организация ФГБОУ ВПО «Воронежский

государственный университет»

Защита состоится 02 марта 2015 г. в 1300 в конференц-зале на заседании диссертационного совета Д 212.037.01 ФГБОУ ВПО «Воронежский государственный технический университет» по адресу: 394026, г. Воронеж, Московский просп., 14.

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

Автореферат разослан «29» декабря 2014 г.

Ученый секретарь

диссертационного совета . Барабанов Владимир Федорович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2

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

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

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

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

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

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

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на одной международной и двух всероссийских

3

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

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

Публикации. По результатам исследования опубликовано 9 научных работ, в том числе 3 - в изданиях, рекомендованных ВАК РФ, получены 2 патента на способ, 3 свидетельства на программы для электронных вычислительных машин. В работах, опубликованных в соавторстве и приведенных в конце автореферата, личный вклад соискателя состоит: [5, 6] — в разработке программ для построения и исследования графовых моделей и имитационного моделирования процесса выполнения программ после возникновения ошибок потока управления; [1, 4, 8] — в разработке способов формирования и размещения операций проверки для обеспечения оперативного обнаружения ошибок потока управления; [7] — в разработке плагина к компоновщику объектных файлов.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе проведено обоснование возможности исследования оперативности обнаружения ошибок потока управления на основе графовых моделей программ. Рассмотрены основные понятия, применяемые в программных средствах обнаружения CFE: граф потока управления (англ. Control-Flow Graph или CFG), узлами которого являются базовые блоки; детализированный граф потока управления (англ. detailed Control-Flow Graph или dCFG), узлами которого являются инструкции программы; а также виды CFE и основные типы инструкций микропроцессора, значимые с точки зрения обнаружения CFE. Предложен новый формат представления программы в виде расширенного графа потока управления (англ. extended Control-Flow Graph или eCFG), ориентированный на использование при разработке и исследовании средств обна-

ружения CFE для программ под микропроцессоры с переменной длиной инструкций (использовался в способе повышения надежности микроЭВМ [4]). Данное представление отличается от dCFG тем, что узлы eCFG представляют собой все возможные начала инструкций в сегменте кода программы, а связи образуют все возможные маршруты выполнения, которые могут возникнуть при произвольной интерпретации содержимого сегмента кода как инструкций. Проанализированы два наиболее эффективных программных метода обнаружения CFE: CEDA и CFCSS (англ. Control-Flow Checking by Software Signatures) without aliasing. В результате выявлена возможность повышения оперативности построенных по методу CEDA средств обнаружения CFE за счёт целенаправленного размещения операций проверки.

Проанализированы известные способы исследования задержки программных средств обнаружения CFE, основанные на внесении CFE в запущенную на эмуляторе программу и анализе её дальнейшего выполнения. Выявлен ряд их недостатков: 1) невозможность за допустимое время исследовать процесс выполнения программы для каждой из возможных CFE; 2) невозможность предварительного оценивания задержки из-за использования в экспериментах тестовых программ, со встроенными средствами обнаружения CFE; 3) использование различных моделей ошибок в существующих системах внесения ошибок приводит к сложности сопоставления результатов, полученных разными системами. Выявлены предпосылки для нового способа исследования задержки программных средств обнаружения CFE, основанного на сводимости процесса выполнения программы после возникновения CFE к Марковским процессам, при его рассмотрении с позиции переходов между узлами eCFG и замене детерминированных переходов между узлами на частоты переходов. При этом для вычисления среднего количества переходов между заданными узлами eCFG возможно использовать известное из теории цепей Маркова соотношение для средних времён достижения одной из подмножества А вершины графа:

kf=0, ViGA

jgA

А А

где к, — математическое ожидание случайной величины H , являющейся моментом первого достижения одной из вершин из множества А ; р^ — элемент переходной матрицы Р , равный вероятности перехода из состояния i в состояние j, который для решения данной задачи заменяется на частоту перехода.

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

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

представлена на рис. 1. Входными данными является еСИв (позволяет учитывать все возможные маршруты выполнения программы) с частотами Ц, переходов между узлами. На выходе в результате решения системы линейных алгебраических уравнений (СЛАУ) (1) получается вектор кА , элементы которого для ¡е1„: пе[1;ш-1] представляют собой среднее количество инструкций, исполняемых до достижения состояния а при совершении ошибочного перехода в состояние 1. Средняя задержка обнаружения СРЕ рассчитывается как среднее арифметическое значений к<А для ¡£10- Состояние аеА, представляющее собой обработчик СРЕ, добавляется при преобразовании еСРО с учётом ис-

Рис. 1. Схема алгоритма построения и анализа графовых моделей В случае построения на предпоследним шаге алгоритма (см. схему рис. 1) СЛАУ не по соотношению (1), а по другому известному из теории цепей Маркова соотношению (2), результатом будут, вместо кА , доля ЬА ошибочных переходов, для которых достижимо состояние а .

Ь,А=1, 1€А

)е1

На рис. 2 приведён пример еСРО для тестовой программы под микропроцессор с фиксированной длинной инструкций. Частоты переходов получены из статистики переходов, определяемой при многократном прогоне программы с различными входными данными. Программа состоит из двух функций М) и Й11.

Рис. 2. еСРв тестовой программы 6

На рис. 3 приведена графовая модель для тестовой программы с рис. 2 со встроенными средствами обнаружения ошибочных переходов между функциями. Средства обнаружения СРЕ представлены операциями проверки — состояниями 14, 15, 20, 21 в множестве Ь и состояниями 25, 26, 31, 32 в множестве Ь. При этом множество 1| задаёт поведение операций проверки в случае срабатывания средств обнаружения СРЕ, что представлено связями из состояний 14 и 20 в состояния 15 и 21, откуда уже имеются связи в а, а множество Ь — в случае несрабатывания средств обнаружения СРЕ, что представлено связями из состояний 25 и 31 в состояния, представляющие следующие за операцией проверки инструкции (27 и 33). Связи из 1(, в Ь или Ь задают, при каких ошибочных переходах исследуемые средства обнаружения СРЕ срабатывают, а для каких — нет. В данном примере ошибочные переходы внутри одной функции представлены связями в 12, а между функциями — в I,. Частоты всех переходов из состояний первой и второй функций равны а и Ь соответственно.

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

7

К

((7У

© <

< © % \ )

© Щ-

1© 1

г®- щ

© % *,

®

© ;

Рис. 3. Графовая модель выполнения программы после возникновения СРЕ

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

В третьей главе описан разработанный программный комплекс для построения и исследования больших графовых моделей выполнения программ после возникновения CFE. Программный комплекс состоит из трёх основных подсистем: подсистема построения и анализа графовых моделей «CFEstimates» (свидетельство о гос. регистрации [5]), подсистема имитационного моделирования «WalkingManager» (свидетельство о гос. регистрации [6]) и модифицированный автором эмулятор Qemu.

При разработке и реализации подсистемы CFEstimates для обрабоки графовых моделей большой размерности (107 узлов с 1012 связей), возникающих при их построении для широко применяемых тестовых программ из наборов spec2000 или Phoronix Test Suite, адаптированы для работы с матрицами с частично регулярной структурой, получаемыми при построении и анализе графовых моделей, разреженный строчный формат (англ. Compressed Row Storage или CRS) и процедура умножения этих матриц на вектор. Под частично регулярной структурой матриц в работе понимается наличие в матрице строк, содержащих большое количество элементов, равных между собой для непрерывных диапазонов столбцов (рис. 4), и несколько элементов с произвольными значениями.

О vi V1 vï о

I-Г.....r^'T........ "'"-'"Л-1

min ip max

Рис. 4. Строка матрицы с частично регулярной структурой Адаптация формата CRS заключается в том, что каждая строка Pj матрицы Р* задаётся одним, двумя или тремя компонентами следующих типов: Y — разреженные данные (CRS), S — данные произвольной структуры, повторяющиеся для нескольких строк матрицы, R — диапазонные значения (формула (3), рис. 5)). Какой компонентой задавать конкретные группы элементов строки матрицы решается в зависимости от схожести их структуры с типовой структурой для компонент Y, S и R.

Yj, если Y

Р*= Si5 если Y—OaS^O (3)

Ri5 если Yi=0ASi=0

где Pji - i-й элемент j-й строки матрицы Р* ;

Yj - i-й элемент компоненты разреженных данных Y строки] (4);

Si — i-й элемент вектора значений произвольной структуры S;

Ri - i-й элемент компоненты диапазонных значений R, задаётся как (5).

Y.Jdj, если i=Lj 1 0, иначе

где Ь - множество индексов ненулевых элементов У; <1, -]-й ненулевой элемент строки матрицы.

V,, для ^<¡<1,

о,

для min<i<t0U t,<i<max иначе

где

и - постоянные значения элементов строки матрицы на соответствующих диапазонах.

Сокращение операций при умножении матриц смежности графовых моделей на вектор (6) достигается за счёт однократного умножении повторяющихся строк матрицы на вектор, и учёта их частично регулярной структуры, хранимой в виде (3). Распараллеливание достигается за счёт одновременного

выполнения операций суммирования V, и операций Рис.5. Формат хранения

умножения Sj-Vj.

Р]-V=Y-V + S-V + R-V= X Y;v;+

i.Y,*0

k= Z S.V.+vvXV.+v

I i:Y, = 0AS^0

ttlo

16Z,

строк матрицы

X V( , если c=0

iez,

, если c= 1

(6)

где

Z, = (i: Y^OAS^Ojnft,,;!,

Z2=(i:Yi=OASi=Ojn([min;t0)u(t1; max]); с — переменная в поле объекта Functor, хранящего уникальную строку матрицы, устанавливается в 1 при первом подсчёте произведения и сбрасывается в 0 после умножения всей матрицы на вектор.

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

Предложен алгоритм вычисления достижимости одного узла графа из остальных, представленного в виде матрицы смежности с частично регулярной структурой, необходимый при реализации процесса анализа графовых моделей выполнения программ после возникновения CFE для обработки бесконечных циклов. Алгоритм (рис. 6) основывается на последовательном выполнения операции векторного логического И (7) между матрицей смежности графа Р* и вектором-столбцом V, содержащим единичные значения против строки матрицы, описывающей целевой узел а: (8). Номера единичных позиций вектора V по окончанию алгоритма соответствуют номерам узлов графа, из которых достижим узел а.

Сокращение количества операций достигается за счёт однократного выполнения операции И между повторяющимися строками матрицы и вектором. Распараллеливание достигается по аналогии с (6), за счёт одновременного выполнении операции И над элементами вектора V; и операций V,.

АлЬ=с

|А| ■ (7)

¡=1 " 1

где А — матрица, Ь и с - вектора, а С;, Ь- и а^еЛ —ихэлементы.

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

Разработанные и реализованные формат хранения матриц и алгоритм позволили применить численный метод бисопряжённых градиентов со стабилизацией решения СЛАУ (1) для анализа графовых моделей с размерностью в 107

Рис. 6. Схема алгоритма вычисления достижимости

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

Р*ЛУ=(УЛУМ8ЛУМЯЛУ)= V (У;ЛУ;)у

[т„= V (8,лУ;Му,л( V У;)Му2л( V V,)) , если с=0

V кУ,=0л$1«0 ¡ег, ¡ег.

т„ , если с = 1

(8)

Вспомогательная подсистема программного комплекса реализует

«\yalkingManager» разработанного автоматизированное проведение экспериментов имитационного моделирования по внесению ошибок потока управления в работающую программу и анализ её последующего выполнения, необходимые как для уточнения частот переходов после возникновения СРЕ в

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

В четвёртой главе для обоснования предложений по повышению оперативности построенных по методу CEDA средств обнаружения CFE с использованием разработанного программного комплекса производится построение, согласно разработанным во второй главе детализированным алгоритмам, графовых моделей для тестовых программ без специальных средств обнаружения CFE (модель builtin) и для тестовых программ со встроенными средствами обнаружения CFE по методу CEDA (модель CEDA). Дополнительно, тем же комплексом, производится имитационное моделирование выполнения после возникновения CFE тестовых программ без специальных средств обнаружения CFE после возникновения CFE. В качестве тестовых программ при этом из набора Phoronix Test Suite взяты пять, в которых преобладают инструкции, работающие с вещественными данными, и восемь, в которых преобладают инструкции, работающие с целочисленными данными. Результаты анализа графовых моделей приведены в таблице 1.

Таблица 1

Результаты анализа графовых моделей

программа size, v A к A

байт инстр. инстр. % инстр. инстр. %

bzip2 102833 1729 102909 3.6901 1804 1246 0.0677

SPg 925241 5154 2970 2.7710 5182 122 0.0153

grep 143253 213 902 3.9747 270 41 0.0028

gzip 86001 217 1784 0.9918 284 56 0.0154

tar 225941 126 538 4.3965 278 19 0.0294

vpxenc 440893 1116 7315 0.8846 1176 29 0.0081

x264 579781 466 2534 0.0852 520 99 0.0057

tachyon 117093 249 653 1.1858 408 15 0.0117

xmllint 39593 160 222 0.0583 354 10 0.0134

djpeg 194677 491 372 1.4037 494 30 0.0195

bullet 865365 1253 1450 1.5341 1342 29 0.0040

7z 866325 439 1241 0.1230 602 19 0.0040

openssl 1969113 4290 1936 0.1770 4930 49 0.0042

В таблице: size — размер программы до встраивания средств обнаружения CFE; Lbmax — максимальная длина пути до узла а в графе модели builtin, LCmn — в графе модели CEDA; kblultinA — средняя задержка обнаружения для модели builtin, kCEDAA — для модели CEDA, l-hbuiIlill — доля пропускаемых CFE для модели builtin, l-hCEDAA —для модели CEDA.

По результатам кА и hA анализа графовых моделей выявлено что: 1)

значение задержки, которое обеспечивается встроенными средствами обнаружения CFE по методу CEDA, пропорционально исходному (без этих средств) уровню задержки; 2) добавление в eCFG дополнительных связей с узлом а при вставке операций проверки по методу CEDA не приводит к существенному сокращению длин путей в eCFG до узла а; 3) CFE, заключающиеся в переходах в инструкции вызовов функций, инструкции ветвления с косвенной адресацией и в инструкции циклов, а также в инструкции, лежащие в eCFG на путях во все такие инструкции, имеют большие задержки обнаружения ; 4) встроенные средства обнаружения CFE по методу CEDA в программах для архитектур микропроцессоров с переменной длиной инструкций, допускают ситуации пропуска операций проверки, приводящие к тому, что CFE сможет обнаружиться не раньше достижения следующей операции проверки; 5) построенные по методу CEDA средства обнаружения CFE оставляют возможность зацикливания в результате CFE, что можно интерпретировать как пропуск CFE.

На основании выявленных особенностей выполнения программ после возникновения CFE выдвинута гипотеза, что при: 1) размещении операций проверки, таким образом, чтобы в dCFG не существовало путей длиннее заданной величины до узла а; 2) использовании операций проверки, содержащих вместо одной инструкции перехода в обработчик ошибки набор одинаковых инструкций минимальной длины, с тем же поведением; 3) размещении операций проверки в каждом цикле CFG, в начале всех функций и перед всеми инструкциями ветвления с косвенной адресацией, — должна сократится средняя задержка обнаружения CFE и зависимость уровня задержки после встраивания средств обнаружения CFE от исходного уровня задержки.

Результаты анализа графовых моделей для встроенных средств обнаружения CFE согласно гипотетическому методу ECCBI (англ. Enhance Control Checking by Basic block Insertion) (модель ECCBI), основанному на методе CEDA, но учитывающему предложенные усовершенствования в виде особого формирования операций проверки и их целенаправленного размещения в dCFG, представлены в таблице 2. Уровень вносимой избыточности по памяти «mem overhead» для каждой из тестовых программ выбирался не больше чем в модели CEDA; ^eccbiA — средняя задержка обнаружения для модели ECCBI; 1 - hECCBIА — доля пропускаемых CFE для модели ECCBI; Ll:ma4 — максимальная длина пути до узла а в графе модели ECCBI. Из результатов видно, что применение предложенных усовершенствований позволяет сократить задержку kECCBIA на 4060% для большинства протестированных программ, а также обеспечить задержку обнаружения CFE, практически не зависящую от исходных уровней задержки (см. результаты для тестовой программы bzip2), что подтверждает выдвинутую гипотезу.

Таблица 2

программа size, байт Lgmax -, инстр. W A KECCB1 . инстр. 1 hECCBI , % mem overhead, %

bzip2 102833 363 14 С 166

f?pg 925241 441 14 0 182

grep 143253 287 19 0 204

Kzip 86001 275 0 185

tar 225941 209 13 0 221

vpxenc 440893 443 11 0 160

x264 579781 547 0 163

tachyon 117093 487 10 0 174

xmllint 39593 448 10 0 201

djpeg 194677 308 14 0 147

bullet 865365 299 15 0 165

7z 866325 571 14 0 215

openssl 1969113 1216 13 0 184

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

ГУ'ЧтттГгТГ | I VTfTTVfVi l I Г 1'ГГТТ"Тyn I I I I 200 400 600 800 1,000 1.200 1,400 1,600 1,800

200 400 600 300

I I ' ' I I 1 1 Ч 1 1 1 I 1 I ч 1 1,000 1,200 1,400 1,600 1,80<

Рис. 7. Гистограмма распределения длин путей до операций проверки для модели CEDA (слева) и для модели ECCBI (справа) Таким образом, в четвёртой главе предложены и проверены посредством построения и анализа графовых моделей целесообразные пути усовершенствования построенных по методу CEDA средств обнаружения ошибок потока управления.

В пятой главе разработан на основе метода CEDA и комплекса проверенных предложений по повышению оперативности построенных согласно методу CEDA средств обнаружения CFE метод оперативного обнаружения ошибок

13

потока управления — ECCBI. Метод ECCBI работает с представлением программы в виде CFG. Для каждого узла выделяется множество узлов-приемников, т. е. узлов, в которые имеется связь из текущего узла, и множество узлов предшественников, т. е. узлов, из которых имеется связь в текущий узел. В методе ECCBI используется три вида операций проверки: операции проверки сигнатур (рис. 8, пара узлов Д'7 и N»), операции проверки инструкций условного перехода (рис. 9, пары узлов N3 Nn и Лч Л») и операции проверки инструкций ветвления с косвенной адресацией (рис. 10, пары узлов N} N%, TV4 М> и N$ Mo).

[000 ¡1 [0010]

©0101 ©0111

^brlid.V.^4

1 j ' Л' 1

00!0Й? N§©0011^

щЬп л'.ш g§ bri Л', g

У

001 ©0100

CFE з® шее

S emp s.ns.

©lilt

g Je Л', Щ

N,

[1001]

— MES(Af,H0'00]

— NES(iV,)=[01Ql]

— NES(iV~}=[0 110]

— NES(.V3)=[01 il]

Фрагмент dCFG с операциями проверки сигнатур

— NES(Afj)=[010i j

— NES(.V,)=[0110]

— NES(.V)=[0111]

ud2 | I I udî I llboonllll

1 [ООН] j ud2 j ud2 1 [01001 1

Рис. 9. Фрагмент dCFG с инструкциями условного перехода

îoi

[ООН]. crap rx, ,V.

© 1001

\ je y m

¡11© ! mollir 1 и<0 II

| [0110] 1 :| ud2 ||

[0101]

УШ- NES(,V,)=[1000] NES{,V,)=[1001] ГГТТТТП — NES(,Y,)=[i010] Щ— NES(.V)=(1011]

Рис. 10. Фрагмент dCFG с инструкциями ветвления с косвенной адресацией В методе ECCBI, как и в его прототипе — CEDA, применяется сигнатурный мониторинг. Для осуществления сигнатурного мониторинга каждому узлу CFG назначаются две сигнатуры, сигнатура узла (NS) и сигнатура выхода из узла (NES), и в каждый узел вставляется две сигнатурные инструкции хог (®): входная и выходная, приводящие значение регистра S, хранящего текущее значение сигнатуры, в равенство с NS и NES, соответственно, в случае коррект-

ного текущего значения 5 (NS и NES по своей сути являются ожидаемыми значениями сигнатурного регистра (Se) на конкретном участке базового блока). Сигнатуры NS уникальны для всех узлов, а сигнатуры NES уникальны для всех предшественников каждого из узлов. Кроме обеспечения равенства Se и 5 обеспечивается различие Se и 5 в любой точке программы при возникновении большинства межузловых CFE (т. е. заключающихся в переходе между различными узлами CFG). Вследствие чего, для проверки и целенаправленной реакции на CFE, используются особым образом размещённые в CFG операции проверки сигнатур, состоящие из двух узлов Л^ и Ntгар (рис. 8 узлы Ni и Ng). В jVSChk осуществляется передача управления в следующий узел Nt только в случае совпадения значений NSj и S, а в противном случае производится переход в узел Ntat>. Узел TVnap формируется из последовательности однобайтовых инструкций вызова исключительной ситуации (ud2) с суммарной длиной N больше максимальной длины инструкций в системе команд (патент [4]).

Схема алгоритма метода ECCBI представлена на рис. 11. На вход алгоритму поступает рабочая программа в виде графа потока управления Рраб, и два параметра Lc — целевое расстояние между операциями проверки сигнатур и N — количество инструкций ud2 в операциях проверки. На выходе алгоритма —

Рис. 11. Схема алгоритма метода ECCBI Размещение промежуточных узлов, по аналогии с методом CFCSS without aliasing, производится между узлами N и всеми их предшественниками, если узел N содержит больше одного предшественника, и хотя бы один из них содержит больше одного приемника. Подобная процедура применяется и для всех узлов с инструкциями вызова функций brlid (рис. 8, Ns и N6). Размещение операций проверки сигнатур в CFG происходит таким образом, чтобы: 1) в dCFG не существовало путей длиннее заданной величины до узлов из Nmp, 2) операция проверки находилась в каждом цикле CFG, в начале каждой функции и перед каждым узлом CFG, заканчивающимся инструкцией ветвления с косвенной адресацией.

Для средств обнаружения CFE, построенных согласно разработанному

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

Разработана программная реализация алгоритма метода ECCBI для процессоров архитектуры х86-64. В ней из-за отсутствия в системе команд данных процессоров инструкции хor с запретом модификации регистра флагов (такие инструкции имеются, например, в архитектурах ARM, MicroBlaze, PowerPC, SPARC), не осуществляется контроль правильности условных переходов и переходов с косвенной адресацией. Разработанная программная реализация представляет собой плагин (свидетельство о гос. регистрации [7]) к компоновщику объектных файлов, работающий в окружении компиляторной инфраструктуры LLVM. Посредством разработанного плагина в тестовую программу были встроены средства обнаружения CFE. Результаты проведённых программой WalkingManager экспериментов с этой тестовой программой представлены на рис. 12 справа (параметр Lc измеряется в количестве инструкций, длина которых обычно составляет несколько байт), а на рис. 12 слева приведена полученная из анализа графовых моделей ECCBI зависимость для той же тестовой программы средней задержки ( кЕССВ1Л ) от параметров: N и Lc.

26 24 22 20 18 16

]i 10 8 6

щ

W

0

4 ю15 4 1П1520

О 5 1и О 5 10

Рис. 12. Расчётная (слева) и фактическая (справа) задержки обнаружения СРЕ Из рисунка 12 видно, что результаты анализа графовых моделей хотя и не совпадают с полученными экспериментально, но имеют один порядок величин и схожую зависимость от параметров. В результате экспериментов с тестовой программой со встроенными средствами обнаружения СРЕ по методу ЕССВ1 также выявлено, что частота пропуска ошибок в результате возникновения внутриузловой СРЕ или зацикливания не превышает 1%. Уровень вносимой избыточности при средней задержке обнаружения в 2 — 26 инструкций по используемой памяти составляет от 274% до 120%, и от 30% до 10% — по

16

процессорному времени, в зависимости от сочетаний параметров. При этом избыточность средств обнаружения CFE, построенных согласно методу-прототипу CEDA, составляет: от 30% до 60% по памяти и от 5% до 58% по процессорному времени. Таким образом, можно заключить, что в пятой главе разработан и реализован метод оперативного обнаружения CFE, эффективность которого подтверждена экспериментально.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

Основные результаты диссертации опубликованы в следующих работах:

Публикации в изданиях, рекомендованных ВАК РФ

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

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

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

Патенты и свидетельства о регистрации программ для ЭВМ

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

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

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

26.08.2013.

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

28.08.2014.

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

Статьи и материалы конференций

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

18

Подписано в печать 23.12.2014 Формат 60x84/16. Бумага для множительных аппаратов. Усл. печ. л. 1,0. Тираж 80 экз. Заказ № 267 ФГБОУ ВПО «Воронежский государственный технический университет» 394026 Воронеж, Московский просп., 14