Содержание к диссертации
ВВЕДЕНИЕ б
Глава 1. АНАЛИЗ МЕТОДОВ И СРЕДСТВ ПСЕВДОСЛУЧАЙНОГО
ТЕСТИРОВАНИЯ ПРОГРАММНО УПРАВЛЯЕМЫХ
УСТРОЙСТВ 16
1.1. Математические модели и методы синтеза
тестовых воздействий и програм* 19
1.2. Средства псевдослучайного тестирования
программно управляемых устройств 30
1.3. Выводы 36
Глава 2. ТЕОРЕТИЧЕСКИЕ И МЕТОДОЛОГИЧЕСКИЕ ОСНОВЫ
РАЗРАБОТКИ И ИССЛЕДОВАНИЯ СТОХАСТИЧЕСКИХ
МЕТОДОВ И СРЕДСТВ КОНТРОЛЯ ПРОГРАММНО
УПРАВЛЯЕМЫХ УСТРОЙСТВ 38
Условия эффективного применения стохастических методов для решения задач контроля цифровых устройств 38
Методологические основы исследования и разработки методов и средств контроля
программно управляемых устройств 51
2.3. Выводы 56
Глава 3. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ПРОЦЕССОВ ГЕНЕРАЦИИ
ТЕСТОВЫХ ВОЗДЕЙСТВИЙ И ТЕСТОВЫХ ПРОГРАММ 58
Модель тестового воздействия 59
Модель процесса генерации тестового воздействия 64
Модель тестовой программы 82
Модель функционально полной программы 89
Модель процесса генерации тестов/ых программ 94
Выводы 102
Глава 4. МЕТОД АНАЛИЗА ПОРСЖШЩИХ СВОЙСТВ
СТОХАСТИЧЕСКИХ ПРОЦЕССОВ ГЕНЕРАЦИИ
ТЕСТОВЫХ ВОЗДЕЙСТВИИ И ПРОГРАММ 104
4.1. Эквивалентное представление порождаюцего
графа стохастического регулярного источника 106
Анализ порождающих свойств стохастического регулярного источника 108
Анализ вероятностных и количественных характеристик языка, порождаемого стохастическим регулярным источником 114
Эквивалентное представление порождающего графа стохастической билинейной
КС-грамматики 120
Анализ порождающих свойств стохастической грамматики 121
Информационные свойства моделей процессов генерации тестовых воздействий и программ 125
Выводы 132
Глава 5. МЕТОДИКА ПОСТРОЕНИЯ МОДЕЛЕЙ СТОХАСТИЧЕСКИХ
ПРОЦЕССОВ ГЕНЕРАЦИИ ТЕСТОВЫХ ПРОГРАММ 134
Особенности архитектуры микропроцессоров, учитываемые при генерации тестовых программ 135
Анализ системы команд тестируемого микропроцессора и синтез элементарных
графов 138
Синтез поровдающего графа стохастического регулярного источника 145
Вывода 164
Глава 6. МЕТРОЛОГИЧЕСКОЕ ОБЕСПЕЧЕНИЕ АВТОМАТИЗИРОВАННЫХ
СИСТЕМ ПСЕВД0СЛУЧАШЇОГО ТЕСТИРОВАНИЯ
ПРОГРАММНО УПРАВЛЯЕМЫХ УСТРОЙСТВ 165
6.1. Типовой тракт формирования событий
с заданной вероятностью 166
метрологическая аттестация генераторов псевдослучайных последовательностей 169
Анализ применяемых дискретных шкал
вероятностей и вносимых ими погрешностей 173
6.4. Интегральная оценка относительной
погрешности вероятности порождения
элементов тестовых воздействий и программ 176
6.5. Метод построения оптимальной дискретной
шкалы вероятностей 180
6.6. ВЫВОДЫ 187
Глава 7. АППАРАТНОЕ, ПРОГРАММНОЕ И МЕТОДИЧЕСКОЕ
ОБЕСПЕЧЕНИЕ АВТОМАТИЗИРОВАННЫХ СИСТЕМ
ПСЕВДОСЛУЧАЙНОГО ТЕСТИРОВАНИЯ ПРОГРАММНО
УПРАВЛЯЕМЫХ УСТРОЙСТВ 189
Т.1. Устройства, реализующие связные управляемые
стохастические процессы 190
7.2. Устройства анализа стохастических
процессов 197
7.3. Подсистема автоматизации процесса синтеза
тестовых программ 202
7.4. Автоматизированная система
ТЕСТ-8103 214
7.5. Автоматизированная система
ЛИНГВИСТ-802 220
7.6. Автоматизированная система
ЛЙНГВИСТ-803 230
7.Т. Вывода 236
ЗАКЛЮЧЕНИЕ 238
ЛИТЕРАТУРА 243
ПРИЛОЖЕНИЕ 270
Введение к работе
Широкое использование программно управляемых устройств (ПУУ) практически во всех сферах человеческой деятельности остро ставит проблему обеспечения их надежного функционирования. Отказы ПУУ, являющихся управляющим ядром многих сложных систем и движущихся в пространстве объектов, могут приводить к тяжелым последствиям. Все это определяет важность и необходимость обеспечения высокого качества и достоверности их контроля на всех этапах их жизненного цикла.
К сожалению развитие теории, методов и средств контроля программно управляемых устройств отстает от требований практики. Это обусловлено быстрым ростом функциональной и структурной сложности устройств, постоянным ростом степени интеграции их элементной базы, усложнением технологических процессов производства, что влечет рост стоимости контрольно-испытательного оборудования, увеличение трудоемкости и снижение достоверности процессов контроля.
Исследованям в области разработки теории» методов и средств контроля устройств вычислительной техники и систем управления посвящены работы многих ученых и руководимых ими научных коллективов, в частности П. П. Пархоменко, В- А. Гуляева, Н. П. БаЯды, В. Г., Тоценко, И. Ф. Клисторина, 0. Г. Шаршунова, А. А. Аракеляна, Г. II. Ясинявичене, S. Thatt, С. Robach, G. Cancier, С. Bellon и др.
В последнее время приобретают все большее распространение и пользуются все болшим вниманием специалистов и исследователей
стохастические метода и средства контроля цифровых устройств, отличающиеся простотой технической реализации, сравнительно низкой трудоемкостью процесса синтеза тестовых воздействий (ТВ) и тестовых программ (ТП), относительно низкой стоимостью реализущих такие метода автоматизированных систем контроля (АСК),
Разработке и исследованию стохастических методов и средств контроля посвящены работы А. М- Романкевича, С. М- Берштейна* В- И. Ярмолика, В- И, Борщевича, А- А. Гремальского, V. Agraval, К. Parker, R. David, Thevenod-Fosse и др.
К стохастическим методам тестирования относят методы, использующие, в той или иной мере, математический аппарат теории вероятностей и математической статистики.
Профессором В, И. Борщевичем выделены, например, следующие области применения стохастических методов [641:
случайный поиск тестовых наборов, используемый в процессе синтеза ТВ с применением средств логического моделирования цифровых устройств и их константных логических неисправностей;
статистическая проверка гипотез о наличии или отсутствии неисправностей в тестируемом устройстве как средство определения его технического состояния;
статистические испытания разработанных ранее тестов для определения их качества (полноты) относительно заданного класса неисправностей;
псевдослучайное отображение множества реакций тестируемого устройства во множество сигнатур, как средство сжатия реакций и условие реализации метода сигнатурного анализа, разработанного специалистами фирмы Hewlett Packard;
- псевдослучайные метода генерации ТВ и ТП, обнаруживающих
заданный класс неисправностей тестируемого устройства.
Под тестированием устройства мы, в соответствии с [74,75], будем понимать активный процесс определения его технического состояния.
Псевдослучайные процессы, обладая основными характеристиками случайных, в то же время имеют ряд важных преимуществ, среди которых:
воспроизводимость, что позволяет использовать для анализа реакций регулярные метода, обладающие большой разрешающей способностью;
простота реализации псевдослучайных генераторов с заданными свойствами посредством программных и аппаратных средств АСК;
возможность гибкого управления параметрами псевдослучайных процессов для достижения желаемых порождающих свойств.
Использование стохастических (псевдослучайных) методов и реализующих их средств для тестирования программно управляемых устройств вычислительной техники и систем управления выдвинуло на передали план новые сложные проблемы.
Выявилась необходимость проведения строгого сравнительного анализа детерминированных и стохастических методов контроля с целью определения условий и границ их наиболее эффективного применения, а также необходимость разработки формальных методов адаптации параметров псевдослучайных процессов к особенностям конкретного тестируемого устройства при генерации тестовых воздействий и программ, разработки математических методов анализа порождающих свойств используемых процессов, разработки алгоритмов
функционирования, аппаратного, программного в методического и метрологического обеспечения автоматизированных систем псевдослучайного тестирования программно управляемых устройств.
Объектами исследования являются тестовые воздействия и программы л связные управляемые стохастические процессы их генерации, а также средства псевдослучайного тестирования программно управляемых устройств.
Целью диссертационной работы является решение актуальной проблемы автоматизации, повышения эффективности и достоверности процессов псевдослучайного тестирования программно управляемых устройств вычислительной техники и систем управления-
Задачи исследования. Достижение поставленной цели требует решения следующих взаимосвязанных задач:
- исследование с единых теоретических и методологических
позиций условий наиболее эффективного применения стохастических
методов и средств для решения задач контроля сложных цифровых,
в том числе программно управляемых устройств;
разработка и исследование математических моделей тестовых воздействий и программ, отражающих их наиболее существенные свойства, определяющие способность обнаруживать функциональные неисправности;
разработка и исследование математических моделей связных управляема стохастических процессов генеращш тестовых воздействий и программ, обеспечивающих возможность адаптации генерируемых воздействий и программ к особенностям конкретного тестируемого устройства;
разработка методов анализа порождающих свойств связных
стохастических процессов для обеспечения целенаправленного управления параметрами генерирующих алгоритмов;
разработка методаки построения моделей связных управляемых стохастических процессов» обеспечивающей формализацию необходимой информации о тестируемом устройстве и формальное преобразование моделей в алгоритмы функционирования автоматизированных систем псевдослучайного тестирования;
разработка устройств, программного, методического и метрологического обеспечения систем, решающих проблему автоматизации и повышения эффективности процесса псевдослучайного тестирования программно управляемых устройств вычислительной техники и систем управления.
Методы исследований основаны на применении математического аппарата теории игр, математической лингвистики, матричного анализа, теории вероятностей, теории информации, а также теории и методов технической диагностики.
Разработан новый аналитический метод исследования порождающих свойств связных стохастических процессов, основанный на исчислении матриц над алгебрами с операциями специального вида.
Научная новизна диссертационной работы заключается в теоретическом обосновании с единых методологических позиций условий наиболее целесообразного и эффективного применения стохастических методов для решения задач контроля сложных цифровых устройств, разработке на основе предложенной концепции методов формализаіщи информации о тестируемом устройстве и ее отображения в структуру и параметры алгоритмов, генерирующих тестовые программы, методов моделирования и анализа порождающих свойств связных
управляемых стохастических процессов» используемых в автоматизированных системах псевдослучайного тестирования. Автор защищает!
концепцию псевдослучайного тестирования программно управляемых устройств, заключакщуюся в использовании доступной информации о конкретном тестируемом устройстве» отображении ее формальным путем в структуру и параметры связных стохастических процессов* обеспечивая их адаптацию к особенностям тестируемого устройства, и решения на этой основе актуальных проблем автоматизации процесса синтеза тестовых воздействий и программ, повышения эффективности и достоверности контроля программно управляемых устройств;
методологию исследования и разработки стохастических методов и средств контроля, опирающуюся на предложенную концепцию и строгое теоретическое обоснование условий их наиболее эффективного применения;
методы математического моделирования тестовых воздействий, программ и связных управляемых стохастических процессов генерации;
метод анализа порождающее свойств связных стохастических процессов генерации;
метод определения погрешностей вероятностных оценок качества тестовых программ и достоверности процесса псевдослучайного тестирования;
принципы построения аппаратуры, программного, методического и метрологического обеспечения автоматизированных систем псевдослучайного тестирования программно управляемых устройств.
Связь с государственными программами и НИР.
Разработки устройств, алгоритмов, программного, методического
и метрологического обеспечения систем контроля выполнялись:
в соответствии с координационным планом НИР АН СССР по проблеме 1.12-8, раздел 1 -12.8.3, тема "Автоматизированные системы проектирования контроля и диагностики микропроцессорной техники*,
* ГР 0I860O22457;
в рамках целевой комплексной программы и на основании приказа Н 535 MB и ССО СССР от 20.05.81 г. по теме "Автоматизированные системы проектирования, контроля и оптимизации технологических процессов и технических объектов", Ж ГР 8103557Э;
на основании постановлений Правительства СССР * 317-126 от 08,04.83 г. и * 30 от 08.02.84 г. для контроля специализированных процессоров;
на основании постановления Правительства СССР J6 355 от 23.03.8Т г. для тестирования управляющих процессоров ультразвуковых средств неразрушающего контроля;
в рамках НИР; "Исследование и разработка программного обеспечения автоматизированных систем контроля электронной аппаратуры" Я ГР 81013731. "Система автоматизированного контроля и даагностики электронных блоков ультразвуковых средств неразрушающего контроля"
* ГР 0I8600I7GI7, "Диагностика - ЭО" per. * У 54443;
в рамка* ОКР "Автомат", per. * У 81337.
Образца систем демонстрировались на ВДНХ СССР (удостоверение
* 24535) и на международной выставке "Связь - 86*.
Практическая ценность диссертационной работы.
На основе результатов исследований, разработанных методов моделирования и анализа определены перспективные направления развития, условия наиболее эффективного применения стохастических
методов и средств тестирования, разработаны метода формализации исходной информации о тестируемом устройстве, процедуры построения математических моделей процессов генерации, устройства и алгоритмы, позволяющие автоматизировать процесс синтеза тестовых воздействий и программ и снизить его трудоемкость.
Результаты исследований позволили получить ряд оригинальных технических решений, защищенных авторскими свидетельствами на изобретения.
Разработанные устройства, алгоритмы и методики реализованы в автоматизированных системах псевдослучайного тестирования, что позволило повысить эффективность и достоверность процесса контроля программно управляемых устройств, обеспечить высокую надежность и качество производимой вычислительной техники и систем управления.
Реализация результатов диссертационной работы.
Основные результаты научных исследований и разработок реализованы в виде ряда устройств, программной подсистемы автоматизации синтеза тестовых программ - П4СТП, алгоритмов функционирования, базового программного, методического и метрологического обеспечения автоматизированных систем псевдослучайного тестирования ТВОТ-7901, ТЕСТ-8103, ЛИНГВИСТ-802, ЛИНГВИСТ-803, внедренных на ряде промышленных предприятий.
Подтвержденный экономический эффект от внедрения результатов диссертационной работы в промышленности составил 830 тысяч рублей (в ценах 1991 года).
По защищаемому научному направлению под руководством автора подготовлены и успешно защищены три кандидатских диссертации.
Апробация работы. Основные научные результаты, положения и выводы диссертационной работы были представлены и одобрены на Международном семинаре по проблеме реализации комплексной программы научно-технического прогресса стран - членов СЭВ до 2000 года (г. Кишинев 1987), Международной конференции по автоматизированным техническим системам (г.г. Евпатория, Москва 1990), 6-ом Международном симпозиуме "Системы, Моделирование, Управление" (SMC-6) (г. Закопане 1990), 18-ом конгрессе Румыно-Американской Академии науки и искусства (г. Кишинев 1993), Всесоюзной НТК "ИИС-81" (г. Львов 1981), на семинаре "функциональный контроль изделий микроэлектроники" (г. Ленинград 1982), Республиканской НТК "Структурные методы повышения точности средств и систем автоматизации экспериментальных исследований" (г. Киев 1989), на 5-й Всесоюзной НТК "Проблемы метрологического обеспечения систем обработки измерительной информации" {г.г. Суздаль, Москва 1984), 5-ом Всесоюзном симпозиуме по модульным ИВС (г. Кишинев 1985), 7-й Всесоюзной НТК "ИИС-87" (г. Ташкент 1987), 11-й Всесоюзной НТК "Метрологическое обеспечение ИИС и АСУ ТП" (г. Львов 1988), на XXX Всесоюзной школе-семинаре им. М. И. Гаврилова (г. Кишинев 1988), на XI НТК "Проблемы разработки измерительных приборов со встроенным интеллектом и перпективы их развития" (г. Каунас 1988), I Всесоюзной школе-семинаре "Разработка и внедрение в народное хозяйство персональных ЭВМ" (г. Минек 1988), XXIII Всесоюзной школе-семинаре по автоматизации научных исследований (г. Кишинев 1989), Республиканском семинаре "Техническая диагностика и эксплуатация вычислительных управляющих систем" (г. Киев 1989), Республиканском семинаре "Вопросы разработки вычислительной техники" (г. Кишинев
1989), Республиканской НТК "Проблемы автоматизации контроля электронных устройств" (г. Киев 1990), Всесоюзной НТК "Моделирование - 91" (г. Кишинев 1991), а также на некоторых других конференциях, совещаниях и семинарах.
По теме диссертации опубликовано 70 научных работ, в том числе б авторских свидетельств СССР на изобретения, статьи в журналах "Электронное моделирование", "Автоматика и телемеханика", "Автоматика и вычислительная техника", "Приборы и системы управления", "Управлякщие системы и машины", "Приборостроение", "Известия Академии наук Молдовы", "Измерительная техника", "Техника средств связи", "Измерения, контроль, автоматизация", "Вопросы радиоэлектроники", "Вопросы специальной радиоэлектроники", "Fuzzy System & A. I. Magazln", "Computer Sciences of Moldova" и других изданиях.
Объем и структура диссертации, диссертация содержит 242 страницы основного текста, состоит из введения, семи глав, заключения, списка использованной литературы из 222 наименований, а также приложения, содержащего информацию о внедрении результатов диссертационной работы в промышленности. Работа иллюстрирована 26 рисунками.
Автор выражает искреннюю благодарность Члену-корреспонденту АН Молдовы, заслуженному деятелю науки, д. т. н., профессору И. Ф. Клисторину и д. т. н., профессору В. И. Борщевичу за конструктивную критику результатов научных исследований, а также за поддержку, оказанную ими в процессе оформления работы.
