ReDoS (catastrophic backtracking) क्या है?

CWE-1333: Inefficient Regular Expression Complexityसंदर्भ पृष्ठ

संक्षिप्त उत्तर

Backtracking वाला regex इंजन मिलान विफल होने पर उसी इनपुट को अलग-अलग तरीकों से बाँटकर फिर आज़मा सकता है। कुछ अस्पष्ट पैटर्न में प्रयास इनपुट की लंबाई के साथ घातीय रूप से बढ़ते हैं। वास्तविक देरी regex, इंजन, इनपुट आकार, concurrency और संसाधन सीमाओं पर निर्भर करती है; बार-बार महँगे अनुरोध सेवा की क्षमता समाप्त कर सकते हैं।

जोखिम वाले पैटर्न

# Nested quantifier
^(a+)+$

# Overlapping alternatives, quantified
^(a|aa)+$

# A long matching prefix plus a final mismatch can
# force extensive retries in vulnerable engines.
# Do not benchmark this with attacker-sized input.

अधिक सुरक्षित

# Bound input before matching, then use a simple
# full-string identifier rule with no nested ambiguity.
import re

IDENTIFIER = re.compile(r"[a-z0-9]{1,64}\Z")

def valid_identifier(value: str) -> bool:
    if not isinstance(value, str) or len(value) > 64:
        return False
    return IDENTIFIER.fullmatch(value) is not None

# A bound reduces worst-case work; still set request
# size, concurrency, and execution-time limits.

Backtracking क्यों बढ़ता है

Backtracking इंजन में ^(a+)+$ जैसा पैटर्न अस्पष्ट है: aaaa को nested quantifiers में कई तरीकों से बाँटा जा सकता है। अंत में ऐसा अक्षर हो जो मेल न खाए, तो पूरी स्ट्रिंग को अस्वीकार करने से पहले इंजन कई विकल्प जाँच सकता है।

ऐसे पैटर्न में मेल खाने वाले prefix के बाद mismatch आने पर खोजे गए रास्ते prefix की लंबाई के साथ घातीय रूप से बढ़ सकते हैं। यह खास पैटर्न और इंजन के मेल पर निर्भर है; हर regex या विफल मिलान में ऐसा नहीं होता। समानांतर अनुरोधों में छोटे इनपुट भी असर डाल सकते हैं, इसलिए इनपुट, concurrency और समय सीमित करें।

अविश्वसनीय इनपुट regex तक कहाँ पहुँचता है

इनपुट validation स्पष्ट जगह है, लेकिन जोखिम User-Agent और अन्य headers, logs, Markdown और syntax highlighting, URL routing, content filters, WAF नियमों और दिए गए fields पर regex चलाने वाली libraries में भी है। लोकप्रिय packages में ReDoS advisories आई हैं; dependencies भी अपने patterns जितनी ही महत्वपूर्ण हैं।

अक्सर पूछे जाने वाले प्रश्न

Which languages are affected?

जोखिम भाषा से अधिक इंजन और पैटर्न पर निर्भर है। सामान्य backtracking इंजन कुछ पैटर्न में अत्यधिक विकल्प जाँच सकते हैं। Go का regexp दस्तावेज़ इनपुट लंबाई के अनुसार linear समय की गारंटी देता है। Rust का regex crate एक search के लिए O(m·n) बताता है (m पैटर्न आकार, n इनपुट आकार); स्थिर पैटर्न पर यह इनपुट के अनुसार linear है। बार-बार खोजने वाले iterators की सीमाएँ अलग हैं। ये इंजन backreferences जैसी सुविधाएँ नहीं देते जो ऐसी गारंटी रोकती हैं।

Is a length limit enough on its own?

सीमा मिलान के लिए उपलब्ध काम घटाती है, लेकिन सुरक्षित मान पैटर्न, इंजन, अनुरोध दर और सेवा बजट पर निर्भर है। अस्पष्ट पैटर्न भी ठीक करें और parsing या matching से पहले सीमा लागू करें।

How do I find vulnerable patterns?

ReDoS-जागरूक static analyzer चलाएँ और निष्कर्षों को वास्तविक इंजन के अनुसार जाँचें। ऐसे दोहराए गए समूह देखें जिनमें quantifier हों या विकल्पों के prefix एक-दूसरे से मिलते हों; फिर अलग-थलग परीक्षण वातावरण में सीमित इनपुट और कठोर timeout के साथ जाँचें।

Can I add a timeout instead?

Timeout समर्थन runtime और API पर निर्भर है। .NET में अविश्वसनीय इनपुट के मिलान पर स्पष्ट timeout दें। अन्य जगह संबंधित इंजन के दस्तावेज़ में उपलब्ध नियंत्रण देखें; लागू timeout न हो तो सुरक्षित इंजन चुनें या पैटर्न बदलें। Timeout, इनपुट और concurrency सीमाओं का पूरक है; यह अस्पष्ट पैटर्न को तेज़ नहीं बनाता।

संदर्भ

यह भी देखें Node.js ReDoS: Regex और CVE-2026-83606