1300

Катастрофоустойчивые компьютерные системы и сервисы

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

Что касается безопасности (далее речь идет о функциональной безопасности (safety)), то в рамках данной работы будем руководствоваться простым постулатом: пока система надежна (работоспособна), она безопасна. Это справедливо, если уровень, на котором должна обеспечиваться работоспособность, корректно обоснован и, если сформулированы и выполняются требования к уровню отказоустойчивости (например, требование, связанное с принципом единичного отказа [8]). В этом случае исключается ситуация, когда первый же отказ может стать критичным. Кроме того, здесь не рассматриваются методы, специфические для обеспечения безопасности (независимая верификация, диверсность и др. [9]).

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

Настоящая работа является развитием работы [10], в части автоматно-базисного подхода, и работ [11—14], где сформулированы принципы и реализованы методы синтеза систем на избыточных логических базисах.

Автоматно-базисный подход к созданию надежных и безопасных систем

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

1.Концептуальным принципом является базисный подход

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

131

Катастрофоустойчивые компьютерные системы и сервисы

Пусть требуется сохранить некоторое множество функ-

ций ΦR Φ после воздействия. Тогда это можно описать ком-

позицией оставшихся функций или цепочками из Φ×* , где * — соответствующая итерация. При этом могут дополнительно заданы временные Tо и стоимостные ограничения Cо.

Функции системы представляются автоматными моделями, описывающими преобразование входных данных в выходные. Автоматная модель представляет собой пятерку [15]:

S= <X, Y, Z, ϕ, ψ>,

вкоторой Х = {х1, х2,..., хi} — конечное входное множество (входной алфавит); Y = {y1, y2,..., yj} — конечное множество внутренних состояний автомата (алфавит состояний); Z = {z1, z2,..., zk} — конечное выходное множество (выходной алфавит);

ϕ — функция переходов (из состояния в другие состояния); ψ — функция выходов; функция переходов представляет собой отображение вида ϕ: X × X a Y; функция выходов представляет со-

бой отображение вида ψ: Х × Y → Z.

Таким образом, вместо абстрактных функций системы рассматривается множество автоматов A ={a1, a2 ,..., an }, дегради-

рующих в результате воздействийΨ* :

A× ={a×j i },i =1, r, j =1, k, k ≤ n.

Причем ставится условие обеспечения восстановления части ав-

томатов AR A после воздействия с заданными ограничениями Tо, Cо. В этом случае необходима суперпозиция автоматов, т.е.

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

Однако проблема функциональной полноты последовательностного автомата в общем случае алгоритмически неразрешима [16]. Тем не менее, любой автомат может быть представлен декомпозицией логического преобразователя и элементов памяти, а проблема функциональной полноты логического преобразователя разрешима в соответствии с теоремой Поста [17]. Логический

133

Катастрофоустойчивые компьютерные системы и сервисы

и так далее, пока подфункции на определенном шаге не будут реализованы одним элементом.

Такое представление должно быть оптимальным по пока-

зателю количества операций вида x1x2 x3 x4.

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

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

f = f1 f2 f3 f4 ,

f1 = f2 = f3 = f4 = f .

При изменении любой одной из четырех функций функция системы не изменяется:

f =1f2 f3 f4 = f ff = f, f1 =1. f =0 f2 f3 f4 =0 ff = f, f1 = 0.

f = f 1 f2 f3 f4 = f f ff = 0 ff = f, f1 = f 1.

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

f = f1 f2 f1 f3 f2 f3 , f1 = f2 = f3 = f .

Например:

f =1 f2 1 f3 f2 f3 = f f ff = f , f1 =1.

135

Катастрофоустойчивые компьютерные системы и сервисы

Например, может быть реализован частично резервирован-

ный ФПТ базис x1x2 x3x4 в виде

f = x1 x2 x1 x2 x3 x4 x3 x4 .

Для сохранения базисной функции 2И-НЕ х1 х2 при модели однократных константных отказов может быть предложено выражение

(x1 x2 x3 x4 )(x5 x6 x7 x8 ),

т.е.

(x1 1 x2 1 x1 2 x2 2 )(x1 3 x2 3 x1 4 x2 4 ).

Дальнейшим развитием подхода может быть сохранение более сложного и более эффективного ФПТ базиса x1x2 x3 x4 —

для этого необходима функция

(x1 1 x2 1 x1 2 x2 2 )(x1 3 x2 3 x1 4 x2 4 ) (x3 1 x4 1 x3 2 x4 2 )(x3 3 x4 3 x3 4 x4 4 ).

Концепция расширения логического базиса для безопасных инфраструктур

Сложные объекты инфраструктур, как правило, слабо формализуются и в прямом виде, логические преобразования, описанные выше, вряд ли могут быть применены. В ряде случаев ограничиваются лишь графовыми моделями, описывающими отношения между объектами. Например, при анализе отказоустойчивости сетей (исследование и создание высоконадежных живучих управляющих информационных систем в ИПУ РАН [20]). Другой пример — переход от автоматных моделей к авто- матно-непрерывным с целью анализа траекторий систем в критических ситуациях [21].

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

137

Катастрофоустойчивые компьютерные системы и сервисы

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

Имеется две системы реальных объектов, процессов, явлений C — защищаемая система и K — угрожаемая система. Это необязательно технические системы, например, это могут быть и социальные, и биологические системы.

Вначале требуется получить математические объекты (модели) ΦC и ΨK , описывающие системы С и K.

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

Задача анализа на этапе проектирования может заклю-

чаться в получении Φ×C и определении, насколько эта модифи-

цированная модель Φ×C соответствует задаче проектирования

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

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

модели-2 (толерантно-базисной) ΦC2 , и ее преобразований R, та-

ких, что R(Φ×C2 ) удовлетворяет поставленным требованиям и ог-

раничениям, а ΦC2 является катастрофоустойчивой либо катаст-

рофобезопасной.

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

Заключение

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

139