Hãy hình dung bộ máy regex như một người giải mê cung theo lối mò mẫm: tới ngã ba thì chọn một hướng, đi tới ngõ cụt thì quay lại thử hướng khác, cứ thế. Khi mê cung có lối ra, anh ta tìm thấy khá nhanh. Nhưng khi mê cung không có lối ra, anh ta buộc phải đi hết mọi con đường trước khi dám kết luận "chịu" — và nếu số đường đi tăng gấp đôi theo mỗi ngã rẽ, cái "chịu" ấy có thể mất hàng giờ. Toàn bộ chuyện ReDoS nằm gọn trong hình ảnh đó, và bài này định viết theo lối quen thuộc: giới thiệu nhóm, tham lam, biên, rồi kết bằng màn biểu diễn kinh điển — regex (a+)+b mười ký tự làm treo CPU.

Tôi chạy thử đoạn biểu diễn đó trên JDK 21. Nó không treo. Nó chạy hết 0,5 mili giây.

Phần cuối bài là chuyện tôi đã đào bao xa để tìm ra thứ thật sự treo được, và con số cuối cùng là 19 giây. Nhưng trước hết là bốn thứ dùng hằng ngày.

Nhóm và nhóm đặt tên

Matcher m = Pattern.compile("(\\d{4})-(\\d{2})-\\d{2}").matcher(s);

  nhóm 0=2026-07-03 1=2026 2=07
  nhóm đặt tên: nam=2026 thang=07

Nhóm 0 luôn là toàn bộ phần khớp; nhóm 1 trở đi đánh số theo thứ tự dấu mở ngoặc từ trái sang.

Đếm ngoặc là việc dễ sai và dễ hỏng: chèn thêm một nhóm ở giữa là mọi chỉ số phía sau lệch đi một, mà trình biên dịch không hề báo. Nên với regex có từ hai nhóm trở lên, hãy đặt tên:

Pattern.compile("(?<nam>\\d{4})-(?<thang>\\d{2})");
m.group("nam");

Tên phải là chữ và số, không dấu gạch dưới — (?<nam_sinh>...) sẽ ném PatternSyntaxException ngay lúc biên dịch.

Còn khi bạn cần ngoặc chỉ để nhóm chứ không để trích xuất, dùng (?:...). Nó không chiếm số thứ tự, và engine không phải lưu vị trí — vừa gọn vừa nhanh hơn một chút.

Tham lam, không tham lam, và cách thứ ba tốt hơn cả hai

  <.+>   (tham lam)      : <b>đậm</b> và <i>nghiêng</i>
  <.+?>  (không tham lam): <b>
  <[^>]+> (chính xác)    : <b>

.+ tham lam: nó nuốt tới cuối chuỗi trước, rồi lùi dần cho tới khi phần còn lại khớp được. Nên <.+> lấy trọn từ dấu < đầu tiên tới dấu > cuối cùng.

.+? không tham lam: nó lấy ít nhất có thể, rồi nới ra khi cần. Đây là phản xạ đầu tiên của phần lớn người viết, và nó cho kết quả đúng ở đây.

Nhưng cách thứ ba mới là cách tôi khuyên: [^>]+ — "mọi ký tự không phải dấu đóng". Nó diễn đạt đúng ý định, và quan trọng hơn: nó không cần quay lui. Mỗi ký tự hoặc thuộc lớp hoặc không, engine không bao giờ phải thử lại. Ghi nhớ điểm này, phần cuối bài sẽ quay lại đúng chỗ đó.

Một cách nói ngắn: . là công cụ tù. Mỗi lần định viết ., hãy hỏi "thật sự là mọi ký tự sao?" — câu trả lời thường là không.

Biên: chỗ regex khớp vào khoảng trống

  \bcat\b trong 'concatenate' : false
  \bcat\b trong 'a cat here'  : true
  ^\d+$ với chuỗi nhiều dòng  : false
  cùng vậy với MULTILINE      : true

\b không khớp ký tự nào — nó khớp ranh giới giữa ký tự từ (\w) và ký tự không phải từ. Nhờ vậy tìm được từ "cat" mà không dính "concatenate".

Cần cẩn thận với tiếng Việt: \w mặc định chỉ là [a-zA-Z0-9_], nên chữ có dấu bị coi là ký tự không-từ và \b cắt ngay giữa từ. Tìm \w+ trong chuỗi "một cái mũ":

  \w+ mặc định : [m, t, c, i, m]
  + UNICODE    : [một, cái, mũ]

Năm mảnh vụn thay vì ba từ. Muốn đúng thì bật cờ Unicode:

Pattern.compile("\\b\\w+\\b", Pattern.UNICODE_CHARACTER_CLASS);

Đây là lỗi im lặng đúng kiểu khó chịu nhất: đếm từ, tô sáng từ khoá hay kiểm tra tên đều vẫn "chạy", chỉ là ra kết quả sai với mọi chuỗi có dấu.

^ và $ mặc định là đầu và cuối cả chuỗi. Với MULTILINE, chúng thành đầu và cuối mỗi dòng. Đây là cờ hay bị quên nhất khi xử lý văn bản nhiều dòng, và triệu chứng là "regex đúng mà không khớp gì".

Còn $ có một chi tiết ít người biết: nó khớp cả ở trước ký tự xuống dòng cuối chuỗi. Cần đúng tận cùng thì dùng \z.

Thay thế: ba mức

  replaceAll  : a#b#c#
  tham chiếu  : 03/07/2026
  hàm thay thế: a[1]b[2]c[3]

Mức một là thay chuỗi thẳng. Mức hai dùng $1, $2 để tham chiếu nhóm:

s.replaceAll("(\\d{4})-(\\d{2})-(\\d{2})", "$3/$2/$1");

Mức ba — có từ Java 9 và ít được biết tới — là truyền một hàm:

m.replaceAll(kq -> kq.group() + "[" + dem.incrementAndGet() + "]");

Hàm nhận MatchResult và trả về chuỗi thay thế, nên bạn tra được cơ sở dữ liệu, đếm, hay áp logic tuỳ ý cho từng lần khớp. Trước Java 9 việc này phải viết vòng lặp appendReplacement/appendTail khá dài.

Một cái bẫy khi thay thế: chuỗi thay thế không phải văn bản thuần. Dấu $ và \ trong đó có ý nghĩa đặc biệt, nên dán dữ liệu người dùng vào là hỏng:

  replaceAll("x", "gia $5 dong")                    -> IndexOutOfBoundsException: No group 5
  replaceAll("x", quoteReplacement("gia $5 dong"))  -> gia $5 dong

Một bảng giá có chữ $5 đủ làm sập chức năng thay thế. Bọc lại bằng Matcher.quoteReplacement(...). Tương tự, ghép dữ liệu người dùng vào chính regex thì bọc bằng Pattern.quote(...).

Bây giờ tới phần regex làm treo CPU

Ví dụ mà mọi bài về ReDoS đều dùng là (a+)+b cho ăn một chuỗi toàn chữ a. Lý thuyết nghe rất thuyết phục: nhóm ngoài có thể chia chuỗi a thành vô số cách, engine phải thử hết trước khi kết luận thất bại, và số cách thử tăng gấp đôi mỗi khi thêm một ký tự.

Đây là kết quả thật trên JDK 21:

  (a+)+b   dài 20 ->   0,41 ms
  (a+)+b   dài 30 ->   0,07 ms
  (a+)+b   dài 45 ->   0,16 ms
  (a+)+b   dài 60 ->   0,24 ms

Không có bùng nổ. Không có xu hướng tăng nào cả.

Tôi không tin ngay, vì kết quả này đi ngược mọi thứ tôi từng đọc. Nên tôi thử tiếp: (a|a)*b, (x+x+)+y, ^([a-z]+)+$, (a?){25}a{25}, ((a)*)*$, mẫu email hỏng mà OWASP hay trích, và mẫu ^(([a-z])+.)+[A-Z]([a-z])+$ vốn được nêu đích danh là ví dụ ReDoS của Java. Mười lăm mẫu, cả matches() lẫn find(), độ dài đầu vào tới 60.

Mẫu chậm nhất trong toàn bộ đợt đo là 1,8 ms.

Đây không phải lời khuyên "regex an toàn rồi". Nó chỉ có nghĩa là bộ máy regex của JDK 21 xử lý được lớp mẫu lồng lượng từ trên một ký tự, và các ví dụ chép đi chép lại trong tài liệu về ReDoS đều rơi đúng vào lớp đó. Bùng nổ vẫn xảy ra — chỉ là ở chỗ khác, và bạn sắp thấy nó.

Chỗ nó thật sự bùng nổ

Sau khi không mẫu kinh điển nào tái hiện được, câu hỏi đầu tiên phải là: bộ đo của tôi có hỏng không? Một phép đo lúc nào cũng ra 0 ms thì đáng ngờ y như một phép đo lúc nào cũng ra 30 giây.

Nên tôi tìm một mẫu chắc chắn phải chậm — nhiều nhóm .* liền nhau, cho ăn chuỗi không bao giờ khớp:

Pattern.compile("(.*)(.*)(.*)(.*)(.*)(.*)x").matcher("a".repeat(120)).matches();

  3 nhóm .* , |vào|=120 ->        5,9 ms
  4 nhóm .* , |vào|=120 ->       40,9 ms
  5 nhóm .* , |vào|=120 ->      913,9 ms
  6 nhóm .* , |vào|=120 ->   19 304,9 ms

Bộ đo không hỏng. Thêm một nhóm .* vào regex làm thời gian chạy nhân lên khoảng hai mươi lần. Sáu nhóm là mười chín giây cho một chuỗi 120 ký tự — trên một luồng, chiếm trọn một nhân CPU.

Độ dài đầu vào cũng vậy, với sáu nhóm cố định:

  |vào|= 40 ->      39,2 ms
  |vào|= 60 ->     367,2 ms
  |vào|= 80 ->   1 886,3 ms
  |vào|=100 ->   6 753,3 ms
  |vào|=120 ->  19 304,9 ms

Gấp ba lần độ dài đầu vào là gần năm trăm lần thời gian chạy. Một endpoint nhận chuỗi 120 ký tự và kiểm tra bằng regex kiểu này thì mười request đồng thời là đủ hạ một máy chủ bốn nhân — không cần botnet, không cần băng thông.

Nguyên nhân vẫn đúng như lý thuyết kể: mỗi .* có thể lấy từ 0 tới toàn bộ phần còn lại, các nhóm chia nhau chuỗi theo vô số cách, và vì x không bao giờ tìm thấy nên engine phải thử hết trước khi trả về false — đúng anh giải mê cung không lối ra ở đầu bài. Chỉ là lý thuyết đó cần một mẫu mà JDK không rút gọn được, chứ không phải mẫu trong sách.

Ba cách chống, và một cách không ăn thua

Cùng regex sáu nhóm, cùng đầu vào 120 ký tự:

  tham lam thường  (.*){6}x   ->  19 176,9 ms
  không tham lam   (.*?){6}x  ->  19 727,6 ms
  chiếm hữu        (.*+){6}x  ->       0,1 ms
  nhóm nguyên tử   (?>.*){6}x ->       0,1 ms

Đổi sang không tham lam không cứu được gì — 19,7 giây, còn chậm hơn bản gốc một chút. Đây là điểm tôi thấy đáng nhớ nhất của cả bài, vì "thêm dấu hỏi cho nó khỏi tham" là phản xạ rất phổ biến. Tham lam và không tham lam chỉ khác nhau ở thứ tự thử, không khác ở số lượng phải thử. Khi kết quả là thất bại, engine duyệt hết cả hai đằng nào cũng như nhau.

Hai thứ chữa được, cùng nguyên lý:

Lượng từ chiếm hữu *+, ++, ?+ — lấy nhiều nhất có thể rồi không bao giờ nhả ra. Không nhả nghĩa là không quay lui, không quay lui nghĩa là không bùng nổ.

Nhóm nguyên tử (?>...) — khi nhóm đã khớp xong thì chốt lại, engine không được quay vào trong thử cách chia khác.

Cả hai đổi ngữ nghĩa của regex, nên đừng rắc bừa: có những mẫu cần quay lui mới khớp đúng. Nhưng với phần lớn regex dùng để kiểm tra hợp lệ, quay lui vốn không cần thiết, và chiếm hữu vừa nhanh hơn vừa an toàn hơn.

Và cách chống rẻ nhất vẫn là cách ở mục "tham lam" phía trên: thay . bằng lớp ký tự hẹp. [^>]+ không có gì để quay lui. Phần lớn regex bùng nổ được là vì có . ở chỗ lẽ ra phải cụ thể hơn.

Vài rào chắn ở tầng ứng dụng

Giới hạn độ dài đầu vào trước khi cho vào regex. Rẻ nhất, hiệu quả nhất, và chặn được cả những mẫu bạn chưa kịp phát hiện là nguy hiểm. Một if (s.length() > 200) return false; đặt trước lời gọi matches() đủ biến 19 giây thành vài mili giây.

Đừng để người dùng cung cấp regex. Nếu buộc phải — ô tìm kiếm nâng cao chẳng hạn — thì chạy nó trên luồng riêng có hạn thời gian, hoặc dùng thư viện có bộ máy tuyến tính như RE2/J.

Pattern.compile là một lần, không phải mỗi lần:

  String.matches trong vòng lặp : 42 ms
  Pattern biên dịch sẵn         : 10 ms

s.matches(re) biên dịch lại regex ở mỗi lần gọi. Trong vòng lặp mười nghìn lần, đó là chênh lệch bốn lần. Khai static final Pattern và dùng lại. Pattern an toàn luồng — cùng lý do với DateTimeFormatter ở bài java.time; chỉ Matcher mới là thứ không được chia sẻ giữa các luồng.

Tách chuỗi

  split có giới hạn : [a, b:c:d]
  splitAsStream lười: [1, 2, 3]

split(re, 2) cắt tối đa thành hai phần — rất hợp khi tách khoá=giá trị mà giá trị có thể chứa dấu bằng.

Còn tham số âm thì giữ lại các phần rỗng ở cuối, thứ mà split mặc định lặng lẽ bỏ đi:

  "a,b,,".split(",")     -> [a, b]
  "a,b,,".split(",", -1) -> [a, b, , ]

Hai phần tử chứ không phải bốn — một chỗ hay gây bất ngờ khi phân tích CSV, vì số cột đọc ra ít hơn số cột thật đúng ở những dòng có ô cuối để trống.

Pattern.splitAsStream trả về Stream và tách lười, nên với chuỗi rất dài mà bạn chỉ cần vài phần tử đầu thì nó không phải xử lý hết.

Mẫu số chung

Điều đáng mang theo khỏi bài này lớn hơn cú pháp regex: "bùng nổ theo cấp số nhân" (catastrophic backtracking) không phải tính chất của regex, mà của bộ máy thi hành nó. Bộ máy của Java, Python, JavaScript, PCRE đều là loại quay-lui — chính anh giải mê cung mò mẫm — nên chúng có thể nổ. Nhưng có một họ bộ máy khác dựng regex thành một ô-tô-mát rồi chạy tuyến tính, không thể nổ dù mẫu có xấu tới đâu:

  • regexp của Go và crate regex của Rust đều dùng RE2, chạy trong thời gian tuyến tính theo độ dài đầu vào. Cái mẫu sáu-nhóm-.* đốt 19 giây của Java, ném vào Go, trả lời tức thì. Cái giá là chúng cố tình bỏ backreference — vì đúng backreference là thứ buộc phải quay lui.
  • re của Python và regex của JavaScript là quay-lui, nên dính đúng lỗ hổng ReDoS. Sự cố sập toàn cầu của Cloudflare năm 2019 và của Stack Overflow năm 2016 đều là một regex quay-lui gặp đúng chuỗi xấu — mất vài dòng regex để hạ cả một hạ tầng.
  • Và ở mức trừu tượng nhất, đây là một sự thật của mọi tìm kiếm có quay lui: trường hợp tồi tệ nhất không phải khi có lời giải, mà khi không có — vì chỉ khi đó thuật toán mới buộc phải vét cạn cả không gian trước khi dám nói "không". SAT solver khổ nhất với các bài UNSAT cũng vì lẽ đó.

Nên câu hỏi đúng khi viết một regex có lượng từ lồng trong lượng từ không phải "nó có khớp đúng không" mà là "khi nó phải trả lời không, nó vét bao nhiêu đường" — và cách tự trả lời chỉ mất ba mươi giây. Chạy đúng dòng này:

System.out.println(Pattern.compile("(.*)(.*)(.*)(.*)(.*)(.*)x")
        .matcher("a".repeat(120)).matches());

Nó in ra false, sau khoảng hai mươi giây. Rồi thêm một dấu + vào mỗi .* cho thành .*+ và chạy lại — vẫn false, nhưng tức thì. Mỗi khi viết một regex kiểu này, hãy cho nó ăn một chuỗi dài không khớp và bấm giờ. Regex khớp được thì hầu như luôn nhanh; chỗ chết người là lúc nó phải nói "không".

Ngày mai: HttpClient có sẵn trong JDK — gọi đồng bộ và bất đồng bộ, và vì sao không cần thêm thư viện HTTP nào nữa.