Archive for Marzec, 2015

Marzec 1, 2015

Zachowywanie prywatności w sieciach społecznościowych

- autor: tsissput

Z pewnością każdy z nas zauważył, że sieci społecznościowe wdarły się szturmem do naszego życia i z uwagi na swoją ogromną popularność nieprędko z niego znikną. W 2013 roku blisko77 90% polskich internautów korzystało z serwisów społecznościowych (dane firmy badawczej Gemius). Co więcej, około 12% pracodawców przyznaje się do przeglądania facebookowych profili kandydatów na stanowisko przed ich zatrudnieniem (dane z roku 2007!). Wraz ze wzrostem popularności serwisów typu Facebook, Twitter, Youtube, coraz większa waga przykładana jest (i słusznie!) do zachowywania prywatności w sieciach społecznościowych.

Żeby dokładnie zrozumieć poruszane w niniejszej notce zagadnienia wprowadzimy model sieci społecznościowej w postaci grafu, w którym wierzchołki odnoszą się do użytkowników, natomiast krawędzie do relacji pomiędzy nimi. Gdy mówimy o prywatności w takiej sieci, musimy uwzględnić wiele aspektów, między innymi:

  • istnienie użytkownika w sieci – jeśli osoba postronna (nazwijmy ją atakującym) dowie się, że dany użytkownik jest w konkretnej sieci (np. sieci reprezentującej milionerów), prywatność zostanie naruszona,
  • parametry wierzchołka takie jak np. jego stopień – jeśli atakujący odkryje ilość połączeń danego użytkownika, może dowiedzieć się o jego priorytecie w sieci,
  • połączenie z inną jednostką sieci – np. podczas transakcji finansowej gdy dwa wierzchołki mają połączenie gdy nastąpiła wymiana środków – również narusza prywatność,
  • wrażliwe dane, które mogą być przypięte do użytkownika (np. ciężka choroba).

Aby móc myśleć o zachowaniu prywatności w sieci, należy wiedzieć w jaki sposób są one „atakowane”. Wyróżniamy ataki aktywne – takie, w których do ataku używane są nowe wierzchołki wprowadzane do sieci, które dołączają się do starych wierzchołków oraz ataki pasywne, w których nie są dodawane ani wierzchołki, ani krawędzie. Atakujący najczęściej zanim zdobędzie poufne dane konkretnego użytkownika musi znać jego otoczenie – wiedza o sąsiadujących wierzchołkach, znajomość topologii mogą wiele „pomóc” atakującemu. Aby utrudnić atakującemu identyfikację konkretnego wierzchołka wprowadza się tzw. anonimizację danych. Jak sama nazwa wskazuje, służy ona po to, by zachować anonimowość poprzez „wystawienie” na zewnątrz sieci z takimi wierzchołkami, aby niemożliwe było ich rozróżnienie.

K-­anonimizacja (K-anonymity)

K­anonimizacja polega na „zaciemnianiu” niektórych danych, aby istniało co najmniej K – 1 węzłów, które będą takie same, a co za tym idzie nierozróżnialne, anonimowe. Innymi słowy nie ma możliwości, aby w sieci istniał jakiś jeden niepowtarzalny wierzchołek (np. gdyby zawierał nr telefonu komórkowego i byśmy nie „zaciemnili” tego numeru – byłoby to niemożliwe). Poniżej przykład 2­anonimizacji. Oryginalna tabela przedstawiająca wierzchołki w sieci:

tab1

Po 2-­anonimizacji ta sama tabela będzie wyglądała następująco:

tab3

W anonimizacji dąży się do tego, aby żaden z obiektów nie wskazywał na konkretny podmiot/przedmiot w sposób jednoznaczny. Ciekawostka: aby jednoznacznie zidentyfikować 87% obywateli USA, „wystarczy” znać datę urodzenia, płeć oraz kod pocztowy.

K­anonimizacja nie musi dotyczyć wyłącznie samych danych – może również dotyczyć np. stopnia wierzchołka (K­degree anonymity). Efekt działania tej anonimizacji jest następujący: dla każdego wierzchołka uzyskujemy co najmniej K – 1 wierzchołków o tym samym stopniu. Nigdy nie będzie sytuacji, że jakiś wierzchołek będzie miał unikatową liczbę połączeń z innymi wierzchołkami. Wykonywane jest to przez algorytm odpowiednio dodający fałszywe i usuwający prawdziwe krawędzie. Empiryczne badania pokazały, że można zachować topologiczną użyteczność grafu zaspokajając założenia K­stopniowej anonimizacji.

Oprócz tych dwóch K­anonimizacji istnieje również K­anonimizacja sąsiadów (K­neighbourhood anonymity), która z kolei wymaga, aby dla wierzchołka istniało K – 1 innych wierzchołków, dla których podgraf bezpośrednich sąsiadów będzie izomorficzny z podgrafem bezpośrednich sąsiadów ów wierzchołka. Innymi słowy – aby w sieci nie istniał żaden wierzchołek o unikatowym zestawie najbliższych sasiadów.

Anonimizacja poprzez losowość

Losowe dodawanie/usuwanie elementów grafu jest kolejną często stosowaną strategią zachowywania prywatności w sieciach. W tej strategii poprzez wprowadzanie fałszywego szumu utrudniamy odczytywanie i eksplorację sieci przez atakującego. Dodatkowo możemy zachowywać niektóre własności grafu np. poprzez dodanie wierzchołkowi k losowych relacji do innych wierzchołków oraz usunięcie k losowych relacji od „starych” wierzchołków zawsze zachowujemy stopień wierzchołka.

Jeśli z n wierzchołków zrobilibyśmy macierz A o wymiarach n * n i uzupełnili wewnątrz pola: 1 – jeśli między wierzchołkiem, który odpowiada wierszowi, a wierzchołkiem, który odpowiada kolumnie jest relacja oraz 0 – gdy relacji nie ma, to wynik procesu anonimizacji poprzez losowość przedstawilibyśmy jako sumę macierzy A + E, gdzie macierz E byłaby „macierzą mieszania”. W macierzy E mielibyśmy wartości +1, jeśli krawędź między odpowiadającymi wierzchołkami została dodana, oraz ­1, gdy usunięta.

Przykład:

tab4

Macierz wynikowa:
tab5

Widać, że w „zafałszowanej” macierzy wynikowej połączenia są inne, natomiast mając „macierz mieszania” jesteśmy w stanie łatwo powrócić do macierzy oryginalnej.

Anonimizacja przez generalizację

W odróżnieniu od K­anonimizacji oraz anonimizacji przez losowość, które modyfikowały strukturę grafu (dodawały/usuwały krawędzie), anonimizacja przez generalizację polega na grupowaniu wierzchołków w klastry (albo grupowaniu relacji), w których można odpowiednio ukryć wrażliwe dane. Najlepszym przykładem może być przedział wiekowy, do którego „wrzucimy” wierzchołek, a w którym już znajdują się inne wierzchołki. Podczas generalizacji niestety musimy się liczyć z utratą części danych lub precyzji – np. zamiast wieku 24 mamy przedział wiekowy (na przykład <20; 40>).

Efektem generalizacji mógłby być np. graf złożony z superwierzchołków zawierających co najmniej K „zwykłych” wierzchołków, a pomiędzy superwierzchołkami byłyby superrelacje, czyli krawędzie pomiędzy superwierzchołkami o wadze równej ilości połączeń między wierzchołkami z dwóch stron superrelacji. Generalizacja jest skutecznym sposobem na anonimizację, aczkolwiek stosowanym w przypadku gdy możemy sobie pozwolić na utratę precyzji.

Przykład generalizacji można przedstawić na znanej już tabeli:

tab1

Po generalizacji oraz dodatkowym „zaciemnieniu” innych danych mamy:

tab2

Metody zachowywania prywatności w sieciach społecznościowych są wciąż w początkowym stadium (porównując np. do danych tabularnych). Wynika to przede wszystkim z tego, że są one znacznie bardziej skomplikowane, dlatego też zachowanie w nich anonimowości jest większym wyzwaniem. Natomiast można się spodziewać szybkiego rozwoju tej dziedziny ze względu na coraz większe zapotrzebowanie na ochronę danych, które „wystawione są” w serwisach już codziennego użytku.

Nie wyobrażam sobie dalszego rozwoju serwisów społecznościowych bez usprawniania ochrony danych w nich przechowywanych. Chociaż w tej chwili zadziwiająco duży odsetek użytkowników korzystających z najpopularniejszych z serwisów nie wydaje się być zainteresowany zachowywaniem prywatności myślę i mam nadzieję, że w najbliższej przyszłości to się zmieni. Aby tak było wraz z rozwijaniem technologii konieczne jest rozwijanie również świadomości użytkowników i ich wiedzy na temat niebezpieczeństw związanych ze zdradzaniem zbyt wielu informacji o sobie w serwisach, w których „żyją”.

Źródła:
http://mic.psnc.pl/download/pgnet_111013_1.pdf
https://www.cs.sfu.ca/~jpei/publications/SocialNetworkAnonymization_survey.pdf
http://webpages.uncc.edu/xwu/publ/ppsn.pdf