Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
29
ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ
МАРТИНЮК Олександр Миколайович
УДК 004.052.32:004.052.42:681.5.09:681.518.5
МЕРЕЖНІ МОДЕЛІ І МЕТОДИ ПОБУДОВИ
ФУНКЦІОНАЛЬНИХ ТЕСТІВ АПАРАТНО-ПРОГРАМНИХ ЗАСОБІВ У СКЛАДІ АВТОМАТИЗОВАНИХ СИСТЕМ УПРАВЛІННЯ
Спеціальність 05.13.06 - Автоматизовані системи управління і прогресивні інформаційні технології
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Одеса - 2007
Дисертацією є рукопис
Робота виконана на кафедрі комп'ютерних інтелектуальних систем і мереж Одеського національного політехнічного університету Міністерства освіти і науки України
Науковий керівник кандидат технічних наук, доцент
Полін Євгеній Леонідович,
Одеський національний політехнічний університет, доцент кафедри комп'ютерних систем і мереж
Офіційні опоненти: доктор технічних наук, професор
Крісілов Віктор Анатолійович,
Одеський національний політехнічний університет, завідувач кафедри системного програмного забезпечення;
кандидат технічних наук, доцент
Скобцов Вадим Юрійович,
Донецький інститут прикладної математики й механіки НАН України, Вчений секретар інституту, старший науковий співробітник.
Захист відбудеться “” вересня 2007 року в 13:30 на засіданні спеціалізованої вченої ради Д 41.052.01 в Одеському національному політехнічному університеті за адресою: 65044, м. Одеса, проспект Шевченко, 1, ауд. 400-А.
З дисертацією можна ознайомитися в бібліотеці Одеського національного політехнічного університету за адресою: 65044, м. Одеса, проспект Шевченко, 1.
Автореферат розісланий “” серпня 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 –червня 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ґSi, 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)&(прPri’НпрPriЗRXi)&(прPri’НпрPriЗTrYi)),
RXi’RX^’(Ж№RXi’=RXi), TrYi’TrY^’(Ж№TrYi’=TrYi),
Idi’Id^’((Ж№Idi’НIdi)&(прIdi’НпрIdiЗRXi)&(прIdi’Нпр2IdiЗTrYi)),
Ai’A^’((Ж№Ai’НAi)&(прAi’НпрAiЗRXi)&(прAi’НпрAiЗTrYi)). (5)
Тут пр і пр – перша і друга проекції векторів. Контрольовані підавтомати із 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)
де
ІА об'єднує множини простих ієрархічних переходів двох основних типів вигляду IT = (Иi1ОI1 (si1, Aci1, aci, bсi))(И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 іР^ = Иi3ОI3 іPi3 = (iI(P, Pci))(iI(P, Pti) для перевіряємих властивостей Р^ = PPc^Pt^ та множину спадкувань іIdі3 іId^ = Иi3ОI3 іIdi3 = (iI (Id, Idci))(iI (Id, Idti) для ідентифікаторів Id^ = IdIdc^Idt^, де Рc^ = Иi1ОI1 Pci1, Рt^ = Иi2ОI2 Pti, Idc^ = Иi1ОI1 Idci1, Idt^ = Иi2ОI2 Idti.
Для автоматів А^ визначаються сумісні спадкування іРі3’ іР^’ = Иi3ОI3 іPi3’= (iI(P, Pci’))(iI(P, Pti’) та іIdі3’ іId^’ = Иi3ОI3 іIdi3’= (iI(Id, Idci’)) (iI(Id, Idti’), як підмножини іРі3’ іРі3, іР^’ іР^. Сумісними є відповідні ним множини перевіряємих властивостей Р^’ = P’Pc^’Pt^’і ідентифікаторів станів Id^’ = Id’Idc^’Idt^’, що є підмножинами Р^’ Р^, Id^’ Id^, де Рc^’ = Иi1ОI1 Pci1’, Рt^’ = Иi2ОI2 Pti’, Idc^ = Иi1ОI1 Idci1’, Idt^’ = Иi2ОI2 Idti’. Отже множина усіх переходів 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 Exti. Ex^ дозволяє визначити сумісну множину Ex^’= Ex’ИExc^’ИExt^’, де Exc^’= Иi1ОI1 Exci1’, Ext^’= Иi2ОI2 Exti’, та сумісну ієрархію експериментних примітивів:
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 –.
Підзадача 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 визначає та перевіряє на сумісність множину спадкувань іРі для перевіряємих властивостей 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)+((m+2)n/k+1)(n/k-1)), (9)
де n=|S|, m=|X|, l = |Y|, k –коефіцієнт декомпозиції, h = k для мережних моделей та h = k для ієрархічних моделей, Q –коефіцієнт лінійної залежності реалізації.
Запропоновані декомпозиційні методи побудови ФТ АПЗ на основі аналітичних спеціалізованих мережної моделі і моделі наскрізних тестових переходів базуються на системі експериментних примітивів і призначені для формального опису композицій експериментів, що можливо реалізувати заданими автоматними мережею та ієрархією.
В четвертому розділі розглянуто архітектуру АСТД та інформаційну технологію побудови ФТ для систем контролю працездатності АПЗ у складі АСУ.
Основне призначення АСТД є у автоматизації підготовки тестового забезпечення, представленого у вигляді наборів, послідовностей і структур ФТ і використованого для: а) верифікації проектів АПЗ на відповідність специфікаціям у процесі їхнього функціонально-алгоритмічного проектування; б) тестування реалізацій АПЗ на відповідність верифікованим проектам АПЗ у процесі їхнього виготовлення; в) тестування екземплярів реалізацій АПЗ у процесі їхньої експлуатації. Застосування КСФТ у складі САПР АПЗ і в складі підсистем контролю й діагнозу, які входять до складу АСУ, дозволяє скоротити час налагодження проектів, вихідного контролю й відновлення працездатності АПЗ.
Відповідно до модульного принципу АСТД реалізована у вигляді множини функціонально закінчених блоків. АСТД використовує моделі й методи побудови ФТ АПЗ та містить основні блоки автоматного, мережного і ієрархічного аналізу, додаткові блоки інтерфейсу, Web-інтерпретатора, допомоги (рис. 1).
Блок автоматного аналізу містить три компоненти, що виконують функції ідентифікації станів, реалізації вихідних та розпізнавання вхідних слів, організації автоматних експериментів. Вхідним для блока є таблично-списковий опис автомата, який одержано через інтерфейс ÀÑÒÄ від мережного та ієрархічного блоків, або від зовнішніх систем. Вихідним для блока є таблично-списковий опис ідентифікаторів станів, реалізованих вихідних та розпізнаних вхідних слів, автоматних експериментних примітивів, що передаються через інтерфейс ÀÑÒÄ мережному та ієрархічному блокам, або зовнішнім системам. Компонента ідентифікації станів виконує побудову ідентифікаторів, що використовуються в експериментах. Компонента реалізації вихідних і розпізнавання вхідних слів визначає регулярні підмножини реалізованих вихідних і розпізнаваних вхідних слів, використованих при реалізації і транспортуванні експериментів у мережі. Компонента організації автоматних експериментів будує експериментні примітиві для автомата в умовах регулярних реалізованої вхідної й розпізнаної вихідної множин слів.
Рис. 1. Архітектура АСТД
Блок мережного аналізу містить три компоненти, що виконують функції структурно-функціонального аналізу, реалізації та розпізнавання поведінки, організації мережних експериментів. Вхідним для блока є таблично-списковий опис автоматної мережі, який одержано через інтерфейс ÀÑÒÄ від ієрархічного блоку, або від зовнішніх систем. Вихідним для блока є таблично-списковий опис компонентних структур, реалізованої та розпізнаної у вузлах поведінки, мережних експериментних примітивів, що передається через інтерфейс ÀÑÒÄ ієрархічному блоку, або зовнішнім системам. Компонента структурно-функціонального аналізу виділяє в МАМ топологічні структури та визначає умови синхронізації поведінки ÊÀ. Компонента реалізації та розпізнавання поведінки забезпечує її визначення у вузлах мережі, використовуючи реалізовану й розпізнавану поведінку ÊÀ, базові композиції й умови синхронізації. Компонента організації мережних експериментів будує реалізуємі, контрольні і розпізнаючі експериментні примітиві для мережі, що задовольняють умовам реалізації й розпізнаваємості.
Блок ієрархічного аналізу містить три компоненти, що виконують функції синхронізації алфавітів, визначення спадкування поведінки й організації ієрархічних експериментів. Вхідним для блока є таблично-списковий опис автоматної ієрархії, який одержано одержаний через інтерфейс ÀÑÒÄ від зовнішніх систем. Вихідним для блока є таблично-списковий опис відношень спадкування алфавітів, перевіряємих властивостей, ідентифікаторів, поведінки, ієрархічних експериментних примітивів, що передається через інтерфейс ÀÑÒÄ зовнішнім системам. Компонента синхронізації алфавітів та подій забезпечує узгодження алфавітів в ієрархічних переходах суміжних рівнів при заміщеннях автоматних переходів і станів. Компонента визначення спадкування та деталізації поведінки синхронізує поведінку суміжних рівнів, забезпечуючи узгодження перевіряємих властивостей, ідентифікаторів, поведінки, ієрархічних експериментних примітивів. Компонента організації ієрархічних експериментів будує наскрізні експериментні примітиві для ієрархії, що задовольняють умовам спадкування.
Додаткові блоки виконують стандартні функції. Інтерфейс АСТД містить три компоненти, що виконують функції вхідного контролю, зовнішнього інтерфейсу з зовнішніми системами, композиційного інтерфейсу. Web-інтерпретатор інтерактивної АСТД містить дві компоненти, що виконують функції управління XML- та XSL-об'єктами й підтримки фреймів. Блок контекстної підказки та допомоги містить дві компоненти, що виконують відповідні інтерактивні функції.
ÀÑÒÄ реалізована у програмних середовищах Java і C++. Для реалізації інтерактивного Web-інтерфейсу використані системи Eclipse SDK і Dev C++ з підтримкою метаязиків XML/XSL. ÀÑÒÄ використовує ПЕОМ із х86-архітектурою, як інструментальну, й орієнтована на роботу у мережних ОС Linux і Windows.
Розроблено інформаційну технологію побудови ФТ для систем контролю працездатності АПЗ у складі АСУ, яка використовується на стадіях проектування, виробництва й експлуатації АПЗ. Розроблені автоматні моделі та методи, відрізняючись на різних стадіях і етапах об'єктами аналізу, зберігають однаковий підхід до побудови ФТ, що надає інформаційній технології властивість наскрізної.
На етапі структурно-функціонального аналізу на основі даних проектування й технічних описів АПЗ: а) визначаються множина мереж, множина дворівневих ієрархій, формуючих загальну ієрархію, множини КА, що входять у мережі й ієрархії; б) для множини автоматних, мережних та ієрархічних графів виконується структурний аналіз топологічних структур, а також визначаються відповідні відношення синхронізації поведінки; в) для ієрархічних переходів виконується аналіз спадкувань і деталізацій автоматних станів і переходів та визначаються відповідні відносини синхронізації поведінки.
На етапі компонентного аналізу на основі даних структурно-функціонального аналізу для кожного автомата з об’єднаної множини: а) визначаються множини ідентифікаторів; б) формуються експериментні примітиви; в) визначаються стратегії автономних експериментів; г) в мережі визначаються реалізовані вихідні напівавтомати і розпізнавані вхідні напівавтомати, представляючи умови реалізації й розпізнавання поведінки; д) у переходах дворівневих ієрархій визначаються спадкування перевіряємих властивостей, ідентифікаторів і експериментних примітивів; е) у ієрархіях визначаються стратегії ієрархічних експериментів.
На етапі композиційного аналізу, на основі даних структурно-функціонального й компонентного аналізу: а) для автоматів мережі до входів мережі формуються зворотні вхідні підмережі і реалізовані вхідні множини слів, а також до виходів мережі формуються прямі вихідні підмережі і реалізовані вихідні розпізнавані множини слів; б) для автоматів мережі на відповідних множинах реалізованих і розпізнаваних слів будується можливі компонентні експериментні примітиви; в) для кожної мережі на основі можливих експериментних примітивів визначаються стратегії експериментів, які представляють мережні ФТ; г) для дворівневих спадкувань стратегій експериментів будуються стратегії експериментів, які представляють ієрархічні ФТ; д) для мережних і ієрархічних стратегій експериментів будуються загальні стратегії, що представляють декомпозиційні ФТ.
Першим класом об’єктів АСТД є МАМ та ІАМ дискретних пристроїв рівня складності 10-10 еквівалентних вентилів зі складу АПЗ АСУ, що містять регулярні структури, регістрові і арифметично-логічні пристрої, ЗУ, великі інтегральні схеми (ВІС) і ВІС мікропроцесорних серій (ВІС МП). Другим класом об’єктів АСТД є МАМ та ІАМ протокольних систем мережних АПЗ АСУ рівня складності 10-10 автоматних станів, що представляють модель мережної взаємодії.
Основним класом помилок АПЗ у АСТД прийнято клас постійних помилок функціонального типу для КА. Помилки представляються відхиленнями функцій d’і l’перевіряємого автомата A' = (S', X, Y, d’, l’, So’) від відповідних функцій переходів d і виходів l еталонного автомата A = (S, X, Y, d, l, So) при умові |S’||S|.
Для обраних об’єктів та класу помилок експериментальні випробування АСТД при побудови ФТ продемонстрували зниження довжини ФТ на 10-25% та зниження обчислювальної складності більш ніж на порядок зі збереженням повноти та вірогідності ФТ на рівні 80-85%. При використанні ФТ за рахунок зменшення довжини ФТ час відновлення працездатності АПЗ скорочується на 3-10%. Верхній рівень досягнуто на регулярних структурах, порівняння виконувалось з автоматним і двокомпонентним декомпозиційним підходами. Декомпозиція також підвищує гнучкість організації ФТ завдяки урахуванню особливостей реалізації АПЗ.
Аналіз застосування АСТД в умовах підприємств для регулярних структур та ЗУ дискретних підсистем реальних АПЗ показав зменшення довжини ФТ на 25-35% та зниження обчислювальної складності на повтори –два порядки зі збереженням повноти та вірогідності ФТ на рівні 85-90% у порівнянні з абстрактно автоматним підходом. Застосування для протокольних систем канально-мережного рівня показало зменшення довжини ФТ на 30-35% та зниження обчислювальної складності на два порядки зі збереженням повноти та вірогідності ФТ на рівні 90%.
ВИСНОВКИ
У дисертаційній роботі розроблені і науково обґрунтовані декомпозиційні моделі і методи побудови експериментів для мережних і ієрархічних композицій автоматів, які застосовані при розробці АСТД АПЗ.
У ході виконання дисертаційної роботи отримані наступні результати:
1. Проведено аналіз аналітичних моделей і основних декомпозиційних методів побудови ФТ АПЗ на основі експериментів з композиціями автоматних моделей. Зроблено висновок про необхідність узагальнення декомпозиційного автоматного підходу до синтезу ФТ, яке дозволить скоротити їхню обчислювальну складність й довжину, підвищити гнучкість побудови тестів зі збереженням повноти та вірогідності. Все це спрямовано на зменшення часу відновлення працездатності АПЗ. АСТД АПЗ охарактеризована як необхідний компонент підготовки тестового забезпечення у підсистемі контролю та функціонального тестування АСУ на всіх етапах життєвого циклу АПЗ: проектування, розробки, виготовлення і експлуатації.
. Запропонована спеціалізована аналітична мережна модель, що дає розвиток існуючим мережним автоматним моделям і заснована на системі моделей вхідних і вихідних напівавтоматів та перевірочних графів. Напівавтомати та перевірочні графи побудовані для КА і описують реалізовану й розпізнавану поведінку у вузлах автоматної мережі. Розроблена модель, на відміну від відомих, забезпечує формальний опис мережних умов, які визначають припустимі автоматною мережею експерименти КА, і має обчислювальну складність меншу, ніж свідомі абстрактна та двокомпонентна моделі.
. Запропонована аналітична спеціалізована модель наскрізних тестових переходів, що заснована на системі моделей автоматних підстановок. Автоматні підстановки представляють спадкування перевіряємої та ідентифікуючої поведінки у переходах автоматної ієрархії. Розроблена модель, на відміну від відомих, забезпечує формальний опис умов спадкувань, які визначають припустимі експерименти спадних ієрархічних переходів, і має обчислювальну складність меншу, ніж абстрактна модель.
. Розроблено декомпозиційний метод побудови ФТ АПЗ, що використовує аналітичну спеціалізовану мережну модель і є заснованим на системі мережних реалізованих і розпізнаних експериментних примітивів для КА. Розроблений метод, на відміну від відомих, забезпечує формальний опис композицій експериментів, які можливо реалізувати заданою автоматною мережею, і дозволяє знизити довжину ФТ на 10-30% та обчислювальну складність на порядок зі збереженням повноти та вірогідності ФТ на рівні 80-85%.
. Розроблено декомпозиційний метод побудови ФТ АПЗ, що використовує аналітичну спеціалізовану модель наскрізних тестових переходів і є заснованим на системі ієрархічних, наслідуваних експериментних примітивів. Розроблений метод, на відміну від відомих, забезпечує формальний опис спадних композицій експериментів, які можливо реалізувати заданою автоматною ієрархією, і дозволяє знизити довжину ФТ на 15-35% та обчислювальну складність більш, ніж на порядок зі збереженням повноти та вірогідності ФТ на рівні 80%.
6. Розроблено програми синтезу тестів, які використовуються для підготовки тестового забезпечення об'єктів АПЗ на основі аналізу мережних і ієрархічних автоматних моделей. Моделі й методи знайшли застосування в АСТД, що використовувалась в САПР ВТ РТІ АН СРСР, використовується при проектуванні й контролі АПЗ і протокольних систем на підприємствах НПП “ЛИК”(м. Миколаїв), ПКП “ТЕЛЕКАРТ-ПРИЛАД”(м. Одеса).
7. Експериментальні випробування АСТД і застосування її в умовах підприємств АСТД проводились для дискретних АПЗ АСУ рівня складності 10-10 еквівалентних вентилів, що містять регулярні структури і пристрої управління, а також для протокольних систем мережних АПЗ АСУ рівня складності 10-10 автоматних станів. Випробування АСТД показали зниження довжини ФТ на 10-25%, обчислювальної складності більш ніж на порядок зі збереженням повноти та вірогідності ФТ на рівні 80-85%, за рахунок зменшення довжини ФТ час відновлення працездатності АПЗ скорочується на 3-10%. Застосування АСТД показало зниження довжини ФТ на 25-35% і обчислювальної складності більш ніж на порядок зі збереженням повноти і вірогідності ФТ на рівні 85-90%, та скороченням часу відновлення працездатності АПЗ на 5-10%.
8. Розроблені моделі і методи впроваджені в навчальний процес кафедри КІСМ ОНПУ у дисциплінах “Надійність, контроль, діагностика й експлуатація ЕОМ”, “САПР”, “Мережні інформаційні технології”і дипломному проектуванні.
СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ За ТЕМою ДИСЕРТАЦІЇ
1. Мартынюк А.Н., Полин Е.Л. Проектирование программно-инструменталь-ного комплекса анализа сетевых сервисных объектов // Тр. Одес. политехн. ун-та. –Одесса, 1999. Вып.2. – С.140 –.
2. Мартынюк А.Н. Учебная административная система сети кафедры // Тр. Одес. политехн. ун-та. –Одесса, 1999. Вып.3. –С.125 –.
3. Мартынюк А.Н. Сетевые автоматные модели синтеза тестов // Холодильна техніка і технологія, Одеса, 2007, 2. – С.94 –97.
. Мартынюк А.Н. Базовые модели прототипа системы синтеза тестов // Радіоелектронні і комп'ютерні системи, Харків “ХАІ”, 2007 – 8(27) С.157 –162.
5. Мартынюк А.Н., Полин Е.Л. Метод верификации моделей и синтеза тестов при нисходящем проектировании электронно-вычислительной аппаратуры // Тезисы докладов Всесоюзной научно-технической конференции “Проектирование вычислительных средств”. Каунас, 1989. –С.120 –.
. Мартынюк А.Н., Заболотный В.Г., Любимова С.Л., Полин Е.Л. Сквозной синтез проверяющих тестов // Тезисы докл. республ. научно-техн. конф. “Проблемы автоматизации контроля электронных устройств”. Винница, 1990. –С.34 –.
. Мартынюк А.Н. Верификация сервиса и протоколов вычислительной сети // Статьи по материалам докладов пятой Украинской научно-методич. конф. “Новые информационные технологии обучения в учебных заведениях Украины”. –Часть 1. Одесса, 1997. –С.129 –130.
. Мартынюк А.Н. Учебный программно-инструментальный комплекс анализа сетевых сервисных объектов // Статьи по материалам докладов шестой Украинской научно-методич. конф. “Новые информационные технологии обучения в учебных заведениях Украины”. –Часть 1. Одесса, 1998. –С.136 –.
. Мартынюк А.Н. Метод синтеза тестовых последовательностей и сценариев для сетевых протоколов // Статьи по материалам докладов шестой Украинской научно-методич. конф. “Новые информационные технологии обучения в учебных заведениях Украины”. –Часть 1. Одесса, 1998. –С.194 –.
. Мартынюк А.Н. Построение тестов для протокольных реализаций // Тр. шестой междунар. научно-практич. конф. “Современные информационные и электронные технологии”. –Одесса. 2005. –С.138.
11. Мартынюк А.Н. Применение сетевой автоматной модели при построении тестов // Тр. восьмой междунар. научно-практич. конф. “Современные информационные и электронные технологии”. –Одесса. 2007. –С.143.
. Мартынюк А.Н. Препроцессорные процедуры задач синтеза тестов тестов // Тр. восьмой междунар. научно-практич. конф. “Современные информационные и электронные технологии”. –Одесса. 2007. –С.142.
Мартынюк А.Н. Сетевые модели и методы построения функциональных тестов аппаратно-программных средств в составе автоматизированных систем управления. –Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 5.13.06 –Автоматизированные системы управления и прогрессивные информационные технологии. Одесский национальный политехнический университет. Одесса, 2007.
Диссертация посвящена разработке прикладной информационной технологии, аналитических сетевых и иерархических моделей и декомпозиционных методов построения функциональных тестов (ФТ). Целью исследования является сокращение времени восстановления работоспособности дискретных аппаратно-программных средств (АПС) в составе АСУ с помощью подсистем контроля и тестирования, достигаемое сокращением вычислительной сложности и длины синтезируемых тестов путем разработки новых декомпозиционных методов построения тестов.
В работе проведен анализ современного состояния развития аналитических моделей и декомпозиционных методов построения ФТ АПС на основе экспериментов с композициями автоматных моделей для класса постоянных функциональных неисправностей в виде отклонений автоматных функций переходов и выходов, не увеличивающих числа внутренних состояний. Показано существование ряда нерешенных задач декомпозиционного синтеза ФТ, основанного на использовании существующих реализуемых и распознающих свойств сетевых и иерархических моделей и компонентных автоматов (КА) в их составе, позволяющих получить тесты достижимой вычислительной сложности и длины при сохранении необходимого уровня их полноты и достоверности для реальных АПС.
Для решения данных задач используется аналитический декомпозиционный подход к построению ФТ, предлагаемый теорией экспериментов с автоматами и автоматными композициями, тестовый анализ выполняется на уровне КА сетей и иерархий, отображений и отношений между ними, что позволяет уменьшить вычислительную сложность и длину ФТ и сократить, тем самым, время восстановления работоспособности АПС в процессе их функционального и тестового контроля.
В работе предложена специализированная аналитическая модель, развивающая существующие сетевые автоматные модели и основанная на системе моделей входных и выходных полуавтоматов, а также проверяющих графов. Полуавтоматы и проверяющие графы построены для КА композиций и представляют реализованное и распознанное поведение в узлах автоматной сети. Разработанная модель в отличие от известных обеспечивает формальное описание сетевых условий, определяющих допустимые сетью эксперименты для КА, и имеет вычислительную сложность меньшую, чем абстрактная или двухкомпонентная модель.
Предложена аналитическая специализированная модель сквозных тестовых переходов, основанная на системе моделей автоматных подстановок. Автоматные подстановки представляют наследование проверяемого и идентифицирующего поведения в переходах автоматной иерархии. Разработанная модель в отличие от известных обеспечивает формальное описание условий наследований, которые определяют допустимые эксперименты нисходящих иерархических переходов, и имеет вычислительную сложность существенно меньшую, чем абстрактная модель.
Развит декомпозиционный метод построения ФТ АПС, использующий аналитическую специализированную сетевую модель и основанный на системе реализованных и распознанных экспериментных примитивов для КА. Разработанный метод в отличие от известных обеспечивает формальное описание композиций экспериментов, которые можно реализовать автоматной сетью, и позволяет снизить длину ФТ на 10-30%, вычислительную сложность на порядок с сохранением полноты и достоверности ФТ на уровне 80-85%.
Разработан декомпозиционный метод построения ФТ АПС, использующий аналитическую специализированную модель сквозных тестовых переходов и основанный на системе иерархических, наследуемых экспериментных примитивов. Разработанный метод в отличие от известных обеспечивает формальное описание нисходящих композиций экспериментов, которые возможно реализовать автоматной иерархией, и позволяет снизить длину ФТ на 15-35%, вычислительную сложность более, чем на порядок с сохранением полноты и достоверности ФТ на уровне 80%.
Для практической реализации прикладной информационной технологии синтеза ФТ, аналитических моделей и декомпозиционных методов разработаны программы построения тестов, используемые для подготовки тестового обеспечения АПЗ на основе анализа автоматных сетевых и иерархических моделей. Тестовое обеспечение является одной из базовых компонент систем контроля и тестирования, поддерживающих работоспособность АПЗ в составе АСУ. Использование в автоматизированной системе тестового диагноза (АСТД) данных моделей, методов и программ позволило формализовать построение как самих декомпозиционных ФТ АПЗ, так и программно-инструментальных средств их синтеза.
Проведена апробация разработанных программных средств в рамках хоздоговорных и опытно-конструкторских работ, а также в рамках учебного процесса кафедры компьютерных интеллектуальных систем и сетей ОНПУ. Показано, что использование программных средств позволяет снизить вычислительную сложность и длину ФТ на 10-30%, сокращая, как следствие, время восстановления работоспособности АПЗ на 3-10%.
Ключевые слова: автомат, сетевая модель, иерархическая модель, функциональный тест, идентификатор, эксперимент.
Мартинюк О.М. Мережні моделі і методи побудови функціональних тестів апаратно-програмних засобів у складі автоматизованих систем управління. - Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за фахом 5.13.06 - Автоматизовані системи управління й прогресивні інформаційні технології. Одеський національний політехнічний університет. Одеса, 2007.
Дисертація присвячена розробці інформаційної технології й методів побудови функціональних тестів (ФТ). Метою дослідження є скорочення часу відновлення працездатності апаратно-програмних засобів (АПЗ) у складі АСУ за допомогою підсистем тестування, що досягається скороченням обчислювальної складності й довжини тестів шляхом розробки декомпозиційних методів синтезу тестів.
У роботі проведений аналіз стану аналітичних моделей і декомпозиційних методів побудови ФТ АПЗ, показане існування невирішених задач.
Для рішення даних задач використовується підхід до синтезу ФТ на рівні композицій компонентних автоматів (КА). Запропоновано аналітичні мережну й ієрархічну моделі АПЗ у вигляді систем моделей поведінки, що дозволяють визначити тести у вузлах мереж і переходах ієрархій. На основі моделей розроблені декомпозиційні методи побудови ФТ у вигляді систем експериментних примітивів.
Для практичної реалізації прикладної інформаційної технології синтезу ФТ розроблені програми, використовані у системах контролю працездатності АПЗ.
Проведено апробацію розроблених програмних засобів у рамках госпдоговірних і дослідно-конструкторських робіт, а також у рамках навчального процесу кафедри комп'ютерних інтелектуальних систем і мереж ОНПУ. Використання програмних засобів знижує обчислювальну складність і довжину ФТ на 10-30%, скорочуючи термін відновлення працездатності АПЗ на 3-10%.
Ключові слова: автомат, мережна модель, ієрархічна модель, функціональний тест, ідентифікатор, експеримент.
Martynyuk A.N. Network model and methods of functional tests construction of hardware-software device in composition of the automated control systems. - the Manuscript.
The dissertation on competition of a scientific degree of Cand.Tech.Sci. on a specialty 5.13.06 - the Automated control systems and progressive information technologies. The Odessa national polytechnic university. Odessa, 2007.
The dissertation is devoted to development of information technology and construction methods of functional tests (FT). The purpose of research is reduction of restoration time of hardware-software device (HSD) serviceability in composition of the automated control systems with the help of subsystems of the testing, achievable by reduction of computing complexity and test lengths, by development decomposition methods of test synthesis.
In work the analysis of a modern condition of analytical models and decomposition methods of construction FT HSD is lead, existence of unresolved problems.
For the decision of the given problems the approach to construction FT at a level of componential automata compositions is used. Analytical specialized network and hierarchical models of HSD as model systems of behavior are constructed, allowing defining test behavior in network units and hierarchy transitions. On the basis of the given models are developed decomposition methods of FT construction as systems accordingly experiment unit.
For practical realization of applied information technology of FT synthesis programs, used for check systems of serviceability HSD in composition of the automated control systems.
Approbation of the developed software in frameworks contractual and developmental works is lead, and also within the framework of educational process of computer intellectual systems and networks department of ОNPU. It is shown, that use of software allows to lower computing complexity and length of FT on 10-30 %, reducing restoration time of serviceability HSD on 3-10 %.
Keywords: automata, network model, hierarchical model, the functional test, behavior, the identifier, experiment.