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

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

005046724

Аветисян Арутюн Ишханович

СОВРЕМЕННЫЕ МЕТОДЫ СТАТИЧЕСКОГО И ДИНАМИЧЕСКОГО АНАЛИЗА ПРОГРАММ ДЛЯ АВТОМАТИЗАЦИИ ПРОЦЕССОВ ПОВЫШЕНИЯ КАЧЕСТВА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

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

Автореферат

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

2 3 ДЗ Г Ш

Москва-2012

005046724

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте системного программирования Российской академии наук

Научный консультант:

доктор физико-математических наук, академик РАН Иванников Виктор Петрович

Официальные оппоненты:

доктор физико-математических наук, чл.-корр. РАН Воеводин Владимир Валентинович

Ведущая организация: Федеральное государственное бюджетное учреждение науки Вычислительный центр им. A.A. Дородницына Российской академии наук

Защита диссертации состоится "15" ноября 2012 г. в 15 часов на заседании диссертационного совета Д.002.087.01 при Федеральном государственном бюджетном учреждении науки Институте системного программирования Российской академии наук по адресу: 109004, Москва, ул. А. Солженицына, 25.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Институте системного программирования Российской академии наук

доктор технических наук, чл.-корр. РАН Каляев Игорь Анатольевич

доктор физико-математических наук, профессор Крюков Виктор Алексеевич

Ученый секретарь диссертационного совета

Автореферат разослан

/Прохоров С.П./

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

Актуальность. Методы статического и динамического анализа программ были предназначены в первую очередь для разработки оптимизирующих компиляторов: каждая оптимизационная фаза компилятора базируется на одном из таких методов. Первые компиляторы были разработаны в конце 50-х годов прошлого века. Одним из основных критериев качества разрабатываемых программ являлась их эффективность. За пятьдесят лет развития техника оптимизирующей компиляции существенно продвинулась, и для одного вычислительного устройства (ядра) современные оптимизирующие компиляторы обеспечивают такую высокую эффективность объектного кода, что стало возможным почти полностью отказаться от ассемблера при разработке как прикладных, так и системных программ.

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

Современные вызовы связаны с такими долгосрочными тенденциями развития отрасли разработки ПО, как существенное усложнение аппаратуры (параллелизм на всех уровнях, специализированные устройства ускорения вычислений, распределенность), взрывной рост размера программных систем (десятки-сотни миллионов строк кода), массовое внедрение мобильных систем, переход на «облачные» инфраструктуры, доступность практически любых систем через сеть (Интернет, Интранет). В связи с этими вызовами особенно актуальна проблема автоматизации процессов обеспечения качества программных систем на этапах их разработки. Качество современных программных систем определяется тремя взаимосвязанными компонентами: (1) эффективностью; (2) безопасностью; (3) переносимостью. Как правило, в настоящее время обеспечение требуемого качества ПО связано с использованием ручного труда высококвалифицированных специалистов и является искусством. Это существенно увеличивает стоимость и сроки разработки ПО.

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

Рассмотрим проблему автоматизации процессов обеспечения качества ПО подробнее.

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

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

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

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

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

Автоматизация процессов обеспечения безопасности программно-аппаратных систем.

Развитие сетевых технологий привело к тому, что практически все современные компьютеры (кластеры, серверы, персональные компьютеры, встроенные системы и др.) доступны через сеть (Internet/Intranet). Широкое распространение получила концепция «облачных вычислений», в рамках которой компьютер пользователя является лишь входной точкой, обеспечивающей доступ к мощным вычислительным системам, базам данных и др.

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

кодирования, так и ошибки проектирования). Но поскольку устранить эти ошибки невозможно, приходится использовать разные технологии обеспечения безопасности: антивирусы, защита по периметру, аудит кода и др. Далеко не все проблемы компьютерной безопасности могут быть решены средствами статического и динамического анализа. Но указанные средства позволяют решить ряд проблем, обеспечивающих такие важные аспекты компьютерной безопасности, как, например, обеспечение устойчивости ПО к внедрению программ атакующего.

Устойчивость ПО к внедрению программ атакующего связана с отсутствием в нем «уязвимостей», т.е. таких ошибок разработчика, которые трудно обнаружить на этапе тестирования, но которые влияют на устойчивость работы ПО. Такие ошибки естественно искать в исходном коде программ. Для обнаружения ошибок этого класса широко используются методы статического и динамического анализа программ.

Ранее внедренные программы атакующего (часто их называют «недокументированными возможностями ПО», - далее НДВ) имеют целью воздействовать на атакованную систему по сигналу атакующего или постоянно обеспечивать дополнительные функции системы, не заметные для ее администрации. Как правило, такие программы внедряются в бинарный код, что значительно затрудняет их обнаружение.

Методы статического и динамического анализа дают возможность разработать новые технологии анализа программ (как на уровне исходного, так и на уровне бинарного кода), позволяющие обеспечить обнаружение дефектов (уязвимости, НДВ) и защиту от их использования.

Автоматизация процессов обеспечения переносимости (с сохранением качества приложений)

Современное многообразие процессорных архитектур, как для настольных и серверных, так в особенности и для мобильных систем, влечет актуальность задачи обеспечения переносимости приложений между архитектурами, а часто -и внутри одного семейства архитектур из-за серьезных различий между процессорными реализациями (разница в наборах команд, количестве регистров, особенно векторных, объемах кэш-памяти и т.п.). Эта задача традиционно решается либо пересборкой приложения, написанного на языках общего назначения для новой архитектуры, либо использованием динамической компиляции (например, 1ауаУМ).

Для сохранения качества приложения, то есть в основном производительности, в первом случае возникает необходимость поддерживать десятки бинарных версий приложения, собранных для различных архитектур и вариантов одной и той же архитектуры (например, для разных поколений процессоров х86-64). Эта необходимость связана с разным поведением машинно-зависимых оптимизаций (распределения регистров, планирования и конвейеризации кода, векторизации) даже на вариантах одной архитектуры, причем влияние на производительность программы может достигать десятков процентов.

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

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

Цель и задачи работы. Разработка и развитие методов статического и динамического анализа программ, и реализация соответствующих программных и инструментальных средств, обеспечивающих автоматизацию программирования для современных платформ и надежное функционирование программного обеспечения в сетевой среде (Internet/Intranet). Для достижения поставленной цели в диссертационной работе необходимо решить следующие основные задачи:

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

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

• Разработать масштабируемые (анализ большого объема кода в приемлемое время с высокой степенью достоверности) методы статического анализа программ, обеспечивающие нахождение уязвимостей и других дефектов в программах на языках C/C++.

• Разработать методы анализа бинарного кода с целью восстановления алгоритмов и нахождения недокументированных возможностей.

• Разработать технологический процесс, обеспечивающий переносимость программ, написанных на языках общего назначения C/C++, за счет автоматического учета особенностей целевой платформы.

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

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

• Новый метод планирования команд и конвейеризации циклов, учитывающий особенности функционирования современных процессоров (ARM, EPIC), с поддержкой условного и спекулятивного выполнения

• Новые методы разработки JavaMPI-nporpaMM, обеспечивающие высокий уровень автоматизации разработки за счет точного прогнозирования на инструментальной машине поведения разрабатываемого приложения с учетом особенностей высокопроизводительной вычислительной системы

• Новые методы статического анализа исходного кода программ, обеспечивающие аудит, нахождение уязвимостей и других дефектов как исходного кода на языках C/C++, так и бит-кода LLVM, в приемлемое время с высокой степенью достоверности

• Новые методы комбинированного статического и динамического анализа бинарного кода, базирующиеся на сборе и анализе трасс, позволяющие восстанавливать алгоритмы и находить недокументированные возможности в защищенном бинарном коде

• Новый метод двухэтапной компиляции, обеспечивающий переносимость программ, написанных на языках общего назначения C/C++, в промежуточном представлении LLVM (бит-код) с использованием динамической компиляции

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

• На основе новых методов машинно-ориентированной оптимизации реализован и внедрен в основную ветвь промышленного свободно распространяемого компилятора GCC новый планировщик потока команд, который используется при оптимизации приложений для платформ EPIC (например, Itanium), а также как основа при разработке машинно-ориентированных оптимизаций для других архитектур (например, ARM).

• Инструменты среды ParJava интегрированы в промышленную среду разработки программ Eclipse на основе свободного ПО и применяются для разработки параллельных приложений, в частности, в ИФЗ РАН реализовано приложение моделирования процесса зарождения интенсивных атмосферных вихрей по теории В.Н. Николаевского.

• Инструменты среды Svace интегрированы в промышленную среду разработки программ Eclipse на основе свободного ПО. По контракту с компанией «Самсунг» Svace внедрена в технологический процесс разработки ПО внутри компании (несколько тысяч программистов, десятки миллионов строк кода).

• Интегрированная среда статического и динамического анализа бинарного кода используется для решения практических задач по обеспечению безопасности ПО.

• Метод двухэтапной компиляции на базе LLVM реализован для Linux-платформ на базе архитектур х86 и ARM. По контракту с компанией «Самсунг» на основе двухэтапной компиляции создается «облачное хранилище» приложений нового поколения, обеспечивающее с одной стороны переносимость программ в рамках семейства ARM, а с другой стороны, высокую степень надежности и безопасности приложений, доступных в рамках хранилища, за счет использования среды Svace и среды анализа бинарного кода.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на конференциях и семинарах различного уровня. В том числе, 27 докладов на международных конференциях и 7 на всероссийских. В частности: Всероссийская научная конференция "Высокопроизводительные вычисления и их приложения», г. Черноголовка, 30 октября-2 ноября, 2000; Международный семинар «Супервычисления и математическое моделирование», Саров, 13-15 июня, 2001; Международная конференция "Parallel Computing Technologies (РаСТ) Novosibirsk, Sept.3-7, 2001; Computer Science and Information Technologies (CSIT), Yerevan, September 17 - 20, 2001; Международной конференции "Параллельные вычисления и задачи управления" Москва, 2-4 октября, 2001; Parallel Computational Fluid Dynamics 2003, May 13-15, 2003 Moscow; Russian-Indian Workshop on High Performance Computing in Science and Engineering, June 16 - 20, 2003, Moscow; Conf. on Computer Science and Information Technology. September 22-26, 2003, Yerevan; The 10th EuroPVM/MPI conference. LNCS 2840. Sept. 2003, Venice; XII Международная конференция по вычислительной механике и современным прикладным программным системам, июнь - июль 2003, Владимир; Всероссийская научная конференция «Научный сервис в сети Интернет». Новороссийск, 20-25 сентября 2004; Parallel Computational Fluid Dynamics, May 24-27, 2004, Canary Islands, Spain; Fifth Mexican International Conference Avances en la Ciencia de la Computacion ENC'04, 20 - 24 September, Colima, Mexico; Международная научная конференция «Суперкомпьютерные системы и их применение», 26-28 октября 2004, Минск; Всероссийская научная конференция «Научный сервис в сети Интернет: технологии распределенных вычислений». Новороссийск, 19-24 сентября 2005; Computer Science and Information Technologies (CSIT), Yerevan, September 19-23, 2005; Всероссийская научная конференция «Научный сервис в сети ИНТЕРНЕТ: технологии параллельного программирования», г. Новороссийск, 18-23 сентября 2006; 13th International Conference On The Methods Of Aerophysical Research. 5 -10 February, 2007, Novosibirsk; MTPP 2007 Parallel Computing Technologies First Russian-Taiwan Symposium Pereslavl-Zalesskii (Russia), September 2-3, 2007; Parallel Architectures and Compilation Techniques (PACT), Brasov, Romania, September 15-19, 2007; International Conference on the Methods of Aerophysical Research, Novosibirsk, 2007; Sixth International Conference on Computer Science and 8

Information Technologies (CSIT'2007), 24-28 September, Yerevan, Armenia; Международная научная конференция «Космос, астрономия и программирование» (Лавровские чтения), 20-22 мая 2008 г. Санкт-Петербург; Седьмая международная конференция памяти академика А.П. Ершова Перспективы систем информатики. Рабочий семинар "Наукоемкое программное обеспечение", 15-19 июня 2009 г. Новосибирск; Международная конференция «РусКрипто'2009»; SAMOS 2009 Workshop, 2009; XIX Общероссийская научно-техническая конференция «Методы и технические средства обеспечения безопасности информации». Санкт-Петербург, 05-10 июля 2010 г.; Всероссийская конференция "Свободное программное обеспечение-2010", СПб, 26-27 октября 2010 года; HiPEAC 2010, January 2010.

Гранты и контракты. Работа по теме диссертации проводилась в соответствии с планами исследований по проектам, поддержанным: грантами РФФИ: 06-07-89119-а «Исследование и разработка технологии решения вычислительно-сложных задач на базе распределенных вычислительных ресурсов», 08-01-00561-а "Инструментальная поддержка процесса разработки больших научно-технических приложений", 08-07-00279-а "Исследование и разработка системы автоматического обнаружения дефектов в исходном коде программ", 08-07-00311-а "Исследование и разработка набора инструментальных средств для языков параллельного программирования нового поколения", 08-07-91850-К0_а "Компиляция программ для высокопроизводительных встраиваемых процессоров", 09-07-00382-а "Методология поддержки разработки эффективных параллельных программ в среде ParJava", 10-07-92600-К0_а "Кодогенерация и автоматическая настройка для акселераторов", 11-07-00466-а "Исследование и разработка инструмента динамического анализа программ для автоматического обнаружения дефектов"; контрактами: «Исследование и разработка средств повышения защищённости программного обеспечения от внешних атак» в рамках ФЦП "Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 годы" (ГК № 02.447.11.1004); "Высокоуровневые модели параллельных вычислений и их библиотеки поддержки времени выполнения" (ГК № 07.514.11.4001) и "Проектирование и разработка web-ориентированного производственно-исследовательского центра, ориентированного на решение задач анализа программ" (ГК №.07.514.11.4040) в рамках ФЦП "Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы"; в рамках следующих Программ фундаментальных исследований Президиума РАН: Программа №1 "Проблемы создания научной распределенной информационно-вычислительной среды на основе развития GRID технологий и современных телекоммуникационных сетей", Программа № 4 «Фундаментальные проблемы системного программирования», Программа №14 «Высокопроизводительные вычисления и многопроцессорные системы». Также работы проводились по договорам с зарубежными и отечественными организациями. Кроме того, работа была поддержана грантом Президента Российской Федерации для поддержки молодых российских ученых и ведущих научных школ РФ.

Авторские свидетельства. Свидетельство об официальной регистрации программы для ЭВМ №2005613149. "Программа поиска уязвимостей типа переполнения буфера в исходном коде программ на языке С". Федеральная служба по интеллектуальной собственности, патентам и товарным знакам. Зарегистрировано в Реестре программ для ЭВМ 05.12.2005 г. Правообладатель: Учреждение Российской академии наук Институт системного программирования РАН. Авторы: Аветисян А.И., Белеванцев A.A., Гайсарян С.С., Журихин Д.М., Маликов O.P., Мельник Д.М., Несов B.C., Спиридонов C.B. Свидетельство об официальной регистрации программы для ЭВМ №2006613032. "Среда межпроцедурного анализа программ". Федеральная служба по интеллектуальной собственности, патентам и товарным знакам. Зарегистрировано в Реестре программ для ЭВМ 31.08.2006 г. Правообладатель: Учреждение Российской академии наук Институт системного программирования РАН. Авторы: Аветисян А.И., Белеванцев A.A., Гайсарян С.С., Журихин Д.М., Маликов O.P., Мельник Д.М., Несов B.C., Спиридонов C.B.

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

Публикации. По материалам диссертации опубликовано 50 работ, в том числе, 1 учебное пособие. 17 статей опубликовано в изданиях, входящих в список изданий, рекомендованных ВАК РФ. Получено 2 свидетельства о регистрации программ для ЭВМ. Наиболее значимые работы перечислены в списке публикаций.

Структура и объем диссертационной работы. Диссертация состоит из введения, шести глав и заключения, изложенных на 271 страницах, списка литературы из 273 наименований, содержит 54 рисунка и 14 таблиц.

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

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

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

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

В разделе 2.1 описывается новый метод планирования команд и конвейеризации циклов, учитывающий особенности функционирования современных процессоров (ARM, EPIC), с поддержкой условного и спекулятивного выполнения. Особенностями предложенного метода, базирующимися на схеме селективного планирования, являются: четкое разделение шагов по выявлению и использованию параллелизма, позволяющее легко добавлять новые преобразования команд и эвристики по выбору наилучшей для планирования команды; поддержка нескольких точек планирования делает равноправными команды из разных базовых блоков и путей выполнения, что позволяет строить в среднем лучшие расписания для регионов планирования без четко выраженных «горячих» путей; организация конвейеризации циклов на основе существующей инфраструктуры планировщика. В целом предлагаемый метод содержит следующие основные шаги:

1. Построение регионов планирования (ациклических подграфов графа потока управления) по данной процедуре программы.

2. Планирование каждого региона отдельно:

a. Обход фронтом планирования (набором точек планирования) региона в топологическом порядке.

b. Для каждой точки планирования, при наличии свободных ресурсов:

i. Выявление параллелизма (сбор доступных для планирования команд в данной точке).

ii. Использование параллелизма (выбор лучшей команды с помощью набора эвристик или переборных алгоритмов).

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

При выявлении параллелизма основную функциональность обеспечивает ядро планировщика, выполняющее сбор готовых для планирования команд (возможно, с учетом одного или нескольких преобразований) и перенос команды в точку планирования с поддержанием корректности программы (шаги 2b-i и 2b-iii). Ядро реализует два базовых преобразования команд - клонирование и унификацию команд, используя в основном данные анализа зависимостей для выполнения своих действий. Остальные преобразования команд обеспечиваются модулями расширения - это переименование регистров и связанный с ним перенос через копии, спекулятивное выполнение, условное выполнение. Модули обращаются к ядру за необходимой информацией о свойствах команд, жизни регистров и т.п. для проведения преобразования, при этом модули могут добавлять свою информацию в структуры данных, поддерживаемые ядром. Конвейеризация циклов также может рассматриваться как модуль, но с точки зрения корректности

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

Использование параллелизма (шаг 2b-ii) заключается в поддержке набора эвристических алгоритмов, сортирующих собранные команды в соответствии с заданным приоритетом, после чего для выдачи выбирается наиболее приоритетная команда. Возможен дополнительный перебор элементов множества готовых команд для упорядочивания выдаваемых команд в пределах одного цикла. Как и в случае модулей, применение эвристик, основанных на информации о критическом пути команды, относительных вероятностях выполнения отдельных команд, жизни регистров и т.п., требует обращения к ядру для поддержания всех необходимых данных в актуальном состоянии.

В разделе 2.2 рассматривается улучшения предложенного в предыдущем разделе метода, основанного на алгоритме селективного планирования, и реализация метода в компиляторе GCC. Схема алгоритма селективного планирования в том виде, как она изложена в литературе, не позволяет применить ее в реальном компиляторе (GCC) языков Си, Си++ и Фортран, а также применить ее к архитектурам с явным параллелизмом команд. Основными причинами этого являются:

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

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

• Большая сложность, выражающаяся в значительном росте времени компиляции на реальных программах (первоначальная версия алгоритма, реализованная нами для компилятора GCC, замедляла его в два раза);

• Отсутствие преобразований, необходимых для выявления параллелизма на современных архитектурах с явным параллелизмом команд типа Itanium (спекулятивное, условное выполнение) и на встраиваемых архитектурах типа ARM (условное выполнение).

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

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

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

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

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

Приводятся особенности внедрения разработанного метода планирования в компилятор ОСС, связанные с модификациями кодогенератора и эвристик планировщика.

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

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

При перемещении команды генерируется ее спекулятивная версия и команда спекулятивной проверки. Для этого дополнительно был доработан кодогенератор архитектуры IA-64 в компиляторе GCC.

Полученные экспериментальные результаты на платформе Intel Itanium показывают среднее ускорение для тестов SPEC CPU FP 2000 в 3.5%, на некоторых тестах - до 11% по сравнению со старым планировщиком GCC.

Основной прирост производительности дает конвейеризация циклов, в которой важную роль играет поддержка спекулятивного выполнения. Это связано с тем, что конвейеризация в предложенном планировщике обрабатывает циклы с неизвестным числом итераций, т.е. возможна выдача команд из "лишней" (следующей за последней) итерации цикла, и для подавления исключительных ситуаций в таких командах - например, при выходе за границу обрабатываемого массива - необходима поддержка спекулятивного выполнения на уровне аппаратуры. Кроме того, для условного перехода, организующего циклическое выполнение, легко предсказать»направление перехода, поэтому вероятность успеха выданной при конвейеризации спекулятивной загрузки велика.

В разделе 2.3 описывается разработанное преобразование поддержки условного выполнения команд в предлагаемом планировщике. Для добавления поддержки команд с условным выполнением решаются следующие подзадачи:

• Вычисление предиката условно выполняющейся команды, сохранение его в атрибутах команды и выполнение преобразования;

• Добавление условно выполняющихся команд во множество готовых команд (это происходит во время объединения множеств доступных команд от обеих ветвей на команде условного перехода);

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

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

конвейеризация циклов с использованием условного выполнения -перенос команд через обратную дугу цикла не приводит к увеличению количества выполняемых команд, а необходимость в использовании переименования регистров и спекулятивных загрузок возникает реже). В полученных экспериментальных результатах в целом производительность набора тестов вещественных вычислений увеличилась на 2%, пять тестов показали заметный рост производительности (на 5% и более), несколько тестов замедлились, но не более, чем на 2.5%. Наибольший прирост производительности объясняется улучшенной конвейеризацией циклов, не требующей затрат на спекулятивные команды проверки.

В третьей главе рассматривается проблема повышения продуктивности параллельных вычислений на вычислительных системах с распределенной памятью (высокопроизводительных кластерах). Фактическим стандартом разработки приложений для таких систем является последовательный язык программирования, расширенный стандартной библиотекой передачи сообщений (как правило, это библиотека MPI), которая содержит разнообразные возможности организации обмена данными между параллельными ветвями программы. В частности, это связано с тем, что для организации эффективных вычислений требуется различные процедуры обмена для различных классов приложений. Таким образом, эффективность прикладной МРТ-программы существенно зависит от того, какие процедуры библиотеки MPI в ней использованы и как размещены в программе обращения к этим процедурам. В отсутствие оптимизирующих компиляторов выбор процедур библиотеки MPI и расстановка обращений к ним осуществляются разработчиком вручную. Таким образом, фрагменты параллельной программы, от которых в наибольшей степени зависят ее масштабируемость и эффективность, разрабатываются практически на ассемблерном уровне. В этих условиях повышение продуктивности может быть достигнуто путем разработки инструментальных средств, позволяющих разработчику сократить время разработки и сопровождения прикладной MPI-программы. Один из возможных наборов таких инструментов предлагает интегрированная среда Par Java.

Для правильного выбора процедур библиотеки MPI и правильного размещения обращений к ним необходимо многократно получать достаточно точную оценку времени выполнения всей разрабатываемой МР/-программы и некоторых ее фрагментов. Для JavaMPI-протрамм такие оценки могут быть получены во время их выполнения на кластере с использованием подсистемы генерации временного профиля среды Java, но это связано с большими затратами как машинного времени, так и времени прикладного программиста, что существенно понижает продуктивность разработки. Кроме того, подсистема генерации временного профиля ориентирована на программы, выполняемые в одном процессе, и не позволяет точно измерить время обмена данными между процессами УауяМР/-программы. Интегрированная среда ParJava позволяет автоматически построить модель разрабатываемой УауаМР/-программы и

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

В разделе 3.1 рассматривается модель JavaMP/-программы Рго%г, выполняемой в К независимых параллельных процессах (на кластере), которая по определению представляет собой К одинаковых логических (модельных) процессов. С каждым логическим процессом р программы Progr {§ < р < К-\) связано модельное время, определяемое по показаниям модельных часов этого процесса. Модельные часы логического процесса р реализуют отображение ТР(У) фрагментов модели программы на моменты времени. Интерпретация модели программы Рго£г на интерпретаторе среды РагЗта позволяет определять модельное время выполнения каждого структурного фрагмента программы Progr и всей программы в целом.

Поскольку УауаМР/-программа разрабатывается в модели БРМО, достаточно определить модель одного процесса, которая определяется как совокупность моделей всех классов, входящих в состав РгоМодель каждого класса - как множество моделей всех методов этого класса; кроме того, в модель класса включается модель дополнительного метода, описывающего поля класса, его статические переменные, а также инициализацию полей класса и статических переменных. Модель метода представляется в виде пары (модель потока управления, модель вычислений).

Модель потока управления (МПУ) представляет собой модифицированное дерево управления метода, полученное из графа потока управления путем выделения и сворачивания областей. Внутренние узлы представляют операторы управления моделируемой программы, а листовые - ее базовые блоки. Каждый внутренний узел МПУ представляет собой дескриптор области, в состав которой входят все операторы метода, соответствующие узлам, входящим в состав поддерева с корнем в этом узле. В качестве базовых блоков в МПУ рассматриваются не только линейные последовательности вычислений (вычислительные базовые блоки), но также и вызовы библиотечных, пользовательских и коммуникационных методов. Каждому базовому блоку В сопоставлен динамический атрибут - модельное время его выполнения Т1те(В) = Т£„{В) — Терп1гу{В), соответствующее разности показаний модельных часов в начале и в конце выполнения блока В. Соответственно каждому внутреннему узлу V сопоставляется модельное время Тте(У) выполнения части метода, описываемой поддеревом с корнем V. В частности, модельное время Тте(/) выполнения метода / равно Т1те( Вс1г), где Вс1г - тело метода /, представленное как один составной оператор.

Модель вычислений содержит байт-код каждого базового блока моделируемого метода, что позволяет интерпретировать ее на Ja.va.VM. По окончании интерпретации очередного базового блока модели вычислений вызывается интерпретатор среды РагУага, который, с помощью МПУ, определяет очередной базовый блок, который следует интерпретировать.

Следует отметить, что модель А/Р/-программы, в которой внутренние узлы соответствуют ее операторам, адекватно отражает свойства моделируемой программы только для среды программирования Java, в которой структура программы, выполняемой на JavaVM (байт-кода), практически не отличается от структуры исходной программы. Для других традиционных языков программирования (C/C++, Fortran), модель должна строиться не над исходным кодом программы, а над ее промежуточным представлением с учетом результатов статической оптимизации, так как оптимизаторы современных компиляторов существенно меняют структуру программы.

Раздел 3.2. посвящен проблеме оценки времени, затрачиваемого на передачу данных между процессами ./ауаМР/-программы. Каждый обмен данными описывается с помощью функций библиотеки MPI, время выполнения которых определяется не только параметрами узлов кластера, но и параметрами его коммуникационной сети. В диссертации разработаны реализованные в среде ParJava модели коммуникационных функций библиотеки MPI, позволяющие оценить время, затрачиваемое на передачу данных между AffY-процессами. Модель каждой коммуникационной функции описывается с помощью восьми базовых операций обмена, выделенных при анализе структуры библиотеки MPI-. Init, Free, Pack, Unpack, Post, Get, Copy, Wait. В работе показано, что для оценки времени выполнения этих операций следует использовать технические характеристики сети кластера (например, Myrinet, InfiniBand и т.п.).

В разделе 3.3 рассматривается проблема моделирования так называемых «горячих» методов JavaMPI-ирограммы. Как известно, в процессе выполнения Java-программы на интерпретаторе строятся оценки ее частотного и временного профилей, что позволяет выявить «горячие» методы этой программы («горячими» называются методы, на выполнение которых тратится большая часть времени выполнения). В процессе дальнейшего выполнения программы на JavaVM ее «горячие» методы поступают на вход оптимизирующего динамического компилятора времени выполнения (J/Г-компилятора), и их код заменяется эквивалентным «агрессивно» оптимизированным «родным» кодом узла кластера, на котором выполняется программа. Считается, что «горячие» методы составляют не более 15-20% всех методов программы, так что их оптимизация и компиляция не занимает много времени. Поскольку «агрессивная» оптимизация может существенно изменить граф потока управления моделируемой программы, в моделях «горячих» методов должны быть учтены изменения, вносимые ^/^-компилятором.

Учет влияния динамического компилятора на выполнение JavaMPI-программы производится, исходя из следующих предпосылок:

1. Динамический компилятор оптимизирует только «горячие» методы.

2. Динамический компилятор существенно изменяет как отдельные базовые блоки, так и весь граф потока управления «горячих» методов.

3. Динамический компилятор выполняется только один раз.

В среде ParJava предусмотрена перестройка моделей «горячих» методов УауаМР/-программы после окончания работы J/Г-компилятора. Такая

перестройка моделей методов JavaMPI-протраммы является частью интерпретации JavaMPI-программы. Для перестройки моделей «горячих» методов используется их бинарное представление, сгенерированное JIT-компилятором.

В разделе 3.4 определяется и обсуждается процесс интерпретации модели JavaMPI-прогроммы, в среде ParJava.

По определению интерпретация каждого логического процесса модели ./аш.Л4Р/-программы выполняется независимо от интерпретации других логических процессов и начинается с интерпретации модели метода main() одного из классов, входящих в состав указанной программы (имя этого класса и, в случае необходимости, значения параметров метода main() указываются пользователем перед началом интерпретации). В процессе интерпретации каждого внутреннего узла V модели определяется модельное время выполнения этого узла Time(V). При этом модельным временем выполнения метода f () будет Time(Vf), а оценкой времени выполнения всей программы - Time(Vmain), т.е. оценка времени выполнения метода main(), с которого начался процесс интерпретации.

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

При интерпретации внутренних узлов показания модельных часов не меняются, так как интерпретация внутреннего узла сводится к выбору очередного базового блока, который необходимо интерпретировать. Следовательно, если в логическом процессе р базовый блок В2 интерпретируется непосредственно после базового блока Ви то Tfnlry(B1) = . В МПУ каждый базовый блок

представлен своим дескриптором, который содержит модельное время выполнения этого базового блока, определенное до начала интерпретации на целевой вычислительной системе, и ссылку на байт-код базового блока, что позволяет интерпретировать модель вычислений программы на JavaVM. Интерпретация модели вычислений используется только для определения текущих значений переменных, используемых в МПУ для выявления очередного узла модели, который следует интерпретировать. Если список таких переменных в дескрипторе базового блока пуст, блок не подлежит интерпретации. Во всех случаях в качестве оценки модельного времени выполнения базового блока берется оценка из его дескриптора.

Каждый логический процесс модели /ауаМР/-программы интерпретируется на инструментальном компьютере в отдельном потоке.

Таким образом, для интерпретации метода (функции) Java MP I-1 фограмм ы МПУ этого метода передается интерпретатору среды ParJava, который, интерпретируя в требуемом порядке внутренние узлы МПУ, вычисляет модельное время, необходимое для выполнения этого метода. Каждый процесс (поток) содержит свой экземпляр интерпретатора среды ParJava. Чтобы определить модельное время, необходимое для выполнения 7аудМР/-программы на Р процессорах, в каждом логическом процессе р определяется модельное время ГняеДтал-п ()) выполнения метода main() и в качестве требуемой оценки времени берется величина max,/Timep(ma i n ()).

Аналогичным образом определяются оценки времени выполнения фрагментов (например, методов, или областей) 7оуяМР/-программы. В работе показано (утверждение 3.7), что относительная погрешность оценки модельного времени выполнения программы не превосходит наибольшей относительной погрешности оценки модельного времени выполнения ее базовых блоков.

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

Редуцированный блок состоит только из дескриптора, в котором учтено значение модельного времени с требуемой точностью (указанное значение получено во время предыдущих интерпретаций программы). Интерпретация редуцированного базового блока тривиальна и состоит в учете вклада этого блока в модельное время.

По определению, результатом применения операции редукции к базовому блоку В является базовый блок Bred, которому соответствует пустая последовательность интерпретируемых выражений (все выражения были вычислены во время предыдущих интерпретаций и их значения известны) и значение оценки модельного времени которого — известная (по предыдущим интерпретациям) константа. Результатом применения операции редукции к внутреннему узлу V является базовый блок Bri,d, значение оценки модельного времени которого было вычислено во время предыдущих интерпретаций модели программы. Сформулировано достаточное условие корректности применения операции редукции к внутреннему узлу V (утверждение 3.1): редукция произвольного внутреннего узла V корректна, если узел V замкнут по коммуникациям, то есть при интерпретации узла V не должно оставаться непринятых сообщений, и все операции приема должны завершаться.

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

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

В разделе 3.6 исследуется проблема прогноза времени выполнения JavaMPI-программы при использовании заданного числа узлов кластера.

Интерпретация ./яуяА4Р/-программы может быть существенно ускорена, если во время ее предварительного прогона оценивать время выполнения не только вычислительных базовых блоков, но и более крупных фрагментов: отдельных итераций циклов, циклов в целом, а в некоторых случаях - и гнезд циклов. В качестве крупных фрагментов программы удобно рассматривать области, т.е. подграфы графа потока управления метода, имеющие единственный входной базовый блок, доминирующий над всеми остальными блоками области, и не более одной обратной дуги, конец которой указывает на входной базовый блок. Легко видеть, что циклы и гнезда циклов языка Java являются областями: в качестве входного базового блока в этом случае можно рассматривать заголовок цикла.

Вводится понятие простой области: область называется простой, если время ее выполнения не зависит от параметров метода, в состав которого она входит (например, область не содержит ветвлений, или, при наличии ветвлений, время выполнения каждой трассы примерно одинаково). Каждая простая область может быть редуцирована. Если тело цикла является простой областью, то и весь цикл является простой областью и может быть редуцирован. Если тело метода является простой областью, то такой метод может быть редуцирован.

Если в состав области входят базовые блоки, соответствующие обращениям к функциям библиотеки MPI, то такая область не является простой, так как время выполнения функции библиотеки MPI не может быть определено точно. Это следует из того, что МР/-процессы, между которыми осуществляется обмен данными, асинхронны, и невозможно точно определить не только время выполнения функций обмена данными, но и момент начала их выполнения. Рассматриваются методы измерения времени выполнения циклов в различных частных случаях. Среда ParJava реализована и использовалась при решении ряда прикладных задач.

В разделе 3.7 рассмотрена модельная задача решения линейного уравнения теплопроводности и реальная задача моделирования процесса зарождения интенсивных атмосферных вихрей, выполненная в Институте физики Земли РАН. Показано, как среда ParJava обеспечила возможность получения достаточно точных оценок границы (погрешность не более 10%) области масштабируемости в каждом из рассмотренных случаев.

В четвертой главе рассматривается проблема поиска уязвимостей и других дефектов (далее - дефектов) в исходных кодах программ с помощью статического анализа и описывается среда анализа Буасе, обеспечивающая, как на этапе аудита кода, так и на этапе его разработки, нахождение соответствующих дефектов в ПО, содержащем десятки миллионов строк кода, с высокой степенью достоверности.

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

В разделе 4.2 рассматриваются теоретические аспекты поиска дефектов с помощью статического анализа. Предложены следующие требования к методам и алгоритмам анализа:

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

• анализ должен наиболее полно учитывать контекст исследуемой процедуры;

• должна обеспечиваться масштабируемость - возможность анализа программ размером в миллионы строк кода и сотни тысяч функций за приемлемое время (для большинства программ время анализа не должно превышать 12 часов);

• необходимо обеспечить возможность анализа при отсутствии исходного кода всей программы (например, используемых библиотек);

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

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

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

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

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

В разделе 4.3 описывается архитектура среды Svace и особенности реализации ее текущей версии, которая позволяет анализировать программы, написанные на языках Си и Си++. Инструмент анализа оперирует файлами с внутренним представлением, сгенерированными компилятором из файлов исходного кода программы и содержащими описания всех используемых типов, глобальных и локальных переменных модуля компиляции, а также текст функций кода для абстрактной регистровой машины. Используется компилятор LLVM-GCC на основе открытого компилятора GCC, генерирующий внутреннее представление для LLYM — популярной системы для построения компиляторов. Представление LLVM (биткод) компактно, его можно сохранять на диске как в бинарном, так и в текстовом виде, добавлять к коду программы метаданные, компоновать и т.п. Структура биткода специально разрабатывалась для быстрой загрузки и поиска необходимых фрагментов.

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

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

В разделе 4.4 описывается ход статического анализа. Анализатор запускается над множеством сгенерированных биткод-файлов и множеством спецификаций библиотечных функций, необходимых для анализа и также хранящихся в виде биткод-файлов. Управление ходом анализа ведет ядро, вызывающее детекторы по мере надобности. После окончания анализа сгенерированные предупреждения сохраняются в текстовом виде и внутреннем формате. Компонент Eclipse позволяет просматривать результаты с привязкой к исходному коду программы.

Аннотация создается автоматически как результат анализа процедуры. Детекторы могут сохранять в аннотации необходимые им данные для последующего анализа и выдачи предупреждений. Необходимые анализатору спецификации стандартных библиотечных функций (например, языка Си) 22

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

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

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

При анализе процедуры строится ее граф потока управления, после чего проводится потоково-чувствительный анализ, аналогичный анализу потока данных, при этом после нескольких проходов сверху вниз анализ завершается проходом снизу вверх. С каждой дугой графа потока управления ассоциируется контекст - информация о потоке данных, установленная для путей выполнения, проходящих через данную дугу. Анализ потока данных происходит путем «продвижения» контекста по дуге, входящей в инструкцию, через эту инструкцию и построение контекста на выходе из инструкции, основываясь на том, как инструкция изменяет состояние памяти. Для инструкции вызова продвижение контекста заключается в получении аннотации вызываемой процедуры и использовании этой аннотации для построения выходного контекста.

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

В разделе 4.5 описываются экспериментальные результаты. После окончания анализа его результаты могут быть просмотрены пользователем в среде Eclipse. Для каждого предупреждения показывается сообщение и релевантные места в исходном коде программы (например, может быть указана полная межпроцедурная трасса по процедурам программы, приводящая к ошибке).

Тестовый пакет из 23 проектов (1,5 миллиона строк кода, пакеты busybox, openssh, postgresql-8.4, gtk+2.0, openssl, sqlite3 и др.) анализируется менее, чем за 2 часа. Время на анализ многих небольших проектов занимает менее минуты.

Полные результаты оценки разработанного инструмента статического анализа не могут быть раскрыты как полученные в ходе работы по договорам с коммерческими компаниями. В целом из 15 групп оцениваемых предупреждений средняя доля истинных предупреждений составила 67% (от 25% до 100%). Более высокая доля истинных предупреждений (50-85%, в зависимости от типа) наблюдается у групп предупреждений о возможном разыменовании нулевого указателя и небезопасном использовании контролируемых внешним вводом данных. Более низкая доля (40-60%, в зависимости от типа) у предупреждений об утечках памяти, использовании неинициализированных данных или освобожденной памяти, и переполнении буфера.

При сравнении результатов анализа с коммерческими инструментами, присутствующими на рынке, можно заметить, что доля истинных предупреждений в среднем схожа с разработанным инструментом, а также пересечение найденных ошибок для некоторых классов ошибок достаточно велико (50-80%), из чего можно сделать вывод, что количество пропусков истинных ошибок незначительно.

В пятой главе рассматривается подход к анализу бинарного кода, состоящий в комбинации статического и динамического анализа, а также методы и программные средства, позволяющие его автоматизировать. Основной задачей, в которой появляется необходимость в анализе бинарного кода, является задача понимания программ. Необходимость решения этой задачи возникает в целом ряде практических ситуаций: при анализе вредоносного кода, когда исходный код отсутствует (исходная программа написана на языке ассемблера), либо недоступен; при поиске НДВ в коммерческом ПО, которое поставляется без исходных кодов; при поддержке унаследованных приложений, в процессе которой бинарный код приложения в результате многочисленных исправлений перестаёт соответствовать исходному коду и, например, в случае обнаружения ошибки требуется анализ бинарного кода.

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

Бинарный код программы, как правило, представляется в виде исполняемого файла некоторого известного формата (например, РЕ32 для ОС Windows или ELF для Linux). Предполагается, что исполняемый файл удовлетворяет «стандартной модели компиляции»: состоит из области кода и области статических данных, таблицы функций, импортируемых программой из сторонних динамически загружаемых библиотек, а также списка функций, экспортируемых программой, в случае, если программа сама является библиотекой. Область кода содержит последовательность функций программы. Библиотечные функции, которые при сборке программы были статически слинкованы с ней, содержатся в её коде и, вообще говоря, неотличимы от функций программы.

Модель программы может быть представлена в виде двух областей - кода и данных. При этом в области кода должны быть выделены участки, соответствующие отдельным статическим переменным. Область кода должна быть дизассемблирована, то есть представлена в виде последовательности ассемблерных команд (ассемблерного листинга) и размечена на функции. В простейшем случае, каждая функция представляет собой непрерывный участок кода и функции следуют одна за другой непрерывно. Для каждой функции должны быть восстановлены её параметры, т.е. выделены участки стека и регистры, через которые они передаются. Также требуется выделить участок стека, содержащий локальные (автоматические) переменные функции и разбить его на области, соответствующие отдельным переменным. Также в случае, если функция возвращает некоторое значение, должны быть определены области памяти (или регистры), в которых будут содержаться возвращаемое значение функции и адрес возврата. Кроме того, требуется представить программу в виде графа вызовов и для каждой функции построить её граф потока управления.

При статическом анализе выделение областей кода и данных, а также таблиц импорта и экспорта, выполняется в процессе разбора исполняемого файла — данные о смещениях и размерах этих областей содержатся в заголовке. Для того чтобы выделить в области данных границы отдельных переменных требуется проанализировать команды чтения и записи к этим данным из области кода. Аналогично, для того, чтобы выделить границы функций, требуется определить их начало, т.е. адрес, на которой управление передаётся с помощью специальной инструкции вывода, и конец - адрес (точнее максимальный адрес, в случае если их несколько) специальной команды возврата.

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

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

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

Однако статический анализ трудно применять к программам, снабженным средствами защиты от анализа. К таким программам относится, в частности, вредоносный код, а также дорогостоящее лицензионное ПО. В первом случае целью защиты является создание препятствий для разработки средств противодействия вредоносному коду, во втором - препятствий незаконному копированию. В таких программах целенаправленно эксплуатируются конструкции, затрудняющие анализ. В частности, известны и активно применяются на практике программные системы, снабжающие исполняемый код программ «навесной» защитой. «Навесная» защита не позволяет восстанавливать ассемблерный листинг программы, нарушает работу программного отладчика. Методы запутывания («обфускации») кода тоже значительно усложняют анализ кода: даже при наличии интерактивного отладчика анализ запутанного кода занимает неприемлемо много времени из-за большого количества ручных операций. Еще одним из распространённых типов защиты кода от анализа является динамический дешифратор - код программы в исполняемом файле находится в зашифрованном виде и расшифровывается в процессе выполнения. В этом случае пытаются снять дамп в тот момент, когда весь код будет уже расшифрован, однако, в случае «ленивой» расшифровки по требованию (то есть выполняемой, только в момент передачи управления на соответствующий код) такого момента может в принципе не существовать, если на текущих входных данных исполняется не весь код программы. Наконец, во вредоносном коде часто применяется механизм защиты, состоящий в использовании самомодифицирующегося кода. В этом случае, по одним и тем же адресам в разные моменты выполнения может находиться разный код, что приводит к невозможности построения однозначного листинга. Одним из вариантов использования подобного механизма является процесс внедрения вредоносного кода с помощью так называемых «зацепок». В этом случае часть кода одной из системных функций перезаписывается переходом на адрес вредоносного кода. Перезапись происходит в процессе выполнения, а адрес, по которому осуществляется перезапись, часто определяется динамически или по таблице, поэтому с помощью статического анализа проанализировать процесс внедрения вредоносного кода практически невозможно.

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

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

В разделе 5.1 рассматривается оригинальный подход к динамическому анализу бинарного кода, реализованный в интегрированной среде статического и динамического анализа. Генерация трассы осуществляется с помощью одного из средств трассировки: существуют как аппаратные, так и программные решения. Трасса записывается как последовательность машинно-независимых инструкций в промежуточном представлении (раздел 5.2). Во время трассировки выполняется сценарий работы программы, выбранный аналитиком так, чтобы обеспечить выполнение исследуемого им алгоритма. В трассе фиксируется последовательность выполнявшихся на процессоре инструкций, аппаратные прерывания, пользовательский ввод и приходящие извне сетевые пакеты. Затем производится первичное структурирование трассы: выделяется код, относящийся к различным процессам и потокам.

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

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

В интегрированной среде реализована подсистема (раздел 5.5), обеспечивающая получение символьной информации о трассе. После того, как вызовы интересующих функций найдены, требуется выделить из них те, которые относятся к работе интересующего алгоритма. Часто выделение выполняется на основе значений параметров функций. Так как функция библиотечная, то параметры и способ их передачи известны и могут быть описаны аналитиком с использованием реализованной подсистемы описания функций. После того, как функция описана, выполняется проход по всем её вызовам в трассе и восстанавливаются значения параметров с помощью реализованного алгоритма восстановления буфера. Результаты выводятся аналитику в виде списка

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

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

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

Для понимания работы анализируемого алгоритма требуется не только знание параметров и их структуры, но и связи (зависимости) по данным между отдельными входными и выходными параметрами, а также последовательности инструкций, реализующие эти связи, то есть, фактически, процесс преобразования входных параметров в выходные. Для получения этих зависимостей и инструкций используется прямой и обратный слайсинг, который может применяться как в статическом (статический слайсинг), так и в динамическом (динамический слайсинг) подходах. Статический слайс будет содержать большее количество инструкций, так как должен соответствовать работе алгоритма на всех входных данных. Он может быть избыточен, в частности, в связи с неточностью анализа работы с указателями (алиасинг). Динамический слайс соответствует работе анализируемого алгоритма только на конкретных входных данных (заданных при снятии трассы) и может быть неполон, в частности из-за неполноты покрытия кода алгоритма при снятии трассы. Комбинация статического и динамического слайсинга позволяет достичь баланса между точностью и объёмом, что необходимо для правильного понимания анализируемого алгоритма.

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

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

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

В разделе 5.6 рассматриваются примеры практического применения разработанной методики.

В первом примере (раздел 5.6.1) происходит автоматическое выделение кода модельного алгоритма, причем рассматриваются две реализации алгоритма, в виде кода для виртуальной машины и в виде управляемого машинного кода. Каждая полученная трасса состояла примерно из 500 ООО шагов. Оба варианта реализации были успешно выделены, для виртуальной машины результат составил 356 инструкций, для управляемого кода - 143.

Второй пример (раздел 5.6.2) заключается в восстановлении алгоритма, работающего с секретными данными: рассматривался алгоритм генерации ключа системы SPLM. Исполняемый файл получает на вход текстовый файл, содержащий идентифицирующие компьютер данные, на выходе — файл с лицензионным ключом. Последовательно были проведены следующие действия: из IDA Pro были импортированы символы стандартных функций, в трассе была выявлена запись лицензионного ключа в файл функцией WriteFile WinApi, среди параметров этой функции был выявлен буфер памяти, содержащий лицензию, с использованием заранее построенного интегрированной средой графа зависимостей для данной трассы был автоматически выделен код, ответственный за построение лицензии. Для облегчения навигации использовалось дерево вызовов функций. Помимо того, в коде был обнаружен некритичный дефект: программа оставляла файловые дескрипторы незакрытыми.

В третьем примере (раздел 5.6.3) требовалось восстановить формат файла, содержащего исполняемый код. Рассматривалась программа-распаковщик, принимающая на вход файл testfile.bin размером 2100 KB и выводящая распакованный код на стандартный вывод. Первоначальный поиск функции ReadFile не дал результат. Дальнейший анализ показал, что было применено отображение файла в память процесса использованием функции ZwMapViewOfSection. Восстановление её параметров позволило выделить область памяти, в которую был отображён файл. Восстановление формата осуществлялось от точки возврата данной функции до конца трассы. По результатам восстановления буфера, содержащего указанный файл, был сделан вывод о том, что фактически читалась незначительная часть файла, причём файл читался непоследовательно, т.е. с разрывами. В результате автоматического анализа формат считанной части файла был восстановлен.

В рамках четвертого примера (раздел 5.6.4) требовалось исследовать поведение вредоносного кода Trojan. Win32.Tdss.ajfl и выделить в виде ассемблерного листинга его код, в момент окончательного разворачивания в памяти зараженной машины. Виртуальная машина AMD SimNow была заражена указанным зловредным кодом путём запуска его исполняемого файла Trojan.Win32.Tdss.ajfl.exe. Данный вредоносный код перехватывает любое

обращение к диску на уровне файловой системы. При снятии трассы была вызвана команда оболочки cmd.exe type для печати на консоль содержимого некоторого файла; выполнение этой команды гарантированно передает управление вредоносному коду. В первую очередь в полученной трассе была найдена функция CreateFileW, для которой было восстановлено значение первого параметра, содержащего имя открываемого файла. После чего был найден вход в ядро ОС, реализованный инструкцией SYSENTER. Затем был найден переход в модуль файловой системы ntfs.sys. Этот переход соответствовал вызову функции IofCallDriver. Первая инструкция этой функции была перезаписана инструкцией JMP, передающей управление вредоносному коду, который затем осуществляет вызов одной из своих функций, используя таблицу переходов. В результате был получен один из диапазонов адресов, по которым был загружен вредоносный код. По данному диапазону была проведена фильтрация трассы и построен ассемблерный листинг, который был сохранён в файл в текстовом виде.

В шестой главе рассматривается разработанный в диссертации метод двухэтапной компиляции, обеспечивающий переносимость программ, написанных на языках общего назначения Си/Си++, с использованием динамической компиляции. Метод двухэтапной компиляции на базе LLVM реализован для Linux-платформ на базе архитектур х86 и ARM. Также в главе рассматривается разработанное в диссертации «облачное хранилище» приложений нового поколения, обеспечивающее с одной стороны переносимость программ в рамках семейства ARM, а с другой стороны, высокую степень надежности и безопасности приложений, доступных в рамках хранилища, за счет использования среды Svace и интегрированной среды статического и динамического анализа бинарного кода.

В разделе 6.1 обсуждается метод двухэтапной компиляции, обеспечивающий переносимость программ, написанных на языках общего назначения Си/Си++, между вариантами процессорных архитектур одного семейства (для переносимости программ между различными архитектурами необходимо накладывать дополнительные ограничения, например, на использование ассемблерных вставок). Двухэтапная компиляция позволяет существенно сократить накладные расходы, связанные с учетом особенностей конкретных платформ, тем самым решая фундаментальную проблему развертывания и поддержки приложений.

На первом этапе приложение компилируется на машинах разработчиков специальным набором компиляторных инструментов на базе LLVM, при этом выполняются лишь машинно-независимые оптимизации. Результат компиляции сохраняется в биткод-файлах LLVM, дополнительно автоматически генерируется информация об устройстве программного пакета и о схеме его инсталляции. На втором этапе программа оптимизируется на машине пользователя с учетом его поведения и особенностей его вычислительной системы. Поддерживается несколько режимов работы: а) автоматическая кодогенерация бинарной программы, оптимизированной под конкретную архитектуру, и инсталляция программы с помощью сохраненной на первом этапе информации; б) 30

динамическая оптимизация программы во время её работы с учетом собранного профиля пользователя с помощью реализованной инфраструктуры сбора профиля на основе пакета Oprofile и JIT-оптимизации на основе JIT-компилятора LLVM; в) оптимизация программы с учетом профиля пользователя во время простоя системы для экономии ресурсов.

При экспериментальной проверке корректности работы созданной системы двухпроходной компиляции на системах х86 и ARM дополнительно была проведена оптимизация компонент LLVM для их более быстрой работы и потребления меньшего объема памяти. При кодогенерации на платформе ARM было достигнуто сокращение использования памяти на 1.6-10.9% и времени компиляции на 10-20%.

В разделе 6.2 обсуждается применяемая на втором этапе двухпроходной компиляции система динамической компиляции с учетом данных динамического профиля. Система сборки профиля реализована на основе профилировщика Oprofile и использует т.н. выборочное профилирование: системный компонент (модуль ядра Linux) собирает статистику о ходе выполнения программы с помощью аппаратных счетчиков на машине пользователя и сохраняет ее в буфер, а демон-профилировщик считывает данные из буфера, распознает и записывает их в FIFO-каналы. Окончательное формирование базы данных профиля осуществляется библиотекой, которая по сигналу от демона получает обработанные данные профиля из FIFO-каналов. Эта данные могут быть сразу переданы динамическому компилятору или сохранены для дальнейшей оптимизации во время простоя системы.

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

Разработанная система динамической компиляции с учетом данных профиля пользователя была протестирована как на корректность работы, так и на производительность. К сожалению, существующие оптимизации в LLVM мало используют данные статического профиля и поэтому должны быть дополнительно доработаны. В работе использовалась существующая в LLVM оптимизация перемещения базовых блоков по данным динамического профиля, применение которой для программы SQLite привело к ускорению работы программы на тестовом наборе данных на -3%. Разработанный алгоритм

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

В разделе 6.3 предлагается метод организации «облачного хранилища» приложений нового поколения, обеспечивающего как переносимость программ в рамках одного семейства процессорных архитектур ARM, так и высокую степень надежности и безопасности хранимых приложений. Для построения такого облачного хранилища необходимо использование предложенной схемы двухэтапной компиляции для получения представления программы в виде бит-код файлов LLVM, а также метаинформации об устройстве приложения и о схеме его установки.

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

Данный подход может быть использован для приложений как с открытым, так и с закрытым исходным кодом без каких-либо опасений со стороны разработчиков, так как восстановление исходного кода приложения по биткод-файлам LLVM является затруднительным. Отметим, что такой подход к развертыванию программ широко применяется в таких средах, как Java.

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

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

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

1. Исследован и разработан новый метод планирования команд и конвейеризации циклов, учитывающий особенности функционирования современных процессоров (ARM, EPIC), с поддержкой условного и спекулятивного выполнения.

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

3. Исследованы и разработаны масштабируемые методы статического анализа исходного кода программ, обеспечивающие нахождение уязвимостей и других дефектов, для эффективного аудита, как исходного кода на языках C/C++, так и бит-кода LLVM, содержащего десятки миллионов строк, в приемлемое время с высокой степенью достоверности.

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

5. Исследован и разработан метод двухэтапной компиляции, обеспечивающий переносимость программ, написанных на языках общего назначения C/C++, с использованием динамической компиляции.

Кроме того, разработанные программные средства используются в учебном процессе факультетов ВМК МГУ и ФУПМ МФТИ. Содержание диссертационной работы легло в основу учебных курсов по параллельному программированию, машинно-ориентированной компиляции, анализу программ на факультетах ВМК МГУ, ФУПМ МФТИ и МИФИ.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в журналах рекомендованных ВАК РФ

1. А.И. Аветисян, С.С. Гайсарян, О.И. Самоваров. "Возможности оптимального выполнения параллельных программ, содержащих простые и итерированные циклы на неоднородных параллельных вычислительных системах с распределенной памятью". Программирование, 2002, № 1, с. 38-54.

2. В.П. Иванников, С.С. Гайсарян, А.И. Аветисян, В.А. Падарян. «Оценка динамических характеристик параллельной программы на модели.» // Программирование, №4,2006.

3. В.П. Иванников, А.И. Аветисян, С.С. Гайсарян, В.А. Падарян. «Прогнозирование производительности MPI-программ на основе моделей.» // Журнал «Автоматика и телемеханика», 2007, N5, с. 8-17.

4. А.И. Аветисян, В.В. Бабкова и А.Ю. Губарь. «Возникновение торнадо: трехмерная численная модель в мезомасштабной теории турбулентности по Николаевскому»// «ДАН/Геофизика», том 419, №4, с. 547-552.

5. Аветисян А.И., Бабкова В., Гайсарян С.С., Губарь А.Ю. «Рождение торнадо в теории мезомасштабной турбулентности по Николаевскому. Трехмерная численная модель в ParJava.» // Журнал «Математическое моделирование». 2008, т. 20, № 8, с. 28-40.

6. В.П. Иванников, Аветисян А.И., Гайсарян С.С., Акопян М.С. "Особенности реализации интерпретатора модели параллельных программ в среде ParJava." Журнал «Программирование». 2009 т. 35, №1 с. 10-25

7. А.И. Аветисян, С.С. Гайсарян, В.В. Бабкова. Итеративная разработка параллельных программ в среде ParJava //Программирование, №4,2009, с. 56-72.

8. А.Ю.Тихонов, А.И. Аветисян. Развитие taint-анализа для решения задачи поиска некоторых типов закладок . Труды ИСП РАН, т. 20, 2011 г. с. 9-24.

9. Арутюн Аветисян, Андрей Белеванцев, Алексей Бородин, Владимир Несов. Использование статического анализа для поиска уязвимостей и

критических ошибок в исходном коде программ. Труды ИСП РАН том 21, 2011, стр. 23-38.

Ю.Арутюн Аветисян, Алексей Бородин. "Механизмы расширения системы статического анализа Svace детекторами новых видов уязвимостей и критических ошибок". Труды ИСП РАН том 21,2011, стр. 39-54.

11.А.И. Аветисян, К.Ю. Долгорукова, Ш.Ф. Курмангалеев. Динамическое профилирование программы для системы LLVM. Труды ИСП РАН том 21,2011, стр. 71-82.

12.А.И. Аветисян, М.С. Акопян, С.С. Гайсарян. Методы точного измерения времени выполнения гнезд циклов при анализе JavaMPI-nporpaMM в среде ParJava. Труды ИСП РАН том 21, 2011, стр. 83-102.

13.Дмитрий Мельник, Александр Монаков, Арутюн Аветисян. "Поддержка команд с условным выполнением в селективном планировщике команд". Труды ИСП РАН том 21, 2011, стр. 103-118.

14.А.И. Аветисян. "Двухэтапная компиляция для оптимизации и развертывания программ на языках общего назначения". Труды ИСП РАН том 22, 2012, стр. 1-11.

15.А.И. Аветисян. "Планирование команд и конвейеризация циклов на современных архитектурах". Труды ИСП РАН том 22, 2012, стр. 12-19.

16.А.И. Аветисян, А.И. Гетьман. "Восстановление структуры бинарных данных по трассам программ". Труды ИСП РАН том 22,2012, 78-95.

17.А.Ю.Тихонов, А.И. Аветисян. "Комбинированный (статический и динамический) анализ бинарного кода". Труды ИСП РАН том 22,2012, 120-131.

Статьи, учебные пособия и материалы конференций

18.А.И. Аветисян, И.В. Арапов, С.С. Гайсарян, В.А. Падарян. "Среда разработки параллельных Java-nporpaMM для однородных и неоднородных сетей JavaVM" Труды Всероссийской научной конференции "Высокопроизводительные вычисления и их приложения". Изд-во Московского университета, М. 2000.

19.А.И. Аветисян, И.В. Арапов, С.С. Гайсарян, В.А. Падарян. "Параллельное программирование с распределением по данным в среде ParJava." Вычислительные методы и программирование. Том 2, М. 2001 стр. 70-87.

20.А.И. Аветисян, В.А. Падарян. "Библиотека интерфейсов и классов, расширяющих язык Java средствами разработки параллельных программ в модели SPMD." Труды Института Системного Программирования РАН. Том 2, М. 2001, стр. 49-64.

21.А.И. Аветисян, И.В. Арапов, С.С. Гайсарян, В.А. Падарян. "Среда ParJava для разработки SPMD-программ для однородных и неоднородных сетей JavaVM." Труды ИСП РАН. Том 2, М. 2001, стр. 27 - 48.

22. A. Avetisyan, S. Gaissaryan, О. Samovarov. "Extension of Java Environment by Facilities Supporting Development of SPMD Java-programs". V. Malyshkin

(Ed.): PaCT 2001, LNCS 2127, Springer-Verlag Berlin Heidelberg 2001, p. 175- 180.

23.V. Ivannikov, S. Gaissaryan, A. Avetisyan, O. Samovarov. "ParJava: IDE Supporting SPMD Java-Programming" Computer Science and Information Technologies (CSIT), Yerevan, Sept. 17-20,2001. Proceedings, p. 92 - 96.

24.В.П. Иванников, С.С. Гайсарян, А.И. Аветисян. "Среда ParJava: разработка масштабируемых параллельных SPMD-программ в окружении Java." Труды Международной конференции "Параллельные вычисления и задачи управления" Москва, 2-4 октября, 2001.

25.Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Development of Scalable Parallel Programs in ParJava Environment. // Parallel CFD 2003, pp. 291 -293

26.V. Ivannikov, S. Gaissaryan, A. Avetisyan, V. Padaryan. "Analyzing dynamic properties of parallel program in ParJava Environment" Computer Science and Information Technologies (CSIT), Yerevan, September 22 - 26, 2003. Proceedings, p. 19-23.

27.Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Improving properties of a parallel program in ParJava Environment // The 10th EuroPVM/MPI conference, Venice, Sept. 2003, LNCS v. 2840,491-494.

28.Сергей Гайсарян, Арутюн Аветисян, Вартан Падарян, Катерина Долгова. Среда разработки параллельных Java-nporpaMM, использующих библиотеку MPI. // Труды всероссийской научной конференции «Научный сервис в сети Интернет». Новороссийск, 20-25 сентября 2004, с. 177-179.

29.Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. "Development of Scalable Parallel Programs in ParJava Environment". B. Chetverushkin, A. Ecer, et al (eds.) // Parallel Computational Fluid Dynamics, 2004 Elsevier B.V., pp. 417 - 423.

30.Victor P. Ivannikov, Serguei S. Gaissaryan, Arutyun I. Avetisyan, Vartan A. Padaryan. Checkpointing improvement in ParJava environment. // Parallel CFD 2004, May, 24-27,2004, Gran-Canaria.

31.Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan and Hennadiy Leontyev. "Dynamic Analysis and Trace Simulation for Data Parallel Programs in the ParJava Environment". M. Estrada, A. Gelbukh (Eds.) // Avances en la Ciencia de la Computación, ENC'04, Colima, Mexico, pp. 481-488.

32.Сергей Гайсарян, Арутюн Аветисян, Вартан Падарян, Геннадий Леонтьев. Применение среды ParJava для разработки параллельных программ. // Международная научная конференция «Суперкомпьютерные системы и их применение». 26-28 октября 2004, Минск, с. 99-103.

33.В.П. Иванников, С.С. Гайсарян, А.И. Аветисян, В.В. Бабкова, В.А. Падарян "Разработка параллельных Java программ для высокопроизводительных вычислительных систем с распределенной памятью", Труды ИСП РАН, т. 5, 2004, стр. 41-62.

34.С.С. Гайсарян, А.И. Аветисян, К.Н. Долгова, В.А. Падарян. "Средства восстановления программы после сбоев среды ParJava."// Тр. Всероссийской научной конф. «Научный сервис в сети Интернет: технологии распределенных вычислений». Новороссийск, 19-24 сентября

2005, стр.

35.V. Ivannikov, S. Gaissaryan, A. Avetisyan, В. Babkova. "Using instrumental computer for SPMD-program analysis and tuning" Computer Science and Information Technologies (CSIT), Yerevan, September 19 - 23, 2005. Proceedings, p. 385 - 388.

36.А.И. Аветисян, C.C. Гайсарян, В.А. Падарян. Принципы реализации модели параллельной программы в среде ParJava. // Труды Всероссийской научной конф. «Научный сервис в сети ИНТЕРНЕТ: технологии параллельного программирования», г. Новороссийск, 18-23 сентября

2006. стр. 106-107.

37.А.Ю. Губарь, А.И. Аветисян, В.В. Бабкова. Численное моделирование возникновения 3D торнадо в теории мезомасштабных вихрей по Николаевскому. // 13th International Conference On The Methods Of Aerophysical Research. 5 - 10 February, 2007, Ed. V.M. Fomin. -Novosibirsk: Publ. House "Parallel" - 250 p; P135-140

38.Аветисян А. И., Бабкова В. В., Губарь А. Ю. Моделирование интенсивных атмосферных вихрей в среде ParJava. // Труды Всероссийской научной конф. «Научный сервис в сети ИНТЕРНЕТ: технологии параллельного программирования», г. Новороссийск, 18-23 сентября 2006. стр. 109-112.

39.Victor Ivannikov, Serguei Gayssaryan, Arutyun Avetisyan, Vartan Padaryan "Model Based Performance Evaluation for MPI Programs" //MTPP 2007 Parallel Computing Technologies First Russian-Taiwan Symposium Pereslavl-Zalesskii (Russia), September 2-3,2007.

40.A.I. Avetisyan, V.V. Babkova, S.S. Gaissaryan, A.Yu. Gubar "Intensive Atmospheric Vortices Modeling Using High Performance Cluster Systems"// PaCT-2007, LNCS, v. 4671/2007, p. 487-495.

41.A.Yu. Gubar, A.I. Avetisyan, and V.V. Babkova, Numerical modelling of 3D tornado arising in the mesovortice turbulence theory of Nikolaevskiy /International Conf. on the Methods of Aerophysical Research: Proc. Pt III /Ed. V.M. Fomin. - Novosibirsk: Publ. House "Parallel", 2007. - 250 p; PI35-140.

42.Victor P. Ivannikov, Arutyun I. Avetisyan, Varvara V. Babkova, Alexander Yu. Gubar "Tornado arising modeling using high performance cluster systems" // Sixth International Conference on Computer Science and Information Technologies (CSIT'2007), 24-28 September, Yerevan, Armenia.

43.Andrey Belevantsev, Dmitry Melnik, and Arutyun Avetisyan. Improving a selective scheduling approach for GCC. GREPS: International Workshop on GCC for Research in Embedded and Parallel Systems, Brasov, Romania, September 2007. http://sysrun.haifa.il.ibm.com/hrl/greps2007/

44.Arutyun Avetisyan, Andrey Belevantsev, and Dmitry Melnik. GCC instruction scheduler and software pipelining on the Itanium platform. 7th Workshop on

Explicitly Parallel Instruction Computing Architectures and Compiler Technology (EPIC-7). Boston, MA, USA, April 2008. http://rogue.colorado.edu/EPIC7/avetisyan.pdf

45.Аветисян А.И., Бабкова В., Гайсарян С.С. High productive programming for cluster systems using Java with explicit call of MPI //Седьмая международная конференция памяти академика А.П. Ершова Перспективы систем информатики. Рабочий семинар "Наукоемкое программное обеспечение", Новосибирск 15-19 июня 2009 г. ООО "Сибирское Научное Издательство", Не. 2009, с. 1-6.

46.А.И. Аветисян, В.В. Бабкова, А.В. Монаков. Обеспечение высокопродуктивного программирования для современных параллельных платформ Труды ИСП РАН, том 16,2009 г., стр 9-30.

47.А.И. Аветисян, В.А. Падарян, А.И. Гетьман, М.А. Соловьев. Автоматизация динамического анализа бинарного кода. Материалы международной конференции «РусКрипто'2009».

48.Alexander Monakov and Arutyun Avetisyan. "Implementing Blocked Sparse Matrix-Vector Multiplication on NVIDIA GPUs", SAMOS 2009 Workshop, LNCS Proceedings, 2009, №5657, pp 288-296

49.0.И. Самоваров, А.И. Аветисян, А.В. Николаев, А.О. Гетьман. «Технолгия использования вычислительной кластерной системы МФТИ-60 для численного модеирования». Москва, МФТИ, 2009. - 73 с.

50.А.И. Аветисян, В.А. Падарян, А.И. Гетьман, М.А. Соловьев. О некоторых методах повышения уровня представления при анализе защищенного бинарного кода. // Материалы XIX Общероссийской научно-технической конференции «Методы и технические средства обеспечения безопасности информации». Санкт-Петербург, 05-10 июля 2010 г. Стр. 97-98.

51.Avetisyan A.I., Campbell R„ Gupta I., Heath M.T., Ко S.Y., Ganger G.R., Kozuch M.A., O'Hallaron, D., Kunze M.; Kwan T.T., Lai K., Lyons M., Milojicic D.S., Hing Yan Lee, Yeng Chai Soh, Ng Kwang Ming, Luke, J-Y., Han Namgoong. Open Cirrus: A Global Cloud Computing Testbed. / «Computer». Volume 43, Issue:4. - April 2010. pp. 35 - 43.

Заказ №392-1/07/2012 Подписано в печать 16.07.2012 Тираж 100 экз. Усл. п.л. 1,8

ООО "Цифровичок", тел. (495) 649-83-30 www.cfr.ru; е-тай:zak@cfr.ru

ВВЕДЕНИЕ.

1. ОБЗОР СОВРЕМЕННЫХ МЕТОДОВ СТАТИЧЕСКОГО И ДИНАМИЧЕСКОГО АНАЛИЗА ПРОГРАММ ДЛЯ АВТОМАТИЗАЦИИ ПРОЦЕССОВ ПОВЫШЕНИЯ КАЧЕСТВА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

1.1. Планирование команд и векторизация циклов.

1.2. Инструментальное обеспечение разработки МР/-программ.

1.3 Статические методы поиска дефектов в исходном коде программ.

1.4 Динамические методы анализа бинарного кода и проблемы безопасности программного обеспечения.

1.5. Компиляторные инфраструктуры, применяемые для поддержки работ в области компиляторных технологий.

2. ВЫЯВЛЕНИЕ ПАРАЛЛЕЛИЗМА КОМАНД ПРИ КОМПИЛЯЦИИ ПРОГРАММ.

2.1. Общий метод планирования команд для архитектур с явным параллелизмом команд в промышленном компиляторе.

2.2. Особенности применения метода планирования команд для современных архитектур в промышленном компиляторе.

2.2.1. Основные структуры данных.

2.2.2. Учёт различных типов команд.

2.2.3. Учёт зависимостей по данным.

2.2.4. Улучшения переименования регистров для компилятора GCC.

2.2.5. Кэширование истории преобразований.

2.2.6. Конвейеризация циклов.

2.2.7. Оценка выгодности перемещения команд при конвейеризации.

2.2.8. Доработка кодогенератора Itanium в компиляторе GCC.

2.2.9 Спекулятивное выполнение при планировании команд.

2.3 Поддержка условного выполнения при планировании команд.

2.3.1 Поддержка преобразования ветвлений в компиляторе GCC.

2.3.2 Преобразования ветвлений при планировании команд.

2.3.3 Экспериментальные результаты.

3. ПРИМЕНЕНИЕ ДИНАМИЧЕСКОГО АНАЛИЗА ДЛЯ НАСТРОЙКИ МР1-ПРОГРАММ. СРЕДА PARJAVA.

3.1. Модель JavaMPI-программы.

3.1.1. Определение модели процесса.

3.1.2. Модельное время.

3.1.3. Построение модели Уст?МР/-программы.

3.2. Оценка времени, затрачиваемого на передачу данных между процессами JavaMPI-программы.

3.2.1. Базовые операции обмена.

3.2.2. Моделирование функций MPI, осуществляющих коммуникации от точки к точке.

3.3. Моделирование «горячих» методов.

3.4. Интерпретация модели.

3.4.1. Интерпретация внутренних узлов.

3.4.2. Интерпретация базовых блоков.

3.4.3. Оценка времени выполнения фрагментов программы.

3.4.4 Интерпретация коммуникационных функций при оценке времени работы программы и оценка времени их выполнения.

3.5. Частичная интерпретация и редукция.

3.5.1. Определение частичной интерпретации.

3.5.2. Корректность редукции.

3.5.3. Применение частичной интерпретации для получения оценок времени выполнения методов.

3.6 Прогноз времени выполнения ./йггаМР/-программы для заданного числа узлов кластера.

3.6.1. Измерение времени работы областей (фрагментов) МР/-программы на целевой вычислительной системе для ускорения интерпретации ее модели.

3.6.2. Измерение времени выполнения сбалансированных гнезд циклов.

3.6.3. Измерение степени разбалансированности гнезда циклов и времени выполнения разбалансированных гнезд циклов в среде Par Java.

3.6.4 Оценка времени выполнения циклов, требующих синхронизации.

3.7. Результаты численных расчетов. Практическое применение среды Par Java.

3.7.1. Применение среды ParJava: настройка простой JavaMP/-программы.

3.7.2. Применение среды ParJava: разработка прикладной JavaMPI-nporpaMMbi моделирования процессов и условий генерации интенсивных атмосферных вихрей (торнадо).

4. ИСПОЛЬЗОВАНИЕ СТАТИЧЕСКОГО АНАЛИЗА ДЛЯ ПОИСКА УЯЗВИМОСТЕЙ И КРИТИЧЕСКИХ ОШИБОК В ИСХОДНОМ КОДЕ ПРОГРАММ.

4.1. Вводные замечания.

4.2. Методы и алгоритмы статического анализа.

4.3. Поиск уязвимостей и критических ошибок в исходном коде программ.

4.3.1. Архитектура инструмента статического анализа.

4.4. Анализ исходного кода инструментом Svace.

4.4.1. Ход анализа.

4.4.2. Описание спецификаций функций.

4.4.3. Описание детекторов.

4.4.4. Описание типов атрибутов.

4.4.5. Примеры реализованных детекторов.

4.4.6. Тестирование компонентов инструмента.

4.5. Тестирование качества анализа.

5. TREX - ПРОГРАММНАЯ СРЕДА ДЛЯ ДИНАМИЧЕСКОГО АНАЛИЗА БИНАРНОГО КОДА

5.1. Общая схема комбинированного анализа.

5.2. Внутреннее представление исполняемого кода программы.

5.3. Интеграция компонент статического и динамического анализа.

5.3.1. Цели и направления интеграции.

5.3.2. Модуль-расширение IDALuaPlugin.

5.3.3 Загрузчик VadsIDALoader.

5.3.4 Клиентский модуль системы ТгЕх.

5.4. Восстановление структуры бинарных данных по трассам программ.

5.4.1. Источники данных для анализа.

Уточнение понятия «сообщение».

Особенности анализа пакетов разного уровня.

Типы сообщений, с точки зрения их структуры.

Задача анализа протокола.

5.4.2. Особенности реализованной системы.

Особенности анализа файлов.

Особенности анализа входящих и исходящих данных.

Система описания моделей функций.

Система описания семантики функций и их параметров.

Общая схема подхода.

5.4.3. Пути развития системы.

Анализ шифрованного трафика.

Методы статического и динамического анализа программ были предназначены в первую очередь для разработки оптимизирующих компиляторов: каждая оптимизационная фаза компилятора базируется на одном из таких методов. Первые компиляторы были разработаны в конце 50-х годов прошлого века. Одним из основных критериев качества разрабатываемых программ являлась их эффективность. За пятьдесят лет развития техника оптимизирующей компиляции существенно продвинулась, и для одного вычислительного устройства (ядра) современные оптимизирующие компиляторы обеспечивают такую высокую эффективность объектного кода, что стало возможным почти полностью отказаться от ассемблера при разработке как прикладных, так и системных программ.

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

Современные вызовы связаны с такими долгосрочными тенденциями развития отрасли разработки ПО, как существенное усложнение аппаратуры (параллелизм на всех уровнях, специализированные устройства ускорения вычислений, распределенность), взрывной рост размера программных систем (десятки-сотни миллионов строк кода), массовое внедрение мобильных систем, переход на «облачные» инфраструктуры, доступность практически любых систем через сеть (Интернет, Интранет). В связи с этими вызовами особенно актуальна проблема автоматизации процессов обеспечения качества программных систем на этапах их разработки. Качество современных программных систем определяется тремя взаимосвязанными компонентами: (1) эффективностью; (2) безопасностью; (3) переносимостью. Как правило, в настоящее время обеспечение требуемого качества ПО связано с использованием ручного труда высококвалифицированных специалистов и является искусством. Это существенно увеличивает стоимость и сроки разработки ПО.

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

Рассмотрим проблему автоматизации процессов обеспечения качества ПО подробнее.

Автоматизация процессов обеспечения эффективности. Цель такой автоматизации -это обеспечение требуемого уровня эффективности при минимизации ресурсов, затрачиваемых на разработку и сопровождение. При этом, современные серверы состоят из нескольких процессоров, имеющих многоядерную архитектуру, каждое ядро обладает параллелизмом на уровне команд. На базе многоядерных процессоров строятся и высокопроизводительные кластеры. В серверах и в узлах кластеров широко используются акселераторы -специализированные процессоры, содержащие тысячи ядер, что позволяет обеспечить высокую степень распараллеливания вычислений (примером акселератора является карта GPU).

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

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

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

Автоматизация процессов обеспечения безопасности программно-аппаратных систем.

Развитие сетевых технологий привело к тому, что практически все современные компьютеры (кластеры, серверы, персональные компьютеры, встроенные системы и др.) доступны через сеть (Internet/Intranet). Широкое распространение получила концепция облачных вычислений», в рамках которой компьютер пользователя является лишь входной точкой, обеспечивающей доступ к мощным вычислительным системам, базам данных и др.

Использование доступа через сеть остро ставит проблемы безопасности, в том числе -проблемы безопасности программного обеспечения. Доступ к компьютерным ресурсам через локальную или глобальную сеть позволяет злоумышленникам, взломав систему защиты, получать конфиденциальную информацию, а также при необходимости парализовать работу жизненно важных информационных инфраструктур. Следует отметить, что основным источником проблем безопасности являются ошибки в системном ПО (как ошибки кодирования, так и ошибки проектирования). Но поскольку устранить эти ошибки невозможно, приходится использовать разные технологии обеспечения безопасности: антивирусы, защита по периметру, аудит кода и др. Далеко не все проблемы компьютерной безопасности могут быть решены средствами статического и динамического анализа. Но указанные средства позволяют решить ряд проблем, обеспечивающих такие важные аспекты компьютерной безопасности, как, например, обеспечение устойчивости ПО к внедрению программ атакующего.

Устойчивость ПО к внедрению программ атакующего связана с отсутствием в нем «уязвимостей», т.е. таких ошибок разработчика, которые трудно обнаружить на этапе тестирования, но которые влияют на устойчивость работы ПО. Такие ошибки естественно искать в исходном коде программ. Для обнаружения ошибок этого класса широко используются методы статического и динамического анализа программ.

Ранее внедренные программы атакующего (часто их называют «недокументированными возможностями ПО», - далее НДВ) имеют целью воздействовать на атакованную систему по сигналу атакующего или постоянно обеспечивать дополнительные функции системы, не заметные для ее администрации. Как правило, такие программы внедряются в бинарный код, что значительно затрудняет их обнаружение.

Методы статического и динамического анализа дают возможность разработать новые технологии анализа программ (как на уровне исходного, так и на уровне бинарного кода), позволяющие обеспечить обнаружение дефектов (уязвимости, НДВ) и защиту от их использования.

Автоматизация процессов обеспечения переносимости (с сохранением качества приложений)

Современное многообразие процессорных архитектур, как для настольных и серверных, так в особенности и для мобильных систем, влечет актуальность задачи обеспечения переносимости приложений между архитектурами, а часто - и внутри одного семейства архитектур из-за серьезных различий между процессорными реализациями (разница в наборах 7 команд, количестве регистров, особенно векторных, объемах кэш-памяти и т.п.). Эта задача традиционно решается либо пересборкой приложения, написанного на языках общего назначения для новой архитектуры, либо использованием динамической компиляции (например, JavaVM).

Для сохранения качества приложения, то есть в основном производительности, в первом случае возникает необходимость поддерживать десятки бинарных версий приложения, собранных для различных архитектур и вариантов одной и той же архитектуры (например, для разных поколений процессоров х86-64). Эта необходимость связана с разным поведением машинно-зависимых оптимизаций (распределения регистров, планирования и конвейеризации кода, векторизации) даже на вариантах одной архитектуры, причем влияние на производительность программы может достигать десятков процентов.

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

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

Цель и задачи работы. Разработка и развитие методов статического и динамического анализа программ, и реализация соответствующих программных и инструментальных средств, обеспечивающих автоматизацию программирования для современных платформ и надежное функционирование программного обеспечения в сетевой среде (Internet/Intranet). Для достижения поставленной цели в диссертационной работе необходимо решить следующие основные задачи:

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

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

• Разработать масштабируемые (анализ большого объема кода в приемлемое время с высокой степенью достоверности) методы статического анализа программ, обеспечивающие нахождение уязвимостей и других дефектов в программах на языках C/C++.

• Разработать методы анализа бинарного кода с целью восстановления алгоритмов и нахождения недокументированных возможностей.

• Разработать технологический процесс, обеспечивающий переносимость программ, написанных на языках общего назначения C/C++, за счет автоматического учета особенностей целевой платформы.

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

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

• Новый метод планирования команд и конвейеризации циклов, учитывающий особенности функционирования современных процессоров (ARM, EPIC), с поддержкой условного и спекулятивного выполнения

• Новые методы разработки JavaMPI-nporpaMM, обеспечивающие высокий уровень автоматизации разработки за счет точного прогнозирования на инструментальной машине поведения разрабатываемого приложения с учетом особенностей высокопроизводительной вычислительной системы

• Новые методы статического анализа исходного кода программ, обеспечивающие аудит, нахождение уязвимостей и других дефектов как исходного кода на языках C/C++, так и бит-кода LLVM, в приемлемое время с высокой степенью достоверности

• Новые методы комбинированного статического и динамического анализа бинарного кода, базирующиеся на сборе и анализе трасс, позволяющие восстанавливать алгоритмы и находить недокументированные возможности в защищенном бинарном коде

• Новый метод двухэтапной компиляции, обеспечивающий переносимость программ, написанных на языках общего назначения C/C++, в промежуточном представлении LLYM (бит-код) с использованием динамической компиляции

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

• На основе новых методов машинно-ориентированной оптимизации реализован и внедрен в основную ветвь промышленного свободно распространяемого компилятора GCC новый планировщик потока команд, который используется при оптимизации приложений для платформ EPIC (например, Itanium), а также как основа при разработке машинно-ориентированных оптимизаций для других архитектур (например, ARM).

• Инструменты среды ParJava интегрированы в промышленную среду разработки программ Eclipse на основе свободного ПО и применяются для разработки параллельных приложений, в частности, в ИФЗ РАН реализовано приложение моделирования процесса зарождения интенсивных атмосферных вихрей по теории В.Н. Николаевского.

• Инструменты среды Svace интегрированы в промышленную среду разработки программ Eclipse на основе свободного ПО. По контракту с компанией «Самсунг» Svace внедрена в технологический процесс разработки ПО внутри компании (несколько тысяч программистов, десятки миллионов строк кода).

• Интегрированная среда статического и динамического анализа бинарного кода используется для решения практических задач по обеспечению безопасности ПО.

• Метод двухэтапной компиляции на базе LLVM реализован для Linux-платформ на базе архитектур х86 и ARM. По контракту с компанией «Самсунг» на основе двухэтапной компиляции создается «облачное хранилище» приложений нового поколения, обеспечивающее с одной стороны переносимость программ в рамках семейства ARM, а с другой стороны, высокую степень надежности и безопасности приложений, доступных в рамках хранилища, за счет использования среды Svace и среды анализа бинарного кода.

По материалам диссертации опубликована 51 работа [1-51]. Основные результаты диссертационной работы докладывались и обсуждались на конференциях и семинарах

10 различного уровня. В том числе, 27 докладов на международных конференциях и 7 на всероссийских. Работа по теме диссертации проводилась в соответствии с планами исследований по проектам, поддержанным грантами РФФИ, контрактами в рамках ФЦП "Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 годы", в рамках Программ фундаментальных исследований Президиума РАН, а также с договорами с компаниями Самсунг Электронике Ко.Лтд. и ФГУП НИИ "Квант". Работа была поддержана грантом Президента Российской Федерации для поддержки молодых российских ученых и ведущих научных школ РФ. Было получено два свидетельства об официальной регистрации программы для ЭВМ в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

2. Исследованы и разработаны методы и поддерживающие их программные инструменты разработки параллельных программ на языке Java с явными обращениями к коммуникационной библиотеке, реализованные в среде ParJava. Эти инструменты позволяют проводить итеративную разработку с минимальным использованием целевой аппаратуры, повышая продуктивность разработки МР/-программ для систем с распределенной памятью.

Инструменты среды ParJava интегрированы в промышленную среду разработки программ Eclipse на основе свободного ПО. Они применяются для разработки параллельных прикладных программ, в частности, в ИФЗ РАН реализовано приложение моделирования процесса зарождения интенсивных атмосферных вихрей по теории В.Н. Николаевского.

3. Исследованы и разработаны масштабируемые методы статического анализа исходного кода программ, обеспечивающие нахождение уязвимостей и других дефектов, для эффективного аудита, как исходного кода на языках C/C++, так и бит-кода LLVM, содержащего десятки миллионов строк, в приемлемое время с высокой степенью достоверности.

Эти методы реализованы в интегрированной среде Svace. Инструменты среды Svace интегрированы в промышленную среду разработки программ Eclipse на основе свободного ПО. По контракту с компанией «Самсунг» Svace внедрена в технологический процесс разработки ПО внутри компании (несколько тысяч программистов, десятки миллионов строк кода).

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

На основе этих методов реализована интегрированная среда ТгЕх, которая используется для решения практических задач по обеспечению безопасности ПО в НИИ «Квант».

5. Исследован и разработан метод двухэтапной компиляции, обеспечивающий возможность распространения программ, написанных на языках общего назначения C/C++, в промежуточном представлении LLVM (бит-код) с использованием динамической компиляции.

Метод двухэтапной компиляции на базе LLVM реализован для Linux-платформ на базе архитектур х86 и ARM. По контракту с компанией «Самсунг» на основе разработанных программных средств создается «облачное хранилище» приложений нового поколения, обеспечивающее с одной стороны переносимость программ в рамках семейства ARM, а с другой стороны, высокую степень надежности и безопасности приложений, доступных в рамках хранилища, за счет использования сред Svace и ТгЕх.

Автор выражает искреннюю благодарность своим учителям - академику Иванникову Виктору Петровичу и профессору Гайсаряну Сергею Суреновичу, а также членам коллектива отдела компиляторных технологий ИСП РАН без энтузиазма и высокого профессионализма которых многие идеи не смогли бы быть реализованы.

1. В.П. Иванников, С.С. Гайсарян, А.И. Аветисян, В.А. Падарян. «Оценка динамических характеристик параллельной программы на модели.» // Программирование, №4, 2006.

2. В.П. Иванников, А.И. Аветисян, С.С. Гайсарян, В.А. Падарян. «Прогнозирование производительности MPI-программ на основе моделей.» // Журнал «Автоматика и телемеханика», 2007, N5, с. 8-17.

3. А.И. Аветисян, В.В. Бабкова и А.Ю. Губарь. «Возникновение торнадо: трехмерная численная модель в мезомасштабной теории турбулентности по Николаевскому»// «ДАН/Геофизика», том 419, №4, с. 547-552.

4. Аветисян А.И., Бабкова В., Гайсарян С.С., Губарь А.Ю. «Рождение торнадо в теории мезомасштабной турбулентности по Николаевскому. Трехмерная численная модель в ParJava.» // Журнал «Математическое моделирование». 2008, т. 20, № 8, с. 28-40.

5. В.П. Иванников, Аветисян А.И., Гайсарян С.С., Акопян М.С. "Особенности реализации интерпретатора модели параллельных программ в среде ParJava." Журнал «Программирование». 2009 т. 35, №1 с. 10-25.

6. А.И. Аветисян, С.С. Гайсарян, В.В. Бабкова. Итеративная разработка параллельных программ в среде ParJava //Программирование, №4, 2009, с. 56-72.

7. А.Ю.Тихонов, А.И. Аветисян. Развитие taint-анализа для решения задачи поиска некоторых типов закладок . Труды ИСП РАН, т. 20, 2011 г. с. 9-24.

8. Арутюн Аветисян, Андрей Белеванцев, Алексей Бородин, Владимир Несов. Использование статического анализа для поиска уязвимостей и критических ошибок в исходном коде программ. Труды ИСП РАН том 21, 2011, стр. 23-38.

9. Арутюн Аветисян, Алексей Бородин. "Механизмы расширения системы статического анализа Svace детекторами новых видов уязвимостей и критических ошибок". Труды ИСП РАН том 21, 2011, стр. 39-54.

10. А.И. Аветисян, К.Ю. Долгорукова, Ш.Ф. Курмангалеев. Динамическое профилирование программы для системы LLVM. Труды ИСП РАН том 21, 2011, стр. 71-82.

11. А.И. Аветисян, М.С. Акопян, С.С. Гайсарян. Методы точного измерения времени выполнения гнезд циклов при анализе JavaMPI-nporpaMM в среде ParJava. Труды ИСП РАН том 21, 2011,стр. 83-102.

12. Дмитрий Мельник, Александр Монаков, Арутюн Аветисян. "Поддержка команд с условным выполнением в селективном планировщике команд". Труды ИСП РАН том 21, 2011, стр. 103-118.

13. А.И. Аветисян. "Двухэтапная компиляция для оптимизации и развертывания программ на языках общего назначения". Труды ИСП РАН том 22, 2012, стр. 1-11.

14. А.И. Аветисян. "Планирование команд и конвейеризация циклов на современных архитектурах". Труды ИСП РАН том 22, 2012, стр. 12-19.

15. А.И. Аветисян, А.И. Гетьман. "Восстановление структуры бинарных данных по трассам программ". Труды ИСП РАН том 22, 2012, 78-95.

16. А.Ю.Тихонов, А.И. Аветисян. "Комбинированный (статический и динамический) анализ бинарного кода". Труды ИСП РАН том 22, 2012, 120-131.

17. Другие публикации автора по теме диссертации (статьи, учебные пособия, материалы конференций)

18. А.И. Аветисян, И.В. Арапов, С.С. Гайсарян, В.А. Падарян. "Параллельное программирование с распределением по данным в среде ParJava." Вычислительные методы и программирование. Том 2, М. 2001 стр. 70-87.

19. А.И. Аветисян, В.А. Падарян. "Библиотека интерфейсов и классов, расширяющих язык Java средствами разработки параллельных программ в модели SPMD." Труды Института Системного Программирования РАН. Том 2, М. 2001, стр. 49-64.

20. А.И. Аветисян, И.В. Арапов, С.С. Гайсарян, В.А. Падарян. "Среда ParJava для разработки SPMD-программ для однородных и неоднородных сетей JavaVM." Труды ИСП РАН. Том 2, М. 2001, стр. 27-48.

21. A. Avetisyan, S. Gaissaryan, О. Samovarov. "Extension of Java Environment by Facilities Supporting Development of SPMD Java-programs". V. Malyshkin (Ed.): PaCT 2001, LNCS 2127, Springer-Verlag Berlin Heidelberg 2001, p. 175 180.

22. V. Ivannikov, S. Gaissaryan, A. Avetisyan, O. Samovarov. "ParJava: IDE Supporting SPMD Java-Programming" Computer Science and Information Technologies (CSIT), Yerevan, Sept. 17-20, 2001. Proceedings, p. 92-96.

23. В.П. Иванников, С.С. Гайсарян, А.И. Аветисян. "Среда ParJava: разработка масштабируемых параллельных SPMD-программ в окружении Java." Труды Международной конференции "Параллельные вычисления и задачи управления" Москва, 2-4 октября, 2001.

24. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Development of Scalable Parallel Programs in ParJava Environment. // Parallel CFD 2003, pp. 291 293

25. V. Ivannikov, S. Gaissaryan, A. Avetisyan, V. Padaryan. "Analyzing dynamic properties of parallel program in ParJava Environment" Computer Science and Information Technologies (CSIT), Yerevan, September 22 26, 2003. Proceedings, p. 19-23.

26. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Improving properties of a parallel program in ParJava Environment // The 10th EuroPVM/MPI conference, Venice, Sept. 2003, LNCS v. 2840, 491-494.

27. Victor P. Ivannikov, Serguei S. Gaissaryan, Arutyun I. Avetisyan, Vartan A. Padaryan. Checkpointing improvement in ParJava environment. // Parallel CFD 2004, May, 24-27, 2004, Gran-Canaria.

28. Сергей Гайсарян, Арутюн Аветисян, Вартан Падарян, Геннадий Леонтьев. Применение среды ParJava для разработки параллельных программ. // Международная научная конференция «Суперкомпьютерные системы и их применение». 26-28 октября 2004, Минск, с. 99-103.

29. В.П. Иванников, С.С. Гайсарян, А.И. Аветисян, В.В. Бабкова, В.А. Падарян "Разработка параллельных Java программ для высокопроизводительных вычислительных систем с распределенной памятью", Труды ИСП РАН, т. 5, 2004, стр. 41-62.

30. V. Ivannikov, S. Gaissaryan, A. Avetisyan, В. Babkova. "Using instrumental computer for SPMD-program analysis and tuning" Computer Science and Information Technologies (CSIT), Yerevan, September 19-23, 2005. Proceedings, p. 385 388.

31. Victor Ivannikov, Serguei Gayssaryan, Arutyun Avetisyan, Vartan Padaryan "Model Based Performance Evaluation for MPI Programs" //MTPP 2007 Parallel Computing Technologies First Russian-Taiwan Symposium Pereslavl-Zalesskii (Russia), September 2-3, 2007.

32. A.I. Avetisyan, V.V. Babkova, S.S. Gaissaryan, A.Yu. Gubar "Intensive Atmospheric Vortices Modeling Using High Performance Cluster Systems"// PaCT-2007, LNCS, v. 4671/2007, p. 487-495.

33. А.И. Аветисян, В.В. Бабкова, А.В. Монаков. Обеспечение высокопродуктивного программирования для современных параллельных платформ Труды ИСП РАН, том 16, 2009 г., стр 9-30.

34. А.И. Аветисян, В.А. Падарян, А.И. Гетьман, М.А. Соловьев. Автоматизация динамического анализа бинарного кода. Материалы международной конференции «РусКрипто'2009».

35. Alexander Monakov and Arutyun Avetisyan. "Implementing Blocked Sparse Matrix-Vector Multiplication on NVIDIA GPUs", SAMOS 2009 Workshop, LNCS Proceedings, 2009, №5657, pp 288-296

36. О.И. Самоваров, А.И. Аветисян, А.В. Николаев, А.О. Гетьман. «Технолгия использования вычислительной кластерной системы МФТИ-60 для численного модеирования». Москва, МФТИ, 2009. 73 с.

37. Brian J. Gough: An Introduction to GCC, Network Theory Ltd., 2004 (Revised August 2005).

38. Chris Lattner and Vikram Adve "LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation"// Proc. of the 2004 International Symposium on Code Generation and Optimization (CGO'04), Palo Alto, California, Mar. 2004.

39. Mary Hall, David Padua, and Keshav Pingali. 2009. Compiler research: the next 50 years. Commun. ACM 52, 2 (February 2009), pp 60-67.

40. Michael С Schatz, Cole Trapnell, Arthur L Delcher and Amitabh Varshney High-throughput sequence alignment using Graphics Processing UnitsIIBMC Bioinformatics 2007, 8:474

41. Ken Kennedy, Charles Koelbel, Hans P. Zima. "The rise and fall of high performance Fortran."// Commun. ACM vol. 54, No 11, (2011) pp 74-82

42. Michael Armbrust, Armando Fox, David A. Patterson et al. Above the Clouds: A Berkeley View of Cloud Computing// Technical Report No. UCB/EECS-2009-28, February 10, 2009, http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-28.html

43. Jianfeng Zhan, Lei Wang, Weisong Shi, Shimin Gong, Xiutao Zang. "PhoenixCloud: Provisioning Resources for Heterogeneous Cloud Workloads" CoRR (Computing Research Repository) abs/1003.0958: (2010)

44. David W. Wall. Limits of instruction-level parallelism. In Proceedings of the Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) , volume IV, pp. 176-188, April 1991.

45. Joseph A. Fisher. Global Code Generation for Instruction-Level Parallelism: Trace Scheduling-2. Hewlett-Packard Technical Report #HPL-93-43, http://www.hpl.hp.com/techreports/93/HPL-93-43.html.

46. Alexandre Nicolau. Percolation Scheduling: a Parallel Compilation Technique. Technical Report. UMI Order Number: TR85-678, Cornell University, 1985.

47. Soo-Mook Moon and Kemal Ebcioglu. Parallelizing Nonnumerical Code with Selective Scheduling and Software Pipelining. ACM TOPLAS, Vol 19, No. 6, pages 853-898, November 1997.

48. J. Bharadwaj, K.N. Menezes, and C. McKinsey. Wavefront Scheduling: Path-Based Data Representation and Scheduling of Subgraphs. In Proceedings of the 32nd Annual International Symposium on Microarchitecture (MICR032), (Haifa, Israel), December 1999.

49. B.R. Rau. Iterative modulo scheduling: An algorithm for software pipelining loops. In Proc. of the 27th Annual International Symposium on Microarchitecture, pp. 63-74. November 1994.

50. M. Hagog, A. Zaks. Swing Modulo Scheduling in GCC. In Proceedings of the GCC Developer's Summit, Ottawa, Canada, 2004.

51. Thomas Ball and James R. Larus. Optimally Profiling and Tracing Programs. ACM Transactions on Programming Languages and Systems, Vol 16, No. 4, July 1994, pp.1319-1360.

52. Thomas Ball and James R. Larus. Efficient path profiling. In Proceedings of the 29th Annual ACM/IEEE international Symposium on Microarchitecture (Paris, France, December 02 04, 1996), pp. 46-57.

53. James R. Larus. Whole program paths. SIGPLAN Not. 34, 5 (May. 1999), pp. 259-269.

54. Thomas Ball and James R. Larus. Branch prediction for free. Proceedings of the SIGPLAN '93 Conference on Programming Language Design and Implementation (PLDI), pp. 300-313, June 1993.

55. Уязвимость переполнения буфера в модуле modssl сервера Apache. http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2002-0653

56. Использование уязвимости сервера Apache. http://seclists.org/vuln-dev/2002/Jun/268

57. Взламываемая уязвимость форматной строки в программе Dia. http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2006-2480

58. Компилятор Open Research Compiler (ORC). http://ipf-orc.sourceforge.net

59. Компилятор Open64. http://www.open64.net

60. Поддержка спекулятивности в компиляторе GCC. http://gcc.gnu.org/ml/gcc-patches/2005-12/msg01752.html

61. Уязвимость испорченного ввода в функциях языка Perl. http://web.nvd.nist.gov/view/vuln/detail?vulnld=CVE-2011-1487

62. Уязвимость испорченного ввода в MediaWiki. http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2008-5249

63. Уязвимость испорченного ввода типа SQL Injection, http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2007-6602

64. Carole Dulong, Rakesh Krishnaiyer, Dattatraya Kulkarni, Daniel Lavery, Wei Li, John Ng, and David Sehr. An overview of the Intel IA-64 compiler. Intel Technology Journal, November 1999.

65. David I. August, Wen-mei W. Hwu, Scott A. Mahlke. A Framework for Balancing Control Flow and Predication // International Symposium on Microarchitecture 1997. P. 92-103.

66. M Snir, SW Otto, S Huss-Lederman, DW Walker, J (1998) MPI—The Complete Reference: Volume 1, The MPI Core. MIT Press, Cambridge, MA.

67. Gropp, William; Steven Huss-Lederman, Andrew Lumsdaine, Ewing Lusk, Bill Nitzberg, William Saphir, and Marc Snir (1998) MPI—The Complete Reference: Volume 2, The MPI-2 Extensions. MIT Press, Cambridge, MA

68. Jesus Labarta, Sergi Girona, Vincent Pillet, Toni Cortes, Luis Gregoris "DiP: A Parallel Program Development Environment" (1996)

69. S. Shende and A. D. Malony. "The TAU Parallel Performance System" // International Journal of High Performance Computing Applications, Vol. 20, No 2, 2006. pp 287-311.

70. V. Bui, B. Norris, K. Huck, L. C. Mclnnes, L. Li, O. Hernandez, and B. Chapman, "A Component Infrastructure for Performance and Power Modeling of Parallel Scientific Applications", in Component-Based High Performance Computing (CBHPC 2008), 2008.

71. D. A. Grove and P.D. Coddington "Performance Modelling Techniques for Parallel Supercomputing Applications", Nova Publishers, 2011, pp. 85-86

72. Bronis R. de Supinski, Paul Hovland et al. SIAM Short Course on PERC Tools for Performance Data Gathering, Analysis and Modeling, 2004// http://www.siam.org/meetings/pp04/

73. Vikram S. Adve Rajive Bagrodia et al. POEMS: End-to-End Performance Design of Large Parallel Adaptive Computational Systems // IEEE Transactions on Software Engineering Volume 26 Issue 11, November 2000

74. S.D. Hammond, G.R. Mudalige, J.A. Smith, S.A. Jarvis J.A. Herdman and A. Vadgama. WARPP A Toolkit for Simulating High-Performance Parallel Scientific Codes// 2nd International Conference On Simulation Tools And Techniques (Simutools 2009)

75. S.D. Hammond, G.R. Mudalige, J.A. Smith, S.A. Jarvis J.A. Herdman and A. Vadgama. WARPP A Toolkit for Simulating High-Performance Parallel Scientific Codes// http://www2.warwick.ac.uk/fac/sci/csc/events/marcwkshpcomputersimulation/hammond.pdf

76. Jeffrey К. Hollingsworth, and Nick Rutar, "Data Centric Techniques for Mapping Performance Data to Program Variables", Parallel Computing, (38)1-2, Jan. 2012

77. E. D'Hollander, Frans Peters "Parallel computing: fundamentals, applications, and new directions" Elsevier, 1998, pp. 352 354

78. Jorg Behrens Performance analysis of parallel programs with Vampir// DKRZ Blizzard Workshop 2010 http://www.dkrz.de/Nutzerportal-en/doku/blizzard/program-analysis/tracing/

79. Andrew Sunderland, Andrew Porter "Profiling Parallel Performance using Vampir and Paraver" Tech. Report 2004 http://www.hpcx.ac.uk/research/publications/HPCxTR0704.pdf

80. K.D. Cooper and L. Torczon. Engineering a Compiler. Morgan Kaufmah Publishers, 2004, ISBN: 1-55860-698-X.

81. Hovemeyer, D. and Pugh, W. Finding bugs is easy. SIGPLAN Not. 39, 12 (Dec. 2004), 92106.

82. M. P. Gallaher and В. M. Kropp. Economic impacts of inadequate infrastructure for software testing. Technical report, RTI International, National Institute of Standards and Technology, US Dept of Commerce, May 2002.

83. David Wagner, Jeffrey S. Foster, Eric A. Brewer, and Alexander Aiken. A first step towards automated detection of buffer overrun vulnerabilities. In Network and Distributed System Security Symposium, pages 3-17, San Diego, CA, February 2000.

84. David A. Wheeler. Flawfinder. http://www.dwheeler.com/flawfinder/, апрель 2008.

85. J. Viega, J. T. Bloch, Y. Kohno, and G. Mcgraw. Its4: a static vulnerability scanner for c and c++ code. In Computer Security Applications, 2000. ACS AC '00. 16th Annual Conference, pages 257-267, 2000.

86. Fortify Software, Inc. RATS Rough Auditing Tool for Security. https://www.fortify.com/ssa-elements/threat-intelligence/rats.html.

87. Code Verification with Polyspace. http://www.mathworks.com/products/polyspace/.

88. Patrick Cousot, Radhia Cousot, Jerome Feret, Laurent Mauborgne, Antoine Miné, David Monniaux, and Xavier Rival. The astrée analyzer, volume 3444/2005, pages 21-30. Springer Berlin / Heidelberg, 2005.

89. Thomas A. Henzinger, Ranjit Jhala, Rupak Majumdar, and Grégoire Sutre. Lazy abstraction. SIGPLAN Not., 37(l):58-70, January 2002.

90. Thomas Ball, Ella Bounimova, Byron Cook, Vladimir Levin, Jakob Lichtenberg, Con Mcgarvey, Bohus Ondrusek, Sriram K. Rajamani, and Abdullah Ustuner. Thorough static analysis of device drivers. SIGOPS Oper. Syst. Rev., 40(4):73-85, October 2006.

91. David Evans, John Guttag, James Horning, and Yang M. Tan. Lclint: a tool for using specifications to check code. SIGSOFT Softw. Eng. Notes, 19(5): 87-96, December 1994.

92. David Evans and David Larochelle. Improving security using extensible lightweight static analysis. IEEE Software, 19(1):42-51, /2002.

93. Nurit Dor, Michael Rodeh, and Mooly Sagiv. Cssv: towards a realistic tool for statically detecting all buffer overflows in c. SIGPLAN Not., 38(5): 155-167, May 2003.

94. Patrice Godefroid. The soundness of bugs is what matters (position statement). In BUGS'2005 (PLDI'2005 Workshop on the Evaluation of Software Defect Detection Tools), 2005.

95. David Hovemeyer and William Pugh. Finding bugs is easy. SIGPLAN Not., 39(12):92-106, December 2004.

96. Klocwork. Системы анализа исходного кода, http://www.klocwork.com/products/, апрель 2008.

97. Ted Kremenek and Dawson Engler. Z-Ranking: Using Statistical Analysis to Counter the Impact of Static Analysis Approximations, pages 1075-1075. 2003.

98. William R. Bush, Jonathan D. Pincus, and David J. Sielaff. A static analyzer for finding dynamic programming errors. Softw. Pract. Exper., 30(7):775-802, 2000.

99. Yungbum Jung, Jaehwang Kim, Jaeho Shin, and Kwangkeun Yi. Taming False Alarms from a Domain-Unaware С Analyzer by a Bayesian Statistical Post Analysis, pages 203-217. 2005.

100. Kwangkeun Yi, Hosik Choi, Jaehwang Kim, and Yongdai Kim. An empirical study on classification methods for alarms from a bug-finding static с analyzer. Inf. Process. Lett., 102(2-3):118-123, 2007.

101. Yichen Xie, Andy Chou, and Dawson R. Engler. Archer: using symbolic, path-sensitive analysis to detect memory access errors. In ESEC / SIGSOFT FSE, pages 327-336, 2003.

102. Dawson R. Engler, David Y. Chen, and Andy Chou. Bugs as inconsistent behavior: A general approach to inferring errors in systems code. In Symposium on Operating Systems Principles, pages 57-72,2001.

103. Coverity. Static source code analysis solutions, http://www.coverity.com.

104. GrammaTech, Inc. CodeSonar. http://www.grammatech.com/products/codesonar/overview.html.

105. Mooly Sagiv, Thomas Reps, Reinhard Wilhelm. Parametric shape analysis via 3-valued logic. // ACM Transactions on Programming Languages and Systems vol. 24, №3 2002. Pp. 217-298.

106. VMProtect Software. Vmprotect software protection, 2008. http://vmpsoft.com/

107. Oreans Technologies. Code virtualizer: Total obfuscation against reverse engineering, Dec. 2008. http://www.oreans.com/codevirtualizer.php

108. Лицензирование, шифрование, сжатие и защита программного обеспечения от взлома и исследования. http://setisoft.com/?lang=ru

109. Профессиональная система лицензирования и защиты программного обеспечения для Windows, http://enigmaprotector.com/ru

110. Safengine Protector, http://www.safengine.com/en-us/products/protector

111. SoftlCE. Kernel mode debugger for Microsoft Windows. http://en.wikipedia.org/wiki/SoftICE

112. Крис Касперски, Ева Рокко. Искусство дизассемблирования. / БХВ-Петербург, 2008. 896 стр.

113. Linux Kernel Debugger Linice. http://www.linice.com/

114. IceExt memory dumper, http://sourceforge.net/projects/iceext/

115. SoftwarePassport. http://www.siliconrealms.com/

116. OllyDbg. 32-bit assembler level analyzing debugger for Microsoft Windows. http://www.ollydbg.de/

117. Syser Kernel Debugger, http://www.sysersoft.com/

118. Debugging Tools for NT-Based Operating Systems, http://msdn.microsoft.com/en-us/library/windows/hardware/ff544635%28v=vs.85%29.aspx

119. Chris Eagle. IDA Pro Book. The Unofficial Guide to the World's Most Popular Disassembler. No Starch Press San Francisco, CA, USA 2008.

120. Dotfuscator Community Edition 4.0. http://msdn.microsoft.com/ru-ru/library/ms227240%28v=vs.90%29.aspx

121. Heng Yin and Dawn Song. TEMU: Binary Code Analysis via Whole-System Layered Annotative Execution. / Technical Report No. UCB/EECS-2010-3 January 11, 2010.

122. Fabrice Bellard. QEMU, a Fast and Portable Dynamic Translator. // Proceedings of the annual conference on USENIX Annual Technical Conference, 2005. p. 41.

123. Anderson, P., Reps, Т., and Teitelbaum, Т., Design and implementation of a fine-grained software inspection tool. // In IEEE Trans, on Software Engineering 29 8 (Aug. 2003), pp. 721-733.

124. Balakrishnan, G. and Reps, T. Analyzing memory accesses in x86 executables. // In Proc. Int. Conf. on Compiler Construction, Springer-Verlag, New York, NY, 2004, pp. 5-23.

125. Balakrishnan, G., Gruian, R., Reps, Т., and Teitelbaum, Т., CodeSurfer/x86 A platform for analyzing x86 executables, (tool demonstration paper). // In Proc. Int. Conf. on Compiler Construction, April 2005.

126. CodeSonar for Intel x86. http://www.grammatech.com/research/products/index.html

127. Horwitz, S. and Reps, T. and Binkley, D. Interprocedural slicing using dependence graphs. // In Proc. Of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation. Pp. 35-46.

128. T. Reps, G. Balakrishnan, and J. Lim. Intermediate-representation recovery from low-level code. // Proceedings of the 2006 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, 2006. Pp. 100-111.

129. GCC: the GNU Compiler Collection.// http://gcc.gnu.org/

130. The LLVM Compiler Infrastructure.// http://llvm.org/

131. Sebastian Pop, Albert Cohen, Cédric Bastoul, Sylvain Girbal, Georges-André Silber, Nicolas Vasilache. "GRAPHITE: Polyhedral Analyses and Optimizations for GCC" // http://gcc.gnu.org/wiki/Graphite?action=AttachFile&do=view&target=graphitepaper.pdf

132. SPEC CPU 2000 benchmarks, http://spec.org/cpu2000

133. Andrey Belevantsev, Maxim Kuvyrkov, Vladimir Makarov, Dmitry Melnik, Dmitry Zhurikhin. An interblock VLIW-targeted instruction scheduler for GCC. In Proceedings of GCC Developers' Summit 2006, Ottawa, Canada, June 2006, pp.1-12.

134. А. Белеванцев, M. Кувырков, Д. Мельник. Использование параллелизма на уровне команд в компиляторе для Intel Itanium. Труды ИСП РАН, т.9, 2006, с.9-22.

135. Andrey Belevantsev, Dmitry Melnik, and Arutyun Avetisyan. Improving a selective scheduling approach for GCC. GREPS: International Workshop on GCC for Research in Embedded and Parallel Systems, Brasov, Romania, September 2007.

136. Целевые архитектуры, поддерживаемые семейством компиляторов GCC. http://gcc.gnu.org/backends.html

137. Лицензия GNU GPL. http://www.gnu.org/copvleft/gpl.html

138. Первая версия автоматической векторизации LLVM. http://llvm.org/viewvc/llvm-project?view=rev&revision=l 49468

139. Отладчик LLDB для LLVM. http://lldb.llvm.org/

140. Компилятор переднего плана DragonEgg для LLVM. http://dragonegg.llvm.org/

141. MPI: A Message-Passing Interface Standard. Version 3.0 Message Passing Interface Forum March 14th, 2011

142. Mark Baker, Bryan Carpenter, and Aamir Shafi. MPJ Express: Towards Thread Safe Java HPC, Submitted to the IEEE International Conference on Cluster Computing (Cluster 2006), Barcelona, Spain, 25-28 September, 2006.

143. A. V. Aho, M.S. Lam, R. Sethi, J. D. Ullman. "Compilers: principles, techniques, and tools." 2nd ed., Pearson Education Inc., 2007, p.836.

144. D. E. Knuth, "An empirical study of FORTRAN programs," Software Practice and Experience, vol. 1, 1971, pp. 105-133.

145. A. Matthew, S. J. Fink, D. Grove, M. Hind, and P. F. Sweeney, "A Survey of Adaptive Optimization in Virtual Machines" // Proceedings of the IEEE, 93(2), 2005. Special issue on program generation, optimization, and adaptation

146. Khalid Al-Tawil, Csaba Andras Moritz. Performance Modeling and Evaluation of MPI. // Journal of Parallel and Distributed Computing, Vol. 61, No 2, pp. 202-223, 2001.

147. Ron Hitchens. Java NIO. O'Reily Media, Ink., 2002. ISBN 0-596-00288-2

148. В. А. Падарян. Оценка времени работы параллельной программы с помощью интерпретатора среды ParJava. / Препринт Института Системного Программирования РАН №6. М.:ИСП РАН, 2005.

149. Библиотека Libc++ для LLVM. http://libcxx.llvm.org/

150. Mark D. Hill, Michael R. Marty: Amdahl's Law in the Multicore Era. IEEE Computer (2008) vol. 41, No 7, hh 33-38

151. John L. Gustafson: Reevaluating Amdahl's Law. Commun. ACM (1988) vol. 31 No 5, pp 532-533

152. Арсеньев C.A., Губарь А.Ю., Николаевский B.H. Самоорганизация торнадо и ураганов в атмосферных течениях с мезомасштабными вихрями. //ДАН, 2004, т.396, № 4, с.541-546.

153. Хргиан А.Х. Физика атмосферы. М: Изд-во Московского Университета, 1986. С.240.

154. Nikolaevskiy V.N. Angular Momentum in Geophysical Turbulence: Continuum. Spatial Averaging Method . Dordrecht: Kluwer (Springer). 2003. p. 245.

155. Хаин А.П., Сутырин Г.Г. Тропические циклоны и их взаимодействие с океаном. Л.: Гидрометеоиздат, 1983. С.272.

156. Емцев Б.Т. Техническая гидромеханика. М.: Машиностроение, 1978. С.463.

157. J.C. Adams, W.S. Brainard, J.T. Martin, B.T. Smith, J.L. Wagener. Fortran 95 Handbook. Complete ISO/ANSI Reference. Scientific and Engineering Computation Series. MIT Press, Cambridge, Massachusetts, 1997

158. Флетчер К. Вычислительные методы в динамике жидкостей (2т). М.: Мир, 1991. С.504, С.522.

159. Gilbert Anthony. Tornado With a Measured Intensity of T3 at Hill Head, Hampshire, 5, November 1999. // J.Meteorol. 2000. 25, N254. c.361-367.

160. VisAD Java component library for interactive and collaborative visualization and analysis of numerical data, http://www.ssec.wisc.edu/~billh/visad.html.

161. P. Cousot and R. Cousot. Static determination of dynamic properties of programs. In Proceedings of the Second International Symposium on Programming, pages 106—130, Dunod, Paris, France, 1976.

162. A. Milanova. Precise and Practical Flow Analysis of Object-Oriented Software. PhD thesis, Rutgers University, Available as Techical Report DCS-TR-539, August, 2003.

163. Antoine Mine. Field-Sensitive Value Analysis of Embedded С Programs with Union Types and Pointer Arithmetic. Proceedings of LCTES'06, June 2006.

164. L. O. Andersen. Program Analysis and Specialization for the С Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994.

165. M. Emami, R. Ghiya, and L. Hendren. Context-Sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers. In Proceedings of the SIGPLAN '94 Conference on Program Language Design and Implementation, Orlando, US, 1994.

166. M. Burke, P. Carini, J.-D. Choi, and M. Hind. Flow-insensitive interprocedural alias analysis in the presence of pointers. Lecture Notes in Computer Science, 892, pages 234-250. Springer-Verlag, 1995.

167. J.-D. Choi, M. Burke, and P. Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In 20th Annual ACM SIGACT-SIGPLAN Symposium on the Principles of Programming Languages, pages 232-245, January 1993

168. M. Hind, M. Burke, P. Carini, and J.-D. Choi. Interprocedural pointer alias analysis. ACM Transactions on Programming Languages and Systems, 21(4):848-894, July 1999.

169. W. Landi. Undecidability of static analysis. ACM Letters on Programming Languages and Systems, l(4):323-337, December 1992.

170. G. Ramalingam. The undecidability of aliasing. ACM Transactions on Programming Languages and Systems,16(5):1467-1471, September 1994.

171. T. J. Marlowe, B. G. Ryder, and M. G. Burke. Defining flow sensitivity in data flow problems. Technical Report RC20138, IBM T. J. Watson Research Center, July 1995.

172. M. Shapiro and S. Horwitz. Fast and accurate flow-insensitive point-to analysis. In 24th Annual ACMSIGACT-SIGPLAN Symposium on the Principles of Programming Languages, pages 114, January 1997.

173. S. Zhang, B. G. Ryder, and W. Landi. Program decomposition for pointer aliasing: A step toward practical analyses. In 4th Symposium on the Foundations of Software Engineering, pages 8192, October 1996.

174. D. Liang and M. J. Harrold. Efficient points-to analysis for whole-program analysis. In O. Nierstrasz and M. Lemoine, editors, Lecture Notes in Computer Science, 1687, pp 199-215. SpringerVerlag, September 1999.

175. A. Diwan, K. S. McKinley, and J. E. B. Moss. Type-based alias analysis. In SIGPLAN '98 Conference on Programming Language Design and Implementation, pages 106-117, June 1998.

176. Лицензия BSD, http://www.opensource.org/licenses/bsd-license.php

177. Стандарт OpenCL. http://www.khronos.org/opencl/

178. Vladimir Makarov. The finite state automaton based pipeline hazard recognizer and instruction scheduler in GCC. In Proceedings of GCC Developers' Summit, Ottawa, Canada, June 2003.

179. S. Swanson, L. K. McDowell, M. M. Swift, S. J. Eggers and H. M. Levy. An evaluation of speculative instruction execution on simultaneous multithreaded processors. ACM Trans. Comput. Syst. 21,3 (Aug. 2003), pp. 314-340.

180. А.А.Белеванцев, С.С.Гайсарян, В.П.Иванников. Построение алгоритмов спекулятивных оптимизаций. Журнал Программирование, N3 2008, с. 21-42.

181. Dmitry Melnik, Sergey Gaissaryan, Alexander Monakov, Dmitry Zhurikhin. An Approach for Data Propagation from Tree SSA to RTL. GREPS: International Workshop on GCC for Research in Embedded and Parallel Systems, Brasov, Romania, September 2007.

182. Маликов О.P. Исследование и разработка методики автоматического обнаружения уязвимостей в исходном коде программ на языке Си. Диссертация на соискание звания к.ф-м.н., Москва, 2006.

183. Diego Novillo. A Propagation Engine for GCC. In Proceedings of GCC Developers' Summit 2005, Ottawa, Canada, July 2005, pp. 175-184.

184. Инструмент Coverity Prevent, http://www.coverity.com/library/pdf/coverityprevent.pdf

185. Инструмент статического анализа компании Klocwork. http://www.klocwork.com/products/insight/klocwork-truepath

186. P. Emanuelsson & U. Nilsson. A Comparative Study of Industrial Static Analysis Tools (extended version). Tech. rep., Linkoping University, 2008.

187. Среда Eclipse, http://www.eclipse.org/

188. D. Liang & M. J. Harrold. Efficient Computation of Parameterized Pointer Information for Interprocedural Analyses. In SAS '01: Proceedings of the 8th International Symposium on Static Analysis, pp. 279-298, London, UK, Springer-Verlag, 2001.

189. T. Kremenek, D. Engler. Z-Ranking: Using Statistical Analysis to Counter the Impact of Static Analysis Approximations. Static Analysis, pp. 295-315, 2003 — Springer.

190. Portable Executable and Object File Format Specification http://download.microsoft.eom/download/e/b/a/ebal050f-a31d-436b-9281-92cdfeae4b45/pecoff.doc

191. Tool Interface Standards (TIS). Executable and Linkable Format (ELF), http://www.x86.org/intel.doc/tools.htm

192. IDA Pro Disassembler, http://www.hex-rays.com/idapro/.

193. Fast Library Identification and Recognition Technology (FLIRT), http://www.idapro.ru/description/flirt/.

194. H. Yin, Z. Liang, D. Song. HookFinder: Identifying and Understanding Malware Hooking Behaviors. // Proceeding of the 15th Annual Network and Distributed System Security Symposium (NDSS'08), 2008

195. P. S. Magnusson, M. Christensson, J. Eskilson, D. Forsgren, G. Hallberg, J. Hogberg, F. Larsson, A. Moestedt, and B. Werner. Simics: A Full System Simulation Platform. // IEEE Computer, 35(2):50-58, Feb. 2002.

196. S. Debray, J. Patel. Reverse Engineering Self-Modifying Code: Unpacker Extraction. // Proceedings of the 17th. IEEE Working Conference on Reverse Engineering, Oct. 2010, pp 131-140.

197. Wang C., Hill J., Knight J,. Davidson J. Software tamper resistance: obstructing static analysis of programs // Tech. Rep., N 12, Dep. of Сотр. Sci., Univ. of Virginia, 2000.

198. Weiser M. Program slicing // Proceedings of the 5th International Conference on Software Engineering. // IEEE Computer Society Press, 1981. pp. 439^149.

199. Korel В., Laski J. Dynamic program slicing // Information Processing Letters, Vol. 29, Issue 3.1988,pp.155-163

200. А. Тихонов, А. Аветисян, В. Падарян. Методика извлечения алгоритма из бинарного кода на основе динамического анализа. // Проблемы информационной безопасности. Компьютерные системы. №3 2008. стр. 66-71

201. В.А. Падарян, М.А. Соловьев, А.И. Кононов. Моделирование операционной семантики машинных инструкций. // Программирование №3, 2011. стр. 50-64

202. Wireshark. http://www.wireshark.org/ дата обращения 22 апреля 2012

203. Network Driver Interface Specification 5.1 http://msdn.microsoft.com/en-us/library/ff556916.aspx дата обращения 22 апреля 2012

204. Trivial File Transfer Protocol (revision 2) http://www.ietf.org/rfc/rfcl350.txt дата обращения 22 апреля 2012

205. DOMAIN NAMES IMPLEMENTATION AND SPECIFICATION http://www.ietf.org/rfc/rfcl 035.txt November 1987

206. Domain Name System. Obsoleting IQUERY http://www.ietf.org/rfc/rfc3425.txt November 2002

207. А.И. Гетьман, Ю.В. Маркин, В.А. Падарян, Е.И. Щетинин. Восстановление формата данных. // Труды Института системного программирования РАН, том 19, 2010, стр. 195-214

208. Bitmap Storage http://msdn.microsoft.com/en-us/library/ddl83391(VS.85).aspx дата обращения 22 апреля 2012

209. J. Newsome and D. Song. Dynamic Taint Analysis for Automatic Detection, Analysis, and Signature Generation of Exploits on Commodity Software. // In Proceedings of the Network and Distributed System Security Symposium (NDSS 2005), 2005

210. J. Caballero , H. Yin ,Z. Liang ,D. Song . Polyglot: Automatic Extraction of Protocol Message Format using Dynamic Binary Analysis. // In Proceedings of the 14th ACM Conference on Computer and and Communications Security, 2007, pp. 317—329.

211. Z. Lin, X. Jiang, D. Xu, X. Zhang. Automatic Protocol Format Reverse Engineering through Context-Aware Monitored Execution. // In Network and Distributed System Security, 2008.

212. G. Wondracek, P. Milani Comparetti, C. Kruegel, E. Kirda. Automatic Network Protocol Analysis. // In 15th Symposium on Network and Distributed System Security, 2008.

213. W. Cui, M. Peinado, K. Chen, H. J. Wang, L. Irun-Briz. Tupni: Automatic Reverse Engineering of Input Formats. // Proceedings of the 15th ACM conference on Computer and communications security, 2008, pp. 391—402.

214. G. A. Venkatesh: The Semantic Approach to Program Slicing. // Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation (PLDI '91). pp. 26—28.

215. J. Caballero. Grammar and Model Extraction for Security Applications using Dynamic Program Binary Analysis. / PhD thesis in Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, September 2010

216. OSCAR «Open System for Communication in Realtime» http://iserverdl.khstu.ru/oscar/ Обновлено 07.02.2005

217. M. Venable, M.R. Chouchane, M.E. Karim, and A. Lakhotia. Analyzing memory accesses in obfuscated x86 executables. In DIMVA'05, pages 1-18, 2005.

218. А. Белеванцев, Д. Журихин, Д. Мельник. Компиляция программ для современных архитектур. Труды Института системного программирования РАН, том 17, 2009 г. стр. 31-50.

219. Portable Native Client Introduction, http://www.chromium.org/nativeclient/pnacl/building-and-testing-portable-native-client

220. Chris Lattner. LLVM: An Infrastructure for Multi-Stage Optimization.// Master's thesis, Computer Science Dept., University of Illinois at Urbana-Champaign, Urbana, IL, 61 pages.

221. Omri Traub, Stuart Schechter, Michael D. Smith. Ephemeral Instrumentation for Lightweight Program Profiling, 2000. www.eecs.harvard.edu/hube/publications/muck.pdf. Date retrieved: October 7, 2011.

222. OProfile official website, http://oprofile.sourceforge.net.

223. Java Virtual Machine Profling Interface documentation. http://download.oracle.eom/javase/l.4.2/docs/guide/jvmpi/jvmpi.html.

224. Vinodha Ramasamy, Robert Hundt, Dehao Chen, Wenguang Chen. Feedback-Directed Optimizations in GCC with Estimated Edge Profiles from Hardware Event Proceedings of GCC Summit 2008. http://research.google.com/pubs/pub36576.html.

225. U. Zwick. The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate. Theoretical Computer Science, 1995, Vol. 148.

226. R. Levin. Complementing Incomplete Edge Profile by applying Minimum Cost Circulation Algorithms. Master's thesis, University of Haifa, 2007. http://www.cs.technion.ac.il/~royl/MscThesisFinalVersionSubmission.pdf.

227. Fabrizio Petrini, Wu-chun Feng, Adolfy Hoisie, Salvador Coll, Eitan Frachtenberg: The Quadrics Network: High-Performance Clustering Technology. // IEEE Micro, 2002, Volume 22, No l,pp 46-57.

228. Myrinet Overview, 2011 // http://web.archive.org/web/20110514103424/http://www.myricom.com/myrinet/overview/

229. Кевин Дайерлинг. InfiniBand: архитектура коммутации для серверов, запоминающих устройств и коммуникационных систем // Мир компьютерной автоматизации on-line, № 3, 2002, http://www.mka.ru/?p=44434

230. Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий. Второе издание. Москва, Вильяме, 2008.

231. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы. Построение и анализ. Москва, МЦНМО, 1999.а/