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.
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. 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.
Thử 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ì.
Hai lần chạy đó là toàn bộ nội dung nửa sau của bài, và là lý do tôi khuyên: mỗi khi viết một regex có lượng từ lồng trong lượng từ, 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 trả lờ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.
