Постоянно возрастающая сложность и многофункциональность современных технических и программных систем выдвигает на передний план проблему обеспечения их надёжности на всех этапах жизненного цикла, что, в свою очередь, приводит к необходимости решения таких задач, как автоматизация поиска неисправностей.
На поиски и устранение ошибок в программном обеспечении тратится более 50 % стоимости разработки, а с учетом адаптации, модификации и обслуживания при эксплуатации – до 70 % стоимости программного продукта за время его жизненного цикла [3]. Задачей ближайшего будущего является движение в сторону такого распределения трудоемкости, чтобы суммарная цена обнаружения большинства дефектов стремилась к минимуму за счет обнаружения преимущественного числа ошибок программы на наиболее ранних фазах разработки программного продукта.
Методы диагностирования по типу предоставляемого результата можно разделить на два вида: детерминистические и недетерминистические.
Детерминистические алгоритмы распознавания дефектов
При условии наличия множества тестов, достаточных для выявления любого отказавшего блока, предлагаются алгоритмы, базирующиеся на методе динамического программирования и методе ветвей и границ. Данные методы гарантируют получение точного решения и имеют высокую вычислительную сложность в задачах большой размерности.
Метод динамического программирования для решения задачи диагностирования был впервые применен в работе [15]. Вданном методе применение каждого теста рассматривается как разбиение множества возможных состояний системы на два подмножества, одному из которых принадлежит истинное состояние. Оптимальным разбиением называется такое, которое обеспечивает минимальное среднее значение стоимости всех дальнейших разбиений. Процедура последовательного применения тестов продолжается до идентификации истинного состояния.
Метод ветвей и границ рассмотрен в работе [7]. При использовании данного метода также используется многошаговый процесс выбора тестов, а применение теста на произвольном шаге разбивает множество допустимых состояний системы на два подмножества. Процесс ветвления представляется ориентированным ацикличным графом, называемым деревом ветвлений. Вершины графа обозначают применяемые тесты и подмножества состояний, разбиваемые применением соответствующих тестов. Конечные вершины называются висячими. Впроцессе разбиения вычисляется нижняя оценка, характеризующая данное решение, и развивается та ветвь, которая на каждом шаге имеет лучшее значение оценки-прогноза. Процедура продолжается до получения подмножества, содержащего единственное состояние системы, которое и будет являться истинным.
Для универсального определения нижней границы значения функции-критерия в работе [10] был предложен метод, базирующийся на теории вопросников. Втеории вопросников каждая вершина дерева ветвлений (кроме висячей) называется вопросом, совокупность вопросов, достаточная для разбиения множества состояний системы на одноэлементные, – вопросником, а стоимость реализации вопросника – ценой его обхода. Висячие вершины вопросника называются события, им приписаны веса – вероятности соответствующих состояний системы, сумма весов событий – потомков некоторого вопроса – называется его весом. Цена обхода вопросника определяется как сумма произведений веса каждого вопроса на цену этого вопроса. Предложенный алгоритм позволяет уменьшить цену обхода вопросника, причем каждому вопросу может соответствовать более 2вариантов ответа.
В работах [6] процессы диагностирования кратных дефектов рассматриваются как управляемые цепи Маркова. Состояниями цепи считаются не состояния системы, а состояния процесса поиска. Предлагаемый в [16] метод диагностирования основан на применении метода динамического программирования. Для каждого состояния поиска вычисляется средняя стоимость управления, которая переводит его в конечное состояние, и определяются тесты, минимизирующие эту величину. Вычисления производятся по рекуррентным соотношениям Беллмана [2], начиная с тех состояний, из которых конечные достигаются за один шаг.
В работе [13] решение проблемы различимости кратных дефектов проводится с помощью точек блокирования. Метод определения максимальной различимости дефектов основан на вычислении приведенной матрицы диапазонов. Данный алгоритм определяет оптимальное расположение блокирующих точек для максимальной различимости с минимальной стоимостью решения. Вработе [14] задача поиска минимального числа точек блокирования решается путем формирования матрицы управляемых разрывов и назначения дополнительных точек блокирования, необходимых и достаточных для обеспечения различимости одиночных дефектов.
В работе [4] рассмотрена мультиагентная организация системного диагностирования больших цифровых систем. Контроль и диагностирование компонентов больших цифровых систем со структурой типа тороидальной решетки проводятся в три этапа. На первом этапе параллельно проверяются компоненты подсистем, выделенных первичной раскладкой; на втором и третьем этапах также параллельно проверяются подсистемы, полученные путем сдвига первичных подсистем на один шаг решетки вправо. Вработе была разработана мультиагентная организация системного диагностирования рассматриваемых БЦС и определены функциональные свойства и взаимосвязи агентов.
В [17] рассматривается задача функционального диагностирования нелинейных динамических систем с запаздыванием. Решение задачи предполагает формирование соотношений избыточности, по результатам их проверки делается вывод о правильности функционирования системы и о виде дефекта в системе. Для систем, описываемых дифференциальными уравнениями с полиномиальной правой частью, предлагается метод формирования соотношений избыточности. Метод допускает, что некоторые постоянные коэффициенты полиномов являются неизвестными.
В [5] описывается метод диагностирования многомерных динамических систем, заданных структурными схемами, содержащими нелинейные и нестационарные элементы. Суть метода состоит в переходе от динамического описания функционирования исходной системы к некоторому «статическому» описанию, представляющему собой совокупность полилинейных алгебраических уравнений. При этом задачи проверки правильности функционирования и поиска неисправных блоков в проверяемой системе сводятся к нахождению и анализу решений таких систем полилинейных уравнений.
Недетерминистические алгоритмы распознавания дефектов
Диагностирование неисправностей системы при помощи детерминистических методов распознавания дефектов эффективно при наличии математической модели ее функционирования. Эти модели в большинстве случаев можно анализировать лишь численными методами, что накладывает ограничение на их использование в реальном времени при поиске неисправностей и управлении технической системой. Почти все реальные процессы функционирования технических систем имеют нелинейное поведение, для них характерно возникновение нештатных ситуаций. Вэтих случаях обычно используют экспертов, то есть происходит вмешательство человека в процесс диагностирования и управления технической системой. Если детерминистические знания недоступны или математическое моделирование требует больших затрат расчетного времени, либо не обеспечивает требуемой точности, то могут быть использованы другие методы. Таким методом является моделирование знаний оператора при помощи эвристических познаний и стратегий логического вывода, как, например, это делается в экспертных системах на основе нечетких логик с реализацией их на базе аппаратных или программно-алгоритмических эмуляционных нейронных сетей [1].
В работе [8] предлагается использовать информационный критерий. На первом этапе алгоритма выбирается проверка, несущая максимальное количество информации о системе, а затем на основе выбранной точки контроля проводится тестирование системы. Врезультате тестирования выделяется подмножество блоков, подозреваемых на наличие дефектов. На каждом очередном шаге осуществляется оптимальный выбор очередной точки контроля, результат тестирования в которой позволяет выделить подмножество блоков, подозреваемых на наличие дефектов, из ранее полученного подмножества. Таким образом, каждый шаг данного алгоритма будет сокращать подмножество блоков, подозреваемых на наличие дефекта.
Использование современных информационных технологий позволило сформировать новые алгоритмы и методы, которые успешно применяются в технической диагностике. Внастоящее время в диагностических системах используются эволюционно-генетические алгоритмы [9] и нейронные сети. Врамках технического диагностирования эволюционно-генетические алгоритмы применяются для выбора или генерации тестовых данных при структурном тестировании аппаратных систем и программ.
В работе [12] рассматривается восстановление причин (диагнозов) по наблюдаемым следствиям (симптомам) на основе нечетких отношений и композиционного правила вывода Заде. Предлагается подход к проектированию нечетких систем диагностики, обеспечивающий решение нечетких логических уравнений совместно с построением и настройкой нечетких отношений на основе экспертно-экспериментальной информации. Настройка заключается в подборе таких функций принадлежности нечетких причин и следствий, а также нечетких отношений, которые минимизируют отличие между модельными и экспериментальными результатами диагностики. Для решения задачи оптимизации используется генетический алгоритм. Предлагаемый подход иллюстрируется компьютерным экспериментом и реальным примером диагностики.
Применение эволюционной оптимизации для тестирования объектно-ориентированного ПО впервые рассмотрено в работе [11]. Вданной работе с помощью генетического алгоритма генерируется тестовая программа для структурного тестирования классов. Классы представляются в виде исходного кода. Используется специализированный генетический алгоритм, содержащий нестандартные операторы мутации и кроссинговера. Данные генетические операторы работают на уровне выражений и изменяют цепочку вызова методов тестируемых классов в тестовой программе. Новые тестовые программы генерируются до тех пор, пока не будет достигнуто желаемое покрытие исходного кода тестируемых классов. Стоит отметить, что в данной работе не рассматривается проблема инкапсуляции, характерная для тестирования объектно-ориентированного ПО.
Выводы
На основании обзора литературных источников можно сделать вывод, что известные в настоящее время методы и алгоритмы диагностирования технических и программных систем носят, как правило, частный характер, т.е. разрабатываются заново для каждой практической задачи. Вобщем виде не решены задачи локализации дефекта производной кратности и учета ошибок контрольно-измерительной аппаратуры. Также было отмечено, что известные детерминистические алгоритмы требуют выполнения большого объема вычислений для получения результата.
Таким образом, проблема разработки алгоритмов оптимального поиска неисправностей в сложных технических и программных системах является на данный момент актуальной.