Математические модели надежности программного обеспечения функционального типа тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат технических наук Гордиенко, Александр Владимирович

• Гордиенко, Александр Владимирович
• кандидат технических наук
• 2000

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

ВВЕДЕНИЕ.

1. ДЕТЕРМИНИРОВАННЫЙ И ВЕРОЯТНОСТНЫЙ ПОДХОДЫ К ТЕСТИРОВАНИЮ ПРОГРАММ.

1.1. Теоретическая сложность проблемы детерминированного тестирования программ.

1.2. Вероятностный подход к тестированию программ.

Модели надежности программного обеспечения.

1.3. Основные определения и формальная постановка решаемой задачи.

1.4. В ы в о д ы.

2. ВЕРОЯТНОСТНОЕ ТЕСТИРОВАНИЕ ОТДЕЛЬНЫХ ПРОГРАММ.

2.1. Теоретическое исследование метода функционального тестирования программ:.

2.2. Разработка модифицированного метода структурного тестирования программ.

2.3. Экспериментальное исследование структурно-ориентированного критерия тестирования программ.

2.4. Генерация исходной информации для тестирования программ.

2.5. В ы в о д ы.

3. РАСЧЕТ БЕЗОТКАЗНОСТИ СИСТЕМЫ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ФУНКЦИОНАЛЬНОГО ТИПА (ПФТ).

3.1. Верхняя оценка вероятности отказа ПФТ.

3.2. Оценка вероятности отказа ПФТ с учетом ограничения на функциональную неоднородность составляющих программ.

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

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

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

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

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

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

Есть основания полагать, что причины такого положения в значительной мере заключаются в имевшей место среди теоретиков ШО тенденции рассматривать чрезмерно широкое поле исследований, ставить перед собой чрезмерно глобальные задачи. Однако задача типа "дана произвольная программа, в которой могут быть любые ошибки, требуется ее надежно проверить и гарантировать, что после проверки она будет всегда правильно работать" на современном уровне развития науки не может быть решена (точнее, математически строго доказано, что в такой постановке задача является алгоритмически неразрешимой).

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

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

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

2) ПФТ функционирует либо на однопроцессорной ЭВМ в последовательном режиме работы, либо на слабо связанной вычислительной системе;

3) ПФТ не содержит каких-либо автоматических средств данамической коррекции невыявленных ошибок в программах.

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

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

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

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

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

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

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Гордиенко, Александр Владимирович

Выводы

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

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

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

В результате проведенного тестирования было выявлено дополнительно свыше 20 дефектов в программах. Указанная АСУТП была внедрена на предприятии п/я А-3611. За время промышленной эксплуатации не было обнаружено ни одного дефекта в ее системе программного обеспечения, что может свидетельствовать о эффективности модифицированного метода структурного тестирования программ для получения качественного программного обеспечения.

ЗАКЛЮЧЕНИЕ

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

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

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

4. Результаты исследований использованы при проверке программного обеспечения автоматизированной системы управлет ния участком намоточных станков. Результаты исследований моплггп Ачппг. тахгм/о т^пгтп ггх.'зтэотзгт ттпт* тгпптга'птг'о тглл'П'патгалрп лЛаг> печения других систем.

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

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

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов / Пер. с англ. М.: Мир, 1979.

2. Бешелев С.Д. Математико-статистические методы экспертных оценок / 2-е изд., перераб. и дополн. М.: Статистика, 1980

3. Бичевский Я.Я., Борзов Ю.В. Тестирование программ ЭВМ / Рига: Латв.гос.ун-т, 1985.

4. Блау С.А., Липаев В.В., Позин Б.А. Эффективность тестирования структуры программных модулей // Автоматика и телемеханика, 1984, 4, с. 139-148.

5. Бондарь Я.С., Катков В.Л. Система автоматической генерации тестов // Программирование, 1995, $ 6, с.27-35.

6. Боэм Б.У. Инженерное проектирование программного обеспечения / Пер. англ. М.: Радио и связь, 1985.

7. Братчиков И.Л. Синтаксис языков программирования. -М.: Наука, 1975.

8. Вентцель Е.С. Теория вероятностей. М.: Наука, 1969.

9. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные приложения. М.: Наука, 1988

10. Воеводин В.В., Ким Г.Д. Машинные операции с точки зрения математика // Сб. работ Вычисл. Центра МГУ. Вып.26. -М.: Мзд.МГУ, 1977, с.31-35.

11. Глушков В.М., Вельбицкий И.М. Технология программирования и методы ее автоматизации // Управляющие системы и машины, 1976, .№ 6.

12. Гордиенко A.B. Вероятностный подход к определению надежности программ // Технология создания программных средств АСУ. -Калинин, 1980, с.154-157.

13. Гордиенко A.B. Генерирование исходной информации для тестирования программного обеспечения АСУ ТП // Системы управления технологическими процессами. Новочеркасск, 1981, с.58-64.

14. Гордиенко A.B. Расчет надежности программного обеспечения АСУ // Системы и технические средства подготовки операторов. -Новочеркасск, 1981, с.73-78.

15. Гордиенко A.B. О сложности проблемы автоматизации генерирования исходных данных для тестирования программ // Кибернетика, 1982, Sb I, с. 123-124.

16. Гордиенко A.B. К вопросу об эффективности критерия тестирования программ по путям // Управляющие системы и машины, 1982, № 2, с.107-109.

17. Гордиенко A.B. Тестирование при оценке динамической корректности программ АСУ // Программирование, 1982, № 6, с.48-52.

18. Гордиенко A.B. Распределение вероятностей отказов при работе программного обеспечения ЭВМ // Изв. СКНЦ ВШ. Серия технических наук, 1983, J6 I, с.54-56.

19. Гордиенко A.B. Определение оптимального числа испытаний составляющих программ при тестировании системы программного обеспечения // Проблемы развития и использования ЭВМ общего назначения. Минск, 1984, с.85-86.

20. Гордиенко A.B. О выборе входного распределения при функциональном тестировании программ // Изв. вузов. Электромеханика, 1985, № 4, C.II4-II6.

21. Гордиенко A.B. Имитационная модель надежности системы программного обеспечения // Программные средства как продукция проиеводотввыно-технического назначения. Калинин, 1985, с.44-45.

22. Гордиенко A.B. Ошибки в межпрограммном интерфейсе: данные статистических исследований // Деп. ВИНИТИ 09.01.92 Jfc 89-В92

23. Гордиенко A.B. Оценка вероятности отказа системы программного обеспечения при известных вероятностях отказа составляющих программ // Деп. ВИНИТИ 29.10.92 Jfc 3I35-B92

24. Гордиенко A.B. О влиянии функциональной неоднородности составляющих программ на общую корректность системы программного обеспечения // Техника. Экономика. Культура. Ростов/Д, 1998, с.213-215.

25. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи / Пер. с англ. М.: Мир, 1982

26. Зайцев A.B. Применение мутационного анализа при тестировании программ. Севастопольский приборостроительный ин-т, 1987. - 21с. //Деп. в УкрНИИНТИ » 1442-Ук87 .

27. Зайцев A.B. Надежность тестирования программ // Программирование, 1989, .№ 6, с.20-25.

28. Иванченко А.Н., Гордиенко A.B. Оптимизация функционального тестирования программ по стоимостному критерию // Изв. вузов. Северо-Кавказский регион. Техн. науки, 1997, ^ 3, с.24-27.

29. Иванченко А.Н., Гордиенко A.B. Структурный подход к расчету количественной оценки безотказности работы системы программного обеспечения // Изв. вузов. Электромеханика, 1999, 4, с.101-108.

30. Иванченко А.Н., Гордиенко A.B. Инженерный расчет количественной оценки безотказности работы системы программного обеспечения // Изв. вузов. Северо-Кавказский регион. Техн. науки, 2000, Ш 2, с.24-28.

31. Карповский Е.Я., Сагач В.В., Черыецкий A.A. Надежность алгоритмов управления. Киев: ТехнХка, 1983.

32. Кауфман A.B., Черноножкин С.К. Критерии тестирования и система оценки полноты набора тестов // Программирование, 1998, Jfe 6, с.44-59

33. Ковалев М.Я., Шафранский Я.М. Построение s-приближенных алгоритмов решения некоторых NP-полных задач // Теория и методы автоматизированного проектирования сложных системен автоматизация научных исследований. Минск, 1985, с. 15-18.

34. Корчемный Д.М. Ошибки в Си-программах. М., 1989. 33с. Деп. в ИНФОРМЭлектро N ДР4744-пр89.

35. Котляров В.П., Пинаев Д.В. Методы и средства автоматизации тестирования программного проекта / Учеб.пос. СПб: СПбГТУ, 1998

36. Липаев В.В. Надежность программного обеспечения. М.: Энергоатомиздат, 1981.

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

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

39. Лонгботтом Р. Надежность вычислительных систем. / Пер. с англ. М.: Знергоатомиздат, 1985.

40. Майерс Г. Искусство тестирования программ. / Пер. с англ. М.: Финансы и статистика, 1982.

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

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

43. Пальчун Б.П., Юсупов P.M. Оценка надежности программного обеспечения. СПб.: Наука, 1994.

44. Пепеляев А.Н., Липин Ю.Н., Левитин Ф.И. Контроль достоверности информации в АСУП. М.: ЦМНТИХММНЕФТЕМАШ, 1975.

45. Позин Б.А. Методы структурного построения тестов для отладки управляющих программ // Программирование, 1980, Jfc 2, с.62-69.

46. Правильщиков П.А., Щепин B.C. Составление структурных программ в диалоговом режиме с одновременной генерацией те'стов // Автоматика и телемеханика, 1979, Л 8, с.129-138.

47. Проверка и утверждение программ реального времени. / Пер. с англ. Киев: Наукова думка, 1990.

48. Taxa X. Введение в исследование операций. В 2 кн. / Пер. с англ. М.: Мир, 1985.

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

50. Тоценко В.Г., Александров A.B., Парамонов Н.Б. Корректность, устойчивость, точность программного обеспечения. Киев: Наукова думка, 1990

51. Яблонский C.B., Гаврилов Г.П., Кудрявцев В.В. Функции алгебры логики и классы Поста. М.: Наука, 1966.

52. Alanko T.O., Smelianski R.L. On the calculation of control transition probabilities in a program // Information Processing Letters, 1986, v.22, N 5, p.273-276.

53. Bassiohi F., Spadafora I. An automated generator for compiler testing // IEEE Transactions on Software Engineering, 1982, y.8, N 4, p.343-353.

54. Bieman J.M., Schultz J.L. An empirical evaluation (and specification) of the all-du-paths testing criterion // Software Engineering Journal, 1992, v.7, N 1, p.43-51.

55. Bishop P.G., Pullen P.D. PODS revisited: A study of software failure behavior // 18th Fault Tolerance in Computing Conf., 1988, p.2-8.

56. Clarke L.A. A system to generate test data and symbolically execute programs // IEEE Transactions on Software Engineering, 1976, v.2, N 3, p.215-222.

57. Cooper K.D., Hall M., Kennedy K., Torczon L. Inter-procudaral analysis and optimization // Communications on Pure and Applied Mathematics, 1995, Vol.XLVIII, p.947-1003.

58. Demillo R.A., Lipton R.J., Sayward P. Hints on test data selection: Help for the practicing programmer // Computer, 1978, v.11, N 4, p.34-41.

59. Dunham J.R. Experiments in software reliability: Life-critical applications // IEEE Transactions on Software Engineering, 1986, v.12, N 1, p.110-123.

60. Duran J.W., Wiorkowski J.J. Quantifying software validity by sampling // IEEE Transactions on Reliability, 1980, v.29, p.141-144.

61. Duran J.W., Ntafos S.G. An evaluation of random testing // IEEE Transactions on Software Engineering, 1984, v.10, N 4, p.438-444.

62. Goodenough J.B. A survey of program testing issues //

63. Software Reliability. Maidenhead, 1977, vol.2, p. 135-154.

64. Horgan J.R., London S., Lyu M.R. Achieving software quality with testing coverage measures // Computer, 1994, v.27, N 9, p.60-69.

65. Howden W. functional Program Testing and Analysis. -New York: McGraw-Hill, 1987.

66. Jones C. Software metrics: good, bad, and missing // Computer, 1994, v.27, N 9, p.98-100.

67. Knight J.C., Ammann P.E. An experimental evaluation of simple methods for seeding program errors // 8th Intern. Conference on Software Engineering, 1985, p.337-342.

68. Knight J.C., Leveson N.G. An experimental evaluation of the assumption of independance in multiversion software // Transactions on Software Engineering, 1986, N 1, p.96-109.

69. Marshall A.C., Hedley D., Riddell I.J., Hennell M.A. Static dataflow-aided weak mutation analysis // Information and Software Technology, 1990, v.32, N 1, p.99-104.

70. Ostrand T.J., Balcer M.J. The category-partition method for specifying and generating functional tests // Communications of the ACM, 1988, v.31, N 6, p.676-686.

71. Nelson E. Estimating software reliability from test data // Microelectronics and Reliability, 1978, v.17, p.67-74.

72. Ntafos S.C., Hakimi S.L. On path cover problem In digraphs and applications to program testing // IEEE Transactions on Software Engineering, 1979, v.5, N 5, p.520-529.

73. Piwowarski P.M., Ohba M., Caruso J. Coverage measurement experience during function test // 15th Intern. Gonf. on Software Engineering, 1993, p.287-301.m

74. Ramamoorthy C.V., Bastani F.B. Software reliability status and perspectives // IEEE Transactions on Software Engineering, 1982, y.8f p.354-371.

75. Roca J.L. Normal approach on correctness software estimation // Microelectronics and Reliability, 1987, v.27, N 4, p.457-458.

76. Roca J.L. Testing hypotheses on correctness software estimation // Microelectronics and Reliability, 1988, v.28, N 4, p.511-512.

77. Shapiro E.Y. Algorithmic Program Debugging. MIT Press, 1982.

78. Wang H.S., Hsu S.R., Lin J.C. A generalized optimal path-selection model for structural testing // Journal of Systems and Software, 1989, v.10, N 1, p.55-63.

79. Weyuker E.J. The cost of data flow testing: An empirical study // IEEE Transactions on Software Engineering, 1990, v. 16, N 2, p.121-128.

80. Wohlin G., Koerner U. Software faults: spreading, detection, and costs // Software Engineering Journal, 1990, v.5, N 1, p.33-42.