FORMALIZATION OF RELIABLE VARIANT OF SOFTWARE CHOICE PROBLEM

Abstract

For design reliable software are usually used such methods as multi versions and duplication. But it lead to increas- ing the cost of the software. For automation the process of design the reliable and cheap software are supposed to use the modification of genetic algorithm.

Full Text

Проблема оценки надежности программного обес- печения (ПО) возникла одновременно с его появлени- ем. Программное обеспечение является составной ча- стью вычислительной системы, а следовательно, на- дежность вычислительной системы неотъемлемо свя- зана с надежностью установленного ПО. Традиционно при оценке надежности программного обеспечения использовались классические методы теории надеж- ности, такой подход и сейчас во многом себя оправ- дывает. Однако по мере развития вычислительной техники пришло четкое понимание того, что ПО - не просто составная часть вычислительной техники. В современных условиях развития цифровой техники специализированное ПО перестало быть принадлеж- ностью одной вычислительной системы (как это было раньше), а стало использоваться на миллионах анало- гичных компьютеров (в основном - персональных). Таким образом, проблема обеспечения устойчивого функционирования расчетных программ, выявления их ошибок, сегодня крайне остро стоит перед разра- ботчиками. За прошедшие десятилетия было создано множество методов, методик и моделей исследования надежности ПО. Однако, к сожалению, единого под- хода к решению этой проблемы предложено не было и, по-видимому, в ближайшее время не предвидится. Тем не менее, при разработке сложных программных систем их создатели стараются в той или иной степе- ни получить оценку надежности ПО. Более правиль- ный подход заключается в последовательном оцени- вании надежности программ на каждом этапе разра- ботки. Р. В. Юнусов предлагает модели оценки надежно- сти для различных этапов разработки ПО. В частно- сти, указывает на сложность архитектуры ПО как на один из факторов, влияющих на его надежность. Рас- сматриваются такие свойства архитектуры, как стати- ческая и динамическая зависимость компонентов, ин- терфейсы компонентов, связь и управление, загру- женность системы, среднее время простоя системы, размер компонентов. Надежность программного обес- печения определяется как вероятность того, что оно функционирует без сбоев, в определенной операцион- ной среде, в течение определенного промежутка вре- мени. Коэффициент надежности архитектуры ПО можно оценить по формуле M Nj Fs = 1 + 0,4а, где а - отношение количества кода на ассемблере и языка высокого уровня. Предполагается, что код на ассемблере может содержать на 40 % ошибок больше. На фазе тестирования возможно использование различных методик, каждая из которых обладает соб- ственными свойствами, временными характеристика- ми, различающихся по стоимости. Фаза тестирования самая продолжительная и может занять до 60 % от всего проекта. Во время тестирования выявляется са- мое большое количество ошибок в ПО. Рассмотрим меры покрытия теста, используемые на данной фазе: покрытие выражений - доля всех условных вы- ражений, выполненных во время теста; покрытие ветвлений - доля всех ветвлений, вы- полненных во время теста; покрытие предикатов - доля всех переменных, используемых для проверки условий перед условным переходом. R = å å PUij ×R , (1) В начальной плотности ошибок (2) коэффициент j=1i=1 ij фазы тестирования (F ) принимает следующие значегде M - число уровней архитектуры ПО; Ni - число компонент на уровне i, i = 1, ,.., M; PUij - вероятность использования компонента; Rij - надежность компо- нента. Оценить данные параметры на фазе разработки ар- хитектуры невозможно, численные показатели в мо- дель берутся непосредственно на фазах кодирования и тестирования. Кроме того, на надежность влияют ошибки, допу- щенные на фазе кодирования ПО. Количество оши- бок, в свою очередь, зависит от квалификации и опыта разработчиков, а также от способа тестирования ПО. Одним из самых часто используемых параметров оценки корректности ПО является плотность ошибок. Начальную плотность ошибок можно оценить как ph ния: «Тестирование модуля», «Подсистемы», «Системы», «Приемлемость». Числовые показатели определяются и задаются экспертом. Параметры для оценки D по выражению (2) долж- ны быть скорректированы с использованием данных, накопленных в результате деятельности разработчи- ков ПО. Коэффициент С обычно лежит в диапазоне от 6 до 20 ошибок/KLOC. Можно брать как средние, так и максимальные и минимальные значения для оценки диапазона плотности ошибок. Кроме того, на стоимость, надежность и время разработки ПО часто накладываются жесткие ограниче- ния. И наконец, разрабатываемое ПО, помимо удовле- творения требованиям надежности и стоимости, должно справляться с задачами, для которых оно соз- дается. D = C × Fph × Fpt × Fm × Fs , (2) Формализация задачи разработки надежного ПО где Fph - коэффициент фазы тестирования; Fpr - коэф- фициент командного программирования; Fm - коэф- фициент опытности и «зрелости» процесса разработ- ки ПО; Fs - коэффициент структурирования; С - кон- станта, определяющая количество ошибок/KLOC (ошибок на тысячу строк исходного кода). Коэффициенты Fpr, Fm, Fs и С зависят только от мастерства и опыта команды разработчиков: коэффициент командного программирования Fpr: плотность ошибок зависит от конкретных людей, их опыта написания программ и отладки. Можно принять следующие значения параметра: «Высокий», «Сред- ний», «Низкий». Числовые показатели определяются и задаются экспертом; коэффициент опытности и «зрелости» процесса разработки ПО Fm. Можно принять следующие значе- ния параметра: «Уровень 1», «Уровень 2», «Уровень 3», «Уровень 4», «Уровень 5». Числовые показатели определяются и задаются экспертом; коэффициент структурирования Fs: этот пара- метр берет во внимание зависимость плотности оши- бок от языка программирования (отношение количе- ства кода на ассемблере и языка высокого уровня). должна привести к оптимизационным постановкам. При этом очевидны две группы критериев: критерии надежности, которые должны быть максимизированы, критерии стоимости, которые должны быть ми- нимизированы. Становится ясно, что речь идет о многокритери- альной задаче оптимизации. Совершенно очевидно противоречие критерия стоимости разработки по отношению к критерию надежности. Время разработ- ки можно отнести к критериям стоимости: они оказы- ваются вполне согласованными (при увеличении од- ного - второй также растет и рост обоих должен при- водить к увеличению надежности). Приведем формальную запись построенной опти- мизационной модели: Нпо(R1, …, Ri, …, RN, L1, …, Li, …, LM, D, T) ® max, Спо(N, M, D, T, Hr) ® min, при ограничениях Hr(Нпо, D, T) < Lim(Hr), Спо < Lim(Спо), где Нпо - критерий оценки надежности; Спо - критерий оценки стоимости; Ri - надежность i-го компонента ПО, i = 1 … N; Lj - надежность связей компонентов типа j = 1… M; D - согласованный критерий, опреде- ляющий квалификацию разработчиков; Т - способ тестирования ПО; Нr - время разработки ПО; Lim(Hr) - ограничение по времени на разработку ПО; Lim(Спо) - ограничение по стоимости ПО. image Работа операторов скрещивания организована та- ким образом, чтобы получаемые в результате решения были допустимыми, однозначно трактовались и содер- жали информацию только из родительских хромосом. Таким образом, для автоматизации процесса разработки надежного ПО необходимо решить задачу многокритериальной условной смешанной оптимиза- ции. В качестве приемлемого средства решения такой задачи был выбран генетический алгоритм. Однако для работы генетического алгоритма необходимо за- кодировать каждое решение в бинарную строку ко- 0000000000 50 % 111111 50 % 111111 0000000000 Родительская хромосома 1 Родительская хромосома 2 Хромосоманечной длины - хромосому. Здесь решение - это набор параметров, однозначно определяющий структуру image 111111 0000000000 потомок 1 ПО и характеристики процесса разработки. Наш же алгоритм должен работать с вариантами ПО произ- 0000000000 111111 Хромосомапотомок 2 вольной конфигурации. То есть нам заранее не из- вестно не только значение параметров ПО, но и их количество. То есть среди вариантов ПО, которые рассматривает алгоритм, могут оказаться такие, кото- Рис. 1. Схема процентного скрещивания рые отличаются количеством типов компонент и свя- зей, а значит и количеством наборов данных. Длина бинарной строки зависит от количества компонент проектируемой программной системы и от количества версий блоков, отвечающих за выполнение одинаковых функций. Также хромосома со- держит информацию о дублировании компонент программной системы, надежностные характеристи- ки отдельных компонент, информацию о квалифика- ции группы программистов, занимающихся кодирова- нием программной системы. При декодировании хро- мосомы по всем этим характеристикам даются оценки надежности и стоимости программной системы в цеimage 000000000000000000000 50 % 111111111111 image 50 % 1110000000000111 0000011111100000 Родительская хромосома 1 Родительская хро- мосома 2 Хромосома- потомок 1 Хромосома- потомок 2 лом. В зависимости от сложности задач, стоящих пе- ред проектируемым ПО, и решений, генерируемых и получаемых в процессе работы алгоритма, длина хромосомы может варьироваться от 30 до 200 генов. На решения, содержащие более 200 генов, наклады- вается ограничение по сложности, и они оценивают- ся со штрафом. И. А. Панфиловым был предложен модифициро- ванный генетический алгоритм с переменной длиной хромосомы [2]. Алгоритм применялся к решению за- дачи проектирования многопроцессорных вычисли- тельных систем. В модифицированном генетическом алгоритме был реализован оригинальный оператор процентного скрещивания, позволяющий скрещивать хромосомы разной длины. Схема процентного скре- щивания для случая, когда в качестве точки скрещи- вания выбирается точка - 50 %, представлена на рис. 1. Также после модернизации механизма про- центного скрещивания была предложена схема двух- точечного процентного скрещивания (рис. 2), в качест- ве точек скрещивания были выбраны точки 25 и 75 %. Рис. 2. Схема двухточечного процентного скрещивания Также И. А. Панфиловым предложены подходы к решению многокритериальной задачи. Однако, оче- видно, что для поставленной задачи потребуются но- вые исследования алгоритма. Таким образом, для ре- шения задачи автоматизации процесса разработки надежного ПО предлагается модифицировать указан- ный алгоритм.