Regular Expression ReDoS in Perl via Trie Overflow

Executive Summary

This vulnerability affects Perl versions through 5.43.9 and involves incorrect regular expression matching when an alternation of more than 65,535 fixed string branches is compiled into a trie in Perl_study_chunk.

The issue occurs because the delta between the first branch and the shared tail in the trie is stored in a 16-bit field. When the branch count exceeds 65,535, this field overflows, causing the trie's match decision table to be truncated without any warning or error.

As a result, the regular expression pattern produces false positive matches (matching strings it should not) and false negative matches (failing to match strings it should). This can lead to incorrect behavior in applications that rely on such patterns for access control or filtering decisions.

Useful 0 Not Useful 0

Detection Guidance

Detecting this vulnerability requires identifying Perl scripts or applications that use regular expressions with a large number of fixed string branches (more than 65,535) compiled into a trie. Since the issue is silent and does not produce warnings or errors, manual inspection or automated analysis of regular expressions is necessary.

• Check Perl version: Run `perl -v` to verify if the installed Perl version is 5.43.9 or earlier. Versions up to and including 5.43.9 are affected.
• Inspect regular expressions in code: Look for patterns with many alternations (e.g., `a|b|c|...|z`) where the number of branches exceeds 65,535. These are likely to trigger the vulnerability.
• Use static analysis tools: Tools like `perlcritic` or custom scripts can scan Perl codebases for complex regular expressions with excessive alternations.
• Enable debugging for regular expressions: Use `use re 'Debug';` in Perl scripts to observe trie compilation behavior. However, note that this may cause crashes in affected versions (as mentioned in Resource 3).

There are no direct network-based detection methods for this vulnerability, as it is a logic flaw in the Perl interpreter's regular expression engine.

Useful 0 Not Useful 0

Impact Analysis

This vulnerability can impact you in several ways if you use Perl applications or scripts that rely on regular expressions for critical operations.

• False positive matches: The regular expression may incorrectly match strings that should not be matched, leading to unintended access or actions. For example, an access control system might grant permissions to unauthorized users.
• False negative matches: The regular expression may fail to match strings that should be matched, causing legitimate requests or data to be rejected. For example, a filtering system might block valid content or allow malicious content to pass through.

If the vulnerable pattern is used in security-sensitive contexts, such as authentication, authorization, or data validation, the impact could be severe, potentially leading to security breaches or data corruption.

Useful 0 Not Useful 0

Compliance Impact

This vulnerability can affect compliance with common standards and regulations in the following ways:

• GDPR (General Data Protection Regulation): If the vulnerability leads to incorrect filtering or access control, it could result in unauthorized access to personal data or failure to protect such data. This may violate GDPR requirements for data protection and privacy, potentially leading to fines or legal action.
• HIPAA (Health Insurance Portability and Accountability Act): In healthcare applications, if the vulnerability causes incorrect handling of patient data (e.g., unauthorized access or failure to filter sensitive information), it could violate HIPAA's privacy and security rules, resulting in penalties.
• Other standards: Many compliance frameworks, such as PCI DSS (Payment Card Industry Data Security Standard) or SOC 2, require accurate and secure handling of data. Incorrect regular expression matches could lead to non-compliance if they affect data integrity or security controls.

Organizations using affected Perl versions should assess whether their applications rely on regular expressions for compliance-related functions and apply the necessary patches to mitigate risks.

Useful 0 Not Useful 0

Mitigation Strategies

• Upgrade Perl: The most effective mitigation is to upgrade to Perl version 5.43.10 or later, where the vulnerability is fixed. This version includes the patch that prevents the overflow condition during trie compilation.
• Apply the upstream patch: If upgrading is not immediately possible, apply the patch provided in Resource 1 (commit 03f74bbbd3a68350d926ee93d56ee4808c28c4c7) to your Perl installation. The patch modifies `regcomp_study.c` to skip trie optimization when the delta would overflow.
• Avoid large alternations in regular expressions: Refactor code to reduce the number of fixed string branches in alternations. For example, split large patterns into smaller ones or use alternative logic (e.g., hash lookups) for access control or filtering decisions.
• Review critical code: Audit Perl scripts or applications that use regular expressions for access control, filtering, or security-sensitive decisions. Replace or modify patterns that could be affected by this vulnerability.

If the vulnerability is suspected to have been exploited, review logs or outputs from affected systems for incorrect access control or filtering decisions. However, exploitation may not leave obvious traces.

Useful 0 Not Useful 0