МОДЕЛИ И МЕТОДЫ СИНТЕЗА ТЕСТОВ ДЛЯ РАСПРЕДЕЛЕННЫХ ИНФОРМАЦИОННЫХ СИСТЕМ НА ОСНОВЕ СЕТЕЙ ПЕТРИ

Краткое содержание

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі наведено загальну характеристику роботи, яка підкреслює її

актуальність, наукову новизну та практичне значення, а також визначено об’єкт,

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

У першому розділі виконано аналіз існуючих автоматних моделей тестування

і методів синтезу тестів РІС, який показує можливість їх розвитку при синтезі тестів

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

аналітичних моделей, методів та інформаційної технології синтезу тестів РІС.

Для сучасних РІС на основі різноманітних багаторівневих мереж характерні

висока розмірність, структурна і функціональна складність, неповнота інформації,

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

Це ускладнює вимоги до працездатності і робить тестовий контроль складовою РІС.

Разом з тим, в силу названих властивостей РІС, моделі і методи підготовки

тестового забезпечення по складності і трудомісткості аналізу навіть перевершують

складність і трудомісткість проектування самих РІС, що обумовлює неослабний

інтерес до нових аналітичних моделей тестування і методів синтезу тестів.

Найбільш простими методами синтезу тестів для автоматних моделей є повно

перебірні методи перевірки всіх комбінацій функціональних відображень РІС, але їх

5

обмежує недосяжна розмірність тестів реальних РІС. Зменшення цієї розмірності

дають методи псевдовипадкового вибору тестових комбінацій, що швидко досягають

40-60% повноти перевірки, але додавання нових комбінацій не збільшує цю повноту.

Абстрактні моделі РІС автоматного класу, що представляють алгоритми їх

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

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

експериментів з автоматами. Тест встановлює відповідність еталонної моделі та

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

автомата, наприклад, ідентифікаторів. Але і ці методи мають експонентну, хоч і

зменшену залежність складності від розміру вхідної моделі, наприклад, NP-важким

залишається визначення характеристичних оточень, застосування абстрактних

автоматних методів до реальних РІС обмежене тільки окремими механізмами РІС.

Зниження експонентної складності синтезу тестів та їх довжини дає мережева

і ієрархічна декомпозиція автоматних моделей. У мережі автоматів для окремого

компонентного автомата потрібно визначення вхідної і вихідної поведінки,

відповідно реалізованої від входів мережі і розпізнаної на її виходах. Тест будується

на неповних вхідній і вихідній множинах слів окремого автомата, що відповідно

реалізуються і розпізнаються. Тест мережі – це композиція тестів її компонентних

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

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

ієрархії автоматів групуються тести компонентних автоматів молодшого рівня у

відповідності зі зв'язками автомата старшого рівня. При низхідному синтезі тест

автомата старшого рівня дає структуру тестів автоматів молодшого рівня. Такі

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

багаторівневих мережних систем, наприклад, з використанням протоколів WiFi, IP,

TCP, HTTP. Але зберігається експонентна складність синтезу тестів, що обмежує

клас РІС рівнем середньої складності (біля 100 умовних автоматних переходів).

Непряме застосування автоматних методів до моделей РІС засноване на знанні

спеціальної інформації РІС – коли тестують механізми прийому, передачі,

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

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

та операційний автомати, застосовують метод «розкручування» – від тестування

базових властивостей до тестування допоміжних властивостей. В результаті лінійно

знижуються складність синтезу тесту і його довжина, але зберігається експонентна

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

РІС для синтезу тестів з середнім рівнем складності. Другий недолік такого підходу

– неточне і неповне визначення класів властивостей і помилок, що перевіряються.

Для синтезу тестів РІС на основі мереж Петрі, найбільш потужних у

автоматному класі, введено поняття бісімуляційної еквівалентності, що відстежує

розгалуження в дереві спрацьовувань подвійної системи з еталонної мережі Петрі і

мережі Петрі, що перевіряється. Мережі Петрі, як асинхронно-подієві, паралельні

моделі, що відповідають властивостям РІС та багаторівневих мережних систем,

дають кращі, з точки зору розмірності, розширення і композиції у порівнянні з

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

подвійної системи, що обмежує їх застосування у синтезі тестів, де клас помилок

експонентної розмірності визначений неявно, і потрібно перевіряти бісімуляційну

еквівалентність еталонної і кожної з помилкових мереж Петрі.

6

Аналіз методів синтезу тестів для реальних РІС розмірності вище середньої

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

невирішених завдань і виправдовує подальший розвиток декомпозиційних моделей

тестування і методів синтезу тестів, зокрема, на основі композицій мереж Петрі.

У цьому зв'язку є обґрунтованою постановка завдання розвитку аналітичних

структурно-аналітичних моделей тестування і методів синтезу тестів на основі

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

обходів для поведінки РІС, які реалізуються і транслюються у вузлах композиції.