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

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

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

1.1. Определение и цели тестирования.

1.2. Программа и ее структурная модель-управляющий граф.

1.3. Покрытие и критерии тестирования.

1.3.1. Критерии структурного тестирования.

1.3.1.1. Критерии потока управления.

1.3.1.2. Критерии потока данных.

1.3.1.3. Мутационные критерии.

1.3.1.4. Отношение включения.

1.4. Взаимосвязь степени структурного покрытия и надежности программы

1.5. Задача генерации входных тестовых данных.

1.6. Структурные методы.

1.6.2. Статические методы.

1.6.2.1. Метод символьного выполнения.

1.6.2.2. Метод тестирования на основе ограничений.

1.6.2.3. Метод динамического сокращения областей значений.

1.6.3. Динамические методы.

1.6.3.1. Метод случайного тестирования.

1.6.3.2. Методы поиска тестовых данных на основе локального и глобального поиска.

1.6.3.2.1. Метод Миллера-Спунера.

1.6.3.2.2. Метод Б. Корела (метод вариации переменной).

1.6.3.2.3. Цель-ориентированный подход на основе локального поиска.

1.6.3.2.4. Цепочечный подход.

1.6.3.2.5. Моделирование отжига.

1.6.3.2.6. Генетические алгоритмы.

1.6.3.3. Метод последовательной релаксации.

1.7. Постановка задачи

1.8. Выводы.

ГЛАВА 2. УСОВЕРШЕНСТВОВАНИЕ МЕТОДОВ ГЕНЕРАЦИИ ВХОДНЫХ

ДАННЫХ.

2.1. Характеристики методов генерации тестовых данных.

2.1.4. Количественные характеристики.

2.1.5. Качественные характеристики.

2.2. Улучшение качественных характеристик.

2.2.6. Обработка строк в методах генерации, разработанных для работы с числовыми данными.

2.2.6.1. Определение длины строки.

2.2.6.2. Сравнение двух строк.

2.2.6.3. Конкатенация двух строк.

2.2.6.4. Извлечение подстроки.

2.2.6.5. Свойства операций над строками.

2.2.6.6. Общий алгоритм адаптации метода для работы со строковыми данными 2.2.6.7. Адаптация метода последовательной релаксации для работы со строковыми данными.

2.2.7. Генерация входных тестовых данных процедурных типов.

2.3. Улучшение количественных характеристик.

1.1. Адаптация метода релаксации для обработки дуговых функций кусочно-линейного вида.

2.4. Выводы.

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

3.1. Обзор вспомогательных алгоритмов для генерации тестовых данных.

3.2. Построение управляющего графа из исходного текста программы.

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

3.4. Алгоритм инструментацни программы.

3.5. Алгоритм построения «линейного» варианта программы.

3.6. Выводы.

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

4.1. Обзор существующих систем генерации тестовых данных.

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

4.3. Модуль синтаксического анализа.

4.4. Модуль построения управляющего графа.

4.5. Модули визуализации.

4.6. Модуль построения набора требуемых путей.

4.7. Модули инструментации и построения линейных вариантов программы

4.8. Модули компиляции, выполнения тестируемых программ и вспомогательные модули.1ДЗ

4.9. Модуль алгоритмов нахождения тестовых данных.

4.10. Модуль верификации.

4.11. Результаты применения программной системы.

4.12. Выводы.

В настоящее время вопросы качества программного обеспечения приобретают особую важность. Неотъемлемой частью процесса обеспечения качества является тестирование. По существующим оценкам [69], затраты на тестирование программ составляют до 50% всего бюджета программного продукта. Таким образом, тестирование — очень трудоемкий и дорогостоящий процесс.

Актуальность проблемы

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

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

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

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

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

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

Цель работы

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

Методы исследования . .

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

Научная новизна

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

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

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

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

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

Практическая ценность

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

Внедрение результатов

Результаты работы внедрены в СПбГУИТМО в учебном процессе, а также в проекте "Интернет-школа программирования". .

Апробация работы

Основные положения диссертационной работы и результаты исследований, включенные в диссертацию, докладывались на различных конференциях СПбГУИТМО, всероссийской научно-методической конференции «Телематика 2005», а также на четырех различных всероссийских конференциях. Доклад на конференции «Микроэлектроника и информатика-2005» (МИЭТ, Зеленоград) был отмечен дипломом за третье место в конкурсе работ аспирантов.

1. Яковлев Ю.А. Критерии полноты тестирования программ// Вестник конференции молодых ученых СПбГУИТМО. Сборник научных трудов. -СПб: СПбГИТМО (ТУ), 2004. - том 1. - с. 150-154

2. Яковлев Ю.А. Среда исследования методов генерации входных данных для структурного тестирования программного обеспечения // Вестник II межвузовской конференции молодых ученых. Сборник научных трудов /Под ред. B.JI. Ткалич. - СПб: СПбГУИТМО(ТУ), 2005. - том 1. - с. 60-64

3. Яковлев Ю.А. Реализация генетического алгоритма для поиска входных данных при структурном тестировании программ. //Материалы международной научно-технической конференции "Наука и образование-2005"- Мурманск, 2005. - с. 12-15

4. Яковлев Ю.А. Генерация входных тестовых данных символьного типа. //Микроэлектроника и информатика-2005. 12-я всероссийская межвузовская научно-техническая конференция студентов и аспирантов. Тезисы докладов. -Москва, 2005.-c.299

5. Яковлев Ю.А., Павловская Т.А. Графическая интерпретация динамических методов генерации входных данных для тестирования программ. //Информационные технологии в науке, проектировании и производстве. Материалы 14-й всероссийской научно-технической конференции.-Нижний Новгород, 2005. — с. 25-28

6. Яковлев Ю.А., Павловская Т.А. Адаптация метода генерации входных данных для тестирования программ с параметрами процедурного типа //Информационные технологии в профессиональной деятельности и научной работе. Сборник материалов региональной научно-практической конференции. - Йошкар-Ола, 2005. - с. 144-146.

7. Яковлев Ю.А., Павловская Т.А. Адаптация алгоритмов генерации входных данных для структурного тестирования объектно-ориентированных программ //Техника и технология, № 2, 2005. - с. 86-88

8. Яковлев Ю.А., Павловская Т.А. Динамические методы генерации входных данных для тестирования учебных программ // Сборник XII Всероссийской научно-методической конференции Телематика 2005 / Под ред. Сергеева А.О. — СПб: СПбГУ ИТМО (ТУ), 2005 г. -т.2. - с. 514-515

Структура и объем работы

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

4.12. Выводы

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

2. Рассмотрен и описан функциональный состав программной системы. Система реализована на объектно-ориентированном языке высокого уровня С# на платформе Microsoft .NET Framework vl.l и содержит более 8200 строк кода (88 классов). Использованы библиотеки синтаксического анализа (antlr), визуализации графов (aiSee) и линейного программирования (lpsolve).

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

ЗАКЛЮЧЕНИЕ

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

Введены характеристики методов и предложены способы улучшения этих характеристик, а именно:

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

Предложено усовершенствование метода релаксации

Разработаны вспомогательные алгоритмы, необходимые для генерации тестовых данных.

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

1. ANTLR - ANother Tool for Language Recognition//^eKTpoHHbm ресурс. http://www.antlr.org

2. Baresel A., Sthamer H. Evolutionary testing of flag conditions//In Proceedings of the Genetic and Evolutionary Computation Conference(GECCO 2003), Lecture Notes in Computer Science vol. 2724, pages 2442-2454, Chicago, USA, 2003. Springer-Verlag.

3. Baresel A., Sthamer H., Schmidt M. Fitness function design to improve evolutionary structural. testing//In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), pages 1329-1336, New York, USA, 2002. Morgan Kaufmann.

4. Beydeda S., Gruhn V. Test Case Generation according to the Binary Search Strategy// In International Symposium on Computer and Information Sciences (ISCIS), LNCS. Springer Verlag, 2003

5. Beydeda S., Gruhn V. Test Data Generation based on Binary Search for Class-level Testing// In ACS/IEEE International Conference on Computer Systems and Applications (AICCSA). IEEE Computer Society Press, 2003

6. Bicevskis J., Borzovs J., Straujums U., Zarins A., Miller E.F. SMOTL A system to construct samples for data processing program debugging//IEEE Transactions on software engineering, 1979, №1, pp. 60-66.

7. Bottaci L. Instrumenting programs with flag variables for test data search by genetic algorithm//In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), pages 1337 1342, New York, USA, 2002. Morgan Kaufmann.

8. Boyer R.S., Elspas В., Levitt K.N. SELECT — A formal system for testing and debugging programs by symbolic execution.//Proceedings of the International Conference on Reliable Software, ACM Press, 1975. pp 234-244.

9. Bueno P.M.S., Jino M. Automatic test data generation for program paths using genetic algorithms//International Journal of Software Engineering and Knowledge Engineering. Vol. 12, No. 6 (2002) pp. 691-709

10. Chilensky J.J., Miller S.P. Applicability of modified condition/decision coverage to software testing//Soflware Engineering Journal, 9(5), pp. 191-200

11. Clarke L. A system to generate test data and symbolically execute programs//IEEE Transactions on Software Engineering, 1976, N2, pp 215-222.

12. Clarke L., Podgurski A., Richardson D.J., Zeil S.J. A comparison of data flow path selection criteria//Proc. 8th International Conference on Software Engineering, pp 244251, 1985.

13. Clarke L., Podgurski A., Richardson D.J., Zeil S.J. A formal evaluation of data flow path selection criteria//IEEE Transactions on Software Engineering, pp. 1318-Д 332,->' November 1989.

14. CMMI VI. 1//Электронный ресурс. http://www.sei.cmu.edu/cmmi/

15. DeMillo R.A. Test adequacy and program mutation/ZProceedings of the 11th International conference on Software Engineering, pp. 355-356, 1989

16. Demillo R.A., Offutt A.J. Experimental Results From an Automatic Test Case Generator//Transactions on Software Engineering Methodology, 2(2): 109-175, 1993.

17. Duran J.W., Ntafos S.C. An evaluation of random testing//IEEE Transactions on Software Engineering, pp. 438-444, July 1984.

18. Edvardsson J., Kamkar M. Analysis of the Constraint Solver in UNA Based Test Data Generation 1999

19. Ferguson R., Korel B. Generating test data for distributed software using the chaining approach. Information and Software Technology, 38(l):343-353, January 1996.

20. Ferguson R., Korel B.The chaining approach for software test data generation//ACM Transactions on Software Engineering and Methodology,5(1 ):63-86, 1996.

21. Frankl P.G., Weyuker E.J. An applicable family of data flow testing criteria/ЛЕЕЕ Transactions on Software Engineering, pp. 1483-1498, October 1988.

22. Gallagher M. J., Narasimhan V. L. ADTEST: A test data generation suite for ada software systems.//IEEE Transactions on Software Engineering,23(8):473 —484, 1997.

23. Garey M.R., Johnson D.S. Computers and intractability: A guide to the theory of NP-completeness. W.H.Freeman, New York, 1979.

24. Goodenough J.B., Gerhart S.L. Toward a theory of test data selection// IEEE Transactions on Software Engineering, 1975, SE-2, № 3.

25. Gotlieb A., Botella В., Rueher M.Automatic Test Data Generation Using Constraint Solving Techniques.// Software Engineering Notes, 23(2):53-62, Mar. 1998.

26. Gupta N., Mathur A.P., Sofia M.L. Automated Test Data Generation Using An Iterative Relaxation Method//ACM SIGSOFT Sixth International Symposium on -Foundations of Software Engineering (FSE-6), pages 231 -244, Orlando, Florida, ^ . November 1998.

27. Gupta N., Mathur A.P., SofTa M.L. UNA Based Iterative Test Data Generation and Its Evaluation.//Automated Software Engineering, 1999. 14th IEEE International Conference on., pages 224-232,1999.

28. Harman M., Hu L., Zhang X., Munro M. Side-effect removal transformation/An Proceedings of the 9th IEEE International Workshop on Program Comprehension (IWPC 2001), pages 310(319, Toronto, Canada, 2001. IEEE Computer Society Press.

29. Harman M., Hu L., Zhang X., Munro M., Dolado J.,. Otero M. C, Wegener J. A. post-placement side-effect removal algorithm//In Proceedings of the 18th IEEE International Conference on Software Maintenance (ICSM 2002), pages 2-11, Montreal, Canada, 2002.

30. Hedley D., Hennell M.A. The causes and effects of infeasible paths in computer programs. //Proceedings of 8th International Conference on Software Engineering, IEEE, London, 1985.

31. Howden V.E. Introduction to the theory of testing. Tutorial: Software testing and validation techniques. 1978

32. Huang J.-C. Program Instrumentation and Software Testing// COMPUTER, 1978. 11(4).

33. International Organization For Standartization, ISO 9000:2000. //Электронный ресурс. www.iso.org

34. Jones В., Sthamer H., Eyres D. Automatic structural testing using genetic algorithms//Software Engineering Journal, 11(5):299-306, 1996.

35. King J. Symbolic execution and program testing//Communications of the ACM. 1976 N7, pp 385-394.

36. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing//Science, pp. 671-680, May 1983.

37. Korel B. Automated software test data generation./ЛЕЕЕ Transactions on Software Engineering, 16(8):870-879, 1990.

38. Korel B. Automated test generation for programs with procedures//International Symposium on Software Testing and Analysis (ISSTA 1996), pages 209-215, San Diego, California, USA, 1996.

39. Korel B. Dynamic method for software test data generation.//Software Testing, Verification and Reliability, 2(4):203-213, 1992.

40. Laski J., Korel B. A data flow oriented program testing strategy/ЛЕЕЕ Transactions on Software Engineering, pp. 347-354, May 1983.

41. Malaiya Y.K., Li M. N., Bieman J.M., Karcich, R. Software Reliability Growth With Test Coverage/ЛЕЕЕ Transactions On Reliability, Vol. 51, No. 4, December 2002.г

42. McCabe Т., Watson A. Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric//National Institute of Standards and Technology (NIST), 1996

43. McGraw G., Michael C., Schatz M. Generating software test data by evolution/ЛЕЕЕ Transactions on Software Engineering, 27(12):1085{ 1110,2001.

44. McMinn Ph. Search-based Software Test Data Generation: A Survey//Software Testing, Verification and Reliability,

45. Miller W., Spooner D. Automatic generation of floating-point test data//IEEE Transactions on Software Engineering, 2(3):223-226, 1976.

46. Niemann, T. A Compact Guide to Lex and Уасс//Электронный ресурс. http://www.epaperpress.com

47. Osman I.H. Metaheuristics: A bibliography//Annals of operations research, pp. 513623, 1996

48. Ould M. Testing a challenge to method and tool developers//Software Engineering Journal, vol. 6, pp. 59-64, Mar. 1991.

49. Pan A., Offutt A.J., Jin Zh. The dynamic domain reduction procedure for test data generation//Software—Practice & Experience archive. Volume 29, Issue 2. (February 1999). pp. 167- 193.

50. Pargas R., Harrold M., Peck R. Test-data generation using genetic algorithms. Software Testing, Verification and Reliability, 9(4):263-282,1999.

51. Poole J. A Method to Determine a Basis Set of Paths to Perform Program Testing//National Institute of Standards and Technology (NIST), 1995

52. Ramamoorthy С. V., Ho S. F., Chen W. T. On the automated generation of program test data./ЛЕЕЕ Transactions on Software Engineering, 2(4):293{300, 1976.

53. Roper M. Computer aided software testing using genetic algorithms.//10th International Software Quality Week, San Francisco, USA, 1997.n

54. Sy N.T., Deville Y. Automatic test data generation for programs with integer and float variables/Tin 16th IEEE International Conference on Automated Software Engineering, November 2001.

55. Tracey N., Clark J., Mander K., McDermid J. An automated framework for test data generation/Tin Proceedings of the International Conference on Automated Software Engineering, IEEE, October 1998.

56. Tracey N., Clark J., Mander K. Automated Program Flaw Finding using Simulated Annealing// Software Engineering Notes, Issue 23, No. 2, Proceedings of the International Symposium on Software Testing and Analysis (ISSTA 1998).

57. Watkins A. The automatic generation of test data using genetic algorithms//In Proceedings of the Fourth Software Quality Conference, pages 300-309, 1995.

58. Wegener J., Baresel A., Sthamer H. Evolutionary test environment for automatic structural testing//Information and Software Technology, 43(14):841-854, 2001. '.

59. Weyuker E.J. The complexity of data flow criteria for test data • selection/flnformation processing letters, 19, pp.103-109, August 1984

60. Xanthakis S., Ellis C., Skourlas C., Le Gall A., Katsikas S., Karapoulios K.Application of genetic algorithms to software testing . //5th International Conference on Software Engineering and its Applications, pages 625-636,Toulouse, France, 1992.

61. Zhao R., Lyu M.R. Character String Predicate Based Automatic Software Test Data Generation//Third International Conference On Quality Software, 2003. p. 255.

62. Бейзер Б. Тестирование черного ящика. -СПб.:Питер, 2004. -320 с.

63. Калниньш А.А., Борзов Ю.В. Инвентаризация идей тестирования программ. -Рига:Латвийский государственный университет им. П.Стучки, 1981.

64. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.:БХВ-Петербург, 2003.

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

66. Корнеев Г.А., Станкевич А.С. Методы тестирования решения задач на соревнованиях по программированию// Вестник II межвузовской конференции молодых ученых. Сборник научных трудов /Под ред. B.JI. Ткалич. — СПб: СПбГУИТМО(ТУ), 2005. том 1.-е. 36-40.

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

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

69. Орлов С. Технологии разработки программного обеспечения. Учебное пособие. -СПб.:Питер, 2003. -528 с.

70. Хантер, Р. Основные концепции компиляторов.-М.: Издательский дом «Вильяме», 2002

71. Черноножкин С.К. Задача автоматического построения тестов и статический анализ//Программирование, 2001, № 2 -с.47-59