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

Тестовий набор, побудований на основі технік тест дизайну, досягає покриття 60-75% операторів коду і 40-60% операторів вибору (операторів циклу, умовних операторів тощо), у той самий час як тестовий набір, побудований без залучення певних технік досягає покриття 30% операторів коду і лише 20% умовних операторів[4]

Аналіз граничних значень

Мета техніки аналізу граничних значення зосередити зусилля на потенційних помилках, що допущені на границях умов (наприклад, розробник міг вказати >, коли необхідна вимога > або =).

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

Рис. 1.5 Техніка аналізу граничних значень

Тестовий набір, побудований за даною технікою, для діапазонів зображених на рис. 1.5, повинен включати тести на перевірку значень 0,1,99,100.

Розбиття на еквівалентні класи

За цим методом уся область вхідних (вихідних) даних розділяється на класи даних, з припущенням, що всі представники одного класу оброблюються додатком однаково. Цей метод використовується для досягнення двох цілей:

· зменшення тестових випадків у наборі

· для вибору правильних тестів, що покривають усі можливі сценарії

Один тест значення взяв з кожного класу під час тестування.

Рис. 1.6 Техніка розбиття на еквівалентні класи

Тестовий набір для вимог на рис. 1.6, побудований за цією технікою повинен містити тести на перевірку значень -1 (лівий діапазон некоректних даних); 25 (діапазон коректних даних); 105 (правий діапазон некоректних даних).

Зазвичай техніки аналізу граничних значень і розбиття на еквівалентні класи використовуються у комбінації.

Діаграма станів і переходів

Діаграма станів та переходів використовується там, де аспекти системи можуть бути описані як скінчений автомат. Це означає, що система може перебувати в (скінченому) числі різних станів, і переходи з одного стану в інший визначаютьс правила «машини». На основі моделі скінченого автомату будуються тести.

Перевагами такого підходу є те, що в ньому перераховуються всі можливі комбінації станів - переходів, а не тільки ті, що є правильними: тестування неправильних шляхів використовується для додатків з високими ступенями ризику.

Створення подібної діаграми часто робить очевидними такі комбінації, які не були визначені, задокументовані, або розглянуті у неформальних вимогах. Це дуже вигідно для виявлення дефектів до початку безпосереднього створення коду.

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

Третя підзадача для роботи - побудова тестів на основі формальної моделі.

Формування тестових наборів. Тестові набори являються собою послідовність тестів, яка формується з урахуванням необхідного рівня тестового покриття. Тести в наборі не повинні дублювати перевірки, однак сформований набір повинен повністю задовольняти встановлену метрику якості робіт.

Остання під задача - формування тестового набору.

Таким чином загальна задача дослідження - автоматична генерація функціональних тестів для додатків з графічним інтерфейсом для ручного виконання може бути декомпозована на наступні під задачі:

Пошук формальної моделі для представлення вимог. Вимоги до цільової системи, що є сформульовані на природній мові, повинні бути перетворені у таке представлення, яке може бути оброблено машиною.

Визначення повноти тестового покриття. Повнота тестового покриття необхідна для того, щоб зрозуміти, коли число тестів у наборі є достатнім, щоб завершити його побудову.

Побудова тестів на основі моделі. Вибір техніки для побудови тестів на основі формальної моделі.

Формування тестового набору. Розробка алгоритму формування тестового набору.

РОЗДІЛ 2. ОБГРУНТУВАННЯ ПІДХОДУ

2.1 Формальні модель представлення вимог

Формальне представлення функціональних вимог перетворює їх на «машино читаємі», тобто створює передумови повністю автоматизувати процес генерації тестів на їх основі.

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

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

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

Логіко-алгебраїчні моделі. При моделюванні ПЗ модель такого типу описує деякий набір його властивостей, які можуть змінюватися з часом, але не дає точного уявлення про те, за рахунок чого змінюються ці властивості. Відмінність між логічним та алгебраїчним численням досить умовне, але, дещо спрощуючи, можна вважати, що логіка має справу з твердженнями в рамках якоїсь мови, а алгебра - з рівностями та нерівностями, які побудовані в деякій мові виразів. У першому випадку основним об'єктом уваги є твердження, хибні або істинні, а в другому - вирази або терми, пов'язані з якимось типом.

Приклади логічних числень такі:

Обчислення висловлювань. У ньому є атомарні висловлювання, які можливо залежать від об'єктних змінних, а також логічні зв'язки («і», сполучення), («або», диз'юнкція), («не», заперечення), => («отже», імплікація), = (еквівалентність), за допомогою яких можна з одних висловлювань будувати інші, більш складні.

Обчислення предикатів додає перелік висловлювань можливість використовувати квантори по об'єктним змінним для побудови нових тверджень. Квантори в цьому обчисленні бувають двох видів - «загальності» та «існування». У численні предикатів крім об'єктних змінних є функціональні і предикатні. Перші являють собою різноманітні функції, результат застосування функції до об'єкта - об'єкт. Другі невизначені твердження, результатом їх застосування до об'єкту має бути або «true», або «false» . У не типізованому обчисленні всі об'єкти рівноправні, функції та предикати можуть приймати будь-які об'єкти в якості аргументів. У типізованих численнях кожен об'єкт має тип, а функціональні і предикатні змінні - сигнатуру, тобто список типів параметрів і тип результату для функцій. Відповідно, будувати формули можна лише дотримуючись відповідності типів параметрів типам виразів, які підставляють на місце цих параметрів.

Обчислення предикатів більш високих порядків. У цих обчисленнях можна використовувати квантори не тільки по об'єктним змінним, але і по функціональним або предикативним. Наприклад, визначення рівності об'єктів іноді формулюється так: , два об'єкти рівні, якщо будь-яке твердження одночасно виконано або не виконано для них обох.

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

Приклади алгебраїчних моделей:

Реляційні алгебри, що лежать в основі реляційних систем управління базами даних.

Алгебраїчні моделі абстрактних типів даних.

Алгебри процесів. Це алгебраїчні обчислення, об'єктами яких є події та процеси, що створюють події або реагують на них. Зазвичай для процесів визначені операції послідовної (';') і паралельної ('||') композиції і операція вибору з двох альтернатив (альтернативна композиція, '+'). Послідовна композиція процесів моделює виконання спочатку першого з них, потім другого. Паралельна композиція моделює паралельне виконання обох процесів. Вибір з двох процесів моделює виконання або першого, або другого. У більшості таких числень процеси можуть взаємодіяти, обмінюючись подіями (один процес породжує подію, інший або інші його споживають). Найбільш широко відомі обчислення процесів CSP (Communicating Sequential Processes), CCS (Calculus of Communicating Systems).

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

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

Кінцевий автомат являє собою систему з кінцевою множиною станів. В кінцевому автоматі визначено певний набір переходів між станами.

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

Ієрархічні автомати дозволяють визначати переходи з групи станів (але кінцевий стан такого переходу має бути лише один). Крім того, в ієрархічних автоматах можуть бути групи паралельних станів - кілька груп станів, що об'єднуються в паралельне сімейство.

Тимчасові автомати - зазвичай це розширені автомати, що містять додатковий набір змінних-таймерів, значення яких змінюються самі по собі з плином часу. Значення таймерів можна використовувати в умовах переходів, зміну змінних або значеннях параметрів реакцій. Крім цього, таймери можна запускати в діях, пов'язаних з переходами. Запущений таймер починає відлік часу з 0. Час може бути дискретним чи безперервним, що дозволяє моделювати поведінку різноманітних систем реального часу.

Гібридні автомати застосовувані для моделювання систем, що взаємодіють з безперервними фізичними процесами. У цих автоматах частина змінних зазвичай має значення, зміна яких описується системою диференціальних рівнянь

Широке використання операційних моделей пов'язано з їх наступними перевагами:

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

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

Моделі проміжного типу мають риси як логіко-алгебраїчних, так і операційних. Основні їх види такі.

Логіки Хоара є специфічним видом логік, затвердження яких складаються з формул логіки деякого виду та програмних команд. У найпростішому вигляді це трійки {Q} S {R}, де S - частина програми на певній мові, а Q і R - формули обчислення висловлювань, що залежать від змінних, що входять до S. Q інтерпретується як умова, виконання перед початком виконання S (передумова), а R - як умову, що має виконуватись після виконання R (післяумови). Якщо R дійсно завжди істинне після виконання S у стані, де істинно Q, така трійка теж вважається дійсною і має назву «трійка Хоара». У логіці Хоара для деякої мови програмування, семантика цієї мови задається у вигляді правил виведення, які дозволяють з тавтологій виводити крок за кроком істинні трійки Хоара.

Узагальненням логік Хоара є динамічні чи програмні логіки. Вони є спеціальним типом модальних логік, в яких оператори модальності пов'язані з інструкціями програм. Зазвичай використовуються оператори [S] і <S>, де S - деяка програма. Твердження [S]Q означає, що завжди після виконання програми S формула Q істинна, а <S> Q - що після виконання S, Q може виявитися істинною. Трійка Хоара {Q} S {R} може бути представлена ??у динамічній логіці як Q=>[S]R.

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

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

Вибір на користь скінченого автомату зумовлений тим, що побудова логіко - алгебраїчних та проміжних моделей практично не вигідна в силу величезних витрат на розробку додаткових аксіом, тверджень та умов(передумов) та післяумов, що визначають заключні правила отримання правильного результату.

2.2 Скінчений автомат

Скінчений автомат (finite state machine) - модель для специфікації поведінки об'єкта у формі послідовностей його станів, які описують реакцію об'єкта на зовнішні події, виконання об'єктом дій, а також зміна його окремих властивостей.

Скінчений автомат є математичною абстракцією в теорії алгоритмів, що дозволяє описувати шляхи зміни стану об'єкта в залежності від його поточного стану і вхідних даних, за умови, що загальна можливу кількість станів скінчене. У процесі роботи скінченого автомату відбувається послідовна зміна скінченого числа його внутрішніх станів, причому стан автомата в певний момент часу однозначно визначається вхідним і вихідним сигналами. Такі автомати являють собою основу всієї сучасної обчислювальної техніки і всіляких дискретних систем автоматичного контролю і управління.

Два типи автоматів:

Автомат Мілі - скінчений автомат, вихідна послідовність якого залежить від стану автомата і вхідних сигналів.

Автомат Мура - скінчений автомат, для якого функція виходів визначає значення вихіденого символу лише за одним аргуметом - станом автомату.

Поширені три способи завдання скінченого автомату:

· Аналітичний

· Табличний

· Графічний

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

Аналітично скінчений автомат визначається наступною сукупністю параметрів:

(2.1)

де:- скінчена множина станів автомату;

- елемент множини S, початковий стан автомата,;

- скінчена множина, елементи якої називаються вхідними символами, входами або стимулами, саме I називають вхідним алфавітом автомата; О - скінчена множина, елементи якого називаються вихідними символами, виходами або реакціями, саме O називають вихідним алфавітом автомата.

- відображення типу , функція переходів.

- відображення типу , функція висновків.

Для автомату Мілі наступні рівняння, формули (2.2) - (2.3), характеризують залежність між множинами S, I, O та абстрактним часом :

 (2.2)

(2.3)

Особливістю автомату Мілі є те, що функція висновків приймає два аргументи.

Для автомату Мура функція переходу залежить від одного параметру:

(2.4)

Табличний спосіб. Наступні дві таблиці використовуються для задання скінченого автомату Мілі - матриця переходів і матриця висносків.

		...

Рис. 2.1 Таблиця переходів автомату Мілі

		...

Рис. 2.2 Таблиця виходів автомату Мілі

Для завдання автомату Мура у табличний спосіб достатньо однієї таблиці.

		...

Рис. 2.3 Сумісна таблиця автомату Мура

де - вихідний сигнал, що відповідає стану , розташований над ним.

Графічний спосіб передбачає завдання скінченого графу у вигляді орієнтованого графу.

1. Множина S представлена вершинами графу.

2. Функція задана дугами графу, при чому вершини та з'єднані дугою, якщо існує перехід із стану в стан .

3. Множина I зображена позначками дуг, позначка ставиться над дугою, що з'єднує вершини та , якщо перехід зі стану в стан існує і має місце під впливом вхідного сигналу .

4. Функція задана позначками дуг або вершин: для автомату Мілі дуга з вершини у вершину позначається вихідним сигналом , якщо перехід зі стану в стан існує і при цьому має місце вихідний сигнал ; для автомату Мура вихідним сигналом познається вершина, що визначається як



Рис. 2.3 Представлення автоматів Мілі і Мура у вигляді орієнтованого графу

У загальному випадку скінчений автомат представляє динамічні аспекти системи. При цьому поведінка моделюється як послідовне переміщення по графу станів від вершини до вершини по дугам, що їх зв'язують, з урахуванням їх орієнтації.

Вибір скінченого автомату для моделювання програмного забезпечення у контексті даної задачі зумовлений тим, що він представляє собою своєрідний «чорний ящик» - на який подаються вхідні сигнали і з якого приймаються вихідні. «Чорного ящику» є досить, щоб перевірити поведінку додатку, тобто виконати його функціональне тестування.

2.3 Діаграма станів і переходів

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

Ідея візуального представлення володіє істотними перевагами, найсуттєвішим з яких є можливість застосування теорії графів. Це дозволить використовувати апробований апарат, що розробляється із часів Ейлера по наші дні, для представлення потоків даних і змін станів.

Діаграма станів і переходів являє собою орієнтований граф формула (2.5).

(2.5)

Який задано неперетинаючимися множинами: множиною вершин V і множиною дуг E і двома функціями інцендентності і , що визначають для кожної дуги її початкову та кінцеву вершини. Граф є скінченим, якщо множини V і E.

Наступні теоретичні відомості про орієнтований граф будуть використані при подальшому розвязку задачі дослідження:

Функції і р визначають відношення суміжності дуг - формула (2.6).

(2.6)

Маршрутом Р називається послідовність суміжних дуг графу така, що при .

Граф будемо називати детермінованим, якщо всі виходящі з нього дуги нееквівалентні.

Оскільки графом буде модельовану еталон реальної системи, для якої перехід однозначно визначає зв'язка <стан, вхідний символ>, недетерміновані графи не становлять елемент дослідження.

2.4 Повнота тестового покриття

Представлення еталонної моделі продукту у вигляді скінченого автомату зводить задачу до побудови тестів на основі обраної моделі.

Природним критерієм повноти тестового покриття при тестуванні автоматів є покриття всіх переходів автомата, що є більш сильною умовою ніж покриття усіх станів.

Більш сильним критерієм є вимога, щоб принаймні одне випробування охоплювати кожну послідовність з N переходів, . Такий підхід називається «N-1 покриттям переходів», тобто якщо тестовий набір покриває усі переходи довжиною одна транзакція, то це «0-е покриття переходів» або просто покриття переходів.

У такому випадку найслабше покриття (всіх станів і переходів) - «0-е покриття переходів»; усіх пар транзакцій - «1-е покриття переходів»; послідовностей з трьох переходів - «2 покриття переходів».

Щоб уникнути комбінаторного вибуху станів і зайвої складності тестування, можливі події будуть розглядатись незалежно одна від одної і покриття можливих комбінацій не враховується, тобто за критерій повноти обрано 0-е покриття переходів.

2.5 Побудова тестів

Задача побудови тестового набору розпадається на дві підзадачі: побудова усіх маршрутів(тестів) на графі і формування тестового набору.

Задача побудови усіх можливих тестів зводиться до математичної задачі побудови всіх маршрутів на графі:

(2.7)

Де F - множина кінцевих вершин.

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

 (2.8)

Де обмеження, що гарантує, що кожна вершина буде пройдена не більше двох разів одним маршрутом. Таким чином гарантується скінченність набору шляхів для графів із циклами, а з урахуванням області застосування - відкинуто буде такі ситуації, які на практиці майже не зустрічаються.

Для побудови усіх маршрутів на графі використовується рекурсивний алгоритм, що є розширенням алгоритму пошуку в глиб.

procedure ПОБУДОВА_МАРШРУТУ(: вершина, accumulator: накопичувач вершин маршруту); begin

if v - фінальна вершина графу, додати її до accumulatorі, зберегти шлях у колекцію, return.

if не існує вихідних ребер з вершини v - return.

if v відвідана більше двох разів - return

else додаємо вершину до accumulator, збільшуємо лічильник відвідування вершини на 1.

while Існують не пройдені ребра графу з вихідною вершиною v

Отримати кінцеву вершину v1 дуги, що з'єднана ребром з вершиною v

ПОБУДОВА_МАРШРУТУ ( v1, accumulator)

end

Видаляємо вершину з accumulator. Зменшуємо на одиницю кількість відвідувань даної вершини у шлуху.

end.



Рис. 2.4 Блок-схема алгоритму побудови всіх маршрутів на графі

2.6 Побудова тестового набору

Побудова тестового набору передбачає віднаходження такої множини , яка забезпечує покриття всіх переходів модельного графу - формула

(2.9)

де T- множина усіх тестів (шляхів графу),

R - результуючий тестовий набір,

- покриття графу G, що досягається набором шляхів R,

- покриття графу G, що досягається набором шляхів T.

такого що є розв'язком задачі оптимізації

Тестовий набір будується з використанням жадібного алгоритму.

Жадібний алгоритм дозволяє отримати оптимальне рішення задачі шляхом здійснення ряду виборів. У кожній точці прийняття рішення в алгоритмі робиться вибір, який в даний момент виглядає найкращим.

У записі алгоритму використовуються наступні умовні позначення:

| S | - потужність множини S

- довжина тесту t, яка вимірюється у кількості тестових впливів

{} - Порожня множина

<> - Порожній упорядкований список

Фіксуємо обмеження довжини тестів M, яке є параметром даного алгоритму. Вважаємо множина непокритих тестових ситуацій C: = повний набір доступних транзакцій, безліч доступних тестів T: = повний набір раніше побудованих тестів, а тестовий набір R :=<>.

Для кожного тесту t з T обчислюємо Cov (t): = безліч тестових ситуацій з C, що покриваються ім. Якщо Cov (t )={}, то видаляємо t з T.

procedure ПОБУДОВА_ТЕСТОВОГО НАБОРУ(M: максимальна довжина кроків тесту, P: вага допустимого перевищення максимальної довжини на користь покриття ); begin

оглушаємо кращим

for кожного тесту з множини тестів Т

if , а , то тест кращий

if і , однак то тест кращий

if , то тест кращий

if , то тест кращий

if , і , а то тест кращий. Додаємо знайдений кращий тест у набір R. Видаляємо із безлічі непокритих ситуації С всі елементи множини .

end

end;

Перше правило - формула (2.10) гарантує, що в першу чергу всі можливі тестові ситуації будуть покриватися тестами з довжиною, що не перевищує максимальну.

&& (2.10)

Друге правило - формула (2.11) вибирає тести з максимально можливим (в межах обмеження довжини) тестовим покриттям - у більшості випадків ця евристика дозволяє зменшити сумарну довжину тестів в наборі за рахунок зменшення їх кількості.

&& && (2.11)

Трете і четверте правила - формули (2.12) та (2.13) відповідно, віддають перевагу тестам, що поліпшують покриття або довжину і не погіршує притому іншу з цих двох характеристик.

if && (2.12)

if && (2.13)

Згідно з п'ятим правилом - формула (2.14) з двох тестів, що перевищують максимальну довжину, один краще іншого, якщо збільшення довжини компенсується (з урахуванням вагового параметра P) збільшенням покриття.

&& && (2.14)

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

Для настройки алгоритму використовуються параметри M і P.

M: задає максимальну довжину тестів набору, що генерується, перевищення якої допускається тільки для покриття недосяжних іншими способами тестових ситуацій. Допустимі значення: ціле позитивне число або + ?.

P: задає вагу перевищення максимальної довжини тестів по відношенню до підвищення покриття. При великих значеннях параметра алгоритм в першу чергу вибирає з тестів, що перевищують максимальну довжину і додають хоча б якесь тестове покриття, самі короткі, що дозволяє зменшити максимальну довжину тестів, але може приводити до істотного збільшення сумарної складності тестового набору; при малих значеннях алгоритм в першу чергу вибирає тести, що покривають більшу кількість тестових ситуацій, що дозволяє мінімізувати сумарну складність тестового набору за рахунок додавання в нього дуже довгих тестів. Допустимі значення: невід'ємні числа (можна нецілі).

Оптимальні значення обох параметрів залежать від розміру і структури графа станів документа, від вимог до тестового покриття й від можливостей тестувальників виконувати довгі тести. У ході апробації алгоритму встановлено, що в більшості випадків оптимальне значення для параметра M трохи перевершує довжину найдовшого можливого в графі маршруту без циклів, що веде з початкового стану в кінцеве, а для параметра P лежить в діапазоні



Рис. 2.5 Блок-схема алгоритму побудови всіх маршрутів на графі

РОЗДІЛ 3. ГЕНЕРАТОР ТЕСТОВОГО НАБОРУ

3.1 Логіка додатку

Додаток повинен реалізувати наступну функціональність для користувача:

Користувач будує діаграму станів і переходів для продукту, що необхідно перевірити.

Користувач запускає додаток, надаючи йому на вхід множину ребер графу переходів.

Система будує усі шляхи графа (множину тестових випадків).

Система будує тестовий набір, користуючись заданим критерієм покриття.

Користувач спів ставляє id станів їх описанню на природній мові, отримуючи таким чином тестові випадки для перевірки цільової системи.

3.2 Вибір середовища

Вибір мови програмування для розв'язання поставленої задачі був зроблений на користь С++. C++ -- дуже потужна мова, що налічує засоби створення додатків практично будь-якого призначення від низькорівневих утиліт і драйверів до складних програмних комплексів най різноманітнішого призначення.

Об'єкт - орієнтованість. С++ надає можливості створення і маніпулювання об'єктами, тобто оперування високорівневими абстракціями даних мови предметної області, а не мови комп'ютеру. Хороші абстракції дозволяють користувачам використовувати об'єкт у відносно безпечної та наперед заданий спосіб.

Мультіпарадигмовість. Підтримуються різні стилі та технології програмування, включаючи традиційне директивне програмування, ООП, узагальнене програмування, метапрограмування (шаблони, макроси).

Механізми звільнення пам'яті. Автоматичний виклик деструкторів об'єктів при їх знищення, причому в порядку, зворотному викликом конструкторів. Це спрощує (досить оголосити змінну) і робить більш надійним звільнення ресурсів (пам'ять, файли, семафори тощо), а також дозволяє гарантовано виконувати переходи станів програми, не обов'язково пов'язані зі звільненням ресурсів (наприклад, запис у журнал).

Перевантаження операторів. Користувальницькі функції-оператори дозволяють стисло і ємко записувати вирази над користувача типами в природному алгебраїчній формі.

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

Розширення. Можливість імітації розширення мови для підтримки парадигм, які не підтримуються компіляторами безпосередньо. Наприклад, бібліотека Boost.Bind дозволяє пов'язувати аргументи функцій.

Кроссплатформенность. Стандарт мови накладає мінімальні вимоги на ЕОМ для запуску скомпільованих програм.

Ефективність. Мова спроектований так, щоб дати програмістові максимальний контроль над усіма аспектами структури і порядку виконання програми. Жодна з мовних можливостей, що призводить до додаткових накладних витрат, не є обов'язковою для використання - при необхідності мова дозволяє забезпечити максимальну ефективність програми.

3.3 Бібліотеки Boost

Boost є зібранням бібліотек, що розширюють С++. Вільно розповсюджуються за ліцензією Boost Software License разом із вихідним кодом.

У даній роботі використовується версія 1.41, на сьогоднішній день найостаннішою версією є 1.46.1 (12.03.2011). Наступні бібліотеки було задіяно:

GRAPH

Бібліотека Boost.Graph надає доступ до структури графу, але приховує деталі його реалізації. Бібліотека пропонує два класи для представлення графу: adjacency_list та adjacency_matrix, і накопичувач для списку ребер edge_list.

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

Adjacency_matrix класу зберігає ребра матриці (де | V | є числом вершин). Елементи цієї матриці представляють ребер у графі. Матриця суміжності подання особливо добре підходить для дуже щільних графіків, тобто ті, де число ребер .

Edge_list клас адаптер, який приймає будь-які ітератор ребер і реалізує список ребер графу.

FOREACH

Бібліотека містить макрос BOOST_FOREACH, який перебирає (ітерує) послідовність. Послідовністю може виступати STL контейнер, масив, пара літераторів(std::pair of iterators).

LEXICAL_CAST

Бібліотека, що визначає функцію lexical_cast.

Шаблон функції lexical_cast пропонує зручний і послідовній спосіб для підтримки загальних перетворень в або з довільного типу, коли вони представлені у вигляді тексту.

3.4 Структура додатку: Класи

Клас graph_coverage

Клас graph_coverage являє собою абстракцію покриття модельного графу. Він містить контейнер з ребрами та відповідним кожному ребру булевою змінною, що містить інформацію про те, чи покрите ребро чи ні. Об'єкт класу graph_coverage використовується під час побудови тестового набору.

Рис. 3.1 Діаграма класу graph_coverage

#include <graph_coverage.h>

Реалізовані наступні методи класу:

graph_coverage<Graph>(const Graph & graph)

Конструктор класу, створює об'єкт - абстракцію покриття графу і ініціалізує значення покриття кожного ребра графу graph як FALSE (непокрите).

aditional_coverage_for_path(std::list<size_t> path) const

Функція повертає додатне число типу size_t, якщо шлях pathпокриває хоча б одне досі непокрите ребро, і 0 - у протилежному випадку.

fully_covered() const

Функція повертає булеве значення. TRUE, якщо кожне ребро модельного графу покрито шляхами(тестами), що увійшли до результуючого набору, і FALSE - у протилежному випадку.

add_coverage_for_path(const std::list<size_t>& path)

Функція помічає всі вершини, що зустрічаються у шляху path як покриті.

Клас edge_id

Об'єкт класу edge_id містить унікальне описання ребра графу, яким слугують його початого і цільова вершини.

Рис. 3.2 Діаграма класу edge_id

#include "edge.h"

edge_id(size_t vertex_source, size_t vertex_target)

Конструктор класу, ініціалізує m_vertex_source та m_vertex_target значеннями переданих параметрів.

Клас Graph

Клас є синонімом класу boost::adjacency_list і використовується для представлення модельного графу.

#include <boost/graph/adjacency_list.hpp>

Наступні методи із тих, що пропонує клас boost::adjacency_list було використано під час реалізації додатку:

out_edges(vertex_descriptor u, const adjacency_list& g)

Повертає пару літераторів, що ітерує діапазон ребер, що виходять вершини u графу G.

target(edge_descriptor e, const adjacency_list& g)

Функція повертає значення типу vertex_descriptor, що є значенням кінцевої вершини ребра e графу g.

num_vertices(const adjacency_list& g)

Функція повертає кількість вершин графу g.

vertex(vertices_size_type n, const adjacency_list& g)

Функція повертає n-у вершину графу g.

3.5 Структура додатку: Методи

Основні функцій, що використовують при розв'язанні задачі:

read_values_in_set<T>(std::istream & input, size_t values_count, std::set<T>* result)

Функція, що читає із вхідного потоку input, values_count кількість ребер, що представлені парами вершин і зберігає їх у контейнер result.

output_test(const std::list<size_t>& path_accumulator, std::ostream & output)

Функція, що виводить у вихідний потік output шлях на графі(тест), що міститься у path_accumulator.

save_to_collection(const std::list<size_t>& path, std::list<std::list<size_t>>& pathes_collection)

Функція поміщає шлях path, у лист pathes_collection - фінальний набір тестів.

trace_graph<BoostAdjacencyList, VertexDescriptor>(const BoostAdjacencyList & graph, const VertexDescriptor & current_vertex, const std::set<size_t>& final_vertices, std::list<size_t>& path_accumulator, std::vector<int>& visits_count_vector, std::list<std::list<size_t>>& pathes_collection)

Функція, що реалізує алгоритм побудови всіх маршрутів на графі із заданим обмеженням (відвідування однієї вершини не більше двох разів). Результат поміщається у pathes_collection. Функція рекурсивна.

Параметрами виступають модельний граф graph, поточна вершина current_vertex, множина кінцевих вершин графу final_vertices, контейнер для шляху, що будується path_accumulator, visits_count_vector - вектор, в якому міститься інформація про кількість відвідування поточної вершини, pathes_collection - тестовий набір, контейнер, в який буде поміщено path_accumulator, коли буде досягнуто одну з вершин множини final_vertices.

read_case(Graph & states_graph, std::set<size_t>& final_states)

Функція, що відповідає за отримання усіх вхідних даних для генерації тестового набору, а саме - значення кількості вершин модельного графу, значення кількості кінцевих вершин, множина кінцевих вершин і множина ребер графу.

generate_all_tests(const Graph & states_graph, const std::set<size_t>& final_states, std::list<std::list<size_t>>& tests_collection)

Функція, яка через виклик функції trace_graph(), будує усі шляхи на графі.

choose_best_tests(const size_t M, const double P, const Graph& states_graph, const size_t states_count, std::list<std::list<size_t> >& tests_collection, std::list<std::list<size_t> >& best_tests)

Функція, що реалізує алгоритм побудови тестового набору. Вхідні параметри: M - максимальна довжина переходів у тесті, P - вага допустимого перевищення довжини тесту на користь покриття, states_graph - модельний граф, states_count - кількість станів модельного графу states_graph, tests_collection - повний набір тестів, що побудовано у результаті роботи функції generate_all_tests(),best_tests - контейнер, що містить результуючу тестову послідовність.

3.6 Інтерфейс додатку та параметри запуску

Додаток має консольний інтерфейс.

Реалізована функціональність слугує демонстрацією розробленого підходу, а обсяги її взаємодії з користувачем робить недоцільним додаткові витрати на розробку графічного користувацького інтерфейсу. Відмова від його реалізації зумовлена також тим, що цільова аудиторія користувачів додатку становить групу спеціалістів з тестування, що є досвідченими користувачами комп'ютера і не розгубляться при необхідності роботи з консольним додатком.

Для коректної роботи додатку він повинен бути запущений з наступними параметрами:

Рис. 3.3 Параметри запуску генератору тестів

РОЗДІЛ 4. РЕЗУЛЬТАТИ РОБОТИ

4.1 Приклад №1: Побудова тестів для системи «Банкомат»

Для демонстрації роботи розробленого методу продемонструємо роботу побудованого додатку для генерації тестів для системи «Банкомат».

Нехай наступні вимоги для процесу автентифікації задані на природній мові у вигляді користувацького сценарію:

Основна діюча особа: Клієнт.

Короткий опис: Перед виконанням будь-якої дії клієнт повинен бути автентифікований.

Передумова: картка вставлена у відповідний отвір банкомату

Основний сценарій:

1. Система запитує пароль.

2. Клієнт вводить пароль.

3. Якщо пароль правильний, то карта прийнята

4. Якщо пароль не правильний, то

4.1 Якщо кількість введень неправильного паролю менше 3, то

4.1.1 Видати попередження про неправильне пароль.

Інакше:

4.2 Видати повідомлення про блокування картки.

4.2.1Заблокувати карту.

Післяумова: Немає.

Для використання додатку необхідно транслювати вимоги на природній мові у діаграму станів і переходів кінцевого автомату.



Рис. 4.1 Специфікація «Автентифікації» у вигляді діаграми станів і переходів

Додаток приймає як вхідний параметр текстовий файл із листом ребер. Вершини повинні бути пронумеровані числами натурального ряду починаю з одиниці.

Рис. 4.2 Діаграма станів і переходів з пронумерованими станами

Запуск генератору тестів:



Рис. 4.3 Запуск Graph.exe

Вміст input.txt:

Рис. 4.4 Файл-описання графу станів і переходів

Побудована послідовність:

{0 -> 1 -> 2 -> 3 -> 4-> 5}

{0 -> 1 -> 2 -> 3 -> 4-> 6}

{0 -> 1 -> 2 -> 3 -> 6}

{0 -> 1 -> 2 -> 6}

Співставляючи унікальні ідентифікатори ребер з їх семантичним значенням отримаємо наступний тестовий набір для ручної перевірки модулю «Автентифікація» системи банкомат:

Таблиця 4.1 Тестовий набір

Тест №1
1	Вставити картку
2	Перша спроба введення паролю
3	Друга спроба введення паролю
4	Третя спроба введення паролю
Результат	Картка заблокована
Тест №2
1	Вставити картку
2	Перша спроба введення паролю
3	Друга спроба введення паролю
4	Третя спроба введення паролю
Результат	Картка прийнята
Тест №3
1	Вставити картку
2	Перша спроба введення паролю
3	Друга спроба введення паролю
Результат	Картка прийнята
Тест №4
1	Вставити картку
2	Перша спроба введення паролю
Результат	Картка прийнята

Побудований тестовий набір для ручного виконання дає змогу перевірити функціональність модулю «Автентифікація» системи «Банкомат». Тести дають змогу викрити найкритичніші помилки системи, тобто блокування зміни станів «Банкомату». Протягом виконання тестового набору досвідченим спеціалістом з тестування також можуть бути викриті і інші дефекти з меншим пріоритетом, такі, наприклад, як недоліки графічного інтерфейсу, граматичні помилки, чи не практичність реалізації.

4.2 Приклад №2: Побудова тестового набору для баг-трекінгової системи, представленої графом із циклами

Нехай необхідно перевірити зміну станів звіту про дефект у баг-трекінговій системі представленій на рис. 4.5.

Рис. 4.5 Зміна станів звіту про дефект у баг-трекінговій системі

Як видно, на модельному графі присутній цикл. Побудуємо тестовий набір для даної системи, що гарантує покриття усіх переходів:

{0 -> 1 -> 2 -> 3 -> 4}

{0 -> 7 -> 0 -> 1 -> 6 -> 5 -> 2 -> 3 -> 4}

{0 -> 1 -> 7 -> 0 -> 1 -> 2 -> 3 -> 4}

{0 -> 1 -> 2 -> 3 -> 5 -> 2 -> 3 -> 4}

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

Зазначимо, що тестовий набір отриманий автоматичним генератором тестів гарантує покриття усіх переходів за зменшену кількість тестів (Усього можливо побудувати 11 коректних переходів). Тим самим розроблений додаток забезпечує зменшення часу на його виконання, а отже економію ресурсів - людських і часу.

4.3 Приклад №3: Побудова різних тестових наборів із встановленим рівнем покриття

Запустимо додаток повторно, для того самого графу станів і переходів з тими самими параметрами алгоритму М і Р.

{0 -> 7 -> 0 -> 1 -> 2 -> 3 -> 4}

{0 -> 1 -> 6 -> 5 -> 2 -> 3 -> 5 -> 2 -> 3 -> 4}

{0 -> 1 -> 7 -> 0 -> 1 -> 2 -> 3 -> 4}

Як бачимо, в результаті роботи було сконструйовано інший набір тестів. Це є результатом перебору евристичним алгоритмом невпорядкованої множині тестів: в загальному випадку результати його роботи недерміновані, однак гарантується досягнення встановленої метрики - покриття усіх переходів.

Подібна евристика з урахуванням предметної області забезпечує розроблений підхід генерації тестів додатковою перевагою: вирішення проблеми «парадоксу пестициду»[8], описаний ще 1983 році, який полягає в тому, що перевірки, проведені за тією самою послідовністю кроків, не можуть викрити нові дефекти у програмі.

ВИСНОВКИ

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

Робота проводилась поетапно, у її процесі було детально розглянуто наступні проблеми і вирішено наступні задачі:

1. Розглянуто процес тестування і його складові. Виявлені проблема наявності помилок у існуючих системах, що є складними і часто асистують людству у критичних завданнях; необхідність тестування з метою віднаходження та попередження помилок під час використання; та конфлікт безкінечних можливостей для перевірок і скінчених ресурсів - людських та часу; і як результат, необхідність залучення інструментальної підтримки процесу тестування.

2. Залучення автоматизації до виконання і генерації тестів. Недоліки і переваги обох підходів та обґрунтування вибору автоматизації створення тестів як задачі дослідження.

3. Існуючи способи формального представлення вимог до програмного продукту - логіко-алгебраїчні та операційні моделі. Обґрунтування вибору на користь скінчено - автоматної моделі для описання еталону поведінки програмного забезпечення.

4. Розглянуто варіанти представлення скінченого автомату і обґрунтовано вибір на користь його візуального представлення діаграмою станів і переходів, що дає можливість залучення до розв'язання глобальної задачі дослідження такого потужного інструменту як теорія графів.

5. Розробка і обґрунтування алгоритмів побудови тестів і тестового набору з використанням рекурсивного і жадібного алгоритмів.

6. Побудовано додаток, що реалізує підхід до генерації тестів і проведені експерименти з його використання.

Заявлений підхід налічує наступні переваги:

· Гнучкість. Підхід може бути використаний для побудови тестового набору для продуктів з різних предметних областей, побудованих з використанням різних архітектур і технологій.

· Фіксація максимальної кількості кроків тесту. У тестовий набір буде залучено тести перевищуючі максимальну встановлену довжину, тільки якщо існують переходи, недосяжні з початкової вершини за максимальну кількість кроків. Таким чином забезпечується зниження ймовірності допущення помилки під час виконання тестів, що є актуальною проблемою під час виконання довгих сценаріїв.

· Недетермінованість. Евристичний алгоритм відбору тестів до тестового набору може обирати різні тести із встановленою метрикою тестового покриття, таким чином мінімізуючи ризик настання «парадоксу пестициду».

· Мінімізація розміру тестового набору. Тестовий набір включає кращі тести для досягнення встановленого покриття, замість усіх можливих тестів.

· Гарантованість досягнення встановленого рівні покриття. Для складних систем, що представлені графом із сотнею вершин і більше, гарантувати досягнення покриття усіх переходів створюючи тестовий набір у ручний спосіб складно і існує ймовірність помилки, на відміну від автоматичного способу.

· Статичне тестування вимог. Під час перетворення представлення вимог на природній мові у скінчено-автоматну модель відбувається їх статичне тестування: виявляються їх недоліки, неточності і протиріччя.

Серед недоліків можна виділити наступні:

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

· Неповна автоматизація. Перетворення моделі графу - автомату у список ребер і співставлення унікальних номерів ребер їх семантичному значенню не автоматизовано на даному етапі.

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

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. Cost Benefits Analysis of Test Automation, Douglas Hoffman, Software Quality Methods, LLC; Douglas Hoffman, 1999. - 14 с.