匿名集合とエントロピー
なぜ大切か 見出しには「あなたのブラウザは唯一だ」や「この特徴は 10 ビットを与える」のような言葉が並びます。このレッスンでは、そうした数字がどう測られるのか、そして多くの数字を真実より大きくしてしまう 2 つの落とし穴を示します。そうすれば、自分のものも含めて、プライバシーの主張を判断できます。
群衆に隠れる
同じ黒いコートを着た通勤客でいっぱいの駅を想像してください。あなたも黒いコートを着ていれば、何百人もの中に隠れられます。真っ黄色のコートを着ていれば、隠れる群衆はあなただけです。
匿名集合:観察者から見て、あなたとまったく同じに見える人々の集まりです。大きいほどよく隠れられます。大きさ 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 の 4 台のブラウザ。割合は 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 ビットの天井もはるかに上回るでしょう。正直な数字は joint のほうです。
よくある誤解
「エントロピーが高いなら、全員が追跡できる」。エントロピーは平均です。群衆のエントロピーが高くても、とてもありふれた設定を持つ大きな集団は、まだよく隠れられます。平均と、小さな集合にいる人の数の両方を見てください。
試してみよう 合格したら、各特徴について entropy_bits(crowd, [t]) を表示してください(解答はそうしています)。最も多くのビットを運ぶ 3 つの特徴はどれでしょうか? それから、それらの特徴についての自分のブラウザの値を、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 に、すべての TRAIT_NAMES に対する crowd のエントロピーを、sum_of_parts に、各特徴ひとつずつのエントロピーの合計を設定します。
この演習はまもなく開きます
その前のレッスンを終えると、このレッスンが解放されます。コース全体が無料でアカウントも不要、このレッスンは今すぐ読めます。
このブラウザは learn.floati.life の Cookie をブロックしているため、ここで修了したレッスンを順番どおりに開けません。このサイトの Cookie を許可して再読み込みしてください。