ĐỊNH NGHĨA VÀ HOẠT ĐỘNG CỦA REDOS

Biểu thức chính quy (Regular Expression - Regex) lần đầu tiên được thảo luận như một khái niệm vào đầu những năm 50 của thế kỷ XX bởi các nhà toán học và những người quan tâm đến lý thuyết về khoa học máy tính. Regex không trở nên phổ biến cho đến cuối những năm 60 khi nó được sử dụng để thực hiện hai trường hợp sử dụng chính là khớp mẫu trong trình soạn thảo văn bản và phân tích từ vựng trong trình biên dịch. Ở cấp độ rất cao, hầu hết các ngôn ngữ lập trình triển khai Regex đều xây dựng những gì được gọi là Tự động hữu hạn không xác định (NFA). Các máy trạng thái này được truyền đầu vào và chúng kiểm tra từng đường dẫn khả thi cho đến khi tìm thấy sự trùng khớp hoặc khi đã kiểm tra hết các đường dẫn. Tất cả công việc trung gian đều bị loại bỏ sau mỗi lần kiểm tra được thực hiện. Mặc dù có các triển khai thay thế, NFA là loại triển khai dễ bị ReDoS vì các giải pháp thử nghiệm có thể theo cấp số nhân. Ngày nay, Regex được sử dụng rộng rãi để so khớp mẫu trong nhiều thứ từ trình duyệt, proxy, tường lửa, công cụ quét bảo mật, máy chủ web và riêng biệt trong các ứng dụng. Có thể nói, rủi ro từ chối dịch vụ ở một hoặc nhiều bước này là khá lớn.

ReDoS là một cuộc tấn công phức tạp sử dụng các thuật toán phức tạp để tạo ra hiện tượng từ chối dịch vụ bằng cách cung cấp một Regex hoặc một đầu vào khiến hệ thống mất nhiều thời gian đánh giá. Trong một cuộc tấn công ReDoS thực tế có nhiều triển khai Regex có độ phức tạp, trường hợp xấu nhất là siêu tuyến tính. Trên một số cặp Regex (đầu vào), thời gian thực hiện có thể tăng theo cấp số nhân liên quan đến kích thước đầu vào. Do đó, kẻ tấn công có thể khiến một chương trình mất nhiều thời gian xử lý bằng cách cung cấp một Regex hoặc đầu vào được thiết kế đặc biệt. Sau đó, chương trình sẽ bị chậm lại hoặc không phản hồi. Mặc dù, các Regex thường được sử dụng để tìm kiếm và phân tích dữ liệu nhưng chúng cũng có thể trở thành điểm yếu trong hệ thống nếu không được xử lý một cách cẩn thận.

Việc khớp Regex có thể được thực hiện bằng cách xây dựng một máy tự động (automaton) trạng thái hữu hạn. Regex có thể dễ dàng được chuyển đổi thành NFA, trong đó với mỗi trạng thái và ký hiệu đầu vào có thể có một số trạng thái tiếp theo có thể xảy ra. Regex cũng có thể dễ dàng chuyển đổi từ trạng thái hữu hạn sang trạng thái không xác định, đặc biệt đối với các biểu thức có trạng thái tiếp theo có thể có ứng với mỗi đầu vào được nhận. Trong những trường hợp như vậy, sau khi chuyển đổi, có một số thuật toán được sử dụng làm công cụ để có thể xác định trạng thái tiếp theo, bài viết này tập trung vào các thuật toán tồn tại nhiều vấn đề nhất:

- Công cụ thử tất cả các đường dẫn có thể cho đến khi tìm thấy một kết quả khớp hoặc tất cả các tuyến đường được thử và không thành công (quay lui). Điều này có vấn đề vì có số lượng đường dẫn n theo cấp số nhân được thực hiện cho một đầu vào có độ dài n, vì vậy trường hợp xấu nhất ta sẽ nhận được kết quả thời gian theo cấp số nhân;

- Công cụ cố gắng chuyển đổi Regex một lần nữa từ tự động hóa không xác định sang tự động hóa xác định. Điều này gây ra vấn đề đó là tùy thuộc vào đường dẫn thực thi, quá trình chuyển đổi có thể mất thời gian theo cấp số nhân để hoàn thành.

Vì vậy, ReDoS xảy ra khi một trong hai thuật toán này được áp dụng cho một Regex cụ thể. Kẻ tấn công có thể lợi dụng điều này và kích hoạt một trong hai điều kiện trên dẫn đến tăng độ phức tạp và làm cho thời gian thực thi trở nên lâu nhất.

VÍ DỤ VỀ TẤN CÔNG REDOS

Ví dụ 1. Đầu tiên, hãy xem một ví dụ đơn giản về biểu thức sau: (x+)+y

Hãy so sánh thời gian tính biểu thức (x+)+y trong hai trường hợp:

- Là đầu vào cho Regex, các chuỗi tương ứng với một mẫu nhất định được cung cấp lần lượt. Trong trường hợp này, độ dài của mỗi dòng tiếp theo lớn hơn độ dài của dòng trước đó 1;

- Đầu vào của Regex là từng chuỗi một, các chuỗi không khớp với mẫu (không có ký tự y ở cuối dòng). Trong trường hợp này, độ dài của mỗi dòng tiếp theo lớn hơn độ dài của dòng trước đó 1.

Kết quả của thí nghiệm này được trình bày tại Hình 1, 2:

Hình 1. Thời gian chạy Regex khi một chuỗi khớp với mẫu ( x+)+y

Hình 2. Thời gian chạy của Regex nếu chuỗi không khớp với mẫu (x+)+y (không có ký tự y ở cuối)

 Có thể thấy, các hàng từ tập đầu tiên sẽ được xử lý ngay lập tức. Nhưng trong trường hợp của bộ thứ hai, thời gian xử lý tăng theo cấp số nhân. Vấn đề là trong trường hợp đầu tiên, Regex tìm thấy kết quả khớp trong lần thử đầu tiên. Khi xử lý chuỗi trong trường hợp thứ hai, mọi thứ trở nên phức tạp hơn nhiều. Mẫu x+ có thể khớp với bất kỳ số lượng ký tự x nào. Mẫu (x+)+ có thể được khớp với một chuỗi bao gồm một hoặc nhiều chuỗi con khớp với x+. Do đó, có nhiều tùy chọn để khớp một chuỗi với một Regex. Số lượng của chúng phụ thuộc vào độ dài của chuỗi con bao gồm các ký tự x. Mỗi khi Regex không tìm thấy ký tự y, nó sẽ bắt đầu kiểm tra tùy chọn tiếp theo và chỉ sau khi xem qua tất cả các tùy chọn, Regex mới có thể đưa ra câu trả lời là không tìm thấy kết quả phù hợp nào.

Mặc dù vậy, không phải tất cả các Regex đều dễ bị ảnh hưởng bởi tấn công Redos. Một Regex dễ bị tổn thương nếu nó đáp ứng các điều kiện sau:

- Có hai biểu thức con, một trong số chúng được bao gồm trong biểu thức kia và một trong các bộ định lượng sau được áp dụng cho mỗi biểu thức con: '*', '+', '*?', '+?', '{...} ' (trong ví dụ trước, biểu thức con x+ được bao gồm trong (x+)+).

- Có một chuỗi có thể được so khớp với cả hai biểu thức con này (chuỗi xxxx có thể được so khớp với cả mẫu x+ và (x+)+ ).

Một ngoại lệ nhỏ là các biểu thức có dạng (\d?|....|[1-9])+. Ở đây biểu thức (\d?|....|[1-9])+ bao gồm các biểu thức con \d? và [1-9] . Chúng được liệt kê thông qua toán tử '|' và cũng có thể được khớp với cùng một chuỗi, ví dụ 111. Trong trường hợp này, việc sử dụng bộ định lượng '?' đến một trong các biểu thức con cũng dẫn đến lỗ hổng.

Ví dụ 2. Xem xét Regex sau:

newDate\((-?\d+)*\)

Mục đích của Regex này là tìm kiếm một chuỗi con như newDate(12-09-2022). Regex này không đáng tin cậy. Ngoài các chuỗi hợp lệ, nó cũng sẽ coi các chuỗi như newDate(8-911-111-11-11) và thậm chí newDate(1111111111111) là hợp lệ .

Không có lựa chọn nào được liệt kê ở trên sẽ dẫn đến hậu quả nghiêm trọng. Tuy nhiên, điều đó sẽ xảy ra nếu bạn xử lý các chuỗi như ' newDate(1111111111111' ) (Hình 3).

Hình 3. Thời gian chạy Regex khi kiểm tra các chuỗi không khớp với mẫu (không có dấu ngoặc đóng ở cuối chuỗi)

Theo ví dụ trên, tấn công Redos xảy ra là do sự hiện diện của một biểu thức con (-?\d+)* bao gồm một biểu thức con \d+. Cả hai biểu thức con đều được áp dụng bộ định lượng '*' hoặc '+' và mỗi biểu thức con có thể được so khớp với cùng một chuỗi, ví dụ: 111.

So sánh những quan sát này với các điều kiện dễ làm tổn thương Regex đã thảo luận trước đó:

- Có hai biểu thức con, một trong số chúng được bao gồm trong biểu thức kia và một trong các bộ định lượng sau được áp dụng cho mỗi biểu thức con: '*', '+', '*?', '+?', '{...} ' (vì vậy , biểu thức con \d+ được bao gồm trong (-?\d+)* );

- Có một dòng có thể được khớp với cả hai biểu thức con (dòng 1111 có thể được khớp với mẫu \d+ hoặc mẫu (-?\d+)* ).

Regex: newDate\((-?\d+)*\) đã gây ra lỗ hổng (CVE-2021-27293) trong một dự án thực tế là thư viện RestSharp.

GIẢI PHÁP PHÒNG NGỪA REDOS

Bài viết xem xét 03 cách chính để bảo vệ Regex khỏi tấn công Redos bằng cách sử dụng ví dụ về biểu thức newDate\((-?\d+)*\) gồm:

Giải pháp 1: Thêm giới hạn về thời gian cần thiết để một chuỗi được xử lý bằng Regex. Trong .NET, điều này có thể được thực hiện bằng cách đặt tham số matchTimeout khi gọi một phương thức tĩnh hoặc khởi tạo một đối tượng Regex mới.

Giải pháp 2: Sử dụng nhóm nguyên tử (?>...). Các biểu thức được đánh dấu là nhóm nguyên tử đã tắt tính năng quay lui. Do đó, trong tất cả các tùy chọn có thể, một nhóm nguyên tử sẽ luôn chỉ khớp với một chuỗi con chứa số ký tự tối đa. Mặc dù các nhóm nguyên tử là phương tiện bảo vệ đáng tin cậy chống lại sự quay trở lại mang tính thảm họa nhưng chúng phải được sử dụng một cách cẩn thận. Trong một số trường hợp, việc sử dụng nhóm nguyên tử có thể làm giảm đáng kể độ chính xác của việc đánh giá Regex.

Giải pháp 3: Viết lại Regex, thay thế biểu thức con không an toàn bằng một biểu thức an toàn. Ví dụ: để tìm một chuỗi như newDate(13-09-2022) thay vì biểu thức dễ bị tổn thương newDate\((-?\d+)*\), có thể sử dụng newDate\((\d{2} -\d{2 }-\d{4})\).

Trong tùy chọn đầu tiên, có hai biểu thức con bao gồm: (-?\d+)* và \d+. Những biểu thức con này có thể được so khớp với cùng một chuỗi con. Trong tùy chọn thứ hai, bất kỳ chuỗi con nào cũng có thể được khớp với không quá một mẫu, do việc kiểm tra bắt buộc ký tự '-' giữa các mẫu \d{...}.

KẾT LUẬN

Tấn công ReDoS là một mối đe dọa nghiêm trọng đối với các hệ thống, ứng dụng web và phần mềm, khi khai thác lỗ hổng trong các Regex để làm gián đoạn hoặc ngừng hoạt động dịch vụ. Qua việc hiểu rõ cơ chế và phương thức tấn công, chúng ta có thể nhận diện và phòng ngừa hiệu quả hơn. Các biện pháp như kiểm tra và tối ưu hóa Regex, hạn chế độ phức tạp và kích thước đầu vào cùng với việc thường xuyên cập nhật các công cụ và thư viện liên quan đều đóng vai trò quan trọng trong việc bảo vệ hệ thống. Từ đó, không chỉ giảm thiểu nguy cơ bị tấn công mà còn duy trì được sự ổn định và hiệu suất của các ứng dụng. Việc nâng cao nhận thức và áp dụng các biện pháp bảo mật thích hợp sẽ là chìa khóa để đối phó với mối đe dọa từ ReDoS trong tương lai.