Đây là bài quan trọng nhất về bảo mật của cả loạt. Bạn có thể viết một regex hoàn toàn hợp lệ, chạy đúng trong mọi test, triển khai lên production — rồi một ngày ai đó gửi một chuỗi vài chục ký tự và làm treo cứng một CPU trong nhiều giây, hoặc lâu hơn. Đây không phải giả thuyết: nó là một lớp lỗ hổng có tên ReDoS (Regular expression Denial of Service), và nó đã hạ gục dịch vụ của Cloudflare, Stack Overflow và nhiều nơi khác. Gốc rễ là catastrophic backtracking — hệ quả trực tiếp của cơ chế backtracking mà phần 5 đã giải thích. Bài này (phần 6 loạt Regex) đo tận mắt sự bùng nổ theo cấp số nhân, và cho thấy vì sao đổi engine là cách chữa triệt để.

Vì sao một mẫu vô hại lại nổ

Xét mẫu (a+)+$. Nó trông ngớ ngẩn nhưng tương đương nhiều mẫu thực tế ((\w+\s?)*, (\d+)*, email regex viết ẩu...). Vấn đề là nested quantifier: một quantifier (+) lồng trong một quantifier khác (( )+). Khi chạy trên chuỗi aaaa...a! — nhiều a rồi một ký tự làm $ thất bại — engine backtracking phải thử mọi cách chia số a đó vào vòng trong và vòng ngoài:

aaaa có thể được nhóm thành (aaaa), (aaa)(a), (aa)(aa), (aa)(a)(a), (a)(a)(a)(a)... — với n ký tự a có 2^(n-1) cách phân hoạch. Vì chuỗi không khớp (do ! ở cuối), engine phải thử hết mọi cách trước khi kết luận "thất bại". Số cách là mũ theo n, nên thời gian là O(2ⁿ).

Ảnh chụp đoạn mã nền tối minh hoạ catastrophic backtracking và ReDoS một mẫu treo cả server mẫu a cộng đóng ngoặc cộng đô la nested quantifier O 2 mũ n tấn công từ chối dịch vụ, vấn đề một regex vô hại trông có thể là bom hẹn giờ mẫu a cộng cộng đô la trông duyệt như bình thường nhưng trên input độc aaaa a chấm than nhiều a rồi một ký tự không khớp đô la engine backtracking phải thử mọi cách chia các a vào vòng trong và vòng ngoài số cách chia mũ theo số a O 2 mũ n vài chục a là treo CPU, vì sao nổ nested quantifier tạo số đường mũ a cộng đóng ngoặc cộng vòng trong a cộng khớp một hoặc nhiều a vòng ngoài lặp aaaa có thể chia aaaa hoặc aaa a hoặc aa aa hoặc a a a a với n ký tự a có 2 mũ n trừ 1 cách phân hoạch khi không khớp đô la thất bại engine thử hết từng cách trước khi bỏ cuộc bùng nổ theo cấp số nhân các mẫu độc tương tự a hoặc a sao đô la chấm sao sao đô la mũ w cộng s hỏi sao đô la, đo bằng python re backtracking có ngưỡng an toàn bad bằng compile a cộng cộng đô la for n trong 16 18 20 22 24 26 28 s bằng a nhân n cộng chấm than input độc không khớp đo thời gian dừng sớm nếu quá 8 giây để không treo, đối chiếu cùng mẫu trên Go RE2 tuyến tính re MustCompile a cộng cộng đô la RE2 chấp nhận chạy khác hẳn không backtrack mô phỏng tất cả trạng thái song song số trạng thái bị chặn O n dù mẫu có nested quantifier

Hình 1: Mẫu (a+)+$ có nested quantifier; trên input aaaa...!, engine backtracking phải thử 2^(n-1) cách phân hoạch số a trước khi kết luận thất bại → O(2ⁿ); Go RE2 không backtrack nên chạy tuyến tính dù cùng mẫu.

Đo thật: nổ theo cấp số nhân, và RE2 miễn nhiễm

Mình đo python re với mẫu (a+)+$ trên 'a'*n + '!', tăng n dần, có ngưỡng dừng an toàn ở 8 giây:

Ảnh chụp bảng kết quả chạy thật ReDoS output thật go-lab mẫu a cộng cộng đô la input a nhân n cộng chấm than, một python re thời gian gấp đôi mỗi khi n cộng 1 cấp số nhân n 16 thời gian 2.66ms n 18 11.89ms gấp 4.48 lần n 20 40.01ms gấp 3.37 lần n 22 139.52ms gấp 3.49 lần n 24 553.64ms gấp 3.97 lần n 26 2213.66ms gấp 4.00 lần khoảng 4 lần mỗi bước cộng 2 bằng 2 lần mỗi cộng 1 n 28 9020.27ms gấp 4.07 lần 9 giây cho 28 ký tự a n bằng 40 sẽ mất hàng ngàn năm chỉ cần vài chục ký tự là treo CPU, hai Go RE2 cùng mẫu cùng input độc nhưng tuyến tính n 28 3.375 micro giây python mất 9 triệu micro giây RE2 nhanh hơn khoảng 2.7 triệu lần n 100 4.167 micro giây n 1000 33.542 micro giây n 10000 300.208 micro giây input gấp 10 thời gian gấp khoảng 10 tuyến tính n 100000 2.19225ms 100 nghìn a vẫn xong tức thì RE2 miễn nhiễm ReDoS đó là lý do dùng nó cho input từ người dùng

Hình 2: Chạy thật — python (a+)+$: n=16 mất 2.66ms, gấp ~4× mỗi bước +2 (tức 2× mỗi +1), n=28 mất 9020ms (9 giây cho 28 ký tự); Go RE2 cùng mẫu: n=28 chỉ 3.375µs (nhanh hơn ~2.7 triệu lần), n=100000 vẫn chỉ 2.19ms (tuyến tính).

  • Cấp số nhân là thật và tàn khốc: từ n=16 (2.66ms) tới n=28 (9020ms), mỗi lần tăng n thêm 2, thời gian gấp ~4 lần — tức gấp đôi mỗi khi thêm một ký tự a, đúng O(2ⁿ). Chỉ 28 ký tự đã mất 9 giây. Ngoại suy: n=40 sẽ mất hàng ngàn năm. Một kẻ tấn công chỉ cần dán vài chục ký tự vào một ô nhập liệu được kiểm bằng regex độc là làm nghẽn một worker.
  • RE2 cùng mẫu, cùng input, nhưng tuyến tính: Go RE2 chạy đúng mẫu (a+)+$ trên đúng input độc — n=28 chỉ mất 3.375µs, nhanh hơn python ~2.7 triệu lần. Và nó scale tuyến tính: n=100000 (gấp 3500 lần cái làm python treo 9 giây) vẫn xong trong 2.19ms. RE2 không backtrack — nó mô phỏng tất cả trạng thái song song với số trạng thái bị chặn (phần 7), nên miễn nhiễm ReDoS hoàn toàn.

Đánh đổi cần cân nhắc

Đổi sang RE2 là cách chữa triệt để nhất — nhưng mất backreference/lookaround. Nếu regex của bạn chạy trên đầu vào không tin cậy, dùng engine tuyến tính (Go regexp, thư viện RE2, Rust regex) loại bỏ ReDoS tận gốc — không mẫu nào làm nó nổ được. Cái giá là mất backreference (phần 5) và lookaround (phần 8). Với phần lớn việc kiểm tra/trích xuất input, đây là đánh đổi đáng: an toàn quan trọng hơn vài tính năng cú pháp.

Nếu buộc dùng engine backtracking, có ba lớp phòng thủ. (1) Timeout: đặt giới hạn thời gian cho mỗi lần khớp (nhiều ngôn ngữ hỗ trợ, ví dụ .NET có Regex timeout). (2) Giới hạn độ dài input trước khi cho vào regex — ReDoS cần input đủ dài để nổ. (3) Viết mẫu không mơ hồ: tránh nested quantifier và các nhánh chồng lấp ((a|a)*), dùng atomic group (?>...) hoặc possessive quantifier a++ (phần 11) để chặn backtracking. Ba lớp này bổ sung nhau, không thay thế nhau.

Test thường không bắt được ReDoS. Input làm regex nổ hiếm khi giống dữ liệu "bình thường" trong test — nó là chuỗi được thiết kế đặc biệt để không khớp sau khi đã tiêu tốn backtracking. Nên một regex qua hết mọi unit test vẫn có thể là bom. Dùng công cụ phân tích tĩnh (như redos-detector, hoặc kiểm mẫu có nested quantifier) và fuzz với input bệnh lý để phát hiện trước khi production.

Ba ý mang về

  1. Catastrophic backtracking gây bùng nổ mũ: đo thật (a+)+$ trên 'a'*n+'!' làm python re mất 2.66ms ở n=16 nhưng 9020ms ở n=28 — gấp đôi mỗi khi thêm một ký tự (O(2ⁿ)); nested quantifier tạo 2^(n-1) đường backtrack khi chuỗi không khớp.
  2. RE2 miễn nhiễm ReDoS: đo thật cùng mẫu cùng input độc, Go RE2 chỉ mất 3.375µs ở n=28 (nhanh hơn ~2.7 triệu lần) và 2.19ms ở n=100000 — tuyến tính, không backtrack.
  3. Phòng ReDoS: dùng engine tuyến tính (RE2/Rust regex) cho input không tin cậy (đánh đổi mất backreference/lookaround); nếu buộc backtracking thì timeout + giới hạn độ dài input + tránh nested quantifier (atomic/possessive); và nhớ test thường không bắt được ReDoS.

Nguồn

Phần sau ta mổ xẻ chính cỗ máy đã miễn nhiễm ReDoS ở trên: RE2 và Go regexp — vì sao nó chạy tuyến tính, nó đánh đổi những gì, và khi nào bạn nên chọn nó thay vì engine backtracking.