Quét 20 thư viện Python phổ biến: Phát hiện các mẫu Regex nguy hiểm gây sập hệ thống

Vào lúc 13:42 UTC ngày 2 tháng 7 năm 2019, một kỹ sư của Cloudflare đã thực hiện thay đổi đối với bộ quy tắc biểu thức chính quy (regex) được sử dụng bởi Tường lửa ứng dụng web (WAF) của họ. Chỉ trong vòng chưa đầy ba phút, lượng lưu lượng truy cập toàn cầu đã giảm mạnh 80%. Tải trên tất cả các CPU phục vụ HTTP trong mạng của họ đã chạm mốc 100%.

Nguyên nhân là do một biểu thức chính quy nhằm phát hiện các cuộc tấn công XSS, chứa mẫu .*(?:.*=.*). Mẫu này bao gồm hai lượng từ sử dụng .* trên cùng một lớp ký tự. Đó chính là kết quả của một sự cố ReDoS (Regular Expression Denial of Service) trong môi trường sản xuất thực tế.

Điều này khiến tôi tò mò muốn biết các mẫu nguy hiểm như vậy xuất hiện thường xuyên thế nào trong các thư viện Python mà chúng ta sử dụng hàng ngày.

Cơ chế hoạt động của ReDoS

Biểu thức chính quy hoạt động bằng cách cố gắng tìm tất cả các cách để khớp một mẫu với một chuỗi. Về nguyên tắc, điều này hoạt động tốt vì bộ khớp sẽ tìm thấy kết quả hoặc loại bỏ các cách không khả thi rất nhanh. Rắc rối phát sinh khi bạn thiết kế một mẫu cho phép các ký tự đầu vào được tiêu thụ bởi các phần khác nhau của mẫu theo nhiều cách khác nhau. Trong trường hợp không khớp, bộ khớp phải thử tất cả các khả năng.

Tuy nhiên, sự gia tăng không phải là tuyến tính. Dưới đây là dữ liệu thực tế từ bài kiểm tra của chúng tôi chạy trên biểu thức chính quy (a+)+ khi được sử dụng trên một chuỗi không khớp:

n=10   ->  0.001s
n=20   ->  0.884s   (chậm hơn 884 lần so với n=10)
n=30   ->  hàng giờ

Khi kích thước đầu vào tăng gấp đôi, thời gian xử lý tăng theo cấp số nhân — chậm hơn 884 lần ở n=20 so với n=10. Ở n=30, xu hướng không hề chậm lại mà là dừng hẳn. Nếu có một điểm cuối sử dụng mẫu này trên dữ liệu đầu vào của người dùng, đó sẽ là một cuộc tấn công từ chối dịch vụ chỉ chờ đợi để xảy ra.

Cách redos-analyzer hoạt động

Hầu hết các công cụ kiểm tra hiện tại thực hiện kiểm tra trên các mẫu bằng cách cung cấp các đầu vào độc hại và đo thời gian xử lý. Mặc dù cách này có thể hiệu quả, nó đòi hỏi phải tạo ra các đầu vào độc hại cụ thể cho mẫu đang xét, một nhiệm vụ đôi khi rất khó khăn.

Thay vào đó, giải pháp của chúng tôi tận dụng thực tế là khi Python phân tích mã regex để biên dịch nó, Python trước tiên tạo ra cây cú pháp trừu tượng (AST) bằng cách gọi module nội bộ sre_parse. Cây AST kết quả bao gồm các bộ giá trị (opcode, value) đại diện cho mẫu dưới dạng cấu trúc. Nếu một cây AST có nút MAX_REPEAT chứa một SUBPATTERN mà bản thân nó lại chứa một MAX_REPEAT, việc lượng từ lồng nhau sẽ được phát hiện độc lập với bất kỳ đầu vào nào.

Điều này cho phép chúng tôi phân tích tĩnh cây AST và phát hiện bốn danh mục mẫu có khả năng nguy hiểm: lượng từ lồng nhau, giá trị null trong lượng từ, các lựa chọn chồng chéo và một danh mục khác không mong muốn.

Kết quả quét trên 20 gói phần mềm

Chúng tôi đã phân tích mã nguồn của 20 thư viện Python phổ biến nhất: requests, flask, django, fastapi, sqlalchemy, pydantic, pytest, numpy, pandas, pillow, scrapy, celery, boto3, httpx, aiohttp, click, rich, typer, black và mypy. Trình phân tích duyệt qua tất cả các tệp kết thúc bằng .py, trích xuất tất cả các lệnh gọi đến re.compile và re.search, và thực hiện quy trình phân tích cho từng cái.

Ban đầu có 90 cảnh báo được báo cáo. Sau khi loại bỏ mã kiểm tra, thư viện bên thứ ba và công cụ xây dựng, còn lại 23 cảnh báo trong mã thời gian chạy.

Trong các phát hiện được xác định, trường hợp của aiohttp có lẽ là thú vị nhất để khám phá thêm. Công cụ đã phát hiện _WS_EXT_RE là có khả năng nguy hiểm vì đây là một ví dụ về việc sử dụng regex sai cách. Cụ thể, nó được sử dụng trong trình phân tích cú pháp cho tiêu đề mở rộng WebSocket, nơi mã sử dụng headers.get(), khiến nó xử lý các giá trị tiêu đề nói chung. Khi đo với các đầu vào gây hại, nó mất khoảng 0.8ms trong trường hợp xấu nhất dưới CPython 3.12, thấp hơn nhiều so với ngưỡng thời gian thực tế. Mặc dù người duy trì thừa nhận rằng nó có thể không hiệu quả, nhưng không có lỗ hổng bảo mật nào liên quan. Tuy nhiên, việc kiểm toán đã chỉ ra rằng một lần kiểm toán trước đây đã tìm thấy _COOKIE_PATTERN (trong PR #11900) có vấn đề, cho thấy aiohttp đã nhận thức được loại lỗi này trong quá khứ.

Một kết quả thú vị khác là trong pytest, tại tệp expression.py dòng 113, mẫu có chứa (:?\w|:|...). Rất có thể, regex dự định là (?:...) — một nhóm không bắt giữ. Tuy nhiên, những gì được viết ở đó là một nhóm bắt giữ khớp dấu hai điểm tùy chọn. Trình phát hiện LIKELY_TYPO đã phát hiện ra điều này vì (:? là một cú pháp hợp mặc dù thực tế hiếm khi được sử dụng có chủ đích.

Khắc phục tự động

Mỗi cấu trúc đều đi kèm với phiên bản đã sửa của mẫu dựa trên các nhóm nguyên tử (atomic groups), được bao gồm trong thư viện re của Python bắt đầu từ phiên bản 3.11.

Nhóm nguyên tử (?>...) đại diện cho một loại cửa một chiều: một khi động cơ regex bước vào nó, không có cách nào khác ngoài việc thất bại ở đó, ngay cả khi sau đó trở nên rõ ràng rằng mẫu tiếp theo không thể tìm thấy. Lý do là không có sự bùng nổ tổ hợp với các nhóm nguyên tử vì không cho phép quay lui (backtracking).

TRƯỚC   (a+)+          nguy hiểm
SAU     (?>a+)+         an toàn

Trong một thí nghiệm sử dụng môi trường Colab với n=22, mẫu đã sửa chạy trong 0.000111 giây trong khi mẫu gốc mất 0.306 giây. Công cụ cũng có thể thực hiện kiểm tra tính tương đương ngữ nghĩa để đảm bảo mã mới khớp với mã cũ.

Cách sử dụng

Bạn có thể cài đặt công cụ này bằng lệnh sau:

pip install redos-analyzer

Nó cũng hoạt động trên Google Colab bằng cách sử dụng !pip install redos-analyzer. API cơ bản chỉ bao gồm hai phương thức: phương thức đầu tiên, analyze(), cung cấp thông báo cảnh báo dưới dạng danh sách các cảnh báo về việc sử dụng mẫu, trong khi phương thức thứ hai, suggest_fix(), đề xuất các bản sửa lỗi cho regex có vấn đề dựa trên mẫu và thông báo cảnh báo đã cho.

Mã nguồn của gói này có thể được tìm thấy tại https://github.com/HarshithReddy01/redos-analyzer. Các bước tiếp theo bao gồm mở rộng phân tích bằng cách quét qua các tệp để tìm các tình huống khi mẫu được định nghĩa ở một nơi trong codebase và sau đó được sử dụng trong một tệp khác (như trường hợp thư viện aiohttp). Trong triển khai hiện tại với cửa sổ 8 dòng xung quanh mỗi điểm gọi, công cụ của chúng tôi có thể phát hiện các tình huống đơn giản như thế này nhưng không thể nhận ra luồng dữ liệu đa mô-đun.

Nếu bạn phát hiện bất kỳ việc sử dụng mẫu nào có vấn đề trong codebase của mình, vui lòng tạo vấn đề (issue) trên GitHub.