Этап 6. Найдем размер зарплаты сотрудника по имени Alf плюс размер зарплаты всех сотрудников, используя выражения BE OR Т и BE OR NOT Т.

WITH ( STATS WHERE ( SEX = M AND

OCCUPATION = Programmer OR AUDITS = 0 ) AS X : SUM ( X, SALARY )

Результат: 488 ООО.

WITH ( STATS WHERE ( SEX = M AND

OCCUPATION = Programmer OR NOT ( AUDITS = 0 ) ) AS X : SUM ( X, SALARY )

Результат: 290 ООО; 488 ООО + 290 ООО = 778 ООО.

Этап 7. Найдем размер зарплаты сотрудника по имени Alf, вычитая из общей суммы (полученной на этапе 5) результат, полученный на этапе 6.

Результат: 50 ООО.

Принцип действия общего трекера схематически представлен на рис. 16.4.

set ( BE ) = ( set ( BE OR Т ) + set ( BE OR NOT T ) ) - set ( T OR NOT T )

Множество, идентифицированное выражением Г

Множество, идентифицированное

Множество, идентифицированное выражением NOT Т

булевым выражением BE -т.е.

Рис. 16.4. Принцип функционирования общего трекера Т

Если исходное предположение оказалось неверным (т.е. Т не является общим трекером), тогда одно или оба выражения ( BE OR Т ) и ( BE OR NOT Т ) могут оказаться недопустимым. Например, если кардинальности для результирующих наборов для выражений BE и Т равны р и q соответственно, где р < q и b < q < 2b, то кардинальность результирующего множества для ( BE OR Т ), которая не может превышать значение р + q, может оказаться меньше Ь. В такой ситуации необходимо выбрать другой вариант выражения для общего трекера и повторить попытку. В [16.6] предполагается, что на практике не так уж сложно найти подходящее выражение для общего трекера. В приведенном здесь частном примере исходный вариант сразу оказался общим трекером (кардинальность его результирующего набора данных равна 5) и оба запроса на этапе 3 также оказались допустимыми.

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

Что в таком случае можно сделать? Некоторые варианты решения этой проблемы уже предлагались в литературе, но все же пока нельзя сказать определенно, является ли какой-либо из них удовлетворительным во всех отношениях. Например, в одном из вариантов предлагается организовать обмен данными ( data swapping ), т.е. обмен значениями атрибутов между кортежами, осуществляемый таким образом, чтобы поддерживалась лишь статистическая точность. При этом даже если злоумышленнику удастся идентифицировать отдельное значение (например, некоторое значение зарплаты), то у него не будет способа узнать, какому именно кортежу (в нашем примере - сотруднику) оно принадлежит. Сложность этого подхода заключается в необходимости отыскать множество тех записей, между которыми можно будет организовать обмен значениями соответствующим образом. Подобные затруднения имеют место и при использовании большинства других методов. В данный момент, видимо, придется согласиться с выводами Деннинга [16.6] о том, что методы нарушения защиты данных просты и не связаны с большими расходами. Поэтому требование обеспечения полной секретности конфиденциальной информации несовместимо с требованием возможности вычисления точных статистических показателей для произвольных подмножеств данных в базе. По крайней мере одно из этих требований должно быть снято прежде, чем можно будет поверить в гарантии обеспечения секретности .

16.5. Шифрование данных

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

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

Пример. Пусть в качестве открытого текста дана следующая строка.

AS KINGFISHERS CATCH FIRE

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

ELIOT

Ниже описывается используемый алгоритм шифрования.

1. Разбейте открытый текст на блоки, длина которых равна длине ключа шифрования. AS+KI NGFIS HERS+ CATCH +FIRE

(Здесь пробелы обозначены знаком + .)

2. Замените каждый символ открытого текста целым числом в диапазоне 00-26, используя для пробела число 00, для А - число 01, для Z - число 26. В результате получится такая строка цифр.

0119001109 1407060919 0805181900 0301200308 0006091805

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

0512091520

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

0119001109 1407060919 0805181900 0301200308 0006091805 0512091520 0512091520 0512091520 0512091520 0512091520 0604092602 1919152412 1317000720 0813021801 0518180625

5. Замените каждое число в нижней строке п. 4 соответствующим текстовым символом.

FDIZB SS0XL MQ+GT HMBRA ERRFY

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

Стандарт шифрования данных

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