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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

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

Спеціальність 05.13.06 - Автоматизовані системи управління і прогресивні інформаційні технології

МАРТИНЮК Олександр Миколайович

Одеса - 2007

Дисертацією є рукопис

Робота виконана на кафедрі комп'ютерних інтелектуальних систем і мереж Одеського національного політехнічного університету Міністерства освіти і науки України

Науковий керівник кандидат технічних наук, доцент

Полін Євгеній Леонідович,

Одеський національний політехнічний університет, доцент кафедри комп'ютерних систем і мереж

Офіційні опоненти: доктор технічних наук, професор

Крісілов Віктор Анатолійович,

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

кандидат технічних наук, доцент

Скобцов Вадим Юрійович,

Донецький інститут прикладної математики й механіки НАН України, Вчений секретар інституту, старший науковий співробітник.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Апаратним і програмним засобам контролю, як функціонального, так і тестового, приділялося й приділяється значна увага. До теперішнього часу в теорії й практиці контролю АПЗ, насамперед систем, спроектованих з урахуванням вимог контролепридатності, досягнуто рівень складності реальних ВІС. Найбільший розвиток і впровадження одержали структурні методи із застосуванням граничного сканування пам'яті, які пропонуються у версіях стандарту IEEE-1149.1. Однак методи сканування вимагають суттєвих додаткових апаратних і програмних витрат.

Масове використання мікропроцесорів, які зазвичай не надають інформацію про логічну структуру, застосування кремнієвих компіляторів, що синтезують ВІС з функціонального рівня, впровадження протокольних технологій з визначеними інтерфейсами при нерозкритій структурі компонентів обумовлюють необхідність продовження досліджень задач аналізу поведінкових моделей і розробки функціональних тестів (ФТ) у контролі АПЗ.

У не декомпозиційних методах, які використовують функціональні моделі, ріст складності АПЗ експоненціально збільшує обчислювальну складність задач аналізу, переводячи їх у клас важко розв'язних для об'єктів рівня складності ВІС. Декомпозиційні методи синтезу ФТ зменшують цю залежність пропорційно коефіцієнту декомпозиції.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дослідження в області розробки ФТ АПЗ проводилися в рамках госпдоговірних робіт (1981-1989) РТІ АН СРСР (м. Москва), що виконувалися за постановою Ради Міністрів СРСР і інших директивних органів, дослідно-конструкторської роботи “Розробка й поставка досвідного зразка програмно-керованого вимірювально-діагностичного комплексу на базі персонального комп'ютера” (2004-2006) НПП “ЛИК” (м. Миколаїв), а також планових науково-дослідних робіт №329-73 “Апаратні засоби автоматизованих систем. Розробка й дослідження методів і засобів автоматизованих систем” (1998-2003) і №531-62 “Апаратно-програмне забезпечення автоматизованих систем” (2004-2006) кафедри комп'ютерних інтелектуальних систем і мереж (КІСМ) Одеського національного політехнічного університету (ОНПУ).

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

виконано аналіз сучасного стану аналітичних моделей і декомпозиційних методів побудови ФТ АПЗ;

на базі відомих аналітичних моделей розроблені спеціалізовані мережна й ієрархічна моделі АПЗ, які засновані на визначенні й спадкуванні автоматної поведінки у заданих вузлах мережі й переходах ієрархії;

розроблені методи і технологію побудови ФТ АПЗ у вигляді композицій експериментів, які припустимо реалізувати у заданих автоматних мережах й ієрархіях;

розроблені програми синтезу ФТ, що є основними у складі автоматизованої системи технічної діагностики (АСТД), які можуть використовуватися для підготовки тестового забезпечення АПЗ на основі аналізу мережних і ієрархічних автоматних моделей.

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

Предметом дослідження є методи побудови ФТ як організації експериментів для композицій автоматних моделей АПЗ у задачах тестування дискретних підсистем АСУ.

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

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

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

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

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

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

Практичне значення отриманих результатів. Практичне значення отриманих результатів складається у розробці прикладної інформаційної технології побудови ФТ для використання в системах контролю працездатності АПЗ у складі АСУ. Застосування моделей і методів зробило можливим формалізацію побудови інструментальних засобів синтезу декомпозиційних ФТ АПЗ у складі АСТД. Це дозволило знизити обчислювальну складність і довжину декомпозиційних ФТ, зберігши їхню повноту і достовірність в класі функціональних несправностей, наближену до рівня повноти і достовірності повно перебірних тестів. Показано, що для АПЗ рівня складності 10⁴-10⁸ еквівалентних вентилів при зниженні обчислювальної складності задачі аналізу на порядок зниження довжини ФТ становить 10-35%. За рахунок цього досягається зменшення відповідно на 3-10% часу відновлення працездатності АПЗ. Мережна та ієрархічна декомпозиції також підвищують гнучкість в організації тестування, обумовлену багатоваріантністю побудови ФТ і можливістю врахування особливостей конкретних АПЗ.

Запропоновані в роботі методи побудови ФТ АПЗ впроваджені у комплекси апаратно-програмних засобів проектування АПЗ кафедри обчислювальних машин і СПКБ “Дискрет” Одеського політехнічного інституту, Радіотехнічного інституту АН СРСР (м. Москва) у рамках госпдоговірних робіт, виконаних за постановою Ради Міністрів СРСР і інших директивних органів, НПП “ЛИК” (м. Миколаїв) у рамках дослідно-конструкторської роботи “Розробка й поставка дослідного зразка програмно-керованого вимірювально-діагностичного комплексу на базі персонального комп'ютера”, а також ПКП “ТЕЛЕКАРТ-ПРИЛАД” (м. Одеса) для тестування пристроїв цифрових телекомунікаційних систем. Результати дисертаційної роботи впроваджені в навчальний процес кафедри КІСМ ОНПУ у курсах “Надійність, контроль, діагностика й експлуатація ЕОМ”, “САПР”, “Мережні інформаційні технології” і у дипломному проектуванні.

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

Запропонована аналітична спеціалізована мережна модель, що заснована на системі моделей вхідних і вихідних напівавтоматів та перевірочних графів, представляючих реалізовану й розпізнану поведінку у вузлах автоматної мережі [3,4]. Запропонована аналітична спеціалізована модель наскрізних тестових переходів, що заснована на системі моделей автоматних підстановок, представляючих спадкування перевіряємої та ідентифікуючої поведінки у переходах автоматної ієрархії [4,7]. Розроблений декомпозиційний метод, який використовує аналітичну спеціалізовану мережну модель і заснований на системі мережних реалізованих та розпізнаних експериментних примітивів [3,4,9]. Розроблено декомпозиційний метод побудови ФТ АПЗ, який використовує аналітичну спеціалізовану модель наскрізних тестових переходів і заснований на системі ієрархічних, наслідуваних експериментних примітивів [4,9,10]. Розроблена інформаційна технологія побудови ФТ для систем контролю працездатності АПЗ у складі АСУ та реалізовані програми синтезу ФТ у складі АСТД [1,2,8,12]. Автор брав участь у випробуваннях програм АСТД й аналізі отриманих результатів.

Апробація роботи. Результати досліджень доповідалися й обговорювалися на дванадцятьох конференціях і семінарах, у тому числі на: Всесоюзній науково-технічній конференції “Проектирование вычислительных средств”, 4 - 6 червня 1989 року, Каунас, республіканській науково-технічній конференції “Проблеми автоматизації контролю електронних пристроїв”, 13 - 15 листопада 1990 року, Вінниця; республіканській науково-технічній конференції “Проблеми автоматизації контролю й діагностування складних технічних систем”, 17 - 19 вересня 1991 року, Житомир; п'ятій Українській науково-методичній конференції “Нові інформаційні технології навчання в навчальних закладах України”, Одеса, 1997 р.; шостій Українській науково-методичній конференції “Нові інформаційні технології навчання в навчальних закладах України”, Одеса, 1998 р.; шостій міжнародній науково-практичній конференції “Сучасні інформаційні й електронні технології”, 23 - 25 травня 2005 року, Одеса; міжнародній науково-технічній конференції “Гарантопридатні (надійні й безпечні) системи, сервіси й технології”, 25 - 27 квітня 2007 року, Кіровоград; восьмій міжнародній науково-практичній конференції “Сучасні інформаційні й електронні технології”, 23 - 25 травня 2007 року, Одеса.

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

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

Структура дисертації. Дисертація складається з 150 сторінок, введення, 4 розділів, висновків, 16 підрозділів, 12 рисунків, 8 таблиць, списку використаних джерел (96 найменувань), 2 додатків.

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

У вступі обґрунтована актуальність теми дисертації, сформульовані мета та задачі досліджень, викладені основні наукові й практичні результати.

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

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

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

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

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

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

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

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

Автомати мережі спільно функціонують по-різному. Для синхронного або почергового функціонування мережі ФТ будуються для кожного компонента мережі, спільну поведінку інших компонентів описує один автомат A. Несправності компонента Х, не виявлені на зовнішніх вузлах мережі, описуються редукціями найбільшого рішення рівняння A*X=C, де C дає еталонну поведінку всієї мережі. Найбільше рішення рівняння показує точність тестування компоненти Х. Узагальнення операції композиції автоматів на основі максимально припустимої поведінки невідомого компонента, якщо відома поведінка мережі й інших компонентів, дозволяє будувати ФТ для синхронного і почергового функціонування.

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

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

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

У роботі основним класом помилок АПЗ, для яких розробляються методи побудови ФТ, прийнятий клас постійних помилок для компонентних автоматів (КА) вигляду A = (S, X, Y, ?, ?, S_o), де S - множина внутрішніх станів, X і Y - вхідний і вихідний алфавіти, ?:S?X?S - функція переходів, ?:S?X?Y або ?:S?Y - функція виходів, S_o?S - множина початкових станів. Помилки представляються будь-якими відхиленнями ?' і ?' перевіряємого автомата A' = (S', X, Y???', ?', S_o') від ? і ? еталонного автомата A = (S, X, Y, ?, ?, S_o) при умові |S'||S|.

У якості вхідної елементарної моделі для методів побудови експериментів КА мережі або ієрархії у роботі використовується система множини слів поведінки, перевіряємих властивостей Pr_i, як відображень _i і _i, ідентифікаторів станів та відносин сумісності і несумісності.

Для опису МАМ запропонована мережа автоматів, як четвірка вигляду:

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

Визначення 2.1. Y-мінімізація min^Y(A^Y_i) - цє мінімізація вихідного напівавтомата вигляду A^Y_i = (S^Y_i, Y_i, ?^Y_i), одержаного при звуженні розмітки переходів автомату A_i до алфавіту Y_i. де ?^Y_i:S^Y_iY_iS^Y_i і S^Y_i S_i.

Визначення 2.2. X-мінімізація min^X(A^X_i) - цє мінімізація вхідного напівавтомата вигляду A^X_i = (S^X_i, X_i, ?^X_i), де ?^Х_i: S^Х_iХ_iS^Х_i і S^Х_i S_i, одержаного при звуженні розмітки переходів автомату A_i до алфавіту X_i.

Для дотримання умов реалізації необхідно, зокрема, визначення регулярної множини слів R^Х_i в алфавіті X_i? = ?_i(X?Y_i'), реалізованої мережею СA на входах довільного А_i з A^. Нехай X_i* - повна множина вхідних слів автомата А_i, розглянутого в автономному режимі. Діє включення R^Х_i??X_i*.

A_i визначає регулярну множину реалізованих вихідних слів R^Y_i у алфавіті Y_i.

У відповідності зі структурою зв'язків ?^-1^ = ?_i?I ?_i^-1 від входів автомата A_i до входів СA існує підмережа T^-1(A_i), для якої ?_i(Y_T^-1_(Ai)) = X_i і X =X'?X_T^-1_(Ai) для деякого незалежного від цієї підмережі вхідного підалфавіту X'. Підмережа T^-1(A_i) визначає зворотне відображення ?^-1: R^Y_T^-1_(Ai)?X_T^-1_(Ai)* реалізованої множини вихідних слів у множину вхідних слів підмережі. Діє рівність R^Y_T^-1_(Ai) = R^Х_i.

У роботі визначені операції послідовної min^Y(A^Y_k?A_m), паралельної A^Y_k?A^Y_m Y-композиції, а також Y-композиції зі зворотним зв'язком min^Y(A^Y_k*A_m), які використовуються при побудові підмережі T^-1(A_i) для довільного A_i з A^. У роботі доведені твердження, використуємі для визначення складності поведінки T^-1(A_i).

Твердження 2.1. Для автомата A_i регулярна вхідна множина реалізованих мережею слів R^Х_i? представлена у алфавіті X_i і включається у поведінку відповідного їй вхідного мінімізованого напівавтомата вигляду A^Х_i = (S^Х_i, Х_i, ?^Х_i), тобто R^Х_i??A^Х_i.

Наслідок 2.1. При Y-мінімізації кожного вихідного напівавтомата A^Y_i з A^Y^ = ?_i?I A^Y_i на основі звуження розмітки переходів до алфавіту Y_i вхідна множина реалізованих слів R^Х_i і відповідний вхідний Y-мінімізований напівавтомат A^Х_i мають розмірність, не більшу розмірності еквівалентного автомата підмережі T^-1(A_i).

У мережі СА потрібно визначення множини вихідних слів Tr^Y_i автомата A_i, розпізнаних на виходах мережі Y. Мережа СА не надлишкова, якщо отриманий у результаті мережної композиції еквівалентний мережі автомат є мінімальним.

У роботі доведено твердження, що використовується для визначення можливості транспортування експериментів до виходів мережі:

Твердження 2.2. У не надлишковій мережі СА будь-який А_i містить підавтомат без втрати інформації.

При визначенні втрат інформації для автомата A_i описується множина розпізнаваних мережею слів Tr^Y_i в алфавіті Y_i, що представляється вихідним мінімізованим напівавтоматом A^Y_Tri = (S^Y_i, Y_i, ?^Y_i).

A_i визначає регулярну вхідну множину розпізнаних слів Tr^X_i у алфавіті X_i.

Для визначення множини розпізнаваних слів Tr^X_i запропоновано узагальнення G(A_i) перевірного графа, підграф G'?G(A_i) якого дає опис Tr^X_i:

G(A_i) = (B(S_i), Y_i?X_i?S_i², ?_i, S_i). (2)

У відповідності зі структурою зв'язків ?^ = ?_i?I ?_i від виходів автомата A_i до виходів СA існує підмережа T(A_i), для якої ?_i^-1(X_T(Ai)) = Y_i і Y =Y'?Y_T(Ai) для деякого незалежного від цієї підмережі вихідного підалфавіту Y'. Підмережа T(A_i) визначає пряме відображення ?: Tr^X_T(Ai)?Y_T(Ai)* розпізнаної множини вхідних слів у множину вихідних слів підмережі. Діє рівність Tr^X_T(Ai) = Tr^Y_i.

У роботі визначені операції послідовної min^X(A_k?A^Х_m), паралельної A^Х_k?A^Х_m X-композиції, а також X-композиції зі зворотним зв'язком min^X(A_k*A_m), які використовуються при побудові підмережі T(A_i) для довільного A_i з A^. У роботі доведені твердження, використуємі для визначення складності поведінки T(A_i).

Твердження 2.3. Для автомата A_i регулярна вихідна множина розпізнаних мережею слів Tr^Y_i? представлена в алфавіті Y_i і для не надлишкової мережі перетинається з поведінкою відповідного їй вихідного мінімізованого напівавтомата вигляду A^Y_i = (S^Y_i, Y_i, ?^Y_i), тобто Tr^Y_i?A^Y_i..

Наслідок 2.2. При X-мінімізації кожного вхідного напівавтомата A^Х_i з A^Х^ = ?_i?I A^Х_i на основі звуження розмітки переходів до алфавіту X_i вихідна множина розпізнаних слів Tr^Y_i і відповідній вихідній Х-мінімізованій напівавтомат A^Y_i мають розмірність, не більшу розмірності еквівалентного автомата підмережі T(A_i).

Для СА сукупність експериментів Ex^ = ?_i?I Ex_i для КА з A^, розглянутих автономно, є основою мережі взаємодіючих, можливих у СА експериментів CEx':

CEx' = (X, Y,--И_iОI--Ex_i’,--И_iОI--a_i). (3)

CEx' використовує припустимі у СА мережі перевіряємих властивостей CPr', реалізованих CR^X' і розпізнаних CTr^Y' множин, ідентифікаторів станів CId', контрольованих підавтоматів CА':

CPr' = (X, Y, Pr^', a^), CR^X' = (X, Y, R^X^', a^), CTr^Y' = (X, Y, Tr^Y^', a^),

CId' = (X, Y, Id^', a^), CА' = (X, Y, А^', a^), (4)

де Pr^' = ?_i?I Pr_i', R^X^' = И_iОI R^X_i', Tr^' = И_iОI--Tr^Y_i', Id^' = И_iОI Id_i', А^' = И_iОI А_i'.

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

Твердження 2.4. У не надлишковій мережі СА будь-який стан sS_i будь-якого А_i має, принаймні, один реалізований і розпізнаний мережею ідентифікатор Id_s.

Наслідок 2.3. Необхідною й достатньою умовою побудови експерименту для А_i мережі СА є наявність, принаймні, одного реалізованого й розпізнаваного мережею ідентифікатора Id_s для кожного його стану sS_i.

Мережі CPr', CR^X', СTr^Y', CId', CА' засновані на множинах перевіряємих і характеристичних властивостей будь-якого автомата А_i з умовами реалізації від входу Х мережі до входів Х_i і транспортування від виходів Y_i до виходу мережі Y:

Тут пр₁ і пр₂ - перша і друга проекції векторів. Контрольовані підавтомати із A^' включаються у автомати з A^ і повністю або частково зберігають в СА перевіряємі Pr^' та характеристичні R^X^', Tr^Y^', Id^' властивості. У роботі доведене твердження, що є основою для методу побудови мережних експериментів.

Твердження 2.5. Включення CP'НCP, CR^X'НCR^X, CTr^Y'НCTr^Y, CId'?CId, CA'?CA породжують включення CEx'НCEx.

Таким чином формується аналітична спеціалізована мережна модель, як сукупність шістки мереж - мереж перевіряємих властивостей CP', характеристичних властивостей CR^X', CTr^Y', CId', контрольованих автоматів СА' і експериментів CEx'.

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

ІА об'єднує множини простих ієрархічних переходів двох основних типів вигляду IT = (И_i1ОI1--(s_i1,--A^c_i1,--a^c_i1,--b^с_i1))(И_i2ОI2--((х_i2,у_i2),--A^t_i2),--n).

Дворівнева ієрархія IА накладає на синхронні КА, що входять до її складу, умови синхронізації алфавітів. Відображення ?^с^, ?^с^, ? для А^ = A?A^c^?A^t^ визначають відношення ієрархічної алфавітної синхронізації ?_ia поведінки автоматів на дворівневій дискретній часовій шкалі ІАМ, що є відношенням сумісності.

Ієрархія експериментних примітивів можлива за умови збереження перевіряємих властивостей і ідентифікаторів станів в ієрархічних відображеннях ?^c^, ?^c^, ? дворівневої ієрархії ІА. Ця умова обмежує множини автоматів з A^ і ієрархічних відображень ?^c^, ?^c^, ?, припустимих для ІА.

Кожний ієрархічний перехід іt_і3 з множини усіх переходів IT, де і₃І₃ = І₁І₂, породжує множину спадкувань іР_і3 іР^ = ?_i3?I3 іP_i3 = (_i1I1(P, P^c_i1))(_i2I2(P, P^t_i2) для перевіряємих властивостей Р^ = PP^c^P^t^ та множину спадкувань іId_і3 іId^ = ?_i3?I3 іId_i3 = (_i1I1 (Id, Id^c_i1))(_i2I2 (Id, Id^t_i2) для ідентифікаторів Id^ = IdId^c^Id^t^, де Р^c^ = ?_i1?I1 P^c_i1, Р^t^ = ?_i2?I2 P^t_i2, Id^c^ = ?_i1?I1 Id^c_i1, Id^t^ = ?_i2?I2 Id^t_i2.

Для автоматів А^ визначаються сумісні спадкування іР_і3' іР^' = ?_i3?I3 іP_i3' = (_i1I1(P, P^c_i1'))(_i2I2(P, P^t_i2') та іId_і3' іId^' = ?_i3?I3 іId_i3' = (_i1I1(Id, Id^c_i1')) (_i2I2(Id, Id^t_i2'), як підмножини іР_і3' іР_і3, іР^' іР^. Сумісними є відповідні ним множини перевіряємих властивостей Р^' = P'P^c^'P^t^' і ідентифікаторів станів Id^' = Id'Id^c^'Id^t^', що є підмножинами Р^' Р^, Id^' Id^, де Р^c^' = ?_i1?I1 P^c_i1', Р^t^' = ?_i2?I2 P^t_i2', Id^c^ = ?_i1?I1 Id^c_i1', Id^t^' = ?_i2?I2 Id^t_i2'. Отже множина усіх переходів IT формує відповідні ієрархії перевіряємих властивостей та ідентифікаторів:

IP' = (A, P', P^c^', P^t^', a^c^,--b^c^,--n), IId' = (A, Id', Id^c^', Id^t^', ?^c^, ?^c^, ?), (7)

Сумісні ієрархії IEx' засновані на ієрархіях сумісних перевіряємих властивостей IР' і ідентифікаторів станів IId'. Хай Ex^ = Ex?Ex^c^?Ex^t^ множина експериментних примітивів, відповідних автоматам з А^ дворівневої ієрархії IА, розглядаємим автономно, де Ex^c^ = ?_i1?I1 Ex^c_i1, Ex^t^ = ?_i2?I2 Ex^t_i2. Ex^ дозволяє визначити сумісну множину Ex^' = Ex'?Ex^c^'?Ex^t^', де Ex^c^' = ?_i1?I1 Ex^c_i1', Ex^t^' = ?_i2?I2 Ex^t_i2', та сумісну ієрархію експериментних примітивів:

IEx' = (Ex', Ex^c^', Ex^t^', a^c^,--b^c^,--n). (8)

У роботі доведене твердження, використоване для спадкувань експериментів:

Твердження 2.6. Необхідною умовою представлення експериментом старшого рівня Ex' структури експериментів молодшого рівня Ex^' є всюди визначеність і ін'єктивність відображень ?^c^, ?^c^, ? множини застосованих ідентифікаторів Id^- Id' автомата А у множину застосованих ідентифікаторів Id⁺ Id^' автоматів з А^.

Твердження дозволяє для A^ визначити сумісну з ІА множину підавтоматів A^' = A'?A^c^'?A^t^', зв'язаних з автоматами з A^ відношенням включення та зберігаючих у дворівневій ієрархії перевіряємі властивості P^' і ідентифікатори станів Id^'. У відповідності до відображень ?^c^, ?^c^, ? властивості автомата А і автоматів з A^ зв'язують гомоморфізми ^ = {, ^c^, ^t^}. Отже, і властивості автомата А і автоматів з A^' зв'язані гомоморфізмами ^' = {', ^c^', ^t^'}. У роботі доведене твердження, використоване при побудові ієрархічних експериментів:

Твердження 2.7. Відображення a^c^Иb^c^Иn: A?(A'?A^c^'?A^t^') і гомоморфізми P?IP, Id?IId, ': A?A', ^c^': A^c^?A^c^', ^t^': A^t^?A^t^', IP?IP', IId?IId' породжують гомоморфізм (Ex?IEx & IEx?IEx')?(Ex?IEx').

Так формується аналітична спеціалізована модель наскрізних тестових переходів, як четвірка ієрархій - ієрархії автоматів IA', ієрархії перевіряємих властивостей IP', ієрархії ідентифікаторів станів IId' та ієрархії експериментів IEx'.

Запропоновані аналітичні спеціалізовані мережна модель та модель тестових переходів, а саме, мережа CEx' та ієрархія IEx' дають просторову та часову структури ФТ і застосовуються для методів побудови мережних та ієрархічних експериментів, використуємих відповідно як мережні та наскрізні ФТ АПЗ.

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

Декомпозиційні методи побудови ФТ використовують як вхідні: а) метод побудови експериментів для КА з застосуванням ідентифікаторів, що встановлює ізоморфізм еталонного A_i та перевіряємого A_i' автоматів; б) структурний аналіз для графів автоматів, мереж СА і ієрархій ІА, який визначає топологічні структури, суттєві для ФТ, а саме, входи, виходи, шляхи, дерева, гамаки, зворотні зв'язки і конденсації; в) аналіз відображень ?^, ?^с^, ?^с^, ? автоматів А^ мереж і ієрархій для визначення відношень алфавітної синхронізації ?_na та ?_ia поведінки КА.

У декомпозиційному методі побудови ФТ АПЗ на основі аналітичної спеціалізованої мережної моделі вирішуються підзадачі 1 - 4.

Підзадача 1 визначає множини вхідних слів R^Х^, реалізованих мережею СA на входах автоматів з A^.

Крок 1.1 для кожного A_i, розглянутого автономно, визначає його власну вихідну множину реалізованих слів R^Y_i у алфавіті Y_i та виконує Y-мінімізацію A_i, яка дає вихідний напівавтомат A^Y_i.

Крок 1.2 відповідно структурі зв'язків ?^-1^ будує підмережу T^-1(A_i), що формує множину R^X_i = R^X_i' на входах автомата A_i від входів підмережі X_T(Ai), за допомогою операцій послідовної, паралельної Y-композиції та Y-композиції зі зворотним зв'язком. Сукупність R^Х^' = ?_i?I R^X_i' для всіх автоматів з A^ зі структурою зв'язків ?^ утворює мережу CR^X'.

Операції кроків виконуються при прямому просуванні у T^-1(A_i) і можливі у послідовних та паралельних структурах, КЗЗ, зокрема, у конвеєрах та гамаках.

Підзадача 2 визначає множини вихідних слів Tr^Y^ автоматів з A^, розпізнаних на виходах мережі Y.

Крок 2.1 для кожного A_i, розглянутого автономно, визначає його власну вхідну множину розпізнаних слів Tr^X_i у алфавіті X_i та виконує X-мінімізацію A_i, яка дає вхідний напівавтомат A^X_i. Для цього крок будує граф G(A_i) та виділяє його підграф G'?G(A_i), що дає опис множини Tr^X_i.

Крок 2.2 відповідно структурі зв'язків ?^ будує підмережу T(A_i), що формує множину Tr^Y_i = Tr^Y_i' на виходах автомата A_i від виходів підмережі Y_T(Ai), за допомогою операцій послідовної, паралельної X-композиції та X-композиції зі зворотним зв'язком. Сукупність Tr^Y^' = ?_i?I Tr^Y_i' для всіх автоматів з A^ зі структурою зв'язків ?^ утворює мережу CTr^Y'.

Операції кроків виконуються при зворотному просуванні у T(A_i) і можливі у послідовних та паралельних структурах, КЗЗ, зокрема, у конвеєрах та гамаках.

Підзадача 3 визначає множини перевіряємих властивостей Pr^' та ідентифікаторів станів Id^' автоматів з A^.

Крок 3.1 для кожного A_i, розглянутого автономно, визначає множину його перевіряємих властивостей Pr_i та відповідно обмеженням (5) для Pr_i' будує множину можливих у мережі перевіряємих властивостей Pr_i'. Сукупність Pr^' = ?_i?I Pr_i' для всіх автоматів з A^ зі структурою зв'язків ?^ утворює мережу CPr'.

Крок 3.2 для кожного A_i, розглянутого автономно, будує множину його ідентифікаторів станів Id_i та відповідно обмеженням (5) для Id_i' будує множину можливих у мережі ідентифікаторів Id_i'. Сукупність Id^' = ?_i?I Id_i' для всіх автоматів з A^ зі структурою зв'язків ?^ утворює мережу CId'.

Підзадача 4 будує множини можливих у мережі експериментних примітивів Ex^' = ?_i?I Ex_i' на основі ідентифікаторів Id^' і перевіряємих властивостей Pr^' та формує стратегії мережних експериментів.

Крок 4.1 для кожного A_i будує множину можливих у мережі експериментних примітивів Ex_i'. Сукупність Ex^' = ?_i?I Ex_i' для всіх автоматів з A^ зі структурою зв'язків ?^ утворює мережу CEx'.

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

У декомпозиційному методі побудови ФТ АПЗ на основі аналітичної спеціалізованої моделі наскрізних тестових переходів вирішується підзадачі 5 і 6.

Підзадача 5 визначає множини спадкувань для перевіряємих властивостей P^ та ідентифікаторів станів Id^ автоматів з A^ у дворівневої ієрархії ІА, а також множину автоматів A^', зв'язаних гомоморфізмами з множиною автоматів А^ та зберігаючих властивості P^' і ідентифікатори Id^'.

Крок 5.1 для кожного ієрархічного переходу іt_і3 визначає та перевіряє на сумісність множину спадкувань іР_і3 для перевіряємих властивостей P^. Сукупність перевірених спадкувань іP^' для усіх ІT разом з ?^c^, ?^c^, ? формує ієрархію ІP'.

Крок 5.2 для кожного ієрархічного переходу іt_і3 визначає та перевіряє на сумісність множину спадкувань іId_і3 для ідентифікаторів станів Id^. Сукупність сумісних спадкувань іId^' для усіх ІT разом з ?^c^, ?^c^, ? формує ієрархію ІId'.

Крок 5.3 для множини автоматів A^ формує множину автоматів A^', зв'язаних відповідно гомоморфізмами ^, повністю або частково зберігаючих у дворівневій ієрархії перевіряємі властивості P^' і ідентифікатори станів Id^'.

Підзадача 6 визначає множину сумісних у ІА експериментних примітивів Ex^' для автоматів з A^ та формує стратегії ієрархічних експериментів.

Крок 6.1 для кожного автомата з A^ будує множину сумісних у ІА експериментних примітивів Ex^' на основі сумісних перевіряємих властивостей Pr^' та ідентифікаторів станів Id^'. Сукупність іEx^' для автоматів з ІA зі структурою відображень ?^c^, ?^с^, ? утворює ієрархію експериментних примітивів ІEx'.

Крок 6.2 формує множину стратегій загальних ієрархічних експериментів відповідно аналізу топологічних структур ІА та базовим стратегіям спадного, висхідного, пріоритетного, інкрементного та регулярного підходів.

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

В четвертому розділі розглянуто архітектуру АСТД та інформаційну технологію побудови ФТ для систем контролю працездатності АПЗ у складі АСУ.

Основне призначення АСТД є у автоматизації підготовки тестового забезпечення, представленого у вигляді наборів, послідовностей і структур ФТ і використованого для: а) верифікації проектів АПЗ на відповідність специфікаціям у процесі їхнього функціонально-алгоритмічного проектування; б) тестування реалізацій АПЗ на відповідність верифікованим проектам АПЗ у процесі їхнього виготовлення; в) тестування екземплярів реалізацій АПЗ у процесі їхньої експлуатації. Застосування КСФТ у складі САПР АПЗ і в складі підсистем контролю й діагнозу, які входять до складу АСУ, дозволяє скоротити час налагодження проектів, вихідного контролю й відновлення працездатності АПЗ.

Відповідно до модульного принципу АСТД реалізована у вигляді множини функціонально закінчених блоків. АСТД використовує моделі й методи побудови ФТ АПЗ та містить основні блоки автоматного, мережного і ієрархічного аналізу, додаткові блоки інтерфейсу, Web-інтерпретатора, допомоги (рис. 1).

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

Рис. 1. Архітектура АСТД

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

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

Додаткові блоки виконують стандартні функції. Інтерфейс АСТД містить три компоненти, що виконують функції вхідного контролю, зовнішнього інтерфейсу з зовнішніми системами, композиційного інтерфейсу. Web-інтерпретатор інтерактивної АСТД містить дві компоненти, що виконують функції управління XML- та XSL-об'єктами й підтримки фреймів. Блок контекстної підказки та допомоги містить дві компоненти, що виконують відповідні інтерактивні функції.

АСТД реалізована у програмних середовищах Java і C++. Для реалізації інтерактивного Web-інтерфейсу використані системи Eclipse SDK і Dev C++ з підтримкою метаязиків XML/XSL. АСТД використовує ПЕОМ із х86-архітектурою, як інструментальну, й орієнтована на роботу у мережних ОС Linux і Windows.

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

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

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

...