автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Обработка баз данных с персонифицированной информацией для задач обезличивания и поиска закономерностей

На правах рукописи

КУЧИН ИВАН ЮРЬЕВИЧ

ОБРАБОТКА БАЗ ДАННЫХ С ПЕРСОНИФИЦИРОВАННОЙ ИНФОРМАЦИЕЙ ДЛЯ ЗАДАЧ ОБЕЗЛИЧИВАНИЯ И ПОИСКА ЗАКОНОМЕРНОСТЕЙ

Специальности:

05.13.01 - Системный анализ, управление и обработка информации (промышленность, информатика)

05.13.19 - Методы и системы защиты информации, информационная безопасность

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

1 5 МА? Ш

Астрахань - 2012

005014666

005014666

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Астраханский государственный технический университет».

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор технических наук, профессор Попов Георгий Александрович.

заведующий кафедрой «Системы автоматизированного проектирования и поискового конструирования» ФГБОУ ВПО «Волгоградский государственный технический университет», заслуженный деятель науки РФ, доктор технических наук, профессор Камаев Валерий Анатольевич,

профессор кафедры «Защита информации» ФГБОУ ВПО «Северо-Кавказский государственный технический университет», доктор технических наук, профессор Калмыков Игорь Анатольевич.

ФГБОУ ВПО «Саратовский

государственный технический университет имени Гагарина Ю.А.».

Защита состоится «29» марта 2012 г. в 11 часов 00 минут на заседании диссертационного совета Д 307.001.06 при Астраханском государственном техническом университете по адресу: 414025, г.Астрахань, ул. Татищева, 16, главный корпус, ауд. 313.

Отзывы на автореферат в двух экземплярах, заверенные гербовой печатью организации, просим направлять по адресу: 414025, г.Астрахань, ул. Татищева, 16, АГТУ, ученому секретарю диссертационного совета Д 307.001.06.

С диссертацией можно ознакомиться в научной библиотеке Астраханского государственного технического университета.

Автореферат разослан « 22 » февраля 2012 г.

Ученый секретарь /^р!

диссертационного совета ^[¿^ А.А. Ханова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Особый интерес в качестве объекта поиска новых знаний представляет персонифицированная информация или персональные данные (ПДн), т.е. цифровая информация, генерируемая или так или иначе связанная с конкретной личностью. Значительная потребность в использовании этой информации и ее анализе, в том числе методами Data Mining, в настоящее время испьггывается в двух сферах: в бизнес-аналитике и сфере государственных услуг (в связи с активным переводом услуг населения в электронный формат: единая карта гражданина РФ, электронные очереди, электронное правительство и т.п.).

В рамках указанной обработки персонифицированной информации все острее проявляются противоречия требований интеллектуального анализа данных и сохранения приватности личности при использовании ее данных. Так 34,7% организаций, обрабатывающих персональные данные, в качестве основного препятствия к использованию их в качестве объекта исследования называют неясность положений Федерального закона №152 «О персональных данных». В частности, Законодательно установлено, но не регламентировано требование проведения предварительной процедуры обезличивания персональных данных перед их исследованием, что значительно препятствует полноценному и безопасному их использованию в качестве объекта поиска новых знаний.

Направлением Data Mining занимались и продолжают заниматься многие российские и зарубежные ученые: Г. Пиатецкий-Шапиро, A.B. Дюк, И.А. Чубуков, Н. Edelstein и др. Использование методов Data Mining применительно к анализу персонифицированной информации без угрозы приватности личности рассмотрены в работах: P.Samarati, G.Aggarwal, RJ Bayardo и др. Наконец, вопросами обезличивания персональных данных в нашей стране посвящены работы: С.Д. Рябко, АЛукацкого, Е.А. Саксонова, Р.В.Шередина, Е.Царева и др.

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

Объект исследования - базы данных с персонифицированной информацией жителей РФ, находящиеся в свободном доступе в сети Интернет.

Предмет исследования. Методы, модели и алгоритмы обработки больших наборов персонифицированных данных.

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

1. Разработать способы оценки свойств персонифицированной информации на основе построения их классификационной структуры.

2. Модифицировать метод SSA-Гусеница для решения задач Data Mining применительно к персональным данным.

3. Построить модель и алгоритм обезличивания данных, позволяющие при необходимости восстанавливать исходные данные.

4. Разработать алгоритм защитного преобразования, зависящий от параметров конкретной операционной среды обработки.

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

Достоверность и обоснованность подтверждена результатами компьютерных экспериментов и внедрением работы в ООО «Новая Клиника» (г. Астрахань).

Научная новизна диссертационного исследования:

1. Сформирована классификационная структура свойств персональных данных вместе со способами оценки этих свойств, которые позволяют повысить степень эффективности и безопасности обработки данных в процессе поиска новых знаний.

2. Модифицирован метод SSA-Гусеница применительно к анализу данных, не являющихся временными рядами, а также разработана процедура эффективного выбора длины окна, позволяющая результативнее определять характеристики регулярных составляющих в базах данных.

3. Предложена новая модель обезличивания, усовершенствующая модель «¿-анонимности» и обеспечивающая более высокий уровень функциональности, по сравнению с последней, за счет реализации возможности восстановления обезличенной информации.

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

Практическая значимость.

1. Полученные в работе количественные оценки свойств баз данных с персонифицированной информацией могут быть использованы для прогнозирования характеристик результатов идентификации личности в произвольных базах персональных данных.

2. Модифицированный метод SSA-Гусеница позволяет применять различные варианты этого метода для анализа данных, не являющихся временными рядами.

3. Разработанный в работе алгоритм обезличивания данных может быть использован для безопасного хранения и обработки персональных данных в коммерческих целях.

Апробация работы. Основные положения и отдельные результаты диссертации докладывались и обсуждались на Международной научно-технической конференции «Современные информационные технологии - 2011» (Пенза, 2011), Международной конференции по информационной безопасности «Info Security Russia» (Москва, 2010), I международной научно-практической конференции «Эволюция системы научных коммуникаций Ассоциации университетов Прикаспийских государств» (Астрахань, 2008), Международной отраслевой научной конференции профессорско-преподавательского состава Астраханского государственного технического университета (Астрахань, 2010).

Публикации. Основные результаты диссертационного исследования опубликованы в 6 печатных работах: 3 статьях в журналах из списка, рекомендованного ВАК РФ, 3 материалах и трудах конференций. Все работы опубликованы без соавторов.

Структура и объем работы. Работа состоит из введения, 3 глав, заключения, списка литературы из 106 наименований и 5 приложений. Основная часть работы изложена на 117 страницах машинописного текста, содержит 17 таблиц и 45 рисунков.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе был проведен анализ проблемы идентификации личности по персональным данным, позволивший сформировать классификационную структуру свойств объекта исследования, определяющих результат идентификации, а также предложен способ их количественной оценки. Совокупность указанных выявленных свойств, вместе с оп^едаляющими их фаугорами приведена на_р_ис.1.

Идентифицирующие свойства БД

• информативность атрибутов

* распределение значений

* число значений

• число атрибутов

• корреляция между атрибутами

Доступность атрибутов БД

• «реальное положение дел на рынке ииф. услуг»

• «природа» информации

• желание субъекта

Рис. 1. Классификационная структура свойств персональных данных, определяющих результат идентификации

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

обработки, в частности, введены такие показатели данных как «доступность», «идентифицируемость», «связность», «информативность» и др.

Необходимость числового выражения результатов идентификации потребовала определения количественных оценок выявленных свойств. Свойства «информативности» и «доступности» атрибутов были определены в ходе анализа 9 баз данных (БД) жителей разных городов РФ, общим объемом более 16 млн. записей, найденных в входе поискового эксперимента в сети Интернет. В работе предлагается следующее соотношение для оценки свойства доступности данных D для конкретного атрибута А:

D(A,)=PAi*FAi + 0,l*EAh где Р,и - вероятность нахождения атрибута А; в базе данных; FAi - степень заполнения атрибута Af (коэффициенты РА„ F м были рассчитаны по данным более 16 млн. записей); £А - доступность атрибута согласно опросу Всероссийского центра изучения общественного мнения (ВЦИОМ), проведенному 16 февраля 2011 года. Коэффициент 0,1 определяет вес результата опроса в общем значении показателя доступности. Расчет был произведен для основных атрибутов, встречающихся в базах с персональными данными (рис. 2).

j~. -..J Заполненность, F~~] ИН Вероятность. Р И Опрос ВЦИОМ, Е

D («фамилия») = 1 D («имя») = 0,99 D («отчество») = 0,98 D («пол») = 0,43 D («дата рож.») = 0,8 D («адрес per.») = 0,85 D («паспорт Мг») = 0,57 D («ИНН») = 0,03 О («фото») = 0,21

Рис. 2. Значения параметров, определяющих доступность атрибутов

Свойство «информативности» атрибута определяет способность дифференцировать выборку по его значениям. Для подсчета «информативности» была

предложена формула, аналогичная формуле Шеннона:

»

где А - атрибут базы данных; /(А) - информативность атрибута А, к - число различных значений, которые принимает атрибут А в рассматриваемой базе данных; p¡ - вероятность того, что атрибут А примет 1-е значение. Практический смысл информативности заключается в знании среднего размера группы КСр, на которые разбивается все множество записей при идентификации по рассматриваемому атрибуту (чем выше информативность признака, тем ближе КСР к 1). Для оценки «качества» распределения атрибутов с точки зрения возможностей идентифика-

ции кроме информативности была определена их максимальная информативность /,„ах(А), которая была рассчитана по «оптимизированным атрибутам» с однородным вероятностным распределением:

/тш(А)= - кщ2{\1Ы') если N'^1; ' 1<Ы\Ш)если Ы'>К _

где N- число записей в базе данных; ЛГ- максимальное число значений, которое принимает атрибут.

Для оценки максимальной информативности атрибута в базе данных произвольного размера N без непосредственного проведения подсчета необходимо знать распределение этого атрибута, в котором каждому значению /V, (числу записей в базе данных) соответствует число его уникальных (неповторяющихся) значений - У,. Это распределение, прежде всего, зависит от природы атрибута и в общем случае является случайным.

Диапазон количества уникальных (различных) значений, принимаемых атрибутом «фамилия», был построен в результате подсчета ^ в 10 случайно сформированных (из значений исходных БД) базах данных размером N¡ на каждой из 42 контрольных точек для 5 наиболее репрезентативных баз данных (БД жителей Астрахани, Тольятти, Тюмени, а также Московской и Астраханской областей) (всего 2100 значений). В получившемся при этом диапазоне возможных значений У, (рис. 3) была построена кривая, соответствующая средним значениям диапазона.

60000 5000040000 30000 ' 20000-

----среднее значение

аппроксимированное значение ( 1 диапазон фамилий

О

50000 1000СЮ 15DC00 300000 25<Ш> 300000 350000 Размер базы данных

ИШЮ 150000 200000 260000 300000 ЗЕОООО размер базы данных

Рис. 3. Диапазон распределения уникальных значений атрибута «фамилия», его эталонное и аппроксимированное значения

Затем с использованием пакета для анализа Origin Pro v.8.5.1 это осреднен-ное распределение было аппроксимировано встроенной экспоненциальной функцией (график 1 на рис. 3).

Анализ ошибок аппроксимации и относительной ширины диапазона показал стабильность найденной функциональной зависимости после того, как размер базы данных начинает превышать 5000 записей. Аналогичные расчеты были произведены для наиболее распространенных атрибутов баз персональных данных («имя», «отчество», «дата рождения» и др.). На графике 2 рис. 3 изображено среднее распределение уникальных значений атрибутов «фамилия», «имя» и «отчество».

В работе был сформулирован ряд гипотез об особенностях распределения значений атрибутов баз ПДн, которые нашли подтверждение в результате соот-

ветствующей проверки в базах данных, собранных в ходе поискового эксперимента.

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

В результате поискового эксперимента был получен перечень баз персональных данных объемом более 16 млн. записей. Выявлены свойства персонифицированной информации, определяющие результаты идентификации личности и представляющие интерес в процессе обработки данных, которые были количественно оценены по найденным БД. Получены функциональные зависимости распределения значений наиболее часто встречающихся атрибутов баз ПДн, которые могут быть использованы для априорного оценивания результатов идентификации в произвольной базе с персональными данными.

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

Основной проблемой поиска знаний в технологии Data Mining является практически полное отсутствие предварительной информации о характере закономерности, которую пытаются выявить в базе данных. Доступный поиск показал, что единственным подходящим в таких условиях является метод анализа временных рядов SSA-Гусеница, который для одномерного ряда заключается в последовательном выполнении следующих процедур: формирование траекторией матрицы, ее сингулярное разложение, группировка членов разложения, последующее восстановление компонентов разложения, а также визуальный анализ и интерпретация результатов.

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

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

1. Генерирование гипотезы о возможной закономерности в БД.

2. Выбор из БД записей, удовлетворяющих гипотезе и их упорядочивание.

3. Перевод выбранных данных в числовой формат, и формирование последовательности числовых данных.

Существуют эмпирические методы нахождения длины окна для построения SSA-Гусеницы, в частности, есть рекомендация использовать длину окна, равную половине длины ряда, либо кратную величине периода при поиске гармонической составляющей. В работе предлагается процедура выбора оптимальной длины окна

I на основе анализа степени средней коррелированное™ «соседних» окон ряда следующим формулам:

рЩ= тах {/?(/)}>

0</</-иа,

где р{1) =

< 1=1

' -' 1=1

у" -начало просматриваемого окна; I - текущая длина всех окон, о(/',0 " соответствующее среднее квадратическое отклонение.

Для проверки возможности применения метода 85А-Гусеница для поиска знаний в базах с персонифицированной информацией, были выбраны 2 подмножества мощностью 2000 записей из БД г. Астрахани. Первое подмножество выбрано из БД с естественным порядком следования записей, второе - из БД, предварительно отсортированной по атрибуту «название улицы». При этом из исследуемой базы данных этот атрибут был исключен. Соответствующее распределение атрибута «номер квартиры» для двух БД представлено на рис. 4.

БД отсортирована по атрибуту «улица»

1 .БД не отсортирована . _ • . / - . /" ' *. *• ,*

Номер записи в БД

Номер записи в БД

Рис. 4. Распределение атрибута «№ квартиры» в двух БД

Визуально невозможно определить, была ли отсортирована исходная база данных по какому-либо атрибуту либо в этой базе данных естественный порядок следования записей, например, по мере их добавления в нее. Для определения факта скрытой сортировки и нахождения гармонической составляющей (атрибута сортировки) был применен описанный метод ЗБА-Гусеница (сформирована транспортная матрица, а затем с помощью программы Са1егр111аг58А построены двумерные диаграммы пар собственных векторов). Длина окна I первоначально была выбрана равной половине длины ряда (№2) для решения принципиального вопроса - есть ли в этом временном ряду выраженные гармонические колебания. Полученные таким образом двумерные диаграммы приведены на рис. 5.

Рис. 5. Двумерные диаграммы пар собственных лекторов для соответствующих БД

Диаграммы на рис. 5. позволяют сделать однозначный вывод о том, что в первом распределении есть определенные закономерности (двумерная диаграмма собственных векторов, отмеченная стрелкой). Для выделения периодической составляющей необходимо подобрать длину окна, кратную периоду этой компоненты, однако, заранее этот период неизвестен, т.к. атрибут сортировки от нас скрыт. При помощи разработанной процедуры нахождения длины окна, опирающейся на средний уровень корреляционной зависимости между соседними окнами, была найдена длина окна ¿=303, при которой гармоническая составляющая хорошо просматривается (образуется наиболее правильная фигура; рис. 5, диаграмма 3).

Знание порядка следования записей в базе данных может быть весьма ценно, например, для восстановления идентичности обезличенной информации. Задачу определения свойства упорядоченности атрибута базы данных можно рассматривать как задачу поиска гармонической составляющей во временном ряду с периодом Т равным NIK, где N - длина ряда, а К - длина сезонной составляющей. В случае с базой данных, N - это число записей, а К - количество различных значений атрибута, по которому была произведена сортировка.

Предлагаемая процедура позволяет значительно снизить время поиска длины окна. В частности, в рассмотренном выше примере время поиска было снижено в 6 раз по сравнению с направленным перебором (бинарным поиском).

В результате доработки существующего метода анализа временных рядов SSA-Гусеница, стало возможным его применение на БД, не являющихся временными рядами. Предложенная процедура нахождения длины окна на основе анализа корреляционной зависимости позволяет найти период гармонической составляющей, что может быть использовано для поиска знаний методами Data Mining.

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

В ходе анализа всех известных на данный момент методов обезличивания были определены два принципиальных способа реализации процедуры обезличи-

вания и рассмотрены варианты их использования для решения практических задач обеспечения приватности личности:

• снижение идентифицирующей способности данных;

• использование недоступных идентификаторов.

Для решения проблемы подготовки базы с персональными данными к исследованиям методами Data Mining за основу была взята модель «¿-анонимности» (к-anonymity), широко известная в зарубежных исследованиях. Ее основная идея заключается в том, что в обезличенной базе данных любая строка должна быть неотличима по идентификаторам, потенциально доступным злоумышленнику, от, как минимум, к- 1 других строк, где к - натуральное число, определяющее степень защиты обезличенной базы данных. Используются две возможные процедуры преобразования информации для достижения ¿-анонимности - удаление и обобщение (с введением доменов), которые могут выполняться на разных уровнях (уровень ячейки БД, уровень строки, столбца) и в разных сочетаниях (отдельно друг от друга либо совместно).

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

- атрибуты

S- субъекты

А, Аг А.

А'„ Хп

а, Хг, Х:„

Sm хм Хт2 | . \ Хм

зы приватности личности и с соблюдением требований законодательства.

Формализация модели представлена далее: рассматривается база данных в виде двумерной таблицы (рис. 6), содержащая персональные данные множества людей 5, База данных В представля-порядковый номер запи-

Хп.А'п,..., Хи - кортеж ПДн, соответствующий субъекту

Рис. 6. Двумерная таблица с ПДн

ет собой множество строк В = {1Аи 2Аь ... пА„}, где пси, А - атрибут БД. Каждая строка таблицы и содержит идентифицирующие и общие данные, связанные с конкретным субъектом

Ц= Р* =

где р, - полные идентифицирующие данные субъекта 5,; с, - общие данные, связанные с субъектом а1 - идентифицирующая информация, доступная потенциальному злоумышленнику (доступный идентификатор); А, - идентифицирующая информация, не доступная злоумышленнику (недоступный идентификатор); «' -номер строки.

Имеется однозначное отображение (биекция) между множеством Б и множеством В (Б -* В). По любой строке I, однозначно восстанавливается один и

только один субъект

Функция обезличивания - это отображение (биективное) множества В в

множество Ц Р. В—> Д такое, что:

1) ЧЦ ^(/£) = Р(1аЪс) = Ю = ¡а'Ъ'с, причем а, отображается в а, ' так, что

соответствующий символ строки а,' либо совпадает с символом а,, либо

равен символу '**. Аналогично bt отображается в Ь,', где а' - обезличенная а, Ь' — обезличеннаяЪ.

2) V/, _/:!..л А/> к, где Д = {;':F(iaj) = F(ia,)} - множество «двойников» для 1-го субъекта (строки), а к- некоторое натуральное число - «степень обезличивания», F определяется следующим образом: если FQabc) = ia'b'c , то F{ia) = ia.

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

В работе был предложен алгоритм (рис. 7), реализующий оригинальную модель обезличивания.

Рис. 7. Блок-схема алгоритма обезличивания с восстановлением

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

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

В качестве доступного иденти-15М !000 "^фикатора был выбран кортеж атрибу-Номер записи в БД ^ {<<фамилия>>; <<имя>>1 «отчество»,

Рис. 8. Изменение диапазона уникальных г о _„пи „„

, , «дата рождения», «пол»}, о роли не-

значений три обезличивании ччча г 44 ' ' г „„„„„„

доступного - «серия и номер паспорта». График 1 на рис. 8 изображает распределение уникальных значений рассматриваемого кортежа атрибутов в исходной базе данных (прямая линия, все записи уникальны). После обезличивания по сформированному шаблону распределение приобретает вид, представленный на графике 2 (рис. 8). Для гарантированного восстановления обезличенных данных проводится процедура повышения информативности отдельных записей (график 3, рис. 8). Результаты ¿-анонимности при обезличивании приведены на рис. 9.

120 - ?

Шк

о 20 40 60 81

©

Рис. 9. Результаты обезличивания предлагаемым алгоритмом

График 1 на рис. 9 демонстрирует результаты идентификации обезличенной БД по общедоступному идентификатору: все записи обезличены (4 <к <60). График 2 - результаты идентификации по полному идентифицирующему набору: все записи БД восстанавливаются (к= 1). Таким образом, обезличенную БД можно хранить неограниченное время без риска нарушения

приватности личности.

Основными параметрами предлагаемого алгоритма являются:

• выбор числа к, разделение идентификаторов по степени доступности;

• шаблон обезличивания для достижения ^-анонимности.

Алфавит: а б в г д е ж

1,1 .а 2,2,6

Параметр обезличивания к выбирается исходя из требований безопасности, предъявляемых к конкретным данным. Определение доступного идентификатора предлагается производить по результатам оценки доступности данных, проведенным в первой главе.

Формирование шаблона обезличивания происходит на основе предложенных в работе способов числового оценивания информативности атрибутов БД, которые необходимы для анализа методами Data Mining, в частности, путем прогнозирования среднего размера группы Кср, получаемого при идентификации обезличенной базы данных по значениям этих атрибутов.

Предложенная модель и алгоритм обезличивания не связаны с конкретной средой обработки информации, однако могут возникнуть задачи, когда для повышения стойкости обезличивания целесообразно также связать процесс обработки с конкретными условиями ее функционирования

Для этого в работе был предложен алгоритм защитного преобразования, опирающийся на большое количество и сложный порядок взаимодействия функций вызовов ядра ОС с открытым кодом. В качестве примера было взято ядро ОС Linux (v2.6.23.11). Проведенный расчет выявил в нем 5211 функций, которые вызываются 481563 раза.

Для реализации предлагаемого алгоритма необходимо провести ряд подготовительных действий:

1. Представление ядра ОС по исходному коду в виде иерархического взвешенного графа. Применительно к ОС Linux подобный граф был построен при помощи утилиты cflow. Графическое представление графа ядра было получено при помощи пакета утилит по автоматической визуализации Graph Viz.

2. Сопоставление каждой функции двух натуральных чисел: относительного и абсолютного номера по проце-

Рис. 10. Пример подготовки графа дуре> опираЮщейся на лексикографическую упорядоченность наименования функций. Назначение каждой вершине символа входного алфавита последовательным перебором вершин и циклическим перечислением символов при их назначении. Пример графа с проведенными подготовительными действиями для упрощенного алфавита приведен на рис. 10.

После завершения описанных подготовительных действий выполняется непосредственно процедура защитного преобразования, приведенная в виде алгоритма на рис. 11.

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

13,1 ,е 14,2,ж 15,3,а 16,4,6 17,5,в 18,6,г 19,7л

ÖOOOÖOOD

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

1. По ключевым элементам обезличиваемой записи формируется абсолютны номер начальной вершины Уо графа__

2. На основе алгоритма поиска в глубину, начиная с текущей вершины.. осуществляется поиск первой из вершин Ук, удовлетворяющей условию sk := s((c(ii-i)+c(io)mod m)))=ik, где st- символ, приписанной данной вершине, s(.) и с(.) - функции преобразования из цифрового формата в символьный и наоборот; т - размер алфавита БД и наоборот; т -размер алфавита БД; bk - Текущий числовой символ записи

3. При выполнении условий в качестве текущего символа обезличенной записи записывается

ЯЛЛ= Ш+Rk,

где Rk - Относительный номер вершины Ук ^ ^

4. Процедуры 2 и 3 повторяются пока не будут просмотрены все символы числового формата записи_____________

Рис. 11. Предлагаемый алгоритм защитного преобразования данных

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

Было произведено внедрение результатов работы в ООО «Новая Клиника» (г. Астрахань), в котором был изменен технологический процесс обработки персональных данных пациентов с применением технологии обезличивания. Внедрение позволило выполнить требования Федерального закона №152 «О персональных данных», а также реализовать право 2% пациентов, желающих получать медицинские услуги анонимно.

В заключении изложены научные результаты, полученные в диссертационной работе.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ

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

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

ности по степени их доступности и адаптировать механизмы защиты данных с учетом результатов классификации.

3. Модифицирован метод SSA-Гусеница, позволяющий использовать аппарат исследования временных рядов для анализа БД произвольного содержания.

4. Предложена новая процедура поиска длины окна для метода SSA-Гусеница. Продемонстрирована эффективность разработанной процедуры в задачах выявления скрытых периодических закономерностей, в частности, было отмечено уменьшение времени поиска длины окна в 6 раз, по сравнению с направленным перебором для базы данных объемом 2000 записей.

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи в журналах, периодических изданиях, включенных в список ВАК РФ

1. Кучин, И.Ю. Защита конфиденциальности персональных данных с помощью обезличивания / И.Ю. Кучин // Вестник АГТУ. Серия «Управление, вычислительная техника и информатика». - 2010. - №2. - С. 158-162.

2. Кучин, И.Ю. Новации в проблематике обезличения персональных данных /И.Ю. Кучин // Информационная безопасность регионов. - 2011. - №2(9). -С. 13-17.

3. Кучин, И.Ю. Анализ и классификация проблем обработки персонифицированной информации в медицинских учреждениях / И.Ю. Кучин // Астраханский медицинский журнал. - 2011. - Т.6. -№ 4. - С. 119-123.

Статьи в сборниках трудов международных и всероссийских конференций

4. Кучин, И.Ю. Некоторые вопросы по защите персональных данных / И.Ю. Кучин // Сб. статей международной научно-технической конференции «СГГ conference». - Пенза: Пензенская гос. тех. академия, 2010. - Вып.12. - С. 126-130.

5. Кучин, И.Ю. Анализ программных средств информационной среды с помощью методов теории графов / И.Ю. Кучин // Сб. трудов I международной научно-практической конференции «Эволюция системы научных коммуникаций Ассоциации университетов Прикаспийских государств». - Астрахань: ООО «Типография «Нова», 2008. - С. 178 - 180.

6. Кучин, И.Ю. Обзор существующих методов анализа программного кода / И.Ю. Кучин // Актуальные проблемы гуманитарных и естественных наук. Москва. - 2012. - №02 (37). - 2012. - С.94-98.

Подписано в печать 28.02.2012 г. Тираж 100 экз. Заказ № 155 Типография ФГБОУ ВПО «АГТУ», тел. 61-45-23 г. Астрахань, Татищева, 16ж.

61 12-5/1989

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Астраханский государственный технический университет»

ОБРАБОТКА БАЗ ДАННЫХ С ПЕРСОНИФИЦИРОВАННОЙ ИНФОРМАЦИЕЙ ДЛЯ ЗАДАЧ ОБЕЗЛИЧИВАНИЯ И ПОИСКА

ЗАКОНОМЕРНОСТЕЙ

Специальности:

05.13.01 - Системный анализ, управление и обработка информации

(промышленность, информатика) 05.13.19 - Методы и системы защиты информации, информационная

безопасность

На правах рукописи

Кучин Иван Юрьевич

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: д.т.н., проф. Г.А. Попов

Астрахань - 2012

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.........................................................................................................................................4

ГЛАВА 1. АНАЛИЗ ПРОБЛЕМЫ ИДЕНТИФИКАЦИИ ЛИЧНОСТИ ПО ПЕРСОНАЛЬНЫМ ДАННЫМ............................................................................................................................................8

1.1. Влияние свойств данных на методы их обработки...........................................................10

1.2. Описание категории «персональные данные»...................................................................И

1.3. Проблема идентификации по персональным данным......................................................14

1.3.1. Анализ проблемы идентификации личности по персональным данным................14

1.3.2. Идентификация личности по персональным данным...............................................18

1.3.3. Фактор связности данных............................................................................................20

1.4. Построение модели оценки характеристики доступности персональных данных........22

1.4.1. Реальное положение дел с доступностью персональных данных на рынке информационных услуг..........................................................................................................23

1.4.2. Влияние природы данных на их доступность............................................................28

1.4.3. Желание субъекта добровольно раскрывать информацию о себе...........................28

1.4.4. Результаты оценки доступности данных....................................................................30

1.4.5. Проведение поискового эксперимента по оценке доступности персональных данных......................................................................................................................................33

1.5. Формирование общей схемы идентификации данных.....................................................35

1.5.1. Результаты оценки доступности данных....................................................................35

1.5.2. Анализ факторов, влияющих на информативность атрибутов................................36

1.5.3. Влияние числа и распределение значений в атрибуте на его информативность ...37

1.5.4. Влияние числа атрибутов и зависимости между ними на информативность.........45

1.6. Обобщение проблемы идентификации личности по персональным данным................46

1.7. Выводы по первой главе......................................................................................................49

ГЛАВА 2. ПОИСК ЗАКОНОМЕРНОСТЕЙ В БАЗАХ С ПЕРСОНИФИЦИРОВАННОЙ ИНФОРМАЦИЕЙ............................................................................................................................50

2.1. Поиск знаний в больших базах данных..............................................................................50

2.2. Предлагаемые усовершенствования метода SSA-Гусеница............................................52

2.2.1. Этап разложение данных в методе SSA.....................................................................56

2.2.2. Этап восстановления ряда в модели SSA...................................................................58

2.2.3. Диагональное усреднение............................................................................................60

2.2.4. Параметры и предлагаемые методы............................................................................61

2.3. Возможная реализация метода SSA-Гусеница..................................................................64

2.4. Нахождение скрытых закономерностей в базах с персональными данными.................66

2.5. Использования персонифицированной информации в качестве объекта поиска знаний методами Data Mining......................................................................................................................70

2.6. Выводы по второй главе......................................................................................................72

ГЛАВА 3. ОБЕЗЛИЧИВАНИЕ ПЕРСОНАЛЬНЫХ ДАННЫХ..................................................73

3.1. Актуальность и классификация подходов обезличивания...............................................73

3.2. Атака на основе связей («join attack»)................................................................................74

3 3. Обезличивание методом сокращения идентифицирующей способности базы данных

............................................................................................................................................................77

3.3.1. Модель «А>анонимности».............................................................................................77

3.3.2. ^-минимальное обезличивание....................................................................................81

3.3.3. Оценка сложности модели ^-минимального обезличивания....................................81

Обобщенные данные предложенных алгоритмов для решения проблемы к-минимального обезличивания приведены в таблице 3.3....................................................83

3.3.4. Выводы по методу обезличивания путем сокращения идентифицирующей способности информации.....................................................................................................84

3.4. Обезличивание путем использования недоступных идентификаторов..........................85

3.4.1. Описание метода обезличивания................................................................................85

3.4.2. Варианты обеспечения безопасности «базы-справочника».....................................91

3.5. Достоинства и недостатки существующих методов обезличивания...............................92

3.6. Обезличивания с использованием неполных идентификаторов с возможностью восстановления.................................................................................................................................94

3.6.1. Формализация предлагаемого метода обезличивания..............................................94

3.6.2. Алгоритм «обезличивания с восстановлением»........................................................95

3.6.3. Тестирование предложенного метода обезличивания на базе реальной базе данных. Обсуждение результатов.........................................................................................96

3.7. Обезличивания путем привязки к графу операционной системы...................................99

3.8. Выводы по третьей главе...................................................................................................

ЗАКЛЮЧЕНИЕ..............................................................................................................................Ю7

СПИСОК ЛИТЕРАТУРЫ..............................................................................................................Ю8

ПРИЛОЖЕНИЯ.............................................................................................................................118

ВВЕДЕНИЕ

Активное внедрение информационных технологий для повышения эффективности управления привело к формированию больших объемов собранных данных. Количественный рост информации в настоящее время приводит к накоплению качественно новых знаний [43, 63]. Традиционные методы обработки накопленных данных, не дают эффективных подходов для ее интеллектуального анализа, в отличие от методов нового и активно развивающегося научного направления Data Mining, нацеленного на поиск ранее неизвестных знаний.

Особый интерес в качестве объекта поиска новых закономерностей представляет персонифицированная информация или персональные данные (ПДн), т.е. информация, генерируемая или так или иначе связанная с конкретной личностью. Значительная потребность в использовании этой информации и ее анализе, в том числе методами Data Mining, в настоящее время испытывается в двух сферах: в бизнес аналитике (в основном для понимания и прогнозирования покупательских предпочтений людей) и сфере государственных услуг (в связи с активным переводом услуг населения в электронный формат: единая карта гражданина РФ, электронные очереди, электронное правительство и прочие сервисы).

В рамках указанной обработки персонифицированной информации все острее проявляются противоречия требований интеллектуального анализа данных и сохранения приватности личности при использовании ее данных. Так 34,7% организаций [93], обрабатывающих персональные данные, в качестве основного препятствия к использованию их в качестве объекта исследования называют неясность положений Федерального закона №152 «О персональных данных»[102]. В частности, законодательно установлено, но не регламентировано требование проведения предварительной процедуры обезличивания персональных данных перед их исследованием [102, Ст.6 п.9], что значительно препятствует полноценному и безопасному их использованию в качестве объекта поиска новых знаний.

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

вступает в конфликт с требованиями другой стороны. Единственным и естественным решением этого противоречия является использование методов обезличивания.

Направлением Data Mining занимались и продолжают заниматься многие российские и зарубежные ученые: Г. Пиатецкий-Шапиро [63], A.B. Дюк [47], И.А. Чубукова [105], Н. Edelstein [17] и др. Использование методов Data Mining применительно к анализу персонифицированной информации без угрозы приватности личности рассмотрены в работах: P.Samarati [21,23], G.Aggarwal [18], RJ Bayardo [10] и др. Наконец, вопросами обезличивания персональных данных в нашей стране посвящены работы: С.Д. Рябко [88], Е.А. Саксонова [91], Р.В.Шередина [91] и др.

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

Объект исследования - базы данных с персонифицированной информацией жителей РФ, находящиеся в свободном доступе в сети Интернет.

Предмет исследования - методы, модели и алгоритмы обработки больших наборов персонифицированных данных.

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

Задачи исследования:

1. Разработка способов оценки свойств персонифицированной информации на основе построения их классификационной структуры;

2. Модификация метода S SA-Гусеница для решения задач DataMining применительно к персональным данным;

3. Построение модели и алгоритма обезличивания данных, позволяющих при необходимости восстанавливать исходные данные;

4. Разработка алгоритма защитного преобразования, зависящего от параметров конкретной операционной среды обработки.

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

Достоверность и обоснованность подтверждена результатами компьютерных экспериментов и внедрением работы в ООО «Новая Клиника» (г. Астрахань).

Научная новизна:

1. Сформирована классификационная структура свойств персональных данных вместе со способами оценки этих свойств, которые позволяют повысить степень эффективности и безопасности обработки данных в процессе поиска новых знаний;

2. Модифицирован метод 88А-Гусеница применительно к анализу данных, не являющихся временными рядами, а также разработана процедура эффективного выбора длины окна, позволяющая результативнее определять характеристики регулярных составляющих в базах данных;

3. Предложена новая модель обезличивания, усовершенствующая модель «к-анонимности» и обеспечивающая более высокий уровень функциональности, по сравнению с последней, за счет реализации возможности восстановления

обезличенной информации;

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

Практическая значимость.

1. Полученные в работе количественные оценки свойств баз данных с персонифицированной информацией могут быть использованы для прогнозирования характеристик результатов идентификации личности в произвольных базах персональных данных;

2. Модифицированный метод 88А-Гусеница позволяет применять различные варианты этого метода для анализа данных, не являющихся временными рядами;

3. Разработанный в работе алгоритм обезличивания данных может быть использован для безопасного хранения и обработки персональных данных в коммерческих целях.

Апробация работы. Основные положения и отдельные результаты диссертации докладывались и обсуждались на Международной научно-технической конференции «Современные информационные технологии - 2011» (Пенза, 2011), Международной конференции по информационной безопасности «Info Security Russia» (Москва, 2010), I международной научно-практической конференции «Эволюция системы научных коммуникаций Ассоциации университетов Прикаспийских государств» (Астрахань, 2008), Международной отраслевой научной конференции профессорско-преподавательского состава Астраханского государственного технического университета (Астрахань, 2010).

Публикации. Основные результаты диссертационного исследования опубликованы в 6 печатных работах: 3 статьях в журналах из списка, рекомендованного ВАК РФ, 3 материалах и трудах конференций. Все работы опубликованы без соавторов.

Структура и объем работы. Работа состоит из введения, 3 глав, заключения, списка литературы из 106 наименований и 5 приложений. Основная часть работы изложена на 117 страницах машинописного текста, содержит 17 таблиц и 45 рисунков.

ГЛАВА 1. АНАЛИЗ ПРОБЛЕМЫ ИДЕНТИФИКАЦИИ ЛИЧНОСТИ ПО

ПЕРСОНАЛЬНЫМ ДАННЫМ

Процесс выявления знаний в больших базах данных требует серьезных вычислительных, временных, а подчас и финансовых затрат [105, стр.19, стр.320, стр.327]. Подобному анализу подвергаются множество категорий данных, среди которых:

• финансовые показатели (колебания курсов валюты, ценных бумаг);

• данные для медицинских, биологических, генетических исследований;

• показатели концентрации геохимических составляющих пород в геологии;

• коммерческая информация для всевозможных маркетинговых исследований и т.п.;

Различия в методах поиска знаний, открытости результатов исследования и способах получения исходных данных для исследования формируют большое разнообразие возможных точек приложения получаемой информации. Некоторые популярные направления даже выделяются в отдельные научные дисциплины. В качестве примера можно привести хемометрику [75] - относительно молодую научную дисциплину, предметом исследований которой являются математические методы изучения химических явлений.

Исходными данными для подобных исследований являются либо результаты целенаправленной регистрации показателей изучаемого объекта, либо ретроспективные данные, которые в большинстве случаев отсутствуют в свободном доступе, что значительно усложняет детальное изучение проблем поиска в больших наборах данных. Кроме того, положительные результаты исследований, а иногда и сам факт их проведения редко афишируются, в связи со значительной коммерческой ценностью [72].

Среди больших наборов данных особо выделяются базы с персонифицированной информацией, благодаря исключительной

распространенности, относительной доступности и потенциально большой ценности. Под «большими данными» в настоящей работе подразумеваются базы данных (БД), содержащие миллионы записей и занимающие гигабайты памяти, в то же время

крупные корпорации уже давно оперирует терабайтами информации и миллиардами записей.

Многие из существующих моделей оценивания информации [103] интерпретируют ценность довольно узко: «аддитивная модель» формирует денежный эквивалент данных, «модели анализа рысков» основываются на рассчитанной денежной стоимости компонентов информации с учетом вероятностных оценок [40] реализации угроз этим компонентам [67]. Наиболее системными представляются модели, определяющие ценность информации как меру увеличения вероятности достижения той цели, для которой она используется. Подобная интерпретация обобщает и стоимостной и рисковый подходы. Согласно A.A. Харкевичу [103, стр. 53]: «если полученная информация не изменяет вероятности достижения цели, это означает, что ценность полученной информации равна нулю. Такая информация называется информационным шумом». Аналогичного «целевого» подхода придерживаются также М.М. Бонгард [32, 33], Р.Л. Стратонович [98, стр. 296-329], В.И. Корогодин [52, стр.2] и др. Корогодин В.И., в частности, ввел термин «полипотентность» [52, стр. 51], означающий, что одна и та же информация может быть использована для решения самых разных задач.

Придерживаясь такой точки зрения можно сказать, что свойство полипотентности