差分隐私-k匿名化 - 文章频道 - 小小黑客安全攻防

k匿名性

在上一篇文章差分隐私进阶-去标识和重标识攻击中使用重标识攻击来获取隐私数据，这篇文章就介绍了使用k-匿名性来解决这个问题。

属性定义：令$B(A1, A2, ..,An)$是一个有限数据的元组（一行数据称为元组）表格，其中表格B的有限属性集为$QT={A1, A2, …,A_n}$。

准标识符定义：令U为一个实体集合，$T(A1, A2,… ,An)$为实体集合的信息表， $fc : U \to T， fg: T \to U$分别表示从实体映射到表格和表格映射到实体。准标识符$pi$满足以下条件：

$$ fg(fc(qi)[QT])=p_i $$

表示准标识符能够从实体集合U中映射出表格T中的数据，这些数据又能从表格T映射出实体U的实体。

K-匿名性定义：令$RT(A1, A2, ..,An)$是一个表格，$QI{RT}$是与之相关的准标识符。当且仅当$RT{[QI{RT}]}$中的每个数值序列至少出现k次时，才能称为满足k-匿名性。

比如，一张表中，$QI_{RT}={name, id}$，则这个数值序列至少出现k次。

验证k-匿名性

构建一个包含年龄和两个考试分数的表格

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from pandas import DataFrame

raw_data = {
    'first_name': ['Jason', 'Molly', 'Tina', 'Jake', 'Amy'], 
    'last_name': ['Miller', 'Jacobson', 'Ali', 'Milner', 'Cooze'], 
    'age': [42, 52, 36, 24, 73], 
    'preTestScore': [4, 24, 31, 2, 3],
    'postTestScore': [25, 94, 57, 62, 70]}
#df = pd.DataFrame(raw_data, columns = ['first_name', 'last_name', 'age', 'preTestScore', 'postTestScore'])
df = pd.DataFrame(raw_data, columns = ['age', 'preTestScore', 'postTestScore'])
df

根据k-匿名性的定义，我们实现一个函数来验证该表格满足多少匿名性。

def is_k_anonymized(df:DataFrame, k):
    for index, row in df.iterrows():
        query = ' & '.join([f"{col} == {row[col]}" for col in df.columns])
        rows = df.query(query)
        if rows.shape[0] < k:
            return False
    return True

print(is_k_anonymized(df, 1))
print(is_k_anonymized(df, 2))
# 输出：
# True
# False

泛化数据来满足k-匿名性

泛化是指将数据修改为不那么特殊的数据，可以和其他数据相匹配。比如，可以对年龄的只保留十位有效数字。通过修改数据来达到满足k-匿名性。

引入更多的数据可以减少泛化影响吗

我们读入上一篇的数据，看看是否能够轻易的通过泛化使其满足k-匿名性

adult_data = pd.read_csv("./data/data_ch1.csv")
adult_data.head()

现在，将年龄，受教育年数作为准标识。我们只对这2个属性做泛化处理。尝试让其满足k=2的匿名性。

df = adult_data[["Age", "Education-Num"]]
df.columns = ["age", "deu"]
is_k_anonymized(df, 1)
# 输出：True
is_k_anonymized(df, 2)
# 输出：False

可以发现，该数据不满足k=2的属性,下面我们将其泛化一下，来达到满足k=2的属性

# 首先对各列的NAN值进行填充
for col in df.columns:
    df[col].fillna((int(df[col].mean())))

# 定义泛化函数
def generalize(x:int):
    return x%10

df=df.apply(generalize)

我将上面的数据直接泛化到0-10之间了。下面我们来看看是否符合k=2的匿名性

is_k_anonymized(df, 2)
# 输出：True

其实，当数据量也大，就越容易满足k-匿名性。上面所做的实验是采用了全局泛化技术。还有局部泛化技术。局部泛化技术是通过统计准标识符属性下的特殊数值进行泛化处理，尽量将损失降到最小。

Datafly算法

算法的步骤：

* 对每个准标识符属性的取值进行数量统计，对取值数量最大的标识符进行层级化的泛化

* 在泛化后的表格进行k-匿名性检测，如果不合格就泛化一下一个准标识属性。

for col in df.columns:
    print(f"{col}列： {df[col].value_counts().shape[0]}")
# 输出：
# age列： 69
# deu列： 16

可以看出，age的取值数量最大，下面对其进行泛化处理。

df["age"]=df["age"].apply(lambda x: x%10)
is_k_anonymized(df, 2)
# 输出 False
for index, row in df.iterrows():
    query = ' & '.join([f"{col} == {row[col]}" for col in df.columns])
    rows = df.query(query)
    if rows.shape[0] < 2:
       print(query)
# 输出：
"""
age == 2 & deu == 2
age == 9 & deu == 2
age == 9 & deu == 1
age == 2 & deu == 1
"""

然后，我们可以看到在对age进行泛化处理后的数据，依旧有4组数据不满足k-匿名性，则对edu进行泛化处理。

df["deu"]=df["deu"].apply(lambda x: x%6)
is_k_anonymized(df, 2)
# 输出
# True