Введение к работе
Актуальность проблемы. Рынок программного обеспечения предоставляет широкий спектр программных продуктов различного назначения и сложности. Увеличение числа новых программных средств, повышенное требование к надежности их функционирования при существенном усложнении алгоритмов делают актуальной проблему проведения сертификационных испытаний программных средств. В то же время, в существующих методиках испытаний и инструментальных программных средствах для таких испытаний пока не реализованы современные математические методы и модели, что не позволяет в должной степени обеспечивать объективность и точность результатов испытаний, а также автоматизировать их. Кроме того, для лабораторий, специализирующихся на разработке и анализе программных продуктов различного назначения, актуально решение таких задач, как оптимизация программ, идентификация свойств программ, структурирование программ с целью упрощения верификации и эффективного внесения изменений при получении новых версий программ, автоматизация исследования исполняемых модулей.
Процедура проведения сертификации программного средства предполагает в ходе испытания выявление свойств этого программного продукта таких, как реентерабельность программы, среда функционирования, взаимодействие с файловой системой жесткого диска, наличие резидентной части и т.п. Кроме того, производится сверка заявленных в представленной документации свойств программы с результатами испытаний. Следует отметить, что, как правило, программное средство поступает в лабораторию испытаний программных продуктов в виде исполняемого модуля. В связи с этим стала актуальной задача разработки математического и программного обеспечения для анализа программ на основе исследования исполняемых модулей с использованием теории алгоритмических алгебр и унификации алгоритмических термов.
В ходе работы были исследованы известные теоретические концепции анализа профамм, в частности работы Р. Флойда, П. Наура, Ч. Хоара, Э. Дейкстры, Р. Андерсона, Ю.И. Янова, А.А. Ляпунова, В.М. Глушкова, Р.И. Подловченко, В.А. Евстигнеева, С.А. Нигияна, Л.О. Хачояна и др. Отмечено, что существующие теоретические формализмы анализа профамм нельзя непосредственно использовать для анализа профамм низкого уровня, поскольку они узко направлены, достаточно сложны, что не позволяет использовать их прикладным программистам, малоприменимы для автоматизации исследования профамм, среди них не существует достаточно простого теоретического формализма, применение которого в чистом виде позволило бы исследовать исполняемые и объектные модули. При этом исследование программ, написанных на языках низкого уровня, не получило должной математической формализации, что привело к необходимости проведения исследований в этом направлении.
Использование формальной профаммной машины для анализа объектного кода профамм является малоизученной проблемой. Решение этой проблемы позволило бы упростить не только идентификацию свойств профамм, но и оптимизацию, эквивалентную трансформацию, структуризацию профамм н
>
уровня. Наиболее пригодным математическим аппаратом автоматизации решения упомянутых проблем является теория унификации алгебраических термов.
Вопросам исследования объектного кода программ с использованием алгоритмических алгебр и теории унификации посвящена диссертационная работа.
Целью работы является разработка и исследование способов формального анализа сложных исполняемых, объектных модулей и программ на языках низкого уровня, позволяющих идентифицировать свойства программ, производить оптимизацию, структуризацию и функционально-эквивалентные преобразования на основе теории алгоритмических алгебр.
Методы исследования. Исследования осуществлялись на основе теории алгоритмических алгебр, теории унификации, теории множеств, теории формальных грамматик и языков, методов структурного программирования.
Научная новизна.
-
В диссертации предложена формальная программная машина, ориентированная на исследование и структуризацию программ на языках низкого уровня, объектного кода программ, исполняемых модулей.
-
В работе сформулированы новые принципы идентификации свойств, оптимизации, правил эквивалентной трансформации программ низкого уровня.
-
Построен оригинальный алгоритм частичной унификации программных термов, используемый для исследования свойств объектного кода программ, эквивалентных преобразований без потери исходных функциональных свойств программ.
-
Разработана методология автоматизированной оптимизации и структуризации программ на языках низкого уровня, позволяющая создавать и верифицировать программы с высокими характеристиками надежности и адаптивности.
Практическая ценность. Результаты работы являются основой для проектирования, внесения изменений в инструментальные средства низкого уровня, исследования правильности и нетривиальных свойств готовых программ. Предложенные в диссертации формализм и методы позволяют производить идентификацию свойств, оптимизацию и структуризацию программ низкого уровня.
Результаты диссертации нашли отражение в реальной программе ETest, предназначенной для исследования свойств программ на языках низкого уровня.
Разработанные средства могут быть приняты за основу при создании спецпроцессоров ЭВМ и языкового инструментария низкого уровня.
Внедрение результатов. Результаты диссертационной работы внедрены в Научно-информационном центре проблем интеллектуальной собственности (НИЦПрИС) при Министерстве общего и профессионального образования Российской Федерации и других организациях, что подтверждается соответствующими актами.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Всероссийской научно-технической конференции «Современные информационные технологии в образовании», Рязань, 1996; Меж
дународном научно-техническом семинаре «Проблемы передачи и обработки информации в информационно-вычислительных сетях», Москва, 1997; 2-ой Всероссийской научно-практической конференции «Современные информационные технологии в образовании», Рязань, 1998; научно-технических конференциях профессорско-преподавательского состава Рязанской государственной радиотехнической академии, 1995-1998 гг.
Публикации. По теме диссертации опубликовано 8 работ.
Структура її объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы и двух приложений. Основной текст содержит 162 страницы, в том числе 10 рисунков, 2 таблицы.
Список литературы содержит 82 наименования.
Основные результаты, выносимые на защиту:
концепция анализа программ низкого уровня доступа на основе понятия формальной программной машины, использугошей теорию алгоритмических алгебр;
способы идентификации свойств программ, оптимизации, правила эквивалентной трансформации программ низкого уровня;
новый алгоритм частичной унификации программных термов, предназначенный для автоматизации анализа программ с целью их структурирования и оптимизации;
принципы построения автоматизированных систем для исследования исполняемых модулей, нашедшие применение в практической реализации программы ETest.
