Chương trình học Bài 47 trên tổng số 156 · Xây một bộ chặn
Xây một bộ chặn

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 -> False

text.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_party khô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.example khớp máy chủ adco.example hoặ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.example là 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.
Đến lượt bạ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ờ.