Считается, что программа как способ представления алгоритма инвариантна формам своего представления. Однако в ходе кодирования возможно внесение непреднамеренных ошибок на каждой стадии жизненного цикла создания программы. Нельзя полностью гарантировать, что в текст программы не будут внесены так называемые “закладки”, направленные на разрушение операционной среды, в которой запущена программа. В соответствии моделями жизненного цикла программ переход от одного уровня абстракции представления исходного алгоритма (или спецификации) к следующему подразумевает такие технологические действия, как тестирование и верификация. Причем в настоящее время верификации уделяется все большее внимание, поскольку этот метод контроля позволяет при меньших временных затратах получать результаты имеющие большую ценность.
Исполняемый код (ИК) и как цель любой программной разработки, и как продукт одного из этапов жизненного цикла программного обеспечения должен проходить те же процедуры контроля (тестирование и верификация), что и алгоритмы, полученные в результате обработки спецификации, и тексты программ, полученные как результат кодирования алгоритмов.
Существует широко распространенное представление программы в виде графа, основанное на понятии "состояние программы". Под состоянием программы понимают содержимое регистров процессора и ячеек памяти (переменных) на некоторый зафиксированный момент. Такое состояние программы ассоциируют с вершиной графа (функциональная вершина), а переходы между ними отображают дугами. Однако такое представление программы отражает скорее состояние аппаратуры, выполняющей ее, и может быть использовано для отладки программы, но не для ее анализа.
В данной работе предлагается метод построения графового представления ИК, ориентированное не столько на отладку программ, сколько на их анализ (обратное проектирование).
Исполняемый код состоит из последовательности машинных команд конкретного процессора. Все команды данного процессора можно разделить на две категории: команды обработки данных (команды пересылки, арифметические команды, команды сдвигов, команды обработки десятичных данных и т.д.) и команды управления последовательностью исполнения (безусловные и условные переходы, команды вызова процедур и команды возврата). С точки зрения выполнения программы, действия процессора по обработке последовательности команд обработки данных – линейный участок – строго детерминированы: команды выполняются одна за другой. Для линейной программы в этом смысле можно выделить всего два состояния: точку запуска и точку останова. Аналогично можно сказать, что любой линейный участок ИК выполняется либо до точки останова программы, либо до команды управления последовательностью команд (КУПК). Точки запуска, останова и КУПК будем называть точками принятия решения.
Определение: функциональная программа – это ИК, решающий некоторую задачу, полученный для конкретного типа процессора и определенной операционной системы. Выполнение функциональной программы (ФП) не зависит от других программ, т.е. ФП не является драйвером и не включает в себя обработчики прерываний.
При построении программы определяется точка входа – адрес первой выполняемой команды. Выход из ФП (завершение работы) может быть реализован произвольным количеством операторов возврата, вызовов функций exit(), abort(), использованием механизма исключительных ситуаций. Таким образом, можно говорить о некотором множестве (конечном) точек выхода из программы.
ФП может быть представлена в виде ориентированного графа, вершинами которого будут: точка входа в ФП; множество точек выхода; команды передачи управления, не являющиеся элементами множество точек выхода. С каждой вершиной ассоциируется структура, хранящая адрес этого узла, и адрес перехода из этого узла (если адрес перехода существует).
Дугам этого графа соответствуют линейные участки программы, состоящие из команд обработки данных. Частным случаем линейного участка является пустой оператор. Граф ФП не может содержать петель и параллельных дуг.
Формирование графа ФП начинается с загрузки образа ФП в память и настройки всех абсолютных адресов переходов и вызовов процедур. Выполнение данного этапа соответствует действиям загрузчика ОС по предварительной обработке исполняемого модуля для его последующего запуска. На этом же шаге производится анализ типа исполняемого модуля. Если его формат не соответствует принятому для данной ОС, то обработка прекращается. Эти действия могут быть представлены следующим алгоритмом.
Алгоритм 1.
Шаг 1. Прочитать управляющую информацию из заголовка исполняемого модуля (ИМ). Определить размер ИМ. Определить загрузочное смещение ИМ.
Шаг 2. Выделить память под ИМ. Запись ИМ в память.
Шаг 3. Установить счетчик обработанных перемещаемых элементов в нуль.
Шаг 4. Принять адрес выделенного блока памяти в качестве адреса начального сегмента программы (АНСП).
Шаг 5. Прочитать очередной элемент из таблицы перемещений (ТП).
Шаг 6. Вычислить адрес перемещаемой ссылки как сумму АНСП и значения из ТП.
Шаг 7. Считать из памяти по вычисленному адресу значение относительной адресной ссылки. Прибавить к считанному значению АНСП (выполнение привязки сегмента).
Шаг 8. Записать полученное значение в память.
Шаг 9. Инкрементировать счетчик обработанных ссылок. Если не все ссылки обработаны, перейти к шагу 5.
Результатом работы данного алгоритма будет образ ФП, загруженный в память с настроенными абсолютными адресами. Полная информация о размере и составе кода ФП может быть получена только после выполнения всех действий в ходе построения ГП.
Далее, начиная с точки входа в программу, формируется список вершин графа ФП в соответствии со следующим алгоритмом.
Алгоритм 2.
Шаг 1. Текущий адрес инициализируется адресом начала обработки –AN. (При первом проходе алгоритма AN инициализируется адресом точки входа.
Шаг 2. Если текущий адрес меньше адреса завершения (AK), перейти к шагу 3, иначе перейти к шагу 9.
Шаг 3. Определить длину и тип команды.
Шаг 4. Если обрабатываемая команда соответствует точке принятия решения, то определить соответствующий адрес перехода (AP) и перейти к шагу 5, иначе – к шагу 8.
Шаг 5. Сформировать очередной элемент списка вершин графа.
Шаг 6. Если значение адреса перехода текущей команды меньше AN перейти к шагу 7, иначе – к шагу 8
Шаг 7. AK := AN; AN := AP; Перейти к шагу 1.
Шаг 8. Увеличить значение адреса обработанной команды на ее длину; перейти к шагу 2.
Шаг 9. Выход из алгоритма.
В качестве параметров алгоритм получает адрес начала обработки и конечный адрес просмотра (для первого запуска алгоритма он принимает значение последнего байта программы). Возвращаемое значение (адрес перехода, если AP < AN, адрес начала обработки в противном случае) заносится в переменную, хранящую АN.
Данный алгоритм может быть представлен следующим образом:
|
где P – процедура формирования списка вершин графа; АN – адрес начала обработки (для первого вызова функции – адрес точки входа.); AK – конечный адрес просмотра; AP – адрес перехода; Ж – композиция базовых операторов S (операторы формирования списка вершин, не содержащие обращения к процедуре P) и процедуры P.
В соответствии с [3] алгоритм, определенный таким образом, является рекурсивным. В [4] показано, что глубина рекурсии для приведенного алгоритма конечна. Применение этого алгоритма обусловлено тем, что в общем случае точка входа в программу не является самым младшим адресом ФП. Однако начинать обработку программы с целью поиска вершин графа возможно только от точки входа, так как по самому младшему адресу (адресу загрузки программы) может находиться, например, сегмент данных, декодирование которого бессмысленно. Следовательно, если в процессе формирования списка вершин графа будет обнаружена команда, адрес перехода которой будет младше адреса точки входа в ФП, то возникнет необходимость обработки команд, начиная от найденного младшего адреса до адреса точки входа.
Следующий этап формирования графа ФП – упорядочивание списка вершин в соответствии с их абсолютными адресами с помощью любого известного алгоритма сортировки. Формирование списка вершин графа ФП закончено. На основании этого списка вершин графа строятся матрицы смежности и(или) инцидентности.
Предложенный в данной работе метод формирования графа ФП позволяет формировать список вершин графа за один проход и хранить только отсортированный список вершин, поскольку вся информация о дугах графа может быть получена на основании анализа адресов переходов, хранимых для каждой вершиной графа.
Граф ФП, построенный в соответствии с предложенным методом, может быть использован для решения задач:
• анализа ИК – например, построение транзитивного замыкания матрицы смежности позволяет находить "висящие" или недостижимые вершины;
• тестирования – для тестирования по методу "белого ящика" важно иметь структуру программы [5], в данном случае структура программы задается графом;
• верификации – в ходе доказательства корректности сегмента программы (в простейшем случае – линейного участка), когда необходимо получить предусловие для заданного постусловия по отношению к данному ИК [6].
|