Potential ReDoS Vulnerability or Inefficient Regular Expression in Project: Need for Assessment and Mitigation

[SuperMaxine]

Hello,

I am writing to report a potential Regular Expression Denial of Service (ReDoS) vulnerability or Inefficient Regular Expression in the project. This issue arises when specially crafted input strings are used in the context of distributed, high-volume requests, potentially leading to a denial-of-service attack.

Location of Issue:

The vulnerability is related to a regular expression used in the following validation file, which may result in significantly prolonged execution times under certain conditions.

yazi/yazi-shared/src/fs/path.rs

Line 18 in d6ca524

let re = regex::Regex::new(r"\$(?:\{([^}]+)\}|([a-zA-Z\d_]+))").unwrap();

PoC Files and Comparisons:

PoC.zip

To evaluate the performance of this inefficient regular expression matching with varying input contents, the following commands can be executed within the PoC folder:

cargo build --release # Build the PoC executable file
time ./target/release/redos AttackString10MB.txt
time ./target/release/redos RandomString10MB.txt
time ./target/release/redos AttackString1MB.txt
time ./target/release/redos RandomString1MB.txt

These commands measure the time taken for the regular expression to match different types of strings. The results on my machine are as follows: For a 10MB attack string, the processing time exceeded 10 minutes. In contrast, a 10MB random string took only 0.016 seconds. A 1MB attack string took 6.099 seconds. By comparison, a 1MB random string took merely 0.005 seconds.

Proposed Solution:

A possible mitigation strategy could include limiting the input length to prevent excessive processing times.

Additional Considerations:

Historically, it was believed that using regex engines with non-backtracking implementations (such as those in Rust or Go) would not lead to ReDoS vulnerabilities. However, recent studies have shown that this is not always the case. I recommend an assessment of how this issue might impact this project.

Thank you for your attention to this matter. Your evaluation and response to this potential security concern would be greatly appreciated.

Best regards,

[sxyazi]

Thank you for the report.

AFAIK, paths in Linux/macOS/Windows all have length limitations, generally quite low. Yazi's path originates from the user's file system, and I don't believe there would be a file name with a length of 1MB; the file system wouldn't allow it.