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

ВВЕДЕНИЕ.:.

Глава 1. МАТЕМАТИЧЕСКИЕ . АСПЕКТЫ ТЕСТИРОВАНИЯ ИНФОРМАЦИОННЫХ СИСТЕМ.

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

1.2 Теоретические основы тестирования программ в информационных системах.

1.2.1 Сфера исследования и основные определения.

1.2.2 Мощность тестовых методов.

1.2.3 Теоретические результаты.

1.3 Обзор и интерпретация предшествующих работ.

1.3.1 Анализ теоретических работ.

Выводы по главе 1.

Глава 2. ИССЛЕДОВАНИЕ И АНАЛИЗ ПРАКТИЧЕСКИХ МЕТОДОВ ТЕСТИРОВАНИЯ ПРОГРАММНЫХ КОМПЛЕКСОВ В ИНФОРМАЦИОННЫХ СИСТЕМАХ.

2.1 Тестирование, не зависящее от спецификаций.

2.2 Тестирование, зависящее от спецификаций.

2.3 Тестирование аппаратуры.

2.4 Дальнейшие исследования в области тестирования, зависящего от спецификаций.

Выводы по главе 2.

Глава 3. РАЗРАБОТКА МЕТОДА КОМПОНЕНТНОГО ТЕСТИРОВАНИЯ ПРОГРАММНЫХ КОМПЛЕКСОВ ИНФОРМАЦИОННЫХ СИСТЕМ.

3.1 Критерий компонентного тестирования информационных систем.

3.2 Компонентное тестирование.

3.3 Программные компоненты и их мутации.

3.3.1 Ссылка на переменную.

3.3.2 Присваивание переменной.

3.3.3 Арифметические выражения.

3.3.4 Отношения.

3.3.5 Булевские выражения.

3.4. Программные конструкции и их тестирование.

3.4.1 Оператор присваивания.

3.4.2 Условный оператор.

3.4.3 Оператор цикла.

3.5. Эффективность и полнота.

3.5.1 Эффективность тестовых множеств.

3.5.2 Полнота тестовых множеств.

3.5.3 Использование определений полноты и эффективности для сравнительного анализа тестовых методов.

Выводы по главе 3.

Глава 4. ЛОГИЧЕСКИЕ МЕТОДЫ ДОКАЗАТЕЛЬСТВА И ТЕСТИРОВАНИЯ ПРОГРАММ.ЮЗ

4.1 Аксиоматический метод Хора.

4.2 Завершимость выполнения алгоритмов.

4.2.1 Доказательство завершимости выполнения алгоритмов.

4.2.2. Тестирование завершимости программ.

4.3. Построение множеств путей выполнения программ и их тестирование

4.3.1 Программы как минимальные фиксированные точки.

4.3.2 Аксиоматический метод поиска тестовых данных.

Выводы по главе 4.

Актуальность темы.

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

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

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

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

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

За последние годы предпринимались попытки достигнуть лучшего теоретического понимания тестирования. Однако эти попытки носят ограниченный характер и могут быть подвергнуты существенной критике.

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

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

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

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

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

Большой вклад в решение различных аспектов проблемы тестирования и программной надёжности внесли отечественные ученые Липаев В.В. [ 1 ], [ 2 ], [ 3 ], [ 4 ], Позин Б.А. [ 5 ], Глушков В.М. [ 6 ], Ершов А.П. [ 7 ], Касьянов В.Н. [ 8 ], Борзов Ю.В. [ 9 ], Кульба В.В. [ 10 ], а также зарубежные специалисты Май-ерс [ 11 ], [ 12 ], Ахо А. [ 13 ], Goodenough John В. , Gerhart L.Susan [ 14 ], How-den W.E. [ 15 ], [ 16 ], [ 17 ], [ 18 ], [ 19 ], [ 20 ], [ 21 ], [ 22 ], [ 23 ], Littlewood B. [ 24 ] и другие.

Цель и задачи исследований.

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

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

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

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

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

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

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

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

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

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

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

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

• предложен механизм анализа сложных конструкций языков программирования (операторы присваивания, условные операторы, циклы) на базе введенных функций оценивания для простейших компонент;

• предложен алгоритм анализа сложных конструкций языков программирования (операторы присваивания, условные операторы, циклы) на базе введенных функций оценивания для простейших компонент;

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

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

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

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

Реализация результатов работы.

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

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

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

Предложенные методы тестирования и доказательства корректности программ используются в учебном процессе в курсах «Информатика», «Информационные системы» и «Семантика языков программирования», читаемых на различных факультетах МЭИ и РГГУ.

Выполненные НИР:

• Разработка программного и методического обеспечения решения студенческих задач на массовых потоках с применением ЭВМ. 1984 г.

• Разработка программного и информационного обеспечения задач обработки данных с учетом требований надежности. 1985 г.

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

• Инструментальные средства автоматизирования разработки программ на структурном подмножестве языка Р1/1.

• Разработка первой очереди пакета прикладных программ РАНГ для анализа ТЭУ отрасли.

• Разработка систем параллельной и распределенной обработки информации в локальной микропроцессорной сети.

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

Апробация результатов.

Основные результаты диссертационной работы докладывались и обсуждались:

• на 1-й и 2-й Всесоюзной научной конференции "Цифровое машинное моделирование информационно-вычислительных систем" (Пенза, 1983г. ,1985г.);

• на 8-м симпозиуме "Логическое управление в промышленности" (Куйбышев, 1990г.);

• на Международных научных конференциях " Информационные средства и технологии" (Москва, 1996г., 1998г., 1999г.);

• на семинарах кафедр "Прикладная математика" МЭИ и "Информационно-вычислительных систем" РГГУ.

Публикации

По теме диссертации опубликовано 10 печатных работ, выпущено 14 отчетов по темам НИР.

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

Очевидно, что тестовый метод М является более мощным, чем тестовый метод Л/, если его успешное применение гарантирует также, что применение метода N будет также успешным, то есть М лучше аппроксимирует доказательство правильности программ, чем N.

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

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

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

В разделе 1.3 переформулированы определения надежности и значимости тестовых методов в том виде, как они были предложены Гуденафом и Герхард [14] и показано, что фундаментальная теорема Гуденафа и Гер-хард о корректности программы является следствием теоремы 1.3.1.1-1. Показано также, что введенные Гуденафом и Герхарт понятия надежности и значимости являются зависимыми в некотором смысле, то есть, по крайней мере, одно из них выполняется для любого теста М. Иными словами, если для теста М не выполняется одно из этих свойств, то гарантировано выполняется другое. Показана также некорректность приведенного Гуденафом и Герхарт ответа на вопрос о критерии выборки тестовых данных, обеспечивающих надежность тестового метода.

Вторая глава посвящена исследованию и анализу имеющихся практических методов тестирования на основе единой методологии, предложенной в главе 1. Формально определены и исследованы методы тестирования, не зависящие от спецификации: операторное, ветвевое и путевое тестирование, а также мутационное тестирование. Получен ряд результатов, характеризующих отношения мощностей различных методов тестирования (теорема 2.1.2-1). Показано, что множество всех методов путевого тестирования {Path | /> 1}, где I - длина тестируемых путей, является строго упорядоченным, причем метод PATH-i в точности соответствует методу операционного тестирования, а метод РАТН2 - метод ветвевого тестирования.

Предложенный в работе [35] метод, концептуально отличный от путевого тестирования, получил название мутационного метода. Суть мутационного метода состоит в поиске тестовых данных, позволяющих отличать исходную программу от любых ее модификаций (мутантов), получаемых путем введения ошибки в исходную программу. Показано, что мутационный анализ может быть легко описан в терминах теории, изложенной в главе 1. Показано, что мутационный анализ является более мощным по сравнению с методом РАТНг и не сравним с РАТНп для п >2 (теорема 2.1.3-1).

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

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

В третьей главе описывается предложенный автором метод компонентного тестирования. Анализ мутационного тестирования, проведенный во второй главе, показывает, что все методы, базирующиеся на мутационном принципе, строят тесты, позволяющие обнаруживать определенные виды (классы) ошибок. Это, безусловно, является сильной стороной мутационного тестирования. Целью мутационного тестирования является построение множеств Г, позволяющих отличать программу Р от любой неэквивалентной программы Р', получаемой из Р применением мутационных трансформаций компонент Р . Типичными трансформациями являются: изменение имен переменных в выражениях, изменения меток в операторах до изменение границ параметров, задающих границы циклов и т.д.

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

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

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

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

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

Рассмотрение методов компонентного тестирования мы будем осуществлять как с точки зрения конструкций языка программирования, так и с функциональной точки зрения. С функциональной точки зрения программе р будет сопоставляться функция f, реализуемая этой программой. Обозначим (Л множество функций, имеющих ту же самую входную область, что и f, включая саму функцию £ Очевидно, что множество функций Г е и/> таких, что f * Г, представляет собой множество "похожих" функций. В общем случае, коды программ Р и Р\ вычисляющих соответственно f \лf , могут быть совершенно различны, поскольку даже одна и та же функция может иметь различные алгоритмы ее вычисления, а значит, и различные коды. В этом случае говорить о практическом тестировании программ, например, программ, вычисляющих полиномы, как у Хаудена [18]. По этой причине мы ограничиваем понятие щихся на на инвариантах цикла. В частности, для цикла while В do S условиями завершимости являются:

• Р & 6 -> (Е > 0), где Р - инвариант цикла, Е - целочисленное выражение;

• VE0 ({0 < Е = Е0} S {0 < Е < Е0}, где Е0 - выражение, принимающее целочисленные значения.

Выполнение этих условий совместно с доказательством того, что Р является инвариантом цикла, гарантирует завершение цикла, так как из них вытекает, что:

• утверждение Е > 0 является инвариантом цикла, то есть выражение Е остается неотрицательным в течение итерационного процесса (условие 1);

• каждое выполнение тела цикла S уменьшает значение Е (условие 2).

Таким образом, выражение Е не может уменьшаться бесконечное число раз и оставаться положительным.

Как показано в главе 4, эти условия имеют ограниченное применение. В частности, существует большое количество программ (циклов), для которых условие 2 не выполняется, хотя соответствующие циклы завершаются. При этом причиной невозможности доказать завершимость цикла не является неудачный выбор целочисленного выражения Е. На невозможность доказать завершимость цикла влияет слишком жесткое условие 2, требующее обязательного уменьшения целочисленного выражения Е после каждого выполнения тела цикла. В то же время существует множество циклических программ, в которых уменьшение выражения Е гарантируется после многократного (два и более) выполнения тела цикла. Именно это наблюдение позволило нам существенно ослабить условие (2), заменив его на условие (2*) VE0 Зт ({0 < Е = Ео} Sm {0 <Е <Е0}), что позволило существенно расширить класс алгоритмов, для которых может быть решена проблема завершимости.

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

В работе показано, что в случае вещественного Е выполнение условий (1) и (2) (либо соответственно (2*)) само по себе не гарантирует завершимости цикла, а лишь свидетельствует о сходимости последовательности значений выражения Е, получаемых после каждого нового выполнения тела цикла к некоторой точке. Таким образом, для доказательства завершимости цикла в этом случае необходимо провести дополнительное исследование о характере сходимости последовательности значений Е, что является в большинстве случаев более простой задачей, чем исходная. Кроме того, предложенный подход позволяет упростить не только процесс доказательства завершимости выполнения циклов, но и анализ причин незавершимости в тех случаях, когда не удается доказать их завершимость.

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

• возможность контроля текущих значений переменных и их сравнения с предыдущими значениями;

• возможность задания шага (числа выполнения цикла) контроля изменения значений цикла;

• возможность генераций арифметических выражений (на базе множества переменных цикла) и анализа изменения их значений.

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

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

Для нахождения тестовых данных предложен метод использования аксиоматической системы Хора. Это позволяет не только обеспечить поиск тестовых данных (если они существуют) для выполнения заданного пути в программе (например, для случая путевого тестирования), но и выполнение заданных условий, налагаемых на исходные данные для тестирования компонент программы (например, в случае компонентного тестирования).

Выводы по главе 4

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

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

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

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

ЗАКЛЮЧЕНИЕ

В диссертационной работе:

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

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

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

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

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

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

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

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

1. Липаев В.В., Качество программного обеспечения, М., Финансы и статистика, 1983.

2. Липаев В.В., Проектирование математического обеспечения АСУ, М., Советское радио, 1977, 400с.

3. Липаев В.В., Распределение ресурсов в вычислительных системах, М., Статистика, 248с.

4. Липаев В.В., Конструктивные показатели качества программ и их связь с технологией проектирования, Известия АНСССР "Технологическая кибернентика", 1982, №2, с 151-163.

5. Липаев В.В., Позин Б.А., Блау С.А., Анализ стратегий тестирования логики программ, Кибернетика, 1982, "2, с 45-50.

6. Глушков В.М., Фундаментальные исследования и технология программирования, 1980, №12, с 3-13.

7. Ершов А.П., Введение в теоретическое программирование (беседы о методе), М„ Наука, 1977, 28с.

8. Касьянов В.Н., Анализ структур программ, Кибернетика, 1980, №1, с 48-67.

9. Каяниньш A.A., Борзов Ю.В., Инвентаризация после тестирования программ, В т. Синтез, тестирование, верификация и отладка программ, Тезисы докладов. Всесоюзная конференция. РиАГУ, 1981.

10. Кульба В.В., Пелихов ВлП., Шелков А.Б., Стратегия резервирования информационных массивов, В кн. Сборник трудов института проблем управления, М., 1978, вып.16, с 26-42.

11. Майерс Г. Надежность программного обеспечения, Пер. с англ. Под ред. В.Ш. Кауфмана, М., Мир, 1920, 360с.

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

13. Ахо А., Хопкрофт Дж., Ульман Дж., Тестирование и анализ вычислительных алгоритмов, Пер. с англ., Под ред. Ю.В. Матиясевича, М., Мир, 1979, 536с.

14. Goodenough J.B. and Gerhart S.L., Toward a Theory pf Test Data Selection. -IEEE Transactions a Software Engineering, vol., SE-1, WO. 2, June 1975, p. 156175.

15. Howden W.E., Functional program Testing., IEEE Transactions on SE, 1980, v. SE-6, №2, p. 162-169.

16. Howden W.E. Theoretical and Empirical Studies of Program Testing., IEEE Transactions on Software Engineering, 1978, v. Se-4, №4, p 293-298

17. Howden W.E., Reliability of the path analysis testing strategy, IEEE Transactions Software Engineering, vol. SE-2, p. 280-215, Sept.1976

18. Howden W.E., Algebraic program testing, Acta Informatica, vol. 10, pp 53-66, 1978

19. Howden W. E., An evaluation of the effective news of Symbolic testing, Software -Practice and Experience, vol.8, pp. 31-79, 1975.

20. Howden W.E., Methodology for the generation of program test data. IEEE Trans. Сотр. (Special Issue on Fault Tolerant Computing), vol. C-24, pp. 554-560, May 1975.

21. Howden W.E., Symbolic Testing and the Dissect Symbolic Evaluation system, -IEEE Transactions on Software Engineering, vol.SE-3, №4, July 1977

22. Howden W.E., Applicability of Software validating fech to scientific programs, ACM tranc. programming languages and Sust., vol.2, 1980

23. Howden W.E. and Eichhorst., Proving program properties from traces, in Software Testing and Verification Technignes 1-st ed., E. Mille and W.E. Howden, Ed. Long Beach, CA : IEEE, 1978

24. Littlwood B. Software reliability model for modular program structure.-IEEE Trans. Reliab., 1979, v.28, p.241-246.

25. De Millo R.A., Lipton R.J., Sayward F.G., Hints on test data selection. Help for the practicing programmer, Computer, Apr. 1978.

26. Алагич С., Арбиб M., Проектирование корректных структурированных программ. Пер. с англ. под редакцией О.М. Рякина, Радио и связь, 1984,263с.

27. Ю.П. Кораблин, Н.Л. Куликова, Программы как минимальные фиксированные точки. М. доклады международной конференции "Информационные средства и технологии", 1998, томЗ, с.24-30.

28. Geller М. Test data as an aid in proving program correctness. Commun Ass Comput Mash., vol 21, may 1978.

29. Courlay J.S., Theory of testing computer programs, Ph.D. dissertation, Univ. Michigan, Univ, Microfilms, 1981.

30. Weyuker E.J., Ostrand T.J., Theories of program testing aid the application of revealing subdomains, IEEE Trans. Soft. Ware Eng., vol Se-6, 1980.

31. Lamport L., On the proof of correctness of Calendar program. Commun. Ass. Comput. Mash., vol 22, Oct., 1979.

32. Kennaway J.R., Hoare C.A.R., A theory of nondeterminism. Automata, Languages and Programming (Lecture Notes Comput. Sci), vol.85

33. Huang J.C. An approach to program testing. Comput. Surveys, vol.7, Sept. 1975.

34. Holthouse M.A., Hetch M.J., Experience with automated testing analysis, IEEE Computer, vol.1, Aug, 1979.

35. Budd T.A. and other, Mutation analysis. Dep. Comput Sci., Yale Univ., Res., Rep. 195, 1979.

36. Lai K.W., Functional Usting of digital systems Ph. D. dissertation, Carnegie -Mellon Univ., 1982.

37. CrowT.S. Testing Software Eng., vol. SE-4, 1972.

38. White L.J., Cohen E.I., A domain strategy for computer program testing. IEEE Trans. Software Eng., vol. SE-6, May 1980.

39. Richardson, Clarke L.A., A practition analysis Method to incriase program reliability. Proc. 5 th IEEE Int. Conf. Software Eng., 1981.

40. Cartwright R. Formal program testing. Proc. 8th Ann. ACM Symp Principles of Programming Languages, 1981.

41. Gannon J., McMullin, Hamlet R., Data-Abstraction implementation, Specification and testing. ACM Tranc. Programming. Langguages Syst., vol.3, July 1981.

42. De Millo R.A., Lipton R.J., A probabilistic remark on the algebraic program testing., Inform Processing Lett., vol.7, June 1978.

43. Foster K.A., Error Sensitive test cases analysis (ESTCA), IEEE Trans Software Eng., vol SE-6, 1982.

44. Stucki L. New directions in automated tolls in improving software quality. Current Trend in Programming Metodology, vol 2.R.T.Ed. Englwood Cliffs N.J., Pentice -Hall, 1971.

45. Дейкстра Э., Взаимодействие последовательных процессов. В сб. : Язык программирования (Под ред. Ф. Женюи), М., Мир, 1972.

46. Hoare С.А., Communicating Sequential Processes. Communication of the ACM. 1978, v.21, v.8, pp. 666-677

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

48. Floyd R.W. Assigning meaning to programs In Proc. Sym. in Applied Math., v. 19, Mathematical Aspects of Computer Science, Amer. Math. Soc., 1967,pp.19-32

49. Manna Z., Mathematical Theory of Computation. N.Y. Mc-Grau - Hill Book Co., 1974.

50. Куратовский К. Топология, т.1, М.: Изд-во "Мир", 1966, 594с

51. Apt K.R., Ten Years of Hoare's logic: A survey -part 1 ACM Transactions on Programming Languages and Systems, vol.3, №4, 1981, pp.431-483

52. Росс Г.В. Принципы оптимизации математического обеспечения автоматизированных систем управления, Докторская диссертация, ВНИИПВТИ, 1991,250с.

53. Кутепов В.П., Кораблин Ю.П., Фальк В.Н. Исчисление функциональных схем, Сб." Цифровая вычислительная техника" №8, 1974.

54. Кутепов В.П. Исчисление функциональных схем и параллельные алгоритмы. Программирование АНСССР, №4, 1975г.

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

56. Хорев П.Б. Методы разработки программных средств, М.: МЭИ, 1994, 119с.

57. Куликова Н.Л., Рякин О.М. Структурные методы тестирования программ. -Учебное пособие по курсу "Системное программирование ", М., МЭИ, 1983г., 92с.

58. Рякин О.М. Основы методологии проектирования корректных программ. Учебное пособие по курсу "Системное программирование", Мм МЭИ,1980г., 82с.

59. Агафонов В.Н. Спецификация программ: понятийные средства и их организация. М., Наука,1990г.

60. Кораблин Ю.П. Семантика языков программирования. М., МЭИ, 1992г., 98с.

61. Кораблин Ю.П. Распределенные вычисления, М., МЭИ, 1989г. 65с.

62. Кораблин Ю.П. Семантика языков распределенного программирования, М., МЭИ. 1996г., 101с.

63. Кораблин Ю.П., Куликова Н.Л. Завершимость выполнения алгоритмов, Тезисы докладов международной конференции "Информационные средства и технологии", М., 1996г.

64. Кораблин Ю.П., Куликова Н.Л. Ассиоматический метод поиска тестовых данных. Тезисы докладов международной конференции "Информационные средства и технологии", М., 1999г.132

65. Кораблин Ю.П., Налитов С.Д., Куликова Н.Л. Распределенное программирование на языке асинхронных функциональных схем, Методическое указание к лабораторным работам по курсу "Структуры вычислительных машин и вычислительных систем", М., МЭИ, 1996г.

66. УТВЕРЖДАЮ" Генеральный директор и главный конструктор

67. Открытое «кдшомрнов обществоцентральный научно-исследовательскийинститут специального машиностроения (оао цниисм)141350 г. Хогыгою, Моссовета 064., телеграф Хотмоао ,3*pt' тедетавп 846203 .Заря* '1. ЦНИИСМ"шш!1. Js¡J /V