МОДЕЛЬ ФУНКЦИОНИРОВАНИЯ ПРОГРАММНОЙ СИСТЕМЫ НА ОСНОВЕ GERT-СЕТИ

Полный текст

Введение. Конкуренция на рынке производителей программного обеспечения (ПО) сейчас высока, как никогда. Сокращение сроков разработки ПО, необхо- димость адаптации программ под различные устрой- ства, необходимость учета программной совместимо- сти и повышенные требования к информационной безопасности - вот неполный перечень причин, поче- му вопрос о надежности программного обеспечения стоит так остро. Важнейшим фактором, определяющим качество никновение сбоя в функционально эквивалентных модулях (версиях) на одних и тех же входных данных происходит в различных точках его исполнения, что снижает вероятность общей ошибки системы. В исследовании используются модели надежно- сти программного обеспечения, использующие для получения оценок различные источники данных. Одна из моделей - коэффициент надежности архитек- туры ПО [4]: N современного программного продукта, является надеж- M j ность его функционирования. Этой проблемой зани- маются исследователи и производители ПО по всему R = åå PUij × Rij , j =1 i=1 (1) миру. Программные сбои, приводящие к остановке производств или обслуживания клиентов, ошибки проектировщиков, приводящие к утечкам клиентских данных, - эти проблемы несут колоссальные финансо- вые и репутационные риски как крупным, так и ма- лым компаниям. Одной из самых известных катаст- роф, вызванных ошибкой программного обеспечения, была гибель ракетоносителя Ariane 5 в 1996 году [1]. В то же время производители программного обес- печения вынуждены сокращать сроки разработки ПО, использовать унифицированные решения для обеспе- чения совместимости программных систем, привле- кать к разработке удаленных специалистов. То есть, несмотря на высокий запрос на надежное ПО, разра- ботчики вынуждены экономить. Самый эффективный способ обеспечить надежность функционирования программного обеспечения - это проведение работ на этапе проектирования ПО. Вы- бор надежной архитектуры программ позволит избе- жать большинства трудностей и сократить затраты на устранение проблем надежности в будущем. Однако у современных исследователей нет единого подхода даже к определению термина «надежность програм- много обеспечения». Одни вкладывают в это понятие невосприимчивость к внешним воздействиям, другие - простоту и прозрачность программных решений, ис- ключающую возможность возникновения ошибок [2]. Причин возникновения ошибок и сбоев в про- граммных системах также великое множество: про- блемы, связанные с проектированием, аппаратным обеспечением, поведением пользователей в системе, внешними воздействиями на систему. Отсюда и раз- нообразие подходов к обеспечению надежности. Это требует развития модельно-алгоритмического обеспе- чения, методов и средств выбора надёжного варианта ПО. Модели оценки надежности программной сис- темы. В данной работе применяется мультиверсион- ный подход к обеспечению программной избыточно- сти [3]. Простое дублирование компонентов, как при аппаратном резервировании, недопустимо, так как в отличие от аппаратуры программные ошибки имеют внутреннюю природу и при дублировании не исчез- нут. При введении программной избыточности возгде M - число уровней архитектуры ПО; Nj - число компонентов на уровне j, j = 1, ..., M; PUij - вероят- ность того, что компонент i на уровне j, iÎ{1, …, Nj}, jÎ{1, ..., M}, будет использоваться; Rij - надежность компонента i уровня j. Значения надежности отдельных компонентов ПО Rij могут быть получены в результате статистической обработки результатов тестирования или могут быть присвоены экспертом. В обоих случаях для расчёта надежности программной системы в целом придется использовать вероятности задействования програм- мных компонентов, оценить которые экспертам непросто. В рамках данного исследования предлагается ме- тод получения количественных оценок надежности для отдельных программных компонентов и для про- граммных комплексов. В качестве метода моделиро- вания предложены GERT-сети [5]. На рис. 1, где представлен пример фрагмента работы программы для ЭВМ, состояние «1» соответ- ствует работе модуля ввода данных, состояние «2» - это следующий по очередности модуль информаци- онной системы, переход к нему возможен с вероятно- стью p1; состояние «3» соответствует системному сбою, который приводит к остановке работы всей программы; состояние «4» описывает работы модуля по корректировке вводимых данных, после которых возможен переход к состоянию «2», «3» или к состоя- нию «5», соответствующему вызову модуля по руч- ной корректировке вводимых данных. При этом р1 + р2 + р3 = 1 и р4 + р5 + р6 = 1. Состояния «1» и «4» носят вероятностный, а состояния «2», «3», «5» - детерминированный характер. Моделирование процесса функционирования про- граммного обеспечения GERT-сетью позволяют отве- тить на следующие вопросы: 1) какова вероятность того, что работа программы приведет к системному сбою; 2) какова вероятность того, что программа про- должит штатную работу; 3) чему равны математическое ожидание и дис- персия времени, необходимого для продолжения штатной работы. Данный подход по расчету надежности оказывает- ся применим для оценки программных систем, со- стоящих из нескольких связанных исполняемых про- граммных модулей, когда передача данных из модуля в модуль и активация следующего программного мо- дуля происходят автоматически, без участия пользо- вателя. Такая схема предполагает не только последо- вательное исполнение модулей, но и варианты с ветв- лением дерева исполняемых модулей. Однако если речь идет об участии некоторого пользовательского интерфейса, где инициация того или иного програм- много модуля зависит от решения пользователя или наборов внешних данных, то моделирование процесса функционирования с помощью GERT-сетей в описан- ном режиме не представляется возможным. Получение экспериментальных значений надеж- ности. Для апробации рассмотренных моделей были проведены экспериментальные исследования с про- граммным комплексом «Протокол безопасного обме- на данными» (ПБОД) [6]. Логически данный ком- плекс состоит из пяти программных модулей и двух хранилищ данных. Каждый модуль представлен 5-8 функциональными блоками, исполняемыми последо- вательно. Были проведены испытания ПБОД, состав- лены протоколы испытаний. В результате экспери- ментов были получены статистические оценки на- дежности функционирования 14-ти функциональных блоков, входящих в различные программные модули комплекса. В табл. 1 представлены количественные значения полученных оценок. Значения коэффициен- тов готовности для функциональных блоков были рассчитаны по методике, предложенной в [7]. Расчет надежности функционирования програм- много комплекса. Требовалось получить оценки надежности функционирования как отдельных про- граммных модулей, так и всего комплекса ПБОД в целом. Для этого процесс функционирования каж- дого модуля был представлен GERT-сетью. Для ста- тистически оцененных компонентов программных модулей в алгоритме были использованы полученные функции плотностей распределения и их характери- стики (табл. 1), для остальных компонентов были предложены экспертные оценки. Пример модели функционирования для программного модуля № 5 представлен на рис. 2. Расчетное значение коэффициента надежности архитектуры ПО согласно методике, предложенной в [7], составило R5 = 0,7589. Вычисление коэффициента надежности архитектуры ПО по формуле (1) для программного модуля № 5 дало результат R5 = = 0,75945375. Расхождение составило E5 = 0,00055375. Для оставшихся программных модулей ПБОД с помощью GERT-сетей были рассчитаны значения коэффициентов готовности Ri. Расхождения с экс- пертным методом также составили незначительные величины. По формуле (1) был рассчитан коэффициент надежности архитектуры R всего ПБОД (табл. 2). Рис. 1. Пример GERT-сети Fig. 1. The example of the GERT-network Таблица 1 Моменты и производящие функции моментов № п/п Тип распределения ME(s) Математическое ожидание Второй момент 1 Экспоненциальное æ s ö-1 ç1 - a ÷ è ø 3 0,16 2 Нормальное esm+(1/ 2)s2s2 100 0 3 Константа n 5 0 4 Экспоненциальное æ s ö-1 ç1 - a ÷ è ø 95 10 5 Экспоненциальное æ s ö-1 ç1 - a ÷ è ø 0 0 Окончание табл. 1 № п/п Тип распределения ME(s) Математическое ожидание Второй момент 6 Экспоненциальное æ s ö-1 ç1 - a ÷ è ø 0 0,1 7 Нормальное esm+(1/ 2)s2s2 5 0,05 8 Нормальное esm+(1/ 2)s2s2 1000 10 9 Нормальное esm+(1/ 2)s2s2 100 6 10 Нормальное esm+(1/ 2)s2s2 1000 20 11 Нормальное esm+(1/ 2)s2s2 45 0,5 12 Нормальное esm+(1/ 2)s2s2 20 10 13 Константа n 20 0 14 Экспоненциальное æ s ö-1 ç1 - a ÷ è ø 5 0,15 Рис. 2. Модель функционирования программного модуля № 5: 1 - блок доступа к адресной информации; 2 - блок доступа к базе входных данных; 3 - входной интерфейс блока; 4 - блок проверки формата; 5 - блок модификации программного кода Fig. 2. The model of operation of software module № 5 (1 - Ad- dressing information access block, 2 - Input data access block, 3 - Block input interface, 4 - Format checker block, 5 - Block of modification in the software) Таблица 2 Результаты расчетов Номер модуля Коэффициентов готовности Ошибка R1 0,87256001 0,00023374 R2 0,70564758 0,00065225 R3 0,90590065 0,00044870 R4 0,65729975 0,00070024 R5 0,75945375 0,00055375 ПБОД R 0,62007891 Проектирование надежного варианта про- граммного комплекса. Для обеспечения надежности функционирования программного комплекса был использован мультиверсионный подход. В работе рассмотрено два распространенных подхода в мульти- версионном программном обеспечении: первый подход - мультиверсионное программирование (N-version Programming, NVP), второй подход - блок восстанов- ления (Recovery Block, RВ) [8]. Был разработан мно- гокритериальный генетический алгоритм, позволяю- щий определить эффективные с точки зрения надежности и стоимости разработки программные блоки, подлежащие мультиверсионному дублированию, спо- соб реализаций мультиверсий (NVP или RB), а также количество версий каждого блока. Задача выбора надежной архитектуры сформули- рована в виде задачи многокритериальной смешанной оптимизации с алгоритмически заданными целевыми функциями. Критериями задачи являются общий коэффициент готовности программного комплекса и трудоемкость, которая также зависит от количества и состава программных компонентов комплекса: ( M N j æ = å åç B T + NVP Ts = + æ RB )×ç NVX Kij öö (2) + å T k ÷÷ на уровне j. На рис. 3 приведен пример кодирования программной архитектуры в виде бинарной хромосомы. Для ГА с переменной длиной хромосом использо- ç ij ij ij ij ç ij ij ÷÷ вался специальный оператор процентного скрещивания. j =1 i=1 è è kÎZij øø В результате применения генетического алгоритма при ограничении Zij ≥ 1, где М - количество архитек- турных уровней в архитектуре ПО; Nj - количество компонентов на уровне j, jÎ{1, ..., M}; Kij - глубина программной избыточности компонента i на уровне j; Zij - множество версий компонента i на уровне j; Tij - трудоемкость разработки компонента i на уровне j; Tkij - трудоемкость разработки версии k компонента i на уровне j, kÎZij, чел. ч; NVXij - трудоемкость разра- ботки среды исполнения версий (приемочного теста для RB - или алгоритма голосования для NVP); Bij - бинарная переменная, принимающая значение 1 (тогда NVPij = 0, RBij = 0), если в программном ком- поненте не используется программная избыточность, иначе равна 0; NVPij - бинарная переменная, прини- мающая значение 1 (тогда Bij = 0, RBij = 0), если в про- граммном компоненте введена программная избыточ- ность методом NVP, иначе равна 0; RBij - бинарная переменная, принимающая значение 1 (тогда Bij = 0, NVPij = 0), если в программном компоненте введена программная избыточность методом RB, иначе равна 0; Ts - общая трудоемкость реализации программной системы. Задача решается многокритериальным генетиче- ским алгоритмом. В исследовании были рассмотрены различные подходы к решению задач многокритери- альной оптимизации [9-12]. Для решения задачи был реализован генетический алгоритм (ГА) с переменной длиной хромосом, позволяющий кодировать програм- мные архитектуры, различающиеся по количеству и составу компонентов [4]. Алгоритм был исследован на множестве тестовых задач [13], результаты иссле- дования позволяют говорить о высокой эффективно- сти предложенной модификации. Длина хромосомы в ГА зависит от количества архитектурных уровней M и количества Ni компонентов на i-м уровне. При этом сами M и Ni выступают как переменные задачи. Zij в хромосоме задают количество версий компонента i были получены различные варианты программных архитектур разрабатываемого комплекса, отличаю- щиеся от исходной повышенной надежностью. При этом алгоритм предлагал реализовывать множество версий лишь для тех программных компонентов, ко- торые были недостаточно надежны. Результаты рабо- ты алгоритма приведены в табл. 3. Заключение. В данном исследовании был пред- ложен новый способ оценки надежности програм- мных систем. Способ позволяет получать оценки надежности функционирования программной системы на основе оценок надежности функционирования ее компонентов. Был разработан стохастический алго- ритм многокритериальной условной оптимизации, позволяющий находить надежные варианты архитек- туры ПО с учетом трудозатрат на реализацию ПО и возможностью использования различных подходов к обеспечению отказоустойчивости. Применение в генетическом алгоритме хромосом переменной дли- ны и оператора процентного скрещивания позволило существенно сократить пространство поиска. Разра- ботанный алгоритм был применен для проектирова- ния программной системы с высокими требованиями к надежности. В ходе проведенных с системой экспе- риментов были получены статистические оценки надежности отдельных ее компонентов, составлена модель функционирования программной системы. В результате применения разработанного генетическо- го алгоритма были предложены архитектуры програм- мной системы, позволяющие существенно улучшить надежность ее функционирования. Благодарности. Работа поддержана Министерст- вом образования и науки Российской Федерации, соглашение № RFMEFI57414X0126. Acknowledgments. This work was supported by the Ministry of Education and Science of the Russian Federa- tion, agreement № RFMEFI57414X0126. Рис. 3. Пример хромосомы в генетическом алгоритме Fig. 3. The example of chromosome in the genetic algorithm Таблица 3 Результаты работы генетического алгоритма № решения Коэффициент готовности системы Трудозатраты на модернизацию, чел. ч 1 0,92007891 489 2 0,87100579 367 3 0,95411304 523 4 0,96486553 597 5 0,90338740 454 Исходные значения 0,62007891 351

Об авторах

Т. А. Панфилова

Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева

Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

И. А. Панфилов

Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева

Email: crook_80@mail.ru
Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

В. В. Золотарев

Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева

Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

И. В. Ковалев

Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева

Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

Е. А. Сопов

Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева

Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

Список литературы

Дополнительные файлы