Содержание к диссертации
Введение
1 Обоснование возможности исследования оперативности обнаружения ошибок потока управления на основе графовых моделей программ 12
1.1 Общие принципы обнаружения ошибок потока управления встроенными в программу средствами 12
1.2 Особенности современных программных методов обнаружения ошибок потока управления 24
1.3 Обоснование возможности исследования оперативности на графовых моделях 29
1.4 Выводы и постановка задач исследования 39
2 Разработка алгоритмов построения графовых моделей выполнения программ после возникновения ошибок потока управления для исследования оперативности их обнаружения 42
2.1 Разработка обобщённого алгоритма построения и анализа графовых моделей выполнения программ после возникновения ошибок потока управления 42
2.2 Пример построения и анализа графовой модели выполнения программы после возникновения ошибок потока управления 57
2.3 Детализация алгоритма построения и анализа графовых моделей для средств обнаружения ошибок по методу CEDA 68
3 Разработка программного комплекса для построения и исследования больших графовых моделей выполнения программ после возникновения ошибок потока управления 75
3.1 Разработка подсистемы эмуляции на базе эмулятора Qemu 76
3.2 Разработка подсистемы построения и анализа графовых моделей 82
3.3 Разработка подсистемы имитационного моделирования 97
4 Обоснование предложений по повышению оперативности построенных по методу CEDA средств обнаружения ошибок потока управления
4.1 Построение и исследование графовых моделей для группы тестовых программ roPhoronix Test Suite 99
4.2 Предпосылки повышения оперативности обнаружения ошибок потока управления 111
4.3 Построение и исследование графовых моделей для преобразованных согласно усовершенствованному методу CEDA тестовых программ 115
5 Разработка и экспериментальное исследование метода оперативного обнаружения ошибок потока управления 122
5.1 Алгоритмизация метода оперативного обнаружения ошибок потока управления 122
5.2 Реализация метода оперативного обнаружения ошибок потока управления для процессоров архитектуры х86-64 134
5.3 Экспериментальное исследование разработанного метода оперативного обнаружения ошибок потока управления 145
Заключение 1
- Особенности современных программных методов обнаружения ошибок потока управления
- Пример построения и анализа графовой модели выполнения программы после возникновения ошибок потока управления
- Разработка подсистемы построения и анализа графовых моделей
- Предпосылки повышения оперативности обнаружения ошибок потока управления
Особенности современных программных методов обнаружения ошибок потока управления
Согласно [3] под ошибкой потока управления понимают расхождение в последовательности инструкций, исполняемых после возникновения сбоя, с рабочей последовательностью инструкций. Большинство известных методов обнаружения CFE реализуются за счёт контроля последовательности исполняемых инструкций посредством той или иной вариации сигнатурного мониторинга. В целом, сигнатурный мониторинг основывается на том, что предварительно (до выполнения программы) некоторым образом выделенным из программы непересекающимся множествам инструкций ставятся в соответствие уникальные числа (эталонные значения сигнатуры), а во время выполнения программы текущее значение сигнатуры постоянно специальным образом обновляется, чтобы при отсутствии CFE всегда соответствовать эталонному значению, а при возникновении CFE — всегда отличаться от него. При обеспечении указанных требований, для контроля последовательности исполняемых инструкций достаточно сравнивать текущее значение сигнатуры с эталонным и, при их несовпадении, сигнализировать об обнаружении CFE. Обычно, в качестве множеств инструкций, которым назначаются уникальные эталонные сигнатуры, выбирают уже существующие структурные единицы, из которых состоит программа на этапе компиляции, например, функции или базовые блоки.
В зависимости от уровня вычислительной системы, средствами которого реализуется обновление текущего значения сигнатуры и сравнение её с эталонным значением, методы обнаружения CFE разделяют на программные, аппаратные и гибридные. Программные методы обнаружения CFE обычно заключаются в реализации этих операций посредством встраивания в основной поток управления программы дополнительных инструкций, называемых в случае реализации операции обновления — следящие (англ. tracking), а в случае реализации операции сравнения — проверяющими (англ. checking) [20].
Процесс выполнения программы со средствами обнаружения CFE можно разделить во времени на три интервала (рисунок 1.1): (0; to), (to; to+k) и ( t0+k). На отрезке (0; to) программа находится в исправном состоянии, а средства обнаружения CFE, производя следящие операции, обновляют текущее значение сигнатуры. В момент времени to происходит возникновение CFE. На отрезке (to; to+k) в программе начинает выполняться последовательность инструкций, отличная от рабочей, при этом могут также исполняться инструкции проверяющих операций средств обнаружения CFE. В том случае, если одна из таких операций обнаруживает факт возникновения CFE, то в момент времени to+k управление передаётся в обработчик CFE, реализующий некоторую процедуру восстановления, которая работает на интервале to+k. Поскольку большинство программных средств обнаружения CFE проектируются таким образом, чтобы ошибка обнаруживалась при первом достижении операции проверки, под срабатыванием средств обнаружения CFE будем понимать переход в обработчик ошибки из этой операции проверки.
Задержка обнаружения 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, ... ,Nn, образующие множество V, графа потока управления P={V, Е} соответствуют базовым блокам, а рёбра Єї, ег, ..., еп, образующие множество Е, представляют возможные в программе переходы между базовыми блоками (рисунок 1.2). Определяют множество приемников узла N, succ(7V), состоящее из узлов, в которые можно непосредственно перейти из узла N, и множество предшественников узла N, pred(TV), состоящее из узлов, из которых можно непосредственно перейти в узел TV. На уровне представления программы в виде графа потока управления CFE можно представить как переход из N BTVJ В случае отсутствия в CFG программы ребра из TV; в TVj (на рисунке 1.2 CFE показана пунктирной линией из N2 в TVs). Но CFE может вполне заключатся и в переходе, представленном в CFG, например, в случае перехода из N3 в TVs при истинности условия if(cond2).
Пример построения и анализа графовой модели выполнения программы после возникновения ошибок потока управления
В качестве примера построим графовую модель выполнения программы после CFE для гипотетического метода сигнатурного мониторинга, в котором за непересекающееся множества инструкций взята функция, а операции проверки размещаются перед выходом из функции и срабатывают при попадании в них управления после ошибочного перехода между функциями. Допустим, что имеется программа для архитектуры микропроцессора с фиксированной длиной инструкций с частотами переходов в инструкциях ветвления.
На рисунке 2.11 проиллюстрирован шаг 2.А1 алгоритма 2.А — построение eCFG. Программа, представленная последовательностью инструкций для гипотетического процессора, приведённая в синтаксисе AT&T ассемблера [55], состоит из двух функций fhO и fhl. В столбце слева приведён адрес инструкции. Допустим, что fhO является главной функцией программы (т.е. ей передаётся управление при запуске программы, а по её завершению происходит завершение работы программы). Статистика переходов представлена на рисунке в виде файла «stat». В eCFG каждой инструкции соответствует один узел с соответствующим индексом: Пі для инструкции по адресу 1, п2 — для инструкции по адресу 2 и т.д.. Связи между узлами задают возможные переходы в программе между инструкциями. Над частью связей показаны частоты переходов, вычисленные по статистике переходов «stat». Для остальных связей вероятности переходов равны единице.
Переход от программы и статистики переходов к eCFG с частотами переходов Типы узлов Пь..п7 определяются согласно особенностям влияния на потока управления конкретной инструкции из архитектуры микропроцессора (см. параграф 1.1). Допустим, что инструкция jge осуществляет переход по указанному адресу, если значение регистра %г0 больше или равно значению на вершине стека, а в противном случае осуществляет переход к инструкции по следующему адресу. Тогда она будет относиться к типу Jcc. Инструкция call осуществляет вызов функции по указанному адресу, поэтому она будет относиться к типу brlid. Инструкция hit осуществляет завершение программы, поэтому она будет относиться к одноимённому типу hit. Инструкция add производит сложение операндов и передаёт управление инструкции по следующему адресу, поэтому она будет относиться к типу line. Инструкция inc инкрементирует значение указанного регистра и передаёт управление к инструкции, расположенной по следующему адресу, поэтому так же будет относиться к типу line. Инструкция jne аналогична инструкции jge, но производит проверку на равенство операндов, поэтому она так же будет относиться к типу Jcc. Инструкция rt производит возврат из функции, осуществляя переход в инструкцию, расположенную по адресу, следующему за адресом вызвавшей функцию инструкции, поэтому эта инструкция будет относиться к типу rt.
Таким образом, после исполнения шага 2.А1 алгоритма имеем eCFG с частотами переходов Ре={ Ve,Ee,Qe] 5 У гц п2 п3 п4 п5 п6 п7} Ее = (п1- п2,п1- Пз,п2- П4,П4- п5,п5- п6,п6- п5,п6- п7,п7- п3} , и множество частот переходов узлов eCFG Qe=((a)1:p1)2=0.6,p1)3=0.4},(a)6:p6)5=0.8,a)6)7=0.2}) (формируются только для узлов ветвления, поскольку для остальных узлов детерминированные ру=1 переходы в единственный приемник j узла і уже определены множеством связей Ее. Нулевые значения ру в ШІ не представлены).
Шаг 2.А2 алгоритма — добавление средств обнаружения CFE — проиллюстрирован на рисунке 2.12. Добавленные узлы и связи обозначены пунктирными линиями. Для упрощения модели, в данном примере следящие операции средств обнаружения CFE не представлены, но предполагается, что корректное значение сигнатуры выставляется при вызове функции, т. е. при переходе из узла п2 в узел п4, и при возврате из функции, т. е. при переходе из узла п7 в узел п8. Операции проверки же представлены парами узлов п8, п9 и Пю, Пи. Узел а представляет первую инструкцию обработчика CFE. Первые узлы операции проверки (щ и Пю) проверяют корректность текущего значения сигнатуры и, в случае его корректности, передают управления следующему узлу программы, а в случае ошибки — узлу типа udl (п9 и Пц), который осуществляет переход в обработчик CFE — узел a . При построении модели примем, что узлы щ и Пю относятся к специальному типу t стр. Для них не заданы частоты переходов, т. к. они будут особым образом представлены в модели, без их учёта.
Добавление в eCFG модели средств обнаружения CFE На рисунке 2.13 проиллюстрированы шаги 2.АЗ-2.А5 алгоритма. Состояния цепи Маркова построены на шаге 2.A3 на основе eCFG, полученного по завершению шага 2.А2 (рисунок 2.12). В данном случае все узлы eCFG, кроме а , представлены в цепи Маркова в трёх экземплярах и распределены по множествам Іо, її, Ь. Множество 1о содержит состояния, соответствующие начальным узлам ошибочного перехода, лежащего в основе CFE. Множество її определяет поведение программы в случае срабатывания средств обнаружения CFE, а множество Ь — в случае несрабатывания. Номера состояний цепи Маркова внутри множества 1о присваиваются в соответствии с порядком, в котором должны располагаться в памяти инструкции программы (изначально присутствующие и добавленные в соответствии с методом обнаружения CFE). Нумерация состояний в каждом из последующих множеств состояний, її и Ь, продолжает нумерацию состояний из 1о, но также соответствует порядку расположения инструкций в памяти. -(26 н-і
Переход от eCFG к цепи Маркова Модель ошибок, заданная на шаге 2.А4, представлена связями из состояний множества 1о. Показаны только связи для первых состояний в функциях fnO и fill, для остальных инструкций функций они совпадают с первыми. В данном примере используется равномерная модель ошибок (2.12), что представлено связями между состояниями из 1о с равными вероятностями переходов в состояния из її и Ь. При этом связи идут в экземпляры состояний из множества її, в случае если начальный и конечный узлы принадлежат одной функции, а в противном случае — в Ь.
Связи (и соответственно вероятностные меры) ДЛЯ СОСТОЯНИЙ ИЗ її и 12 заданы на шаге 2.А5 алгоритма, согласно формулам (2.1)-(2.7). Видно, что для части состояний структура связей и вероятностей переходов сохранена по сравнению с eCFG. Тогда как для узлов ng и Пю состояния из її и Ь имеют отличную структуру связей: у состояний 14 и 20 из її имеются связи в состояния, непосредственно ведущие в а , а у состояний 25 и 31 имеются связи в состояния, представляющие следующую инструкцию программы в соответствующем множестве (її или 12). Именно для того, чтобы представить различное поведение инструкций проверяющих операций в случае обнаружения и в случае пропуска CFE, были созданы эти два множества состояний.
Разработка подсистемы построения и анализа графовых моделей
Далее предлагается основанный на идее алгоритмов Флойда — Уоршелла и Дейкстры упрощённый алгоритм (рисунок 3.6), производящий вычисление достижимости только одного заданного узла направленного графа из всех остальных с асимптотической сложностью 0(п2), не требующий модификации исходной матрицы и хорошо поддающийся распараллеливанию. Алгоритм вычисления достижимости основывается на последовательном выполнении операции векторного логического И между матрицей смежности графа и вектором. Эта операция задаётся схожим образом с операцией векторного произведения матрицы на вектор (3.8). Результатом работы алгоритма так же является вектор, который, по аналогии с матрицей достижимости, будем называть вектором достижимости.
Для сокращения количества операций в алгоритме целесообразно при выполнении операции векторного И прекратить повторение операции логического И (формула 3.8), если для текущего j выражение а Abj приняло единичное значение. В случае же умножения строки матрицы с частично регулярной структурой на вектор, при её задании компонентой R, вычисление операции векторного И можно реализовать простой проверкой попадания ненулевых значений вектора в ненулевые диапазоны R.
Логическое И между матрицей и вектором в случае матрицы с частично регулярной структурой производится согласно (3.9). Распараллеливание достигается по аналогии с (3.7) за счёт одновременного выполнения операции ИЛИ над элементами вектора V; и операций S; Л Схема алгоритма вычисления достижимости Для поддержки работы алгоритма не с матрицей смежности графа, а с матрицей коэффициентов СЛАУ (1.2), примем (3.10),(3.11), поскольку её элементы (кроме стоящих на главной диагонали) принимают ненулевые значения при ненулевой вероятности перехода, т.е. при наличии связи в eCFG.
При большой разветвлённости eCFG полезной оптимизацией также будет прямая замена на единицу повторного вычисления произведения вектора V на строки матрицы, против которых в векторе V уже стоит единица. Пример работы алгоритма приведён на рисунке 3.7. Для упрощения в качестве значений элементов матрицы Р взяты только нули и единицы. Узел ее 5 достижимость которого находится, описывается последней, пятой строкой матрицы Р . vO — начальное значение вектора V. vi — значение вектора V на і-й итерации цикла алгоритма. v3 — вектор достижимости. Поскольку v3[4]=0, из состояния 4 недостижимо состояние ее.
Пример работы алгоритма вычисления достижимости узла Достоинствами приведённого алгоритма при его асимптотической сложности 0(п2) являются: возможность его простого применения не к матрице смежности eCFG, а сразу к матрице коэффициентов СЛАУ с частично регулярной структурой, его хорошая распараллеливаемость и возможность сокращения числа операций для матриц с частично регулярной структурой, получаемых при анализе графовых моделей [43].
Модули графовых моделей методов обнаружения CFE подсистемы построения и анализа графовых моделей (на рисунке 3.3 - «Модель X») реализуют специфичный для этих методов функционал. Тем не менее, все они имеют схожий вид: представляют собой класс с публичными методом buildAndRun() и набором методов-сеттеров setXxxQ, и приватными методами applyNameOfMethod(), insertTrap(), insertXxx(), fillMatrixForSTx() и cleanLoops().
Методы setXxx() обычно предназначены для установки различных параметров метода обнаружения CFE. Метод buildAndRun() осуществляет построение и анализ графовой модели и возвращает его результаты. Метод applyNameOfMethod() вызывается из buildAndRun() и осуществляет эквивалентное преобразование eCFG согласно методу обнаружения CFE NameOfMethod. Метод insertTrap() осуществляет размещение операции проверки в eCFG и поэтому имеется практически в любой модели. Он вызывается из applyNameOfMethod(). Методы insertXxx() являются специфичными для моделей и осуществляют размещение в eCFG операции Ххх, например, метод insertNES() осуществляет размещение выходной сигнатурной инструкции в модели для метода CEDA. Методы fillMatrixForSTx() осуществляют заполнение части 1х хє[0 ;m— 1] (см. алгоритм 2.А) матрицы графовой модели, а метод cleanLoops(), проведя свойственную методу подготовку eCFG, передаёт управление в модуль Loops для обработки бесконечных циклов в eCFG. Таким образом, общий алгоритм для buildAndRun() любого модуля «Модель X» представлен в З.Е. Алгоритм З.Е (Построение и анализ графовых моделей): Функция buildAndRim() имеет доступ к eCFG программы Ре. З.Е1. [Преобразование eCFG]
Подсистема имитационного моделирования WalkingManager позволяет: производить заданное количество экспериментов внесения в выполняемую программу ошибок потока управления; получать информацию для каждого из экспериментов о причине завершения программы, количестве инструкций, исполненных между возникновением CFE и завершением программы; строить граф потока управления для процесса выполнения программы после CFE и сохранять полученную информацию для последующего статистического анализа.
Структура подсистемы имитационного моделирования Модуль управления серией экспериментов формирует параметры каждого эксперимента в зависимости от задания, полученного из GUI/CLI, например: задаёт количество инструкций до внесения эмулятором CFE, задаёт адрес ошибочного перехода в соответствии с моделью ошибок. По завершении эксперимента модуль обеспечивает получение и передачу в модуль формирования статистики результатов эксперимента в виде графа последовательности вызова функций после внесения CFE, число инструкций от момента внесения CFE и до момента остановки процесса моделирования и причины завершения эмулируемой программы. Модуль формирования статистики, в свою очередь, сохраняет эти результаты для последующего формирования краткой сводки результатов экспериментов и вывода всех результатов экспериментов в файл imit.res для обработки специализированными программами. Модуль визуализации предназначен для формирования графического представления в виде формате .dot графа вызовов функций в процессе выполнения программы после внесения CFE, полученного в последнем эксперименте.
Предпосылки повышения оперативности обнаружения ошибок потока управления
Для исследования построены две группы моделей согласно детализированным алгоритмам из параграфа 2.3: для тестовых программ без специальных средств обнаружения CFE (работают только встроенные средств самоконтроля микропроцессора архитектуры х86-64 [70]) (далее — модель builtin) и для тестовых программ со встроенными средствами обнаружения CFE по методу CEDA (далее — модель CEDA). Каждая из групп состоит из набора моделей для тестовых программ из открытого комплекса тестов Phoronix Test Suite v4.8.3 [81]. Среди выбранных тестовых программ присутствуют пять, в которых преобладают инструкции, работающие с вещественными данными: tachyon, djpeg, vpxenc, х264 и bullet, и восемь, в которых преобладают инструкции, работающие с целочисленными данными: xmllint, bzip2, gzip, grep, tar, 7z, gpg, openssl. В каждую группу тестовые программы выбирались таким образом, чтобы размеры сегмента кода в исполняемом файле программы попадали в различные части допустимого (программным комплексом) диапазона для построения графовой модели (от 1000 до 4-Ю6 байт). исполнения инструкций не из сегмента кода программы. В случае имитационного моделирования — при выходе за сегмент кода сигнализировалось обнаружение CFE, а при построении графовых моделей все переходы за пределы сегмента кода заменялись на переходы в состояние а.
Профиль имитационного моделирования состоял из 10000 экспериментов. Диапазон [500; 50000] инструкций разбивался на 100 равных поддиапазонов, на каждом из которых выбиралось случайное число, которое означало момент от начала выполнения программы, в который происходило внесение CFE. Нижняя граница выбрана равной 500 из соображений, что к этому моменту уже выполнены все инициализирующие процедуры в исследуемой программе и она перешла к исполнению основного цикла инструкций. Верхняя граница выбрана равной 50000, т. к. все тестовые программы выполняются до завершения, по крайней мере, 50000 инструкций. Далее для каждого из 100 моментов внесения CFE выбирались адреса ошибочных переходов, лежащих в основе CFE. Для этого сегмент кода, располагающийся в диапазоне памяти [addrmin; addrmax], разбивался также на 100 равных поддиапазонов, на каждом из которых выбирался случайным образом адрес ошибочного перехода. Таким образом, получились 100 групп экспериментов для различных начальных моментов возникновения ошибок по 100 экспериментов для различных адресов ошибочных переходов в каждом. Максимальное количество инструкций, после которого программа считается зациклившейся (maxinstr), принято равным 1-Ю6.
В таблице 4.1 представлены сводные результаты имитационного моделирования и анализа графовых моделей. Столбец size содержит размер сегмента кода программы. Столбец UD2 — содержит количество недопустимых в системе команд инструкций плюс количество инструкций, ведущих за пределы сегмента кода. Столбец avg. ki содержит среднее количество инструкций до обнаружения CFE, полученное при имитационном моделировании. Столбец kbUiitinA содержит среднее количество инструкций до обнаружения CFE, полученное из анализа графовых моделей builtin. В столбце l-hbuiltinA приведены доли пропускаемых CFE. В столбце UD20TH. приведён процент инструкций типа UD2 по отношению к инструкциям всех остальных типов. В столбце Lbmax максимальное значение длины пути L в eCFG до состояния
Из рисунка видно, что значения, полученные из анализа графовых моделей, хотя и не совпадают со значениями из имитационного моделирования, но имеют с ними один порядок величин и схожую зависимость. Вклад в подобное расхождение внесён как допущениями при построении графовых моделей и небольшим размером выборки ошибочных переходов из всех возможных при имитационном моделировании, так и величиной maxinstr, определяющей, через сколько инструкций останавливается имитационное моделирование в случае зацикливания исследуемой программы.
Среднее время обнаружения CFE и максимальный путь до а Кроме количественных особенностей процесса выполнения программы после CFE, из моделей выделен так же ряд качественных. Из имитационного моделирования выявлено, что если после возникновения CFE происходит вызов функции посредством инструкций с непосредственной адресацией, то эта функция будет выполнена нормально, с точки зрения маршрута в eCFG. Это приводит к увеличению задержки обнаружения CFE, особенно, если вызванная функция производит дальнейшие вызовы функции. Пример визуализации процесса выполнения программы после CFE в описанной ситуации представлен на рисунке 4.3, на котором изображён граф вызовов функций после возникновения CFE. Из рисунка видно, что после CFE (переход показан фиолетовым), совершается вызов функции, после которого нормально происходят вызовы других функций и возвраты из них [82]. segment segment Рисунок 4.3 — Граф вызовов функций после возникновения CFE Приведённое предположение относительно инструкций вызова функций с непосредственной адресацией подтверждается результатами анализа графовых моделей. В таблице 4.2 приведён фрагмент файла с результатами анализа графовой модели. Формат результатов описан ранее в параграфе 3.2. Столбец kbUiitinA содержит средние времена достижения целевого состояния а, обозначающего обнаружение CFE. Из таблицы видно, что для инструкции типа brlid (относится к типу brlid) по адресу 0x402d64 kbuiltinA принимает значение 11629, что существенно превышает значения kbuMnA для последующих инструкций. Но более важным здесь является не это, а то, что большое значение kbUiitinA «распространяется» на большую часть предыдущих инструкций, т.к. их тип line и управление после их исполнения переходит к инструкции, расположенной по адресу равному addr+size.
Вторая группа экспериментов проводилась для тестовых программ со встроенными по методу CEDA средствами обнаружения CFE. Эксперименты направлены на выявление достигнутого уровня для метода CEDA по показателю задержки обнаружения CFE, а также на выявление дальнейших возможностей для сокращения задержки. Ввиду отсутствия общедоступной реализации метода CEDA, его исследование проводится только с помощью анализа графовых моделей. Детализированный алгоритм построения и анализа графовых моделей для построенных по методу CEDA средств обнаружения CFE приведён в параграфе 2.3.
CFE для большинства тестовых программ обеспечивает достаточно низкую задержку обнаружения CFE, равную 10-122 инструкции, при уровнях вносимой избыточности по памяти 148-221%. Но существуют ситуации, как, например, в случае с тестовой программой bzip2, когда уровень задержки достигает 1550 инструкций. При этом, как показано на рисунке 4.4, наблюдаемые значения сокращения задержки (avg. Км отн.) относительно программы без встроенных средств обнаружения CFE по методу CEDA для этой ситуации — того же порядка (0,5-8%), что и для остальных тестовых программ. Таким образом, построенные по методу CEDA средства обнаружения CFE обеспечивают достаточно стабильную относительную эффективность по показателю «задержка», но для программ со структурой eCFG, способствующей повышению длительности выполнения программы после возникновения CFE, задержка по абсолютному значению может принимать большие величины. целевого расстояния между операциями (Lc) проверки метода CEDA для тестовой программы bzip2 (для которой получено максимальное значение задержки среди протестированных программ). Диапазон изменения параметра Lc выбран исходя из отсутствия существенного изменения показателя size2 за пределами выбранного диапазона. Из приведённой зависимости видно, что применение метода CEDA к тестовой программе bzip2 приводит к возможности обнаружения CFE в среднем за несколько тысяч инструкций не только для одного значения параметра Lc (в эксперименте из предыдущей серии — таблица 4.3), но и для всего диапазона изменения параметра Lc. При этом также видно, что имеется немонотонная зависимость kCEDAA от Lc, что подтверждает гипотезу о существовании более удачных и менее удачных вариантов расположения
Интерес также представляет отсутствие уменьшения показателя LCmax — максимальной длины пути до узла а — по отношению к группе моделей для тестовых программ без встроенных средств обнаружения CFE по методу CEDA (см. таблицы 4.1 и 4.3) при увеличении количества ведущих в а связей, возникающих из-за размещения операций проверки с инструкциями ud2 в методе CEDA (см. столбы UD2 в таблицах). На рисунке 4.6 представлены гистограммы распределения величины L в модели builtin (слева) и модели CEDA (справа), а в таблице 4.4 — показатели этих распределений. Из гистограмм видно, что и форма распределения практически не изменилась. Математическое ожидание и максимумы тоже остались тех же порядков. Таким образом, можно заключить, что применение метода CEDA практически не сокращает ни среднюю длину путей, ни количество длинных путей в eCFG.
