Họ đang đo gì
Bạn có nghĩ về độ phức tạp như một bề mặt tấn công không. Đây là chỗ thuật toán gặp bảo mật.
Trả lời ngắn~30 giây
Nếu hàm băm không có khoá bí mật thì kẻ tấn công tính trước được hàng nghìn chuỗi cùng bucket, gửi chúng làm khoá JSON, và mỗi lần chèn phải duyệt hết danh sách trong bucket đó — O(n²) cho một request. Đây là hash-flooding, từng làm sập hàng loạt framework web năm 2011. Cách chặn: hàm băm có khoá ngẫu nhiên theo tiến trình (SipHash), giới hạn số khoá trong body, và giới hạn kích thước body.
Giải thích sâu
Điểm quan trọng là vì sao chuyển sang cây lại là biện pháp bảo mật chứ không chỉ hiệu năng. HashMap của Java từ 8 chuyển bucket dài thành cây đỏ-đen, đưa trường hợp xấu nhất từ O(n) xuống O(log n) — nghĩa là chi phí tấn công tăng vọt trong khi chi phí bình thường không đổi. Nhưng nó chỉ hoạt động khi khoá Comparable; với khoá không so sánh được thì vẫn là danh sách.
Cùng một dạng lỗ hổng xuất hiện ở nhiều nơi khác với tên khác: ReDoS là một biểu thức chính quy có backtracking mũ trên chuỗi do người dùng gửi; zip bomb là tỷ lệ nén; billion laughs là XML entity lồng nhau. Mẫu chung là “đầu vào nhỏ, công việc lớn”, và cách phòng chung là đặt giới hạn cứng ở BIÊN chứ không tin vào việc dữ liệu sẽ hợp lý.
Câu hỏi tiếp theo họ sẽ hỏi
?Làm sao phát hiện ReDoS trong code có sẵn?
Tìm những biểu thức có nhóm lặp lồng nhau ((a+)+, (\s*)*) chạy trên đầu vào từ người dùng — đó là dạng gần như luôn có backtracking mũ. Công cụ như safe-regex bắt được phần lớn; ngoài ra đặt timeout cho việc khớp là biện pháp phòng thủ cuối.
Trả lời thế này là mất điểm
- Coi độ phức tạp trung bình là đủ khi đầu vào do bên ngoài kiểm soát. Với dữ liệu đối kháng, trường hợp xấu nhất mới là trường hợp thường.