автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Оптимизационные методы формирования мультиверсионного программного обеспечения критичных по надежности систем управления

ВВЕДЕНИЕ.

ГЛАВА 1. ПРОБЛЕМА ПРОЕКТИРОВАНИЯ

ВЫСОКОНАДЕЖНЫХ СИСТЕМ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

1.1. Программная составляющая критичных по надежности систем управления.

1.2. Проектирование сложных программных средств.

1.2.1. Жизненный цикл программных средств.

1.2.2. Этапы проектирования сложных программных средств.

1.2.3. Комплексирование программ.

1.3. Надежность функционирования комплексов программ.

1.3.1. Надежностная характеристика программного модуля.

1.3.2. Обеспечение надежности программ с помощью введения избыточности.

1.4. Мультиверсионное программирование как методология проектирования отказоустойчивого программного обеспечения.

Выводы.

ГЛАВА 2. ТЕОРЕТИЧЕСКОЕ ИССЛЕДОВАНИЕ

ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ.

2.1. Оптимизационные модели мультиверсионного программирования критичных по надежности систем управления.

2.1.1. Модель с последовательной организацией программных модулей.

2.1.2. Модель с последовательно-параллельной организацией программных модулей.

2.2. Свойства пространства булевых переменных.

2.3. Алгебра подкубов на множестве булевых переменных.

2.4. Программа визуального исследования свойств пространства булевых переменных.

2.4.1. Основные сведения.

2.4.2. Обзор интерфейса пользователя.

2.5. Свойства оптимизационных моделей.

Выводы.

ГЛАВА 3. МЕТОДЫ И АЛГОРИТМЫ РЕАЛИЗАЦИИ

ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ.

3.1. Принципы построения оптимизационных алгоритмов.

3.2. Регулярные алгоритмы оптимизации.

3.2.1. Алгоритмы неявного полного перебора.

3.2.2. Алгоритмы схемы метода ветвей и границ.

3.3. Алгоритмы случайного поиска.

3.3.1. Модификации алгоритма случайного поиска с адаптацией.

3.3.2. Алгоритм случайного поиска граничных точек.

3.4. Экспериментальное сравнение эффективности построенных алгоритмов.

Выводы.

ГЛАВА 4. ПРОГРАММНЫЕ СРЕДСТВА ФОРМИРОВАНИЯ МУЛЬТИВЕРСИОННОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

4.1. Основные сведения.

4.2. Программная реализация процедур поиска.

4.3. Графический интерфейс пользователя пакета решения задач формирования мультиверсионного программного обеспечения.

Выводы.

Проектирование современных критичных по надежности систем управления, выполняющих ключевые функции многих технологических процессов, проводится на базе универсальных или специализированных ЭВМ. Сложность подобных процессов наряду с моделями объекта управления определяет сложность программных средств системы управления. Тем самым от качества функционирования подобных систем зависят безопасность человеческих жизней и экономическая стабильность, как отдельных предприятий, так и целых регионов. В свою очередь, достижения последних лет в области полупроводниковой техники определили четкую зависимость качества функционирования автоматизированных систем управления от стабильности и безотказности программного обеспечения.

Одним из самых распространенных подходов к реализации программной отказоустойчивости является методология избыточности, зарекомендовавшая себя при проектировании аппаратной составляющей контуров управления. В то время, как разработка программного обеспечения имеет характерные особенности, накладывающие ограничения на реализацию программной составляющей критичных по надежности систем управления, методология мультиверсионного программирования, как один из подходов к реализации идеи введения избыточных аналогичных элементов в структуру системы программного обеспечения, на практике доказала свою эффективность. С использованием данной методологии были реализованы программные комплексы систем управления летательными аппаратами, атомными электростанциями и т.п.

В настоящий момент времени на этапе проектирования системы управления немалое значение приобретают время и финансовые средства, затраченные на разработку. Эффективность технологий проектирования программ отражается непосредственно на совокупных затратах на создание комплексов управления объектами. Кроме того, доступность инструментальных средств автоматизации разработки комплексов программного обеспечения определяет длительность создания комплекса программ и общую производительность труда специалистов в коллективе разработчиков [11, 16].

Формирование избыточного комплекса программ, как один из этапов проектирования мультиверсионного программного обеспечения, во многом определяет общие показатели производительности. Рациональное структурное построение программных комплексов гарантирует достаточно полное использование ресурсов ЭВМ, являющееся залогом качественного решения функциональных задач управления. В свою очередь задачи формирования структуры, которые решаются в любых программных средствах, абстрагированы от конкретной управляющей системы, что позволяет рассматривать методы их решения отдельно от целевого назначения системы управления.

Кроме того, технологические особенности проектирования комплексов программного обеспечения, дополняя проблему структурного программного проектирования, выводят ее в разряд общих проблем разработки методов и автоматизированных систем проектирования сложных программных комплексов. Потенциальная возможность широкого применения таких систем для различных программных средств делает рентабельной их разработку [43].

Поэтому проблеме формирования программных комплексов, проектируемых на основе принципов программной избыточности, в настоящее время уделяется значительное внимание. Проблематика проектирования программных комплексов с использованием методологии мультиверсионного программирования рассматривалась в работах А.Авижиениса, Н.Ашрафи, О.Бермана, М.Катлер, Дж.Ву, К.Яо, Р.К.Скотта, Д.МакАллистера, К.Е.Гросспитча и многих других. Однако, основной трудностью проводимых до сих пор исследований являлось отсутствие формальных теоретических методов, использующих единый терминологический базис. Следует отметить также и относительно невысокую эффективность используемых до настоящего момента времени методов формирования структуры комплекса мультиверсионного программного обеспечения.

Таким образом, высокая сложность и практическая значимость задачи проектирования программных комплексов критичных по надежности систем управления, строгая необходимость в построении единого базиса для решения описанной проблемы наряду с высокой практической и теоретической значимостью формального математического аппарата обусловили выбор темы диссертационного исследования и определили ее актуальность.

Целью диссер!ационной работы является разработка и обоснование оптимизационного аппарата решения задачи формирования мультиверсионного программного обеспечения критичных по надежности систем управления.

Для достижения поставленной цели решались следующие задачи:

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

- исследование свойств построенных оптимизационных моделей и определение класса оптимизационных задач;

- изучение свойств полученного класса оптимизационных задач, обоснование и построение математических методов и алгоритмов решения полученных задач оптимизации;

- программная реализация и тестирование построенных алгоритмов.

Методы исследования. Для решения поставленных задач использовался аппарат теории множеств, теории вероятностей, исследования операций, дискретной оптимизации, математического программирования.

Научная новизна результатов, полученных в диссертации, состоит в следующем:

1. Впервые построены оптимизационные модели формирования мультиверсионного программного обеспечения в виде задач условной псевдобулевой оптимизации.

2. С применением новых понятий определены свойства подкубов в пространстве булевых переменных, позволяющие разработать эффективные регулярные алгоритмы решения задач условной

• псевдобулевой оптимизации.

3. Разработаны алгоритмы случайного поиска для решения оптимизационных моделей высокой размерности и теоретически определены области эффективного применения построенных алгоритмов.

4. Разработано математическое и алгоритмическое обеспечение в виде пакета приложений для исследования свойств пространства булевых переменных и решения задач формирования мультиверсионного программного обеспечения.

Практическое значение. Диссертационная работа выполнялась в рамках комплексной программы "Технология и оборудование современных процессов (Прогресс-99)" и по проектам межотраслевых программ Минобразования России и Минатома России по направлению "Научно-инновационное сотрудничество" (проект VII-12), а также в рамках тематического плана НИР НИИ СУВПТ (2000-2002 гг.), финансируемых из средств федерального бюджета.

Основные защищаемые положения.

1. Задачи формирования мультиверсионного программного обеспечения адекватно формализуются в виде задач условной оптимизации псевдобулевых функций.

2. Утилизация выявленных свойств оптимизационных моделей позволяет построить эффективные точные алгоритмы решения задач условной оптимизации монотонных псевдобулевых функций.

3. При решении задач формирования мультиверсионного программного обеспечения большой размерности для обеспечения требуемого качества решения целесообразен переход к субоптимальным процедурам случайного поиска.

4. Разработанное алгоритмическое и программное обеспечение позволяет эффективно решать задачи формирования мультиверсионного программного обеспечения критичных по надежности систем управления (в общем случае оптимизационные задачи "рюкзачного типа").

Публикации.

По теме диссертации опубликовано 12 печатных работ. Список основных публикаций автора по теме диссертации приведен в конце автореферата.

Апробация работы. Основные положения и отдельные результаты диссертационной работы докладывались и обсуждались на Всероссийских конференциях "Решетневские чтения" (1998-2000 гг.), на международной конференции "Современные техника и технологии" (г. Томск) в 2000 году, на международной научно-технической конференции "Информационные технологии в инновационных проектах" (г. Ижевск) в 2000 году, на международной конференции Information Systems Modelling '01 (г. Градец над Моравици, Чехия) в 2001 году, на международной конференции Architecture of Computing Systems (г. Карлсруэ, Германия) в 2002 году.

Диссертационная работа в целом обсуждалась на научных семинарах кафедры системного анализа и исследования операций Сибирской аэрокосмической академии (2000-2002), на семинарах НИИ СУВПТ, Института автономных интеллектуальных систем Немецкого национального исследовательского центра информационных технологий (GMD), г. Санкт-Августин, Германия (2001) и Института теории информации и автоматизации, г. Прага, Чехия (2001).

Основные результаты исследований были отмечены следующими научными фондами:

- Красноярский краевой фонд науки (стипендия для молодых ученых, 2000г.).

- Научный фонд Президента Российской Федерации (стипендия для обучения за рубежом, сентябрь 2000г. - июнь 2001г.). Стажировка проходила в Институте теории информации и автоматизации Чешской Академии Наук, г. Прага, Чехия.

- Немецкая служба академических обменов (DAAD) (стипендия аспирантов и молодых ученых для прохождения научной стажировки в Германии, август 2001г. - январь 2002г.). Стажировка проходила в Институте интеллектуальных автономных систем Немецкого национального исследовательского центра информационных технологий (GMD), г. Санкт-Августин, Германия.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы и приложений.

Основные результаты, содержащиеся в диссертации, изложены в работах [15, 32, 33, 34, 35, 36, 37, 38, 79, 86, 87, 88].

ЗАКЛЮЧЕНИЕ

На основе общих тенденций развития технологий проектирования высоконадежных комплексов программных средств и с использованием методов теории дискретной оптимизации были предложены способы решения задачи формирования мультиверсионного программного обеспечения критичных по надежности систем управления. Решение этой проблемы базируется на следующих основных результатах, имеющих самостоятельное научное и практическое значение.

1. Проведен анализ и формализация задачи формирования мультиверсионного программного обеспечения критичных по надежности систем управления в виде задачи условной псевдобулевой оптимизации.

2. Исследованы свойства построенных оптимизационных моделей и выделен класс оптимизационных задач в составе моделей.

3. Реализованы программные средства с целью изучения отношений в пространстве булевых переменных и исследования свойств класса оптимизационных задач.

4. С применением новых понятий исследованы свойства подкубов в пространстве булевых переменных, изучены свойства класса оптимизационных задач.

5. Обоснованы и построены регулярные математические методы и алгоритмы, позволяющие определить точное решение построенных задач оптимизации.

6. Для обеспечения требуемого качества решения задач формирования мультиверсионного программного обеспечения большой размерности построены субоптимальные процедуры случайного поиска, в том числе модифицированы известные ранее алгоритмы схемы метода изменяющихся вероятностей.

7. Выполнена программная реализация разработанного математического и алгоритмического обеспечения решения задач формирования мультиверсионного программного обеспечения критичных по надежности систем.

1. Антамошкин А.Н. Об одной задаче оптимизации с булевыми переменными. - Автоматика и вычислительная техника, 1981, №6, с. 54-56.

2. Антамошкин А.Н. Оптимизация функционалов с булевыми переменными. Томск: Изд-во Том. ун-та, 1987. 104 с.

3. Антамошкин А.Н. Регулярная оптимизация псевдобулевых функций. -Красноярск: Изд-во Краснояр. ун-та, 1989. 160 с.

4. Антамошкин А.Н. Сравнительная эффективность алгоритмов случайного поиска. Томский Государственный университет, Томск, 1979. 192 с.

5. Антамошкин А.Н. Экспериментальное исследование сравнительной эффективности алгоритмов случайного поиска при минимизации исходного описания. В кн.: Применения случайного поиска. Кемерово: НТО, 1979, с. 34, 35.

6. Буч Г. Объектно-ориентированный анализ и проектирование с примерами на С++. М.: БИНОМ, 1998. 560 с.

7. Гайсарян С.С. Объектно-ориентированные технологии проектирования прикладных программных систем, Центр информационных технологий, www.citforum.ru.

8. Гантер Р. Методы управления проектированием программного обеспечения: Пер. с англ./Под ред. Е. К. Масловского. -М.: Мир, 1981. 392 с.

9. Гене Г. В., Левнер Е. В. Дискретные оптимизационные задачи и эффективные приближенные алгоритмы (обзор). Известия АН СССР. Техническая кибернетика, 1976, № 6, с. 84-92.

10. Гене Г. В., Левнер Е. В. Эффективные приближенные алгоритмы для комбинаторных задач. М., 1981. - 68 с.

11. Давыдов И.Н., Привалов А.С., Ступина А.А. Технология надежностного программирования задач автоматизации управления в технических системах. Красноярск: НИИ СУВПТ и НИИ ИПУ. 2000. 207 с.

12. Журавлев Ю. И. Финкелынтейн Ю. Ю. Локальные алгоритмы для задач линейного целочисленного программирования. В кн.: Проблемы кибернетики. М.: Наука, 1965, вып. 14, с. 289-295.

13. Подан Э. Структурное проектирование и конструирование программ: Пер. с англ./Под ред. Л. Н. Королева. М.: Мир, 1979. 416 с.

14. Ковалев И. В. Система мультиверсионного формирования программного обеспечения управления космическими аппаратами. Диссертация на соискание ученой степени доктора технических наук. Красноярск: КГТУ, 1997.238 с.

15. Ковалев И.В., Ступина А.А. Модельное и алгоритмическое обеспечение средств автоматизированного формирования технологических циклов управления// КГТУ: Сб. научн. трудов; под ред. Б.П.Соустина/ КГТУ. Вып.5. Красноярск , 1996. С. 55-63.

16. Ковалев М. М. Дискретная оптимизация (целочисленное программирование). -Минскб 1977. 191 с.

17. Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование. -М.: Наукаб 1969.368 с.

18. Кошкин Ю.Г. Эффективные алгоритмы решения комбинаторных задач управления космическими аппаратами. Диссертация на соискание ученой степени кандидата технических наук. Красноярск: САА, 1994. 139 с.

19. Кошкин Ю.Г., Ступина А.Ф. Традиционные схемы случайного поиска в пространстве булевых переменных// КГТУ: Информатика и системы управления; под ред. Б.П.Соустина/ НИИ ИПУ, вып. 2. Красноярск, 1997. С. 96101.

20. Лбов Г. С. Выбор эффективной системы зависимых признаков. В кн.: Вычислительные системы. Новосибирск: ИМ СО АН СССР, 1965, вып. 19, с. 21-34.

21. Лбов Г. С. Программа "Случайный поиск с адаптацией для выбора эффективной системы зависимых признаков". В кн.: Геология и математика. Новосибирск: Наука, 1970, с. 204-219.

22. Лесков Д. О. Тестирование алгоритма решения задач рюкзачного типа на основе метода ветвей и границ с релаксацией// Вестник НИИ СУВПТ: Адаптивные системы моделирования и адаптации. Красноярск: НИИ СУВПТ, 2000.-с. 59-61.

23. Липаев В. В. Качество программного обеспечения. М.: Финансы и статистика, 1983. - 263 с.

24. Липаев В. В. Проектирование математического обеспечения АСУ. -М.: Советское радио, 1977. 400 с.

25. Липаев В. В. Проектирование программных средств: Учеб. пособие для вузов по спец. "Автом. сист. обр. информ. и упр.". М.: Высшая школа, 1990.-303 с.

26. Липаев В. В., Потапов А. И. Оценка затрат на разработку программных средств. М.: Финансы и статистика, 1988. 224 с.

27. Липаев В. В. Тестирование программ. М.: Радио и связь, 1986. 292 с.

28. Лонгботтом Р. Надежность вычислительных систем: Пер. с англ./Под ред. П. П. Пархоменко. -М.: Энергоатомиздат, 1985. 288 с.

29. Майерс Г. Надежность программного обеспечения: Пер. с англ. Галимова Ю. Ю./Под ред. В. Ш. Кауфмана. М.: Мир, 1980. 360 с.

30. Мамиконов А. Г. Проектирование АСУ. М.: Высшая школа, 1987. 304 с.

31. Попов А.А. Оптимальное проектирование систем управления на основе применения подхода мультиверсионного программирования и метода изменяющихся вероятностей// В сб.: Информатика и процессы управления №4. Красноярск: КГТУ, 1999. - с.

32. Попов А.А. Пересечение классов псевдобулевых функций// В сб.: Информатика и процессы управления №3. Красноярск: КГТУ, 1998. - с.

33. Попов А.А. Сепарабельность и монотонность псевдобулевых функций// Решетневские чтения: Материалы Всерос. научно-практ. конф. студентов, аспирантов и молодых специалистов. Вып. 2. - Красноярск: САА, 1998.-c.179.

34. Попов А.А. Средства автоматизации проектирования систем отказоустойчивого программного обеспечения// Решетневские чтения: Материалы Всерос. научно-практ. конф. студентов, аспирантов и молодых специалистов. Вып.4. - Красноярск: САА, 2000. - с.181-182.

35. Растригин JI. А. Бинаризация задач оптимизации решений в САПР. В кн.: Моделирование и оптимизация проектных решений в САПР. Таллин, 1983, ч. 2, с. 84-87.

36. Сараев В. Н. Пакет прикладных программ "Оптимизация функционалов с булевыми переменными". В кн.: Применения случайного поиска. Кемерово, 1981, вып. 2, с. 105-110.

37. Семенкин Е. С., Семенкина О. Э., Коробейников С. П. Адаптивные поисковые методы оптимизации сложных систем. Красноярск: СИБУП, 1996. 358 с.

38. Сергиенко И. В., Лебедева Т. Т., Рощин В. А. Приближенные методы решения дискретных задач оптимизации. Киев: Наукова думка, 1981. - 272 с.

39. Стоян Ю. Г. Об одном отображении комбинаторных множеств в евклидово пространство. Харьков, 1982. - 33 с. (Препринт/ИПМаш АН УССР)

40. Страуструп Б. Язык программирования С++: пер. с англ. СПб.: БИНОМ, 1999.-991 с.

41. Технология проектирования комплексов программ АСУ/В. В. Липаев, Л. А. Серебровский, П. Г. Гаганов и др.; Под ред. Ю. В. Асафьева и В. В. Липаева. М.: Радио и связь, 1983. 264 с.

42. Трахтенгерц Э. А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. М.: Наука, 1981. 256 с.

43. Финкелыптейн Ю. Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. - 264 с.

44. Фокс Дж. Программное обеспечение и его разработка: Пер. с англ./Под ред. Д. Б. Подшивалова. -М.: Мир, 1985. 268 с.

45. Хетагуров Я. А., Древе Ю. Г. Проектирование информационно-вычислительных комплексов. -М.: Высшая школа, 1987. 280 с.

46. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975.-534 с.

47. Шилдт Г. Теория и практика С++: пер. с англ. СПб.: BHV Санкт-Петербург, 2000. - 416 с.

48. Янг Ч. Алгоритмические языки реального времени. Конструирование и разработка: Пре. с англ./Под ред. В. В. Мартынюка. М.: Мир, 1985. 400 с.

49. Т. Anderson. A structured decision mechanism for diverse software. In Proc 5th Symposium on Reliability in Distributed Software and Database Systems, pp. 125-129, Los Angeles, CA, January 1986.

50. A. Antamoshkin, A. Stupina. On class of functions with binary variables// Proceedings of International AMSE Conference on Modelling and Simulation, Universidade de Santiago de Compastela 1999, Vol I. Pp. 31-37.

51. O. Antamoshkina, I. Kovalev. Modeling, Optimization, and Computer-Realization of Control Cyclograms. Krasnoyarsk: SAA-Press, 1996. 74 p.

52. N. Ashrafi, O. Berman, M. Cutler. Optimal Design of Large Software Systems Using N-Version Programming. In IEEE Transactions on Reliability, vol. 43, No. 2,1994 Jun, pp. 344-350.

53. N. Ashrafi, O. Berman. Optimization models for selection of programs, considering cost & reliability. In IEEE Trans. Reliability, vol. 41, 1992 Jun, pp. 281287.

54. A. Avizienis and L. Chen. On the implementation of N-version programming for software fault-tolerance during execution. In Proc. IEEE COMPSAC 77, pp. 149-155, November 1977.

55. A. Avizienis. Design diversity the challenge for the eighties. In Digest of 12th FTCS, pp. 44-45, Santa Monica, CA, June 1982.

56. A. Avizienis. Fault tolerance and fault intolerance: complementary approaches to reliable computing. In Proc. 1975 International Conference on Reliable Software, pp. 458-464, April 1975.

57. A. Avizienis. Fault-tolerant computing progress, problems, and prospects. In Information Processing 77, Proc. Of IFIP Congress, pp. 405-420, Toronto, Canada, August 1977.

58. A. Avizienis. The methodology of N-version programming. In Software fault-tolerance/ edited by Lyu M. R., pp. 23-47, Wiley, 1995.

59. A. Avizienis, H. Kopetz, and J. C. Laprie, editors. The Evolution of Fault-Tolerant Computing. Springer, Wien, New York, 1987.

60. A. Avizienis, M. R. Lyu, W. Schuetz., K-S. Tso, and U. Voges. DEDIX 87 A supervisory system for design diversity experiments at UCLA. In Digest of 18th FTCS, pp. 129-168, Tokyo, Japan, June 1988.

61. O. Berman, N. Ashrafi. Optimization models for reliability of modular software systems. In IEEE Trans. Software Engineering, vol. 19, 1993 Dec, pp. 11191123.

62. O. Berman, M. Cutler. Choosing an Optimal Set of Libraries. In IEEE Trans. Reliability, vol. 45, No. 2,1996 June, pp. 303-307.

63. B. W. Bohem. Software Engineering Economics. Prentice-Hall, 1981.

64. J. J. Chen. Software Diversity and Its Implications in the N-version Software Life Cycle. PhD dissertation, UCLA, Computer Science Department, 1990.

65. H. Crowder, E. L. Johnson, M. W. Padberg. Solving Large-Scale Zero-One Linear Programming Problems. Rapports de Recherche №89, Institut de Recherche en Informatique et en Automatique, 1981. 29 p.

66. W. R. Elmendorf. Fault-tolerant programming. In Digest of 2-nd FTCS, pp. 79-83, Newton, MA, June 1972.

67. M. A. Fischler, O. Firschein, and D. L. Drew. Distinct software: an approach to reliable computing. In Proc. 2nd US A-Japan Computer Conference, pp. 573-579, Tokyo, Japan, August 1975.

68. R. S. Garfinkel. Branch and Bound Methods for Integer Programming. In: Combinatorial Optimization, 1979. pp. 1-20.

69. E. Girard and J. С. Rault. A programming technique for software reliability. In Proc. 1973 IEEE Symposium on Computer Software Reliability, pp. 4450, New York, May 1973.

70. P. L. Hammer. Boolean Elements in Combinatorial Optimization. In: Annals of Discrete Mathematics 4, 1979. p. 51 -71.

71. P. L. Hammer (Ivanescu), Rudeanu S. Boolean Methods in Operations Research and Related Areas. Berlin: Springer-Verlag, 1968. 306 p.

72. H. Kopetz. Software redundancy in real time systems. In Information Processing 74, Proc. Of IFIP Congress, pp. 182-186, Stockholm, Sweden, August 1974.

73. I. Kovalev, K.-E. Grosspietsch. Deriving the Optimal Structure of N-Version Software under Resource Requirements and Cost/Timing Constraints. In Proc. Euromicro '2000, IEEE CS Press, Maastricht, 2000, pp. 200-207.

74. I. Kovalev, A. Popov, Ju. Shipovalov. Optimization models for reliability of telecommunication software systems. In Advances in Modelling and Analysis, C, Vol. 43, №4, 2000, AMSE Press, Pp. 35-44.

75. J. K. Lenstra, A. H. G. Rinnooy Kan. Computational Complexity of Discrete Optimization Problems. In: Annals of Discrete Mathematics 4, 1979. p. 121140.

76. M. R. Lyu, Chen J. H., and A. Avizienis. Software diversity metrics and measurements. In Proc. IEEE COMPSAC 1992, pp. 69-78, Chicago, Illinois, September 1992.

77. S. Martello and Paolo Toth. The 0-1 Knapsack Problem. In: Combinatorial Optimization, 1979. pp. 237-279.

78. D. J. Musa. Software quality and reliability basics. In Proc. 1987 Fall Joint Computer Conf, 1987. pp. 114-115.

79. M. W. Padberg. A Note on zero-one programming. Operations Research 23,1975. pp. 833-837.

80. M. W. Padberg. Covering, Packing and Knapsack Problems. In: Annals of Discrete Mathematics 4, 1979. p. 265-287.

81. A. Popov, K.-E. Grosspietsch. A Methodology to Optimize Diversity Approaches for Imperfectly Specified Applications// In: proceedings of the International conference "Architecture of Computing Systems", Karlsruhe, Germany, 2002,-Pp. 65-72.

82. A. Popov. Optimal Design of Fault-Tolerant Software Systems Using Inversion Approach and Pseudo-Boolean Optimization Methods// "Modern Techniques and Technology": abstracts of the VI international conference; Tomsk, Russia: TPU, 2000 Pp. 53-55.

83. A. Popov. The binary model of fault-tolerant software system// Information Systems Modelling: proceedings of the International conference, Hradec nad Moravici, Czech Republic, 2001, Pp. 189-196.

84. B. Randell. Design fault tolerance, pp. 251 270. In 64.

85. R. M. Reiss. A prediction experience with three software reliability models. Workshop on Quantitative Software Models for Reliability, Complexity, Cost: An Assesment of the State of Art, 1979 October, pp. 190-200; IEEE Cat CH0067-9.

86. T. A. Silayeva, K.-E. Grosspietsch. An Innovative Method for Program Reliability Evaluation. Accepted for publication at Euromicro'95. Cosmo (Italy). September 1995.

87. R. K. Scott, D. F. McAllister. Cost Modeling of N-Version Fault-Tolerant Software Systems for Large N. In IEEE Transactions on Reliability, vol. 45, No. 2, 1996 June, pp. 297-302.

88. R. K. Scott, J. W. Gault, D. F. McAllister, and J. Wiggs. Experimental validation of six fault-tolerant software reliability models. In Digest of 14th FTCS, pp. 102-107, Orlando, FL, June 1984.

89. R. K. Scott, J. W. Gault, and D. F. McAllister. Fault-tolerant software reliability modeling. In IEEE Transactions on Software Engineering, SE-13(5): 582592, May 1987.

90. К. S. Shrivastava, editor. Reliable Computing Systems: Collected Papers of the Newcastle Reliability Project. Springer, Wien, New York, 1985.

91. A. Stupina. On optimization of isotone pseudoboolean functions// Proceedings of International AMSE Conference on Modelling and Simulation, Universidade de Santiago de Compastela 1999, Vol I. Pp. 63-75.

92. P. Traverse. AIRBUS and ATR system architecture and specification. In Software Diversity in Computerized Control Systems, pp. 95-104, Springer, Wien, New York, 1988.

93. F. Wang, K. Ramamritham, and J. A. Stankovic. Determining Redundancy Level for Fault Tolerant Real-Time Systems. In IEEE Transactions on Computers, vol. 44, No. 2, 1995 Feb, pp. 292-301.

94. R. Weismantel. On the 0/1 Knapsack Polytope. Konrad-Zuse-Zentrum fuer Informationstechnik, Berlin, 1994. 30 p.

95. J. Wu, K. Yao. Reliability Optimization of Concurrent Software with Redundancy. In Informatica 19,1995, pp. 291-300.

96. J. F. Williams, L. J. Yount, and J. B. Flannigan. Advanced autopilot flight director system computer architecture for Boeing 737-300 aircraft. In AIAA/IEEE 5th Digital Avionics Systems Conference, Seattle, WA, November 1983.

97. F. Zahedi, N. Ashrafi. Software reliability allocation based on structure, utility, price, and cost. In IEEE Trans. Software Engineering, vol. 17, 1991 Apr, pp. 345-356.

98. Элементы методики анализа статистических характеристик исходных текстов программных компонент мультиверсионного1. ПО

99. Базовое положение: на основе статистических исследований ряда авторов 14, 24. установлена зависимость числа ожидаемых первичных ошибок В в исходных текстах программ от объема V: B=Vt3000.

100. Для оценки числа ожидаемых ошибок в ПО на этапе разработки формализованных спецификаций используется соотношение, в котором производится замена реального объема комплекса программ на оценку объема комплекса Vk:54=^-2.1og5(Ft/1300)./3000.

101. Как показано в 24., это соотношение справедливо в диапазоне длин программ 2.6 • 103 < N < 105 ед.

102. Оценка числа ожидаемых ошибок в комплексе программ на этапе программирования:1. Bk=Vk/3000.2\og5[Vk/U00],где Vk объем программы экспериментальный. Это соотношение получено при ограничении Vk > 2600 бит.

103. Возможность оценки параметров мультиверсий модулей на стадии проектирования позволяет применять синтезированный состав такой мультиверсионной системы ПО для реализации систем управления критичных по надежности.j

104. Обнуление компонент вектора {for(int i=0;i<size;i++) data1.=0;void BooleanVector::SetOneVector(void) {for(int i=0;i<size;i++) data1.=l;

105. AnsiString BooleanVector::ToStr(void)

106. Возвращает вектор в виде строки {1. AnsiString temp="";for(int j=0;j<size;j ++) temp+=(dataj.) ? "1" : "0"; return temp;

107. BooleanVector fastcall BooleanVector::Neighbor(int k)1. Соседняя точка {1. BooleanVector temp(size);for(int i=0;i<size;i++) temp.data1.=datai.; temp.data[k]=!temp.data[k]; return temp;int BooleanVector::Module(void)

108. Модуль булевого вектора сумма его компонент {int m=0;for(int i=0;i<size;i++) m+=data1.; return m;void fastcall BooleanVector::SetFromDecimal (int x)

109. Представление десятичного числа в двойчной форме {if(x>pow2(size)-1) x=pow2(size)-1; for (int i=size-l;i>=0;i —) { datasize-l-i.=( (x/pow2(i))>0 ); x-=data[size-l-i]*pow2(i);

110. Значения компонент в виде одного десятичного сила {int г=0;for(int i=0;i<size;i++) r+=datasize-l-i.*pow2 (i); return r;fastcall SubCube::SubCube(int An)n=An ;

111. X0=new BooleanVector(n); Xl=new BooleanVector(n); Mask=new BooleanVector(n);fastcall SubCube::~SubCube()delete X0; delete XI; delete Mask;void SubCube::SetMask(void)

112. Формирование вектора-маски {nK=0 ;for(int i=0;i<n;i++) if((*X0)1.==(*X1)i.) (*Mask)[i]=true; else { (*Mask)[i]=false; nK++; }void fastcall SubCube::SetMask(BooleanVector *VM)

113. Назначение вектора-маски {if(n!=VM->GetSize()) { n=VM->GetSize() ; XO->SetSize(n); Xl->SetSize(n); Mask->SetSize(n);nK=0 ;for(int i=0;i<n;i++) { (*Mask)1.=(*VM)i.; if((*Mask)[i]) nK++;

114. BooleanVector temp(n); int il=0;for(int i=0;i<n;i++) if((*Mask)1.) tempi.=(*X0)[i]; else { temp[i]=(*AX)[il]; il++; } return temp;void fastcall SubCube::

115. Определение принадлежности точки AX подкубу {for(int i=0;i<n;i++) if((*Mask)1.) if((*AX)i.!=(*X0)[i]) return false; return true;

116. Version **Versions; // Версии fastcall Module(int uS=l);

117. TList *В; // Список векторов принадлежности задач классам

118. Versions=new Version*NumberOfVersions.; for(int i=0;i<NumberOfVersions;i++) Versions1.=new Version;

119. Modules Module::operator =(Module &C) // Оператор присваивания {if(this==&C) return *this;

120. ChangeNumberOfVersions(С.NumberOfVersions); for (int i=0;i<NumberOfVersions;i++)

121. FileName=AFileName; return Save();

122. U--------------------------------------------------fastcall NVS1::NVS1(int ul, int uJ)1. FJ=FI=0; J=uJ;

123. Modules=new Module*J.; for(int j=0;j<J;j++)

124. Modulesj.=new Module (); I=ul;

125. B.ChangeSize (I); G.ChangeSize (I); X.SetSize(XDimension() ) ;int NVS1::XDimension(void) {int i,summ=0;for(i=0;i<FI;i++)summ+=ModulesB1.-1.->GetNumberOfVersions(); return summ;int NVS1::SetI(int Value) {if(FI==Value) return Value; FI=Value;

126. X. SetSize(XDimension() ) ; return newJ;void NVS1::SetB(int i,int Value) {1. В1.=Value; UpdateG () ;

127. X. SetSize(XDimension() ) ;void NVS1::SetNumberOfVersions(int i,int s) {

128. Modules 1.->ChangeNumberOfVersions(s); UpdateG();

129. X. SetSize(XDimension() ) ;void NVS1::SetReliability(int i,int s,float v) {

130. Modules1.->Versionss.->Reliability=v;void NVS1::SetCost(int i, int s,float v) {

131. Modules1.->Versionss.->Cost=v;void fastcall NVS1::UpdateG(void)1. G.ChangeSize(FI);

132. RM=new float1.; for(i=0;i<I;i++) { RM1.=1;for(j=0;j<ModulesB1.-1.->GetNumberOfVersions();j++) RM[i]*=pow(1-Modules[B[i]-1]->Versions[j]^Reliability, (*AX)[IStoPOS(i,j) ] ) ; RM[i]=l-RM[i];for(i=0;i<I;i++)

133. TR*=RM1.; delete RM; return TR;float fastcall NVS1::Cost(void)return Cost(&X);float fastcall NVS1::Cost(BooleanVector* AX)float TC=0; int i, s ;for(i=0;i<I;i++)for(s=0;s<ModulesB1.-1.->GetNumberOfVersions();s++) TC+=

134. Распознавание формата файла

135. FileRead(iFileHandle,format,32*sizeof(char));format32.=1\x0';int a=strcmp("N-Version System. Formulation #1",format); if (a)

136. FileClose(iFileHandle); return false;1. Чтение параметров системы

137. FileRead(iFileHandle,&i,sizeof(int)); 11 Прочитали число задач I=i;

138. FileRead(iFileHandle,&i,sizeof(int)); // Прочитали число классов задач J=i;for(i=0;i<I;i++)

139. FileRead(iFileHandle,&B1.,sizeof(int)); for(j=0;j<J;j++)

140. FileRead(iFileHandle,&i,sizeof(int)); Modulesj.->ChangeNumberOfVersions(i);1. UpdateG();for(j=0;j<J;j++)for (i=0; i<Modules j . ->GetNuraberOfVersions () ; i++) { FileRead(iFileHandle,

141. Modulesj.->Versions1.->Reliability), sizeof(float)); FileRead(iFileHandle,

142. Modulesj.->Versions1.->Cost), sizeof(float));1. X.SetSize(XDimension());

143. FileRead(iFileHandle,SBudget,sizeof(float));

144. FileRead(iFileHandle,&Chk,sizeof(bool));

145. ConditionVersionPerModule=Chk;

146. FileRead(iFileHandle,&Chk,sizeof(bool));1. ConditionOddVersions=Chk;

147. FileRead(iFileHandle,&Chk, sizeof(bool));

148. N-Version System. Formulation #1",32*sizeof(char));

149. FileWrite(iFileHandle,&I,sizeof(int)); // Сохранили число задач FileWrite(iFileHandle,&J,sizeof(int)); // Сохранили число классов задачfor(i=0;i<I;i++) // Принадлежность задач классам

150. Modulesj.->Versions1.->Reliability), sizeof(float)); FileWrite(iFileHandle,

151. Modulesj.->Versions1.->Cost), sizeof(float));

152. FileWrite(iFileHandle,&Budget,sizeof(float));

153. B=new TList; for(int i=0;i<I;i++) { TempVec=new vector; В->Add(TempVeс);

154. G.ChangeSize(I); Modules=new Module*J.; for(int j=0;j<J;j++)

155. TempVec=new vector; B->Add(TempVec);