Cụm bài Regex: 1. Cú pháp, Java API và bài tập validate · 2. Bài tập: cấu hình mạng, log sang CSV, lookbehind, dòng trùng · 3. Engine, backtracking và catastrophic backtracking · 4. ReDoS trong Java: sự cố và phòng thủ
Một ô “họ tên” 40 ký tự có thể làm một thread ăn 100% CPU nhiều giây, không exception, không log; vài chục request như thế làm cạn thread pool. Đó là ReDoS (Regular expression Denial of Service), gốc ở cách engine regex của Java (và JavaScript, Python, PCRE) chạy: backtracking. Đọc xong, bạn hiểu engine chạy thế nào, nhận ra và sửa được pattern nguy hiểm; cú pháp ở bài 1, sự cố thật và phòng thủ (timeout tự làm, giới hạn input, RE2/J) ở bài 4.
1. Engine backtracking chạy thế nào
Ý chính: engine đi từ trái sang phải, ghi nhớ mọi điểm lựa chọn, thất bại thì quay lại điểm gần nhất; lối đầu tiên tới cuối pattern là match.
1.1. Từng ký tự, từ trái sang phải
Ý chính: java.util.regex duyệt cây lựa chọn theo chiều sâu (sách hay gọi là “NFA engine”) và nhận phương án đầu tiên thành công, nên alternation chọn nhánh đầu tiên khớp, không chọn nhánh dài nhất.
- Bắt đầu ở vị trí 0, so từng phần tử pattern với input.
- Gặp điểm lựa chọn (nhánh
|, quantifier lấy thêm hay bớt): chọn phương án đầu, ghi nhớ phần còn lại. - Thất bại thì quay lại (backtrack) điểm lựa chọn gần nhất, thử phương án kế.
- Hết phương án thì dời điểm bắt đầu sang 1, 2, … (việc
find()làm). - Phương án đầu tiên tới cuối pattern là match, không phải match “dài nhất”.
Bước 5 giải thích ví dụ car|carpet của slide:
Pattern.compile("car|carpet").matcher("carpet and car").results().map(MatchResult::group).toList();
// [car, car]
Pattern.compile("\\b(?:car|carpet)\\b").matcher("carpet and car").results().map(MatchResult::group).toList();
// [carpet, car]
Đây là quy tắc leftmost, first alternative wins; engine POSIX (grep, awk) theo leftmost-longest và trả “carpet”. Sửa trong Java: đặt nhánh dài trước (carpet|car), hoặc thêm \b hai đầu như slide: nhánh car gặp ranh giới giữa “r” và “p” (cả hai là \w) nên thất bại, engine quay sang carpet.
1.2. Backtracking qua một ví dụ
Ý chính: nhánh thất bại thì engine quay về điểm lựa chọn gần nhất, thử nhánh kế. Trạng thái để quay lại nằm trên call stack.
Pattern \bapple(?:past(?:ry|e)|pie)\b: với “applepaste”, ry thất bại ở “e” nên engine quay lại thử e; với “applepie”, past thất bại ở “i” nên engine thử pie. Kết quả [applepaste, applepie].
flowchart LR
S[apple] --> P[past]
S --> Q[pie]
P --> R[ry]
P --> E[e]
R -->|thất bại, quay lại| E
E --> B[ranh giới từ]
Q --> B
Engine là các node gọi đệ quy, nên “đang ở đâu, nhánh nào” nằm trên call stack (bài 4 nói về StackOverflowError).
Từng bước trên “Twenty popular recipes to make applepaste”
Input: “Twenty popular recipes to make applepaste” và “Popular applepie recipe”. Bỏ qua các vị trí bắt đầu thất bại ngay ở \ba (đa số thất bại ở ký tự đầu nên rất rẻ). Với “applepaste”:
| Bước | Phần pattern | Input còn lại | Kết quả |
|---|---|---|---|
| 1 | \b rồi apple |
applepaste | khớp 5 ký tự |
| 2 | nhánh 1: past |
paste | khớp “past” |
| 3 | nhánh con 1: ry |
e | “e” khác “r”, thất bại, quay lại điểm chọn gần nhất |
| 4 | nhánh con 2: e |
e | khớp |
| 5 | \b |
(hết dòng) | khớp, match là “applepaste” |
Với “applepie”: apple khớp, nhánh 1 past thất bại ngay ở “i” so với “a”, engine quay lại thử nhánh 2 pie, khớp, rồi \b khớp.
1.3. Greedy, lazy, possessive và atomic group
Ý chính: ba loại quantifier khác nhau ở thứ tự thử và có cho quay lại không. Possessive và atomic group cắt hẳn backtracking, nhưng có thể làm pattern không khớp nữa.
| Loại | Cú pháp | Cách chạy | <.+> trên <b>bold</b> |
|---|---|---|---|
| Greedy | *, +, ?, {n,m} |
lấy nhiều nhất, thất bại thì nhả dần từng ký tự | một match: <b>bold</b> |
| Lazy | *?, +?, ?? |
lấy ít nhất, thất bại thì lấy thêm từng ký tự | <b>, </b> |
| Possessive | *+, ++, ?+ |
lấy nhiều nhất và không bao giờ nhả |
Cả hai đều có thể backtrack nhiều. Tốt hơn là nói đúng ý: <[^>]+> (mọi ký tự trừ >), không còn chỗ để quay lại. Atomic group (?>...) khớp xong thì vứt mọi điểm lựa chọn bên trong; X*+ tương đương (?>X*).
Pattern.matches("a+a", "aaa"); // true: a+ nhả lại một "a" cho a cuối
Pattern.matches("a++a", "aaa"); // false: a++ nuốt cả ba và không nhả
Pattern.matches("\".*+\"", "\"abc\""); // false: .*+ nuốt luôn dấu " đóng
Pattern.matches("\"[^\"]*+\"", "\"abc\""); // true
2. Hai họ engine: backtracking và automaton
Ý chính: engine automaton đi qua input đúng một lần nên luôn tuyến tính; cái giá là mất backreference và lookaround.
Automaton (Thompson NFA, DFA dựng lười): máy trạng thái theo dõi cùng lúc mọi trạng thái có thể, thời gian O(độ dài pattern × độ dài input). Đại diện: RE2 (C++, Google), RE2/J (bản Java), regexp của Go, crate regex của Rust, chế độ mặc định của grep.
Bị bỏ: backreference (\1), lookahead/lookbehind, possessive và atomic group (cũng không cần). Rust có \b và anchor, không có lookaround tổng quát.
3. Catastrophic backtracking
Ý chính: match thất bại thì engine phải thử hết mọi cách khớp; pattern cho nhiều cách chia cùng một đoạn input thì số cách tăng theo hàm mũ (hoặc đa thức bậc cao).
3.1. Vì sao có pattern chạy theo hàm mũ
Ý chính: dấu hiệu là có hai cách khác nhau để một đoạn input khớp cùng một phần pattern.
Ví dụ ^(a+)+$ trên n chữ a rồi !: để kết luận thất bại, engine thử mọi cách chia n chữ a thành các nhóm a+ ((aaaa), (aaa)(a), (aa)(aa), …): 2^(n-1) cách.
Ba dạng hay gặp:
- Quantifier lồng nhau mà phần trong và ngoài cùng khớp một ký tự:
(a+)+,(\w*)*,(\w+\s?)*. - Alternation chồng lấn:
(a|aa)+,(\d+|\w+)*(\wbao gồm\d). - Các phần liền kề chồng lấn kèm điểm thất bại ở cuối:
.*.*=.*,\s+$vớifind(). Ra đa thức (n², n³), nhưng input vài chục KB cũng đủ treo.
3.2. Đo trên JDK 21: một bất ngờ
Ý chính: JDK hiện đại ghi nhớ vòng lặp */+ của group nên nhiều ví dụ kinh điển chạy tức thì; lặp có giới hạn, backreference, lồng ba tầng và dạng đa thức vẫn nổ.
Đo trên JDK 21 (Apple Silicon, java File.java, vòng lặp thô, không JMH): chỉ xem như độ lớn.
- 0 ms tới n = 30 (input
"a".repeat(n) + "!"):(a+)+b,^(\w*)*$(ví dụ của slide),(a|aa)+b,^(\w+\s?)*$. Từ JDK 9 (theo mình biết) engine có memoization: biết “vòng lặp bắt đầu ở vị trí i thì thất bại” rồi thì không thử lại. - Vẫn hàm mũ:
^(a+){2,30}$,^(a+)+\1$,((a+)+)+$, và hai pattern form đăng ký dùng{1,20}(10 đến 16 giây ở n = 30). Thêm hai ký tự, thời gian nhân khoảng bốn: đúng dáng 2^n. - Đa thức (memoization không giúp):
.*.*=.*mất 50–87 s với 5.000 ký tự;\s+$mất 630 ms với 20.000 khoảng trắng.
Bảng đo đầy đủ trên JDK 21
Pattern kinh điển, input "a".repeat(n) + "!":
| Pattern | n = 20 | n = 26 | n = 30 |
|---|---|---|---|
(a+)+b |
0 ms | 0 ms | 0 ms |
^(\w*)*$ (ví dụ của slide) |
0 ms | 0 ms | 0 ms |
(a|aa)+b |
0 ms | 0 ms | 0 ms |
^(\w+\s?)*$ |
0 ms | 0 ms | 0 ms |
Pattern vẫn nổ trên JDK 21:
| Pattern | n = 20 | n = 24 | n = 26 | n = 28 | n = 30 |
|---|---|---|---|---|---|
^(a+){2,30}$ (lặp có giới hạn) |
9 ms | 152 ms | 622 ms | 2,4 s | 9,7 s |
^(a+)+\1$ (có backreference) |
12 ms | 173 ms | 692 ms | 2,8 s | 11,4 s |
((a+)+)+$ (lồng ba tầng) |
44 ms | 745 ms | 3,1 s | ||
^([a-zA-Z0-9]+[._-]?){1,20}@[a-z]+\.com$ |
18 ms | 258 ms | 1,0 s | 4,1 s | 15,7 s |
^(\w+\s?){1,20}$ |
16 ms | 219 ms | 869 ms | 3,4 s | 13,2 s |
Hai dòng cuối là pattern “trông bình thường” của form đăng ký: người viết thêm {1,20} “cho an toàn” và đẩy pattern ra khỏi vùng memoization bảo vệ.
Dạng đa thức (input n ký tự x, hoặc n khoảng trắng rồi x, dùng find()):
| Pattern | n = 1.000 | n = 5.000 | n = 20.000 |
|---|---|---|---|
.*.*=.* |
0,5–0,7 s | 50–87 s | (bỏ, quá lâu) |
\s+$ |
6 ms | 76 ms | 630 ms |
Bài tập
Bài 1: Sửa ba pattern dễ tổn thương
Đề: với mỗi pattern đang chạy trong service, chỉ ra input xấu, giải thích vì sao chậm, viết bản sửa giữ đúng ý nghĩa.
- Validate email nội bộ:
^([a-zA-Z0-9]+[._-]?){1,20}@[a-z]+\.com$ - Phát hiện khoảng trắng thừa ở cuối comment, dùng
find():\s+$ - Lọc dòng cấu hình có dạng
key=value, dùngfind():.*.*=.*
Lời giải Bài 1 (đã đo trên JDK 21)
- Input xấu: 30 chữ
arồi!. Group[a-zA-Z0-9]+[._-]?có dấu phân cách tuỳ chọn, nên một dãy chữ liền nhau chia được thành nhiều lần lặp theo vô số cách;{1,20}lại không được memoization bảo vệ. Đo được 15,7 s. Bản sửa^[a-zA-Z0-9]+(?:[._-][a-zA-Z0-9]+)*@[a-z]+\.com$bắt buộc dấu phân cách giữa hai khúc chữ, chỉ còn một cách chia: 0 ms. Nó vẫn nhậnjohn.doe@acme.com,a-b_c@x.com, và từ chối thêma..b@x.com,.a@x.com, chặt hơn một cách hợp lý. Cần giới hạn 20 khúc thì kiểm tra độ dài chuỗi riêng. - Input xấu: 20.000 khoảng trắng rồi
x. Từ mỗi vị trí khoảng trắng,\s+nuốt hết dãy rồi$thất bại: O(n²), đo được 630 ms. Sửa:(?<!\s)\s+$chỉ cho bắt đầu ở khoảng trắng đầu tiên của dãy (0 ms), hoặc bỏ regex:!s.equals(s.stripTrailing()). - Input xấu: một dòng 5.000 ký tự không có
=. Ba.*chia nhau cùng đoạn input ở mọi vị trí bắt đầu: O(n³), đo được 87 s. Sửa:^[^=]*=.*, hoặc đơn giảnline.indexOf('=') >= 0.
Ghi nhớ
- Giải thích được vì sao
car|carpettrên “carpet” trả “car”, và hai cách sửa. - Phân biệt được greedy, lazy, possessive; biết khi nào possessive đổi nghĩa.
- Biết khi nào chọn RE2/J, và mất gì khi chọn.
- Nhận ra ba dạng pattern gây catastrophic backtracking và sửa bằng cách bỏ sự mơ hồ.
- Giải thích được vì sao
(a+)+bnhanh trên JDK 21 mà^(\w+\s?){1,20}$vẫn nổ.
Câu hỏi phỏng vấn
Mid
Greedy, lazy và possessive quantifier khác nhau thế nào?
Greedy lấy nhiều rồi nhả dần, lazy lấy ít rồi thêm dần, possessive lấy nhiều và không bao giờ nhả.
Greedy và lazy cho cùng tập match có thể có nhưng khác thứ tự thử, nên khác match được chọn (<.+> so với <.+?>). Possessive có thể đổi kết quả (".*+" không bao giờ khớp) nhưng cắt hẳn backtracking.
Vì sao car|carpet trên “carpet” trả về “car”?
Vì engine backtracking của Java thử nhánh theo thứ tự và nhận nhánh đầu tiên dẫn tới match; nó không tìm match dài nhất.
Engine POSIX theo leftmost-longest thì trả “carpet”. Sửa: đặt nhánh dài trước (carpet|car) hoặc neo bằng \b(?:car|carpet)\b.
Catastrophic backtracking là gì? Nhận ra một pattern nguy hiểm thế nào?
Là khi số đường engine phải thử tăng theo hàm mũ (hoặc đa thức bậc cao) theo độ dài input, thường khi match thất bại ở cuối.
Dấu hiệu: một đoạn input khớp cùng một phần pattern theo nhiều cách: quantifier lồng nhau ((a+)+, (\w+\s?)*), alternation chồng lấn ((a|aa)+, (\d+|\w+)*), hoặc .* liền nhau (.*.*=.*). Sửa bằng cách bỏ sự mơ hồ: lớp ký tự phủ định, dấu phân cách bắt buộc, possessive hoặc atomic group.
Atomic group (?>...) dùng để làm gì?
Để chặn backtracking vô ích: group đã khớp xong thì engine vứt mọi điểm lựa chọn bên trong, không quay vào thử cách khác.
X*+ chính là (?>X*). Đổi lại, pattern có thể không khớp nữa nếu phần sau cần lấy lại ký tự từ group, nên chỉ dùng khi ranh giới đã rõ.
Senior
RE2 khác java.util.regex ở đâu? Khi nào bạn chọn RE2/J?
RE2 dựng automaton và đi qua input một lần, nên luôn tuyến tính và không thể bị ReDoS; đổi lại không có backreference và lookaround.
Mình chọn RE2/J khi pattern hoặc input đến từ bên ngoài: người dùng tự nhập regex để tìm kiếm hay đặt rule, WAF, dữ liệu import không tin cậy. Pattern nội bộ đã review, input giới hạn độ dài thì engine của JDK là đủ.
Ví dụ ReDoS trong sách như (a+)+b chạy rất nhanh trên JDK 21 của bạn. Vậy Java đã miễn nhiễm ReDoS chưa?
Chưa. JDK hiện đại chỉ ghi nhớ vòng lặp group */+, nên các ví dụ kinh điển không tái hiện, nhưng nhiều dạng khác vẫn nổ.
Lặp có giới hạn ((X+\s?){1,20}), backreference, lồng ba tầng vẫn là hàm mũ; .*.*=.* hay \s+$ với find() vẫn bậc hai, bậc ba. Mình đo được 13 giây cho ^(\w+\s?){1,20}$ với 30 ký tự. Phải test đúng pattern của mình với input xấu, hoặc dùng SonarQube hay CodeQL để phát hiện.
Từ vựng tiếng Anh
| Term | Phát âm | Nghĩa | Ví dụ câu tiếng Anh dùng trong phỏng vấn |
|---|---|---|---|
| backtracking | /ˈbækˌtrækɪŋ/ | quay lui | “A backtracking engine tries one path at a time and goes back when it fails.” |
| catastrophic backtracking | /ˌkætəˈstrɒfɪk ˈbækˌtrækɪŋ/ | quay lui bùng nổ | “Nested quantifiers caused catastrophic backtracking on a 30-character input.” |
| possessive quantifier | /pəˈzesɪv ˈkwɒntɪfaɪər/ | quantifier không nhả lại | “A possessive quantifier never gives characters back.” |
| atomic group | /əˈtɒmɪk ɡruːp/ | nhóm nguyên tử | “An atomic group discards its backtracking positions once it has matched.” |
| memoization | /ˌmeməʊaɪˈzeɪʃn/ | ghi nhớ kết quả đã tính | “Modern JDKs memoize failed loop positions for star and plus.” |
| linear time | /ˈlɪniər taɪm/ | thời gian tuyến tính | “RE2 guarantees linear time in the size of the input.” |
| ambiguity | /ˌæmbɪˈɡjuːəti/ | sự mơ hồ (nhiều cách khớp) | “The fix removes the ambiguity, so each input has exactly one way to match.” |
| leftmost-longest | /ˈleftməʊst ˈlɒŋɡɪst/ | quy tắc chọn match dài nhất của POSIX | “POSIX engines use leftmost-longest, Java uses the first alternative that works.” |
| polynomial | /ˌpɒliˈnəʊmiəl/ | đa thức | “Three adjacent dot-stars make the cost polynomial, roughly cubic.” |
Ghi chép dựa trên khoá Advanced Backend (Ronin Engineer), viết lại theo cách hiểu của mình.