Мультиверсионное программное обеспечение. Алгоритмы голосования и оценка надёжности

Р. Ю. Царев
А. В. Штарик
Е. Н. Штарик

Монография

Институт космических и информационных технологий

мультиВЕРсиоННоЕ 
пРогРАммНоЕ  обЕспЕчЕНиЕ. 
АлгоРитмы  голосоВАНия 
и  оЦЕНкА  НАдёжНости

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

9 785763 827491

ISBN 978-5-7638-2749-1

Министерство образования и науки Российской Федерации 
Сибирский федеральный университет 
 
 
 
 
 
 
 
 
 
Р. Ю. Царев, А. В. Штарик, Е. Н. Штарик 
 
 
МУЛЬТИВЕРСИОННОЕ  
ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ.  
АЛГОРИТМЫ ГОЛОСОВАНИЯ  
И ОЦЕНКА НАДЁЖНОСТИ 
 
 
Монография 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Красноярск 
СФУ 
2013 

УДК 004.451.46 
ББК 32.973.233-018 
        Ц181  
 
 
 
Рецензенты:  
А. Н. Антамошкин, доктор технических наук, профессор, зав. кафедрой математического моделирования и информатики КрасГАУ; 
А. В. Медведев, доктор технических наук, профессор кафедры системного анализа и исследования операций СибГАУ им. М. Ф. Решетнёва 
 
 
 
 
 
 
 
Царев, Р. Ю. 
Ц181 Мультиверсионное программное обеспечение. Алгоритмы голосования и оценка надёжности : монография / Р. Ю. Царев, А. В. Штарик, 
Е. Н. Штарик. – Красноярск : Сиб. федер. ун-т, 2013. – 120 c. 
ISBN 978-5-7638-2749-1 
 
В монографии представлены современные алгоритмы голосования, используемые в мультиверсионном программном обеспечении при принятии решения о корректности полученных результатов; приведена их классификация. 
Рассмотрены проблемы применения алгоритмов голосования в мультиверсионном программном обеспечении. Показана модель оценки надёжности мультиверсионного программного обеспечения, представлены результаты ее исследования при имитировании поведения реальной мультиверсионной системы с распределенной архитектурой. 
Результаты исследования служат теоретической базой для разработки высоконадёжного и отказоустойчивого программного обеспечения на основе мультиверсионной парадигмы. 
Предназначено специалистам, работающим в области проектирования и 
разработки программного обеспечения, а также аспирантам и докторантам. Материалы монографии рекомендуются к использованию при проведении лекционных и практических занятий у магистрантов, обучающихся по программе подготовки магистров 230100.68 «Информатика и вычислительная техника». 
 
УДК 004.451.46 
ББК 32.973.233-018 
 
ISBN 978-5-7638-2749-1                                                              © Сибирский федеральный  
                                                                                                            университет, 2013 

ОГЛАВЛЕНИЕ 
 
ВВЕДЕНИЕ……………………………………………………………… 
5
1. МУЛЬТИВЕРСИОННОЕ  ПРОГРАММНОЕ  ОБЕСПЕЧЕНИЕ 
    КАК  СПОСОБ  ПОВЫШЕНИЯ  НАДЁЖНОСТИ  
    ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ  СИСТЕМ…………….. 
7
1.1. Программный компонент систем управления  
       и обработки информации……………………………………….. 
7
1.2. Надёжность функционирования программного обеспечения 
9
1.2.1. Надёжностная характеристика программного модуля 
9
1.2.2. Обеспечение надёжности программ  
          с помощью введения избыточности……………………... 
14
1.3. Мультиверсионное программирование как методология  
       проектирования отказоустойчивого программного  
       обеспечения систем управления и обработки информации 
17
2. АЛГОРИТМЫ  ГОЛОСОВАНИЯ  В  МУЛЬТИВЕРСИОННОМ 
    ПРОГРАММНОМ  ОБЕСПЕЧЕНИИ……………………………….. 
22
2.1. Алгоритмы голосования, основанные  
       на сравнении выходных данных………………..……………… 
23
2.1.1. Неформализованные алгоритмы голосования………….. 
24
2.1.2. Формализованные алгоритмы голосования…………….. 
34
2.2. Алгоритмы с принятием решения вне зависимости  
       от схожести выходных данных………………………………… 
35
2.2.1. «Максимально вероятное» голосование (MLV)………… 
36
2.2.2. Усреднённое голосование………………………………… 
38
3. СПЕЦИФИКА  ПРИМЕНЕНИЯ  АЛГОРИТМОВ  
    ГОЛОСОВАНИЯ   В  МУЛЬТИВЕРСИОННОМ  
    ПРОГРАММНОМ  ОБЕСПЕЧЕНИИ  
    ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ  СИСТЕМ…………….. 
39
3.1. Неоднозначность принятия решения  
       в алгоритмах голосования согласованным большинством…… 
39
3.2. «Склеивание» подмножеств выходных данных……………….. 
49
3.3. Оценка результатов голосования……………………………….. 
55
3.4. Несовместность разбиений в алгоритмах с минимизацией…… 
58
3.5. Выбор значения -сечения в нечётких алгоритмах……………. 
59
3.6. Комплексное применение алгоритмов голосования  
       в мультиверсионном программном обеспечении……………… 
62
4. ПРАКТИЧЕСКОЕ  ПРИМЕНЕНИЕ  АЛГОРИТМОВ  
    ГОЛОСОВАНИЯ  В  МУЛЬТИВЕРСИОННОМ  
    ПРОГРАММНОМ  ОБЕСПЕЧЕНИИ………………………………. 
70
4.1. Программа NVX…………………………………………………. 
70
4.1.1. Особенности программы…………………………………. 
70

4.1.2. Взаимодействие с исполняемыми версиями……………. 
71
4.1.3. Общая схема работы программы………………………… 
72
4.1.4. Обобщенная схема работы версий………………………. 
74
4.1.5. Требования к разработке версий…………………………. 
75
4.2. Программа NVX-m………………………………………………. 
75
5. МОДЕЛИ  И  МЕТОДЫ  ОЦЕНКИ  НАДЁЖНОСТИ  
    ПРОГРАММНОГО  ОБЕСПЕЧЕНИЯ……………………………… 
78
5.1. Модель анализа на этапе дизайна архитектуры  
       программного обеспечения……………………………………… 
79
5.2. Анализ надёжности программного обеспечения  
       на фазе кодирования……………………………………………... 
81
5.3. Анализ надёжности программного обеспечения  
       на фазе тестирования системы………………………………….. 
82
5.4. Модель оценки транзакционной надёжности  
       объектно-ориентированного программного обеспечения…….. 
83
5.5. Универсальная модель оценки надёжности  
       объектно-ориентированного мультиверсионного  
       программного обеспечения с распределенной архитектурой 
84
6. ПРАКТИЧЕСКОЕ  ПРИМЕНЕНИЕ  МОДЕЛЕЙ  И  МЕТОДОВ 
    ОЦЕНКИ  НАДЁЖНОСТИ  ПРОГРАММНОГО  ОБЕСПЕЧЕНИЯ 
86
6.1. Система SMR……………………………………………………. 
86
6.1.1. Назначение и общие сведения  
          о системе поддержки принятия решений SMR…………. 
87
6.1.2. Структура информационной системы…………………… 
88
6.1.3. Описание основных подсистем…………………………... 
89
6.2. Результаты применения системы SMR………………….……… 
90
ЗАКЛЮЧЕНИЕ…………………………………………………………. 
98
БИБЛИОГРАФИЧЕСКИЙ СПИСОК…………………………………. 
100
Приложение 1. Применение алгоритма выбора значения  
                           λ-сечения CVS………………………………………… 
109
Приложение 2. Условия успешного применения  
                           алгоритмов голосования……………………………… 
116
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ 
 
 
Информационно-управляющие системы (ИУС) характеризуются 
сложной структурой и большим числом взаимосвязей между подсистемами. Объекты управления и сама система управления распределены в пространстве, обладают избыточностью основных элементов и подсистем, 
процесс управления включает в себя сложные расчеты и обработку большого объема информации. Повышение уровня сложности ИУС требует 
учета целого набора параметров или атрибутов, на основе которых формируется состав систем управления и обработки информации. 
Отказ подсистем ИУС при выполнении функций по управлению и 
обработке информации может привести к утрате информации и значительным финансовым потерям. Это определяет повышенные требования по надёжности к системам данного класса. 
Реализация процессов управления и обработки информации в ИУС       
в большой степени зависит от программного обеспечения (ПО) системы. 
Таким образом, надёжность ПО во многом определяет надёжность всей 
АСУ спутниковой системой связи в целом. Информационно-управляющие 
системы, применяемые в критичных областях (контроль полётов, атомная 
промышленность и др.) должны быть максимально надежными. Решающую роль в обеспечении надёжности информационно-управляющих систем играет программный компонент.  
На сегодняшний день существует ряд методов повышения надёжности программного обеспечения информационно-управляющих систем. 
Достаточно эффективным методом обеспечения надёжности ПО, положительно зарекомендовавшим себя на практике, является концепция мультиверсий [1; 5; 1319; 25; 2940; 47; 5052; 5768; 70; 7275; 7778; 80; 
8292; 9699; 101102; 105108; 110113; 115; 119].  
Применяя методологию мультиверсионного формирования программных средств, можно не только обеспечить заданный уровень надёжности, но и гарантировать отказоустойчивость систем управления и обработки информации. Данная методология основывается на программной  
избыточности, введение которой позволяет существенно повысить уровень 
надёжности программной составляющей ИУС. 
Большое количество модулей программного обеспечения, их дополнительные избыточные версии, а также ограничения такие, например, как 
стоимость, объем оперативной и дисковой памяти, требуемое время          
исполнения ставят перед проектировщиком задачу принятия решений по 
выбору состава мультиверсионного программного обеспечения с учетом, 
как правило, ряда атрибутов. 

Методы многоатрибутивного принятия решений, ориентированные 
на класс задач, где множество альтернатив дискретно и, конечно, позволяют произвести эффективный выбор лучшего варианта формирования 
мультиверсионного программного обеспечения ИУС.  
Формирование мультиверсионного программного обеспечения согласно спецификации позволяет привлекать к разработке мультиверсионных компонент специалистов по управлению. Однако зачастую произвести 
выбор лучшего варианта лицу, принимающему решение (ЛПР), сложно 
ввиду большого количества рассматриваемых альтернатив. В связи с этим 
возникает техническая проблема – создание средств автоматизации принятия решений, а именно системы поддержки принятия решений, которая 
позволила бы выбрать состав мультиверсионного программного обеспечения ИУС. 
Поддержка принятия решения предполагает многовариантность решений. Таким образом, лицу, принимающему решение, для оценки и выбора должны предлагаться несколько лучших вариантов формирования 
мультиверсионного программного обеспечения ИУС. Разработка моделей 
и методов, предназначенных для решения данной проблемы, и их реализация в составе системы поддержки принятия решений, является актуальной 
научной проблемой.  
Мультиверсионный подход предполагает независимую генерацию          
и параллельное исполнение нескольких версий одного и того же программного модуля. При этом версии разрабатываются на основе идентичных исходных спецификаций. Концепция мультиверсий даёт ряд преимуществ, в частности, отказ одной версии не приведёт к отказу всей системы. 
Однако при использовании мультиверсионного подхода существует вероятность, что версии выдадут различные результаты. Таким образом, возникает необходимость определить, какие результаты являются корректными, 
а какие ошибочными.  
Задача может быть решена либо путём использования алгоритмов 
голосования, либо применением приёмочных тестов. Алгоритмы голосования в мультиверсионном ПО зарекомендовали себя как достоверный 
способ выбора корректных ответов из всего множества результатов работы 
версий.  
В настоящее время предложено множество алгоритмов голосования, 
которые различаются схемами работы и требованиями к исходным            
данным.  
Подчеркнём, что результат работы алгоритма голосования определяет 
итог работы всей мультиверсионной системы. Поэтому ошибка в процессе 
голосования может привести к отказу всей системы, и, соответственно,       
к значительным потерям.  
 

1.  МУЛЬТИВЕРСИОННОЕ  
ПРОГРАММНОЕ  ОБЕСПЕЧЕНИЕ  
КАК  СПОСОБ  ПОВЫШЕНИЯ  НАДЁЖНОСТИ  
 ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ  СИСТЕМ 
 
 
1.1. Программный компонент систем управления  
и обработки информации 
 
Современные системы управления и обработки информации строятся 
на базе универсальных или специализированных ЭВМ, при этом сложность 
процесса обработки данных и объекта управления определяет сложность 
программных средств автоматизированной системы. В связи с этим можно 
выделить следующие особенности программных средств как сложных систем [40; 48]. 
Наиболее существенными чертами сложных систем принято считать: 
● наличие общей задачи и единой цели функционирования для всей 
системы; 
● большое количество взаимодействующих частей или элементов, 
составляющих систему; 
● возможность расчленения на группы наиболее тесно взаимодействующих элементов – подсистемы, имеющие свое специальное назначение 
и цель функционирования; 
● иерархическую структуру связей подсистем и иерархию критериев 
качества функционирования всей системы; 
● сложность поведения системы, связанную со случайным характером внешних воздействий и большим количеством обратных связей внутри системы; 
● устойчивость по отношению к внешним и внутренним помехам            
и наличие самоорганизации и адаптации к различным возмущениям; 
● высокую надёжность системы в целом, построенной из неабсолютно 
надежных компонент. 
Программные системы (ПС) исполняются на различных типах ЭВМ, 
характеристики которых определяются назначением и сложностью.  
В системах управления в качестве реализующих ЭВМ могут применяться 
универсальные большие и мини-ЭВМ, а также персональные ЭВМ. Общие 
принципы технологии проектирования программного обеспечения для 
систем управления и обработки информации достаточно универсальны,          
и основные особенности проектирования связаны с назначением ПС,               
с доступными ресурсами применяемых ЭВМ, с соответствием их назначению и сложности решаемых программами задач. Эти факторы влияют на 

рациональный уровень автоматизации проектирования, на размер и сложность взаимодействия в коллективе разработчиков, на трудоёмкость и длительность создания программного обеспечения и т. д. Однако принципы           
и методы проектирования ПС при этом меняются относительно мало. 
Программные средства, использующиеся в системах управления           
и обработки данных, обладают всеми свойствами сложных систем. Они 
содержат большое количество компонентов – модулей, тесно взаимодействующих в процессе решения общей целевой задачи. 
Программное обеспечение систем управления и обработки данных 
имеет единую цель функционирования – обработку информации и принятие 
решений для управления объектами, вплоть до формирования соответствующих управляющих воздействий. Для обеспечения взаимодействия 
компонентов в едином комплексе широко используются иерархические 
структуры с несколькими уровнями группирования и подчиненности модулей. Каждый модуль имеет свою целевую задачу и специфический частный критерий качества, как правило, не совпадающий с критерием эффективности всего комплекса программ. Однако частные критерии качества 
модулей и групп программ играют подчиненную роль относительно критериев качества всего программного обеспечения информационно-управляющих систем и должны способствовать получению их допустимых или 
экстремальных значений. Иерархическая структура широко используется 
при анализе критериев качества всей программной системы и ее модулей. 
В сложных информационно-управляющих системах программное 
обеспечение обладает разнообразием функций, связано это с управлением 
несколькими разнотипными объектами и различным назначением обрабатываемой информации. Кроме того, сама программная система может             
является объектом управления для других систем более высокого ранга.  
В то же время управляющие программы сравнительно мало изменяются в течение длительного периода эксплуатации. Изменение характеристик или    
состава управляемых объектов, как правило, не вызывает фундаментальной 
переработки программ, так как возможность таких изменений обычно учитывается в процессе разработки. Управляющие ЭВМ, ориентированные на решение определенного класса задач, проектируются или выбираются с минимальными запасами вычислительных ресурсов. Значительная определенность 
задач, решаемых программными системами, позволяет весьма полно использовать аппаратуру и определять оптимальное соотношение между отдельными параметрами реализующих ЭВМ применительно к конкретным задачам. 
Кроме того, особенность работы управляющих программных систем 
заключается в том, что за ограниченное время решается большое количество различных функциональных задач и одновременно осуществляется 
обмен информацией с многочисленными внешними абонентами. Вследствие асинхронности работы большинства объектов системы управления 

данные от них могут поступать в случайные моменты времени, последовательность которых заранее не известна. Поэтому во многих программных 
системах строгая последовательность решения задач принципиально             
не может быть заранее определена или задана, так как она существенным 
образом зависит от поступающих сообщений и длительности решения тех 
или иных задач. Для решения этой проблемы во время процесса обмена         
и обработки информации используются буферные накопители сообщений 
при приеме и выдаче данных. 
Создание сложных систем с заданными характеристиками при ограниченных ресурсах требует проведения определенного комплекса мероприятий для достижения поставленной цели, который получил название 
проект. Целенаправленное управление проектом предназначено для пропорционального распределения ресурсов между работами по созданию 
системы на протяжении всего цикла проектирования вплоть до внедрения 
системы в серийное производство [4; 8]. Более подробно критерии проектирования программного обеспечения будут рассмотрены в следующей 
главе, а пока остановимся на надёжность программных систем. 
Надёжность функционирования программных систем при искажениях информации, сбоях и частичных отказах аппаратуры, которые могут 
возникать в процессе работы информационно-управляющей системы – 
один из наиболее значимых критериев разработки программных средств. 
Требования по обеспечению высокой надёжности объясняются высокой 
степенью автоматизации процессов управления в ряде систем и особой 
важностью выполняемых функций. Работа в системе управления реальными 
объектами в большинстве случаев требует от программного обеспечения 
надёжного функционирования и обработки данных при длительном (иногда 
круглосуточном и многомесячном) непрерывном решении заданного набора задач. Так как сложность современных информационно-управляющих 
систем возрастает значительно быстрее, чем надёжность используемой         
в них аппаратуры, то все более острой становится проблема обеспечения 
высокого качества выдаваемых результатов и сохранения работоспособности системы в условиях выхода из строя отдельных компонент аппаратуры 
или программных модулей.  
 
 
1.2. Надёжность функционирования  
программного обеспечения 
 
1.2.1. Надёжностная характеристика программного модуля 

Надёжность технических систем определяется в основном двумя 
факторами [26]: надёжностью компонентов и ошибками в конструкции, 
допущенными при проектировании или изготовлении. Относительно не

высокая надёжность компонентов, их глубокая взаимозависимость и способность к разрушению, старению или снижению надёжности в процессе 
эксплуатации привели к тому, что этот фактор оказался превалирующим 
для надёжности аппаратуры. Надёжность сложных программных систем 
определяется теми же двумя факторами. Однако соотношение их влияния 
иное. Хранение программ и данных на магнитных носителях при отсутствии внешнего вмешательства характеризуется очень высокой надёжностью. Доминирующим для надёжности программного обеспечения является второй фактор – ошибки проектирования. 
Программа любой сложности и назначения при строго фиксированных исходных данных и абсолютно надёжной аппаратуре исполняется по 
однозначно определенному маршруту и дает на выходе строго определенный результат. Однако случайное изменение исходных данных и накопленной при обработке информации, а также множество условных переходов в программе создают огромное количество различных маршрутов исполнения. Количество вариантов исполнения программы нельзя проверить 
полностью из-за ограничений на длительность отладки и приемочных испытаний. Источниками ненадёжности являются непроверенные сочетания 
исходных данных, при которых отлаженная программная система дает неверные результаты или проводит к  отказу.   
Для последующего изложения следует уточнить фундаментальные 
понятия теории надёжности и особенности их использования для изучения 
характеристик функционирования программ. 
Понятие отказа связано с нарушением работоспособности изделия и 
его соответствия требованиям технической документации. Отказ при исполнении программ может проявиться как следствие:  
● нарушения кодов записи программ; 
● стирания или искажения данных в оперативной или долговременной памяти ЭВМ; 
● нарушения нормального хода вычислительного процесса.  
Во всех случаях программные отказы приводят к прекращению выдачи пользователям информации и управляющих воздействий или к значительному искажению ее содержания и темпа выдачи. 
Понятие сбой в теории надёжности трактуется как самоустраняющийся отказ, не требующий внешнего вмешательства для замены отказавших компонент. Таким образом, понятия сбой и отказ применительно к 
аппаратуре отличаются степенью физического разрушения компонентов и 
необходимостью их замены. В процессе обработки данных обычно отсутствует физическое разрушение программ и не требуется замена или ремонт 
каких-либо материальных компонент. Основной принцип классификации 
сбоев и отказов – разделение по временному показателю длительности 
восстановления после любого искажения программы, данных или вычис

лительного процесса. При длительности восстановления, меньшей заданного порога, аномалии при функционировании программ следует относить 
к сбоям. При восстановлении, превышающем по длительности пороговое 
значение и нарушающем работоспособность программ, искажения соответствуют отказу. Отсюда возникает задача классификации аномалий при 
функционировании программ на два типа: достаточные для нарушения работоспособности системы и малые отклонения от требований технической 
документации, при которых работоспособность сохраняется. Далее учитываются только значительные искажения программ, данных или вычислительного процесса, достаточные для нарушения работоспособности. 
Классификация программных сбоев и отказов по длительности восстановления приводит к необходимости анализа следующих динамических 
характеристик внешней среды и временных характеристик функционирования программ: 
● инерционности объекта, являющегося источником или потребителем информации; 
● среднего темпа или периодичности решения задач по обработке 
информации для данного объекта; 
● допустимой длительности ожидания отклика или времени реакции 
ЭВМ от момента поступления исходных данных до момента выдачи обработанных результатов. 
Инерционность объекта управления, или потребителя информации, 
обрабатываемой программной системой, является первичным показателем, 
используемым для установления необходимого времени реакции программ. Снижение темпа решения задач управления ведет к ухудшению характеристик функционирования, и при некотором низком темпе работоспособность нарушается, что соответствует отказу. 
Понятие правильной (корректной) программы может рассматриваться статически вне временного функционирования. Степень некорректности 
программ можно характеризовать вероятностью попадания в область исходных данных, которая предусматривалась требованиями спецификации 
(1 на рис. 1.1), однако не была проверена при тестировании и испытаниях 
(2 на рис. 1.1).  
Таким образом, неправильность программы определяется вероятностью совмещения следующих событий: 
● попадания исходных данных в область, заданную требованиями 
спецификации, но не проверенную при отладке и испытаниях; 
● проявления ошибки в программе при обработке таких данных. 
Правильность программы не определена вне области изменения данных, заданной спецификацией, и не зависит от динамики функционирования программ в реальном времени.