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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ Р С Ф С Р-. ПО.ДЕЛАМ НАУКИ И ВЫСШЕЙ ШКОЛЫ,

РОСТОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГ0 .ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ .

Региональный специализированный совет К 063.52.12

На правах рукописи

УРТАНС ГУНТИС БРОНИСЛАВОВ!«

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

05. 13. 11 - математическое и программное обег.пвч-знче вычислительны» машин, компежксов, систем и сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технически:: наук

Ростов-ка-Дону 1.391

)

Работа выполнаиа а ЕГУ им.В.К.Лаккна

Научный руководитель:

доктор техничэскнх наук, профессор' КАТКОВ В. Л.

Очч'цдалькые опоненты: доктор Фиэико-иатэматичаских наук,

ЦЕЙТЛИН Г. Е.

кандидат Физико-математических наук, АБРАМОВИЧ С. М.

Ведущая организация:

Институт технической кибернетики АН БССР

Защита состоится -и и/с?3 199 ¿г. Б/^&асов на заседании специализированного совета К 063.52.12 по присуждению ученой степени кандидата технических наук в Вычислительном центра РГУ по адресу:

344104, Ростов-ча-Дону, проспект Стачки, 200/1'корпус 2.

С диссертацией можно ознакомиться в библиотеке РГУ по адресу: ул.Пушкинская, 148.

С'

Автореферат разослан

Ученый секретарь специализированного совета кандидат технических наук

X. Л. Дженнбаяаев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Суиественио улучшить ситуацию при тестировании могут CHEieBU яптомгугиддиии трптцгояпяия прпгрями, так как они: избавляют разработчика от рутинных операций (или хотя бы сокращают их обьем); следят за качеством тестирования. Одна иг основных .Функций систем автоматизации тёстирования - автоматизация построения полных относительно структурных критериев тестирования программ систем тестов. ,

Поль работы. Целью диссертации является разработка методов автоматизации построения полных систем тестов относительно заданных структурных критериев тестирования программ и использование этих методов при разработке системы автоматизации тестирования для программ на языке ПЛ/1.

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

-разработан новый метод построения покрывающего нножества путей для структурных критериев тестирования программ;

-впервые разработан символьный интерпретатор путч программы для языка ПЛ/1;,

-разработан язык символьных выражений SEL/PL для представления символьных выражений программ ПЛ/1 и выдачи пользователи функции пути программы ПЛ/li

-дополнан и уаовераенствоэан метод свгиантов для решения условий реализуемости пути, основанный на "угадывании" тестовых

значений, ______

-—предложена технологическая схема тестирования, основанная

на автоматизации построения полных систем тестов.

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

Реализация результатов. Описанные в работа методы реализованы в системе автоматизации тестирования, предназначенной для тестирования программ на языке ПЛ/1. Реализация системы содержит: процедуры Формирования внутреннего представления программы (3000 операторов ПЛ/1), стратеги» выбора покрывающего множества путей (5000 операторов), символьный интерпретатор пути программы (5000 операторов), решатель условий реализуемости (5000 операторов), обсяухив&юиие программы (20 ООО операторов).

Работа . ведется в- рамках научно-исследовательской темы "Разработка методов решения задач дискретного программирования и распознавания образов в системах автоматизации лроекгкрованния, управления и обработки данных" (N гос. per. 01860033920!, Система включена в инструментальный комплекс разработки программного обеспечения РНТН. Результаты исследований используются при ведении курса "Тестирование и отладка программ ЭВМ" в Латвийском Университете.

Публикация и апробация работы. Основные результаты работы докладывались:

-на республиканской научно-технической конференции молодых ученых "Проблемы развития и использования ЭВМ обдого назначения", Минск, 1984г.

-на школэ-кокферэннии молодых ученых ВЦ СО АН СССР, Новосибирск, 1984г.

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

качества программного обеспечения ЭВМ", Севастополь, 1986г. -на всесоюзном семинаре "Информатика и ВТ", Зеленоград, 1986г. -на всесоюзной кон<реренции "Проблемы совершенствования синтеза,

тестирования, верификации и отладки программ", Рига, 19""6г. -на республикансой научно-технической конкуренции "Перспективы развития и проблемы эффективного использования ЭВМ общего назначения и персональных ЭВМ", Минск, 1987г. -на научно-технической конференции "Повышение качества

программного обеспечения ЭВМ", Севастополь, 1988г. -на всесоюзной научно-техническом семинаре "Качество программных средств", Калинин, 1990г.

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

ОСьен работы. Диссертация состоит нэ введения, 4 глав, заключения, списка литературы (68 названий), 2 приложений. Работа изложена на 155 страницах машинописного текста и включает 1 рисунок.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Задача построения ПСТ состоит в получении двух взаимозависимых множеств: тестовых данных и тестовых путей. При построении необходимо какой-то из этих объектов взять за основу, т.е. нужно выбрать одну из двух возможностей: 1-)построить систему тестов и убедиться, что соответствующая система путей - покрывающее множество путей; 2)построить покрывающее множество путей и найти соответствующую ПСТ (если такая существует).

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

Начальный путь программы назовем Еаадиаяаиыи,___если_ суиествуют тастовые^данные^ на катовых-прогтанна выполняет именно путкт—Выполнение именно заданного пути программы зависит от значений предикатов в точках ветвления программы, в своп очередь значения предикатов определяются тестовыми данными. Ограничения на входные данные, достаточные для того, чтобы выполнялся

заданный путь, будем называть ¡гсгпяиям» раяяизувмпгти пч-т« Условия реализуемости пути являются системой уравнений над входными значениями программы и могут быть получены при

г.интльнам_птпятти_пгти_программы. Каждое частно» решение

условий реализуемости является тестовыми данными для выполнения пути, эадеюяего условие реализуемости.

Упрптянняа г.твмд пплтупвяия ПОТ таким образом имеет следующую структуру:

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

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

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

В диссертации предлагается третья группа методов построение покрывавяего множества путей и тестовых данных

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

Ппнпянпй иц^вй яииямнурсг.их мятттпя является подсоединение к йачагькам реализуемым отрезкам путей дальнейпих их частей таких образом, чтобы, во-пбР2ЫК; не терять при этом реализуемости внов! полученных путей и, во-вторых, покрыть требуемые элементы структуры программы. Л*<1 пррдп"*Ч рядлилуямпптн пути используется символьный интерпретатор пути программы с решателем условий реализуемости (описываются далее). л*я покрытия требуемых элементов используется эвристический алгоритм (стратегия) выбора продолжения начальных путей. Различные стратегии различаются между собой именно способом выбора продолжений начальных путей, определяющим, пути какого вида и в какой последовательности будут строиться. Целью использования эвристики является эффективность покрытия требуемых структурных элементов программы. Функции эвристики реализуются путем вычисления припритвчои начальных реализуемых путей. Элемент, имеющий на данный момент наивысший приоритет, используется для очередного продолжения.

Гтгт-грг-ист ляяяршдрт^а уппрячп, если: 1)поау-чэно покрывающее множество путей; 2)исчерпаны все продолжения начальных реализуемых"" путей, т.е. просмотрены все реализуемые пути. В первом случае получено покрывающее множество путей, во втором улучшить степень тестированностн программы по сравнению с полученной не удается, так как рассмотрены все реализуемые (по мнению решателя условий реализуемости) пути программа.

Необходимость опряпядвння цэлесообразнвсти_пмдодичняя построения определяется тем, что не всегда удается достичь одну из упомянуты* ситуаций. Это может произойти по следуюаим причинам: 1)некоторые структурные элементы в принципе нерваяизуемы, т.е. не существует входных данных, при которых покрывается часть структурных элементов; 2)для покрытия некоторых' элементов необходимо построить слишком длинный и сложный путь. В первой случав, покрыть элементы невозможно, во втором можно продолжить построение для полного покрытия. Сложность проблемы состоит в той, что при построении невозможно определить, по какой из причин элемент еше не покрыт. Во втором случав для.полного покрытия может потребоваться очень большой обьем перебора вариантов, причем оценить число вариантов перед началом работы стратегии практически невозможно.

В 1.4 описывается пбшд» схема работы всего семейства

ст;

содержит структурные элементы программы, определенные критерием тестирования; ЦШ -покрывающее множество путей; содержит, начальные реализуемые СТСП-пути; Н2. -множество непокрытых элементов; 2ДЦД -множество элементов, покрытых начальным» путями! ЗЯ-СД -множество элементов, покрытых построенными СТОП-путяии! содержит структурные элементы программы; Н£Д -множество начальных реализуемых путей-кандидатов для дальнейшего построения путей! содержит следующую информации о начальных путях: Рррп.нп -начальный путь; 2)Нрр.СП -состояние программы после символьного выполнения данного пути; содержит символьные значения переменных и условия реализуемости пути; 3)НРП ПЭ - структурныэ эдеиактЫ| покрытые данным путем; 4)ВЕИЛЩ - приоритет пути; числовое значение; используется для определения очередности выбора продолжений начальных реализуемых путей, способ вычислений приоритета задает используемая эвристика. БПЭ является исходным множеством, ПМП - результатом, остальные множества - рабочие. > Множестве. НЭ, ЭПНП, ЭПСП, НРП. ПЭ являются подмножествами БПЭ.

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

Пяррп пяриим_яипплнр.нчрм ник-та рабочие обьак-хы стратегии

заполняются следуюяим образом: 1) ПМП - пустое; 2) НЭ - все покрываемые элементы; 3) ЭПНП - пустое; 4) ЭПСП - пустое; 5) НРП - содержит единственный элемент: путь от входа программы до первого оператора с несколькими выходами.

Действия, выполняемые при пппшля икид стратегии:

1) Выбираем из НРП путь с наибольшим приоритетом.

2) Если этот путь реализуем, выполняем. 2.1-2.3; иначе переходим к 2.3.

2. 1) Если это СТОП-путь,, добавляем его к ПМП (если данный элемент покрывает хотя-бы один ранее непокрытый элемент НЭ).

2.2) Если это не СТОП-путь, в НРП добавляем все его

-о£

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

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

Все описанные действия сопровождаются соответствуюдей корректировкой рабочих множеств.

В 1.S дано более формальное описание стратегий:

стратегия:ргос;

/* Начальное присваивание */

ПМП=0; НЭ=ВПЭ; ЭПНП-О; ЭПСП=0; НРП=ШРП(1)>;

do while(finish(НЭ.НРП))

е=тахрге1Л(НРП.Ш1); /* поиск элемента с макс, приоритетом */ if feasible(НРП(е). СП)

then doi /* путь реалиэуви */

if atop (НРП (е) .НП)

then do; /* СГОП-путь */

if НРП.ПЭ(е) * НЭ"=0

then do; Покрыты новые элементы */

1М1=ПМЛ+<НРП(е) ,НП>; Н9= НЭ/НРП(е). ПЭ; ЭПНП=ПЭ/НРП(е). tI9i ЭПСП=ЭПСП+НРП(е) .ПЭ; .' end;

end;

else /* ке СТОП-путь */

do i=l to exita(НРЯ(е).НП)> np=succ(HPn.(e),i)j зр-symbint(np,НРП(е). СП); psicovelm(np);

pr=prior(пр,ре,НЭ,ВПЭ,ЭПНП.9ПСП); ■ НРП=НРП+{(ар,эр,ре.pi)>! ЭПШ-ЭПНП+ре; end;

end;

НРП=НРП/(НР!1(е)) j /* удаление обработанного элемента */ end; end стратегия;

Использованы стандартные операции над множествами: объединение "+", сечение "*" и разность "/".

Все элементы множеств перенумерованы; НРПti? - i-й элемент jSecria КРП. Первым элементом множества начальных реализуемых путей всегда будет начальный путь от входа в программу до первого ветвления - оператора с более чем одним выходом.

Функция aiceCHPnti)): true, есси HPII(i)- СТОП-путь, falaa -в других сжучаях. функция ieaaibla(HPn(i). СП) возвращает true, если путь НРПШ.ВД реализуем, false - в других случаях, функции реализует решатель условий реализуемости пути, описаний в третьей главе, функции micc.(HPn(i), j) возвращает продолжение HPn(i).Hn по j-му продолжению пути .до следующего ветвления или выхода из программы. Допустимое значение j для определенного пути задает управляющий грач» программы, это значение возвращает Функция &xiia.(HPnCi). ЙП). функция ixaisli вазвраяаьт true, если следует завершить работу стратегии, и false - в остальных случаях. Если НРП^О иди НЭ=0, возвращается значение true, иначе ответ определяет эвристика. Функция тягсгаТт возвращает номер элемента множества начальных реализуемых путей с наибольшим приоритетом. Подпрограмма чггсЫ nt •строит состояние программы посредством символьного выполнения пути, подробнее символьное выполнение описано во второй главе. Подпрограмма cnvalm строит множество покрытых структурных элементов пути (в зависимости от критерия тестирования). Функция ргзпг ваавраиаат приоритет создаваемого элемента используя определенный эвристический алгоритм.

В 1.6 рассмотрена модификация стратегии для схемы тестирования ТСТ, в которой на начальном этапе тестирования предусмотрено

использование других способов получения тестов. В этом случае в

t>

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

Для этих целей произведены следующие изменения: 1)стратегия получает на входа множество пользовательских тестов и множество пользовательских путей предназначенных для их первооче;едкой проверки; 2)при каждое проходе цикла стратегии пользо! ателю предоставляется возможность корректировки рабочих множеств путем добавления пользовательских путей и (или) тестов.

дано описание эвристик стратегии системы автоматизации построения тестов программ ПЛ/1.

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

Пусть Р - множество синтаксически правильных программ на определенном языке программирования (например, ПЛ/1),- a pth(p) -множество всех конечных путей программы р (р4Р).

Пусть С- - структурный критерий тестирования программ Р, задавший для каждой программы р-(Р множество покрываемых структурных элементов С(р). Функцию С можно применять также к путям и множествам путей, в этом случае ее результат- структурные элементы, покрытые данным путем (путями множества в совокупности). Множество путей S называется покрывающим множеством путей программы р относительно критерия С, если C(S)=C(p).

Для большей наглядности следующих построений ■ далее сузим множество программ Р, рассматривая только те программы р, для которых С(pth(p))=С(р), т.е. программы без мертвого кода и черных дыр. Выявления упомянутых аномалий производится методами статического анализа потока управления программ.

Птятия>тгуим uwnvriM построения покрывающего множества путей для критерия С будем называть функцию Sip), значения которой -подмножества pth(p) со свойством C(S(p))=С(р).

Введем функцию реализуемости путей г от множеств путей программы р, значением которой является реализуемые пути аргумента (определение реализуемости - в начале главЬ). Отметим, что r(pth(p))^pth(p).

ГСиндмичяпгкм wwrumi построения покрывающего множества путей для критерия С будем называть функцию D(p),' значения которой -подмножества r(pth(p)> со свойством C(Dip)) =С(р). Отметим, что требование C(D(p))=C(p) не может быть предъявлено ■ ввиду алгоритмической неразрешимости проблемы построения ПСТ для языков, содержащих арифметические преобразования данных.

Основным недостатком статических методов является то, что VS множество г(S(р)) может быть значительно меньше S(p), вплоть до

r{S(p))=0, в отличии от динамических методов) для которых D(p)=r(Dip)). С другой стороны динамические методы также не гарантируют определенного уровня C(D(p)).

В преддогенных обозначения» показатель минимальности обьема множества путей для статических методов KM(S,p)=|S(p) |, для динамических - KM(D,p)=|D(p)|.

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

Для статических методов это значение -KP(S,p)=|C(r(S(p)))|/|С(р)| , для динамических методов -

KP(»,p)=|C(r(D(p)>)|/|С(р)|=|С(Р(р))|/|С(р)| . Для сравнения эффективности статических и динамических методов докажем следующее утверждение, используя оба введенных критерия эффективности.

Утверждение., 1 ■ VS VC ЭС Vp4P

(С(г(S(p) ) )=С(р) ==> KP(D,p)=KP(B,p) & KM(D,p)=KM(S,p)) & (С(г (S(p)) )<С(р) ==> (K£>(D,p) = KP(S,p) & KM(D,p)<KH(S,p)

! KP<D,p)>KP(S,p) & KM(S,p)<=KM(5,p)> Содержательное значение утверждения: для каждого статического метода можно построить такой динамический, который дает боле© качественный результат ' как минимум по одному из выбранных критериев эффективности (если »то в принципе возможно) и на хуже - по яругокг.

Во второй гдоае рассмотрены вопросы построения условий реализуемости пути с помощь» сниаоаьиагп выполнения пути_прог.ваими.

Символьное выполнение изяиегов достаточно сложный методом, поэтому пока не существует доступных массовому • пользователи ПУ^рд^ни* ц|^т»ртрттятпопя цжя основных языкоя программирования. Б диссертации рассмотрена проблемы реализации символьного выполнения пути ярограхмн и предложен символьный интерпретатор пояжносества языка ПЛ/1-0ПТ.

В 2. i. рассиотрены основные положения символьного е толне-нкя. йжя этого производится масекатсания знлчаний программы по як "проясжовиевяю" - fjnrnnittjp дялчаяия - значения, нспольэуэмыо в качестве аргументов вычислений; выгодные, аиачашн. - результаты

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

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

В 2.1.5. дано определение символьного выполнения. Симвсльапй пмпялнрни* - это метод статического анализа программ для получения функциональной заьисимостн выходных значений (рогульготов) программы от ее исходных значений. Функциональная зависимость

программы. Аргументами выражений явжяится не конкретные (числовые, строковые и т.д.) 9«1«чв«яя, а символьные исходное значения, представляюиие "некотор«ч >иач»«и« определенного типа".

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

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

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

Далее рассматривайте* свойства символьного выполнения, основным из которых является корректность символьного выполнения.

Обязательный требованием является адекватность пряпбразоаа-Ш1&, которое заключается в том, что при символьном и обычном выполнении пути программы должны выполняться: 1)те жэ преобразования (операции и функции); 2)над теми же данными. При реализации символьного выполнения наиболее сложным является последнее требование адекватности в некоторых случаях использования сложных . структур данных'(индексированных, базированных).

Пусть дана программа и произвольный путь в ней. Пусть api, ..., зрп - исходные Символьные значения программы; pt, ..., Рг> -соответствующие конкретные значения; ari(sp>, .... врп), . ..., 0t«(8pt, , .., г р.,) - выходные символьные значения программы; con - функция конкретизации символьных значений; гi, ra, ..., г» -конкретные значения переменных после обычного выполнения пути на ук&эанных конкретных значениях; urp(spt, ар=, ..., арл) - условия реализуемости пути. Отметим, что зг» - символьные выражения над исходными символьными значениями зр», ара, ..., вро , а игр -

система уравнений над ними.

к.

Г!ицвп]ч,мпя пмппянвния данного пути будем называть клрр^к-гиым, если: 1)Путь программы выполняется на тех и только тех исходных значениях программы, которые являются решением условий реализуемости пути для данного пути; 2)Если заданный путь выполняется при исходных значениях pi,p=,...,рп и выходные значения программы - n,ra,... ,tv., то для каждого к

На практике такую корректность не всегда удается достичь.

Для того, чтобы выполнить второе требование адекватности иногда

с

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

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

выполняется путь, заданный условиями реализуемости пути; 2)Если

соп(зГк (apt ,ара,. . ,spr.), pi ,p=¡.....рг>)=гк .

Pi, ..., îv. являются радениями условий реализуемости пути для заданного пути и выходные значения программы для них - гч, Гп, то для каждого k con(arw(spt.....sp^. ,pi ,'Г» ,ро) =ги .

В 2.2. рассмотрены возможности применеция символьного интерпретатора и требуемые свойства символьнного выполнения при различных применениях. В 2.3. дан обзор систем символьного выполнения, основное внимание уделяя проблемам реализации символьного интерпретатора, рассмотренным далее в 2.4. Этими проблемами являются: Формат операндов символьных выражений, упрощение выражений, обработка индексированных переменных, обработка структур и их 5лементов, работа с указателями и базированными переменными, обработка вызова подпрограмм, учет исключительных ситуаций, учет преобразований типов данных-» выбор способа интерпретации, выбор Формата выполняемой программы и внутренних данных интерпретатора, выбор управляющих директив интерпретатора.

Результатом анализа этих проблем является предложенный в диссертации язык символьных выражений для представления символьных выражений языка ПЛ/1 - ЯЕГ./РГ. (Bymbolic Expreaaion Languaee for PL/1). Объекты SEL/Pt, состоит из двух частей: собственно символьных выражений и словаря символьных выражений. Выражения языка строятся из исходных значений программы и вспомогательных значений при помощи операций и функций языка. Каждый элемент и выражение имеет атрибуты, задающие тип значения, о^нпянив дтркбгтм символьных значений совпадают с атрибутами данных в соответствующем языке программирования•(т. е. ПЛ/1). Выражения сами не содержат описания атрибутов, описания находятся в словаре символьных выражений, что увеличивает наглядность выражений, позволяя при необходимости узнать или проверить значения атрибутов.

Элементами (атомами) языка SEL/PL являются исходные символьные значения программы (входные значения, константы, ' системные значения, результаты внешних подпрограмм и случайные значения) к вспомогательные символьные значения, ,'•' .'

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

В символьны* выражениях используются все операции- и встроенные функции, используемые в ПЛ/1. Кроме этого в выражениях используются некоторые специальные функции символьного

выполнения: conv - изиенекие типа значения; array - массивы, структуры и их элементы; based - области базированной памяти.

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

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

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

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

В 3.1. описывается исторически первый метод данного типа -иртпч npnfi ir nmfint, использованный авторами системы CASEGEH. .

Другой метод, относящийся к вышеупомянутому классу решателей условий реализуемости пути, - пятой гягрднтон. был предложен для системы СМОТЛ. В 3.2 рассмотрены основные положения усовершенствованного метода сегментов.

Можно считать, что метод сегментов представляет собой целенаправленное угадывание решения условий реализуемости пути. Решение проводится в три этапа:

1<Уг;тя^пик-я нд.чмльим* пгрдничвний Устанавливайте! начальные ограничения на пЯяяпть' »ппувтнмм» яндчяний каждого элемента (т.е., переменной или выражения) системы, исходя из определения переменной, ограничений, заданных пользователем.

2)Уточнение_пгодннчвиий. Последовательно уточняются

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

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

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

Если выясняется, что на некотором шаге решения область ДОПУСТИМЫ.* значений какой либо переменной или выражения системы пусто, или же выбираемые конкретные значения все-таки не удовлетворяют систему, делается вывод об отсутствии решения.

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

решение и в результате получен конкретный тест (подчеркнем, что решение в обием виде не ищется); 2)'скстема на самом деле имеет решение, но получить тест не удалось; Э)Система не имеет решения и в результате доказано отсутствие теста; 4)Система на самом деле не имеет решення, но доказательство отсуствия решения не получено. С точки зрения построения теста все случаи кроме первого эквивалентны, тек как приходится обьявлять путь, соответствующий условиям реализуемости пути, ' нереализуемым (возможно - ошибочно).

В 3.3. рассмотрен простой пример работы метода сегментов, а в 3,4. - основные объекты, с котрыми оперирует метод: выражения условий реализуемости пути и области допустимых значений.

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

операция) назовем аыважаниимн_гсдавий_ряалнзуямопти путч, а

результаты и операнды всех выражений ^лямвитями угргпяий дгяалнлуямости пути.. ,

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

В предложенной а диссертации версии метода сегментов

Областями_ДОПУСТИМЫХ_лндчений ЯВЛЯЮТСЯ конячимя ПД^ЯДЧНЯЯИ»

сегментов, полусегментов, интервалов и точек.

В 3.5. описай этап присвоения нячдльных областей допустимых аианеаий., которые формируются исходя из: 1)атри6утов значений; 2)требований условий реализуемости пути; 3)определений встроенных Функций; 4) Форматов ввода данных; 5)указаний программиста; 6)эвристических предположений. При этом первые четыре из них задают объективные ограничения на области допустимых значений, за которые значения переменных и выражений не могут выйти. Остальные ограничения являются субъективными предположениями программиста (5) и.авторов решателя (6) о вероятнейпшх ойластях значений.

Ярядуд ятпрлго угдгтя натопи пагмантпв: минимизация (сужение) областей допустимых значений всех элементов условий реализуемости пути с тем, чтобы увеличить вероятность быстрого угадывания решения в дальнейшем. При этом на основе анализа условий реализуемости пути минимизируются области допустимых значений не ТОЛЬКО ДЛЯ переменных, НО и ДЛЯ выражений. Алгоритм гтужяиия рР^яр.трй пппуг.тиимх лндчяяий заключается в последовательном просмотре выражений, и попытке минимизации областей допустимых значений операндов и результата согласно заданный правилам минимизации. Правила минимизации эаексят от операции данного выражения, типов Операндов и видов их областей допустимых * значений. Обшня правило минимитянии - фиксация результата, если области допустимых значений всех операндов выражения - точки.

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

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

Алгоритм уточнения областей допустимых значений используется также пасла пчачаднпй »никсаиии знячяния■ так как изменение области допустимых значений одного- элемента дает возможность дальнейшего уточнения других областей допустимых значений. В

случае Фиксации_значений веэ» параиянкы* (на третьем этапа

метода), алгоритм минимизации является проверкой того, НЕЧяется ли данная Фиксация решением условий реализуемости пути.

Схема работы этапа уточнения:

уточнение_области_допустнимх_значений: proc returns (BIT(l)); do until (krO)i k=0;

do i=l to чнсло_£Ыражений_д_УРП;

применить_правкла_миш1миэации_к_выраженн»_1; select! when (ОДЗ_суэилась) k=l;

when (ОДЗ_лротиворечива> return''О'В)i other; end;

end! end;

return('l'B),

end уточнение_области_яопустимых_значений|

Далее описываются правила минимизации . для различных операций.

Правила минимизации для арифметических операций основаны на их монотонности. Возьмем исходные области допустимых значений -сегменты: Са1,а23 - для первого операнда! СЫ,Ь2] - для второго операнда; [rl,r2] - для результата обозреваемой операции. Дадим правила для основных операций (области допустимых значений операций и операндов - ранее описанные сегменты): >

операция конечные области допустимых значений

первый операнд второй операнд результат

+ Cmax(al,rl-b2), min(a2,r2-bl)3 [max(M.rl-a2), min(b2.r2-al)] tmaxlrl ,аД+Ы), mlntr2,а2+Ь2>]

- [иах(а1,Ы+г1), min(a2,Ь2+г2)) Cmax(M,al-r2), mln(bl,a2-rl) ] Cmox(rl,al-b2), и1п(г2,а2-Ы)]

* Cnvax(al,rl/b2), min(a2,r2/'bl) 3 Cmax(bl,rl/a2), mln(b2,r2/al)] tmax(rl,al*bl) ,■• nin(r2,«,2*b2)3

/ Ctnax(al,bl*rl), min(a2,Ь2*г2>J Cmax(bl,al/r2), mln(bl,a2/'rl)] Cmax<rl,*J/b2(, Blnfr2,a2/bl)]

Упомянутые правила для "+" и "-" действуют для всей области

значений, а "*" и "/" - для сегментов с положительны«*, границами. Для последних двух операций аналогичные правила мо.тно *напнсать для сегментов в других областях. В 3.6. описана также правила минимизации для других операций и встроенных функций ЯЛ/1.

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

<риксирование_эначений:ргос returns (BIT(l)); выбрать_последовательность_Фиксируемых_знвчений; i=t; 8=0;

do while(1>число_Фиксируемых_эначений); o

Фиксировать_значениа(i);

гс=уточнить_области_допустиных„значений; if гс=-1 tben do;

s(i)=s(i)+l;

if s (i) >допустииое_чисхо_Фкксироваиий then do;

s(i) = 0;

1=1-1;

if i=0 than return('O'B); end; end; else i=i+li ends returni"1*B); ' end Фиксировакие_значений;

Процедура содержит вызов процедур для решения следующих задач: 1)выбор последовательности Фиксируемых значений; 2)опреде-яениэ допустимого числа фиксирований значения; 3)Фиксирование значения; 4)уточнение области допустимых значений после очередного Фиксирования. Последняя из перечисленных процедур - второй

этап мчтода, остальные изложены'в 3.7.

Четвертая глава посвящена вопросам технологии приир-'Эння средств автоматизации построения ПСТ, описанных в первых трех главах. В 4. 1. описана традиционная схема построения ПСТ и отмечены основные ее недостатки. В 4.2. описан инструментальный комплекс РИТМ, используемый в качестве основы для технологической схемы построения ПСТ.

Технологическая схема теотирояяния и птяндки прпгупим (ГСТ):

В диссертации предлагается схема действий и технологические средства построения ПСТ, которая основывается но следующих поло-

жаниях; -1.Использование существующих гестов для предварительного тестирования и учет этих тестов при автоматическом построении ПСТ; 2.Накопление тестовых данных путем многократного использования средств автоматизации построения ПСГ, использование данных полученных на прежних итерациях построения тестов;

3.Повторное тестирование программы после исправления ошибок;

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

Описанная схема имеет следующие положительные свойства: 1.При построении ПСТ используются предварительно подготовленные тесты, что увеличивает эффективность построения ПСТ; 2.Повторное тестирование после исправления ошибок оперативно проверяет программу на предмет внесения новых ошибок в ходе исправлений; 3.Построение новых тестов производится только при успешном выполнении ранее предложенных; 4.Возможность выбора критерия тестирования позволяет после оттестирования программы относительно какого либо критерия» перейти к тестированию относительно другого, используя ранее построенные тесты.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

. 2..-Вперсыэ разработан символьный иитвепитатов дая языка программирования ПЛ/1, реализующий кроме построения условий реализуемости пути выдачу пользователю функций путей программ, возможности диалоговой символьной отладки. Разработан язык символьны)! выражений SEL/PL для представления преобразований данных при символьном выполнении программ на языке ПЛ/1.

3. Для решения условий реализуемости пути дополнен и модифицирован мдтпд сяг^яитпя м«яння уг?дор»й вдядттвмгети пути. Модификации метода заключаются в: систематизации источников установки начальных областей допустимых значении, возможности применения некомпактных областей допустимых значений, дополнении и уточнении правил минимизации для операций и встроенных функций, возможности использования в условия* реализуемости пути специальных функций языка описания преобразований, управлении процессом выбора конкретных значений.

4.Предложена среда функционирования системы построения ПСТ в виде тягнгигпгнчрекрй иирни тестировании» и отладки 1СХ на основа системы автоматизации тестирования ПЛ/1-программ и инструментального комплекса РИТМ.

Основные результаты диссертации опубликованы в следующих работах:

1. Дишлерс Г.Э. , Медведис Н.Э., Уртанс Г.Б. ТЕСТГЕН - система символьного тестирования //Тезисы докладов республиканской научно-технической конференции "Проблемы развитие и использования ЭВМ общего назначения". Мн. -1984. -С.84-85.

2.ТЕСТГЕН - система символьного тестирования программ /Ю.В. Борзов, Г, Э. Дишлерс, И. Э. Медведис, Г. В.Уртанс //Тезисы докладов всесоюзной научно-технической конференции "Программные средства как продукция производственнноттехнического назначения". Калинин. -1985. -С. 153-156.

3.Система символического тестирования ПЛ/1-программ /Ю.В. Борзов, Г.Э. Дишлерс, И. Э. Медведис, Г. Б. Уртанс. /^УСиМ. -1986. -N6. -С.75-79.

4.Дишлерс Г.Э., Медведис Н.Э., Уртанс Г.Б. Система символьного тестирования СИПЛ/1 программ. //Тезисы докладов всесоюзного семинара "Информатика и вычислительная техника". М. "Наука". -1986. -0.158.

5.Дишлерс Г.Э., Медведис Н.Э., Уртанс Г.Б. Эксперименты по построении полных систем примеров для ПЛ/1 программ. //Тезисы докладов республиканской научно-технической конференции "Повышение качества программного обеспечения ЭВМ". Севастополь. -1986. -С.33-34.

6.Уртанс Г.Б. От функции пути к Функции программы //Тезисы докладов всесоюзной научной конференции "Проблемы совершенствования синтеза, тестирования, верификации и отладки программ". Рига. -1986. -т. 2. -С. 116-117.

7.Уртанс Г. Б. функции путей программ //Программирование. -1987. -Н4. -С. 69-78.

в.Уртано Г. Б. Опыт построения симзольного интерпрэтатора программ //Тезисы докладов научно-технической конф. "Перспективы развития и проблемы зфф. использования ЭВМ общего назначения и ПЭВМ". Мн. -1987. -С.41-43.

9. Борзов Ю. В. , Уртано Г. Б. , Иимаров В. А. Выбор' путзй программы для построения тестов //УСиМ. -1989. -N6. -С.29-36.

Ю.Уртанс Г. Б. Символьный интерпретатор программы как инструмент тестирования программ //Программное обеспечение ЭВМ /АН БССР. Ин-т математики. -Ми., 1989. -Вып.85. -Й.185-197.

11.Борзов Ю.В. , Иедведис К.Э., Уртанс Г. Б. Метод сегментов дли реиения систем равенств и неравенств при генерации тестов для Проверки программ //УСиМ. -1990. -N2. -С. 49-58.

12.Уртанс Г. Б. Технологическая схема построения полных систем тестов программ //Тезисы докладов всесоюзного научно-технического семинара "Качество программных средств". Калинин. -1990. -С. 70-72.

Уртанс Гунтис Брониславович, Автореферат. Методы и ' средства автоматизации построения полных систем тестов.

Подписано к печати о2»91« Фб 60x84/16 Физ.пач.л. .Бесплатно.

Отпечатано в типографии Латвийского Университета 226050, Рига, ул.Вейденбаума, 5. $.156