Tập ẩn danh và entropy
Vì sao điều này quan trọng Các tiêu đề báo hay nói những câu như "trình duyệt của bạn là duy nhất" hay "đặc điểm này cho 10 bit". Bài này cho bạn thấy những con số như vậy được đo ra sao, và hai cái bẫy khiến nhiều con số trong đó lớn hơn sự thật. Khi đó bạn có thể đánh giá các tuyên bố về quyền riêng tư, kể cả của chính bạn.
Ẩn trong đám đông
Hãy tưởng tượng một nhà ga đầy người đi làm mặc áo khoác đen giống hệt nhau. Nếu bạn cũng mặc áo khoác đen, bạn ẩn giữa hàng trăm người. Nếu bạn mặc một chiếc áo vàng rực, đám đông bạn ẩn vào chỉ có mình bạn.
Tập ẩn danh (anonymity set): nhóm người trông giống hệt bạn trong mắt một người quan sát. Nó càng lớn, bạn càng ẩn tốt. Một tập có kích thước 1 nghĩa là bạn là duy nhất.
Ở bài 50 bạn đã đo một người, Sam, nổi bật đến mức nào trong một đám đông. Ở đây bạn đo cả đám đông 5.000 trình duyệt tổng hợp (do synthetic_browsers tạo ra, không có người thật nào), để xem mọi người ẩn tốt đến đâu.
Gom nhóm, rồi đếm
Chọn vài đặc điểm, ví dụ ["timezone", "language"]. Dấu vân tay của mỗi trình duyệt là tuple các giá trị đó, ví dụ ("Europe/London", "en-GB"). Một tuple dùng được làm khóa dict, nên collections.Counter có thể đếm bao nhiêu trình duyệt có chung mỗi dấu vân tay:
from collections import Counter
Counter([("A", "x"), ("A", "x"), ("B", "x")])
# Counter({('A', 'x'): 2, ('B', 'x'): 1})Mỗi số đếm là một tập ẩn danh. Số đếm bằng 1 là một trình duyệt duy nhất. Với đủ 13 đặc điểm, phần lớn trong 5.000 trình duyệt hóa ra là duy nhất.
Entropy: một con số cho cả đám đông
Ở bài 48 bạn đã dùng entropy Shannon để đo các ký tự của một văn bản lộn xộn đến mức nào. Cùng công thức đó hoạt động trên một đám đông: với mỗi tập ẩn danh, lấy tỉ lệ p của nó trên tổng số người, và cộng dồn -p * log2(p).
Entropy (của một dấu vân tay): số bit trung bình một bên theo dõi biết được về một khách ngẫu nhiên từ các đặc điểm này. 0 bit: mọi người trông như nhau. log2(N) bit: mọi người trong một đám đông N người đều là duy nhất.
Ví dụ: bốn trình duyệt với múi giờ A, A, B, C. Các tỉ lệ là 1/2, 1/4 và 1/4, nên entropy là 0.5 x 1 + 0.25 x 2 + 0.25 x 2 = 1.5 bit.
Bẫy 1: trần
Một đám đông 5.000 không bao giờ có thể cho thấy hơn log2(5000), khoảng 12.3 bit, vì tới lúc đó mọi người đã là duy nhất. Nên một nghiên cứu trên 5.000 trình duyệt tìm thấy "12 bit" có thể đang chạm trần, không phải đang đo đặc điểm. Và duy nhất trong 5.000 không phải duy nhất trong hàng tỉ. Mẫu lớn hơn cho những con số lớn hơn, trung thực hơn.
Bẫy 2: cộng dồn các đặc điểm
Múi giờ và ngôn ngữ đi cùng nhau: phần lớn trình duyệt Asia/Tokyo nói ja-JP. Card đồ họa và hệ thống cũng vậy. Nên cộng entropy của từng đặc điểm riêng lẻ là đếm cùng một thông tin nhiều lần. sum_of_parts của bạn sẽ ra cao hơn nhiều so với joint, entropy của mọi đặc điểm đo cùng nhau, và cao hơn nhiều so với trần 12.3 bit. Con số kết hợp mới là con số trung thực.
Một hiểu lầm phổ biến
"Entropy cao nghĩa là ai cũng bị theo dõi được." Entropy là một trung bình. Một đám đông có thể có entropy cao trong khi một nhóm lớn những người có cấu hình rất phổ biến vẫn ẩn tốt. Hãy nhìn cả trung bình lẫn có bao nhiêu người nằm trong các tập nhỏ.
Tự thử Khi bạn qua, in entropy_bits(crowd, [t]) cho mỗi đặc điểm (lời giải làm việc này). Ba đặc điểm nào mang nhiều bit nhất? Rồi so sánh các giá trị riêng của trình duyệt bạn cho những đặc điểm đó với một trang kiểm tra dấu vân tay như Cover Your Tracks của EFF.
Trong các ngôn ngữ khác
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
}Tóm tắt
- Một tập ẩn danh là mọi người trông giống hệt bạn; kích thước 1 nghĩa là duy nhất.
- Entropy là số bit trung bình biết được về một khách: gom nhóm, đếm, rồi cộng -p log2(p).
- Không mẫu N nào cho thấy được hơn log2(N) bit; mẫu nhỏ đánh giá thấp đám đông.
- Đo các đặc điểm cùng nhau: cộng từng cái một đếm trùng các đặc điểm liên kết.
Viết fingerprint(row, traits) (một tuple các giá trị), anonymity_sets(rows, traits) (một dict từ dấu vân tay tới số đếm), fraction_unique(rows, traits) (tỉ lệ các hàng nằm trong một tập kích thước 1), entropy_bits(rows, traits) (entropy Shannon trên các tập ẩn danh) và max_bits(n) (log2(n)). Rồi đặt joint là entropy của crowd trên mọi TRAIT_NAMES, và sum_of_parts là tổng entropy của từng đặc điểm đơn lẻ.
Bạn thấy vấn đề gì trong bài học này? Hãy báo cáo nó · Hỏi về bài học này
Bài tập này sẽ sớm mở.
Hoàn thành bài học trước đó để mở khóa bài này. Toàn bộ khóa học là miễn phí, không cần tài khoản, và bạn có thể đọc bài học này ngay bây giờ.
Trình duyệt này đang chặn cookie cho learn.floati.life, nên các bài học bạn đã hoàn thành tại đây không thể mở theo thứ tự. Hãy cho phép cookie cho trang web này và tải lại trang.