Многочлены Жегалкина

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

Определение 4.4. Многочленами Жегалкина назваются формулы над множеством функций F_J={ 0, 1, *, +} (здесь * - это другое обозначение конъюнкции).

Таким образом, каждый многочлен Жегалкина (возможно, после раскрытия скобок и "приведения" подобных членов) представляет сумму (по модулю 2) положительных (монотонных) элементарных конъюнкций (т.е. элементарных конъюнкций без отрицаний). Поскольку для + и * справедливы законы ассоциативности, мы будем при записи многочлена Жегалкина опускать скобки, считая, что * связывает аргументы сильнее, чем +

Нетрудно проверить, что справедливы следующие эквивалентности:

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

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

Доказательство.Существование такого многочлена следует из того, что для любой ДНФ или КНФ можно с помощью указанных эквивалентностей найти эквивалентный многочлен Жегалкина: (J1)-(J3) позволяют заменять все вхождения , и на + и *, а (J4) - перемножать получившиеся после такой замены многочлены.

Для доказательства единственности представления подсчитаем число различных многочленов Жегалкина от переменных. Каждая положительная элементарная конъюнкция имеет вид X_i1 * … * X_ik , где 1 i₁ < … < i_k n . Таких конъюнкций столько же, сколько подмножеств множества , т.е. 2_n . (Конъюнкция, соответствующая пустому подмножеству переменных равна 1). Упорядочим их произвольным образом (например, лексикографически): Tогда каждый многочлен Жегалкина единственным образом можно представить как сумму

где каждый из коэффициентов _i равен 0 или 1. Следовательно, число многочленов Жегалкина равно , т.е. числу всех булевых функций от n переменных. Поэтому каждая функция задается в точности одним многочленом Жегалкина.

Пример 4.3. Пусть функция f(X₁,X₂,X₃) задается ДНФ . Найдем полином Жегалкина, который также задает эту функцию.

Сначала заменяем на *, а затем,применяя эквивалентность (J1), устраняем отрицания и получаем:

Перемножив по правилам (J4), получим:

Эквивалентность (J3) позволяет устранить :

Снова, используя (J4), перемножим первые две скобки и устраним повторения переменных в конъюнкциях:

Упростим эту сумму, используя эквивалентности: X + X 0 и X + 0 X. В результате получим многочлен Жегалкина

эквивалентный исходной ДНФ Φ.

Если функция f(X₁, …, X_n) задана таблично, то для построения реализующего ее многочлена Жегалкина можно применить метод неопределенных коэфициентов. Сопоставим i-ому набору значений переменных в таблице положительную конъюнкцию переменных, равных 1 в этом наборе. В частности, K₁ - пустая конъюнкция, K₂ = X_n, K₃ = X_n-1, K₄ = (X_n * X_n-1). и т.д. Тогда для получения нужного многочлена Жегалкина достаточно определить все коэффициенты _i, i = 1, …, 2ⁿ, в выражении

Подставляя в это равенство значения переменных из набора σ_i, i = 1, …, 2ⁿ, мы получим 2ⁿ линейных уравнений относительно 2ⁿ неизвестных коэффициентов _i. Решив эту систему, получим требуемый многочлен Жегалкина. Эта система треугольная и легко решается "сверху-вниз": каждое _i определяется по значениям ₁, …, _i-1 из уравнения, соответствующего набору σ_i.

Пример 4.4. Рассмотрим в качестве примера функцию f(X₁, …, X_n), заданную следующей таблицей.

Многочлен Жегалкина для нее (как и для любой функции от 3-х переменных) представляется в виде

В этом представлении в индексах у коэффициентов перечислены переменные, входящие в соответствующие конъюнкции.

Последовательно подставляя значения переменных и f из таблицы, получаем:

Следовательно, функция f(X₁, X₂, X₃) представляется многочленом Жегалкина

2. Классификация firewall’ов. Пакетные фильтры, stateful inspection firewall’ы и прокси прикладного уровня.

Firewall’ы защищают компьютеры и сети от попыток несанкционированного доступа с использованием уязвимых мест, существующих в семействе протоколов ТСР/IP. Дополнительно они помогают решать проблемы безопасности, связанные с использованием уязвимых систем и с наличием большого числа компьютеров в локальной сети. Существует несколько типов firewall’ов, начиная от пакетных фильтров, встроенных в пограничные роутеры, которые могут обеспечивать управление доступом для IP-пакетов, до мощных firewall’ов, которые могут закрывать уязвимости в большом количестве уровней семейства протоколов ТСР/IP, и еще более мощных firewall'ов, которые могут фильтровать трафик на основании всего содержимого пакета.

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

Современные firewall’ы могут работать совместно с такими инструментальными средствами, как системы обнаружения проникновений и сканеры содержимого e-mail или web с целью нахождения вирусов или опасного прикладного кода. Но в отдельности firewall не обеспечивает полной защиты от всех проблем, порожденных Интернетом. Как результат, firewall’ы являются только одной частью архитектуры информационной безопасности. Обычно они рассматриваются как первая линия обороны, однако их лучше воспринимать как последнюю линию обороны в организации; организация в первую очередь должна делать безопасными свои внутренние системы. Для внутренних серверов, персональных компьютеров и других систем должны своевременно выполняться все обновления как самих систем, так и других систем обеспечения безопасности, например, антивирусного ПО.

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

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

Сначала сделаем обзор стека протоколов OSI и покажем, на каком уровне функционируют различные типы firewall’ов, такие как пакетные фильтры, stateful inspection firewall’ы и прикладные прокси.

Затем опишем различные окружения firewall’а, например, комбинации конкретных компонентов обеспечивающие то или иное решение. Приведем примеры расположения firewall’ов и их взаимодействий с другими инструментальными средствами безопасности. Также опишем прочие функции современных firewall’ов, такие как использование их в качестве конечных точек VPN, трансляция IP-адресов, фильтрация содержимого web или e-mail.

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