课程大纲 第 53 课,共 156 课 · 诚实地衡量隐私
诚实地衡量隐私

匿名集与熵

为什么重要 新闻标题会说“你的浏览器是独一无二的”或者“这个特征提供 10 比特”之类的话。这一课展示这些数字是如何测量出来的,以及让其中许多数字比真相更大的两个陷阱。这样你就能评判各种隐私说法,包括你自己的。

藏在人群里

想象一个车站里挤满了穿着一模一样黑外套的通勤者。如果你也穿黑外套,你就藏在几百人当中。如果你穿一件亮黄色的,你藏身的人群就只有你自己。

匿名集:在观察者看来和你一模一样的那群人。它越大,你藏得越好。大小为 1 的集合意味着你是独一无二的。

在第 50 课,你测量了一个人 Sam 在人群中有多突出。这里你要测量由 5,000 个合成浏览器(由 synthetic_browsers 编造,没有真实的人)组成的整个人群,看看每个人藏得有多好。

先分组,再计数

挑几个特征,比如 ["timezone", "language"]。每个浏览器的指纹就是这些值组成的元组,例如 ("Europe/London", "en-GB")。元组可以用作字典的键,所以 collections.Counter 能统计有多少个浏览器共享同一个指纹:

from collections import Counter
Counter([("A", "x"), ("A", "x"), ("B", "x")])
# Counter({('A', 'x'): 2, ('B', 'x'): 1})

每个计数都是一个匿名集。计数为 1 的是一个独一无二的浏览器。用上全部 13 个特征时,5,000 个浏览器中的大多数都会变成独一无二的。

熵:描述整个人群的一个数字

在第 48 课,你用香农熵衡量了一段文本中字符的混乱程度。同样的公式也适用于人群:对每个匿名集,取它占所有人的比例 p,然后把 -p * log2(p) 加起来。

(指纹的)熵:跟踪者从这些特征中,平均能了解到一位随机访客的多少比特信息。0 比特:每个人看起来都一样。log2(N) 比特:在 N 个人的人群中,每个人都是独一无二的。

例子:四个浏览器的时区分别是 A、A、B、C。比例是 1/2、1/4 和 1/4,所以熵是 0.5 × 1 + 0.25 × 2 + 0.25 × 2 = 1.5 比特。

陷阱 1:天花板

一个 5,000 人的人群永远显示不出超过 log2(5000)(约 12.3 比特)的熵,因为到那时每个人都已经是独一无二的了。所以一项针对 5,000 个浏览器、发现“12 比特”的研究,可能只是碰到了天花板,而不是在测量这个特征。而且在 5,000 人中独一无二,并不等于在数十亿人中独一无二。样本越大,得到的数字越大,也越诚实。

陷阱 2:把特征加起来

时区和语言是结伴出现的:大多数 Asia/Tokyo 的浏览器都说 ja-JP。显卡和系统也是这样。所以把每个特征单独的熵加起来,会把同样的信息重复计算好几次。你的 sum_of_parts 会远远高于 joint(所有特征一起测量时的熵),也会远远高于 12.3 比特的天花板。联合的那个数字才是诚实的。

一个常见的误解

“熵高就意味着每个人都可以被跟踪。”熵是一个平均值。一个人群可以有很高的熵,而一大群配置非常常见的人仍然藏得很好。既要看平均值,也要看有多少人处在小集合里。

试一试 通过之后,为每个特征打印 entropy_bits(crowd, [t])(参考答案就是这样做的)。哪三个特征携带的比特最多?然后把你自己浏览器在这些特征上的值,和一个指纹测试网站(比如 EFF 的 Cover Your Tracks)进行比较。

用其他语言实现

JavaScript:

function entropyBits(rows, traits) {
  const counts = new Map();
  for (const r of rows) {
    const key = JSON.stringify(traits.map(t => r[t]));
    counts.set(key, (counts.get(key) || 0) + 1);
  }
  let bits = 0;
  for (const c of counts.values()) {
    const p = c / rows.length;
    bits -= p * Math.log2(p);
  }
  return bits;
}

Go:

func entropyBits(keys []string) float64 {
    counts := map[string]int{}
    for _, k := range keys {
        counts[k]++
    }
    bits := 0.0
    for _, c := range counts {
        p := float64(c) / float64(len(keys))
        bits -= p * math.Log2(p)
    }
    return bits
}

回顾

  • 匿名集是所有看起来和你一模一样的人;大小为 1 意味着独一无二。
  • 熵是平均了解到一位访客的比特数:分组、计数,然后对 -p log2(p) 求和。
  • 任何大小为 N 的样本都显示不出超过 log2(N) 比特;小样本会低估人群。
  • 要把特征放在一起测量:一个一个地加起来,会重复计算相互关联的特征。
轮到你了

编写 fingerprint(row, traits)(值组成的元组)、anonymity_sets(rows, traits)(从指纹到计数的字典)、fraction_unique(rows, traits)(处在大小为 1 的集合中的行所占的比例)、entropy_bits(rows, traits)(匿名集上的香农熵)以及 max_bits(n)(log2(n))。然后把 joint 设为 crowd 在全部 TRAIT_NAMES 上的熵,把 sum_of_parts 设为每个单独特征的熵之和。

发现这节课有问题?报告它 · 就这节课提问

这个练习即将开放

完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。