Catastrophic backtracking trong regex là gì, và khi nào bạn không nên dùng regex?

Người phỏng vấn muốn biết bạn hiểu regex chạy thế nào bên dưới, nhận ra rủi ro với dữ liệu mình không kiểm soát, và biết đâu là giới hạn của công cụ này.

Phần lớn bộ máy regex (kể cả của JavaScript) khớp bằng cách thử một hướng, nếu hỏng thì quay lui và thử hướng khác. Với một số biểu thức, đặc biệt là biểu thức có lặp lồng trong lặp như ^(\d+\.?)+$, số hướng cần thử tăng gấp đôi cho mỗi ký tự thêm vào khi chuỗi không khớp. Đó là catastrophic backtracking: một chuỗi chỉ dài vài chục ký tự có thể làm một dòng code chạy hàng giây, hàng giờ. Khi regex chạy trên dữ liệu do người ngoài gửi, nó trở thành một lỗ hổng từ chối dịch vụ (ReDoS), và OWASP có một trang riêng về chuyện này.

Cách phòng: tránh lặp lồng hoặc hai phần lặp chồng lên nhau, viết sao cho mỗi ký tự chỉ có một cách khớp, giới hạn độ dài đầu vào trước khi chạy regex, và thử biểu thức với một chuỗi dài không khớp thay vì chỉ thử các chuỗi đúng. Ở những nơi quan trọng, có thể dùng bộ máy đảm bảo thời gian tuyến tính hoặc có giới hạn thời gian.

Còn khi nào không nên dùng regex: với cấu trúc có trạng thái hoặc lồng nhau, như tách ô CSV có ngoặc kép hay đọc HTML, một vòng lặp qua từng ký tự hoặc một thư viện đọc đúng định dạng rõ ràng và an toàn hơn. Regex hợp để chuẩn hóa từng mẩu nhỏ như số điện thoại hay ngày tháng, sau khi đã tách đúng ô.

Điểm cộng: kể một ví dụ chuẩn hóa dữ liệu bẩn bằng regex kèm báo cáo các dòng bị loại, thay vì bỏ qua lỗi âm thầm.