Методы построения графо-аналитических моделей функциональных программ тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Лаздин, Артур Вячеславович

• Лаздин, Артур Вячеславович
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Лаздин, Артур Вячеславович

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

1.1 Программа как объект исследования.

1.2 Методы контроля программ

1.2.1 Статический анализ программ

1.2.2 Динамический анализ программ. 18 1 2.3 Другие методы анализа

1.3 Место методов анализа в жизненном цикле ПО

1.4 Постановка задачи 38 Выводы

ГЛАВА 2. МЕТОД ВОССТАНОВЛЕНИЯ УПРАВЛЯЮЩЕГО ГРАФА

ФУНКЦИОНАЛЬНОЙ ПРОГРАММЫ ПО ЕЕ ИСПОЛНЯЕМОМУ КОДУ.

2.1 Формальные модели программ.

2.2 Типы и структуры исполняемых модулей.

2.2.1 Обобщенный формат команды процессора

2.2 2 Графовое представление исполняемого кода.

2.2.3. Графо-аналитическая модель исполняемого модуля.

2.3 Метод формирование управляющего графа функциональной программы.

2.4 Оценка степени сложности управляющего графа ФП. 67 Выводы

ГЛАВА 3. СТРУКТУРНО-ФУНКЦИОНАЛЬНАЯ ДЕКОМПОЗИЦИЯ

УПРАВЛЯЮЩЕГО ГРАФА ФУНКЦИОНАЛЬНОЙ ПРОГРАММЫ.

3.1 Поиск процедур. Алгоритмы. 78 3.3. Поиск параметров процедур.

3.2 Поиск циклов. Алгоритмы.

3.4 Поиск параметров цикла.

3.5 Поиск инвариант цикла.

Выводы

ГЛАВА 4. ПРОГРАММНАЯ СИСТЕМА ВОССТАНОВЛЕНИЯ УПРАВЛЯЮЩЕГО

ГРАФА ФУНКЦИОНАЛЬНОЙ ПРОГРАММЫ.

4.1 Общая структура программной системы.

4.2 Модуль имитатора загрузчика.

4.3 Модули дешифрации и поиска КУПК

4.5 Модуль формирования и сортировки списка вершин

4.6 Модули поиска процедур и циклов

4.6 Модуль формирования матриц

4.7 Методика работы с программной системой

4 7 1 Чтение данных из заголовка исполняемого модуля.

4 7.2 Запись в файл дампа ИМ.

4.7.3 Дизассемблирование команд ИМ.

4.7.4 Формирование и сортировка предварительного списка вершин 117 4.7.5. Поиск адресов начала и конца всех процедур ИМ.

4.7.6 Поиск адресов начала и конца всех циклов ИМ и определение их вложенности.

4.7.7 Запуск программной системы 120 Выводы

Введение диссертации (часть автореферата) на тему «Методы построения графо-аналитических моделей функциональных программ»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Внедрение результатов. Разработанная программная система формирования и декомпозиции управляющего графа функциональной программы используется в СПбГУ ИТМО на кафедре информатики и прикладной математики в рамках учебно-исследовательской САПР верификации и тестирования для анализа результатов лабораторных работ по курсам «Системное программное обеспечение», «Программирование на языке ассемблер», «Технология программирования» для студентов специальности 230101 «Вычислительные машины, системы, комплексы и сети».

Апробация работы Основные результаты диссертационной работы докладывались и получили одобрение на Всероссийской научно-технической конференции «Диагностика веществ, изделий и устройств» (Орел, 1999), научно-технических конференциях профессорско-преподавательского состава ИТМО (С.-Петербург 1999, 2000, 2002, 2003 г.г.).

Публикации. По материалам диссертации опубликовано 10 работ.

Структура и объем работы Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 72 наименований содержит 142 страниц текста, 21 рисунок и 9 таблиц.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Лаздин, Артур Вячеславович

Выводы.

1. Описана программная система восстановления управляющего графа ФП по предложенным в диссертационной работе методу формирования управляющего графа и модели представления ИК и методам его функциональной (процедурной) и структурной декомпозиции.

2. Рассмотрен и описан функциональный состав разработанной программной системы. Система реализована на алгоритмическом языке высокого уровня С++ и содержит более 3000 строк кода.

3. В тексте диссертационной работы приводятся примеры обращения к разработанной программной системе и пример обработанного ей файла. t

ЗАКЛЮЧЕНИЕ

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

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

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

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

5. Разработаны алгоритмы поиска процедур и циклических участков исполняемого кода программы

6. Разработана программная система восстановления и декомпозиции управляющего графа исполняемого кода программы.

Список литературы диссертационного исследования кандидат технических наук Лаздин, Артур Вячеславович, 2009 год

1. Абрамов. С.А. Элементы анализа программ. -М.: Наука. 1986. 128с.

2. Андерсон Р. Доказательство правильности программ. -М.: Мир. -1982,- 168с.

3. Баранов С.Н., Домарацкий А.Н., Ласточкин Н.К., Морозов В.П., Практическая модель процесса разработки программных изделий. //Программные продукты и системы. 1998. N 4. с. 7-14.

4. Баскерт Р. Саати Т. Конечные графы и сети. М.: Наука. 1974. 368с.

5. Бейбер JI.P. Программное обеспечение без ошибок. М. Радио и связь, 1996. 173 с.

6. Бромберг И.А. Система контроля этапов жизненного цикла ПО // Открытые системы. 1998. N6. с. 47-52.

7. Буч Г. Объектно-ориентированное проектирование с примерами применения. М.: Конкорд, 1992.

8. Бурдонов И.Б., Демаков А.В., Косачев А.С., Максимов А.В., Петренко А.К. Формальные спецификации в технологиях обратной инженерии и верификации программ // Труды Института системного программирования Российской Академии наук. N 1, 1999.

9. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ,- М.: Мир, 1985. 332 с.

10. Ю.Вендров A.M. CASE-технологии. Современные методы и средства проектирования информационных систем. М.: Финансы и статистика, 1998.176с.

11. П.Вирт Н. Алгоритмы + структуры данных = программы: Пер. с англ. М.: Мир, 1985. 406с.

12. Воас Д. Качество ПО: восемь мифов // Открытые системы. 1999. N9-10.

13. Вьюкова Н.И., Галатенко В.А., Ходулев А.Б. Систематический подход к программированию. М.: Наука. Гл. ред. физ.-мат. лит., 1988. 208 с.

14. Н.Гацко Г. Тестирование ПО как один из элементов системы качества // Открытые системы. 1998. N6.

15. Григорьев B.JI. i486. Архитектура и программирование. М.: ГРАНАЛ, 1993.- 338 с.

16. Грис. Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975. - 544с.

17. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир. 1981. 366с.

18. Дейкстра Э. Дисциплина программирования. М.: Мир, 1978. 275с.

19. Калинин СВ., Туренко Д.Л. Построение дерева вызовов в задаче анализа исполняемого кода API Win32 // Труды научной конференции по радиофизике ННГУ, 2001г. с.357,358

20. Котляров В.П. CASE-технология и возможности современных CASE-средств в поддержке этапов проектирования программного проекта // Сметем, информат. 1995. N4. С. 272-303.

21. Коул Дженнифер, Горэм Томас, МакДональд Марк, Спарджеон Роберт. Принципы тестирования ПО // Открытые системы (Изд-во "Открытые системы"). 1998. № 2.

22. Кузнецов Б.П. Структура и сложность модулей циклических программ // Автоматика и телемеханика. 1999. N2.2 8. Кузьминский М., Волков Д. Современные суперкомпьютеры: состояние и перспективы // Открытые системы. 1995. N6. с. 33-40.

23. Лаздин А.В. Способы машинного представления графа переходов функциональной программы. / Тез. докл. XXX научно-технической конференции профессорско-преподавательского состава СПб ГИТМО (ТУ), 1999 с.94.

24. Лаздин А.В. Немолочнов О.Ф. Использование графа переходов функциональной программы для синтеза испытательных последовательностей. / Тез. докл. XXX научно-технической конференции профессорско-преподавательского состава СПб ГИТМО (ТУ), 1999 г. с. 94.

25. Лаздин А.В. Построение графа функциональной программы. Материалы Всероссийской научно-технической конференции «Диагностика веществ, изделий и устройств». Орел, 1999 с. 190.

26. Лаздин А.В. Немолочнов О.Ф. Функциональная программа как объект тестирования и верификации. Тез. докл. научно-техническойконференции профессорско-преподавательского состава СПб ГИТМО (ТУ), 2000 с. 6.

27. Лаздин А.В. Алгоритмы построения списка вершин графа программы. / Тез. докл. научно-технической конференции профессорско-преподавательского состава СПб ГИТМО (ТУ), 2000. с. 7.

28. Л аз дин А.В., Немолочнов О.Ф. Оценка сложности графа функциональной программы / Научно-технический вестник СПБ ГИТМО (ТУ). Выпуск 6. Инфориационные, вычислительные и управляющие системы / Гл. ред. В.Н. Васильев. СПб.: СПбГИТМО (ТУ), 2002.

29. Лаздин В.П., Лаздин А.В. Измерение температуры по ИК-излучению с автоматическим учетом коэффициента черноты объекта измерения. // Тепловые режимы и охлаждение радиоэлектронной аппаратуры. 1998. N 1. с.55-60.

30. Липаев В.В. Качество программного обеспечения. -М.: ФиС, 1983. -263с.

31. Липаев В.В. Отладка сложных программ. Методы, средства, технология. -М.: Энергратомиздат, 1993. -384 с.

32. Липаев В В. Надежность программных средств. М.: СИНТЕГ, 1998, - 232 с.

33. Липаев В.В. Управление разработкой программных средств: Методы, стандарты, технология. М.: Финансы и статистика, 1993.

34. Липаев В.В. Проектирование программных средств. М.: Высшая школа, 1990

35. Липаев В.В. Тестирование программ. М.: Радио и связь, 1986 296 с.

36. Логунова О.А. Лаздин А.В. Пухтеева Е.А. Рекурсивный алгоритм формирования списка вершин графа переходов функциональной программы. Сборник научных трудов молодых ученых и специалистов СПб ГИТМО (ТУ), 2000 с. 31-35.

37. Майерс Г. Искусство тестирования программ. М.: Мир, 1982. 212с.

38. Матвеев В.А., Молотков С.В., Зегжда Д.П.,Мешков А.В., Семьянов П.В., Шведов Д.В.Основы верификационного анализа безопасности исполняемого кода программ.Под редакцией проф. Зегжды П.Д. СПб.: СПбГТУ, 1994. 58 с.

39. Международные стандарты, поддерживающие жизненный цикл программных средств. М.: МП "Экономика", 1996.

40. Мельников И.А., Раабе А.С., Тамм Б.Г. Инструментарий машинной поддержки цикла жизни программного обеспечения. Обзор западных средств//Прикладная информатика. 1988. Вып. 14. С. 16-40.

41. Миндубаева Н.Н. Лаздин А.В. Поиск процедур по графу переходов функциональной программы. Сборник научных трудов молодых ученых и специалистов СПб ГИТМО (ТУ), 2000 с. 26-31.

42. Непомнящий В.А., Рякин О.М. Прикладные методы верификации программ. М.: Радио и связь, 1988.

43. Никифоров В.В., Домарацкий Я.А. Системное тестирование программных изделий. // Программные продукты и системы. 1998. N 4. с. 40-46.51.0ре О. Теория графов. -М.: «Наука», 1968. 352с.

44. Основы верификационного анализа безопасности исполняемого кода программ. / Матвеев В.А., Молотков С.В., Зегжда Д.П.,Мешков А.В., Семьянов П.В., Шведов Д.В. Под редакцией проф. Зегжды П.Д. СПб.: СПбГТУ, 1994. 58с.

45. Отладка систем управляющих алгоритмов ЦВМ реального времени. Под ред. В.В. Липаева. М.: - РиС, 1974. - 326с.

46. Пильщиков В.Н. Программирование на языке ассемблера IBM PC. М.: "ДИАЛОГ-МИФИ", 1994. 288 с.

47. Поттосин И.В. О критериях добротности программ //Системная информатика. Вып.6. Новосибирск: Наука, 1998.

48. Потосин И.В. «Хорошая программа»: попытка точного определения понятия. //Программирование. 1997. N2. с. 3-17.

49. Пратт Т. Языки программирования: разработка и реализация. М.: Мир, 1979.-472с.5 8. Промышленные контроллеры фирмы "Matsushita". Matsushita Automation Controls.

50. Романюк С.Г. Оценка надежности программного обеспечения. // Открытые системы. 1994. N4. с.24-28.

51. Семьянов П.В. Автоматизация поиска неизвестных разрушающих программных средств в исполняемом коде. // Всероссийская научно-техническая конференция «Методы и технические средства защиты информации», тезисы докладов, СПбГТУ, 1995.

52. Сингер М. Мини-ЭВМ PDP-11: программирование на языке ассемблера и организация машины. М.: Мир, 1984. 272 с.

53. Требования и спецификации в разработке программ. М.: Мир, 1984. 344 с.

54. Хьюз Д., Мичтом Д. Структурный подход к программированию. М.: Мир, 1980.-С. 29-71.

55. Шалыто А. А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998.

56. Alur R., Henzinger Т., Pei-Hsin Но. Automatic symbolic verification of embedded systems //IEEE Trans, on Software Eng. 1996. N3.

57. Bell C.G., Gray J. What's next in high-performance computing? // Communications of the ACM (CACM). 2002. Vol. 45. No.2. P. 91-95.

58. Bell D., Morrey I., Pogh J. Software Engineering. A programming Approach. Prentice Hall, 1992. 338p.

59. Corbett J.C. Evaluating deadlock detection methods for concurrent software //IEEE Trans, on Software Eng. 1996. N2.

60. Humphery G. Managing the Software Process. Reading: Addison-Wesley, 1989.-494p.

61. IA-32 Intel® Architecture Software Developer's Manual Volume 1 г Basic Architecture http://developer.intel.ru/design/pentium4/manuals/245470.htm

62. Lowry M Analytic Verification and Validation for Space Missions. NASA Ames Research Center http://is.arc.nasa.gov/AR/projects/AtnVrf.html

63. Revised version of DP9126 Criteria of the Evaluation of Software Quality Characteristics. ISO TC97/SC7 #610. - Part 6.1. ПРИЛЖЕНИЯ