Главная » SQL, Базы данных » СТАТИСТИЧЕСКИЕ БАЗЫ ДАННЫХ

0

Статистической (в приведенном здесь контексте) называется база данных, в которой допускаются запросы с агрегированием данных (суммированием, вычислением среднего значения и т.д.), но не допускаются запросы по  отношению к элементарным данным. Например, в статистической базе данных  разрешается выдача запроса "Какова средняя зарплата служащих?", тогда как  выдача запроса "Какова зарплата служащего Мэри?" запрещена.

Проблема статистических баз данных заключается в том, что иногда с помощью логических заключений на основе выполнения разрешенных запросов можно вывести ответ, который прямо может быть получен только с помощью запрещенного запроса. Как указывается в [17.8], "Обобщенные значения содержат следы исходной информации, и она может быть восстановлена злоумышленником после  соответствующей обработки достаточного количества этих обобщенных значений. Такой процесс называется дедуктивным формированием конфиденциальной  информации с помощью логического вывода". Следует отметить то, что эта проблема, к сожалению, становится все более и более важной по мере  того,  как  использование  хранилищ  данных  (см.  главу  22)  получает  все  большее распространение.

Рассмотрим более подробный пример. Предположим, что в базе данных содержится только одна переменная отношения, STATS, представленная на рис. 17.2. Предположим

также для простоты, что все атрибуты определены на основе примитивных типов данных

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

себе целью узнать размер зарплаты работника по имени Alf. Наконец предположим, что из других источников пользователь и узнал, что Alf — программист мужского пола. Проанализируем представленные ниже запросы3.

3    Для  сокращения  объема  текста  все  запросы  данного  раздела  представлены  на   языке Tutorial D в сокращенной форме. Например, в запросе 1 выражение COUNT ( х )  следовало бы представить в более полной форме (скажем) как EXTEND TABLE_DEE   ADD   COUNT( X )     AS RESULT1.

1.         WITH ( STATS WHERE SEX = ‘M’ AND .

OCCUPATION  =   ‘Programmer’    )

AS  X  : COUNT   (  X  )

Результат: 1.

2.         WITH ( STATS WHERE SEX = ‘M’ AND OCCUPATION = ‘Programmer’ ) AS X

: SUM ( X, SALARY )

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

Рис. 17.2. Переменная отношения  STATS (примеры  значений)

Очевидно, что защита базы данных была нарушена, хотя пользователь и  прймения только разрешенные ему статистические запросы. Как показано в примере, если пользователь сумеет найти такое логическое выражение, которое позволит ему идентифицировать некоторую личность, то информация о данной личности окажется незащищенной. По этой причине система должна отвергать любые запросы, для которых кардинальность обобщаемого  множества  окажется  меньше  некоторого  установленного  минимального значения Ь. Это также означает, что система должна отвергать запросы, кардинальность обобщаемого  множества которых превосходит значение п-Ь (где п — кардинальность исходной  переменной отношения). Дело в том, что можно привести еще один  пример нарушения защиты этой базы данных, осуществляемого посредством  ввода  показанной ниже последовательности запросов 3-6.

3.         COUNT    (   STATS   )

Результат: 12.

4.         WITH   (  STATS  WHERE  NOT   (  SEX  =   ‘M’   AND OCCUPATION  =   ‘Programmer’    )     )

AS  X   : COUNT   (  X  )

Результат: 11; 12 11 = 1.

5.         SUM   (   STATS,   SALARY   )

Результат: 728 000.

6.         WITH ( STATS WHERE NOT ( SEX = ‘M’ AND OCCUPATION = ‘Programmer’ ) ) AS X

: SUM ( X, SALARY )

Результат: 678 000; 728 000 678 000 = 50 000.

К сожалению, можно легко показать, что в общем нарушения защиты нельзя предотвратить, просто разрешая выполнение лишь таких запросов, в которых  агрегируемое множество имеет кардинальность с в диапазоне b < с < п Ь.  Еще  раз обратимся к примеру на рис. 17.2. Если b = 2, то в таком случае будут разрешены запросы только с кардинальностью с, находящейся в диапазоне 2 < с  <  8. Это означает, что следующее логическое выражение использовать нельзя.

SEX = ‘M’ AND OCCUPATION = ‘Programmer’

Теперь рассмотрим приведенную ниже последовательность запросов.

7.          WITH ( STATS WHERE SEX = ‘M’ ) AS X :

COUNT ( X )

Результат: 4.

8.         WITH ( STATS WHERE SEX = ‘M’ AND NOT

( OCCUPATION. = ‘Programmer’ ) ) AS X :

COUNT     (   X   )

Результат: 3.

На основании запросов 7 и 8 пользователь и может сделать вывод, что существует только один мужчина-программист, следовательно, это и есть Alf (поскольку пользователь и уже знает из других источников, что сотрудник по имени Alf является мужчиной и программистом). Зарплата этого сотрудника может быть определена следующим образом.

9.          WITH ( STATS WHERE SEX = ‘M’ ) AS X :

SUM ( X, SALARY )

Результат: 328 000.

10.     WITH ( STATS WHERE SEX = ‘M’ AND NOT

( OCCUPATION = ‘Programmer’ ) ) AS X

: SUM ( X, SALARY )

Результат: 278 000; 328 000 278 000 = 50 000.

Логическое  выражение  SEX  =  ‘ M ‘  AND  OCCUPATION  =  ‘  Programmer’  называется индивидуальным средством слежения (individual tracker) для человека по имени Alf [17.8], поскольку оно позволяет отыскать информацию об отдельном человеке по имени Alf. В общем случае, если пользователю известно некоторое логическое выражение BE, идентифицирующее некоторого человека I, и если логическое выражение BE может быть выражено в виде ВЕ1 AND BE2, то  логическое выражение ВЕ1 AND NOT BE2 является индивидуальным средством  слежения для человека с идентификатором I (при условии, что в системе разрешено использовать выражения ВЕ1 и ВЕ1 AND NOT BE2, т.е. оба они приводят к результату, кардинальность с которого находится в диапазоне b < с < п b). Причина этого заключается в том, что определенное с помощью BE множество идентично разности между множеством, определенным с помощью ВЕ1, и множеством, определенным с помощью ВЕ1 AND NOT BE2, что наглядно представлено на рис. 17.3.

{ X : BE } { х : ВЕ1 AND BE2 }

≡ {х : ВЕ1 } MINUS { X : ВЕ1 AND NOT BE2 }

Рис. 17.3. Индивидуальное средство слежения ВЕ1 AND NOT ВЕ2

В [17.8] упомянутые здесь идеи обобщены и показано, что практически для любой ста тистической базы данных всегда могут быть определены общие средства слежения (в от личие от множества средств слежения за личными данными). Общее средство слежения (general tracker) — это логическое выражение, которое может быть использовано для по иска ответа на любой запрещенный запрос, т.е. запрос, включающий недопустимое логи ческое  выражение.  (В  противоположность  этому,  индивидуальное  средство  слежения работает только на основе запросов, включающих конкретные запрещенные выражения.) Фактически оказывается, что любое логическое выражение с результирующим набором данных  с кардинальностью с в диапазоне 2b < с < п 2b является общим  средством слежения (здесь b должно быть меньше, чем п/4, что обычно всегда  выполняется на практике). Как только такое средство слежения будет найдено, сразу же можно будет по лучить ответ на запрос, включающий запрещенное  логическое выражение BE, ЧТО на глядно показано в следующем примере. (Для определенности рассмотрим случай, в кото ром кардинальность результирующего множества логического выражения BE меньше b. Случай, когда b больше п b, обрабатывается аналогично.) Обратите внимание на то, что по определению т является общим средством слежения тогда и только тогда, когда NOT т также является общим средством слежения.

Пример. Предположим снова, что b = 2; тогда общим средством слежения  будет любое логическое выражение с кардинальностью результирующего множества с в диапазоне 4 < с < 6. Еще раз предположим, что пользователю u известно из внешних источников, что сотрудник по имени Alf является  мужчиной и программистом, т.е. запрещенное логическое выражение BE выглядит так, как показано ниже.

SEX = ‘M’ AND OCCUPATION = ‘Programmer’

Допустим также, что пользователь и хочет узнать размер зарплаты сотрудника Alf. В этом случае общее средство слежения придется применить дважды:  сначала, чтобы удостовериться, что BE однозначно идентифицирует сотрудника по имени Alf (этапы 2—4), а затем непосредственно для того, чтобы определить  размер зарплаты сотрудника Alf (этапы 5-7).

Этап 1. Попробуем найти выражение для общего средства слежения т. В качестве первого приближения выберем следующее выражение.

AUDITS   =   0

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

WITH ( STATS WHERE AUDITS = 0 ) AS X : COUNT ( X )

Результат: 5.

WITH ( STATS WHERE NOT ( AUDITS = 0 ) ) AS X : COUNT ( X )

Результат: 5; 5 + 5 = 10. Теперь можно легко определить, что выбранное выше выражение т действительно оказалось общим средством слежения.

Этап 3. Найдем результат сложения общего количества сотрудников в базе данных с количеством сотрудников, для которых удовлетворяется  неразрешенное выражение BE, для чего используем выражения BE OR Т и ВЕ OR NOT T.

WITH ( STATS WHERE ( SEX = ‘M’ AND OCCUPATION = ‘Programmer’ OR AUDITS =

0 ) AS X : COUNT ( X )

Результат: 6.

WITH ( STATS WHERE ( SEX = ‘M’ AND OCCUPATION = ‘Programmer’ OR NOT (

AUDITS = 0 ) ) AS X : COUNT ( X )

Результат: 5; 6 + 5 = 11.

Этап 4. На основании полученных выше результатов можно сделать заключение, что количество сотрудников, к которым относится логическое выражение BE, равно единице (результат этапа 3 минус результат этапа 2), т.е. логическое выражение BE однозначно идентифицирует сотрудника по имени Alf.

Теперь на этапах 5 и 6 повторим запросы, использованные на этапах 2 и  3, но вместо [ии COUNT укажем функцию SUM.

Этап 5. С помощью выражений т и NOT T найдем размер зарплаты всех сотрудников в базе данных.

WITH ( STATS WHERE AUDITS = 0 ) AS X

: SUM ( X, SALARY )

Результат: 438 000.

WITH ( STATS WHERE NOT ( AUDITS = 0 ) ) AS X : SUM ( X, SALARY )

Результат: 290 000; 438 000 + 290 000 = 728 000.

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

WITH ( STATS WHERE ( SEX = ‘M’ AND OCCUPATION = ‘Programmer’ OR AUDITS =

0 ) AS X : SUM ( X, SALARY )

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

WITH ( STATS WHERE ( SEX = ‘M’ AND   . ,.,_.

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

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

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

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

{ X : BE } ≡ ( { X : BE OR T } UNION { X : BE OR NOT T } ) MINUS { X : T OR NOT T }

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

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

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

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

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

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии