K-Anonymization Tool for databases

Authors

Louis Tochon
Kévin Huguenin (Superviser)

Arborescence des fichiers

Omitted files are not required to understand the project.

📦k-ano_Tool
 ┣ 📂.github\workflows //Configuration folder
 ┃ ┗ 📜python-app.yml //test environnement properties
 ┣ 📂Flask project //First Flask project to gain knowledge
 ┣ 📂K-anoTool //Flask project with the anonimization tool
 ┃ ┣ 📂Env //Virtual Python Env
 ┃ ┣ 📂Static //Static files (JS, CSS, IMG, Saved files)
 ┃ ┣ 📂Templates //HTML Templates
 ┃ ┣ 📂Upload //Sub-directory for Upload part of the project
 ┃ ┣ 📂Result //Sub-directory for Result part of the project
 ┃ ┣ 📂About //Sub-directory for About part of the project
 ┃ ┗ 📜app.py //launch project file
 ┣ 📂Presentation //Folder with powerpoint for meetings
 ┣ 📂Prototyping //Folder with prototypes of generalizytion interface
 ┣ 📂Test_algo //Algorithm's development folder
 ┃ ┣ 📂data
 ┃ ┣ 📂ideas //Ideas for improving algorithms
 ┃ ┣ 📂yed //Folder containing algorithm's graph 
 ┃ ┣ 📜datafly_v1_weighted.py //Proposal of datafly algorithm with weighted attributes
 ┃ ┣ 📜datafly_v1.py //Basic datafly algorithm
 ┃ ┣ 📜incognito_v1.py //First try with incognito algorithm
 ┃ ┣ 📜mondarian.py //Open Source Code for mondarian algorithm
 ┃ ┣ 📜samarati_tree.py //File to generate the distance matrix lattice for samarati algorithm
 ┃ ┣ 📜sw.py //Original proposal algorithm to include weights
 ┃ ┗ 📜ssw.py //Suppr_weighted_algo combined with samarati
 ┣ 📜test.py //test file
 ┣ 📜LICENSE
 ┗ 📜README.md

Goal

The main goal of this project is to provide an anonymization tool to k-anonymize a database with algorithms based on weights for each attribute and to implement a tool to easily create the wanted tree of generalization.

Description of the project

To realize this project, the algorithm created needs to incorporate the weights at each level of generalization to describe the quantity of information lost. The algorithm proposed is called SW and basically tests every possible generalization level to find the smallest information lost. However, testing all combinations is not a viable solution due to the exponential time needed. To solve this problem, a second algorithm is proposed which is called SSW (for Samarati-SW). This one includes a binary search which enables avoiding combinations which are leading to a larger information loss than a previous solution found.

This anonymization algorithm will be deployed on a web application written in Python through the framework Flask.

In a second time, an interface on the same web application will be created to provide a tool to the user to easily create his own tree of generalization.

The crucial point of this project is to do a user-friendly tool with easy interactions to make the experience as simple as possible.

This project will focus on the medical domain to handle a single use case and go as deep as possible to provide a complete tool.

The algorithms

SW (Proposal)

SSW (Proposal)

Complexity comparison

SW

maximum generalization level = n
number of qid = k
number of combination of generalization's level = n^k
one-level generalization = O(n)
max-level generalization = O(k * n²)
anonimity level check = O(n)
supression check = O(n)

Final complexity level : O(n^k * (k * n² + n + n + n)) = O(n^k * (k * n² + 3n)) = O(n^k * n²)

SSW

maximum generalization level = n
number of qid = k
number of combination of generalization's level = n^k
one-level generalization = O(n)
max-level generalization = O(k * n²)
anonimity level check = O(n)
supression check = O(n)