CWE-1333: Độ phức tạp biểu thức chính quy không hiệu quả

Một số bộ máy biểu thức chính quy sử dụng cơ chế quay lui để thử các cách phân tích khác nhau khi một token không khớp. Nếu biểu thức cho phép số lần quay lui tăng theo cấp số mũ theo độ dài dữ liệu, một đầu vào dài được tạo để không khớp có thể khiến bộ máy thực hiện lượng tính toán quá lớn. Vấn đề thường phát sinh trong giai đoạn triển khai, khi các mẫu dễ viết với ký tự khớp không giới hạn được sử dụng mà không đánh giá chi phí quay lui. Hành vi này thường được gọi là ReDoS hoặc quay lui thảm họa.

Điểm yếu thường xuất hiện khi biểu thức chính quy dùng các mẫu có thể tạo ra nhiều khả năng quay lui, đặc biệt là các bộ định lượng lồng nhau hoặc các nhóm bắt giữ chồng lấn. Một số bộ máy biểu thức chính quy hỗ trợ quay lui: khi một token không khớp, bộ máy có thể quay về vị trí trước đó để thử cách phân tích khác. Rủi ro trở thành đáng kể khi số lần thử tăng theo cấp số mũ theo độ dài đầu vào, đầu vào có thể không khớp và đầu vào đủ dài. Đây là điểm yếu không phụ thuộc ngôn ngữ; bản ghi cũng nêu Go là một nền tảng áp dụng.

Hậu quả chính là ảnh hưởng đến tính sẵn sàng do tiêu thụ tài nguyên CPU. Kẻ tấn công có thể cung cấp đầu vào được tạo đặc biệt để kích hoạt quay lui quá mức, làm CPU tăng đột biến và có thể trì hoãn hoặc ngăn việc xử lý các yêu cầu hay thông điệp khác. Bản ghi phân loại tác động này là từ chối dịch vụ.

• Kiến trúc và thiết kế: Ưu tiên các bộ xử lý biểu thức chính quy không hỗ trợ quay lui, chẳng hạn bằng cách loại bỏ các bộ định lượng lồng nhau. Đây là một trong số ít biện pháp có hiệu quả cao khi biểu thức chính quy do người dùng cung cấp.
• Cấu hình hệ thống: Thiết lập giới hạn quay lui trong cấu hình của bộ triển khai biểu thức chính quy, chẳng hạn pcre.backtrack_limit của PHP, đồng thời cân nhắc giới hạn thời gian thực thi của tiến trình.
• Triển khai: Không áp dụng biểu thức chính quy lên dữ liệu đầu vào không đáng tin cậy khi có thể tránh. Khi bắt buộc phải dùng biểu thức chính quy, tránh quay lui trong biểu thức.
• Xử lý đầu vào: Giới hạn độ dài đầu vào mà biểu thức chính quy được phép xử lý.

Phân tích tĩnh tự động, thường được gọi là Kiểm thử bảo mật ứng dụng tĩnh (SAST), có thể phát hiện một số trường hợp bằng cách phân tích mã nguồn hoặc mã nhị phân đã biên dịch mà không cần thực thi. Phương pháp này thường lập mô hình luồng dữ liệu và luồng điều khiển, sau đó tìm các mẫu nguy hiểm nối nguồn dữ liệu đầu vào với các điểm xử lý biểu thức chính quy hoặc thành phần bên ngoài. Phương pháp này không nhất thiết phát hiện được mọi biểu thức có hành vi quay lui quá mức, nên cần xem xét cả cấu trúc biểu thức và giới hạn đầu vào trong quá trình đánh giá.

Các ví dụ đại diện trong bản ghi gồm:

• CVE-2020-5243: máy chủ có thể bị ReDoS qua chuỗi User-Agent được tạo đặc biệt do các nhóm bắt giữ chồng lấn gây quay lui quá mức.
• CVE-2021-21317: gói npm phân tích user-agent dễ bị ReDoS do các nhóm bắt giữ chồng lấn.
• CVE-2019-16215: bộ phân tích Markdown dùng biểu thức chính quy không hiệu quả, cho phép làm tăng mức sử dụng CPU và trì hoãn việc xử lý các thông điệp khác.
• CVE-2019-6785: một chuỗi dài trong sản phẩm quản lý phiên bản có thể gây từ chối dịch vụ do biểu thức chính quy không hiệu quả.
• CVE-2019-12041: mã JavaScript cho phép ReDoS qua chuỗi dài do quay lui quá mức.
• CVE-2015-8315: ReDoS khi phân tích thời gian.
• CVE-2015-8854: ReDoS khi phân tích tài liệu.
• CVE-2017-16021: ReDoS khi xác thực URL.

Đây là các ví dụ đại diện được bản ghi tuyển chọn, không phải danh sách đầy đủ mọi lỗ hổng.