СТАТИСТИЧНІ БАЗИ ДАНИХ

Статистичної (У наведеному тут контексті) називається база даних, в якій допускаються запити з агрегування даних (підсумовуванням, обчисленням середнього значення і тд), але не допускаються запити по відношенню до елементарних даними Наприклад, в статистичній базі даних дозволяється видача запиту Яка середня зарплата службовців”, Тоді як видача запиту Яка зарплата службовця Мері” заборонена

Проблема статистичних баз даних полягає в тому, що іноді за допомогою логічних висновків на основі виконання дозволених запитів можна вивести відповідь, який прямо може бути отриманий тільки з допомогою забороненого запиту Як вказується в [178], Узагальнені значення містять сліди вихідної інформації, і вона може бути відновлена ​​зловмисником після відповідної обробки достатнього кількості цих узагальнених значень Такий процес називається дедуктивним формуванням конфіденційної інформації за допомогою логічного висновку . Слід відзначити те, що ця проблема, на жаль, стає все більш і більш важливою в міру того, як використаннясховищ даних(Див главу 22) набуває все більшого поширення

Розглянемо більш докладний приклад Припустимо, що в базі даних міститься тільки одна змінна відносини, STATS, представлена ​​на рис 172 Припустимо

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

(Тобто числового і строкового) Далі припустимо, що деякому користувачеві і в цій базі даних дозволено виконувати тільки статистичні запити, але він поставив

собі метою дізнатися розмір зарплати працівника на імя Alf Нарешті припустимо, що з інших джерел користувач і дізнався, що Alf – програміст чоловічої статі Проаналізуємо представлені нижче запроси3

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

1&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp WITH ( STATS WHERE SEX = M AND

OCCUPATION  =   Programmer    )

AS  X  : COUNT   (  X  )

Результат: 1

2&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp WITH ( STATS WHERE SEX = M AND OCCUPATION = Programmer ) AS X

: SUM ( X, SALARY )

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

Рис 172 Мінлива відносини STATS (приклади значень)

Очевидно, що захист бази даних була порушена, хоча користувач і прйменія тільки дозволені йому статистичні запити Як показано в прикладі, якщо користувач зуміє знайти таке логічне вираження, яке дозволить йому ідентифікувати деяку особистість, то інформація про даної особистості виявиться незахищеною З цієї причини система повинна відкидати будь-які запити, для яких кардинальність обобщаемого безлічі виявиться менше деякого встановленого мінімального значення Ь Це також означає, що система повинна відкидати запити, кардинальність обобщаемого безлічі яких перевершує значення п-Ь (де п – кардинальність початкової змінної відносини) Справа в тому, що можна навести ще один приклад порушення захисту цієї бази даних, що здійснюється за допомогою введення показаної нижче послідовності запитів 3-6

3&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp COUNT    (   STATS   )

Результат: 12

4&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp WITH   (  STATS  WHERE  NOT   (  SEX  =   M   AND OCCUPATION  =   Programmer    )     )

AS  X   : COUNT   (  X  )

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

5&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp SUM   (   STATS,   SALARY   )

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

6&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp 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&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp WITH ( STATS WHERE SEX = M ) AS X :

COUNT ( X )

Результат: 4

8&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp WITH ( STATS WHERE SEX = M AND NOT

( OCCUPATION = Programmer ) ) AS X :

COUNT     (   X   )

Результат: 3

На підставі запитів 7 і 8 користувач і може зробити висновок, що існує тільки один чоловік-програміст, отже, це і є Alf (оскільки користувач і вже знає з інших джерел, що співробітник на імя Alf є чоловіком і програмістом) Зарплата цього співробітника може бути визначена таким чином

9&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp WITH ( STATS WHERE SEX = M ) AS X :

SUM ( X, SALARY )

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

10&nbsp&nbsp&nbsp&nbsp 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 [178], оскільки воно дозволяє відшукати інформацію про окрему людину по імені 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}

Рис 173 Індивідуальне засіб стеження ВЕ1 AND NOT Ве2

В [178] згадані тут ідеї узагальнені і показано, що практично для будь ста статистичної бази даних завжди можуть бути визначені загальні засоби стеження (у від личие від безлічі засобів стеження за особистими даними) Загальне засіб стеження (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

Принцип дії показаного нижче загального засоби стеження схематично представлений на рис 174

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

Рис 174 Принцип функціонування спільного засоби стеження Т

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

Узагальнимо отримані результати Практично завжди існує вислів, що є загальним засобом стеження, знайти яке так само легко, як і використовувати Дійсно, вираз для загального засоби стеження досить швидко можна просто вгадати шляхом перебору декількох варіантів [178] Навіть у тих випадках, коли не існує вираження для загального засоби стеження, можуть бути знайдені, як показано в [178], специфічні засоби стеження, призначені для конкретних запитів Важко уникнути загального висновку, що безпека статистичних баз даних залишається нагальною проблемою

Що в такому випадку можна зробити Деякі варіанти вирішення цієї проблеми вже пропонувалися в літературі, але все ж поки не можна сказати точно, чи є який-небудь з них задовільним у всіх відносинах Наприклад, в одному з варіантів пропонується організувати обмін даними (Data swapping), тобто обмін значеннями атрибутів між кортежами, здійснюваний таким чином, щоб підтримувалася лише статистична точність При цьому навіть якщо зловмисникові вдасться ідентифікувати окреме значення (наприклад, деяке значення зарплати), то у нього не буде

способу дізнатися, якому саме кортежу (у нашому прикладі – співробітнику) воно належить Складність цього підходу полягає в необхідності відшукати безліч тих записів, між якими можна буде організувати обмін значеннями відповідним чином Такі труднощі мають місце і при використанні більшості інших запропонованих методів В даний момент, мабуть, доведеться погодитися з висновками, наведеними в [178], про те, що методи порушення захисту даних прості і не повязані з великими витратами Тому вимога забезпечення повної секретності конфіденційної інформації несумісне з вимогою можливості обчислення точних статистичних показників для довільних підмножин даних в базі Принаймні одна з цих вимог повинно бути знято перш, ніж можна буде довіряти гарантіям забезпечення секретності .

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

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*