Накладные расходы
В предложенной реализации накладные расходы возникают при вызове метода инициализации прямых Java буферов, но эти накладные расходы возникают только один раз за все время работы программы, поэтому время, которое на них тратится, не существенно влияет на общую производительность программного продукта.
Накладные расходы возникают при преобразовании данных из формата языка Java формат языка Fortran. Однако полное преобразование данных из одного формата в другой есть необходимость выполнять только дважды за работу всего приложения: в начале, после инициализации, и в конце, перед тем, как вывести окончательный результат работы приложения. Следовательно, эти накладные расходы тоже считаются разовыми и не существенно влияют на время выполнения программного продукта.
Однако возникают еще накладные расходы, когда данные обрабатываются не только в Fortran-подпрограммах, но и в основной программе, написанной на языке Java. В этом случае при каждом переключении есть необходимость преобразовать данные из одного формата в другой. Но, как правило, объем данных, обрабатываемый сразу и в Java-коде и в коде, реализованном на языке Fortran, не очень велик. Следовательно, не следует преобразовывать сразу все данные, которые рассчитываются в приложении, а нужно преобразовать только тот их фрагмент, который нужен для обработки. Такой подход позволит сократить накладные расходы на преобразование данных. Именно эти накладные расходы следует учитывать при оценке времени работы программного приложения.
Некоторые ограничения реализации приложения пользователя
Fortran-подпрограммы, которые вызываются из Java-среды, не должны содержать символа "подчеркивание" в своем имени. В противном случае разделяемая библиотека не сможет сопоставить реализованные в ней методы с теми, которые вызываются. Это вызовет падение работы всего приложения.
Компилятор GNU g77, разрешает использование переменных без их явного описания. Однако, если явно не определить тип переменной в подпрограмме, которая вызывается из Java-окружения, вероятен случай, что виртуальная Java-машина получит внешний сигнал. Этот сигнал, номер которого 11, сообщает виртуальной машине о некорректном обращении к памяти за пределами ее работы. Аналогичная ситуация может возникнуть и с функциями. При описании функций стандартом предусмотрено описывать явно тип возвращаемого значения. Однако, если этого не сделать, то компилятор сам подберет соответствующий тип, исходя из типа возвращаемого выражения. Если такую функцию вызывать из программы, реализованной только на языке Fortran, то все будет работать стабильно. Но как только объектный модуль с такой функцией участвует в формировании разделяемой библиотеки и подобного рода функция вызывается подпрограммой, которая, в свою очередь, вызывается виртуальной машиной Java, выполнение основной программы прекращается по причине получения виртуальной Java-машиной сигнала номер 11.
Данные ограничения в дальнейшем развитии работы будут сняты посредством автоматического добавления в код Fortran-программы недостающих описаний.
Описание практической части
Прототипная реализация выполнена посредством связывания вызова подпрограммы, реализованной на языке Fortran, из Java-программы через язык С (JNI). В настоящее время окружение Java не предоставляет возможности вызывать напрямую подпрограммы, реализованные на языке Fortran.
Реализация выполнена для GNU компилятора Fortran (g77), GNU компилятора С (gcc) версии 3.3.4 и JDK версии 1.4.2_03.
Компилятор g77 основан на стандарте ANSI Fortran 77, но он включает в себя многие особенности, определенные в стандартах Fotran 90 и Fortran 95 [].
JDK версии 1.4.2_03 содержит пакет java.nio, который предоставляет возможность использования новых средств ввода-вывода, таких, как прямые буферы и JNI (Java Native Interface).
Как уже отмечалось в пункте 2, прежде чем выполнить вызов подпрограммы, реализованной на языке Fortran, из Java среды, необходимо выделить область памяти, которая была бы доступна как из Java окружения, так и из среды Fortran.
Для этого нужно:
На языке Fortran реализовать подпрограмму. В этой подпрограмме должны быть объявлены все общие блоки, которые будут использоваться для обмена данными Fortran-среды с Java окружением. На языке С должен быть реализован модуль, который через разделяемую библиотеку посредством JNI будет вызываться из Java-среды. Модуль должен содержать функцию, которая вызывается из среды Fortran. Данной функции в качестве параметров по ссылке из Fortran-среды передается адрес первого, адрес последнего элемента и размер в байтах последнего элемента общего блока. По полученным данным вычисляются и сохраняются начало и размер общего блока. Такая функция вызывается для каждого общего блока. Некоторая функция вычисляет и сохраняет размер общего блока, а так же сохраняет адрес начала общего блока. Теперь во встроенном модуле, реализованном на языке С, хранятся адреса и размеры всех общих блоков, которые определены в подпрограмме, реализованной на языке Fortran. Следовательно, запросив по указанному адресу прямой буфер нужного размера, будет получено размещение нового байт буфера Java-среды в том же участке памяти, что и соответствующий ему общий блок. На языке Java реализуется класс, который содержит метод инициализации и метод получения прямого байт буфера.
Метод инициализации вызывает встроенный метод инициализации, реализованный на языке С в описанном в пункте 2 модуле. Встроенный метод инициализации вызывает Fortran-подпрограмму, описанную в пункте 1. Метод получения прямого байт-буфера вызывает встроенный С-метод, который заказывает в оперативной памяти прямой буфер нужного размера, начиная с указанного адреса. Дальше полученный прямой байт буфер уже сам пользователь может представлять как буфер тех данных, которые ему нужны.
Байт-буферы расположены непосредственно в том же участке памяти, что соответствующие им общие блоки, следовательно, все данные, которые записываются в прямой буфер в Java-коде, автоматически становятся доступными из общего блока в коде, реализованном на языке Fortran. И наоборот: все, что помещено в общий блок в Fortran-подпрограмме, автоматически становится доступно из прямого буфера в Java-программе. Такое расположение данных полностью решает поставленную в пункте 1 задачу о совместном размещении данных Java окружения и среды Fortran на одном участке памяти. Чтобы выполнить вызов Fortran-подпрограммы из Java-среды, нужно:
В Java среде расположить параметры для передачи в среду Fortran на прямом буфере. Этот прямой буфер передается в качестве параметра вспомогательным С-функциям, которые описаны в пункте 2. Так же в качестве параметра передается смещение в буфере, по которому расположены передаваемые параметры. На языке С реализовать встраиваемый через JNI в Java-окружение модуль. В этом модуле реализуются вспомогательные функции для каждой вызываемой Fortran-подпрограммы из Java окружения. Каждая такая вспомогательная функция вызывается из Java-программы. Одним из ее действий является непосредственный вызов Fortran-подпрограммы. Также вспомогательная функция выполняет передачу параметров из Java окружения в среду Fortran, как это описано в пункте 2. То есть вспомогательная функция получает адрес буфера, вычисляет адреса параметров, зная смещения их расположения в буфере, и передает вычисленные адреса Fortran-подпрограмме. На языке Java реализуется класс, который занимается записью и чтением данных из общей для Fortran среды и Java оболочки памяти.При этом при записи выполняется преобразование данных из формата языка Java в формат языка Fortran, а при чтении выполняется преобразование данных из формата языка Fortran в формат языка Java, как это описано в пункте 2.
Отличия языков C и Fortran
У языков программирования C и Fortran существует ряд различий, из-за которых нельзя перенести организацию JNI для языка С на организацию подобного интерфейса для языка Fortran.
В стандарте языка С напрямую не указан размер примитивных типов []. Выбор наилучшего для данной архитектуры размера типов оставлен на рассмотрение разработчиков компилятора. В стандарте языка Fortran для каждого примитивного типа данных строго задан их размер. Это позволяет установить взаимно однозначное соответствие между типами языка Java и типами языка Fortran, не используя промежуточных типов, как это реализовано в JNI. Среда Fortran размещает данные в статической области памяти программы. К данным есть доступ только по ссылке, и нет возможности получить адрес памяти, где они расположены. Среда Fortran не поддерживает динамически создаваемых объектов данных. Среда C, во-первых, располагает данные программы в стеке, в куче и в статической области памяти программы, во-вторых, определена операция взятия адреса, позволяющие получить доступ не только к значениям данных, но и к адресам памяти, где они расположены. Соответственно, для передачи данных из Java среды в C среду JNI достаточно указать адрес области памяти, где данные хранятся. Передачу данных из Java среды в Fortran среду нельзя выполнить аналогично тому, как это сделано в JNI. Все параметры в языке Fortran передаются только по ссылке, потому что в нем не определено понятие адреса переменной. В языке С параметры передаются только по значению, однако есть возможность передавать в качестве параметра функции указатели на ту область памяти, где хранится переменная. Соответственно, передачу данных из среды Java в среду Fortran и обратно нельзя выполнить аналогично тому, как это сделано в JNI. В многомерных массивах языка С данные располагаются по строкам, тогда как в многомерных массивах языка Fortran данные располагаются по столбцам. В языке Fortran есть возможность непосредственно работать с частями массива - вырезками и сечениями. В языке С такой возможности нет.
Следовательно, методика передачи массивов, реализованная в JNI, не может быть применена для среды Fortran. В языке Fortran есть общие блоки COMMON. Эти блоки можно размечать по-разному в каждой подпрограмме. Так, например, в одной подпрограмме может быть объявлен массив типа complex размера 100, расположенный в общем блоке /A/, а в другой подпрограмме на этой же памяти, то есть в том же общем блоке /A/, может быть объявлен массив типа real размера 200. Оба массива будут размещаться в памяти, начиная с одного и того же виртуального адреса, данные, которые в нем расположены - одни и те же, однако тип данных разный. В языке С аналогичная возможность может быть реализована посредством использования объявления union. Однако передача данных, расположенных в COMMON блоках, с целью повышения эффективности должна выполняться по схеме, отличной от той, которая реализована в JNI. Однако передача данных, расположенных в COMMON блоках с целью эффективности должна выполняться по схеме, отличной той, которая реализована в JNI для передачи данных, объявленных в union. Учитывая то, что в реализации связывания подпрограмм, написанных на языке Fortran, с Java окружением должна быть сделана эффективная передача данных между Fortran-подпрограммами и основным Java-модулем, а так же принимая во внимание отличия языков С и Fortran, можно сделать вывод о том, что организация связывания между виртуальной машиной Java и подпрограммами, реализованными на языке Fortran, должна осуществляться по несколько иной схеме, нежели связывание C-методов и виртуальной машины Java.
Отображение типов данных языка Java в типы данных языка Fortran
Основные типы языка Java и соответствующие им типы языка Fortran представлены в таблице 1. Данные для таблиц взяты из литературы [] и [].
Таблица 1. Отображение примитивных типов языка Java в типы языка Fortran.
| Int | 4 байт | INTEGER |
| Short | 2 байт | INTEGER*2 |
| Long | 8 байт | INTEGER*8 |
| Byte | 1 байт | CHARACTER |
| Float | 4 байт | REAL |
| Double | 8 байт | DOUBLE PRECISION |
| Char | 2 байт | CHARACTER |
| Boolean | 1 байт | LOGICAL*1 |
Массив языка Java можно отобразить на такое представление данных языка Fortran как массив. Отображение массива языка Java на массив языка Fortran можно сделать через прямой буфер, средства работы с которым предоставлены в пакете "java.nio".
Данные в Fortran-программах могут быть представлены в виде констант или имен переменных (или идентификаторов).
Основные типы языка Fortran и соответствующие им типы языка Java представлены в таблице 2. Данные для таблиц взяты из литературы [] и []
Таблица 2. Отображение примитивных типов языка Fortran в типы языка Java.
| INTEGER*2 | 2 байт | short |
| INTEGER INTEGER*4 | 4 байт 4 байт | int int |
| REAL REAL*4 DOUBLE PRECISION REAL*8 REAL*16 | 4 байт 4 байт 8 байт 8 байт 16 байт | float float double double double double |
| COMPLEX COMPLEX*8 COMPLEX*16 COMPLEX*32 | 8 байт 8 байт 16 байт 32 байт | float float float float double double double double double double |
| LOGICAL*1 LOGICAL LOGICAL*4 | 1 байт 4 байт 4 байт | byte int int |
| CHARACTER CHARACTER*L | 1 байт L байт | byte string |
Для отображения данных, определенных в общем блоке, в окружении Java следует использовать прямой байт буфер. Такое отображение легко организовать, потому что общий блок представляет собой некоторую область памяти, хранящую неоднородные данные. Прямой байт буфер, доступный в Java окружении также представляет собой область памяти, которая может хранить неоднородные данные.
Для каждого как именованного, так и неименованного общего блока можно использовать по одному буферу.
В языке Fortran массивом называется упорядоченная последовательность данных, занимающая непрерывную область памяти, к которой можно обращаться по имени [].
Массивы характеризуются типом значений их элементов и граничными парами - диапазоном индексов по каждому измерению. Несмотря на то, что Fortran массивы могут быть как одномерными, так и многомерными, в памяти они располагаются как одномерный массив. Причем элементы многомерного массива располагаются в памяти таким образом, что значение первого индексного выражения возрастает быстрее второго, значение второго - быстрее третьего и т. д. []. Следовательно, приведенный индекс многомерного массива можно рассчитать по ниже приведенной формуле, а именно: пусть имеется многомерный массив arr[N, M, K], тогда приведенный индекс элемента arr[i, j, k] рассчитывается следующим образом: (i-1)+(j-1)*N+(k-1)*N*M
Массив языка Fortran следует отображать на прямой байт буфер, доступный в Java среде. Такое представление выгодно, потому что многомерный Fortran-массив в памяти располагается как одномерный массив. Для получения данных из прямого буфера соответствующих элементу многомерного Fortran-массива в Java окружении реализуется специальный класс. Многомерный массив не может иметь больше 7 измерений [], то всегда можно автоматически получить данные из прямого буфера, соответствующие элементу многомерного Fortran-массива в Java окружении. При этом следует обойтись без транспонирования самого Fortran-массива. Для ссылки на элемент массива задается индексированная переменная; на массив в целом ссылаются по его имени. Начиная со стандарта Fortran 90, в языке есть возможность непосредственно работать с частями массива - вырезками и сечениями. Вырезка из массива представляет собой подмассив вида <имя_массива>(< нижняя граница - верхняя граница),
Элементы вырезки из массива могут быть взяты с шагом, отличным от единицы. В этом случае вырезка по соответствующему измерению задается уже не граничной парой, а триплетом. <имя_массива>(< нижняя граница - верхняя граница, шаг >,…)
Если по какому-то измерению опущены обе границы, то говорят о сечении массива. Вырезку из массива можно также задать с помощью векторного индекса[]. Для отображения вырезки или сечения массива на объекты Java среды также можно использовать байт буфер.Такое отображение можно выполнить следующим образом. Весь массив отображается на буфер, а дальше в Java среде организуется специальный класс, содержащий методы получения и записи элементов вырезки и сечения массива посредством пересчета с учетом шага. Таким образом, любой массив языка Fortran можно отобразить на прямой байтовый буфер языка Java. Если массив размещен на общем блоке, он автоматически отобразится в Java окружение при отображении общего блока. Если массив определен посредством использования оператора DIMENSION, то для него надо создать прямой буфер, расположенный на том участке памяти, который компилятор языка Fortran выделил для хранения данного массива. Что касается вырезки и сечения массивов, так это представление данных можно отобразить через указатели на соответствующие элементы.
в корректности работы реализации, была
Чтобы убедиться в корректности работы реализации, была взята программа расчета динамики взрыва сверх новой звезды, реализованная на языке Fortran. []. Основная функция main, которая управляет расчетами, была переписана на язык Java. Остальные подпрограммы оставлены на языке Fortran. Результаты работы исходной программы, реализованной только на языке Fortran, и программы, основная часть которой реализована на языке Java, а подпрограммы выполнены на языке Fortran, одинаковые. Для сравнения времени работы полученного приложения, реализованного на языке Java с использованием Fortran-подпрограмм, было произведено сравнение с точно таким же приложением, но реализованным целиком на языке Fortran и на языке Java. Приложение можно представить в виде следующей схемы, представленной на рисунке 1.
| полное приложение (ms) | инициализация (ms) | счет (ms) | запись (ms) | |
| Fortran | 261559 | 42826 | 218450 | 283 |
| Java + Fortran | 266223 | 43540 | 221623 | 1060 |
| Java | 337225 | 69874 | 265727 | 1624 |
Размещение данных в среде Fortran
Программа, написанная на языке Fortran, допускает использование следующих видов программных единиц: стандартных функций, подпрограмм FUNCTION, подпрограмм SUBROUTINE, операторов - функций, подпрограмм, написанных на других языках программирования, и подпрограмм BLOCK DATA [].
Формальные параметры языка Fortran передаются обычно по ссылке, за исключением тех случаев, когда параметр не модифицируется в подпрограмме []. В языке Fortran имеются средства, позволяющие использовать одну и ту же область памяти для хранения данных, общих для двух или более программных модулей выполняемой программы. Таким средством является общий блок []. Значения объектов из общего блока доступны всем программным единицам, в которых этот блок описан []. Каждый общий блок обязательно занимает в памяти непрерывный участок. Если некоторый программный модуль содержит несколько объявлений COMMON с одним и тем же именем, то все они рассматриваются как одно объявление и располагаются в памяти непрерывно и последовательно.
Для объявления массивов в языке Fortran существуют специальные предложения спецификации: объявление размерности DIMENSION []. Так же массивы могут быть расположены в общих блоках. Массивы, полученные объявлением DIMENSION, представляют собой локальные данные той подпрограммы, внутри которой они описаны.
При вызове подпрограмм, реализованных на языке Fortran, из Java окружения необходимо передавать данные из среды Java в среду Fortran. Также может возникнуть необходимость передавать данные из среды Fortran в среду Java, если вызываемая программная единица из среды Fortran - FUNCTION - возвращает значение. Все параметры Java-среда передает только по значению, в среде Java нет методов работы с указателями, а все данные Java-программы расположены в куче.
Любая подпрограмма, реализованная на языке Fortran, может получать данные извне либо как параметры, либо через общие блоки, которые в ней описаны.
Если Fortran-подпрограмма получает данные для обработки через общие блоки, то вызывающая Java-программа должна иметь доступ на запись и чтение к той памяти, в которой эти общие блоки расположены.
Такой доступ Java- программе возможно обеспечить, если на памяти, где располагается общий блок, разместить Java-объект. В качестве такого Java-объекта может быть взят прямой буфер класса Buffer, методы работы с которым доступный через пакет java.nio. Для того чтобы получить такой буфер, нужно из Fortran среды передать адрес начала общего блока и его размер. Дальше достаточно создать прямой буфер байтов, адрес начала которого будет совпадать с адресом начала общего блока, а размер будет такой же, как у соответствующего общего блока. Если Fortran-подпрограмма получает данные для обработки через формальные параметры, то для передачи таких параметров из Java окружения необходимо выделить прямой буфер в Java-окружении, на который передаваемые параметры будут помещены. После того, как передаваемые параметры будут расположены на буфере, Fortran-подпрограмме нужно передавать только адрес этого буфера и смещение в нем, по которому расположен соответствующий параметр. Возврат данных из функций языка Fortran осуществляется по значению. Для передачи возвращаемого значения функцией языка Fortran в Java-окружении, нужно это значение располагать в той области памяти, которая доступна и Java-окружению, и среде Fortran. Такой областью памяти с точки зрения среды Java может выступать прямой буфер. На нем необходимо выделить место для значения, возвращаемого функцией среды Fortran, и передать смещение в буфере Fortran-функции как параметр. А Fortran-функция запишет по полученному адресу возвращаемое значение.
Разработка системной поддержки вызова программ, реализованных на языке Fortran, из среды Java.
С.С. Гайсарян, К.Н. Долгова, Труды Института системного программирования РАН
Имеется достаточно большое количество программ,
Имеется достаточно большое количество программ, реализованных на языке Fortran и не потерявших ценность. В настоящее время широкую популярность получила среда программирования Java, обеспечивающая переносимость программ. Следовательно, возникает потребность иметь возможность вызывать подпрограммы, реализованные на языках Fortran, из Java-программ. Для вызова подпрограмм, реализованных на языке С из Java программ есть JNI, который доступен, начиная с версии JDK 1.2. Аналогичного интерфейса для вызова Fortran-подпрограмм нет. Предложенная работа повещена разработке методики вызова Fortran-подпрограмм из Java-среды. В настоящей работе рассмотрены основные отличия языков С и Fortran, препятствующие использованию методики, аналогичной JNI для вызова Fortran-подпрограмм из Java-программ. Построено отображение данных языка Fortran на данные Java и обратно. Предложена методика реализации общей области памяти для Java- и Fortran-сред через прямые буферы пакета java.nio. В последнем разделе описана прототипная реализация, выполненная с использованием JNI, которая показала эффективность предложенной методики.
Вызов Fortran-подпрограмм из Java среды
При вызове Fortran-подпрограмм из Java среды необходимо учитывать особенности чтения данных в Java- и Fortran-средах.
Java-машина читает байты, в которые записано одно число, слева направо (прямое чтение), а в C и Fortran - программах порядок байт в записи чисел зависит от архитектуры. То есть на некоторых платформах используется чтение справа налево (так называемое инвертированное чтение). Следовательно, на некоторых платформах для корректной работы, данные, записанные Fortran-подпрограммой, нужно подвергнуть дополнительному преобразованию в формат языка Java, чтобы Java-программа прочитала их корректно. И наоборот, данные, записанные Java-программой, тоже надо подвергать обратному преобразованию в формат языка Fortran, чтобы подпрограмма, реализованная на языке Fortran, смогла прочитать именно то, что было помещено в Java-коде. В выше упомянутом преобразовании предполагается менять местами соответствующие записи в ячейках. Такое преобразование необходимо осуществлять каждый раз, когда обработка данных, расположенных в памяти, общей и для Java-окружения, и для среды Fortran, передается от Java машины Fortran-среде и обратно.
Такое преобразование предполагается целесообразным выполнять при каждой записи виртуальной машиной Java данных в общую память и при каждом считывании данных из общей памяти Java машиной. Следовательно, среда Fortran всегда будет обрабатывать данные, записанные в формате языка Fortran, а Java машина всегда будет работать с данными, записанными в формате языка Java.
Разработана организация взаимодействия среды Java
Разработана организация взаимодействия среды Java и подпрограмм, реализованных на языке Fortran. Была выполнена прототипная реализация. Прототипная реализация показала, что описанная методика вызова подпрограмм, реализованных на языке Fortran, из окружения Java, реализуется с минимальными накладными расходами, а, следовательно, эффективно. Дальнейшее развитие предполагает разработку методики рефакторинга Fortran-программ с целью преобразования их в такой вид, какой было бы удобно автоматически транслировать на язык Java.
Алгоритм разбиения программы на нити
В настоящем разделе рассматривается построение промежуточного представления программы, над которым работает алгоритм, а также подробно описывается сам алгоритм разбиения программ на нити. Подробное описание алгоритма можно найти в [3]. Алгоритм состоит из трех частей:
Построение ценовой модели, отражающей свойства локальности Разбиение программы на нити Дополнительные оптимизации
Рис. 1. Пример функции и ее DDG.
Анализ маскирующих преобразований
Все маскирующие преобразования делятся на текстуальные преобразования, преобразования управляющей структуры и преобразования структур данных. Преобразования управляющей структуры в свою очередь делятся на две группы: маскирующие преобразования реструктуризации всей программы и маскирующие преобразования над одной процедурой. Преобразования структур данных в рамках данной работы не рассматривались.
В группе текстуальных маскирующих преобразований рассматриваются преобразования удаления комментариев, переформатирования текста программы и изменения идентификаторов в тексте программы. В группе маскирующих преобразований управляющей структуры, воздействующих на программу в целом, рассматриваются преобразования открытой вставки процедур, выделения процедур, переплетения процедур, клонирования процедур, устранения библиотечных вызовов. В группе маскирующих преобразований маскировки над одной процедурой рассмотрены преобразования внесения непрозрачных предикатов и переменных, внесения недостижимого кода, внесения мёртвого кода, внесения дублирующего кода, внесения тождеств, преобразования сводимого графа потока управления к несводимому, клонирования базовых блоков, развёртки циклов, разложения циклов, переплетения циклов, диспетчеризации потока управления, локализации переменных, расширения области действия переменных, повторного использования переменных, повышения косвенности.
| Int fib(int n) { int a, b, c; a = 1; b = 1; if (n 1; n--) { c = a + b; a = b; b = c; } return c; } | int fib(int n) { int a, b, c, i; long long t; a = 1; b = 1; if (n |
| (a) исходная программа | (b) замаскированная программа |
Рис. 5. Пример применения маскирующего преобразования внесения тождеств
На Рис. 5 показан пример применения маскирующего преобразования внесения тождеств к программе, вычисляющей функцию Фибоначчи. Преобразование основано на малой теореме Ферма
Для этого примера цена равна 3.83, а усложнение программы - 4.85. Расстояние между исходной и замаскированной программой равно 21.
| LC | UC | YC | DC | |
| Исх. процедура fib | 12 | 0 | 0.1111 | 14 |
| Замаскированная fib | 23 | 0 | 0.3086 | 29 |
Другое маскирующее преобразование - введение непрозрачных предикатов - является ключевым для повышения устойчивости других маскирующих преобразований, например, внесения недостижимого кода. Непрозрачным предикатом называется предикат, всегда принимающий единственное значение true или false. При маскировке программы предикат строится таким образом, что его значение известно, но установить по тексту замаскированной программы, является ли некоторый предикат непрозрачным, трудно. В работе рассматриваются методы построения непрозрачных предикатов, использующие динамические структуры данных и булевские формулы.
На основании определения устойчивости маскирующих преобразований, дан-ного выше, становится возможным провести анализ всех опубликованных маскирующих преобразований для выявления их устойчивости по отношению к нашему множеству демаскирующих преобразований и алгоритмов анализа. Мы можем ввести количественную классификацию маскирующих преобразований и выявить наиболее устойчивые маскирующие преобразования. Для этого вводятся - эвристическая оценка CL сложности анализа, которая устанавливает глубину анализа замаскированной программы, необходимого для выполнения демаскирующего преобразования, и эвристическая оценка SL степени поддержки демаскировки, устанавливающая необходимую степень участия человека в процессе демаскировки. Для оценки CL используется шкала, приведённая в таблице 1. Для оценки SL используется шкала: "автоматический анализ" (0 баллов), "полуавтоматический анализ" (1 балл), "ручной анализ с развитой инструментальной поддержкой" (2 балла), "только ручной анализ" (3 балла). Итоговая оценка DL трудоёмкости анализа равна
DC=CL+SL
В нашей работе показано, что для каждого маскирующего преобразования можно предложить автоматический или полуавтоматический метод демаски-ровки, позволяющий приблизить демаскированную программу p` к исходной программе p. При использовании полустатических алгоритмов анализа программ мы исходим из предположения, что для замаскированной программы существует достаточное количество тестовых наборов, обеспечивающее требуемый уровень доверия.
Таким образом можно получить количественную классификацию маскирующих преобразований. Для каждого маскирующего преобразования приводится оценка сложности маскировки и оценка трудоёмкости демаскировки. Значение, получаемое как разность оценки трудоёмкости демаскировки и оценки сложности маскировки, позволяет оценить насколько демаскировка данного маскирующего преобразования сложнее, чем маскировка. Исходя из этого определяются маскирующие преобразования, применение которых неоправдано, например, переформатирование программы, разложение циклов, локализация переменных; методы маскировки, которые следует применять только в комплексе с другими методами, например, изменение идентификаторов, внесение дублирующего кода и методы маскировки, применение которых наиболее оправдано, например, внесение тождеств, переплетение процедур, построение диспетчера, повышение косвенности. Сравнение двух маскирующих преобразований приведено в таблице 3. Через D обозначена разность OC-DL, через ?1 обозначено расстояние между текстами замаскированной и исходной программ fib, а через ?2 - расстояние между текстами демаскированной и исходной программ. Из таблицы следует, что маскирующее преобразование построения диспетчера предпочтительнее, так как, при равных с методом внесения тождеств трудо-затратах на демаскировку, обеспечивает лучшее соотношение усложнения программы к цене преобразования.
| Преобразование | OC | TC | MC | ?1 | CL | SL | DL | ?2 | D |  |
| Внесение тождеств | 2 | 3.83 | 4.85 | 21 | 4 - 5 | 2 | 7 | 0 | 5 | 1.27 |
| Построение диспетчера | 2 | 3.83 | 6.14 | 39 | 5 | 2 | 7 | 2 | 5 | 1.60 |
Автоматическое выявление уязвимостей защиты программ
Бурное развитие современных телекоммуникационных технологий позволило решить задачу доступа к информационным и вычислительным ресурсам вне зависимости от географического расположения поставщика и потребителя ресурсов. Сеть Интернет связывает миллионы компьютеров по всей планете. С другой стороны, именно общедоступность информационных ресурсов подняла на новый уровень требования к безопасности программного обеспечения. Необходимым условием обеспечения безопасности ПО является его корректная работа на всех возможных входных данных и всех других видах внешних по отношению к программе воздействий.
Следует заметить, что данное требование сильнее, чем требование отсутствия в программе ошибок, если под ошибками понимать несоответствие действи-тельного поведения программы специфицированному на указанном в спецификации множестве входных данных программы. Спецификация может определять поведение программы лишь на подмножестве множества всех возможных входных данных. Например, для программ, получающих данные от пользователя или из других неконтролируемых программой внешних источников реальное множество входных данных представляет собой просто множество всех возможных битовых строк вне зависимости от спецификации входных данных программы. Если программа является частью многопро-цессной системы и взаимодействует с другими процессами и окружением, реальное множество входных данных зависит и от всех возможных темпоральных вариантов взаимодействия процессов, а не только от специфицированных.
Когда требование корректной работы программы на всех возможных входных данных нарушается становится возможным появление так называемых уязвимостей защиты (security vulnerability). Уязвимости защиты могут приводить к тому, что одна программа может использоваться для преодоления ограничений защиты всей системы, частью которой является данная программа, в целом. В особенности это относится к программам, обслуживающим различные общедоступные сервисы сети Интернет и к программам, работающим в привилегированном режиме.
Рассмотрим, например, последний случай "взлома" Интернет-сервера проекта Debian Linux. Программа- сервер синхронизации файлов по сети rsync содержала уязвимость в защите, которая позволяла, подключившись к серверу rsync и подав на ему на вход специально подготовленные входные данные, принудить процессор исполнить не исполняемый код программы rsync, а исполняемый код, переданный в этих входных данных. Сама по себе программа rsync не является привилегированной, но таким образом был получен доступ к компьютеру с возможностью запускать произвольные программы (доступ shell account). Естественно, такой способ получения дос-тупа к компьютеру обходит все нормальные средства аутентификации, такие как ввод регистрационного имени и пароля, ввод однократного ключа и т. д.
Получив возможность выполнения произвольных программ на сервере, злоумышленник использовал другую уязвимость в защите, теперь непосред-ственно ядра Linux, которая была связана с недостаточной проверкой параметра, передаваемого системному вызову sbrk. Передавая этому систем-ному вызову отрицательные значения можно было добиться открытия доступа к критически важным страницам памяти, после чего можно было добиться выполнения произвольной программы уже с правами суперпользователя (root). Обычно такая программа - это интерпретатор командной строки /bin/sh. Таким образом, неизвестный злоумышленник в два этапа получил полный контроль над машиной, на которой он раньше даже не имел shell account.
Уязвимости в защите, которые могут быть использованы просто подключением к уязвимой программе без какой-либо авторизации называются удалённо-эксплуатируемыми (remotely exploitable). Уязвимости в защите, которые требуют наличия локального доступа типа shell account обычно называются локально-эксплуатируемыми (locally-exploitable). Наиболее опасен первый тип уязвимостей, так как он позволяет вообще произвольному (неизвестному) лицу получить возможность запуска произвольных программ.
Следует заметить, что данный пример отнюдь не единичен.
Уязвимости разной степени опасности обнаруживаются в программах систематически несколько раз в месяц. В связи со столь неблагоприятной ситуацией, в США была разработана процедура сертификации программного обеспечения (Common Criteria). ПО, не прошедшее сертификацию по этой процедуре не может работать на критически важных серверах государственного значения.
Это показывает, почему ведущие производители телекоммуникационного оборудования и программного обеспечения привлекают большие ресурсы для аудита существующего массива программного обеспечения для выявления и устранения в них уязвимостей защиты. К сожалению, в настоящий момент процесс аудита программного обеспечения с целью выявления уязвимостей защиты совершенно неудовлетворительно поддерживается инструмен-тальными средствами. Как будет показано далее, основная проблема сущест-вующих инструментальных средств - высокий процент ложных срабатываний, когда фрагмент программы, не содержащий ошибок, приводящих к уязвимостям защиты, отмечается как опасный. Высокий процент ложных срабатываний требует большого количества ручного труда для отсеивания ложных сообщений от сообщений, действительно выявляющих ошибки.
В настоящее время в рамках контракта с Nortel Networks в отделе компи-ляторных технологий ведётся разработка инструментального средства для автоматического выявления уязвимостей защиты некоторых типов. Дальнейшие разделы настоящей работы посвящены описанию разрабаты-ваемого прототипа инструментального средства.
Ценовая модель
Нашей целью является построение разбиения программы на нити, максимально использующего возникающие события локальности. Чтобы иметь возможность судить о степени оптимальности того или иного разбиения, необходимо ввести некоторую ценовую модель. Так как мы оптимизируем время выполнения программы, то естественно ввести веса узлов графа зависимости по данным, равные времени выполнения узла в последовательной программе.
Время выполнения узла может быть найдено с помощью профилирования программы. Для этого необходимо инструментировать исходный код программы, вставляя вызовы функций из библиотеки поддержки, вычисляющих время выполнения инструкций, и выполнить программу на нескольких наборах типичных входных данных. Для получения более точных результатов можно воспользоваться высокоточными аппаратными счетчиками, имеющимися на большинстве современных архитектур (например, инструкцией RDTSC для Pentium III и выше). Эта оценка времени выполнения точно показывает реальное время выполнения программы, но затрудняет эмуляцию кэша на этапе разделения на нити, так как сложно определить, насколько уменьшится время выполнения узла при попадании в кэш (возможно, при профилировании это попадание уже произошло).
Ценовая модель должна также отражать события локальности, происходящие во время выполнения программы. Статических весов для узлов DDG для этой цели недостаточно. Необходима эмуляция кэша в процессе разделения на нити и соответствующая корректировка времени выполнения узла.
Граф зависимостей по данным
При разделении программы на нити прежде всего нужно учитывать зависимости по данным. Поэтому естественно потребовать, чтобы промежуточное представление программы содержало легкодоступную информацию о зависимостях по данным между различными частями программы. В то же время необходимо максимально отразить сведения о "естественном" параллелизме программы, причем на разных уровнях - от отдельных инструкций, до более крупных программных блоков.
Представлением, обладающим всеми необходимыми нам свойствами, является иерархический граф зависимостей по данным, используемый в [9] (data dependence graph, DDG). Узлом такого графа может являться:
Простой оператор (сложение, умножение, сравнение, присваивание и т.д.) Более сложный оператор (условный оператор, оператор цикла и т.д.) Граф зависимостей по данным следующего уровня, инкапсули-рующий свойства соответствующего программного блокаДуги графа DDG представляют собой зависимости по данным между узлами. Более формально, пусть u и v - узлы DDG, причем в последовательной программе u предшествует v. Дуга (u, v) входит в граф тогда и только тогда, когда между u и v есть зависимость по данным одного из трех типов:
"запись-чтение" (в узле v необходимы результаты вычислений узла u), "чтение-запись" (в узле v записывается переменная, значение которой считывается в u), "запись-запись" (оба узла записывают одну и ту же пере-менную).Наличие одной из указанных зависимостей по данным между узлами говорит о том, что при параллельном выполнении программы для получения результатов, совпадающих с последовательной версией, необходимо выполнить u раньше, чем v.
Легко заметить, что граф зависимостей по данным является ориентированным ациклическим графом. Это объясняется тем, что циклы в DDG означают наличие циклических зависимостей по данным, возможных, в свою очередь, только в операторах цикла исходной программы. Но циклы, как и другие сложные операторы, раскрываются на более низком уровне иерархии, обеспечивая разрыв таких зависимостей по данным.
Это свойство графа будет использоваться нами в дальнейшем.
Пример функции и ее графа зависимостей по данным приведен на Рис. 1. DDG состоит из трех узлов: двух простых узлов и оператора цикла, раскрывающегося в DDG второго уровня.
Граф зависимостей по данным строится для каждой функции программы. Алгоритм построения состоит из следующих этапов:
Построение графа потока управления программы.
Выбор программных блоков, которые будут узлами текущего уровня иерархии DDG.
Нахождение зависимостей по данным между этими узлами с помощью алгоритма достигающих определений.
Если необходимо, продвинуться на следующий уровень иерархии и достроить граф.
Для того, чтобы отразить на графе побочные эффекты работы функции, в графе вводится специальный узел EXIT. Все узлы, генерирующие побочные эффекты (например, осуществляющие запись в глобальную переменную), связаны дугой с узлом EXIT. Все этапы алгоритма разделения на нити, описанные ниже, работают с представлением программы в виде графа зависимостей по данным.
Инструментальные средства для обнаружения уязвимостей защиты
В настоящее время разработано большое количество инструментальных средств, предназначенных для автоматизации поиска уязвимостей защиты программ на языках Си и Си++. В данном разделе мы рассмотрим наиболее распространённые инструментальные средства.
По виду использования инструментальные средства можно разделить на два типа: инструменты, добавляющие дополнительные динамические проверки в программу и инструменты только статического анализа программ. В нашей работе мы рассмотрим инструменты, которые выявляют уязвимости защиты с помощью статического анализа программ.
CodeSurfer. CodeSurfer - это инструмент анализа программ, который не предназначается непосредственно для поиска ошибок уязвимости защиты. Его основными достоинствами являются: Анализ указателей Различные анализы потока данных (использование и определение переменных, зависимость данных, построение графа вызовов) Скриптовый язык.CodeSurfer может быть использован для поиска ошибок в исходном коде, для улучшения понимания исходного кода, и для реинженерии программ. В рамках среды CodeSurfer велась разработка прототипа инструментального средства для обнаружения уязвимостей защиты, однако разработанное инструментальное средство используется только внутри организации разработчиков.
Flawfinder, ITS4, RATS, PScan. Все эти программы разработаны для поиска ошибок переполнения буфера и ошибок, связанных с использо-ванием форматных строк. Данные инструменты во многом схожи. Они все используют возможности только лексического и простейшего синтакси-ческого анализа, поэтому в данном случае не приходится говорить о сколь-нибудь эффективном нахождении ошибок при помощи этих программ - результаты, выданные ими, могут содержать до 100% ложных сообщений.Основные свойства этих программ:
" База данных потенциально опасных функций (ITS4, RATS) " Подробное аннотирование исходного кода (Flawfinder, ITS4) Возможность поиска функций, принимающих внешний ввод. (Flawfinder - с опцией -inputs, RATS) UNO. UNO - простой анализатор исходного кода.Он был разработан для нахождения таких ошибок, как неинициализированные переменные, нулевые указатели и выход за пределы массива. UNO позволяет выполнять несложный анализ потока управления и потоков данных, осуществлять как внутри- так и меж-процедурный анализ, специфицировать свойства пользователя. Однако, к сожалению, данный инструмент не доработан для анализа реальных приложений, не поддерживает многие стандартные библиотеки, и, на данном этапе, разработки не позволяет анализировать сколь-нибудь серьёзные программы. FlexeLint, Splint. Это наиболее мощные инструменты из всех, рассмотренных в данной работе. Они предназначены для анализа исходного кода с целью выявления различных ошибок. Обе программы производят семантический анализ исходного кода, анализ потоков данных и управления. В конце работы выдаются сообщения нескольких основных типов:
Возможен нулевой указатель. Проблемы с выделением памяти (например, нет free() после malloc()). Проблемный поток управления (например, недостижимый код). Возможно переполнение буфера, арифметическое переполнение. Количество таких сообщений при работе над кодом большой программы может быть очень значительным. Поэтому оба инструмента поддерживают опции, позволяющие настраивать сообщения. Опции могут задаваться также и в исходном коде, например, в виде аннотаций.
FlexeLint и Splint не разрабатывались с целью поиска ошибок уязвимости защиты. Однако обе программы позволяют находить некоторые, наиболее простые случаи потенциального переполнения буферов. При этом FlexeLint не подходит для нахождения ошибок с форматными строками, в то время как Splint выдаёт предупреждения такого типа.
Как видно из приведённого краткого обзора, существующие инструменты не задействуют все современные методы статического анализа программ, ограничиваясь лишь контекстным анализом. Как было отмечено в [12], применение глубокого статического анализа программ может позволить существенно снизить количество ложных срабатываний и повысить точность обнаружения уязвимостей защиты.
Интегрированная среда
Все направления исследований, описанные в настоящей статье реализуются на базе единой интегрированной среды для изучения алгоритмов анализа и опти-мизации программ [1]. IRE является системой с открытыми исходными кодами и распространяется на условиях Общей публичной лицензии GNU (GNU General Public License). Система доступна для загрузки из сети Интернет [4]. Интегрированная среда построена как набор связанных друг с другом инструментов, работающих над общим промежуточным представлением программ MIF. Для управления инструментами ИС предоставляется графический интерфейс пользователя.
В настоящее время в качестве исходного и целевого языка программирования используется язык Си, но внутреннее представление разработано таким образом, чтобы поддерживать широкий класс процедурных и объектно-ориен-тированных языков программирования. Все компоненты ИС реализованы на языке Java, за исключением транслятора из Си в MIF, который реализован на языке Си.
Использование методов анализа потоков данных для решения задачи обнаружения уязвимостей
В отделе компиляторных технологий по контракту с фирмой Nortel Networks разрабатывается прототип инструментального средства для автоматического обнаружения уязвимостей. В прототипе нами реализовано автоматическое выявление уязвимостей переполнения буфера, форматных строк, испорченного ввода. В дополнение к ним реализовано обнаружение ошибок утечки динамической памяти.
Для разрабатываемого инструментального средства нами реализован новый алгоритм выявления уязвимостей защиты, основанный на глубоком межпроцедурном анализе указателей в программе. Алгоритм состоит из следующих основных компонент:
Внутрипроцедурный анализ указателей, основанный на понятии "абстрактной ячейки памяти" (abstract memory location). Анализ диапазонов для переменных целых типов. Контекстно-зависимый (context-sensitive) и потоково-зависимый (flow-sensitive) межпроцедурный анализ. Специальная поддержка основных функций стандартной библиотеки языка Си и возможность спецификации семантики функции с помощью аннотаций.Анализ указателей (alias analysis) [10] позволяет для каждой переменной указательного типа в каждой точке программы построить множество объектов, на которые он может указывать. В языке Си анализ указателей является необходимым шагом для выполнения практически любого оптимизирующего преобразования. Кроме того, анализ указателей для языка Си осложняется неразличимостью указателей и массивов, а также присутствием указательной арифметики.
Для анализа указателей мы выбрали подход, основанный на моделировании операций с указателями. Каждому объекту, который может существовать при работе программы, то есть статическим переменным, переменным, создаваемым и уничтожаемым на стеке, переменным в динамической памяти ставится в соответствие абстрактная ячейка памяти. При анализе программы абстрактные ячейки памяти создаются, когда в работающей программе выделяется память под соответствующую переменную. Абстрактная ячейка памяти хранит следующую информацию:
| Size | Размер данной абстрактной ячейки. Для функций динамического выделения памяти размер ячейки определяется по параметру функции. |
| overlap | Множество абстрактных ячеек памяти, которые накладываются на данную абстрактную ячейку. Этот атрибут используется для переменных агрегатных, потому что в таких случаях создаются отдельные абстрактные ячейки памяти и для структуры целиком, и для каждого составляющего структуру поля. |
Атрибуты абстрактной ячейки памяти, описанные выше, являются стати-ческими, то есть не изменяются всё время жизни абстрактной ячейки памяти.
В каждой точке программы с абстрактной ячейкой памяти могут быть связаны динамические атрибуты, которые описываются ниже.
| Len | Текущая длина строки для строковых переменных. |
| value | Значение переменной. |
| input | Указывает, зависит ли данная абстрактная ячейка памяти в данной точке программы прямо или косвенно от внешних источников данных. |
| Undef | Неопределённое значение, изначально возникает, когда переменная неинициализирована и как результат операций, если один из аргументов - Undef. |
| Any | Переопределённое значение. Возникает когда статического анализа недостаточно для определения значения переменной (например, при чтении значения переменной из внешнего источника), либо как результат операции, если один из аргументов имеет значение Any, либо как результат операции при соответствующих операндах. |
| [a,b] | Любое значение в интервале от a до b. |
Значения указательных типов представляются множествами пар (AML, offset), где AML - абстрактная ячейка памяти, а offset - смещение от начала ячейки, которое имеет мета-тип M_Integer, то есть представляет собой диапазон смещений указателя внутри данного объекта. Кроме того, поддерживается значение Undef для неопределённых (неинициализированных) переменных, значение Any(type), если указательное выражение может принимать произвольное значение типа type, и значение Any, если указательное выражение может принимать произвольное значение.
Значения Any могут возникать как результат слияния значений переменных в точках слияния потока управления, вследствие ограниченной глубины анализа объектов в динамической памяти, и когда указательное значение возвращается функцией, для которой не существует исходного кода и не специфицированы аннотации.
Внутрипроцедурный анализ указателей реализован по стандартной схеме итеративного прямого анализа потоков данных процедуры [11]. Для каждой инструкции процедуры на основании входящих динамических атрибутов абстрактных ячеек памяти вычисляются выходящие атрибуты, которые затем подаются на вход следующей инструкции. В точке слияния потока управления выполняется операция слияния динамических атрибутов (join). Анализ выполняется итеративно до тех пор, пока множества динамических атрибутов не перестанут изменяться.
Одновременно с анализом указателей по аналогичной схеме выполняется анализ целочисленных интервалов. Эти два вида анализа переплетаются друг с другом, поскольку от интервалов целочисленных переменных могут зависеть указательные выражения и наоборот.
При выполнении внутрипроцедурного анализа основную сложность представляют циклы. Для циклов реализуются специальный алгоритм вычисления диапазонов индуктивных переменных и зависящих от них выражений, состоящий из двух шагов. На первом шаге делается расширение диапазона индуктивной переменной до максимального, на втором шаге выполняется ограничение диапазона с учётом условий в теле цикла.
При анализе практически любой программы возникает необходимость в межпроцедурном анализе. По степени точности анализа можно выделить контекстно-чувствительные и контекстно-нечувствительные методы анализа. Во втором типе методов анализа процедуры рассматриваются независимо от контекста, в котором они вызываются. Множество динамических атрибутов на входе в процедуру получается как слияние множеств динамических атрибутов во всех точках вызова данной процедуры. Множество динамических атрибутов на выходе процедуры переносится во все точки возврата из процедуры в вызывающую её процедуру.
Как и в случае внутрипроцедурного анализа межпроцедурный анализ ведётся итеративно до тех пор, пока множества на входах и выходах не перестанут изменяться. В контекстно-чувствительных методах анализа, анализ каждой процедуры проводится независимо для каждого вызова процедуры и учитывает контекст вызова этой процедуры. Как следствие, контекстно-чувствительный анализ требует больше ресурсов для своего выполнения.
В нашем инструментальном средстве мы используем гибридный подход. В точке вызова каждой процедуры учитывается контекст вызова, но контекст возврата из процедуры берётся как объединение всех контекстов выхода для всех вызовов данной процедуры в программе. Это позволяет повысить точность анализа, несильно увеличивая его сложность.
Дополнительной сложностью, возникающей при межпроцедурном анализе, является необходимость анализа указателей при вызовах процедур через указатель. Хотя множество возможных значений указательного выражения нарабатывается в процессе межпроцедурного анализа, это может потребовать перестройки графа вызовов процедур на ходу. В текущем прототипе нашего инструментального средства мы используем консервативный подход, предполагая, что каждый раз по указателю могут быть вызваны все процедуры, списки формальных параметров которых соответствуют фактическим параметрам вызова.
Для выявления уязвимостей защиты программ, работающих в некотором операционном окружении необходимо знание семантики работы этого окружения. Прототипная версия инструментального средства разработана в расчёте на операционное окружение, предоставляемое Linux. Непосредственно в алгоритм анализа встроена поддержка основных функций стандартной библиотеки языка Си (в особенности функций работы со строками и с памятью, в том числе динамической), основных примитивов POSIX работы с файлами, файловой системой, процессами и т. д., а также некоторых специфичных расширений Linux, в частности, интерфейса модулей ядра.
В настоящее время разрабатывается язык аннотаций, чтобы дать возможность пользователю нашего инструментального средства самому специфицировать семантику процедур, отсутствующих в исходном коде или для которых автоматический анализ недостаточно точен.
При разработке языка аннотаций необходимо учитывать противоречивые требования: во-первых, язык должен быть достаточно мощным, чтобы позволять специфицировать семантику с требуемой для анализа степенью точности, но, с другой стороны, он должен быть достаточно простым, чтобы не требовать от пользователей специфических знаний формальных методов, и т. д.
Язык аннотаций строится на расширении синтаксиса языка Си, уже применяющемся в широко распространённом компиляторе GCC. Так, для спецификации того, что возвращаемое значение некоторой функции foo находится в интервале [0,5] используется следующая конструкция:
int foo(int x) __attribute__ ((post(foo >= 0 && foo Здесь __attribute__((...)) - это синтаксическое расширение GNU C, поддерживаемое нашим инструментальным средством, post - специальный атрибут, позволяющий определять постусловие для функции, а имя функции foo используется в постусловии для обозначения значения, возвращаемого этой функцией. Кроме того, реализуется специальная поддержка для стандартного макроса assert.
Экспериментальные результаты
Мы применили нашу реализацию алгоритма к тестовой функции, решающей алгебраическое уравнение четвертой степени x4+ax3+bx2+cx+d=0.
Функция не содержит циклов и не может быть распараллелена традиционными способами. Полученная многопоточная версия функции была реализована с помощью библиотеки pthread под операционной системой Linux. Экспериментальные запуски были проведены на четырехпроцессорном Intel Itanium, на которых установлена ОС RedHat Linux 7; использовались компиляторы GCC 3.3.1 и ICC 8.00b. Программа запускалась 100 раз, время ее выполнения измерялось с помощью высокоточных аппаратных счетчиков. Вычислялось среднее значение времени выполнения ? и среднеквадратичное отклонение ?. Все значения времени выполнения, не укладывающиеся в промежуток [?-2?,?+2?] удалялись из выборки, после чего среднее значение пересчитывалось. Эта величина использовалась для подсчета ускорения. Результаты эксперимента приведены на Рис. 4.
Рис. 4. Ускорение, достигнутое на Itanium
Маскирующие преобразования программ
Другим направлением, развиваемым в рамках IRE является исследование маскировки (obfuscation) программ. Мы рассматриваем проблему защиты программ от обратной инженерии, проводимой с целью модификации и/или включения фрагментов защищаемой программы во вновь разрабатываемый программный код. Защита в данном случае состоит в том, чтобы затруднить понимание деталей реализации компонент большой программной системы, сделав его настолько дорогим, чтобы дешевле было разработать оригинальное программное обеспечение.
Одним из способов такой защиты является маскировка программ, заклю-чающаяся в применении к исходному тексту программы цепочки маски-рующих преобразований, то есть преобразований, сохраняющих реализуемую программой функцию (являющихся функционально эквивалентными), но затрудняющих понимание этой функции.
Целью нашего исследования является новый метод маскировки программ, удовлетворяющего следующим требованиям:
Исходная и замаскированная программа записаны на языке Си. В методе применяются цепочки маскирующих преобразований, элементы которых берутся из некоторого заранее зафиксированного множества параметризованных маскирующих преобра-зований. Все цепочки таких преобразований порождаются автоматически поддерживающими метод инструментальными средствами и являются допустимыми по своим характеристикам, то есть уве-личивают размер маскируемой программы и/или уменьшают скорость её работы не более чем в фиксированное количество раз. Метод маскировки устойчив относительно современных методов ста-тического и полустатического анализа программ, развитых для языка Си.Предложена новая методология анализа маскирующих преобразований, которая позволяет давать качественную и количественную характеристику преобразований. Количественная характеристика преобразований позволяет дать их классификацию и выявить среди них наиболее подходящие для использования при маскировке программ. Основываясь на проведённом исследовании нами предложен новый метод маскировки программ, который удовлетворяет всем целям, сформулированным выше.
Методология анализа маскирующих преобразований программ
Для оценки действия маскирующих преобразований на программу мы используем несколько показателей сложности кода программ. Традиционно, подобного рода показатели называются "метрики", в дальнейшем мы будем придерживаться этого термина и в нашей работе. Метрики сложности кода программы ставят в соответствие любой программе некоторое число, которое тем больше, чем "сложнее" программа. Простейшая метрика LC размера процедуры равна количеству инструкций промежуточного представления MIF в записи процедуры. Метрика YC сложности циклической структуры равна мощности транзитивного замыкания отношения достижимости в графе потока управления процедуры. Метрика DC сложности потока данных определяется как количество дуг в графе зависимостей по данным, строящемся по результатам анализа достигающих определений программы. Метрика UC количества недостижимого кода определяется как количество инструкций в программе, которые не выполняются ни при каких наборах входных данных. Известно, что точное вычисление метрик DC и UC является алгоритмически неразрешимой задачей.
Через O(p,e) мы обозначим применение метода маскировки O к программе p. e - это параметр, который позволяет выбрать единственную программу p' = O(p,e) из множества функционально эквивалентных замаскированных программ O(p). В частности, параметр e может быть случайным числом. Множество изменения параметра e обозначим через E. Тогда LC(p) - значение метрики LC до маскировки, а LC(O(p,e)) - после маскировки.
Композитная метрика цены TC преобразования O(p,e) вычисляется по метрикам LC и UC следующим образом:
Для конечного множества D программ цена маскирующего преобразования определяется как
Метод маскировки называется допустимым для множества D, если
Для конечного множества D программ усложнение определяется как
Чем больше метрика усложнения программы, тем сложнее для понимания становится замаскированная программа в силу увеличения числа информационных и управляющих связей.
Для оценки сложности самого маскирующего преобразования вводится оценка OC сложности маскирующего преобразования, которая определяется как требуемая для выполнения данного маскирующего преобразования глубина анализа программы согласно таблице 1.
| Требуемая глубина анализа | Значение OC |
| Лексический анализ | 0 |
| Синтаксический анализ | 1 |
| Семантический анализ | 2 |
| Анализ потока управления | 3 |
| Консервативный анализ потока данных | 4 |
| Полустатический анализ | 5 |
| Точный анализ потока данных | 6 |
Для оценки степени различия текстов программ вводится расстояние ?(p1,p2) между текстами программ p1 и p2, которое используется для оценки устойчивости маскирующего преобразования. Введём расстояние ?C между графами потока управления двух процедур, равное минимальному количеству операций удаления и добавления рёбер и дуг, переводящих один граф в граф, изоморфный другому. Аналогично введём расстояние ?D между графами зависимостей по данным двух процедур. Обозначим через ?CD(f1,f2) сумму ?C(f1,f2)+?D(f1,f2). Тогда расстояние ?(p1,p2) вычисляется по формуле
Здесь минимум берётся по всевозможным множествам M, состоящим из пар (f1,f2), где f1 - процедура из программы p1, f2 - процедура из программы p2. Все процедуры f1 и f2 встречаются в M не более одного раза. Через M1 обозначено множество процедур программы p1, отсутствующих в M, а через M2 - множество процедур программы p2, отсутствующих в M. E - это пустой граф.
Такие подготовительные определения позволяют нам определить понятие устойчивости метода маскировки программ по отношению к заданному набору алгоритмов их анализа и основанным на них методам демаскировки программ следующим образом.
Пусть
Тогда метод маскировки - это цепочка
Метод маскировки O является допустимым, то есть
Константа ? называется порогом устойчивости.
Параметры C и ? подбираются эмпирически. Параметр C - это оценка вычислительных ресурсов используемых для атаки на замаскированную программу. Чем больше C, тем более сложные методы демаскировки могут применяться для атаки. Параметр ? зависит от ценности защищаемой программы и уровня экспертизы, ожидаемого при атаке на замаскированную программу. Чем больше ценность маскируемой программы и чем выше ожидаемый уровень подготовки лиц, выполняющих атаку на замаскированную программу, тем больше должен быть порог устойчивости ?.
Наш анализ методов маскировки программ исходит из предположения, что множество всех возможных алгоритмов анализа и преобразования программ, которые могут использоваться для демаскировки программ, фиксировано. Для нашего анализа мы выбрали представительное множество методов, составленное следующим образом. Большинство рассматриваемых демаскирующих преобразований являются оптимизирующими преобразованиями, используемыми в оптимизирующих компиляторах. К таким преобразованиям относятся, например, устранение общих подвыражений и устранение мёртвого кода. Кроме них описываются алгоритмы полустатического анализа такие, как построение и анализ покрытия дуг и базовых блоков, и основанные на них разработанные в рамках данной работы демаскирующие преобразования.
В рамках нашего исследования нам удалось получить качественную и количественную характеристику опубликованных другими исследователями и разработчиками систем маскировки маскирующих преобразований. Был проведён сравнительный анализ их цены TC, усложнения маскируемой программы MC и оценки сложности OC. На примере программы, вычисляющей функцию Фибоначчи, проводится ранжирование маскирующих преобразований по соотношению усложнение/цена.
Новый метод маскировки программ
Новый метод маскировки программ мы далее обозначим аббревиатурой "ММ". Его более подробное описание можно найти в [2]. Метод ММ применяется к функциям маскируемой программы по отдельности, при этом структура маскируемой программы в целом не изменяется. Для изменения структуры маскируемой программы могут применяться стандартные методы открытой вставки и выноса функции, которые, однако, не являются частью предлагаемого метода маскировки.
При маскировке каждой функции ММ использует, наряду с локальными несущественными переменными, глобальные несущественные переменные, которые формируют глобальный несущественный контекст. В маскируемую программу вносятся несущественные зависимости по данным между сущест-венным и несущественным контекстом функции. Наличие глобального несущественного контекста, совместно используемого всеми замаскированными функциями, приводит к появлению в замаскированной программе зависи-мостей по данным между всеми функциями и глобальными переменными.
Метод ММ состоит главным образом из преобразований графа потока управления. В результате граф потока управления замаскированной программы значительно отличается от графа потока управления исходной программы. Метод не затрагивает структур данных исходной программы, но вносит в за-маскированную программу большое количество несущественных зависимостей по данным. В результате, замаскированная программа значительно сложнее исходной как по управлению, так и по данным.
Мы предполагаем, что перед маскировкой были выполнены все стандартные шаги анализа программы: лексический, синтаксический, семантический, анализ потока управления (построение графа потока управления и деревьев доминирования и постдоминирования) и консервативный глобальный анализ потоков данных (достигающие определения и доступные выражения с учётом возможных алиасов). Дополнительно может быть выполнено профилирование дуг, результаты которого учитываются в преобразованиях клонирования дуг и развёртки циклов.
Общая идея метода может быть охарактеризована следующим образом.
Во-первых, значительно увеличить сложность графа потока управления, но так, чтобы все дуги графа потока управления, внесённые при маскировке, проходились при выполнении программы. Это позволяет преодолеть основную слабость "непрозрачных" предикатов: насколько бы не были они сложны для статического анализа программы, полустатический анализ позволяет выявить такие предикаты (точнее, порождённые ими несущественные дуги графа потока управления) с большой долей уверенности. Во-вторых, увеличить сложность потоков данных маскируемой функции, "наложив" на неё программу, которая заведомо не влияет на окружение маскируемой функции и, как следствие, не изменяет работы программы. "Холостая" функция строится как из фрагментов маски-руемой функции, семантические свойства которых заведомо известны, так и из фрагментов, взятых из библиотеки маскирующего трансля-тора. Чтобы затруднить задачу выявления холостой части замаскиро-ванной функции используются как языковые конструкции, трудно поддающиеся анализу (указатели), так и математические тождества. Метод маскировки можно разбить на несколько этапов:
Увеличение размера графа потока управления функции без нарушения его структурности. На этом этапе выполняются различные преобразо-вания перестройки циклов, которые изменяют структуру циклов в теле функции, клонирование базовых блоков. Цель этого этапа - существенно увеличить размер графа потока управления функции. Разрушение структурности графа потока управления функции. На этом этапе в граф потока управления вносится значительное количество новых дуг. При этом существовавшие базовые блоки могут оказаться разбитыми на несколько меньших базовых блоков. В графе потока управления могут появиться пока пустые базовые блоки. Цель этого этапа - подготовить место, на которое в дальнейшем будет внесён несущественный код. Генерация несущественного кода. На этом этапе граф потока управления заполняется инструкциями, которые не оказывают никакого влияния на результат, вырабатываемый маскируемой программой.
Несущественная, "холостая" часть пока никак не соприкасается с основной, функциональной частью программы. "Зацепление" холостой и основной программы. Для этого исполь-зуются как трудноанализируемые свойства программ (например, указатели), так и разнообразные математические тождества и неравенства. В качестве примера применения предложенного метода маскировки мы выбрали небольшую программу, которая решает задачу о 8 ферзях. Для маскировки мы выберем основную функцию queens этой программы.
| Метрика | queens | MM(queens) | CM(queens) |
| LC | 49 | 711 | 4171 |
| YC | 0.595 | 0.8119 | 0.2402 |
| UC | 0 | 0 | 0 |
| DC | 82 | 8964 | 143807 |
| Преобразование | OC | TC | MC | MC/TC | CL | SL | DL | D |
| MM(queens) | 4 | 29.02 | 110.68 | 3.81 | 5 | 2 | 7 | 3 |
| CM(queens) | ? | 170.24 | 1754.14 | 10.30 | 5 | 2 | 7 | ? |
В таблице 4 в столбце queens приведены базовые метрики сложности кода для исходной процедуры queens; в столбце MM(queens) - для процедуры, замаскированной с помощью предложенного метода маскировки; в столбце CM(queens) - для процедуры, замаскированной с помощью коммерческого маскировщика рассмотренного выше.
В таблице 5 приведены метрики цены применения маскирующего преобразования, усложнения программы требуемой глубины анализа для предложенного метода маскировки MM и для коммерческого маскировщика CM. Для коммерческого маскировщика сложность алгоритма маскировки неизвестна, поэтому в соответствующих ячейках таблицы стоит знак "?". Из таблицы видно, что новый метод маскировки MM существенно дешевле, чем реализованный в коммерческом маскировщике.
О некоторых задачах анализа и трансформации программ
С.С. Гайсарян, А.В. Чернов, А.А. Белеванцев, О.Р. Маликов, Д.М. Мельник, А.В. Меньшикова
Труды
Промежуточное представление
Промежуточное представление MIF используется всеми инструментами интегрированной среды. Оно является представлением среднего уровня и спроектировано таким образом, чтобы представлять программы, написанные на широком спектре процедурных и объектно-ориентированных языков программирования.
Программа в представлении MIF представляет собой последовательность четвёрок, которые используются для представления как декларативной, так и императивной информации о программе. Текстуальное представление MIF используется как интерфейс между анализатором языка и интегрированной средой, а также для хранения анализируемых программ.
Разбиение на нити
На этом шаге производится собственно разбиение графа зависимостей по данным на нити. Количество нитей является параметром алгоритма. Так как целью разбиения является получение выигрыша по времени, возникающего из-за увеличения количества событий локальности в каждой нити, то необходимо привязать каждую нить к одному конкретному процессору или, точнее, к конкретному кэшу. Поэтому количество нитей, на которые производится разбиение, обычно равно количеству процессоров в системе.
Алгоритм разбиения состоит в итерировании списка узлов графа, еще не назначенных конкретной нити, и определения нити для какого-либо из узлов (группы таких алгоритмов обычно называются list scheduling). На каждом шаге такой алгоритм делает локально оптимальный выбор. Это значит, что при выборе очередного узла из списка делается попытка присвоить его каждой из имеющихся нитей, после чего выбирается лучшая.
Для того, чтобы иметь возможность оценивать варианты присвоения узла нити, необходимо ввести некоторую оценочную функцию. В нашем случае такая функция содержит время выполнения нити, а также среднеквадратичное отклонение времен выполнения всех нитей. Это следует из того соображения, что в оптимальном разбиении времена выполнения нитей должны быть достаточно близки друг к другу. Возможно включение и других параметров.
При включении узла в какую-либо нить необходимо провести пересчет вре-мени выполнения этой нити. Алгоритм пересчета состоит из следующих шагов:
Учет времени, необходимого на синхронизацию с другими нитями, если она требуется. Учет возникающих событий локальности.Рассмотрим более подробно каждый из этих шагов.
2.1.3.1. Учет времени на синхронизациюОбрабатываемый на текущем этапе узел может зависеть по данным от некоторых других. В этом случае необходимо дождаться выполнения каждой нити, которые содержит такие узлы. Порядок обхода узлов в списке должен быть таков, чтобы гарантировалось, что все такие узлы уже были распределены на нити. Для этого можно обходить узлы в естественном порядке, то есть так, как они расположены в последовательной программе, либо выполнить тополо-гическую сортировку графа зависимостей по данным.
Еще раз подчеркнем, что иерархичность графа обеспечивает то, что он является ациклическим.
Таким образом, к моменту обработки некоторого узла все узлы, от которых он зависит по данным, уже распределены на нити. Если какие-либо из таких узлов находятся в других нитях, то перед выполнением текущего узла необходимо провести синхронизацию со всеми такими нитями. Для того, чтобы осуществить такую синхронизацию, нужно завести по одной общей переменной для каждой нити. Присваивание значения i такой переменной для некоторой нити j означает, что эта нить выполнила узел i. Нить, ждущая результатов вычисления узла i, должна ждать, пока соответствующая общая переменная не примет нужного значения. Пример такой синхронизации показан на Рис. 2.
Времена выполнения каждой из нитей, проводящих синхронизацию, должны быть увеличены соответствующим образом. Нить, пишущая в общую переменную о результатах выполнения узла, дополнительно работает время t1. Нить, ждущая данных от нескольких узлов, ожидает последний из выполняющихся узлов, после чего тратит время t2. Эти времена являются параметрами алгоритма.
Рис. 2. Пример синзронизации
2.1.3.2. Учет возникающих событий локальности Для учета событий локальности для каждой нити необходимо эмулировать кэш процессора, на котором она выполняется. При распределении текущего узла на какую-либо нить необходимо проверить все переменные, которые читаются либо пишутся узлом, на попадание в кэш. Если попадание произошло, то время выполнения узла должно быть уменьшено на интервал времени t3, также являющийся параметром алгоритма.
Рис. 3. Пример эмулирования кэша
Для учета событий как временной, так и пространственной локальности необходимо моделирование линий кэша, т.е. помещение в кэш не одной переменной, а некоторого блока памяти, окружающего нужную переменную. Моделирование различных типов кэшей приведет к разным результатам при разделении на нити.
Пример моделирования событий локальности изображен на Рис. 3.
Разбиение программ на нити и повышение локальности
В настоящее время широко распространены рабочие станции и персональные компьютеры, содержащие несколько центральных процессоров. Массовые многопроцессорные системы обычно содержат 2, 4 или 8 процессоров, работающих над общей памятью с одинаковым для всех процессоров временем доступа (SMP). Для максимального использования возможностей SMP-систем в вычислительно-интенсивных приложениях необходимо максимально использовать "легковесные" процессы (нити). В этом случае накладные расходы на коммуникацию минимизированы, так как все нити разделяют одно адресное пространство, а синхронизационные операции выполняются проще и быстрее, чем для обычных ("тяжелых") процессов.
Известно, что большинство программ при работе демонстрируют хорошую локальность, т.е. работают над близко расположенными в памяти данными, или выполняют одни и те же инструкции. На этом наблюдении основана работа процессорных кэшей. Для наиболее полного использования возможностей кэша необходимо улучшать локальность программы.
В данном разделе мы представим новый алгоритм для разделения программы на нити, который улучшает локальность программы в целом. Полученные экспериментальные результаты показывают оправданность применения нового алгоритма для разбиения на нити программ без чёткой циклической структуры, которые не могут быть разбиты на нити традиционными методами. Основным выводом работы является то, что соображения локальности должны приниматься во внимание при разделении программы на нити для небольшого числа процессоров.
Системы с разделяемой памятью наиболее удобны для программиста параллельных приложений. Более того, часть работы по распараллеливанию последовательного кода может быть выполнена компилятором. Существует много исследований по автоматическому распараллеливанию циклов и рекурсивных процедур на таких системах. Некоторые разработки реализованы в промышленных компиляторах, например, IBM Visual Age C++, Intel C++ Compiler, SGI MIPSPro, REAPAR и других.
В последнее время проводятся исследования по автоматическому распарал-леливанию любого последовательного кода.
Предложено несколько подходов, таких, как управление выполнением нитей (thread-level speculation) [6], коммутативный анализ, динамическое распределение задач на нити (dynamic task scheduling) [5], автоматическое разделение на нити на этапе компиляции. Часть предложенных алгоритмов проверена авторами на эмуляторах, часть реализована в существующих исследовательских компиляторах, например, в компиляторе SUIF Стенфордского университета [7].
Формализация понятия локальности проведена в [8]. Рассматривается два вида событий локальности:
Событие временной локальности происходит при повторном доступе к ячейке памяти, уже имеющейся в кэше.
Событие пространственной локальности происходит при доступе к ячейке памяти, расположенной в блоке, уже загруженном в кэш при обращении к какой-либо другой ячейке.
Для увеличения количества событий локальности в последнее время предложено большое количество оптимизирующих преобразований программы. Основными методами являются:
Группировка инструкций, использующих одни и те же данные (locality grouping), для увеличения количества событий временной локальности. Упаковка данных в памяти (data packing) для увеличения количества событий пространственной локальности. Перестановка процедур, базовых блоков и т.п.
Целью данной работы является исследование вопроса о том, как может быть проведено разделение программы на потоки для увеличения количества событий локальности программы в целом. Для этого предлагается использовать эвристический алгоритм разделения программы на нити, учитывающий в процессе разделения возникающие события локальности и динамически подстраивающий параметры эвристик.
Результаты экспериментов
Текущий прототип инструментального средства был проверен на нескольких тестовых примерах, как широко распространённых (bftpd), так и являющихся частью приложений, разрабатываемых в фирме Nortel для своего оборудования. Были получены следующие результаты.
| Application | Total number of warnings | Number of "true positives" | Number of "possible errors" | Number of "false positives" | "false positives" % | FlexeLint |
| Bigfoot | 20 | 4 | 3 | 13 | 65% | 0 (0%) |
| Log_api | 4 | 1 | 3 | 0 | 0% | 0 (0%) |
| Bftpd | 57 | 2 | 32 | 23 | 40% | 0 (0%) |
| Config_api | 11 | 9 | 0 | 2 | 18% | 1 (11%) |
Таблица 6. Результаты запуска инструментального средства
В этой таблице, в столбце "Total" приведено общее количество сообщений об обнаруженных ошибках, выведенных нашим инструментальным средством. В столбце "True" дано количество сообщений, указывающих на действительные проблемы в коде. В столбце "Possible" дано количество сообщений, истинность или ложность которых мы не смогли подтвердить из-за недостатка информации о программе. В столбце "False" дано количество ложных срабатываний. Наконец, в столбце "FlexeLint" дано количество истинных сообщений об ошибке, выявленных инструментальным средством FlexeLint.
Как видно из проведённых испытаний, текущий прототип системы для обнаружения уязвимостей защиты демонстрирует очень хорошие результаты. Процент ложных срабатываний оказался намного ниже, чем у других аналогичных инструментальных средств.
Состав среды
Программа на языке Си транслируется в промежуточное представление с помощью компонента "Анализатор Си в MIF". В настоящее время поддерживается стандарт ISO C90 и некоторые расширения GNU. Чтобы обеспечить независимость интегрированной среды от деталей реализации стандартной библиотеки Си для каждой конкретной платформы и обеспечить возможность корректной генерации программы на Си по её внутреннему представлению, анализатор использует собственный набор стандартных заго-ловочных файлов (stdio.h и т. д.). На уровне стандартной библиотеки полностью поддерживается стандарт ISO C90 и некоторые заголовочные файлы POSIX. Внутреннее представление программы находится в памяти инте-грированной среды, но возможно сохранение внутреннего представления в файле.
Компонент "Генератор MIF ->C" позволяет по программе во внутреннем представлении получить программу на языке Си. При генерации программы корректно генерируются директивы #include для всех использованных в исходной программе системных заголовочных файлов. Для проведения полустатического анализа программ генератор поддерживает несколько типов инструментирования программы. Инструментирование программы заключается во внесении в ее текст специальных операторов, собирающих информацию о ходе выполнения программы. В настоящее время генератор поддерживает инструментализацию программы для сбора полных трасс выполнения программы, профилирование базовых блоков и дуг, профилирование значений. Собранные в результате выполнения инструментированной программы профили выполнения могут впоследствии использоваться для анализа и преобразования программ.
Компоненты "Анализаторы" реализуют различные методы статического и полустатического анализа программ. При этом сама программа не трансформируется, а во внутреннее представление программы добавляется полученная в результате выполнения анализа информация. В интегрированной среде эти компоненты доступны посредством пункта меню Analyze. Например, алгоритм разбиения программы на базовые блоки, доступный через пункт меню Mark basic blocks, строит граф потока управления программы, создаёт соотвествующие структуры данных в памяти системы и добавляет ссылки на построенный граф в структуры данных внутреннего представления программы.
Компоненты "Трансформаторы" реализуют различные преобразования программ. При этом результатом работы компонента трансформации является новая программа во внутреннем представлении, для которой в интегрированной среде создаётся новое окно. Исходная программа сохраняется неизменной. Трансформационные компоненты доступны в интегрированной среде посредством пунктов меню Optimize, Transform и Obfuscate в зависимости от класса преобразования.
Компоненты "Визуализаторы" реализуют различные алгоритмы визуализации информации о программе. Эти компоненты доступны посредством пункта меню Vizualize интегрированной среды.
Виды уязвимостей защиты
В настоящее время сложилась некоторая классификация уязвимостей защиты в зависимости от типа программных ошибок, которые могут приводить к появлению уязвимости в программе. В рамках данной работы мы рассмотрим лишь некоторые виды уязвимостей.
Переполнение буфера (buffer overflow). Данная уязвимость возникает как следствие отсутствия контроля или недостаточного контроля за выходом за пределы массива в памяти. Языки Си/Си++, чаще всего используемые для разработки программного обеспечения системного уровня, не реализуют авто-матического контроля выхода за пределы массива во время выполнения программы. Это самый старый из известных типов уязвимостей (знаменитый червь Морриса использовал, среди прочих, уязвимости переполнения буфера в программах sendmail и fingerd), уязвимости такого типа наиболее просто использовать.
По месту расположения буфера в памяти процесса различают переполнения буфера в стеке (stack buffer overflow), куче (heap buffer overflow) и области статических данных (bss buffer overflow). Все три вида переполнения буфера могут с успехом быть использованы для выполнения произвольного кода уязвимым процессом. Так, упомянутая выше программа rsync содержала уязвимость буфера в куче. Рассмотрим для примера более детально уязвимость переполнения буфера в стеке как наиболее простую на примере следующей простой программы:
#include < stdio.h> int main(int argc, char **argv) { char buf[80]; gets(buf); printf("%s", buf); return 0; }Предположим, что стек процесса растёт в направлении уменьшения адресов памяти. В таком случае непосредственно перед выполнением функции gets стек будет иметь следующую структуру:
| SP+96 | Аргументы командной строки, переменные окружения и т. д. |
| SP+88 | Аргументы функции main (argc, argv) |
| SP+84 | Адрес возврата из main в инициализационный код |
| SP+80 | Адрес предыдущего стекового фрейма |
| SP+80 | Сохранённые регистры (если есть), локальные переменные (если есть) |
| SP | Буфер (char buf[80]) |
Как известно, функция gets не позволяет ограничивать длину вводимой со стандартного потока ввода строки.
Вся введённая строка до символа '\n', кроме него самого, будет записана в память по адресам, начинающимся с адреса массива buf. При этом, если длина введённой строки превысит 80 символов, то первые 80 символов строки будут размещены в памяти, отведённой под массив buf, а последующие символы будут записаны в ячейки памяти, непосред-ственно следующие за buf. То есть, таким образом будут испорчены сначала сохранённые регистры и локальные переменные, затем адрес предыдущего стекового фрейма, затем адрес возврата из функции main и т. д. В момент, когда функция main будет завершаться с помощью оператора return, процессор выполнит переход по адресу, хранящемуся в стеке, но этот адрес испорчен в результате выполнения функции gets, поэтому переход произойдёт совсем в другое место, чем стандартный код завершения процесса.
Теперь, чтобы проэксплуатировать такое переполнение буфера, необходимо подать на вход программе специальным образом подготовленную строку, которая будет содержать небольшую программу, выполняющую нужные злоумышленнику действия (это так называемый shellcode, который в простейшем случае просто выполняет вызов стандартного командного интерпретатора /bin/sh). Кроме того, нужно так подобрать размер подаваемых на вход данных, чтобы при их чтении на место, где размещается адрес возврата из main, попал адрес начала shellcode. В результате в момент завершения работы функции main произойдёт переход на начало фрагмента shellcode, в результате чего будет запущен интерпретатор командной строки. Интерпретатор командной строки будет иметь полномочия пользователя, под которым работал уязвимый процесс, кроме того, стандартные средства аутентификации оказываются обойденными.
Для предотвращения выполнения произвольного кода в случае использования переполнения буфера используются такие приёмы, как запрет выполнения кода в стеке, отображение стандартных библиотек в адресное пространство процесса со случайных адресов, динамический контроль барьерных данных и так далее. Но не один из этих приёмов не может гарантировать предотвращения использования уязвимости переполнения буфера в стеке, поэтому ошибки приводящие к переполнению буфера должны быть устранены непосредственно в исходном коде.
Ошибки форматных строк (format string vulnerability). Этот тип уязвимостей защиты возникает из-за недостаточного контроля параметров при использо-вании функций форматного ввода-вывода printf, fprintf, scanf, и т. д. стандартной библиотеки языка Си. Эти функции принимают в качестве одного из параметров символьную строку, задающую формат ввода или вывода последующих аргументов функции. Если пользователь программы может управлять форматной строкой (например, форматная строка вводится в программу пользователем), он может сформировать её таким образом, что по некоторым ячейкам памяти (адресами которых он может управлять) окажутся записанными указанные пользователем значения, что открывает возможности, например, для переписывания адреса возврата функции и исполнения кода, заданного пользователем.
Уязвимость форматных строк возникает, по сути, из-за того, что широко используемые в программах на Си функции, интерпретируют достаточно мощный язык, неограниченное использование возможностей которого приводит к нежелательным последствиям. Как следствие, в безопасной программе не должно быть форматных строк, содержимое которых прямо или косвенно зависит от внешних по отношению к программе данных. Если же такое невозможно, при конструировании форматной строки она должна быть тщательно проверена. В простейшем случае из пользовательского ввода должны "отфильтровываться" опасные символы "%" и "$".
Уязвимости "испорченного ввода" (tainted input vulnerability). Это широкий класс уязвимостей защиты, в качестве подкласса включающий в себя уязвимости форматных строк. Уязвимости испорченного ввода могут возникать в случаях, когда вводимые пользователем данные без достаточного контроля передаются интерпретатору некоторого внешнего языка (обычно это язык Unix shell или SQL). В этом случае пользователь может таким образом задать входные данные, что запущенный интерпретатор выполнит совсем не ту команду, которая предполагалась авторами уязвимой программы.
Рассмотрим следующий пример:
#include < stdio.h>
#include < stdlib.h>
int main(void) { char buf[80], cmd[100]; fgets(buf, sizeof(buf), 80); snprintf(cmd, sizeof(cmd), "ls -l %s", buf); system(cmd); return 0; }
В этом примере ожидается, что пользователь программы вводит имя файла, а программа вызывает стандартную программу ls, которая печатает информацию о введённом файле. При этом для вызова программы ls командная строка передаётся интерпретатору командной строки /bin/sh. Это можно использовать если ввести в программу строку, содержащую, например, символ ; (точка с запятой), например "myfile ; rm -rf /". Строка, фактически переданная интерпретатору командной строки будет равна "ls -l myfile ; rm -rf /", то есть фактически будет состоять из двух команд интерпретатора shell, а не из одной, при этом вторая команда - это запрос на удаление всей файловой системы.
Как и в случае уязвимости форматной строки, достаточное условие отсутствия уязвимости типа испорченного ввода в программе состоит в том, что "опасные" аргументы "опасных" функций никак не должны зависеть от внешних по отношению к программе данных.
Кроме перечисленных здесь типов уязвимостей защиты существуют и другие типы, например - уязвимости как следствие синхронизационных ошибок (race conditions), некорректная работа с временными файлами, слабое шифрование и другие классы уязвимостей. В рамках данной работы мы остановимся лишь на трёх перечисленных выше типах.
Механизм контрольных точек
В среде ParJava реализован инструмент “CheckPoints”, реализующий механизм контрольных точек, который позволяет существенно сократить объемы сохраняемых данных и время на их сохранение.
Реализация механизма контрольных точек для параллельной программы является нетривиальной задачей. Параллелизм усложняет процесс установки точек останова, т. к. сообщения порождают связи между отдельными процессами, и приходится обеспечивать так называемые консистентные состояния. Состояние двух процессов называется неконсистентным, если при передаче сообщения одного процесса другому, может возникнуть состояние, когда первый процесс еще не послал сообщение, а во втором уже сработала функция получения сообщения. Если в таком состоянии поставить точку останова, то восстановив впоследствии контекст задачи, мы не получим ее корректной работы.
Пользователь указывает в программе место сохранения данных с помощью директивы EXCLUDE_HERE. В контрольной точке 1 (рис. 4) не сохраняются данные, которые будут обновлены до своего использования («мертвые» переменные). В контрольной точке 2 не сохраняются данные, которые используются только для чтения до этой контрольной точки. Результатом будет значительное уменьшение размеров сохраняемых данных в контрольной точке и уменьшение накладных расходов на их сохранение.
Рис. 4. Контрольные точки
Вначале граф потока управления G=(N, E) разбивается на подграфы G?. Корнем каждого подграфа G? является директива EXCLUDE_HERE. Подграф включает все пути, достижимые из этой директивы, не проходящие через другую директиву EXCLUDE_HERE.
Для каждого подграфа вычисляются 2 множества переменных: DE(G?) - множество переменных, которые «мертвы» на каждой директиве EXCLUDE_HERE в G? и RO(G?) - множество переменных, предназначенных только-для-чтения по всему подграфу G?.
Для нахождения множеств DE(G?) и RO(G?) используется консервативный анализ потока данных. В каждом состоянии S в программе вычисляются два множества характеризующие доступ к памяти: use[S] – множество переменных, которые могут быть использованы вдоль некоторого пути в графе, и def[S] – множество переменных, которым присваиваются значения до их использования вдоль некоторого пути в графе, начинающегося в S, или множество определений переменных.
Ячейка памяти l является «живой» в состоянии S, если существует путь из S в другое состояние S? такой, что l
use[S?] и для каждого S?? на этом пути l
def[S??].
Ячейка l является элементом DE(G?), если l «мертвая» во всех операторах сохранения контрольных точек в G?. Ячейка памяти l является ячейкой только-для-чтения в операторе S, если l
use[S]. Поэтому l RO(G?) тогда и только тогда, когда lgen[S] для всех S в G?. Эти определения консервативны, поскольку они ищут все возможные пути через граф потока управления, тогда как некоторые из них могут никогда не достигнуть выполнения в программе. Анализ «живых» переменных обычно выражается в виде уравнений потока данных, по одному на каждое состояние в программе. Мы дадим уравнение потока данных, которое позволит нам определить DE(G?) и RO(G?) для каждого подграфа G? в программе. Каждое из этих уравнений может быть решено обычным итеративным методом. Для достижения нашей цели уравнение потока данных характеризуем его функцией обновления. Такая функция ассоциируется с каждым состоянием S. Определим in[S] как множество мертвых переменных в точке непосредственно перед блоком S, а out[S] – такое же множество в точке, непосредственно следующей за блоком S. Вычисляем множество мертвых переменных в направлении обратном графу потока управления. Система уравнений выглядит следующим образом: out[S] = ?S? in[S?] in[S] = FS, где out[S] = ?S? DEAD[S?] – это пересечение множества мертвых переменных для всех состояний S?, которые являются преемниками S в G, а FS – это функция обновления, которая в нашем случае равна FS = out[S] 
gen[S] – use[S] и свидетельствует о переменных, которые мертвы непосредственно перед S и тех переменных, которые стали мертвыми после S, плюс о тех, в которые производилась запись в состоянии S, минус любые ячейки, с которых происходило чтение в S. При следующем запуске эти массивы и параметры загружаются, и по ним полностью восстанавливается контекст прерванной задачи.
Механизмы времени выполнения среды ParJava
Для обеспечения возможности использования среды Java на высокопроизводительных кластерных системах были реализованы стандартная библиотека MPI и механизм контрольных точек.
Модель параллельной Java-программы и ее интерпретация
Модель SPMD-программы представляет собой совокупность моделей всех классов, входящих в состав моделируемой программы. Модель каждого класса – это множество моделей всех методов этого класса; кроме того, в модель класса включается модель еще одного дополнительного метода, описывающего поля класса, его статические переменные, а также инициализацию полей и статических переменных. Модель метода (функции) состоит из списка описаний локальных и глобальных переменных метода и модифицированного абстрактного синтаксического дерева метода: внутренние вершины модели соответствуют операторам языка Java, а листовые – базовым блокам. В качестве базовых блоков рассматриваются не только линейные последовательности вычислений (вычислительные базовые блоки), но также и вызовы библиотечных функций, вызовы пользовательских методов и функций и вызовы коммуникационных функций. Для обеспечения возможности интерпретации модели по частям введено понятие редуцированного блока, который представляет значения динамических атрибутов уже проинтерпретированных частей метода.
Каждый MPI-процесс моделируемой программы представляется в ее модели с помощью логического процесса, который определен как последовательность действий (примеры действий: выполнение базового блока, выполнение операции обмена и т.п.). Каждое действие имеет определенную продолжительность. В логическом процессе определено понятие модельных часов. Начальное показание модельных часов каждого логического процесса равно нулю. После интерпретации очередного действия к модельным часам соответствующего логического процесса добавляется значение времени, затраченного на выполнение этого действия (продолжительности). Продолжительность каждого действия, а также значения исследуемых динамических параметров базовых блоков, измеряются заранее на целевой платформе.
Для идентификации логических процессов используются номера моделируемых процессов, использованные в моделируемой программе при описании коммуникатора MPI (будем называть их пользовательскими номерами процессов).
Как известно, для удобства программирования приложений в стандарте MPI реализована возможность задавать коммуникаторы, позволяющие задавать виртуальные топологии сети процессоров, описывая группы процессов. В среде ParJava коммуникаторы, заданные программистом, отображаются на MPI_COMM_WORLD, получая, тем самым, наряду с пользовательскими номерами внутренние номера. Все инструменты среды ParJava работают с внутренними номерами процессов, но при выдаче сообщений пользователю эти номера переводятся в пользовательские. В дальнейшем, при упоминании номера логического процесса будет подразумеваться его внутренний (системный) номер. Внутренний номер используется для доступа к логическому процессу при моделировании коммуникационных функций. Для сокращения времени интерпретации и обеспечения возможности выполнения интерпретации на инструментальном компьютере в среде ParJava моделируются только потоки управления процессов моделируемой программы и операции обмена данными между процессами. Это допустимо, так как значения времени выполнения и других исследуемых динамических атрибутов базовых блоков определяются на целевой вычислительной системе до начала интерпретации модели. Интерпретация модели лишь распространяет значения указанных динамических атрибутов на остальные узлы модели. Такой подход позволяет исключить из моделей базовых блоков переменные, значения которых не влияют на поток управления моделируемой программы. В результате часть вычислений, в которых определяются и используются указанные переменные, становится «мертвым кодом» и тоже исключается, что ведет к сокращению, как объема обрабатываемых данных, так и общего объема вычислений во время интерпретации. В некоторых базовых блоках описанный процесс может привести к исключению всех вычислений, такие базовые блоки заменяются редуцированными блоками. Внутреннее представление модели SPMD-программы разрабатывалось таким образом, чтобы обеспечить возможность возложить как можно большую часть функций интерпретатора на JavaVM.
Такое решение позволило существенно упростить реализацию интерпретатора и обеспечить достаточно высокую скорость интерпретации, однако для его реализации потребовалось внести некоторые структурные изменения в модель параллельной программы. Внутреннее представление модели базового блока B представляет собой пару <DescrB, BodyB>, где DescrB – дескриптор блока B (т.е. семерка <id, ?, P, IC, OC, Time, A>, где id – уникальный идентификатор базового блока, присваиваемый ему при построении модели, ? – тип базового блока, P – ссылка на модель его тела, IC – множество входных управляющих переменных, OC – множество выходных управляющих переменных, Time – время выполнения базового блока, A – ссылка на список остальных его атрибутов), а BodyB – модель тела блока B (список выражений на байт-коде, вычисляемых в блоке B). Внутреннее представление модели метода определяется как тройка <дескриптор метода, модель потока управления, модель вычислений>. Дескриптор метода содержит сигнатуру метода, список генерируемых методом исключений, список дескрипторов формальных параметров и ссылки на модель потока управления и модель вычислений. Модель потока управления – это модифицированное АСД, описанное в [], в котором базовые блоки представлены своими дескрипторами. Модель вычислений – это преобразованный байт-код интерпретируемой Java-программы: все базовые блоки модели вычислений включены в состав переключателя, значение управляющей переменной которого определяет номер очередного интерпретируемого базового блока. Интерпретация модели состоит в выполнении Java-программы, определяющей модель вычислений на JavaVM: в интерпретаторе модели потока управления определяется очередное значение управляющей переменной переключателя модели вычислений, после чего интерпретируется модель соответствующего базового блока. Интерпретация модели базового блока определяется его типом. Для блоков типа «вычислительный блок» (время выполнения таких базовых блоков определяется заранее на целевой платформе) вносится соответствующее изменение во временной профиль метода, и управление возвращается в модель вычислений.
Для блоков типа «вызов пользовательской функции», управление возвращается в модель вычислений, где вызывается модель вычислений этого метода. Во время выполнения вызванной модели вычислений в стек помещается текущее состояние, и подгружаются необходимые структуры данных. После интерпретации метода из стека извлекается состояние на момент вызова пользовательской функции и продолжается выполнение модели вычислений первой функции. Для блоков типа «вызов коммуникационной функции», управление возвращается в модель вычислений, где вызывается модель соответствующей коммуникационной функции, которая помимо выполнения передачи данных между логическими процессами обеспечивает вычисление оценки времени выполнения коммуникации и внесение соответствующих изменений во временной профиль. При интерпретации блоков типа «редуцированный блок» (динами-ческие атрибуты таких блоков уже определены и они не интерпретируются), возврат в модель вычислений не происходит; вносятся изменения во временной профиль, и выполняется поиск следующего базового блока.
Моделирование процесса зарождения торнадо
В Институте физики Земли РАН была разработана математическая модель развития торнадо в трехмерной сжимаемой сухоадиабатической атмосфере. Большой объем вычислений для получения численного решения потребовал реализации программы на высокопроизводительных вычислительных кластерах. Рассматриваемая система уравнений является сильно нелинейной системой смешанного типа. Для решения системы использовалась явная разностная условно-устойчивая схема второго порядка точности по времени и пространству; критерии ее устойчивости оказались близкими к явной схеме Маккормака.
Программа разработана в Институте системного программирования РАН в сотрудничестве с Институтом физики Земли РАН с использованием среды ParJava и предназначена для выполнения на кластерных вычислительных системах.
Программу можно разделить на два блока: загрузка/инициализация данных и главный цикл. Сохранение результатов происходит во время выполнения главного цикла. Входные данные хранятся в файле, где перечислены физические параметры модели и вспомогательные данные для работы программы, например, количество выдач значимых результатов и пути.
Для выявления возможностей распараллеливания циклы были исследованы при помощи Омега теста, реализованного в среде ParJava, который показал отсутствие зависимостей по данным между элементами массивов, обрабатываемых в циклах. Это позволило разделить массивы на блоки и распределить полученные блоки по процессорам кластера. Поскольку разностная схема является трехточечной, возникают теневые грани ширины в один пространственный слой. На текущей итерации используются только данные, вычисленные на предыдущих итерациях. Это позволяет обновлять теневые грани один раз при вычислении каждого слоя, что снижает накладные расходы на пересылку. Исследования на интерпретаторе показали, что двумерное разбиение массивов наиболее эффективно, поэтому в программе использовалось двумерное разбиение. Вариант с трехмерным разбиением оказался не самым оптимальным из-за неоднородности вычислений по оси Z.
Как показано в разд. 2, для данного класса задач необходимо использовать коммуникационный шаблон с использованием неблокирующих коммуникаций.
Так как программа моделирования торнадо – это программа с большим временем счета: 300 секунд жизни торнадо на кластере МСЦ (64 вычислителя Power 2,2 GHz, 4 GB) рассчитывались около недели, ? и большим объемом генерируемых данных, использовался механизм контрольных точек.
На рис. 5 приводятся графики ускорения программы при блокирующих и неблокирующих обменах данными. При тестировании производительности использовались начальные данные рабочей задачи, но вычислялись только первая секунда жизни торнадо.
Рис. 5. График ускорения.
Данные результаты вычислений использовались в исследовании процесса зарождения торнадо и они продемонстрировали адекватность используемой модели и возможность использования среды ParJava для разработки такого рода приложений.
Более подробно результаты моделирования торнадо рассматриваются в работе [22].
Моделирование теплового движения молекул воды и ионов в присутствии фрагмента ДНК
Для моделирования теплового движения молекул воды и ионов в присутствии фрагмента ДНК методом Монте-Карло существовала параллельная программа, написанная на языке Fortran с использованием MPI. Биологические и математические аспекты задачи и программы описаны в работе [23]. В параллельной программе исходное пространство, заполненное молекулами, разделяется на равные параллелепипеды по числу доступных процессоров. Процессоры проводят испытания по методу Монте-Карло над каждой молекулой. Решение о принятии новой конфигурации принимается на основе вычисления изменения энергии. Для вычисления изменения энергии на каждом шаге производится выборка соседей, вклад которых учитывается при вычислении. После того как процессоры перебирают все молекулы, производится обмен данными между процессорами, моделирующими соседние области пространства.
Исходная Fortran-программа требовала для моделирования реальных систем большого числа процессоров (от 512) и могла выполняться только на количестве процессоров, равному кубу натурального числа, то есть на 8, 27, 64 и т.д. процессорах. Это приводило к увеличению времени, необходимого для моделирования одной системы. Главная проблема заключалась в кубическом росте количества перебираемых молекул при выборе соседей, с увеличением количества молекул, моделируемых на одном процессоре.
В среде ParJava была реализована аналогичная программа на языке Java с использованием MPI. Исследование производительности Java-программы позволило выявить причину неэффективной работы Fortran-программы. Для сокращения объема вычислений при построении списка соседей были предложены и реализованы две модификации. Основная модификация заключалась во введении дополнительного разделения молекул по пространству. Это позволило уменьшить количество перебираемых молекул и сократить объем вычислений при построении списка соседей.
Для оценки эффективности произведенных модификаций сравнивались три программы. Исходная Fortran-программа с использованием MPI, сравнивалась с двумя Java-программами, также использующими MPI.
Первая Java-программа включает в себя только одну модификацию, заключающуюся в использовании одного набора соседей при вычислении энергии для текущего и измененного положения молекулы. Во второй программе, дополнительно было реализовано разбиение на поддомены. Обе Java-программы можно запускать на произвольном числе процессоров, с одним ограничением: по каждому из направлений исходная ячейка должна быть разделена хотя бы на 2 домена. Для сравнения производительности была проведена серия тестов с разным числом вычислителей. Объем задачи увеличивался с ростом числа вычислителей таким образом, чтобы на каждом вычислителе был одинаковый объем данных. На 8 вычислителях моделировалась кубическая ячейка с ребром 100 ангстрем, а на 64 вычислителях ребро ячейки составляло 200 ангстрем, при этом каждый вычислитель моделировал 4166 молекул. В процессе моделирования над каждой из молекул проводилось по 1000 испытаний. Результаты измерения, приведенные на рис. 6, получены на кластере ИСП РАН, состоящем из 12 узлов (2 х Intel Xeon X5355, 4 ядра), объединенных сетью Myrinet. Число MPI-процессов соответствовало числу ядер, каждое из которых может рассматриваться как отдельный вычислитель. Для Fortran-программы измерения производились с использованием 8, 27 и 64 ядер. Для Java-программ измерения производились с использованием 8, 12, 16, 24, 27, 32, 36, 40, 48, 56, 64 ядер.
Рис. 6. Сравнение исходной программы на языке FORTRAN77 c модифицированными программами на языке Java. Из графика видно, что при равных объемах данных первая модифицированная программа на Java работает в 1,5 раза быстрее, а вторая в 2-3 раза, при этом удалось сохранить точность расчета. Программа на Java, в точности соответствующая исходной программе на языке Фортран, требовала от 10 до 30% больше времени и имела аналогичную форму графика производительности. Исследование и модификация программы в среде ParJava позволило увеличить объем решаемой задачи с полным сохранением свойств модели. Модифицированная программа позволила смоделировать на 128 вычислителях кластера МСЦ фрагмент В-ДНК, состоящий из 150 пар нуклеотидов (15 витков двойной спирали, 9555 атомов) и водную оболочку, содержащую ионы Cl- и Na+.Ячейки, включавшая этот фрагмент, имела размер в 220A, и он содержал ~300 тысяч молекул воды. Время работы программы 9 часов, за это время над ионами и молекулами воды было произведено по 10000 элементарных испытаний. Более подробно результаты моделирования теплового движения молекул воды и ионов в присутствии фрагмента ДНК приводятся в работе [24].
Направления дальнейших исследований
В настоящем разделе рассматриваются дальнейшие работы по параллельному программированию. Ставится цель разработать методы и реализовать соответствующие инструментальные средства, позволяющие в автоматическом режиме выявлять потенциальный параллелизм, генерировать параллельный код и осуществлять доводку полученного кода с учетом особенностей выбранной аппаратуры (кластер, система с общей памятью, кластер с многоядерными узлами).
Для анализа и трансформации гнезд циклов, в которых все индексные выражения и границы циклов задаются аффинными формами относительно индексов массивов, будет разработана инфраструктура, базирующаяся на декларативном представлении гнезд циклов в виде выпуклых многогранников в пространстве индексов. Такое представление существенно снижает накладные расходы на анализ и трансформацию гнезд циклов, так как позволяет выполнять их с помощью операций над матрицами. В составе инфраструктуры будет реализован набор методов (API), реализующих семь базовых трансформаций циклов (любая трансформация цикла является их суперпозицией), а также методы, позволяющие определять зависимости по данным, выявлять шаблоны доступа к памяти, вычислять границы циклов при изменении порядка циклов в гнезде и др. Кроме того, будет разработана и реализована подсистема преобразования императивного представления (байт код) программы в декларативное, а также подсистема преобразования декларативного представления в параллельные программы для систем с распределенной памятью (Java+MPI) или для систем с общей памятью (Java-треды). Будет исследован круг вопросов связанных с генерацией эффективного кода в модели, когда каждый процесс MPI является многотредовым. Будет проведен сравнительный анализ такой реализации с реализацией на Java+MPI на кластерах с многоядерными узлами.
Будет разработан инструмент, позволяющий в автоматическом режиме подбирать коммуникационные примитивов с использованием методики, рассмотренной в разделе 2. В основе инструмента многократная интерпретация модели разрабатываемой параллельной программы.
Для обеспечения многократной интерпретации в приемлемое время будет реализована возможность автоматической генерации «скелета» реального приложения. Будут исследованы произвольные (не аффинные) гнезда циклов и разработаны инструментальные средства, позволяющие распараллеливать их в диалоговом режиме: инструмент для выяснения наличия зависимостей по данным между итерациями цикла с помощью синтетического Омега-теста и инструменты для вычисления вектора направлений и вектора расстояний между, характеризующих зависимости между итерациями гнезда циклов. В последнее время получили распространение специализированные устройства, обеспечивающие высокую степень параллелизма. Одним из классов таких устройств являются графические акселераторы. При стоимости и энергопотреблении, сравнимыми с процессорами архитектуры x86-64, они превосходят их по пиковой производительности на операциях с плавающей точкой и пропускной способности памяти приблизительно на порядок. Большой интерес вызывают исследования возможности использования неоднородных вычислительных архитектур, включающих универсальные процессоры и акселераторы для решения задач, не связанных непосредственно с обработкой графики. Для разработки программ для таких гибридных систем в настоящее время используется модель программирования CUDA, первоначально разработанная для акселераторов Nvidia. Она точно отражает организацию оборудования, что позволяет создавать эффективные программы, но в то же время требует от разработчика хорошего понимания архитектуры акселератора, а перенос существующего кода для выполнения на акселераторе с помощью CUDA обычно требует значительных модификаций. Соответственно, актуальной является задача разработки технологий компиляции, позволяющих упростить написание эффективных программ и перенос существующего кода на графические акселераторы. Для этого предлагается определить набор прагм, позволяющих выделить участки кода, которые должны быть скомпилированы для выполнения на акселераторе. Чтобы быть разумной альтернативой более низкоуровневым средствам, такой набор расширений должен быть достаточно гибким, чтобы позволять улучшать производительность кода за счёт тонкой настройки конфигурации потоков выполнения и распределения данных в иерархии памяти акселератора.В то же время, реализованные средства должны позволять последовательный перенос программного кода на акселератор с минимальными изменениями в исходных кодах и процессе компиляции. Реализацию предлагается осуществить в компиляторе GCC, который является де-факто стандартным компилятором для операционной системы Linux, поддерживает несколько входных языков (C, C++, Fortran, Java, Ada и другие) и позволяет генерировать код для множества архитектур. В GCC уже реализованы OpenMP 3.0 и система анализа зависимостей и трансформации циклов GRAPHITE, что является существенной частью необходимой для такого проекта инфраструктуры.
Обеспечение высокопродуктивного программирования для современных параллельных платформ
, , , http://www.ispras.ru/groups/ctt/parjava.html
Труды Института системного программирования РАН
, , , http://www.ispras.ru/groups/ctt/parjava.html
Труды Института системного программирования РАН
, , , http://www.ispras.ru/groups/ctt/parjava.html
Труды Института системного программирования РАН
Аннотация. В настоящей статье описываются некоторые перспективные направления исследований по высокопродуктивному программированию для параллельных систем с распределенной памятью, проводимые в отделе компиляторных технологий Института системного программирования РАН. Обсуждаются текущие исследования и направления будущих работ, связанных с высокопродуктивным программированием многоядерных и гетерогенных систем.
Приложения среды ParJava
В этом разделе описываются результаты применения разработанной методологии поддержки разработки параллельных программ на примере создания программ моделирования интенсивных атмосферных вихрей (ИАВ) и моделирования теплового движения молекул воды и ионов в присутствии фрагмента ДНК.
Реализация стандартной библиотеки MPI для окружения Java
Первой задачей, которую было необходимо решить при разработке среды ParJava, была эффективная реализация стандартной библиотеки MPI для окружения Java. В настоящее время известно несколько реализаций библиотеки MPI для окружения Java, но ни одна из этих реализаций не обеспечивает достаточно эффективных обменов данными. Кроме того, в них реализованы не все функции библиотеки MPI. Поэтому для среды ParJava была разработана оригинальная реализация библиотеки MPI для окружения Java – библиотека mpiJava.
В настоящее время в библиотеке mpiJava поддерживаются все функции стандарта MPI 1.1, а также параллельные операции ввода-вывода из стандарта MPI 2.
Библиотека mpiJava реализована путем «привязки» (binding) к существующим реализациям библиотеки MPI с помощью интерфейса JNI по аналогии с «привязкой» для C++, описанной в стандарте MPI 2.
Начиная с версии 1.4, в Java поддерживаются прямые буферы, содержимое которых может находиться в памяти операционной системы (вне кучи Java). Использование прямых буферов при передаче данных позволяет избежать лишних копирований данных. Это позволяет сократить накладные расходы на передачу данных.
Средства разработки параллельных приложений в среде Java
Среда ParJava позволяет выполнять большую часть разработки параллельной Java-программы на инструментальном компьютере. Для этого используется модель параллельной Java-программы [], интерпретируя которую на инструментальном компьютере можно получить оценки времени выполнения программы на заданном кластере (кластер определяется числом узлов, параметрами платформы, используемой в качестве его узлов, и параметрами его коммуникационной сети), а также оценки других динамических атрибутов программы, построить модели ее профилей и трасс. Полученная информация о динамических свойствах параллельной программы позволяет оценить границы ее области масштабируемости, помогает прикладному программисту вручную оптимизировать программу, проверяя на интерпретаторе, как отразились произведенные изменения на ее масштабируемости. Возможность использования инструментального компьютера для оптимизации и доводки параллельной программы избавляет программиста от большей части отладочных запусков программы на целевой вычислительной системе, сокращая период отладки и доводки программы.
Технологический процесс разработки параллельных программ в среде ParJava
В рамках среды ParJava разработан и реализован ряд инструментальных средств, которые интегрированы с открытой средой разработки Java-программ Eclipse []. После подключения этих инструментальных средств к Eclipse, получилась единая среда разработки SPMD-программ, включающая как инструменты среды ParJava, так и инструменты среды Eclipse: текстовый редактор, возможность создания и ведения проектов, возможность инкрементальной трансляции исходной программы во внутреннее представление. Интеграция в среду Eclipse осуществлена с помощью механизма «подключаемых модулей».
При разработке параллельной программы по последовательной программе сначала оценивается доля последовательных вычислений, что позволяет (с помощью инструмента “Speed-up”) получить оценку максимального потенциально достижимого ускорения в предположении, что все циклы, отмеченные прикладным программистом, могут быть распараллелены. Затем с использованием инструмента “Loop Analyzer” среды ParJava циклы исследуются на возможность их распараллелить.
Для распараллеленных циклов с помощью инструмента “DataDistr” подбирается оптимальное распределение данных по узлам вычислительной сети. В частности, для гнезд циклов, в которых все индексные выражения и все границы циклов заданы аффинными формами, инструмент “DataDistr” позволяет с помощью алгоритма [] найти такое распределение итераций циклов по процессорам, при котором не требуется синхронизаций (обменов данными), если, конечно, требуемое распределение существует (см. ниже пример 1). В этом случае инструмент “DataDistr” выясняет, можно ли так распределить итерации цикла по узлам, чтобы любые два обращения к одному и тому же элементу массива попали на один и тот же процессор. Для этого методом ветвей и сечений находится решение задачи целочисленного линейного программирования, в которую входят ограничения на переменные циклов, связанные с необходимостью оставаться внутри границ циклов, и условия попадания на один и тот же процессор для всех пар обращений к одинаковым элементам массива.
Задача решается относительно номеров процессоров, причем для удобства процессоры нумеруются с помощью аффинных форм (т.е. рассматривается многомерный массив процессоров). Если оказывается, что для обеспечения сформулированных условий все данные должны попасть на один процессор, это означает, что цикл не может выполняться параллельно без синхронизации. В последнем случае инструмент “DataDistr” может в диалоговом режиме найти распределение данных по узлам, требующее минимального числа синхронизаций при обменах данными. Для этого к условиям сформулированной задачи линейного программирования добавляются условия на время обращений к одним и тем же элементам массива: например, в случае прямой зависимости, требуется, чтобы обращение по записи выполнялось раньше, чем обращение по чтению. В частности, при решении дополнительных временных ограничений, может оказаться, что они могут быть выполнены, если обрабатываемые в программе массивы будут разбиты на блоки. При этом смежные блоки должны быть распределены по процессорам «с перекрытием», чтобы все необходимые данные были на каждом из процессоров. При этом возникают так называемые теневые грани (т.е. части массива, используемые на данном процессоре, а вычисляемые на соседнем процессоре). Ширина теневых граней определяется алгоритмом решения задачи и определяет фактический объем передаваемых в сети сообщений. Количество теневых граней зависит выбора способа нумерации процессоров: априорно выгоднее всего, чтобы размерность массива процессоров совпадала с размерностью обрабатываемых массивов данных. Однако в некоторых случаях оказывается более выгодным, чтобы размерность массива процессоров была меньше, чем размерность обрабатываемых массивов данных. Пример 1. В качестве примера работы инструмента “DataDistr” рассмотрим цикл: for (i = 1; i
Для приведенного примера инструмент “DataDistr” выдаст следующее распределение: X[1,100] = X[1,100] + Y[0,100]; /*s1*/ for (p = -99; p = 0) Y[p+l,l] = X[p+l,0] + Y[p+l,l]; /*s2*/ for (i = max(l,p+2); i
где p – номер вычислителя, а цикл по p определяет распределение данных по вычислителям.
Таким образом, исходный цикл расщепился на 200 цепочек вычислений, каждая из которых может выполняться независимо. После того, как данные распределены по вычислителям, прикладному программисту необходимо выбрать такие операции обмена данными и так трансформировать свою программу, чтобы добиться максимально возможного перекрытия вычислений и обменов данными. Среда ParJava позволяет решать этот вопрос в диалоговом режиме, используя интерпретатор параллельных программ (инструмент “Interpreter”). В тривиальных случаях даже использование стандартных коммуникационных функций (MPI_send, MPI_receive) позволяет достичь достаточного уровня масштабируемости. Однако, в большинстве случаев это невозможно, так как приводит к большим накладным расходам на коммуникации, а это в соответствии с законом Амдаля существенно урезает масштабируемость. Достичь перекрытия вычислений и обменов для некоторых классов задач позволяет использование коммуникационных функций MPI_Isend, MPI_Ireceive совместно с функциями MPI_Wait и MPI_Test. Это поясняется примером 2. Пример 2. Как видно из схемы на рис. 1, необходимо добиться, чтобы во время передачи данных сетевым процессором (промежуток между моментами времени
и 
) вычислитель был занят обработкой данных, а не простаивал в ожидании окончания пересылки. 
Рис. 1. Схема передачи данных MPI Подбор оптимальных коммуникационных функций требует многочисленных интерпретаций различных версий разрабатываемой программы. Для ускорения этого процесса строится «скелет» программы и все преобразования делаются над ним. После достижения необходимых параметров параллельной программы автоматически генерируется вариант программы в соответствии с полученным коммуникационным шаблоном. Проиллюстрировать важность оптимального выбора операций пересылок можно на следующем «скелете» реальной программы моделирования торнадо (рис. 2а). Если в рассматриваемом «скелете» заменить блокирующие операции Send и Recv на неблокирующие и установить соответствующую операцию Wait после гнезда циклов получится «скелет», представленный на рис. 2б.
На рис. 3 приведены графики ускорения «скелетов» программы представленного на рис. 2а и 2б. Как видно, такая замена существенно расширила область масштабируемости программы. При этом окончательная версия «скелета», удовлетворяющая требованиям прикладного программиста, используется для построения трансформированной исходной программы.
Рис. 2. Схематичное изображение алгоритмов с блокирующими и неблокирующими пересылками К сожалению, в большинстве реальных программ такими простыми преобразованиями не удается достичь необходимого уровня перекрытия, либо такое преобразование невозможно. Использование предлагаемой технологии обеспечивает возможность применения различных преобразований программы, и достигать необходимых параметров программы в приемлемое время. Этот процесс отладки и оптимизации параллельной программы показывает, что задача сама по себе неформализована. На сегодняшний день не может быть реализован компилятор, делающий оптимизацию автоматически, т.к. в некоторых точках процесса программист обязан принимать волевые решения.
Рис. 3. Сравнение масштабируемости параллельных программ, использующих блокирующие и неблокирующие пересылки На следующем этапе, необходимо проинтерпретировать полученную программу на реальных данных, для того чтобы оценить, какое количество вычислителей будет оптимальным для счета. Для этого снова используется инструмент «Inerpreter». Поскольку интерпретатор использует смешанную технику, включающую в себя элементы прямого выполнения, довольно остро стоит проблема нехватки памяти на инструментальной машине. Моделирование некоторых серьёзных программ требует использования довольно больших массивов данных, которые не могут быть размещены в памяти одного вычислительного узла. Для решения этой проблемы проводится преобразование модели, представляющее собой удаление выражений программы, значение которых не влияет на поток управления. Это позволяет качественно изменить требования по памяти, в том числе существенно сократив время интерпретации. Таким образом, инструментальные средства среды ParJava позволяют реализовать технологический процесс, обеспечивающий итеративную разработку параллельной программы.Отметим, что итеративная разработка предполагает достаточно большое число итераций, что может привести к большим накладным расходам по времени разработки и ресурсам. Итеративная разработка реальных программ, предлагаемая в рамках ParJava, возможна благодаря тому, что большая часть процесса выполняется на инструментальном компьютере, в том числе за счет использования инструментов, базирующихся на интерпретаторе параллельных программ. Применение интерпретатора позволяет достаточно точно оценивать ускорение программы. Ошибка на реальных приложениях не превосходила 10%, и в среднем составила ~5% [36-44]. Окончательные значения параметров параллельной программы можно уточнить при помощи отладочных запусков на целевой аппаратуре.
к тому, что одним из
Развитие компьютерных и сетевых технологий привело к тому, что одним из основных свойств современных вычислительных систем является параллелизм на всех уровнях. Происходит широкое внедрение кластерных систем (распределенная память) с тысячами процессоров. Началось широкое производство многоядерных процессоров общего назначения, Современные многоядерные процессоры имеют не более 16 ядер, однако производители уже серьезно говорят о нескольких сотнях и даже тысячах ядер []. Кроме того, выпускаются специализированные процессоры, содержащие сотни параллельно работающих ядер на одном чипе (графические акселераторы компаний AMD и nVidia). Высокая производительность, низкое энергопотребление и низкая стоимость специализированных многоядерных процессоров (как правило, это процессоры для компьютерных игр) способствовали стремлению использовать их не только по их прямому назначению. Начались исследования возможностей широкого применения гетерогенных архитектур, состоящих из процессора общего назначения и набора специализированных многоядерных процессоров (акселераторов) для решения вычислительных задач общего назначения. Акселератор имеет доступ как к своей собственной памяти, так и к общей памяти гетерогенной системы. Примерами таких архитектур являются: архитектура IBM Cell, архитектуры, использующие графические акселераторы компаний AMD и nVidia, многоядерный графический ускоритель Larrabee компании Intel. Остро встал вопрос о языках параллельного программирования, которые могли бы обеспечить достаточно высокую производительность труда программистов, разрабатывающих параллельные приложения. Однако языки, разработанные в 90-е годы (HPF [], UPC [] и др.) не смогли решить эту проблему []. Это привело к тому, что промышленную разработку прикладных параллельных программ, обеспечивающих необходимое качество, приходится вести, на так называемом «ассемблерном» уровне, на последовательных языках программирования (C/C++, Fortran), разработанных в 60-70 гг., с явным использованием обращений к коммуникационной библиотеке MPI (для систем с распределенной памятью), явным указанием прагм OpenMP (для систем с общей памятью), с использованием технологии программирования CUDA [] (расширение языка C для акселераторов Nvidia), которая точно отражает организацию оборудования, что позволяет создавать эффективные программы, но требует высокого уровня понимания архитектуры акселератора и др. Таким образом, в настоящее время параллельное программирование связано с ручной доводкой программ (распределение данных, шаблоны коммуникаций, либо синхронизации доступа к критическим данным и т.п.).
Это связано со значительными затратами ресурсов и требует высокой квалификации прикладных программистов. Цена, которую нужно заплатить, чтобы добиться хорошей производительности и требуемой степени масштабируемости приложений, часто оказывается непомерно высокой. Поэтому целью современных исследований является фундаментальная проблема высокой продуктивности [] разработки параллельных приложений, когда обеспечивается достаточный уровень производительности при приемлемом уровне затрат на разработку. Это особенно актуально в связи с тем, что параллельное программирование становится массовым. Исследования ведутся по многим направлениям: изучаются свойства приложений, делаются попытки классификации приложений, в том числе для выявления в них общих ядер; исследуются свойства аппаратуры с целью максимального их использования и развития; ведутся исследования и разработки по целому спектру средств программирования. Одним из направлений исследований является разработка языков нового поколения (X10 [], Chapel [], Fortress [], Cilk [], Brook+ [] и др.). Несмотря на то, что эти разработки опираются на опыт предыдущих лет, пока они не привели к успеху, прежде всего, из-за недостаточного уровня современных компиляторных технологий. Реализуются как промышленные, так и исследовательские, системы, поддерживающие доводку программ разрабатываемых на «ассемблерном» уровне. К настоящему времени известно несколько таких систем: отладчики DDT [], TotalView [], система TAU [], разработанная в университете штата Орегон и др. Одним из таких средств является интегрированная среда ParJava [], разработанная в ИСП РАН, которая предоставляет прикладному программисту набор инструментальных средств, поддерживающих разработку параллельных программ для вычислительных систем с распределенной памятью (высокопроизводительных кластеров) на языке Java, расширенном стандартной библиотекой передачи сообщений MPI. В настоящее время среда Java представляет значительный интерес с точки зрения высокопроизводительных вычислений.
Это связано как с положи- тельными свойствами Java как среды разработки прикладных программ (переносимость, простота отладки и др.), так и с тем, что использование инфраструктуры Java существенно упрощает разработку инструментальных средств. Можно упомянуть такие системы как: ProActive Parallel Suite [] (INRIA), MPJ Express [] (University of Reading and University of Southampton), Distributed Parallel Programming Environment for Java [] (IBM) и др. Кроме того, добавлена поддержка Java + MPI в известной среде разработки параллельных программ на языках C/C++ и Fortran 77/90 TAU. В проекте ParJava решались две задачи: обеспечить возможность эффективного выполнения параллельных программ на языке Java с явными обращениями к MPI на высокопроизводительных кластерных системах и разработать технологический процесс реализации параллельных программ, обеспечивающий возможность переноса как можно большей части разработки на инструментальный компьютер. В настоящей статье описываются некоторые перспективные направления исследований по высокопродуктивному программированию для параллельных систем с распределенной памятью, проводимые в отделе компиляторных технологий Института системного программирования РАН. Обсуждаются текущие исследования и направления будущих работ, связанных с высоко-продуктивным программированием многоядерных и гетерогенных систем. Статья состоит из 4 разделов. В разделе 2 описывается среда ParJava, модель параллельной Java-программы и возможности ее интерпретации, технологический процесс разработки программ в среде ParJava, механизмы времени выполнения. В разделе 3 приводятся результаты применения среды при разработке программ моделирования интенсивных атмосферных вихрей (ИАВ) и моделирования теплового движения молекул воды и ионов в присутствии фрагмента ДНК. В разделе 4 обсуждаются направления дальнейших исследований.
