Технология индустриального программирования

Котляров В.П. Технология индустриальногот программирования
ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ТЕСТИРОВАНИЯ
Программа – это аналог формулы в обычной математике.
Формула для функции f, полученной суперпозицией функций f1* f2* f3*... * fn
– выражение, описывающее эту суперпозицию. Если аналог f1... fn – операторы языка программирования, то их формула – программа.
Существует 2 метода обоснования истинности формул:
i) Формальный подход или Доказательство применяется, когда из исходных формул-аксиом с помощью формальных процедур (правил вывода) выводятся искомые формулы и утверждения (теоремы). Вывод осуществляется путем пере-хода от одних формул к другим по строгим правилам, которые позволяют свести процедуру перехода от формулы к формуле к текстовой подстановке:
A**3 Ю A*A*A Ю A → R, R → A*R, R → A*R
С помощью формального подхода удается избежать обращения к бесконечной области значений и на каждом шаге доказательства оперировать только с конеч-ным множеством символов. ii) Интерпретационный подход применяется, когда осуществляется подстанов-ка констант в формулы, а затем интерпретация формул, как осмысленных утвер-ждений в элементах конкретных множеств значений. На конечных множествах проверяется истинность интерпретируемых формул на множестве значений
Интерпретационный подход используется при экспериментальной проверке соот-ветствия программы своей спецификации

Котляров В.П. Технология индустриальногот программирования
ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ТЕСТИРОВАНИЯ
Отладка (debug, debugging) – процесс поиска, локализации и исправления ошибок в программе [IEEE Std.610-12.1990].
Отладка состоит из Ю поиска ошибок (тестирования) + исправления ошибок
Тестирование обеспечивает констатацию наличия ошибок, если ошибки имеются.
Исправление (собственно отладка) обеспечивает локализацию ошибок, нахождение причин ошибок и соответствующую корректировку программы
Если программа не содержит синтаксических ошибок (прошла трансляцию) и следовательно может быть выполнена на компьютере, она обязательно вычисляет какую-либо функцию: осуществляет отображение входных данных в выходные
Следовательно компьютер на своих ресурсах доопределяет частично определен-ную программой функцию до тотальной определенности. Т.о. судить о правиль-ности или неправильности результатов выполнения программы можно только, сравнивая спецификацию желаемой функции с результатами ее вычисления, что и осуществляется в процессе тестирования.
Тестирование разделяют на статическое и динамическое:
Статическое тестирование выявляет неверные конструкции (ошибки) без выпол-нения программы формальными методами статического (в т.ч. Синтаксического) анализа (CodeCheker)
Динамическое тестирование выявляет ошибки только в процессе выполнения программы

Котляров В.П. Технология индустриальногот программирования
ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ТЕСТИРОВАНИЯ
Организация тестирования. Тестирование осуществляется на заданном заранее множестве входных данных X и множестве предполагаемых результатов Y – (X,Y), которые задают график некоторой желаемой функции. Кроме того зафиксирована процедура Оракул, которая определяет соответствуют ли выходные данные – Yв, вычисленные по входным данным – X, желаемым результатам Y, т.е. принадлежит ли каждая вычисленная точка (x,yв) графику желаемой функции (X,Y).
Оракул дает заключение о факте появления неправильной пары (x,yв) и ничего не говорит о том, как она вычислялась или каков правильный алгоритм – он только сравнивает вычисленные и желаемые результаты. Оракулом м.б. даже Заказчик или программист производящий ручные вычисления, поскольку Оракулу нужен какой-либо другой способ получения функции (X,Y) для вычисления эталонных значений yОY.
В процессе тестирования Оракул последовательно получает элементы множества (X,Y) и соответствующие им результаты вычислений Yв для поиска несовпадений
При выявлении (x,yв) П(X,Y) запускается процедура исправления ошибки, которая заключается в внимательном анализе (просмотре) протокола промежуточных вычислений, приведших к (x,yв), с помощью следующих средств:

Котляров В.П. Технология индустриальногот программирования
ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ТЕСТИРОВАНИЯ
«выполнение программы в уме» (deskchecking),
вставка операторов протоколирования (печати) промежуточных результатов (logging),
пошаговое выполнение программы (single-step operation),
выполние с заказанными остановками (breakpoints) и анализом трасс (traces) и дампов (dump inspection),
реверсивное (обратное) выполнение (reversible execution).
Сравнение промежуточных результатов с эталонными (полученными независимо) позволяет найти причины и место ошибки, исправить текст программы, провести повторную трансляцию и настройку на выполнение и продолжить тестирование.
Тестирование заканчивается, когда достаточное в соответствии с выбранным критерием количество тестов прошло (pass) успешно.

Котляров В.П. Технология индустриальногот программирования
ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ТЕСТИРОВАНИЯ
Тестирование - процесс функционирования системы или компоненты в заранее определенных условиях с записью и анализом результатов функционирования и оценкой свойств тестируемого объекта.
[IEEE Std.610-12.1990]
[Катков В.Л, Шимаров В.А.] - контролируемое выполнение программы на конечном множестве тестовых данных и анализ результатов этого выполнения для поиска ошибок.
Три фазы тестирования:
1) составление (генерация) тестов,
2) прогон программы на тестах,
3) оценка результатов выполнения программы на тестах
Основная проблема тестирования - определение достаточности множества тестов для истинности вывода о правильности реализации программы и нахождении этого множества тестов.

Котляров В.П. Технология индустриальногот программирования
ГРАФОВАЯ МОДЕЛЬ ПРОГРАММЫ
Граф программы - G(V,A), где V(V1,… Vm) – множеств вершин (операторов), A(A1,… An) – множество дуг (управлений), соединяющих операторы-вершины
Путь – последовательность вершин и дуг, в которой любая дуга выходит из вершины Vi и приходит в вершину Vj , например: (3,4,5,9) (3,4,5,6,7,8,5,6,7,8) (3,4,5) (3,4,5,6,7,8)
1 function Z(x:real, n:int);
2 i:int
3 Z:=1
4 i:=1
5 M: if n>i then begin
6 Z:=Z*x
7 i:=i+1
8 goto M end
9 end
Ветвь – путь (V1, V2, … Vk), где V1 - либо первый либо условный оператор программы, Vk - либо условный оператор либо оператор выхода из программы, а все остальные операторы – безусловные,
например: (3,4,5) (5,6,7,8) (5,9)
Пути, различающиеся хотя-бы числом прохождений цикла – разные пути, поэтому число путей в программе м.б. не ограничено. Ветви - линейные участки программы, число ветвей конечно .

Котляров В.П. Технология индустриальногот программирования
ГРАФОВАЯ МОДЕЛЬ ПРОГРАММЫ
function H(x:real,y:real);
1 if x**2+y**2+2<=0
2 then H:=17
3 else H:=64
4 H:=H**2+x**2
Существуют реализуемые и нереализуемые пути в программе, в
нереализуемые пути нельзя попасть в обычных условиях:
H(x.y): путь (1,3,4) реализуем, путь (1,2,4) нереализуем в условиях нормальной работы, но не при сбоях

Котляров В.П. Технология индустриальногот программирования
ОСНОВНЫЕ ПРОБЛЕМЫ ТЕСТИРОВАНИЯ
Пусть программа H(x:int, y:int) реализована в машине с 64 разрядным словом, тогда мощность множества тестов ||(X,Y)||=2**128 ~ 10**38 тестов
(1GHz ; 1 тест=1ms ~ 10**32s ~ 25 лет) 1
Программа работы схвата робота:
M1: ЧтДатчика (вкл:Bool); if вкл then goto M2 else M1;
M2: ОткрытьСхват; ЗакрытьСхват; goto M1
Это тривиальный пример, имеющий бесконечное множество последовательностей входных значений
Тестирование программы на всех возможных входных значениях невозможно, невозможно и тестирование на всех путях. Следовательно надо отбирать конечный набор тестов, позволяющий хорошо проверить программу по нашим интуитивным представлениям

Котляров В.П. Технология индустриальногот программирования
ОСНОВНЫЕ ПРОБЛЕМЫ ТЕСТИРОВАНИЯ
Требование к тестам - программа на любом из них должна останавливаться, т.е. не зацикливаться.
Можно ли заранее гарантировать останов на любом тесте ?
Теория алгоритмов: Не существует общего метода для решения этого вопроса, более того и вопроса достигнет ли программа на данном тесте заранее фиксированного оператора.
Задача о выборе конечного набора тестов (X,Y) для проверки программы неразрешима в общем случае Ю ищем частные случаи решения задачи.

Котляров В.П. Технология индустриальногот программирования
КРИТЕРИИ ВЫБОРА ТЕСТОВ
Требования к идеальному критерию тестирования [Goodenough J.B., Gerhart S.L.] :
1. Критерий должен показывать, когда некоторое конечное множество тестов достаточно для тестирования данной программы.
2. Критерий должен быть полным, т.е. в случае ошибки должен существовать тест из множества тестов, удовлетворяющих критерию, который раскрывает ошибку.
3. Критерий должен быть надежным, т.е. любые два множества тестов, удовлетворяющих ему, одновременно должны раскрывать или не раскрывать ошибки программы
4. Критерий должен быть легко проверяемым, например вычислимым на тестах
Для нетривиальных классов программ в общем случае не существует полного и надежного критерия, зависящего от программ или спецификаций

Котляров В.П. Технология индустриальногот программирования
КРИТЕРИИ ВЫБОРА ТЕСТОВ
КЛАССЫ КРИТЕРИЕВ
i. Структурные критерии
ii. Функциональные критерии (опираются на описание задачи)
iii. Критерии стохастического тестирования
iv. Мутационные критерии

Котляров В.П. Технология индустриальногот программирования
СТРУКТУРНЫЕ КРИТЕРИИ (класс i)
Тестирование команд (С0, P1)- набор тестов в совокупности должен обеспечить прохождение каждой команды (каждого оператора) не менее 1 раза (используется в больших программных системах, где другие критерии не применить)
Тестирование ветвей (С1, P2)- набор тестов в совокупности должен обеспечить прохождение каждой ветви не менее 1 раза (распространен в Авт.Системах Тестир.)
Тестирование путей (С2, P∞)- набор тестов в совокупности должен обеспечить прохождение каждого пути не менее 1 раз. Если программа содержит цикл, то число итераций ограничено (часто - 2, или числом выходных классов путей)
ПРИМЕР Критерий C0 (X,Y)={(xвх=30, xвых=0)} 1-2-3-4-5-6
1 Proc PR(x:int); begin Критерий C1 (X,Y)={(30,0), (17,17)} +1-2-4-6
2 If x > 17 then Критерий C2 (X,Y)={(30,0), (17,17), (-13,0), (21,-4)}
3 x:=17-x; 2 If > Ј Ј >
4 If x= -13 then 4 If = № = №
5 x:=0; С2 проверяет программу более тщательно, чем С1,С2, но не
6 end проверяет соответствие со спецификациями, если оно не
отражено в структуре программы.
Если задано, что |x| Ј100, то операторы 3 и 5 на тесте (-177,-177) не изменят величину х=-177 и результат не соответствует спецификации.

Котляров В.П. Технология индустриальногот программирования
Пример использования структурного критерия
3 трассы 1-2-3-6-8-9-10, 1-4-6-8-9-10, 1-4-6-8-7-6-8-9-10 и 1-5-6-8-9-10, построенные по графу (UCM диаграммы), гарантируют полное покрытие ветвей и частичное покрытие путей при условии однократного прохода цикла.

Котляров В.П. Технология индустриальногот программирования
Структурный критерий для поддиаграмм
Если трассы содержат абстрактные фрагменты с описанием поведения, (например, Stub1 - 8 ), то трассы, представляющие поведение внутри элемента Stub, могут быть получены отдельно и затем добавлены в итоговую трассу с детальным поведением.
Например, поведение элемента, представленного диаграммой Stub1 описывается следующими трассами: S1-S2-S6-S7, S1-S3-S6-S7, S1-S4-S6-S7, S1-S5-S6-S7, а также идентичным набором трасс, оканчивающихся элементом S8 вместо последовательности элементов S6-S7. При подстановке детального поведения Stub1 в трассу, описывающую полное поведение системы, вход 6 в Stub1 соединяется с элементом S1, выход S7 – с элементом 9, выход S8 – с элементом 7 на рис. 3.

Котляров В.П. Технология индустриальногот программирования
ФУНКЦИОНАЛЬНЫЕНЫЕ КРИТЕРИИ (класс ii)
- Тестирование пунктов спецификаций - набор тестов в совокупности должен обеспечить проверку каждого тестируемого пункта не менее 1 раза
- Тестирование классов входных данных - набор тестов в совокупности должен обеспечить проверку представителя каждого класса (нормальных/ошибочных типов)
-- текстовые входные файлы из разных источников
- Тестирование правил - набор тестов в совокупности должен обеспечить проверку каждого правила, если входные значения описываются набором правил грамматики
-- грамматика д.б. достаточно простой
- Тестирование классов выходных данных - набор тестов в совокупности должен обеспечить проверку представителя каждого выходного класса, если результаты заранее расклассифицированы
-- проверяются в том числе ограничения на ресурсы, тайм-ауты
- Тестирование функций - набор тестов в совокупности должен обеспечить проверку каждого действия, реализуемого программой не менее 1 раза
- Комбинированные критерии для программ и спецификаций - набор тестов в совокупности должен обеспечить проверку всех комбинаций непротиворечивых условий программ или спецификаций. -- все комбинации условий надо проверить,а противоречивые обнаружить и убрать

Котляров В.П. Технология индустриальногот программирования
Пример
документа
TRS, описываю
щего требования

Котляров В.П. Технология индустриальногот программирования
СТОХАСТИЧЕСКИЕ КРИТЕРИИ (класс iii)
Тестирование сложных программных комплексов (Кпрг) - когда набор тестов (X,Y) имеет громадную мощность. Разрабатываем программы - имитаторы последовательностей входных сигналов {x}, для которых вычисляем {y}. Контолируем:
1) соответствие y=yэталонному - детерминированный случай, 2) соответствие {y} - известному распределению F(y) - стохастический случай
- Критерии прекращения стохастического тестирования
-- статистические методы принятия решений о совпадении гипотез о распределении случайных величин - St, χ2
-- модель скорости выявления ошибок [P.B.Moranda]
NC N - исходное число ошибок в Кпрг (N-1)C перед тестированием
С - константа снижения скорости выявления ошибок за счет
t1 t2 … tn нахождения очередной ошибки
t1,t2,…tn - кортеж возрастающих интервалов обнаружения ошибок,
если за T выявлено n ошибок

Котляров В.П. Технология индустриальногот программирования
СТОХАСТИЧЕСКИЕ КРИТЕРИИ (класс iii) - продолжение
Пусть за T выявлено n ошибок:
(1) (N-i+1)*C*ti = 1 – (скорость NC)*(время_выявления_i_ошибки) есть 1 по определению
(2) NCt1+(N-1)Ct2+…+(N-n+1)Ctn=n NC(t1+t2+…+tn) - C* е (i-1)ti = n
NCT - C* е (i-1)ti = n
(3) е 1/(N-i+1) = TC -- из (1) определено С*ti и просуммировано от 1 до n
(4) C = n/(NT - е (i-1)ti ) -- выражаем из (2)
(5) е 1/(N-i+1) = n/(N - 1/T* е (i-1)ti ) -- подставляем С в (3)
Оцениваем величину N приблизительно (методы оценки числа ошибок в программе), наблюдаем t1,t2…tn и по (5) находим tn+1.
Если tn+1 > Tдопустимого, то тестирование заканчиваем.
Наблюдая t1,t2…tn, T= е ti, можно прогнозировать время следующего шага и уточнять величину С.