Автоматика и телемеханика, № 8, 2008
РАСЭ 02.T0.-c
© 2008 г. М.А. ПОТАПОВ, канд. физ.-мат. наук, Е.А. ШАТОХИН (Институт автоматизации проектирования РАН, Москва)
НЕКОТОРЫЕ МЕТОДЫ АВТОМАТИЗИРОВАННОГО АНАЛИЗА И УПРАВЛЯЕМОГО ПРЕОБРАЗОВАНИЯ ПРОГРАММ
Рассматриваются принципы и методы создания программных систем, облегчающих анализ и преобразование структуры программ. При реализации масштабных проектов невозможно иметь полное представление о структуре программы без использования специальных систем. Такие системы содержат средства анализа исходной программы и в результате автоматизированного преобразования создают другую программу, обладающую заданными свойствами. В качестве примеров рассматриваются задачи быстрого автоматического дифференцирования и задачи обфускации ("затемнения", запутывания) программ.
1. Введение
История развития математических исследований, являющихся основой современных методов автоматизированного анализа и управляемого преобразования программ, восходит к временам Ньютона, Лейбница, Эйлера и Вейерштрасса. Целенаправленно и интенсивно эти проблемы начали изучаться с появлением электронно-вычислительных машин. Одной из первых работ, где были рассмотрены вопросы автоматизированного программирования и введен целый ряд терминов и понятий (компьютерная (машинная) алгебра, вычислительный граф (схема) алгоритма), широко используемых в наше время [1], стала [2]. Важным продвижением в развитии компьютерной алгебры стала статья [3]. В нашей стране в последние годы ряд аспектов этой тематики получил современное освещение и развитие в [4,5] и др. Практическая реализация идей компьютерной алгебры и автоматизированного программирования в различных приложениях началась сравнительно недавно - с 80-90-х
ГОДОВ.
Вручную, как правило, затруднительно анализировать зависимости данных в программах с большим числом операций. К настоящему времени разработаны средства, облегчающие анализ и преобразование структуры программ для различных классов задач. Эти программные системы используют возможности современных языковых средств и соответствующих трансляторов. Такие системы содержат средства анализа исходной программы и в результате автоматизированного преобразования создают другую программу, обладающую заданными свойствами.
Применение таких средств оказывается полезным в самых разных задачах, например:
1. При выполнении быстрого автоматического дифференцирования функций. Использование графа алгоритма позволяет быстро и с высокой точностью вычислять
производные функций, заданных в виде программного кода. Методы быстрого автоматического дифференцирования обладают реальными преимуществами по сравнению с традиционными конечно-разностным и символьным дифференцированием.
2. Для обфускации ("затемнения", запутывания) программ при решении проблем информационной безопасности.
3. При разработке эффективных алгоритмов и их программных реализаций для параллельных вычислительных систем [5].
В данной статье рассматриваются вопросы использования свойств структуры алгоритмов при реализации быстрого автоматического дифференцирования и в задачах обфускации программ. Задача быстрого автоматического дифференцирования является одной из центральных при управлении динамическими системами в режиме реального времени. Сравнительно новая проблема обфускации программ важна при управлении автоматизированным преобразованием программ с целью создания максимальных препятствий для их несанкционированного использования.
2. Основные понятия
Код (программа) на некотором языке программирования обычно описывает не один алгоритм, а некоторое семейство алгоритмов [5]. При выполнении кода реализуемый алгоритм зависит от того, как срабатывают условные операторы и т.д. Это в свою очередь определяется входными данными программы.
Пусть при реализации алгоритма выполняется конечный набор операций из некоторого множества M ("множество элементарных операций"). M может быть, например, множеством арифметических операций, может включать в себя математические функции из стандартных библиотек используемых языков программирования M
Пусть при конкретных входных данных программа описывает некоторый алгоритм. Сопоставим этому алгоритму ориентированный граф G = (V,E) следующим образом [5].
M
M
последовательности можно перенумеровать. В качестве множества вершин V графа возьмем множество номеров элементов. Ниже будем говорить для краткости, что в G
Для каждой пары вершин (a, b) из V построим ребро (a, b) в том и только в том случае, если результат операции в вершине a является аргументом для операции в b
b
алгоритма, будем считать их результатом специальной операции ввода данных (in)
MG не имеющие ни одной входящей дуги. Такие вершины будем называть входными. Соответственно. вершины, не имеющие ни одной исходящей дуги, будем называть выходными [5]. Среди выходных вершин есть те, результаты операций в которых являются искомыми результатами работы алгоритма.
G
называется графом информационной зависимости реализации алгоритма при фиксированных входных данных, или, короче, графом алгоритма. В англоязычной литературе этому понятию соответствует выражение " computational graph" [6]. Граф алгоритма является одним из представлений "явной схемы", предложенной Л.В. Канторовичем [2].
Еще раз отметим: граф алгоритма строится для фиксированных ВХОДНЫХ Д, (i Н Н Ы X программы. При других входных данных он может быть иным. В общем случае граф алгоритма не является ни деревом разбора соответствующей программы, ни control flow графом и т.д. [6].
Быстрое автоматическое дифференцирование (fast automatic differentiation, FAD) - один из методов вычисления производных функции, заданной в виде кода на каком-либо языке программирования [1]. Процесс вычисления значения функции для конкретных входных данных представляет собой конечную последовательность операций из множества M. Выражения для производных этих операций известны заранее. Тогда, применяя правило дифференцирования сложной функции, можно получить значение производной искомой функции.
Пример 1. Пусть функция z(x) определяется так: z = f (g(h(x), k(x))), где f, g, h, k - операции из M (см. рис. 1). Необходимо найти производную функции z в точке xo. (Предположим, что производные функций f, g, h, k существуют в соответствующих точках.) Обозначим: ho = h(xo), ko = k(xo), go = g(ho, ko).
В "прямом" методе быстрого автоматического дифференцирования ("forward mode") последовательность действий такова [6]:
1) dh = h'(xo)dx;
2) dk = k'(xo)dx;
3) dg = (gh(ho,ko)h'(xo) + gk(ho,ko)k'(xo))dx;
4) dz = f'(go)(gh(ho,ko)h'(xo) + gk(ho,ko)k'(xo))dx.
Это соответствует проходу по графу алгоритма от входных вершин к выходным, т.е. в "прямом" направлении: в таком же порядке выполняются операции при вычислении z(xo).
В "обратном" методе ("reverse mode") проход по графу алгоритма осуществляется в противоположном направлении - от вершины, соответствующей искомой функции,
ДОDVA TTTJLTV DQTiTITTiU"
JDAAJ^rtDlA. 111JUJHL.
1) dz = f'(go)dg;
2) dz = f'(go)(gh(ho,ko)dh + gk(ho,ko)dk);
3) dz = f'(go)(gh(ho,ko)h'(xo)dx + gk(ho,ko)dk);
4) dz = f'(go)(gh(ho,ko)h'(xo) + gk(ho,ko)k'(xo))dx.
В обоих случаях погрешность полученного значения производной определяется только погрешностью вычисления производных элементарных операций и погрешностью вычисления суммы и произведения. Способы вычисления производных для M
этому погрешность значения z'(xo) возникает только за счет накопления ошибок округления при выполнении сложения и умножения.
3. Быстрое автоматическое дифференцирование
3.1. Общие сведения
Рнс. 1. Граф алгоритма вычисления z(x).
Рассмотрим более общий случай. Пусть значение функции г : Вр ^ В вычисляется в следующем процессе:
^ ( ик = Ек (и^ ,...,пка{к)) , р < к < п; 1 < ,..., < к,
\ г(и1,...,ир) = ип,
и1,..., ир - независимые переменные (входные данные алгоритма), Ек - операции из М, в (к) - число аргументов операции Ек.
Пусть процесс (1) проведен для точки и = (и1}... ,ир), пусть также все частные производные операций Ек существуют в точке и. Необходимо найти У г (и) - градиент функции г в этой точке.
Граф алгоритма (1) имеет п вершин. Сопоставим каждой вершине число ак. В вершину с номером к (р < к ^ п) входят дуги только из вершин к1,... ,к8(к). Вершины 1, 2,... ,р являются входными (см. раздел 2).
"Прямой" метод в данном случае можно реализовать так. Пусть - произвольный рмерный вектор. Положим ак = гшк, к = 1,...,р. Для каждой не входной вершины (р < к ^ п) выполним следующие операции:
1) найдем все частные производные функции Ек в соответствующих точках; ак
г=1
При этом порядок обхода вершин графа может быть разным. Главное, чтобы верши-к Ек
(т.е. кь...,к8(к)).
После выполнения этих операций ап равен скалярному произв едению У г в данной точке на вектор ад. Если гш - ^'-й единичный координатный вектор, то ап -значение производной функции г по и., в точке и. Операции
в вершине
№ к выполняются за время не более С Тк, вде Тк - время выполнения операций по вычислению значения Ек, С1 - константа, не зависящая пр
ции г "прямым" методом не превосходит С1Т, вде Т - время вычисления г (и). Все
р
Общее количество операций над числами при определении У г в "прямом" методе р
В случае, когда 2 : Вр ^ Вто, "прямой" метод позволяет за один проход по графу алгоритма определить значения частных производных всех т компонент искомой функции по данному аргументу.
ап = 1
ак = 0, к < п. Для всех к = п — 1,п — 2,... ,р +1 выполним следующие операции:
Ек
Ек
с номерами к1,... ,к8(к)), выполним:
дРк '1 т
акг = акг+ --ак, г = 1,..., в(к).
дикг
к
Ек
а.
ции г по и. в точке и. Таким образом, за один проход по графу алгоритма определены все компоненты градиента функции г. Операции в вершине № к выполняются за
время не более С2Тк, где С2 - константа, те зависящая от п и р. Поэтому общее время вычисления Уг "обратным"' методом не превосходит С2Т, где Т - время вычисления г (и). Отметим, что явной зависимости от количества начальных данных (р) для этой оценки нет.
В [5] рассматривается способ определения градиента, аналоги
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.