Graf bazlı sorgu seti yöntemi ile diferensiyel mahremiyetin sağlanması

Abstract

Bilimin ve teknolojinin gelişmesiyle birlikte dünyamız ve günlük hayatımızın da her bir evresi değişmeye ve gelişmeye devam ediyor. Özellikle yirminci yüzyılda oluşup gelişen bilgisayar ve hesaplamalı bilimler gündelik hayatımızın gelişmesine büyük etki yapmıştır. Bilimin gelişmesi için şunu söyleyebiliriz, bundan bin yıl evvel gözlem ve deneye dayalı olan bilim, son beş yüz yılda teorik bir unsur halini de aldı ve birçok bilimin hem deneysel hem teorik dalları mevcut bulunmaktadır. Ancak son elli yılda gelişen bilişim ve teknolojiyle, birçok disiplin hesaplamalı branşlara da sahip oldu (deneysel fizik, teoriksel fizik, hesaplamalı fizik gibi). Fakat hesaplamalı bilim bilgi yönetiminide içerecek şekilde gelişmektedir ve her gün büyük miktarda veri toplanmaktadır. Sonuç olarak geldiğimiz nokta itibariyle bizler veri çağında yaşıyoruz.Toplanan büyük miktarda veri arasından gerekli bilgiyi çıkarma işlemine gereksinim duyulmuştur ve bilgi keşif süreçleri için gereken adımları sırasıyla belirtmek gerekirse veri temizleme, veri entegrasyonu, veri seçimi, veri dönüştürme, veri madenciliği, model değerlendirme ve bilgi sunumudur. Veri madenciliği bu süreç içinde, yetenekli metodlar uygulayarak veri modellerini çıkarır. Veri madenciliğinin değişik görevleri mevcuttur ve bu görevleri yüksek seviyede öngörücü ve tanımlayıcı olarak kategorileştirebiliriz. Sınıflandırma ve Bağlanım görevleri ve bunların algoritmaları, İlişki Kuralı Analizi, Küme Analizi, Metin, Bağlantı ve Kullanım madenciliği mevcuttur. Veritabanlarına kaydedilen büyük çaplı veri, veri analizcilerine sunulur ve gerekli bilgilerin çıkarılması beklenir. Ancak bu süreçte bir dezavantaj oluşmaktadır. Bu dezavantaj ise veri analizcilerinin veri setinde kaydı bulunan bireylerin hassas verilerine erişebilmesi durumudur. Bunun engellenmesi için Mahremiyeti Koruyan Veri Madenciliği alanı gelişmiştir ve ifşa edilmesi istenmeyen veya izin verilmemiş hassas bilgileri korumak isteyen veri madenciliği alanıdır. Bu alanda yapılan çalışmalar olarak hassas bilgilerin korunması ve mahremiyetin sağlanması için K-Anonimlik, L-Çeşitlilik, T-Yakınlık gibi yöntemler geliştirilmiştir.2006 yılında ise Dwork, Diferansiyel Mahremiyet'i anlattığı yöntemde etkileşimli olan bir güvenlik mekanizması yöntemi sunmuştur. Dwork bu makalesinde istatistiksel veritabanı güvenliğinin, krpitoloji alanındaki semantik güvenliğin aksine, kişisel verilerin korunmasını garanti etmesinin mümkün olmadığını kanıtlamıştır. Semantik güvenli bir kriptolojik sistemde, görülmeden öğrenilemeyen şifreli mesaj incelenerek açık mesaj hakkında herhangi bilgi elde edinilemez. Ancak istatistiksel veritabanları için benzeri tanımların mahrem bilgileri koruma yöntemleri için mümkün olmadığını ispat edilmiştir. Bunun sebebi de saldırıyı yapacak kişinin yardımcı bir bilgiye sahip olmasıdır. Bu yöntemde bir güvenilir veri toplayıcısının sunduğu arayüz üzerinden kullanıcıların veritabanına sorgular atılması sağlanıp, muhtemelen gürültü eklenmiş cevaplar gösterilir. Diferansiyel Mahremiyet sadece istatistiksel sorgulara izin verir ve Diferansiyel Mahremiyet'in SQL dilinde uygulandığı bir yöntem geliştirilmiştir. Toplama Fonksiyonlarından bazılarına (COUNT, SUM, MIN ve MAX) uygulanabilir, ancak bu tez çalışmasında sadece COUNT Toplama Fonksiyonu üzerinden ilerlenilmiştir. Buna göre sorguların alanları bulunup grafa döküldükten sonra, NP-Hard bir problem olan sorgu kümesinin hassasiyeti bulunmuştur. Hassasiyet bulunduktan sonra mahremiyet bütçesi olan ɛ değeri ile bulunan hassasiyet değeri ölçeklenecek şekilde gürültü eklenerek kullanıcıya muhtemelen gürültülü cevapların döndüğü bir yöntem geliştirilmiştir. Bu sayede Diferansiyel Mahremiyet sağlanarak kişilerin hassas verilerinin korunmasına yönelik bir yöntem geliştirilmiştir.Bu yönteme uygun sorgu setleri oluşturularak veri analizi görevleri uygulanırsa hassasiyetin korunması sağlanmaya çalışılabilir. Bu tez çalışmasında değinilen bilgi kazanımıyla entropi hesaplama ile Öznitelik Seçimi, Ki-kare testi ile Korelasyon Analizi ve Naïve Bayes sınıflandırıcılarla Sınıflandırma işlemlerinde veritabanına atılacak sorguların Graf Bazlı Sorgu Seti Yöntemine uygun olarak atılması durumunda Diferansiyel Mahremiyet sağlanabilir.

As the technology and science has been improved, our daily life has changed. Especially, with the invention and improvement of computer at the 20th century, we can say that one of the most important thing that affects human life is computer science.According to Szalay and Gray, Computational Science is the new branch of most disciplines. However, empirical science was mainly a thousand years ago. After that, in the past five hundred years, theoretical science had been a part for almost every discipline. But now, most disciplines have empirical and theoretical parts. Moreover, in the past fifty years, computational branch has been another part for most disciplines. To give an example and clarify this, we can consider Physics. Physics has different branches; empirical Physics, theoretical Physics and computational Physics. And due to the Computational Science, scientist have to deal with a huge amount of data which is from new scientific instruments, simulations, online data and Internet. So, because of information management by computational science, computer science challenges have been shown up.There is a popular word which mentions that people are living in the information age. If we understand what data mining is, that word is not correct. Human are living in the data age actually. As it is mentioned, there is a great amount of data that is collected each every day and will be. Some people take data mining as a synonym for knowledge discovery from data, whereas some take it as just a step in the knowledge discovery process. These steps are data cleaning, data integration, data selection, data transformation, data mining, pattern evaluation and knowledge presentation. Data cleaning, data integration, data selection and data transformation are considered as preprocessing for data mining. And at the mining step some intelligent methods are applied to find patterns. Then with evaluation where interesting patterns due to interesting measures are represented. These are the steps to turn data into knowledge.It is a common approach that data are published for analysis. However, there is a privacy risks behind of sharing data. This privacy risk and possible disadvantage is the disclosure of sensitive information of individual. There is an area to prevent this risk which is called Privacy Preserving Data Mining. According to the description of Evfimievski and Grandison, this area tries to safeguard sensitive information from unsolicited or unsanctioned disclosure.To mention some studies of the Privacy Preserving Data Mining area, K-Anonymity, L-Diversity, T-Closeness has been published. K-Anonymity is a method which considers the quasi-identifiers, L-Diversity is a technique beyond K-Anonymity which considers diversity of sensitive data. And T-Closeness is another method beyond both K-Anonymity and L-Diversity. With T-Closeness method, it is aimed that the distribution of sensitive data in a group should be close to all data.Differential Privacy is a protection mechanism by Dwork. According to Dwork, there is no absolute guarantee by statistical database security, where semantic security in cryptography can guarantee to individuals. From a semantically secure cryptosystem, we can not gain any information about text-plain by cipher-text which can not be learned without seeing it. But Dwork proved that, same definition is not possible due to the auxiliary information. For example, supposing an attacker who knows an individual's height is 2 inches shorter than the average height of women in a country. And the database gives the information of the average height of women in the individuals' country. Then the attacker can exactly know the height of the individual. So there is always some risk for sensitive data for any statistical database. Moreover, there is two privacy mechanism models. One is non-interactive and the other one is interactive. With the non-interactive model, the data which has sensitive information is sanitized before it is published and shared. K-Anonymity is an example for this type of model. On the other hand, with interactive model, a trusted data collector provides an interface so that the interface users can pose queries and get the possible perturbed answers. Differential privacy is an example to interactive models.In this study, an approach to achieve the differential privacy is studied and explained. This model is fit for SQL which is very common in information technologies. With the approach and method only some statistical queries are considered to be answered with a provided interface. These statistical queries can have some aggregate functions which are COUNT, SUM, MIN and MAX. However, as an aggregate function COUNT is mainly considered and explained in this study.As the step for Differential Privacy, computation the sensitivity of a query set is NP-hard. But in the study, an approach to calculate the sensitivity of the query set is explained. So the solution is that building region-intersection graph for non ignored queries. After the intersections are measured, a graph is generated where each every node represents a query, and edges between nodes represents intersection of regions. Then it is showed that computation of the sensitivity of the query set is equivalent to bounding the sensitivity from above. After the sensitivity of the query set is found, Laplace noise is added to the each every non ignored query. To add the Laplace noise, there is two magnitude; the sensitivity of the query set and privacy budget ɛ. Then the users of the interface get the possibly perturbed answers and with the model Differential Privacy is provided for only statistical queries which fits the model.Moreover, it is possible to use this model for data analysis techniques. The model fits for some data analysis techniques because in order to apply the technique, the queries can be generated based on the model in this study. Although there is a lot of data analysis models fits with the model, there is some implemented and mentioned ones; Feature Selection with entropy, Correlation Analysis by chi-square test and Classification with Naïve Bayes Classifiers. All of these three data analysis techniques can be applied with SQL queries which fits the model explained. So, it is possible to analyze the data while protecting the sensitive information of individuals.Feature Selection is the process to calculate the top-k attributes with the lowest entropy. So that, the lowest entropy offers the highest information gain. The top-k attributes can be used to generate decision trees. Correlation Analysis is for analysis the correlation between the attributes of a table. In the study, Chi-square test is used to calculate the correlation between attributes. Naïve Bayesian Classifiers which are statistical, tries to find out the probabilities for a given tuple the belonging class. For example, according to a training data set, the belonging class probabilities of a tuple are found and decision is made.