FORMALIZATION OF RELIABLE VARIANT OF SOFTWARE CHOICE PROBLEM

详细

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.

全文:

Проблема оценки надежности программного обес- печения (ПО) возникла одновременно с его появлени- ем. Программное обеспечение является составной ча- стью вычислительной системы, а следовательно, на- дежность вычислительной системы неотъемлемо свя- зана с надежностью установленного ПО. Традиционно при оценке надежности программного обеспечения использовались классические методы теории надеж- ности, такой подход и сейчас во многом себя оправ- дывает. Однако по мере развития вычислительной техники пришло четкое понимание того, что ПО - не просто составная часть вычислительной техники. В современных условиях развития цифровой техники специализированное ПО перестало быть принадлеж- ностью одной вычислительной системы (как это было раньше), а стало использоваться на миллионах анало- гичных компьютеров (в основном - персональных). Таким образом, проблема обеспечения устойчивого функционирования расчетных программ, выявления их ошибок, сегодня крайне остро стоит перед разра- ботчиками. За прошедшие десятилетия было создано множество методов, методик и моделей исследования надежности ПО. Однако, к сожалению, единого под- хода к решению этой проблемы предложено не было и, по-видимому, в ближайшее время не предвидится. Тем не менее, при разработке сложных программных систем их создатели стараются в той или иной степе- ни получить оценку надежности ПО. Более правиль- ный подход заключается в последовательном оцени- вании надежности программ на каждом этапе разра- ботки. Р. В. Юнусов предлагает модели оценки надежно- сти для различных этапов разработки ПО. В частно- сти, указывает на сложность архитектуры ПО как на один из факторов, влияющих на его надежность. Рас- сматриваются такие свойства архитектуры, как стати- ческая и динамическая зависимость компонентов, ин- терфейсы компонентов, связь и управление, загру- женность системы, среднее время простоя системы, размер компонентов. Надежность программного обес- печения определяется как вероятность того, что оно функционирует без сбоев, в определенной операцион- ной среде, в течение определенного промежутка вре- мени. Коэффициент надежности архитектуры ПО можно оценить по формуле 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. Схема двухточечного процентного скрещивания Также И. А. Панфиловым предложены подходы к решению многокритериальной задачи. Однако, оче- видно, что для поставленной задачи потребуются но- вые исследования алгоритма. Таким образом, для ре- шения задачи автоматизации процесса разработки надежного ПО предлагается модифицировать указан- ный алгоритм.