В. В. Кулямин Институт системного программирования РАН

Введение Сложность современных систем Тестирование и связанные понятия Тестирование на основе моделей Модели поведения Модели ситуаций Методы построения тестов Работы ИСП РАН 2

Software сложнее hardware (1968) 3

4

5

6

Основная причина – сложность Среднее количество ошибок на 1000 строк кода – постоянно (???) 7

Космические аппараты Mariner I (1962) Фобос-1 (1988) Mars Climate Orbiter, Mars Polar Lander (1999) Инфраструктура AT&T long distance network crash (1990) Northeast Blackout (2003) OpenSSL rnd in Debian (2006-8) Heathrow Airport Terminal 5 baggage system (2008) Автомобили Toyota Prius (2005, 2010) Медицинское оборудование Therac-25 (1985-7) Авионика и военное оборудование Lockheed F-117 (1982) MIM-104 Patriot (1991) Ariane 5 (1996) USS Yorktown (1997) F-22 Raptor (2007) 8 Потери индустрии США в 2001 году – 60 G$

Не делать ошибок Невозможно из-за сложности Предотвращение ошибок Повышение уровня абстракции языков Устранение error-prone конструкций Стандартизация и документирование языков, интерфейсов и библиотек Выявление ошибок Верификация и валидация Тестирование на основе моделей – частный случай Исправление ошибок 9

Computer Science Алгоритм Одна четкая задача o ее м.б. невозможно решить o или можно решить идеально Можно устранить ошибки Основа – математика Фундаментальная дисциплина Электродинамика Software Engineering Система Много неясных задач o нужно решать неразрешимое o и нельзя решить окончательно Ошибки есть всегда Основа – mix (???) o Ad hoc решения o Микроэкономика o Групповая и когнитивная психология o Социология Инженерная дисциплина (???) Электротехника 10

[SWEBOK 2004] Проверка соответствия тестируемой системы требованиям Верификация Альтернативы – валидация Другие мнения (Cem Caner) – любой анализ В ходе реальной работы этой системы Альтернативы Экспертиза, статический анализ, проверка моделей (model checking) дедуктивный анализ (theorem proving) В конечном наборе специально созданных ситуаций Другие мнения (IEEE ) Альтернативы Мониторинг (runtime verification, passive testing) 11

Поиск ошибок Четкие результаты Гарантировать отсутствие ошибок нельзя Что делать, если ошибки не находятся? Когда можно прекратить тестирование? Оценка качества тестируемой системы (SUT) Объективные условия завершения Критерии полноты тестирования – как выбирать тесты Контроль развития системы Тесты – инструмент отслеживания изменений Организация тестов – как облегчить модификации 12

По проверяемым свойствам ISO 9126 o Функциональность o Надежность o Производительность Нагрузочное o Переносимость o Удобство использования Удобство сопровождения Регрессионное Аттестационное (соответствия) По исполнителю При разработке Альфа Бета Приемочное По уровню Модульное Компонентное Интеграционное Функций (features) Системное По источнику тестов Структурное «Черного ящика» «Серого ящика» На отказ o «Дымовое» o Стрессовое По интерфейсу UI API Сообщения 13

Тест – тестовая ситуация + проверка Тестовый вариант Инициализация Выполнение Проверка Финализация 14 public void testGetClients() { Session s = SessionFactory.getSession(); s.beginTransaction(); List clients = s.createQuery("from Client").list(); Client jones = new Client("Mike", "Jones"); Assert.assertContains(clients, jones "Jones should be in clients"); s.rollbackTransaction(); }

Обращение к тестируемой системе Воздействие Данные обращения Набор параллельных обращений Состояние системы Внешние условия 15 Вызов функции или метода Product.get(74291).setValue(485); Отправка сообщения Send( new ProductValueChangeMsg(74291, 485) ); Ввод команды produpd -t -id val 485 Нажатие на кнопку

Требования Модель поведения тестируемой системы (SUT) Определяет корректное и некорректное поведение Структура тестовых ситуаций Модель ситуаций, возникающих при работе SUT Определяет виды и элементы ситуаций, их важность и связанные риски Критерий полноты тестирования, критерий покрытия, метрика покрытия Тестирование на основе моделей Используемые модели заданы явно 16

Логико-алгебраические Различные логики Первого порядка, теории типов, временные, модальные, … Различные алгебраические структуры Исполнимые Различные автоматы FSM, LTS, расширенные, взаимодействующие, иерархические, временные, сети Петри, Statecharts, … Гибридные LTS ~ Алгебры процессов, модели стандартных термов Abstract State Machines Программные контракты с состоянием 17

x – 32-битное целое число abs(x) – (x 0) ? (x) : (-x) abs(x) 0 abs(– ) = Машинная целочисленная арифметика Z / 2 32 Z = {[-2 31 ], [ ], …, [-2], [-1], [0], [1], [2], …, [ ]} +, –, * (34)! = 18 ? – ? 0

x – число с плавающей точкой (double) sqrt(x) – квадратный корень pre : (x 0) post: (sqrt*sqrt = x) r = [sqrt(2)] double = /2 52 r*r = … post: abs(sqrt*sqrt – x) < ε = 3* r = [sqrt(2 105 )] double = abs(r*r – ) = post: (x = 0) (sqrt = 0) & (x 0) abs((sqrt*sqrt – x)/x) < ε 19

x – число с плавающей точкой (double) atan(x) – арктангенс post: (x = 0) (atan = 0) & (x 0) abs((tan(atan) – x)/x) < ε (tan(atan(10 50 )) = [ π /2] double = /2 49 (π /2 - [ π /2] double ) = … 10 –17 20 π /2 atan(x) π /2 [π /2] double

21 Нормализованные: E > 0 & E < 2 k –1 X = (–1) S ·2 (E–B) ·(1+M/2 (n–k–1) ) Денормализованные: E = 0 X = (–1) S ·2 (–B+1) ·(M/2 (n–k–1) ) Exceptional: E = 2 k –1 M = 0 : +, – M 0 : NaN знак k+1 n-1n-1 0 экспонентамантисса k n, k S E M B = 2 (k–1) –1 2 (–1) · = 13/16 = 0,8125 0, -0 1/0 = +, (–1)/0 = – 0/0 = NaN n = 32, k = 8 – float (single precision) n = 64, k = 11 – double n = 79, k = 15– extended double n = 128, k = 15– quadruple 1/2 (n-k-1) – 1 ulp

дает результат округления точного значения в соответствии с текущим режимом к ближайшему к +, к –, к 0 для + дает + и выставляет флаг DIVISION-BY-ZERO для -0 дает -0 (???!!!) для x < 0 дает NaN и выставляет флаг INVALID в случае неточного результата выставляет флаг INEXACT нигде не выставляет флаги OVERFLOW, UNDERFLOW 22

Расширенный конечный автомат 23 FreeLocked create() /sid; owner := null destroy() lock(tid)/ok tid ; owner:=tid trylock(tid, wt)/ ok tid ; owner:=tid [tid=owner & waiting.empty()]unlock(tid)/ok tid ; owner:=null [tid=owner]lock(tid)/locked tid [tidowner]lock(tid)/fail tid [tid=owner]trylock(tid, wt)/locked tid [tidowner]trylock(tid, wt)/timer[tid]:=wt, waiting.push(tid) timeout[tid]/fail tid ; waiting.remove(tid) [tid=owner & !waiting.empty()]unlock(tid)/ok; owner:=waiting.pop(), timer[owner]:=0 [tid=owner]unlock(tid)/ok tid ; owner:=null waiting := new Queue timer:= new TimerList

0 P Расширенная сеть Петри C (in) /x 1 :=in (in) /x 2 :=in/x 3 :=in /x 4 :=in /x1/x1 /x2/x2 /x3/x3 /x4/x4

Абстрактный тип данных L – список объектов типа E Операции empty : L insert : L N E L remove : L N L size : L N get : L E Аксиомы empty.size() = 0 [0iX.size()] X.insert(i, e).size() = X.size() + 1 [0i

Составляющие Элементы тестовых ситуаций o Действия и их наборы o Данные и состояния Классификация ситуаций и их элементов, выделение однородных областей Важность и риски Виды моделей ситуаций Доменные (на основе входных и выходных данных) Структурные (на основе затрагиваемых элементов SUT) Функциональные (на основе элементов требований) Проблемные (на основе возможных проблем и рисков, гипотез об ошибках) 26

ВариантЧисло AЧисло BA+BA+B – – 7–0 8–+ 9–– ВариантЧисло AЧисло BA+BA+B –– –+ 7+–0 8+–– 9–0– 10–++ 11–+0 12–+– 13––– ВариантЧисло AЧисло BA+BA+BВариантЧисло AЧисло BA+BA+B –+– –MAX ––– 40––20––OVR 50MIN 21–MINOVR MAX MAX+OVR MAX–+ 9+ OVR25MAX OVR 10+–+26MAXMIN– 11+–027MIN0 12+––28MIN+– 13+MIN–29MIN-OVR 14–0–30MINMAX– 15–++31MIN OVR 16–+0 ВариантМножество AМножество B A B 1 2 непусто 3непусто 4непусто 5непусто непусто = A = B 6непусто непусто = A B 7непусто непусто = B A 8непусто непусто A, B 27

S = 0 или S = 1 Денормализованные числа E = 0 M = 0 +0, –0 M , , , , Нормализованные числа 0 < E < 2 k-1 E , , , , M , , , , , Исключительные числа E = 2 k-1 M = 0 +, – M 0 NaN , , , , знак k+1 0 экспонентамантисса k S E M

29 max 0

ax 2 + bx + с = 0 int solve(double a, double, b, double c, double *x1, double *x2) 30 ВариантУсловиеЧисло решений Результат 1a = b = с = 0–1–1 2a = b = 0, с 000 3a = 0, b 011 4a 0, b 2 -4ac < 000 5a 0, b 2 -4ac = 011 6a 0, b 2 -4ac > 022 ВариантУсловиеЧисло решений Результат 1a = b = с = 0–1–1 2a = b = 0, с > 000 3a = b = 0, с < 000 4a = 0, b > 011 5a = 0, b < 011 6a > 0, b 2 -4ac < 000 7a < 0, b 2 -4ac < 000 8a > 0, b 2 -4ac = 011 9a < 0, b 2 -4ac = a > 0, b 2 -4ac > a 022

Компоненты, классы, методы Инструкции Ветвления Цепочки блоков Цепочки вызовов Элементарные условия и их комбинации 31

public Node ReplaceChild(Node nc, Node oc) { if(nc == null) throw new NullReferenceException("The new child is null"); if(oc == null || !Children.Contains(oc)) throw new DomException("Ref node is not a child of this node", NOT_FOUND_ERROR); if( !(this is Document) && nc.OwnerDocument != this.ownerDocument || this is Document && nc.OwnerDocument != this) throw new DomException("New child provided is from another document context", WRONG_DOCUMENT_ERROR); if(nc == this || Ancestors.Contains(nc)) throw new DomException("Cannot insert this node or its ancestor", HIERARCHY_REQUEST_ERROR); if(!(nc is ISPImplDocumentFragment) && !this.IsAllowedChild(nc)) throw new DomException("Cannot insert...", HIERARCHY_REQUEST_ERROR); if(this is Document && nc is DocumentType && !this.Children.Contains(nc) && this.HasDifferentChildOfType(typeof(DocumentType), oc)) throw new DomException("The second DocumentType cannot be inserted in a Document", HIERARCHY_REQUEST_ERROR); if( this is Document && nc is DocumentType && !this.Children.Contains(nc) && !this.HasDifferentChildOfType(typeof(DocumentType), oc) && HasDifferentNoncommentChildrenBefore(oldChild, newChild)) throw new DomException("DocumentType node cannot be inserted in a Document after non-comment nodes", UNKNOWN_ERROR); if( this is Document && !(nc is Comment) && !(nc is DocumentFragment) && !(oldChild is DocumentType) && HasDifferentDocumentTypeChildAfter(oldChild, newChild)) throw new DomException("Non-comment node cannot be inserted into a Document before DocumentType", UNKNOWN_ERROR); if(this is Document && nc is Element && !this.Children.Contains(nc) && this.HasDifferentChildOfType(typeof(Element), oc)) throw new DomException("The second Element cannot be inserted in a Document", HIERARCHY_REQUEST_ERROR); if(this.IsReadOnly) throw new DomException("This node is read-only", NO_MODIFICATION_ALLOWED_ERROR); if(nc.ParentNode != null && nc.ParentNode.IsReadOnly) throw new DomException("Parent of new child is...", NO_MODIFICATION_ALLOWED_ERROR); if(nc is DocumentFragment) { foreach(Node ni in nc.Children) { if(!this.IsAllowedChild(ni)) throw new DomException("Cannot insert...", HIERARCHY_REQUEST_ERROR); if(this is Document && ni is DocumentType && this.HasDifferentChildOfType(typeof(DocumentType), null)) throw new DomException("The second DocumentType cannot be inserted in a Document", HIERARCHY_REQUEST_ERROR); if(this is Document && ni is Element && this.HasDifferentChildOfType(typeof(Element), null)) throw new DomException("The second Element cannot be inserted in a Document", HIERARCHY_REQUEST_ERROR); if(this is Document && !(ni is Comment) && !(oldChild is DocumentType) && HasDifferentDocumentTypeChildAfter(oldChild, null)) throw new DomException("Non-comment node cannot be inseted into a Dcoument before DocumentType", UNKNOWN_ERROR); } } int i = this.Children.IndexOf(oc); if(!(nc is DocumentFragment) && nc != oc) { if(nc.ParentNode != null) nc.ParentNode.Children.Remove(nc); nc.parent = this; if(this.Children.Contains(nc)) this.Children.Remove(nc); this.Children.Insert(i, nc); } else if(nc is DocumentFragment) { foreach(Node ni in nc.Children) { ni.parent = this; this.Children.Insert(i++, ni); } nc.Children.Clear(); } if(nc != oc) { this.Children.Remove(oc); oc.parent = null; } return oc; } 32 УсловияВетвиКритерии покрытия abcda || !b && cc && !a || b && dDCCCD/CCMDCMC/DCSMCCMCC XXXXXXX X XXXXX X XX XXX XX X XXX X XX XX X X XXX XXXXX

DU-пары и DU-пути 33 1 int gcd(int a, int b) 2 { 3 if(a == 0) 4 return b; 5 if(b == 0) 6 return a; 7 if(a > 0 && b 0) 8 b = -b; 9 10 while(b != 0) 11 { 12 if(b > a && a > 0 || b < a && a < 0) 13 { 14 a = b-a; 15 b = b-a; 16 a = a+b; 17 } b = a-b; 20 a = a-b; 21 } return a; 24 }

Состояния Переходы Цепочки переходов Простые пути Простые циклы с продолжением

Операторы мутации if(A) B else C o if(A) B o if(A) C o if(A) C else B o B o C Программа P мутанты {P 1, P 2, …, P n } устраняем эквивалентные выполняем тесты определяем «неубитых» мутантов 35 X := Y + Z o X := Y o X := Z o X := Y – Z o Y := Y + Z

Вероятностные Комбинаторные Автоматные Нацеленные 36

Тестовые ситуации строятся на основе вероятностных распределений Модель ситуаций представляет собой распределения для различных элементов ситуаций По частоте использования По связанным рискам По отлаженности 37

Позволяет получить много тестов с минимальными затратами Хорошо автоматизируется Хорошо находятся случайные ошибки (опечатки) Полнота полученного набора тестов непредсказуема Плохо находятся серьезные ошибки Исходные распределения часто неизвестны 38 Вероятностное тестирование

Тестовые воздействия разбиваются на некоторые элементы Тестовые ситуации строятся как всевозможные комбинации этих элементов по определенным правилам Дерево классификации Тестирование на основе грамматик Покрывающие наборы Пути в автоматах 39

Во многих случаях достаточно дешево Хорошо автоматизируется Более систематично, чем вероятностное Некоторые виды ошибок находятся плохо При учете многих факторов построение набора тестов требует гораздо больше ресурсов 40 Комбинаторное тестирование

РазмерЦветаФорматПринтерБраузерОС 1 страницаНет цветных рисунков A4HPInternet Explorer Windows XP 2 страницыЕсть цветные рисунки A3EpsonMozilla FirefoxWindows Vista 7 страницA5CanonOperaLinux Ubuntu B5XeroxLinux SUSE LetterLinux RHEL 41 3·2·5·4·3·5 = 1800 вариантов

11 страницаНет цветных рисунковA4HPInternet ExplorerLinux RHEL 21 страницаНет цветных рисунковA4HPOperaWindows XP 31 страницаНет цветных рисунковA3A3EpsonInternet ExplorerWindows Vista 41 страницаНет цветных рисунковLetterCanonInternet ExplorerLinux RHEL 51 страницаЕсть цветные рисункиA5EpsonOperaLinux Ubuntu 61 страницаЕсть цветные рисункиB5HPMozilla FirefoxWindows Vista 71 страницаЕсть цветные рисункиLetterXeroxOperaLinux SUSE 82 страницыНет цветных рисунковA3A3XeroxMozilla FirefoxLinux RHEL 92 страницыНет цветных рисунковB5CanonOperaLinux SUSE 102 страницыНет цветных рисунковLetterHPMozilla FirefoxLinux Ubuntu 112 страницыЕсть цветные рисункиA4XeroxOperaLinux Ubuntu 122 страницыЕсть цветные рисункиA3A3HPOperaLinux SUSE 132 страницыЕсть цветные рисункиA5XeroxOperaWindows Vista 142 страницыЕсть цветные рисункиLetterEpsonInternet ExplorerWindows XP 157 страницНет цветных рисунковA4CanonInternet ExplorerWindows Vista 167 страницНет цветных рисунковA3A3XeroxOperaWindows XP 177 страницНет цветных рисунковA5HPInternet ExplorerLinux SUSE 187 страницНет цветных рисунковA5CanonMozilla FirefoxWindows XP 197 страницНет цветных рисунковB5HPInternet ExplorerLinux RHEL 207 страницНет цветных рисунковB5XeroxInternet ExplorerLinux Ubuntu 217 страницЕсть цветные рисункиA4EpsonMozilla FirefoxLinux SUSE 227 страницЕсть цветные рисункиA3A3CanonOperaLinux Ubuntu 237 страницЕсть цветные рисункиA5EpsonOperaLinux RHEL 247 страницЕсть цветные рисункиB5EpsonOperaWindows XP 257 страницЕсть цветные рисункиLetterEpsonInternet ExplorerWindows Vista вариантов Покрытие пар – покрывающий набор силы 2 Можно построить комбинации всех троек – покрывающий набор силы 3 – 100 вариантов

Покрывающий набор силы t для k параметров, имеющих значения n 1, …, n k – матрица {С ij } i [1..N], j [1..k], C ij [1..n j ] j1, …, jt jl [1..k] v j1, …, v jt v jl [1..n jl ] i [1..N] l [1..t] С ijl = v jl множество таких наборов – CA(t; n 1, …, n k ) Однородные наборы – n 1 = … =n k =n, CA(t; k, n) Минимальное число строк в однородном наборе – ~tn t log 1+ (k) Построение минимальных однородных наборов из CA(t; k, 2) или CA(2; k, n > 2) – NP-полная задача 43

Алгоритм построения CA(2; k, 2) Выбрать N : k C N-1 N/2 Можно построить набор из N строк 44 kN

Алгоритм построения CA(2; p k +1, p k ) n=p k, p – простое Первый столбец ()– блоки по n одинаковых значений i Второй столбец (0) – все n значений j в каждом блоке В столбце с номером m 1..(n-1) (i*m+j) в поле GF(p k )

Алгоритм построения CA(2; mn+1, n=p k ) из CA(2; m, n) Исходный набор {A ij } i [1..N], j [1..m] Вспомогательная матрица {B ij } i [1..z=(n 2 -n)], j [1..(n+1)] 46 nn … n N 0A 11 … A 12 … …A 1m … 0A 21 … A 22 … …A 2m … …………………………………… 0A N1 … A N2 … …A Nm … z B 11 B 12 … B 13 … …………B 1(n+1) … …………………………………… B z1 B z2 … B z3 … …………B z(n+1) … mm…………m

Неоднородные Переменной силы С ограничениями на сочетания значений Переборно-оптимизационные алгоритмы 47

Тестовые ситуации, определяемые критерием полноты, строятся прямо 48 Источники выделяемых ситуаций Разбиения на классы эквивалентности Ограничения на элементы ситуаций Граничные случаи Риски Функции системы Длинные сценарии использования

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

Разрешение ограничений Перебор данных с проверкой попадания в нужную ситуацию Использование решателей (SMT-solvers) Оптимизационные алгоритмы 50

Всегда ли реализация ведет себя как спецификация? Спецификация a/x b/y b/x b/y a/ya/x 0 12 Реализация a/x b/y b/x b/y a/ya/x

Требования к спецификации Детерминизм Полная определенность Минимальность Сильная связность или наличие reset (R) Гипотезы о реализации Реализация – конечный детерминированный автомат с теми же стимулами I и реакциями O Полная определенность Сильная связность или наличие reset (R) В начале находимся в начальном состоянии Число состояний ограничено 52

Покрывающее множество C Пример: C = {, b, bb} Различающая последовательность d Есть не всегда, м.б. экспоненциальной длины Пример: d = ab (0 xy, 1 xx, 2 yy) a/x b/y b/x b/y a/ya/x D-метод (не всегда применим, экспоненциален) {R}CI N–n+1 {d} Пример: RaabRbabRbaabRbbabRbbaabRbbbab Характеристическое множество W Есть всегда, строится за O(pn 2 ) Пример: W = {a, b} или {ab} W-метод (применим всегда, сложность O(pn 3 )) {R}CI N–n+1 W Пример: RaaRabRbaRbbRbaaRbabRbbaRbbbRbbaaRbbabRbbbaRbbbb

Недетерминизм Неполная определенность Различные тестовые возможности Модели – Labeled Transition Systems (LTS) Сложные отношения согласованности Теория разработана плохо – нет финитных моделей ситуаций 54

Разработка тестов и тестирование Операционные системы реального времени Базовые библиотеки Linux (Linux Standard Base) Протоколы IPv6, Mobile IPv6, IPsec Отдельные модули компиляторов Intel Микропроцессоры архитектуры MIPS Создание технологий и инструментов Тестирование на основе моделей (UniTESK) Проверка соответствия стандарту LSB 55

56 Тестируемая система Модель состояния + оракул Модель поведения Генератор воздействий Метрика покрытия 12% Модель ситуаций 36%57%87% Модель состояния

57 постусловие specification class SqrtSpecification { specification static double sqrt(double x) reads x { pre { return x >= 0; } post { if(x == 0) { branch "Zero argument"; return sqrt == 0; } else { branch "Positive argument"; return sqrt >= 0 && Math.abs((sqrt*sqrt-x)/x < epsilon; } specification double SQRT(double x) reads (double)x { pre { return x >= 0.; } coverage ZP { if(x == 0.) return (ZERO, "Zero argument"); else return (POS, "Positive argument"); } post { if(coverage(ZP, ZERO)) return SQRT == 0.; else return SQRT >= 0. && abs((SQRT*SQRT - x)/x) < epsilon; } сигнатура операции предусловие ограничения доступа ветви функциональности

58 состояния параметрыобласть определения операции цели покрытия

59 Модель ситуаций Модель поведения Структуры данных Инварианты Пред- и постусловия Операции и события Варианты исполнения Виды состояний Модель состояния Обходчик автоматов Оракулы Виды параметров Генератор Итераторы данных Описание автомата ДействияСостояния Метрика покрытия Тестируемая система Генерация тестовой последовательности на лету Предусловия Постусловия

60 s 11 Тести- руемая система s 21 s 12 s 31 Несколько последовательностей воздействий Частично упорядоченное множество событий Семантика чередования – это множество должно вытягиваться в последовательность r 12 r 22 r 11 r 21 Время Время

Модель ситуаций Модель поведения Типы данных Инструкции Модель исполнения Структура процессора Варианты исполнения Шаблоны Эквива- лентность Алгоритм обработки Блоки и связиЦелевой язык Ограничения сложности Комбинации 61 Тестовые программы Зависимости Модель исполнения Итератор комбинаций Итератор зависимостей Итератор ситуаций Привязка инструкций Генератор Итераторы данных

62