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

На правах рукописи

КОЛЕСОВ Константин Валерьевич

ТЕНЗОРНЫЙ МЕТОД ОЦЕНКИ НАДЁЖНОСТИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

05.13.01 - Системный анализ, управление и обработка информации (космические и информационные технологии)

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Красноярск - 2009

003461842

003461842

Работа выполнена в Сибирском государственном аэрокосмическом университете имени академика М.Ф. Решетнева, г. Красноярск

Научный руководитель: доктор технических наук, профессор

Петров Михаил Николаевич

Официальные оппоненты: доктор технических наук, профессор

Малинкин Виталий Борисович

кандидат технических наук Юронен Юрий Павлович

Ведущая организация: Сибирский федеральный университет,

г. Красноярск.

Защита диссертации состоится « 06 » марта 2009 г. в 13 часов на заседании диссертационного совета Д 212.249.02 при Сибирском государственном аэрокосмическом университете имени академика М.Ф. Решетнева по адресу: 660014, г. Красноярск, проспект имени газеты «Красноярский рабочий», 31.

С диссертацией можно ознакомиться в библиотеке Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева.

Автореферат разослан « » сре/?^сгл.£ 2009 г.

Ученый секретарь диссертационного совета

Моргунов Е.П.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы

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

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

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

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

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

1. Анализ существующих на сегодняшний день методик, моделей и аЛ-

горитмов оценки надежности программного обеспечения.

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

3. Разработка тензорного метода анализа надежности программного обеспечения на стадии тестирования программных средств.

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

5. Применение метода для анализа реальных программ и программного обеспечения.

Методы исследования

При выполнении работы использовалась тензорная методология, математическое моделирование параметров сложных систем, элементы теории вероятностей, имитационное моделирование в среде ОРЗБ.

Научная новизна

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

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

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

4. Предложен метод анализа сложных систем с использованием метода диакоптики - разбиения системы на отдельные подсистемы с последующим объединением решений.

Значение для теории

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

Практическая значимость

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

Достоверность полученных результатов

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

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

Реализация результатов работы

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

Апробация работы

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

- на XIV Всероссийском семинаре «Нейроинформатика и её приложения», Красноярск, 2006 г.;

- на IX Всероссийском семинаре «Моделирование неравновесных систем», Красноярск, 2006 г.;

- на 111 научной международной конференции «Фундаментальные исследования», Доминиканская республика, 2008 г.

Диссертационная работа обсуждалась на научных семинарах кафедры «Системный анализ и исследование операций» Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева в 2007

- 2008 гг.

Публикации

По материалам диссертации опубликовано 16 работ, в том числе: 2 работы в ведущих рецензируемых журналах и изданиях, определенных ВАК РФ, 1 монография. Полный список публикаций представлен в конце автореферата.

Структура и объем работы

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассмотрены основные методы оценки надежности программных средств на различных этапах жизненного цикла создания программного обеспечения.

Обзор всех существующих на сегодняшний день методов анализа надежности позволяет выделить следующие закономерности:

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

- все существующие методы анализа привязаны к конкретным этапам жиз-

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

Основным понятием теории надежности является определение надежности как «способность системы или компонента выполнять требуемые функции при определенных условиях за определенный период времени».

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

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

Методы проектирования надежного программного обеспечения делятся на:

1. Предупреждение ошибок - методы, позволяющие минимизировать или исключить появление ошибки.

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

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

Методы предупреждения ошибок.

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

Методы обнаружения ошибок.

Методы обнаружения ошибок базируются на введении в программное обеспечение системы различных видов избыточности:

• Временная избыточность. Использование части производительности аппаратных средств для контроля исполнения и восстановления работоспособности ПС после сбоя.

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

• Программная избыточность включает в себя: «взаимное недоверие» - компоненты системы проектируются, исходя из предположения, что другие компоненты и исходные данные содержат ошибки, и должны пытаться их обнаружить; немедленное обнаружение и регистрацию ошибок; выполнение

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

Методы обеспечения устойчивости к ошибкам.

Методы обеспечения устойчивости к ошибкам направлены на минимизацию ущерба, вызванного появлением ошибок, и включают в себя:

• обработку сбоев аппаратуры;

• повторное выполнение операций;

• динамическое изменение конфигурации;

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

• копирование и восстановление данных;

• изоляцию ошибок.

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

Наконец, возможно совместное использование указанных методов -так называемые гибридные модели. Причем в данном случае подразумевается не только одновременное использование методов во времени, но и их применение на разных этапах жизненного цикла программ.

Во второй главе рассмотрен тензорный метод анализа сетей и его основные принципы.

Любая система простейшего типа состоит из одномерных элементов (резисторов, узлов связи, блоков), соединенных в определенных точках; силы накладываются вдоль этих элементов на узлы. Подобные структуры называют сетями.

Использовать тензорную методологию для анализа электрических сетей впервые предложил американский инженер Габриель Крон. Вся сеть в этом случае представляет соединенные определенным образом катушки и источники ЭДС. Предполагается, что накладываемые электромагнитные величины мгновенно распространяются через всю сеть; иными словами, рассматриваемые сети имеют сосредоточенные, а не распределенные параметры. Хотя сам Крон описывал такие сети терминами электротехники, следует подчеркнуть, что используемая методология имеет отношение не только к методам электротехники. При изменении соответствующих выражений (например, «сила» вместо «напряжения») эта методология может также применяться при исследовании механических сетей. Метод рассуждения в основном заимствован из геометрии: из «топологии» и из дифференциальной геометрии. Математический аппарат, применяемый в рассмотрении технических задач, известен как «тензорная алгебра» и «тензорный анализ». Изучение сетей предпринято таким образом, чтобы сформировать логический фундамент для познания более сложных технических структур, составные

части которых имеют более одного измерения, соединение частей не сохраняется, распространение воздействий не мгновенное.

В то время как одна катушка характеризуется величинами е, ¡, Л, Ь, С и Ъ, множество катушек характеризуется целыми п-матрицами е, 1, ^ Ь, С и Z. Следовательно, несколько катушек характеризуется тем же числом символов того же типа, что и одна катушка, но отличие в их описании состоит в том, что отдельные числа заменяются «-матрицами различной размерности, зависящей от числа элементов.

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

В определенной степени сложные системы не только описываются тем же количеством символов, что и простые системы, но и сам весь метод рассуждения, используемый в анализе их поведения, соответствует этапам анализа простейших систем, отличаясь только тем, что вместо каждой величины используется «-матрица.

Иными словами, перед тем как исследовать любую сложную систему со многими переменными, необходимо сначала выполнить анализ некоторой более простой системы с одной (или более) степенью свободы. После этого можно перенести все этапы этого анализа простой системы на сложную систему, заменяя каждую величину соответствующей ей «-матрицей. Замечательно также то, что окончательный вид уравнения сложной системы с п степенями свободы совпадает с видом окончательного уравнения простой системы с одной (или более) степенью свободы, отличаясь только тем, что каждая величина заменена соответствующей «-матрицей.

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

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

Фундаментальное предположение тензорного анализа состоит в том,

что:

- новая система описывается тем же числом «-матриц и того же типа, что и старая система (а именно, е', г' и I1), но отличается от нее численным значе-

нием компонент «-матриц;

- уравнение новой системы, записанное в «-матрицах, имеет тот же вид, что и уравнение старой системы;

- «-матрицы новой системы могут быть найдены из «-матриц старой системы с помощью рутинного преобразования.

Эти положения носят название «постулата второго обобщения». Таким образом, переход от одного способа соединения элементов к другому не требует введения каких-либо новых «-матриц и изменения расположения «-матриц в уравнении. Отличие состоит только в том, что «-матрицы е' и г' имеют компоненты, отличающиеся от компонентов матриц прежнего уравнения, и переменная I теперь заменяется новой переменной 1'.

Операцию перехода от одного способа соединения к другому называют «преобразованием» или «преобразованием системы координат». Это можно также назвать «заменой переменных», поскольку множество переменных \ заменяется другим множеством переменных I'.

Для того чтобы математически представить один геометрический (или физический) объект, необходимо показать все его компоненты во всех возможных системах координат, которых может быть достаточно много. Это означает, что полное математическое описание геометрического объекта возможно лишь очень большим, как правило, бесконечным числом п-матриц.

На практике это описание осуществляется следующим образом:

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

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

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

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

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

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

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

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

«Метод анализа и окончательные уравнения, описывающие поведение сложной физической системы (с п степенями свободы), могут быть найдены последовательно при анализе простейшего, но наиболее общего элемента системы при условии, что каждая величина заменяется соответствующей п-матрицей. Простейший элемент системы может иметь одну или несколько степеней свободы».

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

го объекта, однако сам геометрический объект остается неизменным.

Если определена «-матрица компонентов геометрического объекта в некоторой одной системе координат, то есть для одной структуры алгоритма программного обеспечения, то каждая другая система координат определяется с помощью, так называемой матрицы преобразования, которая собственно и показывает чем новая система координат отличается от прежней системы. Поскольку существует множество систем координат, то и число матриц преобразования будет значительным. Формулу, позволяющую определить компоненты геометрического объекта в других системах координат, называют «формулой преобразования».

Постулат второго обобщения утверждает, что если компоненты геометрических объектов известны для одной частной системы координат, то для любой другой системы координат того же типа (число которых, вообще говоря, бесконечно) компоненты этих геометрических объектов могут быть определены с помощью тензора преобразования С. Уравнения поведения, записанные в терминах геометрических объектов, имеют одинаковый вид для всех систем данного типа.

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

Ниже приведен пример анализа некоторой структуры программного обеспечения, блок-схема алгоритма которого представлена на рисунке 1.

/

\

"ч

5

А,

ч.

Рисунок 1 - Блок-схема алгоритма программы

Для того, чтобы не загромождать рисунок, возле каждой ветви приведен лишь ее номер, который подставляется в индексы 1 соответствующих величин , /¡н X,.

Параметры структуры алгоритма: п = 8 - число ветвей; и ~9 - число узлов; К = 1 - число подсетей; {п~к) = и-К = 9-1 = 8- число узловых пар; к = п-(п-к) = 8-8 = 0- число контуров.

Так как число контуров равно нулю, то исходная структура алгоритма является чисто узловой.

1. Структура примитивного узлового алгоритма из 8 ветвей, которая будет использоваться в качестве вспомогательной, приведена на рисунке 2.

А 6 6

Рисунок 2 - Структура примитивного узлового алгоритма

2. Установление геометрических объектов и уравнений состояния.

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

Геометрические объекты, необходимые для описания примитивного алгоритма (в соответствии с постулатом первого обобщения): Л - вектор, компоненты которого представляют собой интенсивности потоков отказов, поступающих в соответствующие ветви.

^ - вектор, компоненты которого представляют собой коэффициенты готовности, возникающих в функциональном блоке алгоритма (в соответствующих ветвях) под действием поступающего потока отказов. / - квадратная матрица размерностью п-строк на п-столбцов. Элементы главной диагонали представляют собой значения интенсивностей потока от-

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

Я =

А,

К8=

К& К& Ч

Кё, К&

г=

Л. 0 0 0 0 0 0 0

0 кг 0 0 0 0 0 0

0 0 Лз 0 0 0 0 0

0 0 0 3"4,4 0 0 0 0

0 0 0 0 /м 0 0 0

0 0 0 0 0 /б,б 0 0

0 0 0 0 0 0 Л.7 0

0 0 0 0 0 0 0 А

Матричное уравнение состояния примитивного алгоритма:

Так как матрица / - диагональная, то эквивалентная система уравнений состояния примитивной схемы алгоритма получается перемножением соответствующих компонент матрицы / и вектора К^:

Л2 =/2.2 '^2,

Лз =/з,з3,

Х4 =/4,4

Л5 =/5.5-Кё5,

Лв =/б.б-К8б,

Д7 =/7,7-К^т,

Л8 =/8,8 ■ Кё8 ■

3. Определение тензора преобразования.

Направления совокупных коэффициентов готовности в выбранных узловых парах (открытых путях) показаны на рисунке 3.

Ч,

Рисунок 3 - Открытые пути в исходной схеме алгоритма

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

а 1 Ъ ; : ! с! ! е { 8 ь

1 -1 1 0 0 0 0 0

1 0 0 0 0 0 0 0

-1 1 0 0 0 0 -1 1

А 0 0 0 1 0 0 0 0

0 0 0 1 -1 1 0 0

N6=-Nd+Ne-Ng + Nll 0 0 0-1 1 0 -1 1

0 0 0 0 0 0 0 1

0 0 0 0 0 0 1 -1

Транспонированная матрица преобразования:

11-10 0 0 0 0

-10 10 0 0 0 0

0 0 0 0 0 0 0 0

Ат = 0 0 0 1 1 -1 0 0

0 0 0 0 -1 1 0 0

0 0 0 0 1 0 0 0

0 0-10 0 -1 0 1

0 0 10 0 1 1 -1

4. Нахождение геометрических объектов, соответствующих исходному алгоритму.

Интенсивности потоков отказов в открытых путях исходного алгоритма (между двумя узлами узловой пары):

1 1 -1 0 0 0 0 0 Л Л, + Л2 - лг

-1 0 1 0 0 0 0 0 ~ Л] Л^

0 0 0 0 0 0 0 0 л; л,

0 0 0 1 1 -1 0 0 К = Л4 + Л5 - Я6

0 0 0 0 -1 1 0 0 л5 -Л5+Л6

0 0 0 0 1 0 0 0 Л6 л

0 0 -1 0 0 -1 0 1 ¿7 ~Л3~Л6+Лг

0 0 1 0 0 1 1 -1 л% Л5 +Л6+Л7- я8

Значения интенсивностей отказов в открытых путях (между узлами узловых пар) исходном алгоритме находятся по следующей формуле:

В целях экономии места применяется правило: при умножении любой матрицы М на диагональную (если такое умножение возможно), эта матрица сохраняет свою размерность, а каждый ее ненулевой элемент М, ■ умножается на диагональный элемент /• ■ в соответствующем столбце. Таким образом, после проведения первого умножения.

О О — О о ~ — -7

oo'Voo'T"0'-4 0000—1000

0000

о о

ч00

^ +

I

■л чГ

, -о" , -С ^

о о . « о ^ +

^ i ^ i

^ +

1 <

ч^ +

Ч о

t.

^ V-, О

I

ООО^Н— о о —i О О О ООО О -Т'О — ООООО .^ООООО

ООООООц^4-,

ОООООООц^-

О ^ ^ О О О

ч^

О О О

О О О

ц^" ^ v^" О О

ч^

Ч< « -О. + ^

+ ч

О О о

S ^ ^ Ч ,

I

о ^ ^ ^ о о о о

I

о ^ © о о о о о

^ ^ о о о о ^

о о о о о о о

^ ч ? ^

О ООО о

s;

^ с.-- а

+ ^ о о о - I I

+ <

+

• t. ~

ООО ^

5. Нахождение уравнения состояния исходного алгоритма.

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

Эквивалентная система уравнений состояния исходного алгоритма:

( Л]+Л2-Л3 = (/и + /2,2 + Дз) • Ъ'.МгГч - /з,з) ■ ^+(/1.1) • Кё'с

- А, + Л3 = (-/,., - Дз)' К8\ +(/,., + /з.з)' +(-/!,I)' ^ +

+ (-/з,З)-^УК/З,З№'л,

Л = (Л.) • +(-/,.) • +(/1.1) ■ -Кг'с.

я4 + д5 - я6 = (Д4 + /5>5 + дб) • ^+(-/„ - /6>6) • +(/„) • +

I +(/б,б)-^,г+(-/б.б

\ -а5 + д6 = (-/5>5 -/6,6> ^+(/5,5 + /6,6)• ■

+ (-/б.б№>(/б.б№л.

¿5 = (/5,5 +(-/5,5 ) • +(/5,5 ) ' -

- лз - Л6 + Д8 = (Л,з№'й+(-/з,з)-Ай'ь+СДб) ■■ Ак'„+(-/б,б) ■■ +

+ (/з,3 +/б,6 + /8,8 №'*+(-/« - Л,6

Я5 +Аб + -Л, =(-Дз)- АкХДзУ■Кв'ьЧ-ие)+(Д+

I +(-/з,3 "Дб -/8,8)-^'г+(/з,3 +Л,6 +/7,7 +Л,8)-^'/г

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

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

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

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

2. Синтез топологии алгоритма по заранее заданным характеристикам надёжности.

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

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

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

Кроме того, тензорный метод анализа дает такие глубокие возможности, как анализ больших структур по частям (метод диакоптики) с последующим объединением результатов, и синтез алгоритмической структуры с заданными характеристиками.

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

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

Кроме того, если в состав системы уравнений, описывающих первоначальную систему, входило N отдельных уравнений с N неизвестными, то при разбиении системы на п отдельных подсистем для описания связей между ними вводятся к неизвестных. Поэтому необходимо найти И+к переменных в п+1 независимых группах, а не просто решить систему из N уравнений с N переменными. Впрочем, такое усложнение дает значительное уменьшение габаритов исходных анализируемых подсистем.

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

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

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

• Из всех моделей наиболее удобны так называемые топологические модели, в которых каждая отдельная ветвь может быть индуктивностью, оператором, блок-схемой или другим элементом; все элементы связаны между собой с помощью графа. Из всех терминологий электрическая терминология становится наиболее удобной, так как все анализируемые величины легко представить и описать.

На стадии тестирования уже известен алгоритм самой программы, взаимосвязь модулей между собой и их основные характеристики. Задача выбора структурной схемы в данном случае уже решена, и необходимо решать уже другие проблемы. В частности, необходимо произвести тестирование программного обеспечения, методы тестирования при этом уже известны и хорошо изучены, а вот время, в течение которого необходимо тестировать программное обеспечение, неизвестно. На практике используются различные способы оценки этого времени - в частности, достаточно популярны модели роста надежности программного обеспечения (Software reliability growth models), однако данные модели чаще всего рассматривают программу как черный ящик и поэтому не являются в полной мере оптимальными. Между тем структура программы является известной и поэтому ее использование на стадии тестирования дает новые возможности.

В четвертой главе представлена программная реализация системы модельно-алгоритмической поддержки многоэтапного анализа надежности программных средств, и приводятся примеры использования созданной сис-

темы в реальных проектах.

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

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

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

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

Все последующие этапы анализа сводятся к перемножению матриц:

Е' -Ст *Е , Л' = С/ *А *С .

или:

А' = СТ*Л,

В конечном счете, получается система уравнений, решение которой позволяет найти результат.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

Использование тензорного метода анализа надежности программного обеспечения дает преимущества по сравнению с другими методами анализа, что позволяет говорить об актуальности данного направления. В результате диссертационного исследования получены следующие основные результаты, имеющие самостоятельное научное и практическое значение.

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

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

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

4. Осуществлено применение тензорного метода анализа к анализу надежности программного обеспечения на стадии тестирования, позволяющее получить численные значения надёжности. Кроме этого, полученные системы уравнений позволяют выбрать оптимальную структуру алгоритма при заданных характеристиках надёжности.

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

6. Разработана программная реализация тензорного метода анализа, которая позволяет анализировать показатели надежности программ на основе блок-схем алгоритмов.

Результаты моделирования программных средств подтвердили эффективность тензорного метода анализа на указанных стадиях разработки программного обеспечения с применением современных ЭВМ для расчета показателей надежности ПО.

Основные результаты диссертационной работы опубликованы в следующих работах (знаком * обозначены работы, опубликованные в издании, включенном в список изданий, рекомендованных ВАК для опубликования результатов диссертационных исследований):

1. Колесов, К.В. Основные направления обеспечения надёжности программных комплексов [Текст] / К.В. Колесов // Нейронформатика и сё приложения - 2006. - Красноярск: Изд-во ИВМ СО РАН, 2006. - С. 53-54.

2. Колесов, К.В. Обеспечение гарантированной готовности программно-информационных технологий [Текст] / К.В. Колесов // Моделирование неравновесных систем - 2006. - Красноярск: Изд-во ИВМ СО РАН, 2006.-С. 97-98.

3. Колесов, К.В. Программа оптимизации вычислений численным методом проекции градиента МПГ v.0.1 [Текст] / К.В. Колесов // Инновации в науке и образовании. - 2006, - № 8 (19). - С. 35.

4. Колесов, К.В. Фреймовая интеллектуальная система v.0.1 [Текст] / К.В. Колесов // Инновации в науке и образовании. - 2006. - № 8 (19). - С. 36.

5. Колесов, К.В. Система автоматизации разработки веб-сайтов SiteMaster V0.01 [Текст] / К.В. Колесов // Инновации в науке и образовании. -2006. -№ 8 (19). -С. 36.

6. Колесов, К.В. Программа автоматизации вычислений модульных выражений MODC v.l [Текст] / К.В. Колесов // Инновации в науке и образовании. - 2006. - № 12 (23). - С. 32.

. 7. Золотухин, В.В. Тензорная методология исследования надёжности алгоритмов программного обеспечения [Текст]: Монография / В.В. Золотухин, К.В, Колесов, М.Н. Петров; под ред. М.Н. Петрова. - Красноярск: НИИ СУВПТ, 2007 - 206 с.

8. Алгазин, Е.С. Анализ надёжности алгоритмов программного обеспечения узловой структуры [Текст] / Е.С. Алгазин, К.В. Колесов, М.Н. Петров // Сб. науч. тр. НГТУ. - Новосибирск: НГТУ, 2007. - Вып. 3 (49). - С. 83-85.

9. * Колесов, К.В. Анализ надежности алгоритма программного обеспечения ортогональной структуры узловым методом [Текст] / К.В. Колесов // ВестникСиб. гос. аэрокосмич. ун-та.-2008.-Вып. 1 (18).-С. 60-65.

10. Колесов, К.В. Тензорный метод анализа надежности алгоритма программного обеспечения узловой структуры [Текст] / К.В. Колесов, М.Н. Петров // Информационные технологии моделирования и управления. -2008. - Вып. 3 (46). - С. 332-337.

11. Петров, И.М. Тензорный метод анализа алгоритмов программного обеспечения ортогональной структуры [Текст] / И.М. Петров, К.В. Колесов, М.Н. Петров // Успехи современного естествознания. - 2008. - № 6. - С- 148.

12. * Колесов, К.В. Использование метода диакоптики для анализа надежности программного обеспечения [Текст] / К.В. Колесов // Вестник Сиб. гос. аэрокосмич. ун-та. - 2009. - Вып. 1 (22). - С. 43-47.

Программные разработки, зарегистрированные в Отраслевом фонде алгоритмов и программ:

13. Колесов К.В. Программа оптимизации вычислений численным методом проекции градиента МПГ v.0.1. - М.: ВНТИЦ, 2006. № 50200601578.

14. Колесов К.В. Фреймовая интеллектуальная система v.0.1. - М.: ВНТИЦ, 2006. № 50200601579.

15. Колесов К.В. Система автоматизации разработки веб-сайтов SiteMaster V0.01. -М.: ВНТИЦ, 2006. № 50200601580.

16. Колесов К.В. Программа автоматизации вычислений модульных выражений MODC v.l. -М.: ВНТИЦ, 2007. № 50200700090.

Колесов Константин Валерьевич Тензорный метод оценки надёжности программного обеспечения

Автореферат

Подписано в печать « 29 » декабря 2008 г. Формат 60x84 /16. Печ. л.1. Тираж 100 экз. Заказ № //

Отпечатано в отделе копировальной и множительной техники СибГАУ. 660014, г. Красноярск, пр. им. газ. «Красноярский рабочий», 31