Семантическая отладка программ методом поиска конкретных ошибок тема автореферата и диссертации по математике, 01.01.10 ВАК РФ

Актуальность теш. В настоящее время значительно возрос объем задач, которые можно перевести на язык вычислительных машин. Расширился диапазон естественных наук,для которых на сегодняшний день возможно и необходимо применение вычислительных машин. Основными этапами решения всякой задачи на ЭВМ являются: формализация, которая заключается в ее математическом описании с использованием определенных обозначений и систем правил; программирование-перевод построенной математической модели на язык конкретной ЭВМ, например, на ФОРТРАН; отладка-поиск и устранение из программы ошибок для ее адекватного функционирования согласно математической модели и исходной постановке задачи. Ввиду неформальности и сложности отладки доля времени и других ресурсов, необходимых на поиск и устранение ошибок в программах, может достигать Ъ0% и более от всех выделенных на решение задачи.

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

Цель работы. Целью диссертационной работы является:

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

2) исследование метода отладки программ путем поиска конкретных семантических ошибок, взаимосвязи метода с другими способаш отладки, эффективности метода;

3) разработка командного языка для проведения диалоговой отладки программ пользователя методом поиска конкретных ошибок;

4) разработка эффективных алгоритмов для поиска конкретных семантических ошибок;

5) разработка диалоговой системы отладки, поддерживающей метод поиска конкретных ошибок;

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

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

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

- разработан язык ПОИСК-ДИАЛОГ для проведения семантической отладки программ;

- разработаны алгоритмы анализа исходных текстов программ и поиска семантических ошибок;

- создана диалоговая система отладки КАПКАН-ФОРТРАН на основе метода поиска конкретных ошибок;

- исследованы области применения системы отладки КАПКАН-ФОРТРАН и разработаны методики применения отладочных процедур;

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

Практическая ценность.Диссертационная работа выполнялась в плане работ по научно-технической программе IKHT 0.Ц.025 задания

04.22 "Разработать и ввести в эксплуатацию в опытной зоне РСВЦ УССР программное обеспечение системы отладки, оптимизации, верификации, модификации и документирования программного обеспечения для сетей ЭВМ".

Система КАПКАН-ФОРТРАН внедрена в ряде организаций страны с суммарным экономическим эффектом 180,78 тыс. рублей.

Разработанный метод поиска конкретных ошибок и созданная на его основе система отладки КАПКАН-ФОРТРАН могут использоваться для поиска семантических ошибок в программах распределенной обработки данных, в программном обеспечении АСУ, в пакетах прикладных програш и в отдельных программах, написанных на языке Ф0РТРАН-1У ОС ЕС или его подмножествах.

Публикации и апробация работы. Основные результаты и отдель-,ные разделы диссертационной работы докладывались и обсуждались на I Всесоюзной конференции молодых ученых и специалистов"Уп-равление производством и АСУ"(Одесса, 1980 г.),на Всесоюзной конференции "Программное обеспечение АСУ"(Калинин,1980г.),на Всесоюзной конференции "Синтез, тестирование, верификация и отладка программ" (Рига, 1981г.), на Всесоюзной конференции"Программное обеспечение вычислительных сетей и систем реального времени"(Киев,1981 г.),на Республиканской конференции"Методы и средства повышения эффективности обработки информации в системах управления реального времени" ( Киев, 1982 г.), на I Всесоюзной конференции "Р-технология программирования" (Киев, 1983 г.), на Международной научно-технической конференции"Программное обеспечение ЭВМ" (Калинин,СССР,1984г.),на конференции"Пути повышения качества программного обеспечения ЭВМ"(Севастополь,1984г.),на научных семинарах при Республиканском доме экономической и научно-технической пропаганды (Киев, 1983г., 1984г.), на научных семинарах в Московском госуниверситете (1984 г.), в Вычислительном центре АН

СССР ( Москва, 1984 г.), на кафедре вычислительной математики Львовского госуниверситета, на семинарах при научном совете по проблеме "Кибернетика" АН УССР ( Киев, 1978 - 1982 г. ).

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

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

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

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

Третья глава посвящена описанию разработанной диалоговой системы отладки программ методом поиска конкретных ошибок, ориентированной на язык ФОРТРАН-1У ОС ЕС. Определены назначение и общие характеристики системы, описаны структура и функции составных частей, база данных системы, функционирование системы. Описан язык отладки ПОИСК-ДИАЛОГ, управляющий работой системы.

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

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

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

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

2) Разработан метод поиска конкретных ошибок, проведено сравнение и обоснованы его преимущества по сравнению с традиционными методами отладки программ. Обоснование метода выполнено на модели программы путем оценки объемов данных, подлежащих анализу при разных методах отладки и скорости сходимости этих методов.

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

4) Разработаны и реализованы структура, функции составных частей и база данных системы отладки. Разработан и реализован язык отладки ПОИСК-ДИАЛОГ, предназначенный для управления работой системы отладки в целом, а также для организации диалога между пользователем и системой. Конструкции языка приближены к естественному разговорному языку.

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

6) Исследованы основные области применения системы отладки КАПКАН-ФОРТРАН: поиск семантических ошибок; проверка .утверждений о программе; сбор, сортировка и изучение ошибок программирования; метрологические исследования программ; формирование ди сциплины программирования.

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

ЗАКЛЮЧЕНИЕ

1.' Айзенберг Я.Е., Вельбицкий И.В., Конорев Б.М., Стогний А. А. Автоматизированная система производства программ СИНТЕРМ. -Управляющие системы и машины, 1980, № I, с. 16-21.

2. Антипенко В.И., Черняховский В.В. Интерактивная система отладки программ. В кн.: Технология программирования. Киев: ИК АН УССР, 1980, с. 40-47.

3. Арефьева Н.А., Пушкина И.П., Родионов С.Т. HIPO-технология метод разработки и сквозного документирования программ по принципу "сверху-вниз". - Управляющие системы и машины, 1978, Р 3, с. 35-39.

4. Архангельский Б.В. Некоторые оптимизационные процедуры над операторными схемами. Программирование, 1980, Р 3, с.13-27.

5. Архангельский Б.В., Никитин А.И. Системы оптимизации программ. Киев: Технгка, 1983. - 167 с.

6. Архангельский Б.В., Черняховский В.В. Методика отладки программного обеспечения РВ-систем;. В кн.: Программное обеспечение вычисл. сетей и систем реального времени: Тез. докл. Всесоюз. конф. Киев: ИК АН УССР, 1981, с. 36-38.

7. Архангельский Б.В., Черняховский В.В. Диалоговая отладка программ на ФОРТРАНе и ее реализация в Р-технологии. В кн.: Р-технология программирования: Тез. докл. I Всесоюз. конф. 4.II. Опыт применения. Киев: ИК АН УССР, 1983, с. 11-13.

8. Архангельский Б.В., Черняховский В.В. Каталог локальных ошибок программирования. Киев, 1984. - 38 с. - Рукопись деп. в ВИНИТИ, № 6094-84 ДЕП.14.v Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.2. М.: Мир, 1978, - 487 с.

9. Бабаян Б.А., Сахин Ю.Х. Система "Эльбрус". Программирование, 1980, № 6, с. 72-86.16; Бабенко Л.П., Довгополая Л.И., Трохименко B.C. и др.

10. Об отладочных средствах в системе программирования. -В кн.: Теория языков и методы построения систем программирования: Труды симп., ИК АН УССР: Киев-Алушта, 1972, с. 309-314.

11. Безбородов Ю.М. Индивидуальная отладка программ. -М.: Наука, 1982. 192 с.

12. Боэм Б., Браун Дж., Каспар X. и др. Характеристики качества программного обеспечения. М.: Мир, 1981. 208 с.

13. Брановицкий В.И., Довгялло A.M., Никитин А.И., Стогний А.А. Диалог человека с ЭВМ: основные понятия и определения.

14. Управляющие системы и машины, 1978, JE 4, с. 3-7.

15. Брановицкий Б.И., Никитин А.И. Диалог человека с ЭВМ. Ориентация диалоговой системы на уровень подготовки пользователя.- Управляющие системы и машины, 1982, Л 3, с. 57-59.

16. Вельбицкий И.В., Ходаковский В.Н., Шолмов Л.И. Технологический комплекс производства программ на машинах ЕС ЭВМ и БЭСМ-6. М.: Статистика, 1980. - 263 с.

17. Гаганов П.Г., Липаев В.В. Характеристики ошибок в процессе разработки комплексов программ. Программирование, 1976, № 2, с. 36-41.

18. Глушков В.М., Капитонова Ю.В., Летичевский А.А. О применении метода формализованных технических заданий к проектированию программ обработки структур данных. Программирование, 1978, I 6, с. 31 - 43.

19. Говорун Н.Н., Залаторюс Ю.П., Никитина В.И. и др. Язык входных сообщений и язык запроса информационной системы "Кадры". Дубна: ОИЯИ, 1977. - 12 с.

20. Говорун Н.Н., Мальцева С.М., Никитина В.И., Тентюкова Г.Н.

21. Формирование, обновление и редактирование базы данных ИСК.-Дубна: ОИЯИ, 1979. 12 с.

22. Головкин Б.А. Надежное программное обеспечение. Обзор. -Зарубежная радиоэлектроника, 1978, Ji 12, с. 3-61.

23. Гросс М., Лантен А. Теория формальных грамматик. М.: Мир, 1971. - 294 с.

24. Жоголев Е.А. Синтаксически управляемое конструирование программ. Программирование, 1979, 16, с. 20 - 25.

25. Жоголев Е.А. Технологические основы модульного программирования. Программирование, 1980, № 2, с. 44 - 49.48.! Задыхайло И.Б., Котов Б.И., Красовский А.Г. и др. О повышении эффективности символьных преобразований, М., 1975.

26. Препринт / ИПМ АН СССР: № 15 ).49.;.3аикин Н.С., Семашко Г.Л., Шириков В.П. Пакетная обработка в системе математического обеспечения "Дубна" ЭВМ БЭСМ-6. Дубна: ОШИ, 1973. - 8 с.

27. Жалнинып А.А., Борзов Ю.В. Инвентаризация идей тестирования программ. Методическая разработка по математическому обеспечению ЭВМ. Рига: ЛатГУ им. П. Стучки, 1981. - 55 с.

28. Касьянов В.Н. Анализ управляющих графов программ. В кн.: Системное программирование. Ч. 2. Новосибирск: ВЦ СО АН СССР, 1973, с. 35 - 48.

29. Касьянов В.Н. Практический подход к оптимизации программ. Новосибирск, 1978. - (Препринт / ВЦ СО АН СССР: В 135).

30. Касьянов В.Н. Анализ структур программ. Кибернетика, 1980, Jf I, с. 48-61.

31. Липаев В.В., Серебровский Л.А., Филиппович В.В. Система автоматизации программирования и отладки комплексов программ управления ЯУЗА-6. Программирование, 1977, № 3, с. 87 - 94.

32. Майерс Г. Надежность программного обеспечения. М.: Мир, 1980. - 360 с.65.' Майерс Г. Искусство тестирования программ. -М.: Финансы и статистика, 1982. 176 с.

33. Мартин Д. Программирование для вычислительных систем реального времени. М.: Наука, 1975. - 360 с.

34. Мелконян О.Е. Система отладки программ СЖОНТ. Программирование, 1977, & 3, с. 83 - 87.

35. Никитин А.И. Общее программное обеспечение систем реального времени, Киев: Наукова думка, 1980. - 132 с.

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

37. Пархоменко П.П., Правильщиков П.А. Диагностирование программного обеспечения (обзор). Автоматика и телемеханика, 1980, № I, с. 103 - 121.

38. Правильщиков П.А. Построение тестов для программ. -Автоматиvка и телемеханика, 1977, $ 5, с. 147 160.72; Рауд P.К., Тамм Б.Г. Состояние в области программирования для микро- ЭВМ. Программирование, 1982, & 5, с. 31-43.

39. Редько В.II. Основания композиционного программирования. Программирование, 1979, № 3, с. 3-13.

40. Семик В.П., Сергиенко И.В. О некоторых принципах построения системы отладки программ. Кибернетика, 1966, $ 3, с.78-82.

41. Средства отладки больших систем / Под ред. Р.Растина. М.: Статистика, 1977. - 135 с.

42. Тамм Б.Г., Тыугу Э.Х. О создании проблемно-ориентированного программного обеспечения. Кибернетика, 1975, Jf 4, с. 76 - 85.

43. Тейер Т., Липов М., Нельсон Э. Надежность программного обеспечения. М.: Мир, 1981. - 323 с.

44. Тыугу Э.Х., Харф М.Я. Алгоритмы структурного синтеза программ. Программирование, 1980, #4, с. 3-13.84..' Хьюз Дж., Мичтом Дж. Структурный подход к программированию.-М.: Мир, 1980, 280 с.

45. Черняховский В.В. Некоторая классификация ошибок программирования и их характеристики. Киев, 1981. - ( Препринт "Математическое обеспечение ВЦКП. Надежность и качество программного обеспечения. I." / ИК АН УССР: 81 - 23, с. 22 - 32 ).

46. Черняховский В.В. Целенаправленный поиск ошибок программирования. В кн.: Прикладное программирование: Сборник научныхтрудов. Киев: Ж АН УССР, 1982, с. 37 42.

47. Шварц Дж. Т. Обзор ошибок.- В кн.: Средства отладки больших систем / Под ред. Р.Растина.-М.: Статистика, 1977.- 135 с.88.'Шинкевич Г.С., Шкут Н.В. О системах отладки АШШ-программ. --Шнек, 1977. 26 с. ( Препринт / Ин-т математики АН БССР:1. J£ 13).

48. Шураков В.В., Алферова З.В., Лихачева Г.Н. Программное обеспечение ЭВМ. М.: Статистика, 1979. - 376 с.

49. Ющенко В.Л., Перевозчикова О.Л. Развитие языков программирования и диалоговых систем в СССР. Кибернетика, 1976, № 6, с. 16 - 33.

50. Baumann R. Software mit System: Software-Fehler. Elektro-niker, 1978, 17, N10, EL1-EL4.

51. Boehm B.W. Software Design and Structuring. Practical Strategies for Developing Large Software Systems. Addison-Wesley, 1975, p. 103-128.

52. Boyer R.S., Elspas В., Levitt K.N. SELECT a Formal System for Testing and Debugging Programs by Symbolic Execution. -Proceedings 1975 International Conference on Reliable Software, p. 234. - Los Angeles, Calif., 1975.

53. Brown A.R,, Sampson W.A. Program Debugging. Macdonald and Co., London, 1973. - 166 pp.

54. Clarke L.A. A system to Generate Test Data and Symbolically Execute Programs. IEEE Transactions on Software Engineering, 1976, SE-2, N0.3, P. 215.

55. Endres A. Fehleranalyse and Fehlerursachen in Systemprog-rammen. Lect. Notes Comput. Sci., 1975, 23, p. 114-160.

56. Mills H.D. Top Down Programming in Large Systems. Debugging Techniques in Large Systems. Prentice-Hall, Inc., 1971, p. 41-45.

57. Nelson Eldred C. Software reliability. FTC-5 Int. Symp. Fault-Toler. Comput., Paris, 1975. - New York, N.Y., 1975, p. 24-28.99» Nov&k Du&an. COBOL-chyby v ufeivatelskych programech. Me-chanizace, automatizace, administrace. 1976,16,NO.2,p.53-55.

58. Osterweil L.J., Fosdick L.D. DAVE A validation error detection and documentation system for Fortran programs. -Software - Practice and Experience, 1976, vol.6, p.473-486.

59. Program Test Methods /Edited by W.C.Hetzel. Prentice-Hall, Inc., Englewood Cliffs., New Jersey, 1973.

60. Ramamoorthy C.V., Ho S.B.F. Testing Large Software with Automated Software Evaluation Systems. IEEE Transactions on Software Engineering, 1975, vol.SE-1, N0.1, p. 46-58.

61. Rouse W.B. Design of man-computer interfaces for online interactive systems. Proc. IEEE, 1975, vol.63, N0.6, p.847-857.

62. Shooman M.L., Bolsky M.J. Types, distribution and test and correction times for programming errors. Proc. Int. Conf. Reliable Software, Los Angeles, Calif., 1975. - S.1., s.a.,1. P. 347-357.

63. Stay J.E. HIP0 and integrated program design. IBM System Journal, 1976, N0.2, p. 143-154.

64. Testing tricks and techniques are really only common sense. EDN/EEE, 1977, 22, NO.11, p. 161-167.

65. Wirth N. Program development Ъу stepwise refinement. -Comm. ACM, 1971, v.14, N0.4, p. 221-227.