ПРИМЕНЕНИЕ САМОКОРРЕКТИРУЮЩИХСЯ СРЕД ДЛЯ ОБЕСПЕЧЕНИЯ ПРОАКТИВНОЙ БЕЗОПАСНОСТИ КОМПЬЮТЕРНЫХ СИСТЕМ
34
УДК 004.021
О. В. КАЗАРИН, В. Ю. СКИБА
ПРИМЕНЕНИЕ САМОКОРРЕКТИРУЮЩИХСЯ СРЕД ДЛЯ ОБЕСПЕЧЕНИЯ ПРОАКТИВНОЙ БЕЗОПАСНОСТИ
КОМПЬЮТЕРНЫХ СИСТЕМ
Для создания проактивно безопасных компьютерных систем предлагается применять алгоритмический инструментарий, использующий методологию самотестирующихся и самокорректирующихся программ. Данный подход наряду с использованием самокорректирующихся схем может применяться при создании проактивно безопасных компьютерных систем. Ключевые слова: проактивная безопасность, самотестирующаяся и самокорректирующаяся программы, вероятностная оракульная программа, свойство случайной самосводимости, устойчивость, тесты линейной и единичной состоятельности.
Введение. Проактивная безопасность — это органичное структурное свойство компьютерной системы (КС), которое позволяет ей защищать свои информационные ресурсы и сохранять их функциональность как на этапе разработки, так и на этапе эксплуатации КС.
В настоящей работе предлагается применять для создания проактивно безопасных КС алгоритмический инструментарий, использующий методы самотестирования и самокоррекции программ [1—3], который наряду с самокорректирующимися схемами (см., например, определения из работ [4, 5]), может стать одним из базовых элементов для создания таких КС.
Основные положения методологии создания самотестирующихся и самокорректирующихся программ. Пусть необходимо написать программу P для вычисления функции f так, чтобы P(x)=f(x) для всех значений x. Традиционные методы верификационного анализа и тестирования программ не позволяют убедиться с вероятностью, близкой к единице, в корректности результата выполнения программы, в частности, потому что тестовый набор входных данных, как правило, не перекрывает весь их возможный спектр. Один из методов решения данной проблемы заключается в создании так называемых самокорректирующихся и самотестирующихся программ [6—9].
Чтобы добиться корректного результата выполнения программы P, необходимо написать такую программу Tf, которая позволяла бы оценить вероятность того, что P(x)≠f(x) для любых x, т.е. вероятность ошибки выполнения программы P. При этом Tf может обращаться к P как к своей подпрограмме.
Обязательное условие функционирования программы Tf следующее: ее время выполнения, не учитывающее времени вызовов программы P, должно быть значительно меньше, чем время выполнения любой корректной программы для вычисления f. Самотестирование про-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 1
Применение самокорректирующихся сред для обеспечения проактивной безопасности КС 35
граммы P должно лишь незначительно увеличивать время ее выполнения. Кроме того, желательно, чтобы длина кода программы Tf составляла константный мультипликативный фактор от длины кода программы [1].
Пусть π — некоторая вычислительная задача и(или) задача поиска решения. Для x, рассматриваемого в качестве входа задачи, пусть π(x) обозначает результат решения задачи π. Пусть Р — программа (предположительно предназначенная) для решения задачи π, которая останавливается (например, не имеет зацикливаний) на всех входах задачи π. Будем говорить, что Р имеет дефект, если для некоторого входа x задачи π имеет место P(x)≠π(x).
Определим (эффективный) программный чекер Cπ для задачи π; CπP(I, k) является произвольной вероятностной машиной Тьюринга, удовлетворяющей следующим условиям. Для любой программы P (предположительно решающей задачу π), выполняемой на всех входах задачи π, для любого элемента I задачи π и для любого положительного k (параметра безопасности) имеет место:
— если программа P не имеет дефектов, т.е. P(x)=π(x) для всех входов x, тогда CπP(I,k) выдаст ответ „норма“ с вероятностью не менее 1–1/2k;
— если программа P имеет дефекты, т.е. P(x)≠π(x) для всех входов x, тогда CπP(I,k) выдаст ответ „сбой“ с вероятностью не менее 1–1/2k.
Самокорректирующаяся программа — это вероятностная программа Cf, которая помогает программе P скорректировать саму себя, если только последняя выдает корректный результат с низкой вероятностью ошибки, т.е. для любого x программа Cf вызывает программу P для корректного вычисления f(x), в то время как собственно сама P обладает низкой вероятностью ошибки.
Самотестирующейся / самокорректирующейся программной парой называется пара программ вида (Tf,Cf). Предположим, что пользователь может взять любую программу P, которая целенаправленно вычисляет f и тестирует саму себя при помощи программы Tf. Если P проходит такие тесты, тогда по любому x пользователь может вызвать программу Cf, которая, в свою очередь, вызывает P для корректного вычисления f(x). Даже если программа P некорректна для некоторых входных значений, ее в данном случае все равно можно уверенно использовать для корректного вычисления f(x) для любого значения x.
Кроме того, если удастся написать программу P′ для вычисления f, тогда некоторая пара (Tf,Cf) может использоваться для самотестирования и самокоррекции P′ без какой-либо ее модификации.
Вероятностная программа M является вероятностной оракульной, если она может вызывать другую программу, которая является исполнимой во время выполнения M (MA означает, что M может делать вызовы программы A).
Пусть программа P предположительно вычисляет функцию f; I является объединением подмножеств In, где n∈N, Dp={Dn|n∈N} есть множество распределений вероятности Dn над In. Далее, пусть err(P,f,Dn) — это вероятность того, что P(x)≠f(x), где x выбрано случайным образом в соответствии с распределением Dn из подмножества In. Пусть β есть некоторый параметр безопасности. Тогда (ε1,ε2)-самотестирующейся программой для функции f в отношении Dp с параметрами 0≤ε1
УДК 004.021
О. В. КАЗАРИН, В. Ю. СКИБА
ПРИМЕНЕНИЕ САМОКОРРЕКТИРУЮЩИХСЯ СРЕД ДЛЯ ОБЕСПЕЧЕНИЯ ПРОАКТИВНОЙ БЕЗОПАСНОСТИ
КОМПЬЮТЕРНЫХ СИСТЕМ
Для создания проактивно безопасных компьютерных систем предлагается применять алгоритмический инструментарий, использующий методологию самотестирующихся и самокорректирующихся программ. Данный подход наряду с использованием самокорректирующихся схем может применяться при создании проактивно безопасных компьютерных систем. Ключевые слова: проактивная безопасность, самотестирующаяся и самокорректирующаяся программы, вероятностная оракульная программа, свойство случайной самосводимости, устойчивость, тесты линейной и единичной состоятельности.
Введение. Проактивная безопасность — это органичное структурное свойство компьютерной системы (КС), которое позволяет ей защищать свои информационные ресурсы и сохранять их функциональность как на этапе разработки, так и на этапе эксплуатации КС.
В настоящей работе предлагается применять для создания проактивно безопасных КС алгоритмический инструментарий, использующий методы самотестирования и самокоррекции программ [1—3], который наряду с самокорректирующимися схемами (см., например, определения из работ [4, 5]), может стать одним из базовых элементов для создания таких КС.
Основные положения методологии создания самотестирующихся и самокорректирующихся программ. Пусть необходимо написать программу P для вычисления функции f так, чтобы P(x)=f(x) для всех значений x. Традиционные методы верификационного анализа и тестирования программ не позволяют убедиться с вероятностью, близкой к единице, в корректности результата выполнения программы, в частности, потому что тестовый набор входных данных, как правило, не перекрывает весь их возможный спектр. Один из методов решения данной проблемы заключается в создании так называемых самокорректирующихся и самотестирующихся программ [6—9].
Чтобы добиться корректного результата выполнения программы P, необходимо написать такую программу Tf, которая позволяла бы оценить вероятность того, что P(x)≠f(x) для любых x, т.е. вероятность ошибки выполнения программы P. При этом Tf может обращаться к P как к своей подпрограмме.
Обязательное условие функционирования программы Tf следующее: ее время выполнения, не учитывающее времени вызовов программы P, должно быть значительно меньше, чем время выполнения любой корректной программы для вычисления f. Самотестирование про-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 1
Применение самокорректирующихся сред для обеспечения проактивной безопасности КС 35
граммы P должно лишь незначительно увеличивать время ее выполнения. Кроме того, желательно, чтобы длина кода программы Tf составляла константный мультипликативный фактор от длины кода программы [1].
Пусть π — некоторая вычислительная задача и(или) задача поиска решения. Для x, рассматриваемого в качестве входа задачи, пусть π(x) обозначает результат решения задачи π. Пусть Р — программа (предположительно предназначенная) для решения задачи π, которая останавливается (например, не имеет зацикливаний) на всех входах задачи π. Будем говорить, что Р имеет дефект, если для некоторого входа x задачи π имеет место P(x)≠π(x).
Определим (эффективный) программный чекер Cπ для задачи π; CπP(I, k) является произвольной вероятностной машиной Тьюринга, удовлетворяющей следующим условиям. Для любой программы P (предположительно решающей задачу π), выполняемой на всех входах задачи π, для любого элемента I задачи π и для любого положительного k (параметра безопасности) имеет место:
— если программа P не имеет дефектов, т.е. P(x)=π(x) для всех входов x, тогда CπP(I,k) выдаст ответ „норма“ с вероятностью не менее 1–1/2k;
— если программа P имеет дефекты, т.е. P(x)≠π(x) для всех входов x, тогда CπP(I,k) выдаст ответ „сбой“ с вероятностью не менее 1–1/2k.
Самокорректирующаяся программа — это вероятностная программа Cf, которая помогает программе P скорректировать саму себя, если только последняя выдает корректный результат с низкой вероятностью ошибки, т.е. для любого x программа Cf вызывает программу P для корректного вычисления f(x), в то время как собственно сама P обладает низкой вероятностью ошибки.
Самотестирующейся / самокорректирующейся программной парой называется пара программ вида (Tf,Cf). Предположим, что пользователь может взять любую программу P, которая целенаправленно вычисляет f и тестирует саму себя при помощи программы Tf. Если P проходит такие тесты, тогда по любому x пользователь может вызвать программу Cf, которая, в свою очередь, вызывает P для корректного вычисления f(x). Даже если программа P некорректна для некоторых входных значений, ее в данном случае все равно можно уверенно использовать для корректного вычисления f(x) для любого значения x.
Кроме того, если удастся написать программу P′ для вычисления f, тогда некоторая пара (Tf,Cf) может использоваться для самотестирования и самокоррекции P′ без какой-либо ее модификации.
Вероятностная программа M является вероятностной оракульной, если она может вызывать другую программу, которая является исполнимой во время выполнения M (MA означает, что M может делать вызовы программы A).
Пусть программа P предположительно вычисляет функцию f; I является объединением подмножеств In, где n∈N, Dp={Dn|n∈N} есть множество распределений вероятности Dn над In. Далее, пусть err(P,f,Dn) — это вероятность того, что P(x)≠f(x), где x выбрано случайным образом в соответствии с распределением Dn из подмножества In. Пусть β есть некоторый параметр безопасности. Тогда (ε1,ε2)-самотестирующейся программой для функции f в отношении Dp с параметрами 0≤ε1