So khớp yêu cầu với quy tắc
Vì sao điều này quan trọng Một bộ chặn kiểm tra từng yêu cầu một mà trang thực hiện, thường hơn một trăm mỗi trang, với hàng chục nghìn quy tắc. Nếu việc kiểm tra đó chậm, mọi trang đều có cảm giác chậm, và mọi người tắt bộ chặn đi. Nhanh và đúng là điều khiến sự bảo vệ dùng được.
Hai việc: đúng câu trả lời, nhanh chóng
Hãy nghĩ tới một thư viện có 5.000 cuốn sách. Để tìm một cuốn, bạn sẽ không đọc mọi gáy sách từ kệ đầu tiên. Bạn tới đúng khu, rồi đúng kệ. Một bộ chặn nên làm y như vậy: nhảy thẳng tới vài quy tắc có thể khớp, và chỉ kiểm tra những cái đó.
Bài tập này được chấm trên cả hai. Các bài kiểm tra đếm số lần decide của bạn gọi rule_matches cho một yêu cầu, và ngân sách là 20 lần kiểm tra khi đã tải 5.000 quy tắc. Ta đếm số lần kiểm tra thay vì bấm giờ, nên một điện thoại chậm và một máy tính xách tay nhanh được chấm theo cùng một cách.
Bước 1: ký tự đại diện
Ký tự đại diện (wildcard): một ký hiệu thay cho "bất kỳ ký tự nào". Trong danh sách bộ lọc nó là *, nên /beacon/*/hit khớp /beacon/42/hit và /beacon/abc/hit.
Tách mẫu tại mỗi dấu *, rồi tìm các mảnh trong văn bản, theo thứ tự, mảnh nào cũng đứng sau mảnh trước:
wildcard_in("*/collect?*cid=", "https://m.example/collect?x=1&cid=9")
# pieces: "/collect?" then "cid=" -> both found, in order -> True
wildcard_in("a*b", "b then a")
# "a" found at position 7, then no "b" after it -> Falsetext.find(piece, pos) trả về vị trí piece bắt đầu, chỉ tìm từ vị trí pos, hoặc -1 nếu nó không có ở đó. Chú ý rằng trong danh sách bộ lọc ? và . là các ký tự bình thường, nên đừng dùng biểu thức chính quy hay fnmatch, vốn coi chúng là đặc biệt.
Bước 2: một quy tắc với một yêu cầu
rule_matches(rule, url, third_party) trả lời có hoặc không cho một quy tắc:
- Một quy tắc có đặt
third_partykhông bao giờ khớp một yêu cầu bên thứ nhất. - Một quy tắc tên miền
adco.examplekhớp máy chủadco.examplehoặc bất kỳ máy chủ nào kết thúc bằng.adco.example. Dấu chấm quan trọng:notadco.examplelà của người khác. - Một quy tắc mẫu khớp khi
wildcard_in(value, url.lower())là đúng.
Bước 3: một chỉ mục, để bạn chỉ kiểm tra vài quy tắc
Chỉ mục (index): một cấu trúc được dựng một lần cho phép bạn tìm thứ gì đó mà không phải tìm khắp mọi nơi, như mục lục ở cuối một cuốn sách. Ở đây: một dict từ tên máy chủ tới các quy tắc cho máy chủ đó.
Một dict của Python tìm thấy một khóa trong một bước, dù nó chứa bao nhiêu khóa. Nên hãy dựng, một lần:
index = {"domains": {"adco.example": [rule, ...], ...},
"patterns": [rule, rule, ...]}Với một yêu cầu tới img.adco.example, hãy tra mọi phần đuôi của tên máy chủ: img.adco.example, adco.example, example. Đó là ba lần tra thay vì 5.000 lần kiểm tra. Thêm vài quy tắc mẫu (các bộ chặn thật cũng lập chỉ mục cho chúng, theo một đoạn văn bản ngắn chúng phải chứa; ta giữ chúng trong một list trơn).
Bước 4: quyết định, với ngoại lệ thắng
Kiểm tra mỗi ứng viên. Nếu bất kỳ quy tắc khớp nào là một ngoại lệ, câu trả lời là "allow", dứt khoát. Nếu không, nếu bất kỳ quy tắc chặn nào khớp, "block"; nếu không có gì khớp, "allow". Ngoại lệ tồn tại vì đôi khi danh sách bắt nhầm những thứ một trang thật sự cần, như cdn.example, nơi phục vụ một thư viện vô hại.
Một hiểu lầm phổ biến
"Nhiều quy tắc hơn nghĩa là một bộ chặn chậm hơn." Với một chỉ mục tốt thì không: tra một máy chủ trong một dict tốn khoảng như nhau dù có 50 hay 50.000 quy tắc. Thứ làm chậm một bộ chặn là kiểm tra các quy tắc từng cái một.
Tự thử Sau khi bạn qua, đổi decide để lặp qua mọi quy tắc trong list (không có chỉ mục) và chạy lại các bài kiểm tra. Bài kiểm tra ngân sách thất bại với số đếm khoảng 5.000. Con số đó là phần việc chỉ mục của bạn tiết kiệm cho mỗi yêu cầu của mỗi trang.
Trong các ngôn ngữ khác
JavaScript:
function wildcardIn(pattern, text) {
let pos = 0;
for (const piece of pattern.split("*")) {
if (!piece) continue;
const at = text.indexOf(piece, pos);
if (at === -1) return false;
pos = at + piece.length;
}
return true;
}
// Index: a Map from host to rules; look up each ending of the host.
function candidates(index, host) {
const parts = host.split(".");
const out = [];
for (let i = 0; i < parts.length; i++) {
out.push(...(index.domains.get(parts.slice(i).join(".")) || []));
}
return out.concat(index.patterns);
}Go:
func wildcardIn(pattern, text string) bool {
pos := 0
for _, piece := range strings.Split(pattern, "*") {
if piece == "" {
continue
}
at := strings.Index(text[pos:], piece)
if at < 0 {
return false
}
pos += at + len(piece)
}
return true
}Tóm tắt
- Mẫu có ký tự đại diện: tách tại
*và tìm các mảnh theo thứ tự. - Quy tắc tên miền khớp máy chủ hoặc bất kỳ tên miền con nào, so sánh theo từng nhãn.
- Một chỉ mục (một dict theo máy chủ) nghĩa là vài lần tra thay vì hàng nghìn lần kiểm tra.
- Một ngoại lệ khớp luôn thắng một quy tắc chặn.
Viết bốn hàm. wildcard_in(pattern, text): True khi các mảnh của pattern giữa các dấu * đều xuất hiện trong text theo thứ tự. rule_matches(rule, url, third_party): True khi một dict quy tắc (từ bài trước) khớp với yêu cầu. build_index(rules): sắp xếp các quy tắc theo bất kỳ cách nào bạn thích để decide bỏ qua được phần lớn chúng. decide(index, url, third_party): trả về "block" hoặc "allow", với bất kỳ ngoại lệ khớp nào thắng, gọi rule_matches tối đa 20 lần mỗi yêu cầu khi đã tải 5.000 quy tắc.
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.