Có một tính năng regex trông vô hại nhưng thực ra chạm tới ranh giới sâu nhất của lý thuyết tính toán: backreference (\1, \2...). Với nó, bạn viết được những mẫu "thông minh" như tìm từ bị gõ lặp hai lần hay khớp thẻ đóng đúng với thẻ mở. Nhưng cái giá phải trả không phải chuyện cú pháp — mà là: backreference khiến regex không còn là "regular" theo nghĩa toán học, và hệ quả trực tiếp là engine buộc phải dùng backtracking (mở đường cho ReDoS ở phần 6), còn các engine tuyến tính như RE2 (phần 7) thì từ chối hỗ trợ nó hoàn toàn. Bài này (phần 5 loạt Regex) đo thật cả hai mặt: sức mạnh của backreference trong Python, và sự từ chối thẳng thừng của Go.

Backreference: khớp lại đúng cái đã bắt

Khi bạn đặt một phần mẫu trong ngoặc (...), engine bắt (capture) đoạn văn bản khớp được vào một nhóm đánh số 1, 2, 3... Một backreference \1 sau đó nghĩa là: "khớp lại đúng chuỗi văn bản mà nhóm 1 đã bắt" — không phải khớp cùng mẫu, mà khớp đúng nội dung đã thấy. Vài ví dụ:

  • (\w+)\s+\1 — bắt một từ, rồi đòi đúng từ đó xuất hiện lại: tìm từ gõ lặp như the the.
  • <(\w+)>.*?</\1> — bắt tên thẻ, rồi đòi thẻ đóng </...> mang đúng tên đó: <b>...</b> khớp, <b>...</i> thì không.
  • (['"]).*?\1 — bắt dấu mở (nháy đơn hoặc kép), rồi đòi dấu đóng đúng loại đã mở.

Điểm mấu chốt: backreference đòi engine nhớ một chuỗi độ dài tùy ý đã khớp trước đó, để so lại sau.

Ảnh chụp đoạn mã nền tối minh hoạ backreference khi regex không còn regular nữa slash 1 slash 2 nhớ cái đã bắt buộc backtracking RE2 từ chối, backreference khớp lại đúng chuỗi mà nhóm đã bắt ngoặc tròn bắt một chuỗi vào nhóm 1 slash 1 sau đó đòi khớp đúng chuỗi ấy không phải cùng kiểu mà đúng y nguyên văn bản đã bắt nhóm w cộng slash s cộng slash 1 từ lặp đôi the the on on thẻ nhỏ hơn w cộng lớn hơn chấm sao hỏi nhỏ hơn gạch slash 1 lớn hơn thẻ đóng phải trùng thẻ mở ngoặc nháy đơn nháy kép chấm sao hỏi slash 1 dấu đóng phải trùng dấu mở, vì sao điều này phá vỡ lý thuyết regular regex thuần tương đương máy trạng thái hữu hạn bộ nhớ cố định nhưng chuỗi lặp lại chính nó cần nhớ chuỗi đã bắt độ dài tùy ý ngôn ngữ w w hay a mũ n b mũ n không phải ngôn ngữ regular bổ đề bơm nên backreference mạnh hơn regular không dùng DFA hữu hạn được nên engine buộc phải backtracking thử và quay lui, hệ quả engine tuyến tính RE2 không hỗ trợ nó python re PCRE Perl Java có backreference dùng backtracking Go regexp RE2 grep -E cơ bản không vì cam kết tuyến tính err bằng regexp Compile nhóm w cộng slash s cộng slash 1 Go sẽ báo lỗi đó là đánh đổi có chủ đích không phải thiếu sót chi tiết phần 07

Hình 1: Backreference \1 khớp lại đúng chuỗi nhóm đã bắt (từ lặp, thẻ mở-đóng, nháy); vì đòi "nhớ chuỗi độ dài tùy ý" nên vượt khỏi máy trạng thái hữu hạn (ngôn ngữ {w w} không phải regular), buộc engine backtracking, và RE2 từ chối hỗ trợ.

Vì sao "không còn regular"

Đây là chỗ lý thuyết ngôn ngữ hình thức bước vào. Một biểu thức regular thuần (theo định nghĩa toán học) tương đương một máy trạng thái hữu hạn — bộ nhớ cố định, không phụ thuộc độ dài input. Nhưng "một chuỗi lặp lại chính nó" (ww, với w bất kỳ) không thể nhận diện bằng bộ nhớ cố định: để so nửa sau với nửa đầu, bạn phải nhớ nửa đầu, mà nửa đầu dài tùy ý. Ngôn ngữ {ww} (giống aⁿbⁿ quen thuộc) không phải ngôn ngữ regular — điều này chứng minh được bằng bổ đề bơm (pumping lemma).

Nên khi một "regex" có backreference, nó mạnh hơn lớp ngôn ngữ regular. Không có DFA hữu hạn nào biểu diễn được nó, và engine buộc phải dùng cơ chế thử-và-quay-lui (backtracking): thử một khả năng bắt của nhóm, đi tiếp, nếu \1 không khớp thì quay lui thử khả năng khác. Chính cơ chế backtracking bắt buộc này là mầm mống của thảm họa hiệu năng ở phần 6.

Đo thật: Python làm được, Go RE2 từ chối

Ảnh chụp bảng kết quả chạy thật backreference output thật go-lab python re vs Go regexp RE2, một python nhóm b w cộng slash s cộng slash 1 b bắt đúng từ lặp đôi input the the cat sat on on the mat mat bắt từ lặp ba kết quả the on mat slash 1 khớp lại đúng từ vừa bắt, hai python thẻ đóng phải trùng thẻ mở nháy phải trùng nháy input b dam trên b i nghieng trên i b loi trên b nhỏ hơn w cộng lớn hơn chấm sao hỏi nhỏ hơn gạch slash 1 lớn hơn ba kết quả b i b thẻ đóng slash 1 đòi đúng thẻ đã mở ngoặc nháy chấm sao hỏi slash 1 dấu đóng bằng dấu mở nháy kép xin chao nháy kép khớp mở nháy kép mà đóng nháy đơn không slash 1 thất bại nháy đơn don nháy đơn khớp, ba Go RE2 từ chối slash 1 ngay khi biên dịch lỗi thật regexp Compile nhóm w cộng slash s cộng slash 1 lỗi error parsing regexp invalid escape sequence slash 1 regexp Compile thẻ w cộng chấm sao slash 1 lỗi tương tự đối chiếu regexp Compile w cộng slash s cộng w cộng err bằng nil không backref biên dịch OK RE2 từ chối slash 1 vì không thể giữ cam kết tuyến tính với backreference

Hình 2: Chạy thật — python (\b\w+)\s+\1\b bắt ['the','on','mat']; <(\w+)>.*?</\1> cho ['b','i','b']; ([\'"]).*?\1 khớp "..." và '...' nhưng không khớp khi mở " đóng '; Go regexp.Compile với \1 báo invalid escape sequence: \1, còn mẫu không backreference cho err=`.

  • Python bắt từ lặp và thẻ khớp: (\b\w+)\s+\1\b trên the the cat sat on on the mat mat cho đúng ['the','on','mat'] — mỗi từ bị gõ đôi. <(\w+)>.*?</\1> cho ['b','i','b']: mỗi thẻ đóng khớp đúng thẻ mở. Và ([\'"]).*?\1 khớp "xin chao" (mở " đóng ") và 'don', nhưng không khớp "xin chao' — vì \1 đòi dấu đóng đúng là ", không phải '. Không có backreference thì không cách nào diễn đạt các ràng buộc "phải trùng nhau" này.
  • Go RE2 từ chối thẳng: regexp.Compile((\w+)\s+\1) trả lỗi thật error parsing regexp: invalid escape sequence: \1``. RE2 không có khái niệm backreference nên coi \1 là escape không hợp lệ. Để đối chiếu, mẫu không backreference (\w+)\s+\w+ biên dịch bình thường (err=<nil>). Đây không phải thiếu sót — đó là đánh đổi có chủ đích để giữ cam kết chạy tuyến tính (phần 7).

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

Backreference tiện, nhưng thường là dấu hiệu bạn cần một parser. Dùng <(\w+)>.*?</\1> để khớp một cặp thẻ phẳng thì ổn; nhưng nếu dữ liệu có thẻ lồng (<b><b>...</b></b>), backreference vẫn bó tay vì không đếm được độ sâu (giới hạn cùng loại với phần 2). Khi ràng buộc "phải trùng nhau" bắt đầu chồng lên "phải lồng đúng", đó là lúc bỏ regex mà dùng parser thật.

Backreference mở cửa cho ReDoS. Vì buộc backtracking, một mẫu có backreference (hoặc chỉ cần backtracking nói chung) có thể bị đầu vào độc làm bùng nổ thời gian mũ — chủ đề chính của phần 6. Nếu bạn chạy regex trên đầu vào từ người dùng (biểu mẫu, request), cân nhắc dùng engine tuyến tính (RE2) và chấp nhận mất backreference, đổi lấy an toàn.

\1 khi thay thế khác \1 khi khớp. Trong nhiều công cụ (sed, re.sub), \1 ở phần thay thế nghĩa là "chèn lại nhóm 1 đã bắt" — đó là chuyện bình thường, không liên quan tính regular và không cần backtracking (chỉ là dán lại text). Đừng nhầm hai vai trò: \1 trong mẫu là backreference (phá vỡ regular), \1 trong chuỗi thay thế chỉ là tham chiếu nhóm để nội suy (phần 10 sẽ nói kỹ).

Ba ý mang về

  1. Backreference khớp lại đúng chuỗi đã bắt: đo thật (\b\w+)\s+\1\b bắt từ lặp ['the','on','mat'], <(\w+)>.*?</\1> khớp thẻ đóng đúng thẻ mở ['b','i','b'], và ([\'"]).*?\1 đòi dấu đóng trùng dấu mở — những ràng buộc "phải trùng nhau" không viết được nếu thiếu nó.
  2. Nó khiến regex "không còn regular": "nhớ chuỗi độ dài tùy ý" vượt khỏi máy trạng thái hữu hạn ({ww} không phải ngôn ngữ regular theo bổ đề bơm), nên engine buộc phải backtracking — mầm mống của ReDoS.
  3. Engine tuyến tính từ chối nó: đo thật Go RE2 trả invalid escape sequence: \1`` khi biên dịch, trong khi mẫu không backreference cho err=<nil> — đánh đổi có chủ đích để giữ tuyến tính; nếu chạy regex trên đầu vào người dùng, cân nhắc mất backreference để đổi lấy an toàn.

Nguồn

Phần sau ta đo tận mắt mặt tối của backtracking: catastrophic backtracking và ReDoS — một mẫu tưởng vô hại như (a+)+$ gặp đúng input độc có thể treo cả CPU, và ta sẽ đo thời gian nổ theo cấp số nhân.