ЗАСТОСУВАННЯ ГЕНЕТИЧНОГО АЛГОРИТМУ ДЛЯ ФОРМУВАННЯ НАБОРІВ ВХІДНИХ ТЕСТОВИХ ДАНИХ - Scientific conference
Main page
UA RU EN

Congratulation from Internet Conference!

Hello

Рік заснування видання - 2011

ЗАСТОСУВАННЯ ГЕНЕТИЧНОГО АЛГОРИТМУ ДЛЯ ФОРМУВАННЯ НАБОРІВ ВХІДНИХ ТЕСТОВИХ ДАНИХ

23.08.2023 14:29

[1. Information systems and technologies]

Author: Бердник Михайло Геннадійович, доктор технічних наук, Національний технічний університет «Дніпровська політехніка»; Захаров Дмитро Ігорович, аспірант, Національний технічний університет «Дніпровська політехніка»; Стародубський Ігор Петрович, аспірант, Національний технічний університет «Дніпровська політехніка»


ORCID: 0000-0003-4894-8995 Бердник М.Г.

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

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

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

Одним із способів візуалізації коду є граф потоків управління (ГПУ), який визначається як спрямований граф СГ = (V, R, vint, vout), де  V - набір вузлів графа, R - підмножина декартового добутку V×V, яке визначає бінарне відношення на V (множина ребер графа), vint, vout – вхідний та вихідний вузли, відповідно, vint є V, voutє V. Ребро (гілка) графа (vi, vJ) відповідає можливій передачі управління від вузла до vi вузла vJ . Кожна гілка може бути позначена предикатом, що визначає умови, за яких ця гілка буде пройдена при черговому запуску програми. Використання графа потоків управління дозволяє визначити шлях, яким пройшли обчислення при виборі відповідного тестового набору.

Таким чином, можно визначити шлях P в графе, який є набором вузлів P = (vint, vil,..., vij,...,vout) , таких що ( vij, vij+1)є R .

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

Визначимо  (u1, u2...un)  – вектор вхідних змінних тестованого коду; область визначення вхідних змінних Ω = Ω1×Ω2, ...×Ωn , де  Ωi – область визначення вхідної змінної ui. Шлях P досягнутий, якщо існує вхідний тестовий набір, що призводить до проходження потоку керування цим шляхом, в іншому випадку шлях P недосяжний. Мета генерації даних - знайти безліч тестових наборів (x1, x2...xk),  xi є Ωi, що ініціюють проходження по заданій безлічі досяжних шляхів.  Як критерій якості тестового набору можна використовувати функцію, яка задає ненульові ваги тим вузлам графа, по яких проходить шлях P:

                                                                               

де  wi(x)– ненульові ваги, що відповідають шляху P та вхідному вектору  xi є Ωi; n(x) – кількість операторів на аналізованому шляху.

Розглянемо формальну постановку задачі  генерації тестових даних та її розв'язання з допомогою генетичного алгоритму (ГА). Відповідно до термінології ГА визначимо популяцію особин, що складається з k хромосом   (x1, x2...xk), де кожна хромосома xi=(ui1, ui2...uin) відповідає одному набору тестових даних, складається з n генів (значень n вхідних змінних). Основний  цикл ГА виконуються ітераційно до досягнення максимально можливого покриття або заданої кількості поколінь:

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

2. Оцінка популяції. Кожна хромосома популяції оцінюється функцією пристосованості (наприклад, функцією (1) у разі потреби покриття заданого шляху P).

3. Селекція (відбір). Кращі 20% хромосом відбираються у незмінному вигляді для наступного покоління; решта 80% хромосом наступного покоління будуть отримані в результаті схрещування. Ця пропорція отримана емпірично і дозволяє забезпечити достатню різноманітність популяції з високою швидкістю збіжності.

4. Схрещування. Половина особин наступного покоління формується шляхом випадкового схрещування 20% найкращих хромосом попереднього покоління один з одним. Інші хромосоми будуть отримані шляхом випадкового схрещування всіх хромосом попереднього покоління один з одним.

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

6. Формування тестових наборів даних у вигляді пулу елітних хромосом. У кожному поколінні відбувається відбір особин популяції в пул елітних хромосом, що забезпечують додаткове покриття коду, порівняно з попереднім покриттям. Обчислення ваги у функції пристосованості (1) може бути проведено з використанням різних метрик складності коду.

Завдання полягає у максимізації цільової функції, тобто F(X) →max.. Використання генетичних алгоритмів дозволяє порівнювати безліч різних варіантів даних для тестування програми. Широкі можливості до удосконалення дозволяє збільшити кількість початкових тестових варіантів, кількість поколінь та додати нові властивості, завдяки яким можна суттєво збільшити можливості знаходження більш відповідних варіантів. Якщо відстежувати пройдені графи і знижувати ваги тих графів, які найчастіше зустрічаються в різних варіантах, можна забезпечити пошук нових шляхів, які на даний момент можуть не траплятися, але можуть бути важливими не менше, ніж ті, що найчастіше зустрічаються.



Creative Commons Attribution Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
допомога Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter

Another articles in this section

Сonferences

Conference 2024

Conference 2023

Conference 2022

Conference 2021



Міжнародна інтернет-конференція з економіки, інформаційних систем і технологій, психології та педагогіки

Наукова спільнота - інтернет конференції

:: LEX-LINE :: Юридична лінія

Інформаційне суспільство: технологічні, економічні та технічні аспекти становлення