ReDoS

सेवा से नियमित अभिव्यक्ति इनकार (ReDoS)^[1] एक एल्गोरिथम जटिलता का हमला है जो एक नियमित अभिव्यक्ति और/या एक इनपुट प्रदान करके सेवा से इनकार करता है जो मूल्यांकन के लिए एक लंबा समय लेता है। हमला इस तथ्य का फायदा उठाता है कि बहुत से^[2] रेगुलर एक्सप्रेशन#कार्यान्वयन में सुपर-लीनियर वर्स्ट-केस जटिलता है; कुछ रेगेक्स-इनपुट जोड़े पर, लिया गया समय इनपुट आकार के संबंध में बहुपद या घातीय रूप से बढ़ सकता है। एक हमलावर इस प्रकार एक विशेष रूप से तैयार की गई नियमित अभिव्यक्ति और/या इनपुट प्रदान करके एक कार्यक्रम को पर्याप्त समय बिताने का कारण बन सकता है। कार्यक्रम तब धीमा हो जाएगा या अनुत्तरदायी हो जाएगा।^[3]^[4]

विवरण

नियमित अभिव्यक्ति (रेगेक्स) मिलान एक परिमित-राज्य automaton बनाकर किया जा सकता है। रेगेक्स को आसानी से गैर-नियतात्मक परिमित-राज्य ऑटोमेटन (एनएफए) में परिवर्तित किया जा सकता है, जिसमें प्रत्येक राज्य और इनपुट प्रतीक के लिए कई संभावित अगले राज्य हो सकते हैं। ऑटोमेटन के निर्माण के बाद, कई संभावनाएँ मौजूद हैं:

इंजन इसे नियतात्मक परिमित ऑटोमेटन | नियतात्मक परिमित-राज्य ऑटोमेटन (डीएफए) में परिवर्तित कर सकता है और परिणाम के माध्यम से इनपुट चला सकता है;
इंजन एक-एक करके सभी संभावित पथों का प्रयास कर सकता है जब तक कि एक मैच नहीं मिल जाता है या सभी पथों की कोशिश की जाती है और विफल हो जाती है (बैकट्रैकिंग)।^[5]^[6]
इंजन समानांतर में गैर-नियतात्मक ऑटोमेटन के माध्यम से सभी संभावित रास्तों पर विचार कर सकता है;
इंजन गैर-नियतात्मक automaton को डीएफए आलसी मूल्यांकन (यानी, फ्लाई पर, मैच के दौरान) में परिवर्तित कर सकता है।

उपरोक्त एल्गोरिदम में से, पहले दो समस्याग्रस्त हैं। पहला समस्याग्रस्त है क्योंकि एक नियतात्मक automaton तक हो सकता है $2^{m}$ कहाँ बताता है $m$ nondeterministic automaton में राज्यों की संख्या है; इस प्रकार, NFA से DFA में रूपांतरण में EXPTIME लग सकता है। दूसरा समस्याग्रस्त है क्योंकि एक गैर-निर्धारिती automaton में लंबाई के पथों की एक घातीय संख्या हो सकती है $n$ , ताकि लंबाई के एक इनपुट के माध्यम से चलना $n$ घातीय समय भी लगेगा।^[7] हालांकि, पिछले दो एल्गोरिदम, पैथोलॉजिकल व्यवहार प्रदर्शित नहीं करते हैं।

ध्यान दें कि गैर-पैथोलॉजिकल रेगुलर एक्सप्रेशन के लिए, समस्याग्रस्त एल्गोरिदम आमतौर पर तेज़ होते हैं, और व्यवहार में, कोई उनसे O(m) समय में एक रेगेक्स को संकलित करने और O(n) समय में मिलान करने की उम्मीद कर सकता है; इसके बजाय, एनएफए के अनुकरण और डीएफए की आलसी गणना में समय जटिलता (एम²एन) सबसे खराब स्थिति वाली जटिलता।^[8] रेगेक्स सेवा से इनकार तब होता है जब ये अपेक्षाएं उपयोगकर्ता द्वारा प्रदान किए गए रेगेक्स पर लागू होती हैं, और उपयोगकर्ता द्वारा प्रदान किए गए दुर्भावनापूर्ण रेगुलर एक्सप्रेशन रेगेक्स मैचर की सबसे खराब स्थिति वाली जटिलता को ट्रिगर करते हैं।

जबकि रेगेक्स एल्गोरिदम को एक कुशल तरीके से लिखा जा सकता है, अस्तित्व में अधिकांश रेगेक्स इंजन रेगेक्स भाषाओं को अतिरिक्त निर्माणों के साथ विस्तारित करते हैं जिन्हें हमेशा कुशलता से हल नहीं किया जा सकता है। गैर-नियमित भाषाओं के लिए इस तरह के रेगुलर एक्सप्रेशन#पैटर्न अनिवार्य रूप से बैकट्रैकिंग का उपयोग करने के लिए अधिकांश प्रोग्रामिंग भाषाओं में रेगेक्स के कार्यान्वयन को बाध्य करते हैं।

उदाहरण

घातीय बैकट्रैकिंग

सबसे गंभीर प्रकार की समस्या बैकट्रैकिंग रेगुलर एक्सप्रेशन मैच के साथ होती है, जहां कुछ पैटर्न में एक रनटाइम होता है जो इनपुट स्ट्रिंग की लंबाई में घातीय होता है।^[9] के तार के लिए $n$ वर्ण, रनटाइम है $O(2^{n})$ . यह तब होता है जब एक रेगुलर एक्सप्रेशन में तीन गुण होते हैं:

रेगुलर एक्सप्रेशन दोहराव लागू करता है (+, *) एक उप अभिव्यक्ति के लिए;
सबएक्सप्रेशन एक ही इनपुट से कई तरीकों से मेल खा सकता है, या सबएक्सप्रेशन एक इनपुट स्ट्रिंग से मेल खा सकता है जो एक लंबे संभावित मैच का उपसर्ग है;
और बार-बार उप-अभिव्यक्ति के बाद, एक अभिव्यक्ति होती है जो किसी ऐसी चीज से मेल खाती है जो उप-अभिव्यक्ति से मेल नहीं खाती।

दूसरी स्थिति को दो उदाहरणों के साथ सबसे अच्छी तरह समझाया गया है:

में (a|a)+$, पुनरावृत्ति को उप-अभिव्यक्ति पर लागू किया जाता है a|a, जो मेल खा सकता है a प्रत्यावर्तन के प्रत्येक पक्ष पर दो तरह से।
में (a+)*$, पुनरावृत्ति को उप-अभिव्यक्ति पर लागू किया जाता है a+, जो मेल खा सकता है a या aa, वगैरह।

इन दोनों उदाहरणों में हमने प्रयोग किया $ स्ट्रिंग के अंत से मिलान करने के लिए, तीसरी स्थिति को संतुष्ट करने के लिए, लेकिन इसके लिए किसी अन्य वर्ण का उपयोग करना भी संभव है। उदाहरण के लिए (a|aa)*c समान समस्यात्मक संरचना है।

उपरोक्त सभी तीन रेगुलर एक्सप्रेशन फॉर्म के स्ट्रिंग्स पर लागू होने पर एक्सपोनेंशियल रनटाइम प्रदर्शित करेंगे $a...a!$ . उदाहरण के लिए, यदि आप उनके विरुद्ध मिलान करने का प्रयास करते हैं aaaaaaaaaaaaaaaaaaaaaaaa! बैकट्रैकिंग एक्सप्रेशन इंजन पर, इसे पूरा होने में काफी लंबा समय लगेगा, और प्रत्येक अतिरिक्त के लिए रनटाइम लगभग दोगुना हो जाएगा a से पहले !.

बैकट्रैकिंग करना भी संभव है जो बहुपद समय है $O(n^{x})$ , घातीय के बजाय। यह पर्याप्त लंबे इनपुट के लिए भी समस्या पैदा कर सकता है, हालांकि इस समस्या पर कम ध्यान दिया गया है क्योंकि महत्वपूर्ण प्रभाव डालने के लिए दुर्भावनापूर्ण इनपुट का अधिक लंबा होना आवश्यक है। ऐसे पैटर्न का एक उदाहरण हैa*b?a*x, जब इनपुट एक मनमाने ढंग से लंबा अनुक्रम हैaएस।

ऑनलाइन रिपॉजिटरी में कमजोर रेगेक्स

ऑनलाइन रेगुलर एक्सप्रेशन रिपॉजिटरी में तथाकथित दुष्ट या कमजोर रेगेक्स पाए गए हैं। ध्यान दें कि पूर्ण रेगेक्स पर हमला करने के लिए एक कमजोर उप-अभिव्यक्ति खोजने के लिए पर्याप्त है:

RegExLib, id=1757 (ईमेल सत्यापन) - देखें red हिस्सा
^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$
OWASP वैलिडेशन रेगेक्स रिपॉजिटरी, Java Classname - देखें red हिस्सा
^(([a-z])+.)+[A-Z]([a-z])+$

ये दो उदाहरण भी इनपुट के लिए अतिसंवेदनशील हैं aaaaaaaaaaaaaaaaaaaaaaaa!.

हमला

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

हालाँकि, यदि सर्वर-साइड पर पहले से ही एक कमजोर रेगेक्स मौजूद है, तो एक हमलावर इसके बजाय एक इनपुट प्रदान करने में सक्षम हो सकता है जो उसके सबसे खराब स्थिति वाले व्यवहार को ट्रिगर करता है। इस मामले में, ईमेल स्कैनर और घुसपैठ का पता लगाने वाले सिस्टम भी असुरक्षित हो सकते हैं। सौभाग्य से, ज्यादातर मामलों में, समस्याग्रस्त नियमित अभिव्यक्तियों को गैर-दुष्ट पैटर्न के रूप में फिर से लिखा जा सकता है। उदाहरण के लिए, (.*a)+ पर फिर से लिखा जा सकता है ([^a]*a)+.

वेब एप्लिकेशन के मामले में, प्रोग्रामर सिस्टम के क्लाइंट और सर्वर साइड दोनों पर इनपुट को मान्य करने के लिए एक ही नियमित अभिव्यक्ति का उपयोग कर सकता है। एक हमलावर ग्राहक कोड का निरीक्षण कर सकता है, दुष्ट नियमित अभिव्यक्तियों की तलाश कर सकता है, और इसे हैंग करने के लिए सीधे वेब सर्वर पर तैयार किए गए इनपुट भेज सकता है।^[10]

यह भी देखें

संदर्भ

↑ OWASP (2010-02-10). "Regex Denial of Service". Retrieved 2010-04-16.
↑ Davis, James; Louis, Michael; Coghlan, Christy; Servant, Francisco; Lee, Dongyoon (2019). "Why Aren't Regular Expressions a Lingua Franca? An Empirical Study on the Re-use and Portability of Regular Expressions" (PDF). The ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering: 443–454.
↑ RiverStar Software (2010-01-18). "Security Bulletin: Caution Using Regular Expressions". Archived from the original on 2011-07-15. Retrieved 2010-04-16.
↑ Ristic, Ivan (2010-03-15). ModSecurity Handbook. London, UK: Feisty Duck Ltd. p. 173. ISBN 978-1-907117-02-2.
↑ Crosby and Wallach, Usenix Security (2003). "Regular Expression Denial Of Service". Archived from the original on 2005-03-01. Retrieved 2010-01-13.
↑ Bryan Sullivan, MSDN Magazine (2010-05-03). "Regular Expression Denial of Service Attacks and Defenses". Retrieved 2010-05-06. {{cite web}}: External link in |author= (help)
↑ Kirrage, J.; Rathnayake, A.; Thielecke, H. (2013). "Static Analysis for Regular Expression Denial-of-Service Attacks". Network and System Security. Madrid, Spain: Springer. pp. 135–148. arXiv:1301.0849. doi:10.1007/978-3-642-38631-2_11.
↑ Lazy computation of the DFA can usually reach the speed of deterministic automatons while keeping worst case behavior similar to simulation of an NFA. However, it is considerably more complex to implement and can use more memory.
↑ Jim Manico and Adar Weidman (2009-12-07). "OWASP Podcast 56 (ReDoS)". Retrieved 2010-04-02.
↑ Barlas, Efe; Du, Xin; Davis, James (2022). "सेवा के रेगेक्स इनकार के लिए इनपुट स्वच्छता का शोषण" (PDF). ACM/IEEE International Conference on Software Engineering: 1–14.

बाहरी संबंध

Examples of ReDoS in open source applications:
Some benchmarks for ReDoS
- Achim Hoffman (2010). "ReDoS - benchmark for regular expression DoS in JavaScript". Retrieved 2010-04-19.
- Richard M. Smith (2010). "Regular expression denial of service (ReDoS) attack test results". Retrieved 2010-04-19.
Paper on implementing regular expressions not vulnerable to certain classes of ReDoS
- Russ Cox (2007). "Regular Expression Matching Can Be Simple And Fast". Retrieved 2011-04-20.
Tools for detecting ReDoS vulnerabilities
- H. Thielecke, A. Rathnayake (2013). "Regular expression denial of service (ReDoS) static analysis". Retrieved 2013-05-30.
- B. van der Merwe, N Weideman (2017). "Regex Static Analysis". Retrieved 2017-08-12.

[ReDoS_in_OWASP-1] OWASP (2010-02-10). "Regex Denial of Service". Retrieved 2010-04-16.

[2] Davis, James; Louis, Michael; Coghlan, Christy; Servant, Francisco; Lee, Dongyoon (2019). "Why Aren't Regular Expressions a Lingua Franca? An Empirical Study on the Re-use and Portability of Regular Expressions" (PDF). The ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering: 443–454.

[RiverStar-3] RiverStar Software (2010-01-18). "Security Bulletin: Caution Using Regular Expressions". Archived from the original on 2011-07-15. Retrieved 2010-04-16.

[ModSecurity-4] Ristic, Ivan (2010-03-15). ModSecurity Handbook. London, UK: Feisty Duck Ltd. p. 173. ISBN 978-1-907117-02-2.

[Crossby.26Wallach-5] Crosby and Wallach, Usenix Security (2003). "Regular Expression Denial Of Service". Archived from the original on 2005-03-01. Retrieved 2010-01-13.

[Sullivan-6] Bryan Sullivan, MSDN Magazine (2010-05-03). "Regular Expression Denial of Service Attacks and Defenses". Retrieved 2010-05-06. {{cite web}}: External link in |author= (help)

[KirrageRathnayakeThielecke-7] Kirrage, J.; Rathnayake, A.; Thielecke, H. (2013). "Static Analysis for Regular Expression Denial-of-Service Attacks". Network and System Security. Madrid, Spain: Springer. pp. 135–148. arXiv:1301.0849. doi:10.1007/978-3-642-38631-2_11.

[8] Lazy computation of the DFA can usually reach the speed of deterministic automatons while keeping worst case behavior similar to simulation of an NFA. However, it is considerably more complex to implement and can use more memory.

[Podcast-9] Jim Manico and Adar Weidman (2009-12-07). "OWASP Podcast 56 (ReDoS)". Retrieved 2010-04-02.

[10] Barlas, Efe; Du, Xin; Davis, James (2022). "सेवा के रेगेक्स इनकार के लिए इनपुट स्वच्छता का शोषण" (PDF). ACM/IEEE International Conference on Software Engineering: 1–14.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]