Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

Java CoreSenior17 phút đọc

ReDoS trong Java: sự cố thật, timeout tự làm và checklist phòng thủ

Ôn 11 thẻ
Trong bài này

Cụm bài Regex: 1. Cú pháp, Java API và bài tập validate · 2. Bài tập: cấu hình mạng, log sang CSV, lookbehind, dòng trùng · 3. Engine, backtracking và catastrophic backtracking · 4. ReDoS trong Java: sự cố và phòng thủ

ReDoS (Regular expression Denial of Service) là khi một request với vài chục ký tự chọn khéo làm một thread chạy 100% CPU nhiều giây, không exception, không log lỗi. Bài này đi qua hai sự cố thật, bề mặt tấn công ở backend Java, các lớp phòng thủ khi java.util.regex không có timeout, và xét lại best practice của slide bằng số đo. Nên đọc trước bài 3 để biết vì sao engine backtracking bùng nổ.

Sơ đồ tóm tắt:

flowchart TD
  A["Thread RUNNABLE kẹt trong regex"] -->|"Nhận ra bằng"| B["Thread dump"]
  B --> C["Phòng thủ nhiều lớp"]
  C --> D["Pattern chỉ một cách khớp"]
  C --> E["Giới hạn độ dài trước regex"]
  C --> F["CharSequence có deadline"]
  C --> G["Input lạ: RE2/J"]
  C --> H["Lớp ký tự thay alternation"]

1. ReDoS trên production

Ý chính: chỉ một pattern mơ hồ trên đường nóng là đủ làm sập cả hệ thống lớn. Stack Overflow sập 34 phút vì \s+$, Cloudflare mất lưu lượng toàn cầu 27 phút vì .*.*=.*.

  • Stack Overflow, 7/2016: một bài có ~20.000 khoảng trắng liên tiếp, code trim dùng ^[\s‌]+|[\s‌]+$. Khoảng 200 triệu bước cho một lần render, và trang đó nằm trên trang chủ.
  • Cloudflare, 7/2019: một rule WAF (Web Application Firewall, tường lửa lọc request HTTP) chứa .*(?:.*=.*), triển khai đồng loạt. CPU các máy xử lý HTTP lên 100%.
Chi tiết hai sự cố: vì sao tốn ngần ấy bước, và bài học rút ra

Stack Overflow. Với nửa sau [\s‌]+$, engine thử bắt đầu ở từng ký tự khoảng trắng, nuốt hết dãy, rồi thất bại vì cuối dãy không phải cuối chuỗi: 20.000 + 19.999 + … ≈ 200 triệu bước. Load balancer thấy trang chủ chậm nên đánh dấu server không khoẻ, và trang ngừng phục vụ khoảng 34 phút. Đúng dạng \s+$ đã đo ở bài 3: 20.000 khoảng trắng mất 630 ms trên JDK 21.

Cloudflare. .*(?:.*=.*) là dạng .*.*=.*: ba .* liền nhau chia nhau cùng một đoạn input, chi phí bậc ba. Lưu lượng toàn cầu rớt khoảng 27 phút. Bài học gồm cả kỹ thuật (chuyển sang engine có bảo đảm thời gian, RE2 hoặc engine của Rust) lẫn quy trình (rule WAF cũng phải triển khai từ từ như code).

Nhắc lại từ bài 3: trên JDK 21 vẫn còn pattern chạy theo hàm mũ (lặp có giới hạn {n,m}, backreference, lồng ba tầng) hoặc đa thức (.*.*=.*, \s+$ với find()). Mọi con số trong bài đo trên JDK 21 bằng vòng lặp thô (không phải JMH), nên hãy xem như độ lớn.

Bề mặt tấn công điển hình ở backend Java:

  • @Pattern trên DTO cho ô tự do như tên, địa chỉ, mô tả.
  • Parse header (User-Agent, Accept-Language), URL, query string bằng regex tự viết.
  • Log hoặc dữ liệu import, nơi một dòng bất thường dài hàng MB.
  • Tính năng cho người dùng nhập regex: tìm kiếm, filter, rule alert.
  • Thư viện bên thứ ba: đã có nhiều CVE ReDoS trong thư viện parse user-agent, validate email, markdown.

2. Phòng thủ trong Java

Ý chính: phòng thủ nhiều lớp: pattern không mơ hồ, giới hạn độ dài input, timeout tự làm, engine tuyến tính cho input lạ, và công cụ quét sớm. Không lớp nào đủ một mình.

2.1. Viết pattern không mơ hồ

Cách sửa tận gốc là bảo đảm mỗi đoạn input chỉ có một cách khớp. Ba bản sửa, đo trên cùng input xấu:

Pattern dễ tổn thương Bản sửa Trước Sau
^([a-zA-Z0-9]+[._-]?){1,20}@[a-z]+\.com$ ^[a-zA-Z0-9]+(?:[._-][a-zA-Z0-9]+)*@[a-z]+\.com$ 15,7 s (n=30) 0 ms
\s+$ (dùng find) (?<!\s)\s+$, hoặc String.stripTrailing() 630 ms (n=20.000) 0 ms
.*.*=.* (dùng find) ^[^=]*=.* 87 s (n=5.000) 0 ms
Năm mẹo đứng sau các bản sửa, kèm số đo
  • Thay . bằng lớp ký tự phủ định nói rõ ranh giới: [^=]*= thay cho .*=.
  • Bắt buộc dấu phân cách giữa các lần lặp: \w+(?:\s\w+)* thay cho (\w+\s?)*.
  • Neo điểm bắt đầu khi biết chắc: ^[^=]*= chỉ thử ở vị trí 0, còn [^=]*= không neo vẫn thử ở n vị trí (đo được 670 ms với n=20.000).
  • Dùng lookbehind để chỉ bắt đầu ở đầu một dãy: (?<!\s)\s+$.
  • Possessive hoặc atomic group (không trả lại ký tự đã nuốt) khi phần phía sau không cần lấy lại: \s++$ giảm từ 630 ms xuống 142 ms nhưng vẫn bậc hai, vì nó không bớt được số vị trí bắt đầu. Possessive giúp, nhưng không thay được việc bỏ sự mơ hồ.

2.2. Giới hạn độ dài input trước khi chạy regex

Mọi pattern backtracking đều rẻ khi input ngắn, nên đây là lớp rẻ nhất: ô tên 100 ký tự, header vài KB, dòng log cắt ở 10 KB trước khi parse.

2.3. Timeout: Java không có sẵn

java.util.regex không có tham số timeout (.NET có Regex.MatchTimeout). Ý đầu tiên thường là chạy trong thread khác rồi future.get(timeout), nhưng nó không dừng được regex:

Future<Boolean> f = executor.submit(() -> evil.matcher("a".repeat(30) + "!").matches());
try { f.get(100, TimeUnit.MILLISECONDS); }
catch (TimeoutException e) { f.cancel(true); }   // cancel trả true...
// ...nhưng worker vẫn chạy tiếp: đo được nó kết thúc sau 15,4 giây

Cách dùng được: engine đọc input qua CharSequence.charAt() liên tục, nên bọc input trong một CharSequence tự ném exception khi quá hạn. Với ^(a+){2,30}$ và 32 chữ a cộng !, matchesWithin(..., 100 ms) ném exception sau đúng khoảng 100 ms; input bình thường như “aaaa” vẫn trả true.

Code DeadlineCharSequence và các chi tiết khi dùng
final class DeadlineCharSequence implements CharSequence {
    private final CharSequence inner;
    private final long deadlineNanos;

    DeadlineCharSequence(CharSequence inner, long deadlineNanos) {
        this.inner = inner;
        this.deadlineNanos = deadlineNanos;
    }

    @Override public char charAt(int index) {
        if (System.nanoTime() > deadlineNanos) throw new RegexTimeoutException();
        return inner.charAt(index);
    }
    @Override public int length() { return inner.length(); }
    @Override public CharSequence subSequence(int start, int end) {
        return new DeadlineCharSequence(inner.subSequence(start, end), deadlineNanos);
    }
    @Override public String toString() { return inner.toString(); }
}

final class RegexTimeoutException extends RuntimeException {
    RegexTimeoutException() { super("regex evaluation exceeded its time budget", null, false, false); }
}

static boolean matchesWithin(Pattern p, CharSequence input, Duration budget) {
    long deadline = System.nanoTime() + budget.toNanos();
    return p.matcher(new DeadlineCharSequence(input, deadline)).matches();
}
  • Exception tắt stack trace (writableStackTrace = false) vì nó là luồng điều khiển, không phải bug.
  • System.nanoTime() ở mỗi charAt tốn vài chục nanosecond. Nếu thấy đáng kể, chỉ kiểm tra mỗi 1.000 lần gọi bằng một bộ đếm.
  • Bắt RegexTimeoutException ở tầng gọi và trả 400 cho input, kèm một metric để biết có ai đang thử tấn công.
  • Cách này không dừng được regex trong thư viện bên thứ ba nếu thư viện tự gọi String.matches.

2.4. Engine thời gian tuyến tính

Khi pattern do người dùng nhập, hoặc input lớn và không tin cậy, đổi engine an toàn hơn vá từng pattern. RE2/J (com.google.re2j:re2j) không backtracking nên thời gian tuyến tính theo độ dài input, và API gần giống JDK:

com.google.re2j.Pattern p = com.google.re2j.Pattern.compile(userSuppliedRegex);
boolean hit = p.matcher(line).find();   // thời gian tuyến tính theo độ dài input

Pattern dùng backreference hay lookaround bị từ chối ngay lúc compile, đúng hành vi mình muốn với regex do người ngoài nhập. (Đoạn này mình không chạy trong bài vì cần thêm dependency.)

2.5. StackOverflowError với alternation trong vòng lặp

Engine của Java đệ quy một tầng cho mỗi lần lặp của group có alternation (a|b). (a|b)* trên chuỗi “abab…” 5.000 ký tự đã tràn stack 2 MB, còn [ab]* và (?:a|b)*+ thì không.

Bảng đo theo độ dài input và kích thước stack
Input (a|b)* [ab]* (?:a|b)*+
1.000 ký tự true true true
5.000 ký tự StackOverflowError true true
100.000 ký tự StackOverflowError true true

Thread mặc định 2 MB stack trên macOS ARM. Trên Linux x64 mặc định 1 MB nên ngưỡng còn thấp hơn; với -Xss512k thì 1.000 ký tự đã tràn.

2.6. Phát hiện sớm bằng công cụ

  • SonarQube và SonarLint: rule regex có thể backtracking quá mức (S5852) và rule stack overflow của regex (S5998).
  • CodeQL: query java/redos và java/polynomial-redos, chạy được trong GitHub code scanning.
  • Fuzz pattern quan trọng bằng input dài sinh tự động trong unit test, kèm @Timeout(1) của JUnit 5.

3. Nhìn lại best practice của slide

Ý chính: phần lớn lời khuyên của slide đúng, nhưng ba chỗ cần sửa: capture group gần như không đắt, ví dụ ^(\w*)*$ đã lỗi thời trên JDK 21, và “thêm timeout” thì Java phải tự làm.

Lời khuyên của slide Đánh giá ngắn
Compile một lần Đúng, nhanh gấp đôi String.matches
Đừng làm mọi thứ thành tuỳ chọn Đúng, quan trọng hơn ta nghĩ
Dùng *, + tiết kiệm Đúng một nửa: cái hại là chồng lấn
Tận dụng lazy +? Cẩn thận: không bớt số phương án
Lớp ký tự phủ định thay dấu chấm Đúng
Capture group đắt, dùng (?:) Đúng về đọc hiểu, phóng đại về hiệu năng
Tránh pattern hàm mũ như ^(\w*)*$ Đúng nguyên tắc, ví dụ lỗi thời
Thêm timeout nếu có thể Đúng, nhưng Java không có sẵn
Đánh giá chi tiết từng lời khuyên, kèm số đo
  • Compile một lần. String.matches compile lại mỗi lần gọi. Đo thô 1 triệu lần validate email: khoảng 500 ns/lần với String.matches, 240 ns/lần với static final Pattern. Chênh gấp đôi và sinh thêm rác; với vài nghìn request mỗi giây chưa phải nút thắt, nhưng miễn phí nên cứ làm.
  • Đừng làm mọi thứ thành tuỳ chọn; nghĩ về cái không được khớp. Pattern toàn ? và * vừa khớp nhầm (chuỗi rỗng cũng hợp lệ), vừa tạo nhiều cách khớp cho cùng một input, tức là nguyên liệu của backtracking.
  • Dùng *, + tiết kiệm. Vấn đề không nằm ở số lượng quantifier mà ở quantifier chồng lấn nhau. [^,]*,[^,]* an toàn dù có hai *.
  • Tận dụng lazy +?. Lazy đổi thứ tự thử chứ không bớt số phương án; trên input thất bại, nó tốn ngang greedy. Lớp ký tự phủ định thường tốt hơn.
  • Lớp ký tự phủ định thay cho dấu chấm. Vừa nói rõ ý, vừa xoá phần chồng lấn: "[^"]*" không thể chạy quá dấu " đóng.
  • Capture group đắt, dùng (?:). Đo (\w+)@(\w+)\.(\w+) và bản non-capturing: 77–85 ns so với 75–81 ns, gần như ngang nhau. Lý do thật để dùng (?:): số thứ tự nhóm không bị lệch khi thêm nhóm, và người đọc biết nhóm đó không được dùng.
  • Tránh pattern hàm mũ, ví dụ ^(\w*)*$. JDK 21 chạy chính ví dụ này tức thì (bài 3, mục 3.2); các dạng {n,m}, backreference, lồng ba tầng và đa thức vẫn nguy hiểm.
  • Thêm timeout nếu có thể. Phải tự làm bằng CharSequence có deadline (mục 2.3); Future.cancel không có tác dụng.

Bài tập

Bài 1: Review một validator

Đề: review đoạn code sau trong một PR.

public record CreateCustomerRequest(
        @Pattern(regexp = "^([a-zA-Z]+\\s?){1,10}$") String fullName,
        String searchRule) {}

@Service
class CustomerService {
    List<Customer> search(CreateCustomerRequest req, List<Customer> all) {
        return all.stream()
                .filter(c -> c.note().matches(req.searchRule()))
                .toList();
    }
    String mask(String text, String secret) {
        return text.replaceAll(secret, "***");
    }
}
Lời giải Bài 1, viết dưới dạng comment review
  • TODO (fullName): pattern có dạng (X+\s?){1,10}, là ReDoS trên JDK 21 (cùng dạng ^(\w+\s?){1,20}$ mất 13 giây với 30 ký tự). Sửa thành ^[\p{L}]+(?:\s[\p{L}]+){0,9}$. Dùng \p{L} để nhận tên tiếng Việt có dấu, và thêm @Size(max = 100), kèm giới hạn kích thước body ở tầng server vì @Size không chặn được @Pattern.
  • TODO (searchRule): người dùng tự nhập regex, chạy bằng engine backtracking trên mọi bản ghi. Một rule như (a+){2,30}$ làm treo thread. Hoặc đổi sang tìm kiếm thường (contains, full-text search), hoặc dùng RE2/J và compile một lần ngoài vòng lặp, kèm giới hạn độ dài rule. Hiện tại String.matches còn compile lại pattern cho từng bản ghi.
  • TODO (mask): secret được dùng làm pattern. Nếu secret chứa . hay +, nó khớp sai chỗ; nếu chứa ( thì ném PatternSyntaxException. Dùng text.replace(secret, "***"), thay theo nghĩa đen mọi chỗ, không qua regex.
  • NIT: ^...$ thừa với @Pattern, vì Hibernate Validator dùng matches() và đã neo cả chuỗi; giữ lại cũng không sai, chỉ để người đọc khỏi thắc mắc.

Ghi nhớ

  • Giải thích được vì sao \s+$ với find() là bậc hai, và nối nó với sự cố Stack Overflow 2016.
  • Viết lại được một pattern mơ hồ để mỗi input chỉ có một cách khớp.
  • Giải thích được vì sao @Size và Future.cancel(true) không bảo vệ được regex, và cái gì thay thế.
  • Biết khi nào phải đổi sang RE2/J, và đổi lại mất gì.
  • Nhận ra ReDoS từ thread dump, và biết vì sao (a|b)* nguy hiểm hơn [ab]*.

Câu hỏi phỏng vấn

Mid

Một form validate tên bằng @Pattern. Bạn kiểm tra gì để chắc nó không thành điểm ReDoS?

Ba thứ: pattern có mơ hồ không, độ dài input có bị chặn trước regex không, và có test với input xấu không.

  • Pattern có quantifier lồng nhau hoặc lặp có giới hạn của một group chứa phần tuỳ chọn không ((\w+\s?){1,20}); nếu có thì viết lại cho mỗi input chỉ có một cách khớp (\w+(?:\s\w+){0,19}).
  • Input có bị giới hạn độ dài trước khi tới regex không: @Size đứng cạnh không đủ vì thứ tự kiểm constraint không được bảo đảm, cần giới hạn body ở server hoặc @GroupSequence.
  • Một unit test với input dài xấu nhất kèm @Timeout.
Vì sao \s+$ dùng với find() lại chậm, dù không có quantifier lồng nhau?

Vì find() thử bắt đầu ở từng vị trí, và từ mỗi vị trí \s+ lại nuốt hết dãy rồi thất bại: tổng cộng khoảng n²/2 bước.

20.000 khoảng trắng mất 630 ms, và đây đúng là sự cố của Stack Overflow năm 2016. Sửa bằng (?<!\s)\s+$ để chỉ bắt đầu ở đầu dãy, hoặc không dùng regex: stripTrailing().

Senior

Service Java của bạn bỗng ăn 100% CPU, không có log lỗi. Làm sao biết có phải ReDoS không?

Lấy vài thread dump cách nhau vài giây; nhiều thread RUNNABLE với stack sâu toàn java.util.regex.Pattern$...match là gần như chắc chắn.

  • Dùng jcmd <pid> Thread.print; xem cùng một frame code ứng dụng đứng ở đáy stack. JFR hoặc async-profiler cho flame graph rõ hơn.
  • Tìm request gây ra từ access log (request chậm, payload dài), tái hiện bằng unit test, sửa pattern.
  • Thêm giới hạn độ dài input và timeout bằng CharSequence có deadline.
Java có timeout cho regex không? Bạn làm thế nào?

Không có. Cách dùng được là bọc input trong một CharSequence mà charAt ném exception khi quá deadline, vì engine gọi charAt liên tục.

Future.get(timeout) rồi cancel(true) không dừng được, vì engine không kiểm tra cờ interrupt; thread vẫn chạy tới khi regex xong. Kèm theo: giới hạn độ dài input, và với pattern do người dùng nhập thì dùng engine thời gian tuyến tính như RE2/J.

Vì sao (a|b)* có thể làm StackOverflowError, và vì sao lỗi này nguy hiểm?

Engine của Java đệ quy một tầng cho mỗi lần lặp của group có alternation, nên độ sâu stack tăng theo độ dài input.

Trên thread 2 MB, chuỗi 5.000 ký tự đã tràn. StackOverflowError là Error, không bị catch (Exception e) bắt, nên có thể giết thread của consumer hoặc worker. Sửa bằng lớp ký tự [ab]*, group possessive, hoặc [\s\S]* thay cho (.|\n)*.

Bạn đưa ra checklist review regex nào cho team?

Pattern không mơ hồ, input có giới hạn, test với input xấu, và engine tuyến tính cho mọi thứ từ bên ngoài.

  • Pattern là static final, không dùng String.matches/replaceAll trên đường nóng. Có anchor đúng chỗ.
  • Không có quantifier lồng nhau hay alternation chồng lấn; dùng lớp ký tự phủ định thay cho .* ở giữa pattern.
  • Input được giới hạn độ dài trước khi chạy regex.
  • Unit test với case phải khớp, case gần giống không được khớp, và input xấu dài có @Timeout.
  • Pattern hay input từ bên ngoài thì dùng RE2/J.
  • Dữ liệu người dùng đưa vào pattern thì bọc Pattern.quote, đưa vào chuỗi thay thế thì bọc Matcher.quoteReplacement.

Từ vựng tiếng Anh

Term Phát âm Nghĩa Ví dụ câu tiếng Anh dùng trong phỏng vấn
ReDoS /ˈriːdɒs/ tấn công từ chối dịch vụ qua regex “A single crafted request was enough to cause a ReDoS.”
thread dump /θred dʌmp/ ảnh chụp stack của mọi thread “The thread dump showed dozens of threads deep inside Pattern$Loop.match.”
time budget /taɪm ˈbʌdʒɪt/ ngân sách thời gian “Each match gets a 100-millisecond time budget.”
untrusted input /ʌnˈtrʌstɪd ˈɪnpʊt/ input không tin cậy “Never run a backtracking regex on untrusted input without a length limit.”
stack overflow /stæk ˈəʊvəfləʊ/ tràn stack “Alternation inside a star recursed once per character and overflowed the stack.”
catastrophic backtracking /ˌkætəˈstrɒfɪk ˈbækˌtrækɪŋ/ quay lui bùng nổ “Nested quantifiers caused catastrophic backtracking on a 30-character input.”
linear time /ˈlɪniər taɪm/ thời gian tuyến tính “RE2 guarantees linear time in the size of the input.”
defence in depth /dɪˈfens ɪn depθ/ phòng thủ nhiều lớp “A length limit, a safer pattern and a time budget give us defence in depth.”
staged rollout /steɪdʒd ˈrəʊlaʊt/ triển khai từng phần “Cloudflare now ships WAF rules through a staged rollout, just like code.”

Ghi chép dựa trên khoá Advanced Backend (Ronin Engineer), viết lại theo cách hiểu của mình.