Введение в системы БД (542480), страница 157
Текст из файла (страница 157)
Например, в статистической базе данных разрешается выдача запроса "Какова средняя зарплата программистов?", тогда как выдача запроса "Какова зарплата программиста Мэри?" запрещена. Проблема статистических баз данных заключается в том, что иногда с помощью логических заключений на основе выполнения разрешенных запросов можно вывести ответ, который прямо может быть получен только с помощью запрещенного запроса. Как указывается в 116.6], "Обобщенные значения содержат следы исходной информации, и она может быть восстановлена злоумышленником после соответствующей обработки этих обобщенных значений. Такой процесс называется логическим выводом конфиденциачьной информации". Следует отметить, что эта проблема, к сожалению, становится все более и более важной по мере того, как использование хранилищ данных (см.
главу 21) получает все большее распространение. Предположим, что в базе данных содержится только одна переменная-отношение, ЯТАТЯ, представленная на рис. 16.2. Предположим также для простоты, что все атрибуты определены на основе примитивных типов данных (т.е. числового и строкового). Далее предположим, что некоторому пользователю 0 в этой базе данных разрешено выполнять только статистические запросы, но он поставил себе целью узнать размер зарплаты работника по имени 'А11'. Наконец предположим, что из других источников пользователь Р узнал, что работник по имени 'А11' является мужчиной и программистом.
Проанализируем представленные ниже запросы. 1. И1ТН ( ЯТАТЯ ИНЕНЕ ЯЕХ = 'М' АИР ОССРРАТ10Н = 'Ргоагапапег' ) АЯ Х СОПИТ ( Х ) Результат; ! . 2. И1ТН ( ЯТАТЯ ИНЕНЕ ЯЕХ = 'М' АИР ОССРРАТ10Н = 'Ргоагапапег' ) АЯ Х ЯНМ ( Х, ЯАЕАНХ Результат: 50 000. ° 615 Глава 16. Зац(ипза данньп ХАМЕ ВЕК СННЛКЕХ ОСС1)РАТ10Х ЯА1 АНУ ТАХ АШЗ(ТЯ Рнс. ! 6.2, Переиеннал-отношение ЯТАТЯ Очевидно, что защита базы данных была нарушена, хотя пользователь 0 применил только разрешенные ему статистические запросы. Как показано в примере, если пользователь сумеет найти такое логическое выражение, которое позволит ему идентифицировать некоторую личность, то информация о данной личности окажется незащищенной.
По этой причине система должна отвергать любые запросы, для которых кардинальность обобщаемого множества окажется менее некоторого установленного минимального значения Ь. Это также означает, что система должна отвергать запросы, кардинальность обобщаемого множества которых превосходит значение Н-Ь (где Н вЂ” кардинальность исходной переменной-отношения). Дело в том, что можно привести еще один пример нарушения зашиты этой базы данных, осуществляемого посредством ввода показанной ниже последовательности запросов 3-6. 3.
СОНЕТ ( БТАТЯ ) Результат: 12. 4. НРТН ( ЯТАТБ ННЕНЕ НОТ ( БЕХ н 'И' АНР ОССОРАТ10Н = 'Ргодгапвег' ) ) АЯ Х СОНЕТ ( Х ) Резулылат: 11;!2 — 11 = 1. 5. БОИ ( ЯТАТБ, БАЕАНУ ) Результат: 728 000. б. НТТН ( БТАТЯ ННЕНЕ НОТ ( ЯЕХ = 'И' АНО ОССОРАТ1ОН = 'Ргодгащпег' ) ) АЯ Х ЯОИ ( Х, ЯАТЛНТ ) Результат: 678 000; 728 000 — 678 000 = 50 000. ° К сожалению, можно легко показать, что для исключения нарушений зашиты совершенно недостаточно определить допустимость запроса просто по значению кардинальности с обобщаемого им множества, которое должно находиться в диапазоне Ь < с < Х вЂ” Ь. Еще раз обра- 616 Часть )'. Дополнительные аспекты А)1 Веа Сагу 1|а|ни Еб Рау 0цу На! 1уу шоу М У Р Е М Р М М Р Е РгоЕгапцпег РЬуа||йап РгоНгащ|пег Вш!бег С!ег1| Агт!аФ 1лзтуег Ношеша)сег РгоНгапнпег РгоНгаш|пег ЯОК 1ЗОК 66К 60К 44К ЗОК 19ОК 44)г 64К 60К 1ОК 20К 18К 12К 4К ОК ОК 2)г 10К 2-К тимся к примеру на рис, 16.2.
Если Ь = 2, то в таком случае будут разрешены запросы только с кардинальностью с, находящейся в диапазоне 2 < с < 8. Это значит, что следующее логическое выражение использовать нельзя. ЯЕХ = 'М' АМО ОССОРАТ1ОН = 'Ргодгаммег' Теперь рассмотрим приведенную инке последовательность запросов 7-10. 7. И1ТН ( ЯТАТЯ ННЕКЕ БЕХ = 'М' ) АЯ Х СОНЕТ ( Х ) Результат: 4. 8. Н1ТН ( БТАТЯ ННЕКЕ ЯЕХ = 'М' МО МОТ ( ОССОРАТ10Н = 'Ргодгашмег' ) ) АЯ Х СООМТ ( Х ) Результат: 3. На основании запросов 7 и 8 пользователь 0 может сделать вывод, что существует только один мужчина-программист, следовательно, его зовут 'А11' (поскольку пользователь 0 уже знает нз других источников, что сотрудник по имени 'А11' является мужчиной и программистом).
Зарплата этого сотрудника может быть определена следующим образом. 9. И1ТН ( ЯТАТБ ЯНЕКЕ БЕХ = 'М' ) АЯ Х ЯОМ ( Х, БАЪАКУ ) Результат; 328 000. 1О. ИТТН ( ЯТАТЯ ИНЕКЕ БЕХ = 'М' АКО НОТ ( ОССОРАТТОМ = 'Ргодгапмег' ) ) АБ Х БОМ ( Х, БАЕВУ ) Результат: 278 000; 328 000 — 278 000 = 50 000. ° Логическое выражение БЕХ = 'М' АМ0 ОССНРАТ108 = 'Ргодгавмег' называется трекером (охотником) за индивидуальными данными (1по(т(оца( пасКег) для человека по имени 'А11' (16.6), поскольку оно позволяет отыскать индивидуальную информацию о человеке по имени 'А11'. В общем случае, если пользователю известно некоторое логическое выражение ВЕ, идентифицирующее некоторого человека 1, и если логическое выражение ВЕ может быть выражено в виде ВЕ1 АМ0 ВЕ2, логическое выражение ВЕ1 М0 МОТ ВЕ2 является трекером за индивилуальными данными человека по имени 1 (при условии, что в системе разрешено использовать выражения ВЕ1 и ВЕ1 М0 НОТ ВЕ2, т.е.
оба они приводят к результату, кардинальность (с) которого находится в диапазоне Ь < с < Н - Ь). Причина этого заключается в том, что определенное с помощью ВЕ множество идентично разнице между множеством, определенным с помощью ВЕ1, и множеством, определенным с помощью ВЕ1 АН0 ХОТ ВЕ2, что наглядно представлено на рис.
16.3. вес ( ВЕ ) = аег ( ВЕ1 М0 ВЕ2 ) = вет (ВЕ1) - вес (ВЕ1 МО МОТ ВЕ2) б17 Глава 1б. Защита данных Рис. !бай Тренер за индивидуазьными данными ВЕ1 АУО ЕОТ ЕЕ2 В (!6.6! упомянутые здесь идеи обобщены и показано, что практически для любой статистической базы данных всегда может быть определен общий трекер (в отличие от множества индивидуальных трекеров). Общий трекер (Еепега! ггасйег)— это логическое выражение, которое может быть использовано для поиска ответа на любой запрещенный запрос, т.е.
запрос, включающий недопустимое логическое выражение. (В противоположность этому индивидуальный трекер работает только на основе запросов, включающих конкретные запрещенные выражения.) Фактически оказывается, что любое логическое выражение с результирующим набором данных с кардинальностью с в диапазоне 2Ь < с < й - 2Ь является общим трекером (здесь Ь должно быть меньше, чем И/4, что обычно всегда выполняется на практике).
Как только такой трекер будет найден, сразу же можно будет получить ответ на запрос, включающий запрещенное логическое выражение ВЕ, что наглядно показано в следующем примере. (Для определенности рассмотрим случай, в котором кардинальность результирующего множества логического выражения ВЕ меньше Ь. Случай, когда Ь больше й - Ь, обрабатывается аналогично.) Обратите внимание, что по определению Т является общим трекером тогда и только тогда, когда йОТ Т также является общим трекером. Пример.
Предположим снова, что Ь = 2; тогда общим трекером будет любое логическое выражение с кардинальностью результирующего множества с в диапазоне 4 < с < б. Еше раз предположим, что пользователю 0 известно из внешних источников, что сотрудник по имени 'А11' является мужчиной и программистом, т.е. запрещенное логическое выражение ВЕ выглядит так, как показано ниже.
ЯЕХ = 'И' АВВ ОССОРАТ100 = 'Ргоагавпег' Допустим также, что пользователь 0 хочет узнать размер зарплаты сотрудника 'А11'. В этом случае общий трекер придется применить дважды: сначала, чтобы удостовериться, что ВЕ действительно идентифицирует сотрудника по имени 'А11' (этапы 2-4), а затем непосредственно для того, чтобы определить размер зарплаты сотрудника 'А11' (этапы 5 — 7).
Этап 1. Попробуем найти выражение для общего трекера Т. В качестве первого приближения выберем следующее выражение. А001ТБ = 0 618 Часть !'. Дополнительные аспекты Этап 2. С помощью выражений Т и НОТ Т определим общее количество сотрудни- ков, сведения о которых содержатся в базе данных. И1ТН ( ЯТАТЯ ИНЕНЕ АНАПЕ = О ) АЯ Х СОПИТ ( Х ) Резулыпат: 5. И1ТН ( ЯТАТБ ИНЕСЕ ИОТ ( АП01ТЯ = О ) ) АБ Х СОПИТ ( Х ) Результат: 5; 5 ь 5 = 1О. Теперь легко видеть, что выбранное выше выражение Т действительно оказалось общим трекером.
Этап 3. Найдем результат сложения общего количества сотрудников в базе ланных с количеством сотрудников, для которых удовлетворяется неразрешенное выражение ВЕ, для чего используем выражения ВЕ ОН Т и ВЕ ОЕ НОТ Т. ИПН ( БТАТЯ ИНЕНЕ ( БЕХ = 'М' АИО ОССПРАТ1ОН = 'Рго9гаппег' ОН АП01ТЯ = О ) АЯ Х СОПИТ ( Х ) Результат: 6. И1ТН ( ЯТАТЯ ИНЕКЕ ( ЯЕХ = 'М' АНП ОССПРАТ1ОИ = 'РгоОгапюпег' ОН ИОТ ( АП01ТЯ = О ) ) АЯ Х СОПИТ ( Х ) Результат: 5; 6 -ь 5 = 11. Этап 4. Из полученных выше результатов можно сделать заключение, что количество сотрудников, которые удовлетворяют логическому выражению ВЕ, равно единице (результат этапа 3 минус результат этапа 2), т.е.
логическое выражение ВЕ единственным образом идентифицирует сотрудника по имени 'А1Т '. Теперь на этапах 5 и 6 повторим запросы, использованные на этапах 2 и 3, но вместо функции СОПИТ укажем функцию БПМ. Этап 5. С помощью выражений Т и НОТ Т найдем размер зарплаты всех сотрудников. И1ТН ( ЯТАТБ ИНЕНЕ АПППБ = О ) АЯ Х БПМ ( Х, БАБАХ ) Результат: 438 000. И1ТН ( БТАТЯ ИНЕНЕ КОТ ( АП01ТЯ = О ) ) АЯ Х ЯПМ ( Х, ЯАТАНТ ) Результат: 290 000; 438 000 + 290 000 = 728 000.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
