Cả bài trong một trang: ý chính, sơ đồ, điểm phỏng vấn.
Regex engine trong Java: backtracking, possessive quantifier và catastrophic backtracking
1Engine backtracking chạy thế nào
java.util.regex thử nhánh theo thứ tự, ghi nhớ điểm lựa chọn, thất bại thì quay lại (backtrack) điểm gần nhất. Match đầu tiên thắng, không phải match dài nhất.
flowchart TD
A["Vị trí bắt đầu"] --> B{"Điểm lựa chọn"}
B -->|"phương án đầu"| C["So tiếp input"]
C -->|"tới cuối pattern"| D["Match"]
C -->|"thất bại"| E["Quay lại điểm gần nhất"]
E --> B
E -->|"hết phương án"| F["Dời vị trí bắt đầu"]
F --> A
2Nhánh đầu tiên thắng
Quy tắc leftmost, first alternative wins: car|carpet trên "carpet" trả "car". Engine POSIX (grep) lấy match dài nhất.
Pattern.compile("car|carpet")
.matcher("carpet and car") // [car, car]
Pattern.compile("\\b(?:car|carpet)\\b")
.matcher("carpet and car") // [carpet, car]
3Greedy, lazy, possessive
Ba loại quantifier khác nhau ở thứ tự thử và có cho nhả lại ký tự không. Possessive cắt backtracking nhưng có thể đổi nghĩa.
Loại
Cú pháp
Cách chạy
Greedy
*, +
Lấy nhiều, thất bại thì nhả dần
Lazy
*?, +?
Lấy ít, thất bại thì thêm dần
Possessive
*+, (?>…)
Lấy nhiều, không bao giờ nhả
4Engine automaton: RE2/J
Máy trạng thái theo dõi mọi trạng thái cùng lúc, đi qua input một lần nên luôn tuyến tính. Đổi lại mất backreference và lookaround.
JDK: pattern team đã review, input giới hạn độ dài.
RE2/J: người dùng tự nhập regex hoặc input lớn không tin cậy.
Cùng họ: Go regexp, Rust regex, grep mặc định.
5Catastrophic backtracking
Nổ khi một đoạn input khớp cùng phần pattern theo nhiều cách. JDK 21 ghi nhớ vòng */+ nên ví dụ kinh điển chạy tức thì, nhưng nhiều dạng vẫn nổ.
Pattern, 30 chữ a + !
JDK 21
(a+)+b, ^(\w+\s?)*$
0 ms
^(a+){2,30}$
9,7 s
^(\w+\s?){1,20}$
13,2 s
💡 Ghi nhớ
Match đầu tiên thắng: đặt nhánh dài trước hoặc neo \b.
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ốiPattern.matches("a++a", "aaa"); // false: a++ nuốt cả ba và không nhảPattern.matches("\".*+\"", "\"abc\""); // false: .*+ nuốt luôn dấu " đóngPattern.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+)* (\w bao 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ới find(). 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.
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ùng find(): .*.*=.*
Lời giải Bài 1 (đã đo trên JDK 21)
Input xấu: 30 chữ a rồ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ận john.doe@acme.com, a-b_c@x.com, và từ chối thêm a..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ản line.indexOf('=') >= 0.
Ghi nhớ
Giải thích được vì sao car|carpet trê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+)+b nhanh 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.