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

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

УДК 004.052.32:004.052.42:681.5.09:681.518.5

МЕРЕЖНІ МОДЕЛІ І МЕТОДИ ПОБУДОВИ
ФУНКЦІОНАЛЬНИХ ТЕСТІВ АПАРАТНО-ПРОГРАМНИХ ЗАСОБІВ У СКЛАДІ АВТОМАТИЗОВАНИХ СИСТЕМ УПРАВЛІННЯ

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

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

Одеса - 2007

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

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

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

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

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

Захист відбудеться “20” вересня 2007 року в 13:30 на засіданні спеціалізованої вченої ради Д 41.052.01 в Одеському національному політехнічному університеті за адресою: 65044, м. Одеса, проспект Шевченко, 1, ауд. 400-А.

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

Автореферат розісланий “20” серпня 2007 р.

Вчений секретар
спеціалізованої вченої ради Ямпольський Ю.С.

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

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

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

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

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

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

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

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

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

-

-

-

-

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

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

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

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

-

-

-

-

Практичне значення отриманих результатів. Практичне значення отриманих результатів складається у розробці прикладної інформаційної технології побудови ФТ для використання в системах контролю працездатності АПЗ у складі АСУ. Застосування моделей і методів зробило можливим формалізацію побудови інструментальних засобів синтезу декомпозиційних ФТ АПЗ у складі АСТД. Це дозволило знизити обчислювальну складність і довжину декомпозиційних ФТ, зберігши їхню повноту і достовірність в класі функціональних несправностей, наближену до рівня повноти і достовірності повно перебірних тестів. Показано, що для АПЗ рівня складності 104-108 еквівалентних вентилів при зниженні обчислювальної складності задачі аналізу на порядок зниження довжини ФТ становить 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, d, l, So), де S – множина внутрішніх станів, X і Y – вхідний і вихідний алфавіти, d:SґX®S – функція переходів, l:SґX®Y або l:S®Y – функція виходів, SoНS – множина початкових станів. Помилки представляються будь-якими відхиленнями d’ і l’ перевіряємого автомата A' = (S', X, Y, d’, l’, So’) від d і l еталонного автомата A = (S, X, Y, d, l, So) при умові |S’||S|.

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

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

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

СA = (X, Y, A^, a^), (1)

де X і Y – загальні вхідний і вихідний алфавіти мережі СA, І – множина індексів усіх КА мережі, А^ = ИiОI Ai – множина КА, a^ = ИiОI ai – множина алфавітних відображень вигляду ai: XґYi’ ® Xi, де i’ОI\{i}, причому, Y=Xk для деякого kОI.

Відображення a^ визначають відношення сумісності для мережної алфавітної синхронізації gna поведінки КА на однорівневій дискретній часовій шкалі MАМ.

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

Визначення 2.1. Y-мінімізація minY(AYi) – цє мінімізація вихідного напівавтомата вигляду AYi = (SYi, Yi, dYi), одержаного при звуженні розмітки переходів автомату Ai до алфавіту Yi. де dYi:SYiYiSYi і SYi Si.

Визначення 2.2. X-мінімізація minX(AXi) – цє мінімізація вхідного напівавтомата вигляду AXi = (SXi, Xi, dXi), де dХi: SХiХiSХi і SХi Si, одержаного при звуженні розмітки переходів автомату Ai до алфавіту Xi.

Для дотримання умов реалізації необхідно, зокрема, визначення регулярної множини слів RХi в алфавіті Xi = ai(XґYi’), реалізованої мережею СA на входах довільного Аi з A^. Нехай Xi* – повна множина вхідних слів автомата Аi, розглянутого в автономному режимі. Діє включення RХi НXi*.

Ai визначає регулярну множину реалізованих вихідних слів RYi у алфавіті Yi.

У відповідності зі структурою зв'язків a-1^ = ИiОI ai-1 від входів автомата Ai до входів СA існує підмережа T-1(Ai), для якої ai(YT-1(Ai)) = Xi і X =X’ґXT-1(Ai) для деякого незалежного від цієї підмережі вхідного підалфавіту X’. Підмережа T-1(Ai) визначає зворотне відображення b-1: RYT-1(Ai)®XT-1(Ai)* реалізованої множини вихідних слів у множину вхідних слів підмережі. Діє рівність RYT-1(Ai) = RХi.

У роботі визначені операції послідовної minY(AYk°Am), паралельної AYkґAYm Y-композиції, а також Y-композиції зі зворотним зв'язком minY(AYk*Am), які використовуються при побудові підмережі T-1(Ai) для довільного Ai з A^. У роботі доведені твердження, використуємі для визначення складності поведінки T-1(Ai).

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

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

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

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

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

При визначенні втрат інформації для автомата Ai описується множина розпізнаваних мережею слів TrYi в алфавіті Yi, що представляється вихідним мінімізованим напівавтоматом AYTri = (SYi, Yi, dYi).

Ai визначає регулярну вхідну множину розпізнаних слів TrXi у алфавіті Xi.

Для визначення множини розпізнаваних слів TrXi запропоновано узагальнення G(Ai) перевірного графа, підграф G’НG(Ai) якого дає опис TrXi:

G(Ai) = (B(Si), YiґXiґSi2, Di, Si). (2)

У відповідності зі структурою зв'язків a^ = ИiОI ai від виходів автомата Ai до виходів СA існує підмережа T(Ai), для якої ai-1(XT(Ai)) = Yi і Y =Y’ґYT(Ai) для деякого незалежного від цієї підмережі вихідного підалфавіту Y’. Підмережа T(Ai) визначає пряме відображення b: TrXT(Ai)®YT(Ai)* розпізнаної множини вхідних слів у множину вихідних слів підмережі. Діє рівність TrXT(Ai) = TrYi.

У роботі визначені операції послідовної minX(Ak°AХm), паралельної AХkґAХm X-композиції, а також X-композиції зі зворотним зв'язком minX(Ak*Am), які використовуються при побудові підмережі T(Ai) для довільного Ai з A^. У роботі доведені твердження, використуємі для визначення складності поведінки T(Ai).

Твердження 2.3. Для автомата Ai регулярна вихідна множина розпізнаних мережею слів TrYi представлена в алфавіті Yi і для не надлишкової мережі перетинається з поведінкою відповідного їй вихідного мінімізованого напівавтомата вигляду AYi = (SYi, Yi, dYi), тобто TrYi AYi..

Наслідок 2.2. При X-мінімізації кожного вхідного напівавтомата AХi з AХ^ = ИiОI AХi на основі звуження розмітки переходів до алфавіту Xi вихідна множина розпізнаних слів TrYi і відповідній вихідній Х-мінімізованій напівавтомат AYi мають розмірність, не більшу розмірності еквівалентного автомата підмережі T(Ai).

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

CEx’ = (X, Y, ИiОI Exi’, ИiОI ai). (3)

CEx’ використовує припустимі у СА мережі перевіряємих властивостей CPr’, реалізованих CRX’ і розпізнаних CTrY’ множин, ідентифікаторів станів CId’, контрольованих підавтоматів CА’:

CPr’ = (X, Y, Pr^’, a^), CRX’ = (X, Y, RX^’, a^), CTrY’ = (X, Y, TrY^’, a^),

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

де Pr^’ = ИiОI Pri’, RX^’ = ИiОI RXi’, Tr^’ = ИiОI TrYi’, Id^’ = ИiОI Idi’, А^’ = ИiОI Аi’.

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

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

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

Мережі CPr’, CRX’, СTrY’, CId’, CА’ засновані на множинах перевіряємих і характеристичних властивостей будь-якого автомата Аi з умовами реалізації від входу Х мережі до входів Хi і транспортування від виходів Yi до виходу мережі Y:

Pri’Pr^’((Ж№Pri’НPri)&(пр1Pri’Нпр1PriЗRXi)&(пр2Pri’Нпр2PriЗTrYi)),

RXi’RX^’(Ж№RXi’=RXi), TrYi’TrY^’(Ж№TrYi’=TrYi),

Idi’Id^’((Ж№Idi’НIdi)&(пр1Idi’Нпр1IdiЗRXi)&(пр2Idi’Нпр2IdiЗTrYi)),

Ai’A^’((Ж№Ai’НAi)&(пр1Ai’Нпр1AiЗRXi)&(пр2Ai’Нпр2AiЗTrYi)). (5)

Тут пр1 і пр2 – перша і друга проекції векторів. Контрольовані підавтомати із A^’ включаються у автомати з A^ і повністю або частково зберігають в СА перевіряємі Pr^’ та характеристичні RX^’, TrY^’, Id^’ властивості. У роботі доведене твердження, що є основою для методу побудови мережних експериментів.

Твердження 2.5. Включення CP’НCP, CRX’НCRX, CTrY’НCTrY, CId’НCId, CA’НCA породжують включення CEx’НCEx.

Таким чином формується аналітична спеціалізована мережна модель, як сукупність шістки мереж – мереж перевіряємих властивостей CP', характеристичних властивостей CRX', CTrY', CId', контрольованих автоматів СА’ і експериментів CEx'.

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

Як базова запропонована дворівнева ієрархія автоматів, як шістка вигляду:

IA = (A, Ac^, At^, ac^, bс^, n), (6)

де

- A = (S, X, Y, d, l, S0) – старший КА верхнього рівня звичайного вигляду;

- Ac^ = Иi1ОI1 Aci1 – множина підавтоматів, які заміщають через підстановку макростани, вигляду Aci1 = (Sci1, Xci1, Yci1, dci1, lci1, Sci10, Fci10), де Sci10НSci1 і Fci10НSci1 – множини початкових і кінцевих станів підавтомата Aci1;

- At^ = Иi2ОI2 Atj2 – множина підавтоматів, заміщуючих через підстановку макропереходи, вигляду Atj2 = (Stj2, Xtj2, Ytj2, dtj2, ltj2, {stj20}, {ftj20}), де stj20ОStj2 і ftj20ОStj2 – початковий і кінцевий стани підавтомата Atj1;

- aс^ = Иi1ОI1 aсi1 – множина часткових відображень, заміщуючих входи у розщепляємі макростани на входи в нові початкові стани з Sci10 вигляду aci1:(SґX®s)®(SґX®Sci10);

- bс^ = Иi1ОI1 bсi1 – множина часткових відображень, заміщуючих виходи з розщепляємих макростанів у виходи з нових кінцевих станів з Fci10 вигляду bсi1:(sґX®S)®(Fci10ґX®S), де s – заміщаємий макростан, Sci10 і Fci10 – множини нових, початкових і кінцевих станів заміщаючого підавтомата Aci1;

- n – часткове відображення, заміщуюче макропереходи n:SґX®Иi2ОI2 Ati2.

ІА об'єднує множини простих ієрархічних переходів двох основних типів вигляду IT = (Иi1ОI1 (si1, Aci1, aci1, bсi1))(Иi2ОI2 ((хi2,уi2), Ati2), n).

Дворівнева ієрархія IА накладає на синхронні КА, що входять до її складу, умови синхронізації алфавітів. Відображення aс^, bс^, n для А^ = AИAc^ИAt^ визначають відношення ієрархічної алфавітної синхронізації gia поведінки автоматів на дворівневій дискретній часовій шкалі ІАМ, що є відношенням сумісності.

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

Кожний ієрархічний перехід іtі3 з множини усіх переходів IT, де і3І3 = І1І2, породжує множину спадкувань іРі3 іР^ = Иi3ОI3 іPi3 = (i1I1(P, Pci1))(i2I2(P, Pti2) для перевіряємих властивостей Р^ = PPc^Pt^ та множину спадкувань іIdі3 іId^ = Иi3ОI3 іIdi3 = (i1I1 (Id, Idci1))(i2I2 (Id, Idti2) для ідентифікаторів Id^ = IdIdc^Idt^, де Рc^ = Иi1ОI1 Pci1, Рt^ = Иi2ОI2 Pti2, Idc^ = Иi1ОI1 Idci1, Idt^ = Иi2ОI2 Idti2.

Для автоматів А^ визначаються сумісні спадкування іРі3’ іР^’ = Иi3ОI3 іPi3’ = (i1I1(P, Pci1’))(i2I2(P, Pti2’) та іIdі3’ іId^’ = Иi3ОI3 іIdi3’ = (i1I1(Id, Idci1’)) (i2I2(Id, Idti2’), як підмножини іРі3’ іРі3, іР^’ іР^. Сумісними є відповідні ним множини перевіряємих властивостей Р^’ = P’Pc^’Pt^’ і ідентифікаторів станів Id^’ = Id’Idc^’Idt^’, що є підмножинами Р^’ Р^, Id^’ Id^, де Рc^’ = Иi1ОI1 Pci1’, Рt^’ = Иi2ОI2 Pti2’, Idc^ = Иi1ОI1 Idci1’, Idt^’ = Иi2ОI2 Idti2’. Отже множина усіх переходів IT формує відповідні ієрархії перевіряємих властивостей та ідентифікаторів:

IP’ = (A, P’, Pc^’, Pt^’, ac^, bc^, n), IId’ = (A, Id’, Idc^’, Idt^’, ac^, bc^, n), (7)

Сумісні ієрархії IEx’ засновані на ієрархіях сумісних перевіряємих властивостей IР’ і ідентифікаторів станів IId’. Хай Ex^ = ExИExc^ИExt^ множина експериментних примітивів, відповідних автоматам з А^ дворівневої ієрархії IА, розглядаємим автономно, де Exc^ = Иi1ОI1 Exci1, Ext^ = Иi2ОI2 Exti2. Ex^ дозволяє визначити сумісну множину Ex^’ = Ex’ИExc^’ИExt^’, де Exc^’ = Иi1ОI1 Exci1’, Ext^’ = Иi2ОI2 Exti2’, та сумісну ієрархію експериментних примітивів:

IEx’ = (Ex’, Exc^’, Ext^’, ac^, bc^, n). (8)

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

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

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

Твердження 2.7. Відображення ac^Иbc^Иn: A®(A’ИAc^’ИAt^’) і гомоморфізми P®IP, Id®IId, ’: A®A’, c^’: Ac^®Ac^’, t^’: At^®At^’, IP®IP’, IId®IId’ породжують гомоморфізм (Ex®IEx & IEx®IEx’)Ю(Ex®IEx’).

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

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

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

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

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

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

Крок 1.1 для кожного Ai, розглянутого автономно, визначає його власну вихідну множину реалізованих слів RYi у алфавіті Yi та виконує Y-мінімізацію Ai, яка дає вихідний напівавтомат AYi.

Крок 1.2 відповідно структурі зв'язків a-1^ будує підмережу T-1(Ai), що формує множину RXi = RXi’ на входах автомата Ai від входів підмережі XT(Ai), за допомогою операцій послідовної, паралельної Y-композиції та Y-композиції зі зворотним зв'язком. Сукупність RХ^’ = ИiОI RXi’ для всіх автоматів з A^ зі структурою зв'язків a^ утворює мережу CRX’.

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

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

Крок 2.1 для кожного Ai, розглянутого автономно, визначає його власну вхідну множину розпізнаних слів TrXi у алфавіті Xi та виконує X-мінімізацію Ai, яка дає вхідний напівавтомат AXi. Для цього крок будує граф G(Ai) та виділяє його підграф G’НG(Ai), що дає опис множини TrXi.

Крок 2.2 відповідно структурі зв'язків a^ будує підмережу T(Ai), що формує множину TrYi = TrYi’ на виходах автомата Ai від виходів підмережі YT(Ai), за допомогою операцій послідовної, паралельної X-композиції та X-композиції зі зворотним зв'язком. Сукупність TrY^’ = ИiОI TrYi’ для всіх автоматів з A^ зі структурою зв'язків a^ утворює мережу CTrY’.

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

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

Крок 3.1 для кожного Ai, розглянутого автономно, визначає множину його перевіряємих властивостей Pri та відповідно обмеженням (5) для Pri’ будує множину можливих у мережі перевіряємих властивостей Pri’. Сукупність Pr^’ = ИiОI Pri’ для всіх автоматів з A^ зі структурою зв'язків a^ утворює мережу CPr’.

Крок 3.2 для кожного Ai, розглянутого автономно, будує множину його ідентифікаторів станів Idi та відповідно обмеженням (5) для Idi’ будує множину можливих у мережі ідентифікаторів Idi’. Сукупність Id^’ = ИiОI Idi’ для всіх автоматів з A^ зі структурою зв'язків a^ утворює мережу CId’.

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

Крок 4.1 для кожного Ai будує множину можливих у мережі експериментних примітивів Exi’. Сукупність Ex^’ = ИiОI Exi’ для всіх автоматів з A^ зі структурою зв'язків a^ утворює мережу CEx’.

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

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

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

Крок 5.1 для кожного ієрархічного переходу іtі3 визначає та перевіряє на сумісність множину спадкувань іРі3 для перевіряємих властивостей P^. Сукупність перевірених спадкувань іP^’ для усіх ІT разом з ac^, bc^, n формує ієрархію ІP’.

Крок 5.2 для кожного ієрархічного переходу іtі3 визначає та перевіряє на сумісність множину спадкувань іIdі3 для ідентифікаторів станів Id^. Сукупність сумісних спадкувань іId^’ для усіх ІT разом з ac^, bc^, n формує ієрархію ІId’.

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

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

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

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

ФТ на основі мережних та ієрархічних методів мають відповідні аналітичні оцінки складності обчислень cn та сі (об'єму обчислень/пам'яті) і довжини d:

cn = Q(k((lmn/k2n-1)n/k(2n+3)-3+2(n-1)/k(4m+n))+k2((n/k(2m+1)+m((n-1)/k)(2n/k+l)),

cі = Q(k((lmn/k2n-1)n/k(2n+3)-3+k((n/k(2m+1),

d = Q(h((m+1)(n/k)2+((m+2)n/k+1)(n/k-1)), (9)

де n=|S|, m=|X|, l = |Y|, k – коефіцієнт декомпозиції, h = k2 для мережних моделей та h = k для ієрархічних моделей, Q – коефіцієнт лінійної залежності реалізації.

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

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

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

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

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

Рис. 1.