Regex में Catastrophic Backtracking से कैसे बचें?

रेगुलर एक्सप्रेशन का कैटास्ट्रॉफिक बैकट्रैकिंग इस तथ्य को संदर्भित करता है कि जब रेगुलर एक्सप्रेशन मिलान करता है, तो यह बहुत अधिक बैकट्रैक करता है, जिससे 100% CPU उपयोग होता है और सामान्य सेवाएं अवरुद्ध हो जाती हैं।

पृष्ठभूमि

मैंने एक लेख पढ़ा है जो 100% CPU का कारण बनने वाले रेगुलर बैकट्रैक की खोज और समाधान प्रक्रिया का विवरण देता है। मूल लेख काफी लंबा है, और मैंने पहले OpenResty विकास में दो बार इसी तरह की समस्याओं का सामना किया है।

यहां एक संक्षिप्त सारांश है ताकि आपको पृष्ठभूमि पर समय बिताने की आवश्यकता न हो।

1. अधिकांश विकास भाषाओं के लिए रेगुलराइजेशन इंजन बैकट्रैकिंग-आधारित NFA (थॉम्पसन के NFA पर आधारित नहीं) का उपयोग करके लागू किए जाते हैं।
2. यदि बहुत अधिक बैकट्रैकिंग होती है, तो 100% CPU के साथ कैटास्ट्रॉफिक बैकट्रैकिंग होती है।
3. ऑनलाइन वातावरण का पता लगाने के लिए gdb या systemtap के साथ डंप का विश्लेषण करने की आवश्यकता होती है।
4. ऐसी समस्याएं कोड लाइव होने से पहले पता लगाना मुश्किल होती हैं और रेगुलर एक्सप्रेशन की केस-बाय-केस समीक्षा की आवश्यकता होती है।

विकास के दृष्टिकोण से, समस्याग्रस्त रेगुलर एक्सप्रेशन को ठीक करना कहानी का अंत है। अधिक से अधिक, बैकट्रैकिंग की संख्या को सीमित करने के लिए एक सुरक्षा तंत्र जोड़ें, जैसे कि OpenResty में यह।

lua_regex_match_limit 100000;

इस तरह, भले ही कैटास्ट्रॉफिक बैकट्रैकिंग हो, यह सीमित होगा और पूरा CPU नहीं चलेगा।

क्या यह पहले से ही परफेक्ट लगता है? चलिए विकास स्तर से परे जाकर इसे एक अलग आयाम में देखते हैं।

हमलावर

बस एक मशीन का उपयोग करें, एक अनुरोध भेजें, और आप सर्वर के दूसरी तरफ हिट कर सकते हैं, यह एक हैकर के लिए परमाणु हथियार का सपना है। इसकी तुलना में, DDoS क्या है, यह कमजोर है, आंदोलन बड़ा और महंगा है।

इस हमले का अपना नाम भी है: ReDoS (रेगुलर एक्सप्रेशन डिनायल ऑफ सर्विस)।

चूंकि रेगुलर एक्सप्रेशन का इतना व्यापक उपयोग है और यह लगभग हर बैकएंड सेवा के हर हिस्से में मौजूद है, इसलिए कमजोरियों में से एक का फायदा उठाने का अवसर है।

एक परिदृश्य की कल्पना करें जहां एक हैकर WAF में एक ReDoS कमजोरी की खोज करता है और WAF को डाउन करने के लिए एक अनुरोध भेजता है; आप कम समय में समस्या का पता नहीं लगा पाते हैं, यह भी नहीं समझ पाते हैं कि यह एक हमला है; आप अपने व्यवसाय को ट्रैक पर रखने के लिए WAF को पुनः आरंभ करने या अस्थायी रूप से बंद करने का विकल्प चुनते हैं; जब WAF काम नहीं कर रहा होता है, तो हैकर SQL इंजेक्शन का उपयोग करके आपके डेटाबेस को खींच लेता है। आप, दूसरी ओर, अभी भी पूरी तरह से अनजान हो सकते हैं।

ओपन सोर्स सॉफ्टवेयर और क्लाउड सेवाओं के व्यापक उपयोग के कारण, यह सुनिश्चित करना पर्याप्त नहीं है कि आपके द्वारा लिखे गए रेगुलर एक्सप्रेशन कमजोरियों से मुक्त हैं। यह एक और विषय है, हम यहां केवल उन रेगुलर एक्सप्रेशन पर चर्चा करेंगे जो हमारे नियंत्रण में हैं।

ऐसे रेगुलर एक्सप्रेशन कैसे खोजें?

समस्याओं को हल करने का पहला कदम उन्हें खोजना है, और सभी को खोजने का प्रयास करना है, जिसे सुरक्षित रूप से खोजने की क्षमता के रूप में भी जाना जाता है।

मैन्युअल कोड समीक्षा से समस्याग्रस्त नियमों को खोजने की उम्मीद करना विश्वसनीय नहीं है। अधिकांश डेवलपर्स सुरक्षा के प्रति जागरूक नहीं होते हैं, और यदि वे उन्हें खोजने की कोशिश करेंगे, तो भी वे एक जटिल रेगुलर एक्सप्रेशन में समस्या का पता लगाने में सक्षम नहीं होंगे।

यहीं पर स्वचालित उपकरण काम आते हैं।

हमारे पास इस समस्या को हल करने के लिए निम्नलिखित दो स्वचालित तरीके हैं।

• स्थैतिक परीक्षण

ऐसे उपकरण कोड में रेगुलर एक्सप्रेशन को स्कैन कर सकते हैं और एक निश्चित एल्गोरिदम के अनुसार, उनमें से कैटास्ट्रॉफिक बैकट्रैकिंग वाले रेगुलर एक्सप्रेशन का पता लगा सकते हैं।

उदाहरण के लिए, RXXR2, जो एक पेपर में एक एल्गोरिदम पर आधारित है जो रेगुलर को ε-NFA में परिवर्तित करता है और फिर उसे खोजता है, लेकिन रेगुलर एक्सप्रेशन के विस्तारित सिंटैक्स का समर्थन नहीं करता है, इसलिए छूटे हुए रिपोर्ट होंगे।

• डायनामिक फजिंग

फज टेस्ट एक सामान्य सॉफ्टवेयर परीक्षण विधि है जो लंबे समय तक बड़ी मात्रा में यादृच्छिक डेटा दर्ज करके सॉफ्टवेयर क्रैश, मेमोरी लीक और अन्य समस्याओं का पता लगाती है।

इसी तरह, हम रेगुलर परीक्षण में इस दृष्टिकोण का उपयोग कर सकते हैं। हम मौजूदा रेगुलर एक्सप्रेशन के आधार पर परीक्षण डेटा उत्पन्न कर सकते हैं, या पूरी तरह से यादृच्छिक रूप से उत्पन्न कर सकते हैं।

SlowFuzz ओपन सोर्स उपकरणों में से एक है, यह भी एक पेपर पर आधारित एल्गोरिदम का कार्यान्वयन है, पेपर इस पेपर के अंत में सूचीबद्ध किया जाएगा, यह एक सामान्य उपकरण है, और रेगुलर की संरचना के लिए प्रसंस्करण नहीं करता है, इसलिए छूटे हुए रिपोर्ट होंगे।

SDLFuzzer माइक्रोसॉफ्ट द्वारा कुछ साल पहले विकसित एक विशेष ReDoS पता लगाने वाला उपकरण है, लेकिन अब इसे बनाए नहीं रखा जाता है।

इस क्षेत्र में चुनने के लिए बहुत सारे उपकरण नहीं हैं, और इतना ध्यान नहीं दिया जाता है। हालांकि, मैंने जानकारी की खोज के दौरान नानजिंग विश्वविद्यालय के कई शिक्षकों और पीएचडी द्वारा ReDoS पर एक पेपर पाया, और पेपर के साथ उपकरण ReScue को ओपन सोर्स किया: https://2bdenny.github.io/ReScue/. इस उपकरण ने कई ओपन सोर्स परियोजनाओं में ReDoS कमजोरियों की पहचान की है।

यहां पेपर में तुलना परीक्षण के परिणाम हैं।

क्या इसे एक बार और हमेशा के लिए किया जा सकता है?

भले ही हम ऐसे उपकरणों का उपयोग करें, फिर भी गलत अलार्म और छूटे हुए अलार्म होंगे, तो क्या ReDoS को हल करने का एक बार और हमेशा के लिए तरीका है?

फिर हमें समस्या की जड़ पर वापस जाना होगा: रेगुलर इंजन मिलान करने के लिए बैकट्रैकिंग का उपयोग करता है।

क्या अगर हम इस दृष्टिकोण को छोड़ दें तो ठीक होगा? हां, रेगुलर इंजन के कई अन्य कार्यान्वयन पहले से ही हैं जो इसे एक बार और हमेशा के लिए हल कर सकते हैं। वे सभी बैकट्रैकिंग को छोड़कर NFA/DFA ऑटोमेटन दृष्टिकोण का उपयोग करते हैं, लाभ यह है कि यह स्ट्रीमिंग मिलान के लिए उपयुक्त है और सुरक्षित भी है, नुकसान यह है कि यह कई रेगुलर विस्तार सिंटैक्स का समर्थन नहीं करता है, जैसे बैकरेफरेंस, अच्छी तरह से इनका आमतौर पर उपयोग नहीं किया जाता है।

• Google RE2

Google का RE2 अधिक पूर्ण ओपन सोर्स परियोजनाओं में से एक है। यह PCRE के अधिकांश सिंटैक्स का समर्थन करता है, और Go, Python, Perl, Node.js और अन्य विकास भाषाओं के लिए लाइब्रेरी कार्यान्वयन हैं, शुरुआत और प्रतिस्थापन लागत बहुत कम है।

आइए Perl को एक उदाहरण के रूप में लें और देखें कि क्या RE2 कैटास्ट्रॉफिक बैकट्रैकिंग समस्याओं से बच सकता है।

आइए परिणामों की इस तुलना चार्ट को देखें।

कोड निम्नलिखित है, यदि आप रुचि रखते हैं तो इसे स्वयं आजमा सकते हैं।

time perl -e 'if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print("hit");}'

40.80s user 0.00s system 99% cpu 40.800 total

इस कैनोनिकल को चलाने में 40.8 सेकंड लगते हैं, इस दौरान CPU 99% होता है।

RE2 के साथ, तुलना बहुत स्पष्ट है।

time perl -e 'use re::engine::RE2; if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print(" hit");}'

perl -e 0.00s user 0.00s system 34% cpu 0.011 total

• Intel Hyperscan

Intel Hyperscan भी RE2 के समान एक रेगुलर इंजन है, और Perl, Python और अन्य भाषाओं के लिए लाइब्रेरी हैं, इसलिए शुरुआत करना बहुत मुश्किल नहीं है।

केवल Intel के अभ्यास के अनुसार, अधिक प्लेटफॉर्म बाइंडिंग, केवल x86 में चल सकता है।

यदि कोई अनूठा लाभ है, तो यह Intel के इंस्ट्रक्शन सेट और हार्डवेयर के साथ बेहतर काम करने की क्षमता हो सकती है, प्रदर्शन में सुधार के साथ, जैसे कि इसके अपने DPDK के साथ संयोजन।

Snort, एक ओपन सोर्स नेटवर्क इंट्रूज़न डिटेक्शन टूल, भी Hyperscan का उपयोग करके पिछले रेगुलर इंजन को प्रतिस्थापित करता है, इसलिए Snort से परिचित छात्र इसे आजमा सकते हैं।

विस्तार

यहां रेगुलर एक्सप्रेशन पर कुछ पेपर हैं, यदि आप रुचि रखते हैं तो इन्हें एक विस्तार के रूप में पढ़ा जा सकता है।

1. SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities: https://arxiv.org/pdf/1708.08437.pdf

2. Static Analysis for Regular Expression Exponential Runtime via Substructural Logics: https://arxiv.org/abs/1405.7058.pdf

3. ReScue: Crafting Regular Expression DoS Attacks: https://dl.acm.org/doi/10.1145/3238147.3238159

4. Regular Expression Matching Can Be Simple And Fast: https://swtch.com/~rsc/regexp/regexp1.html