अधिकांश समय regex तेज़ी से चलते हैं और कोई समस्या नहीं देते। पर कुछ पैटर्न में एक छिपा हुआ ख़तरा होता है — किसी ख़ास इनपुट पर वे इतने धीमे हो सकते हैं कि सेकंड के बजाय मिनटों या उससे भी अधिक समय ले लें, और इस बीच पूरी प्रणाली ठप पड़ जाए। इस परिघटना को विनाशकारी बैकट्रैकिंग कहते हैं, और यह न केवल एक प्रदर्शन-समस्या है, बल्कि एक असली सुरक्षा-जोखिम भी।
बैकट्रैकिंग असल में होती क्या है
जब कोई regex इंजन किसी पैटर्न को टेक्स्ट से मिलाने की कोशिश करता है, तो वह अक्सर कई रास्ते आज़माता है। अगर एक रास्ता विफल हो जाए, तो इंजन पीछे लौटता है और कोई दूसरा संभव रास्ता आज़माता है। इसी पीछे लौटने और दोबारा कोशिश करने को बैकट्रैकिंग कहते हैं, और सामान्य मामलों में यह बिल्कुल ठीक है।
समस्या तब खड़ी होती है जब आज़माने को रास्तों की संख्या इनपुट के साथ बहुत तेज़ी से बढ़ने लगती है। कुछ पैटर्न और कुछ इनपुट के मेल में संभव संयोजन इतने अधिक हो जाते हैं कि इंजन उनमें भटकता रह जाता है, और एक छोटा-सा इनपुट भी उसे लगभग रोक देता है।
विनाशकारी मामला कैसे बनता है
विनाशकारी बैकट्रैकिंग आम तौर पर तब आती है जब किसी पैटर्न में परिमाणक एक-दूसरे के भीतर इस तरह बैठ जाते हैं कि एक ही टेक्स्ट को कई अलग-अलग तरीक़ों से बाँटा जा सकता है। जब ऐसा हो और मिलान अंततः विफल हो, तो इंजन हर संभव बँटवारे को आज़माने की कोशिश करता है।
संभावनाओं की यह संख्या अक्सर इनपुट की लंबाई के साथ विस्फोटक रूप से बढ़ती है। यही कारण है कि कुछ ही अतिरिक्त वर्ण जोड़ने से मिलान-समय कई गुना बढ़ सकता है, और एक मामूली दिखने वाला पैटर्न अचानक एक गंभीर ख़तरा बन जाता है।
यह एक सुरक्षा-समस्या क्यों है
अगर कोई पैटर्न उपयोगकर्ता-इनपुट पर चलता है और विनाशकारी बैकट्रैकिंग के प्रति संवेदनशील है, तो एक हमलावर जान-बूझकर ऐसा इनपुट भेज सकता है जो इंजन को अटका दे। बस कुछ सावधानी से गढ़े गए अनुरोध पूरी सेवा को व्यस्त रखकर ठप कर सकते हैं।
इसी हमले को सेवा-अस्वीकार यानी डिनायल ऑफ़ सर्विस कहा जाता है, और regex के संदर्भ में इसे अक्सर ReDoS के नाम से जाना जाता है। यही कारण है कि बैकट्रैकिंग को केवल एक प्रदर्शन-मुद्दा मानना भूल है; यह एक असली सुरक्षा-छेद है।
ख़तरनाक पैटर्न को पहचानना
सौभाग्य से जोखिम भरे पैटर्न के कुछ पहचानने योग्य लक्षण हैं। जब एक परिमाणक के भीतर दूसरा परिमाणक हो, और भीतर के हिस्से एक-दूसरे को ओवरलैप करते हों, तो सतर्क हो जाना चाहिए। ऐसे ढाँचे ही टेक्स्ट को कई तरीक़ों से बाँटने की गुंजाइश देते हैं।
इन लक्षणों को जान लेना समीक्षा के दौरान बहुत उपयोगी होता है। जब कोई regex इस तरह के घोंसले वाले परिमाणक दिखाए, तो उसे विशेष ध्यान और परीक्षण के साथ देखना चाहिए, न कि बिना सोचे स्वीकार कर लेना।
पैटर्न को सुरक्षित रूप से दोबारा लिखना
अधिकांश ख़तरनाक पैटर्न को अधिक स्पष्ट और कम अस्पष्ट रूप में दोबारा लिखा जा सकता है। मूल विचार यह है कि इंजन के पास आज़माने को रास्तों की संख्या घटाई जाए — पैटर्न को इस तरह आकार दिया जाए कि किसी टेक्स्ट को बाँटने का एक ही स्पष्ट तरीक़ा हो।
जब अस्पष्टता हटती है, तो बैकट्रैकिंग की गुंजाइश भी हट जाती है। यही कारण है कि साफ़, सटीक पैटर्न न केवल पढ़ने में आसान होते हैं, बल्कि प्रदर्शन की दृष्टि से भी सुरक्षित होते हैं। पठनीयता और सुरक्षा यहाँ एक ही दिशा में चलती हैं।
रक्षा की अतिरिक्त परतें
पैटर्न सुधारने के अलावा कुछ रक्षात्मक उपाय भी मदद करते हैं। उपयोगकर्ता-इनपुट की लंबाई पर एक उचित सीमा लगाना संभावनाओं के विस्फोट को सीमित कर देता है। मिलान पर एक समय-सीमा रखना यह सुनिश्चित करता है कि कोई एक अनुरोध इंजन को अनिश्चितकाल तक न रोके।
कुछ regex इंजन ऐसे डिज़ाइन किए गए हैं जो विनाशकारी बैकट्रैकिंग के प्रति प्रतिरोधी हैं। जहाँ अविश्वसनीय इनपुट पर पैटर्न चलाने हों, वहाँ ऐसे इंजन का चुनाव एक मज़बूत बचाव हो सकता है। ये परतें मिलकर एक ही पैटर्न की ग़लती को पूरी प्रणाली गिराने से रोकती हैं।
परीक्षण में सबसे ख़राब मामले को आज़माएँ
चूँकि विनाशकारी बैकट्रैकिंग सामान्य इनपुट पर छिपी रहती है, इसलिए केवल सामान्य परीक्षण इसे नहीं पकड़ते। ज़रूरत है कि जान-बूझकर ऐसे इनपुट आज़माए जाएँ जो पैटर्न को सबसे ज़्यादा मेहनत पर मजबूर करें — ख़ास तौर पर लंबे, दोहराव वाले इनपुट जो अंत में विफल होते हों।
ऐसे सबसे ख़राब मामलों को परीक्षण में शामिल करना ही असली जोखिम उजागर करता है। अगर किसी पैटर्न का मिलान-समय इनपुट की लंबाई बढ़ाने पर तेज़ी से बढ़ता दिखे, तो यह एक स्पष्ट चेतावनी है कि पैटर्न संवेदनशील है और उसे दोबारा लिखने की ज़रूरत है।
यह अभ्यास ख़ास तौर पर तब अनिवार्य है जब पैटर्न अविश्वसनीय इनपुट पर चलने वाला हो। ऐसे मामलों में सबसे ख़राब मामले का परीक्षण केवल एक अच्छी आदत नहीं, बल्कि एक सुरक्षा-आवश्यकता है, क्योंकि यही वह इनपुट है जो एक हमलावर भेजेगा।
सतर्कता को एक आदत बनाएँ
विनाशकारी बैकट्रैकिंग का सबसे बड़ा ख़तरा यह है कि वह विकास के दौरान छिपी रहती है। पैटर्न सामान्य इनपुट पर बिल्कुल ठीक चलता है, और समस्या केवल उस ख़ास, दुर्भावनापूर्ण इनपुट पर सामने आती है जिसे शायद कभी आज़माया ही न गया हो।
इसीलिए सबसे अच्छा बचाव सतर्कता को एक आदत बनाना है — जोखिम भरे पैटर्न पहचानना, उन्हें साफ़ रूप में लिखना, इनपुट-सीमा और समय-सीमा लगाना, और अविश्वसनीय इनपुट के लिए सुरक्षित इंजन चुनना। ये कुछ अनुशासन मिलकर एक मामूली दिखने वाले regex को एक छिपे हुए संकट में बदलने से रोक देते हैं।