जुलाई २, २०१९ मा Cloudflare आउटेजको विवरण

लगभग 9 वर्ष पहिले Cloudflare एउटा सानो कम्पनी थियो, र मैले यसको लागि काम गरिन, म केवल एक ग्राहक थिएँ। क्लाउडफ्लेयर सुरु गरेको एक महिना पछि, मैले एउटा सूचना प्राप्त गरें कि मेरो वेबसाइट jgc.orgDNS ले काम गरिरहेको देखिँदैन। Cloudflare मा परिवर्तन गरिएको छ प्रोटोकल बफरहरू, र त्यहाँ टुटेको DNS थियो।

मैले तुरुन्तै म्याथ्यू प्रिन्सलाई "मेरो DNS कहाँ छ?" शीर्षकको साथ लेखे र उनले प्राविधिक विवरणहरूले भरिएको लामो जवाफ फिर्ता पठाए (यहाँ सम्पूर्ण पत्राचार पढ्नुहोस्), जसलाई मैले जवाफ दिएँ:

बाट: जोन ग्राहम-कमिङ
मिति: अक्टोबर 7, 2010, 9:14
विषय: पुन: मेरो DNS कहाँ छ?
प्रति: म्याथ्यू प्रिन्स

राम्रो रिपोर्ट, धन्यवाद। समस्या परेमा अवश्य फोन गर्नेछु । एकपटक तपाईंले सबै प्राविधिक जानकारी सङ्कलन गरिसकेपछि यसको बारेमा पोष्ट लेख्नु उपयुक्त हुन्छ। मलाई लाग्छ कि मानिसहरूले खुला र इमानदार कथाको आनन्द लिनेछन्। विशेष गरी यदि तपाइँ लन्च पछि ट्राफिक कसरी बढेको छ भनेर देखाउन ग्राफहरू संलग्न गर्नुहुन्छ।

मसँग मेरो साइटमा राम्रो निगरानी छ, र म हरेक असफलताको बारेमा एसएमएस प्राप्त गर्छु। अनुगमनले देखाउँछ कि विफलता 13:03:07 देखि 14:04:12 सम्म भयो। परीक्षणहरू प्रत्येक पाँच मिनेटमा गरिन्छ।

म पक्का छु कि तपाईंले यो पत्ता लगाउनुहुनेछ। के तपाई निश्चित हुनुहुन्छ कि तपाईलाई युरोपमा आफ्नै व्यक्तिको आवश्यकता छैन? 🙂

र उहाँले जवाफ दिनुभयो:

बाट: म्याथ्यू प्रिन्स
मिति: अक्टोबर 7, 2010, 9:57
विषय: पुन: मेरो DNS कहाँ छ?
प्रति: जोन ग्राहम-कमिङ

धन्यवाद। हामीले लेख्ने सबैलाई प्रतिक्रिया दियौं। म अहिले अफिस जाने बाटोमा छु र हामी ब्लगमा केही लेख्ने छौँ वा हाम्रो बुलेटिन बोर्डमा आधिकारिक पोष्ट पिन गर्नेछौँ। म पूर्ण रूपमा सहमत छु, इमानदारी सबै कुरा हो।

अब Cloudflare साँच्चै ठूलो कम्पनी हो, म यसको लागि काम गर्छु, र अब मैले हाम्रो गल्ती, यसको नतिजा र हाम्रा कार्यहरूको बारेमा खुलेर लेख्नु पर्छ।

जुलाई २ का घटनाक्रम

जुलाई २ मा हामीले WAF हरूका लागि व्यवस्थित नियमहरूमा एउटा नयाँ नियम ल्याएका थियौं CPU स्रोतहरू सकिँदै थिए विश्वव्यापी रूपमा क्लाउडफ्लेयर नेटवर्कमा प्रत्येक प्रोसेसर कोर प्रोसेसिंग HTTP/HTTPS ट्राफिकमा। हामी नयाँ कमजोरी र खतराहरूको प्रतिक्रियामा WAF हरूका लागि व्यवस्थित नियमहरू निरन्तर सुधार गर्दैछौं। मेमा, उदाहरणका लागि, हामीले हतार गर्यौं नियम थप्नुहोस्SharePoint मा गम्भीर जोखिमबाट जोगाउन। हाम्रो WAF को सम्पूर्ण बिन्दु छिटो र विश्वव्यापी रूपमा नियमहरू लागू गर्ने क्षमता हो।

दुर्भाग्यवश, गत बिहीबारको अद्यावधिकमा नियमित अभिव्यक्ति समावेश थियो जसले ब्याकट्र्याकिङमा धेरै HTTP/HTTPS CPU स्रोतहरू बर्बाद गर्यो। हाम्रो कोर प्रोक्सी, CDN, र WAF प्रकार्यहरूले परिणामको रूपमा पीडित भयो। ग्राफले HTTP/HTTPS ट्राफिक सेवाका लागि प्रोसेसर स्रोतहरू हाम्रो नेटवर्कमा सर्भरहरूमा लगभग 100% पुग्छ भनी देखाउँछ।

घटनाको समयमा उपस्थितिको एक बिन्दुमा CPU प्रयोग

नतिजाको रूपमा, हाम्रा ग्राहकहरू (र हाम्रा ग्राहकहरूको ग्राहकहरू) क्लाउडफ्लेयर डोमेनहरूमा 502 त्रुटि पृष्ठको साथ समाप्त भयो। 502 त्रुटिहरू क्लाउडफ्लेयर फ्रन्ट-एन्ड वेब सर्भरहरू द्वारा उत्पन्न गरिएको थियो जसमा अझै पनि नि:शुल्क कोरहरू थिए तर HTTP/HTTPS ट्राफिक ह्यान्डलिंग प्रक्रियाहरूसँग सञ्चार गर्न असमर्थ थिए।

हामीलाई थाहा छ यसले हाम्रा ग्राहकहरूलाई कति असुविधा ल्याएको छ। हामी असाध्यै लज्जित छौं। र यो असफलताले हामीलाई घटनासँग प्रभावकारी रूपमा व्यवहार गर्नबाट रोक्यो।

यदि तपाइँ यी ग्राहकहरू मध्ये एक हुनुहुन्थ्यो भने, तपाइँ सायद डराएको, क्रोधित र निराश हुनुहुन्थ्यो। यसबाहेक, हामीसँग भएको छैन विश्वव्यापी अवरोधहरू। उच्च CPU खपत खराब शब्दको नियमित अभिव्यक्तिको साथ एक WAF नियमको कारणले गर्दा अत्यधिक ब्याकट्र्याकिङको परिणाम थियो। यहाँ दोषी अभिव्यक्ति हो: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))

यद्यपि यो आफ्नै अधिकारमा रोचक छ (र म यसको बारेमा तल थप विवरणमा कुरा गर्नेछु), Cloudflare सेवा खराब नियमित अभिव्यक्तिको कारणले मात्र होइन 27 मिनेटको लागि डाउन थियो। हामीलाई असफलता निम्त्याउने घटनाहरूको अनुक्रम वर्णन गर्न केही समय लाग्यो, त्यसैले हामी प्रतिक्रिया दिन ढिलो थियौं। पोष्टको अन्त्यमा, म नियमित अभिव्यक्तिमा ब्याकट्र्याकिङको वर्णन गर्नेछु र तपाईलाई यसको साथ के गर्ने भनेर बताउनेछु।

के भयो

क्रम मा सुरु गरौं। यहाँ सबै समय UTC मा छन्।

13:42 बजे, फायरवाल टोलीका एक इन्जिनियरले पत्ता लगाउने नियमहरूमा सानो परिवर्तन गरे। XSS एक स्वचालित प्रक्रिया प्रयोग गरेर। तदनुसार, एक परिवर्तन अनुरोध टिकट सिर्जना गरियो। हामी त्यस्ता टिकटहरू जिरा (तलको स्क्रिनसट) मार्फत व्यवस्थापन गर्छौं।

3 मिनेट पछि, PagerDuty को पहिलो पृष्ठ देखा पर्‍यो, WAF मा समस्या रिपोर्ट गर्दै। यो एक सिंथेटिक परीक्षण थियो जसले WAFs को कार्यक्षमता परीक्षण गर्दछ (हामीसँग ती सयौं छन्) Cloudflare बाहिर सामान्य सञ्चालन निगरानी गर्न। यो तुरुन्तै अन्य क्लाउडफ्लेयर अन्त-देखि-अन्त सेवा परीक्षणहरू असफल भएको, विश्वव्यापी ट्राफिक समस्याहरू, व्यापक 502 त्रुटिहरू, र विश्वभरका सहरहरूमा हाम्रो उपस्थितिको पोइन्ट (PoP) बाट रिपोर्टहरूको एक टन रिपोर्टहरूको बारेमा सूचनाहरू पछ्याइएको थियो जसले अभावलाई संकेत गर्दछ। CPU स्रोतहरूको।

मैले यी मध्ये धेरै अलर्टहरू प्राप्त गरें, बैठकबाट बाहिर निस्किए, र म टेबलमा जाँदै थिएँ जब हाम्रो समाधान विकास विभागका प्रमुखले भने कि हामीले हाम्रो ट्राफिकको 80% गुमाएका छौं। म हाम्रा SRE इन्जिनियरहरूकहाँ दगुरेँ, जो पहिले नै समस्यामा काम गरिरहेका थिए। सुरुमा हामीले यो कुनै अज्ञात आक्रमण हो भन्ने सोचेका थियौं।

Cloudflare SRE इन्जिनियरहरू संसारभर छरिएका छन् र घडी वरिपरि स्थिति निगरानी। सामान्यतया, यी अलर्टहरूले तपाईंलाई सीमित दायराका विशिष्ट स्थानीय समस्याहरूको बारेमा सूचित गर्दछ, आन्तरिक ड्यासबोर्डहरूमा ट्र्याक गरिन्छ, र प्रति दिन धेरै पटक समाधान गरिन्छ। तर यी पृष्ठहरू र अधिसूचनाहरूले वास्तवमा केहि गम्भीर संकेत गरे, र SRE इन्जिनियरहरूले तुरुन्तै गम्भीरता स्तर P0 घोषणा गरे र व्यवस्थापन र प्रणाली इन्जिनियरहरूलाई सम्पर्क गरे।

हाम्रा लन्डन इन्जिनियरहरू त्यसबेला मुख्य हलमा व्याख्यान सुनिरहेका थिए। व्याख्यान अवरुद्ध हुनुपर्‍यो, सबैजना ठूलो सम्मेलन कोठामा भेला भए, र थप विशेषज्ञहरू बोलाइयो। यो कुनै सामान्य समस्या थिएन जुन SREs ले आफैंसँग सामना गर्न सक्छ। सही विशेषज्ञहरू समावेश गर्न यो अत्यावश्यक थियो।

14:00 मा हामीले निर्धारण गर्यौं कि समस्या WAF मा थियो र त्यहाँ कुनै आक्रमण थिएन। प्रदर्शन टोलीले CPU डाटा तान्यो र यो स्पष्ट भयो कि WAF दोषी थियो। अर्को कर्मचारीले स्ट्रेस प्रयोग गरेर यो सिद्धान्त पुष्टि गरे। कसैले WAF मा समस्या भएको लगहरूमा देख्यो। 14:02 बजे, सम्पूर्ण टोली मकहाँ आयो जब यो विश्वव्यापी हत्याको प्रयोग गर्ने प्रस्ताव गरिएको थियो, क्लाउडफ्लेयरमा निर्मित मेकानिजम जसले विश्वव्यापी रूपमा एउटा कम्पोनेन्ट बन्द गर्छ।

हामीले WAF को लागि कसरी विश्वव्यापी हत्या गर्यौं त्यो फरक कथा हो। यो त्यति सरल छैन। हामी हाम्रो आफ्नै उत्पादनहरू प्रयोग गर्छौं, र हाम्रो सेवा पछि पहुँच काम गरेन, हामीले प्रमाणिकरण गर्न र आन्तरिक नियन्त्रण प्यानलमा लग इन गर्न सकेनौं (जब सबै कुरा ठीक भइसकेको थियो, हामीले थाहा पायौं कि केही टोली सदस्यहरूले सुरक्षा सुविधाको कारणले पहुँच गुमाएका थिए जसले प्रमाणहरू असक्षम पार्छ यदि आन्तरिक नियन्त्रण प्यानल प्रयोग गरिएको छैन भने। लामो समय)।

र हामीले हाम्रो आन्तरिक सेवाहरू, जस्तै जिरा वा निर्माण प्रणालीमा पुग्न सकेनौं। हामीलाई एक वर्कअराउंड मेकानिजम चाहिन्छ, जुन हामीले कहिलेकाहीं प्रयोग गर्यौं (यसलाई पनि काम गर्न आवश्यक छ)। अन्तमा, एक इन्जिनियरले 14:07 मा WAF लाई असक्षम गर्न सफल भयो, र 14:09 मा, ट्राफिक र CPU स्तरहरू जताततै सामान्यमा फर्किए। क्लाउडफ्लेयरको बाँकी सुरक्षा संयन्त्रहरूले सामान्य रूपमा काम गरे।

त्यसपछि हामीले WAF पुनर्स्थापना गर्ने बारे सेट गर्यौं। स्थिति सामान्य भन्दा बाहिर थियो, त्यसैले हामीले नकारात्मक परीक्षणहरू (आफैलाई परिवर्तन वास्तवमा समस्या हो कि भनेर सोध्दै) र सकारात्मक परीक्षणहरू (रोलब्याकले काम गरेको सुनिश्चित गर्दै) छुट्टै ट्राफिक प्रयोग गरेर, त्यहाँबाट भुक्तानी गर्ने ग्राहकहरूलाई स्थानान्तरण गर्यौं।

14:52 मा हामी विश्वस्त भयौं कि हामीले कारण बुझ्यौं र सुधार गर्यौं, र WAF फेरि सक्षम गर्यौं।

Cloudflare कसरी काम गर्दछ

Cloudflare सँग WAF को नियमहरू प्रबन्ध गर्न समर्पित इन्जिनियरहरूको टोली छ। तिनीहरू पत्ता लगाउने दरहरू सुधार गर्न, झूटा सकारात्मकहरूलाई कम गर्न, र नयाँ खतराहरू देखा पर्दा तुरुन्तै प्रतिक्रिया दिन प्रयास गर्छन्। पछिल्लो 60 दिनमा, WAF का लागि व्यवस्थित नियमहरूको लागि 476 परिवर्तन अनुरोधहरू प्रशोधन गरिएका छन् (औसत प्रत्येक 3 घण्टामा एक)।

यो विशेष परिवर्तनलाई सिमुलेशन मोडमा तैनाथ गर्न आवश्यक छ, जहाँ वास्तविक ग्राहक ट्राफिक नियम मार्फत जान्छ, तर केहि पनि रोकिएको छैन। हामी नियमहरूको प्रभावकारिता परीक्षण गर्न र गलत सकारात्मक र गलत नकारात्मक दरहरू मापन गर्न यो मोड प्रयोग गर्छौं। तर सिमुलेशन मोडमा पनि, नियमहरू वास्तवमा कार्यान्वयन हुनैपर्छ, र यस अवस्थामा नियमले नियमित अभिव्यक्ति समावेश गर्दछ जुन धेरै प्रोसेसर स्रोतहरू खपत गरिरहेको थियो।

तपाईले माथिको परिवर्तन अनुरोधबाट देख्न सक्नुहुन्छ, हामीसँग यस प्रकारको परिनियोजनको लागि एक डिप्लोइमेन्ट योजना, रोलब्याक योजना, र आन्तरिक मानक अपरेटिङ प्रोसिजर (SOP) को लिङ्क छ। नियम परिवर्तनको लागि SOP ले यसलाई विश्वव्यापी रूपमा प्रकाशित गर्न अनुमति दिन्छ। वास्तवमा, क्लाउडफ्लेयरमा, चीजहरू पूर्ण रूपमा फरक तरिकाले गरिन्छ, र SOP ले निर्देशन दिन्छ कि हामीले परीक्षण र आन्तरिक प्रयोगको लागि सफ्टवेयरलाई पहिले उपस्थितिको आन्तरिक बिन्दु (PoP) मा पठाउँछौं (जसलाई हाम्रा कर्मचारीहरूले प्रयोग गर्छन्), त्यसपछि ग्राहकहरूको सानो संख्यामा। एक पृथक स्थान, त्यसपछि ग्राहकहरूको ठूलो संख्यामा, र त्यसपछि मात्र सम्पूर्ण संसारमा।

यो जस्तो देखिन्छ। हामी बिटबकेट मार्फत आन्तरिक रूपमा git प्रयोग गर्छौं। परिवर्तनहरूमा काम गर्ने इन्जिनियरहरूले कोड पेस गर्छन्, जुन TeamCity मा बनाइएको छ, र जब निर्माण पास हुन्छ, समीक्षकहरू नियुक्त गरिन्छन्। एक पटक पुल अनुरोध स्वीकृत भएपछि, कोड भेला हुन्छ र परीक्षणहरूको श्रृंखला चलाइन्छ (फेरि)।

यदि निर्माण र परीक्षण सफलतापूर्वक सम्पन्न भयो भने, परिवर्तन अनुरोध जिरामा सिर्जना गरिन्छ र उपयुक्त प्रबन्धक वा नेतृत्वले परिवर्तनलाई अनुमोदन गर्नुपर्छ। स्वीकृति पछि, तैनाती तथाकथित "PoP menagerie" मा हुन्छ: DOG, PIG र क्यानरी (कुकुर, सुँगुर र क्यानरी)।

DOG PoP एक Cloudflare PoP हो (हाम्रो अन्य शहरहरू जस्तै) जुन क्लाउडफ्लेयर कर्मचारीहरूले मात्र प्रयोग गर्छन्। आन्तरिक प्रयोगको लागि PoP ले तपाईंलाई ग्राहक ट्राफिक समाधानमा प्रवाहित हुनु अघि समस्याहरू समात्न अनुमति दिन्छ। उपयोगी कुरा।

यदि DOG परीक्षण सफल भयो भने, कोड PIG (गिनीपिग) चरणमा सर्छ। यो Cloudflare PoP हो, जहाँ थोरै मात्रामा नि:शुल्क ग्राहक ट्राफिक नयाँ कोड मार्फत प्रवाह हुन्छ।
यदि सबै ठीक छ भने, कोड क्यानरीमा जान्छ। हामीसँग संसारका विभिन्न भागहरूमा तीन क्यानरी PoPs छन्। तिनीहरूमा, सशुल्क र नि: शुल्क ग्राहकहरूको ट्राफिक नयाँ कोड मार्फत जान्छ, र यो त्रुटिहरूको लागि अन्तिम जाँच हो।

Cloudflare मा सफ्टवेयर रिलीज प्रक्रिया

यदि कोड क्यानरीमा ठीक छ भने, हामी यसलाई जारी गर्छौं। सबै चरणहरू मार्फत जाँदै - DOG, PIG, Canary, सम्पूर्ण संसार - कोड परिवर्तनको आधारमा धेरै घण्टा वा दिन लाग्छ। क्लाउडफ्लेयरको नेटवर्क र क्लाइन्टहरूको विविधताको कारणले गर्दा, हामी सबै ग्राहकहरूलाई विश्वव्यापी रूपमा जारी गर्नु अघि कोडको राम्रोसँग परीक्षण गर्छौं। तर WAF ले यो प्रक्रियालाई विशेष रूपमा पछ्याउँदैन किनभने धम्कीहरूलाई छिट्टै जवाफ दिन आवश्यक छ।

WAF धम्की
विगत केही वर्षहरूमा, सामान्य अनुप्रयोगहरूमा खतराहरूमा उल्लेखनीय वृद्धि भएको छ। यो सफ्टवेयर परीक्षण उपकरणहरूको अधिक उपलब्धताको कारण हो। उदाहरणका लागि, हामीले भर्खरै लेखेका छौं फज्जिङ).

स्रोत: https://cvedetails.com/

धेरै पटक, अवधारणाको प्रमाण सिर्जना गरिन्छ र तुरुन्तै Github मा प्रकाशित गरिन्छ ताकि अनुप्रयोगलाई कायम राख्ने टोलीहरूले यसलाई द्रुत रूपमा परीक्षण गर्न र यो पर्याप्त रूपमा सुरक्षित छ भनेर सुनिश्चित गर्न सकून्। तसर्थ, Cloudflare लाई सकेसम्म चाँडो नयाँ आक्रमणहरूमा प्रतिक्रिया दिन सक्ने क्षमता चाहिन्छ ताकि ग्राहकहरूले आफ्नो सफ्टवेयर ठीक गर्ने अवसर पाउँछन्।

Cloudflare को द्रुत प्रतिक्रिया को एक उत्कृष्ट उदाहरण मे मा SharePoint जोखिम सुरक्षा को तैनाती हो (यहाँ पढ्नुहोस्)। घोषणाहरू गरिसकेपछि लगभग तुरुन्तै, हामीले हाम्रा ग्राहकहरूको SharePoint स्थापनाहरूमा भेद्यताको शोषण गर्ने ठूलो संख्यामा प्रयासहरू देख्यौं। हाम्रा केटाहरूले हाम्रा ग्राहकहरूको सुरक्षा गर्न नयाँ धम्कीहरू र लेख्ने नियमहरू निरन्तर निगरानी गरिरहेका छन्।

बिहीबार समस्या निम्त्याएको नियमले क्रस-साइट स्क्रिप्टिङ (XSS) विरुद्ध सुरक्षा गर्नु पर्ने थियो। त्यस्ता आक्रमणहरू पनि पछिल्ला वर्षहरूमा धेरै पटक भएका छन्।

स्रोत: https://cvedetails.com/

WAF को लागि व्यवस्थित नियम परिवर्तन गर्ने मानक प्रक्रिया भनेको विश्वव्यापी परिनियोजन अघि निरन्तर एकीकरण (CI) परीक्षण सञ्चालन गर्नु हो। गत बिहीबार हामीले यो गर्यौं र नियमहरू रोल आउट गर्यौं। 13:31 बजे, एक इन्जिनियरले परिवर्तनको साथ स्वीकृत पुल अनुरोध पेश गरे।

13:37 मा TeamCity ले नियमहरू सङ्कलन गर्‍यो, परीक्षणहरू दौड्यो र अगाडि बढ्यो। WAF परीक्षण सुइटले WAF को मुख्य कार्यक्षमता परीक्षण गर्दछ र व्यक्तिगत कार्यहरूको लागि ठूलो संख्यामा एकाइ परीक्षणहरू समावेश गर्दछ। एकाइ परीक्षण पछि, हामीले धेरै संख्यामा HTTP अनुरोधहरू प्रयोग गरेर WAF को लागि नियमहरू परीक्षण गर्यौं। HTTP अनुरोधहरूले WAF (आक्रमण रोक्न) र कुन मार्फत अनुमति दिन सकिन्छ (सबै कुरा रोक्न र गलत सकारात्मकबाट बच्न) द्वारा अवरुद्ध गर्ने अनुरोधहरू जाँच गर्दछ। तर हामीले अत्यधिक CPU प्रयोगको लागि परीक्षण गरेनौं, र अघिल्लो WAF निर्माणहरूको लगहरू जाँच गर्दा नियम परीक्षण कार्यान्वयन समय बढेको छैन, र पर्याप्त स्रोतहरू छैनन् भन्ने शंका गर्न गाह्रो थियो।

परीक्षणहरू उत्तीर्ण भयो र TeamCity ले 13:42 p.m. मा परिवर्तन स्वतः तैनाथ गर्न थाल्यो।

quicksilver

WAF नियमहरू तत्काल खतरा निवारणमा केन्द्रित छन्, त्यसैले हामी तिनीहरूलाई Quicksilver को वितरित कुञ्जी-मूल्य भण्डार प्रयोग गरेर प्रयोग गर्छौं, जसले सेकेन्डमा विश्वव्यापी रूपमा परिवर्तनहरू प्रचार गर्छ। हाम्रा सबै ग्राहकहरूले ड्यासबोर्डमा वा एपीआई मार्फत कन्फिगरेसन परिवर्तन गर्दा यो प्रविधि प्रयोग गर्छन्, र यसको लागि धन्यवाद हो कि हामीले बिजुलीको गतिमा परिवर्तनहरूलाई प्रतिक्रिया दिन्छौं।

हामीले Quicksilver को बारेमा धेरै कुरा गरेका छैनौं। पहिले हामीले प्रयोग गर्यौं क्योटो टाइकुन विश्वव्यापी रूपमा वितरित कुञ्जी-मूल्य भण्डारको रूपमा, तर त्यहाँ सञ्चालन समस्याहरू थिए, र हामीले हाम्रो आफ्नै स्टोर लेख्यौं, 180 भन्दा बढी शहरहरूमा प्रतिलिपि गरिएको। हामी अब क्लाइन्टहरूमा कन्फिगरेसन परिवर्तनहरू पुश गर्न, WAF नियमहरू अद्यावधिक गर्न, र क्लाउडफ्लेयर कार्यकर्ताहरूलाई क्लाइन्टहरूद्वारा लेखिएको JavaScript कोड वितरण गर्न Quicksilver प्रयोग गर्छौं।

यसले ड्यासबोर्डको बटन क्लिक गर्न वा विश्वव्यापी कन्फिगरेसन परिवर्तन गर्न API लाई कल गर्न केही सेकेन्ड मात्र लिन्छ। ग्राहकहरूले सेटअपको यो गति मन पराए। र कामदारहरूले तिनीहरूलाई लगभग तत्काल विश्वव्यापी सफ्टवेयर तैनाती दिन्छ। औसतमा, Quicksilver ले प्रति सेकेन्ड लगभग 350 परिवर्तनहरू प्रचार गर्दछ।

र Quicksilver धेरै छिटो छ। औसतमा, हामीले 99 सेकेन्डको 2,29 औं पर्सेन्टाइल हासिल गर्‍यौं जसले विश्वव्यापी रूपमा प्रत्येक कम्प्युटरमा परिवर्तनहरू प्रचार गर्‍यौं। गति सामान्यतया राम्रो कुरा हो। आखिर, जब तपाइँ एक प्रकार्य सक्षम गर्नुहुन्छ वा क्यास खाली गर्नुहुन्छ, यो लगभग तुरुन्तै र जताततै हुन्छ। Cloudflare कार्यकर्ताहरू मार्फत कोड पठाउने कार्य उही गतिमा हुन्छ। क्लाउडफ्लेयरले आफ्ना ग्राहकहरूलाई सही समयमा छिटो अपडेटहरू दिने वाचा गर्दछ।

तर यस अवस्थामा, गतिले हामीलाई क्रूर मजाक खेल्यो, र नियमहरू सेकेन्डको कुरामा जताततै परिवर्तन भयो। तपाईंले याद गर्नुभएको होला कि WAF कोडले Lua प्रयोग गर्दछ। Cloudflare ले उत्पादन र विवरणहरूमा व्यापक रूपमा लुआ प्रयोग गर्दछ WAF मा Lua हामी पहिले नै छलफल। Lua WAF प्रयोग गर्दछ PCRE आन्तरिक रूपमा र मिलानको लागि ब्याकट्र्याकिङ लागू गर्दछ। नियन्त्रण बाहिर निस्कने अभिव्यक्तिहरूबाट जोगाउने कुनै संयन्त्र छैन। तल म यस बारे थप कुरा गर्नेछु र हामी यसको बारेमा के गर्दैछौं।

नियमहरू तैनाथ गर्नु अघि, सबै कुरा सहज रूपमा गयो: पुल अनुरोध सिर्जना गरियो र स्वीकृत गरियो, CI/CD पाइपलाइन सङ्कलन र कोड परीक्षण गरियो, परिनियोजन र रोलब्याकलाई नियन्त्रण गर्ने SOP अनुसार परिवर्तन अनुरोध पेश गरिएको थियो, र तैनाती पूरा भयो।

Cloudflare WAF तैनाती प्रक्रिया

केहि गलत भयो
मैले भनेझैं, हामी हरेक हप्ता दर्जनौं नयाँ WAF नियमहरू प्रयोग गर्छौं, र त्यस्ता तैनातीका नकारात्मक परिणामहरूबाट जोगाउन हामीसँग धेरै प्रणालीहरू छन्। र जब केहि गलत हुन्छ, यो सामान्यतया एकै पटक धेरै परिस्थितिहरूको संयोजन हो। यदि तपाईंले एउटा मात्र कारण फेला पार्नुभयो भने, यो, निस्सन्देह, आश्वस्त छ, तर यो सधैं सत्य हुँदैन। यी कारणहरू हुन् जसले सँगै हाम्रो HTTP/HTTPS सेवाको विफलता निम्त्यायो।

1. एक इन्जिनियरले नियमित अभिव्यक्ति लेखे जुन अत्यधिक परिणाम हुन सक्छ ब्याकट्र्याकिङ.
2. एक विशेषता जसले नियमित अभिव्यक्तिलाई धेरै CPU बर्बाद गर्नबाट रोक्न सक्छ, धेरै हप्ता अघि WAF को रिफ्याक्टरिङमा गल्तीले हटाइएको थियो — WAF लाई कम स्रोतहरू खपत गर्न रिफ्याक्टरिङ आवश्यक थियो।
3. नियमित अभिव्यक्ति इन्जिनमा कुनै जटिलता ग्यारेन्टी थिएन।
4. परीक्षण सुइटले अत्यधिक CPU खपत पत्ता लगाउन सकेन।
5. SOP ले गैर-अत्यावश्यक नियम परिवर्तनहरूलाई बहु-चरण प्रक्रिया बिना विश्वव्यापी रूपमा रोल आउट गर्न अनुमति दिन्छ।
6. रोलब्याक योजनालाई पूर्ण WAF निर्माण दुई पटक चलाउन आवश्यक छ, जसले लामो समय लियो।
7. विश्वव्यापी ट्राफिक समस्याहरूको बारेमा पहिलो चेतावनी धेरै ढिलो ट्रिगर गरिएको थियो।
8. हामीले स्थिति पृष्ठ अपडेट गर्न केही समय लियौं।
9. हामीलाई त्रुटिको कारण प्रणालीहरू पहुँच गर्न समस्याहरू थिए, र बाइपास प्रक्रिया राम्रोसँग स्थापित थिएन।
10. SRE इन्जिनियरहरूले केही प्रणालीहरूमा पहुँच गुमाए किनभने तिनीहरूको प्रमाणहरू सुरक्षा कारणहरूले गर्दा समाप्त भयो।
11. हाम्रा ग्राहकहरूसँग Cloudflare ड्यासबोर्ड वा API मा पहुँच थिएन किनभने तिनीहरू क्लाउडफ्लेयर क्षेत्रबाट जान्छन्।

गत बिहीबार देखि के परिवर्तन भयो

पहिले, हामीले WAF को लागि रिलीजहरूमा सबै काम पूर्ण रूपमा रोक्यौं र निम्न गर्दैछौं:

1. हामीले हटाएको CPU अति प्रयोग सुरक्षालाई हामी पुन: प्रस्तुत गर्दैछौं। (तयार)
2. अत्यधिक ब्याकट्र्याकिङका अन्य सम्भावित केसहरू फेला पार्न र सच्याउन WAF का लागि व्यवस्थित नियमहरूमा म्यानुअल रूपमा सबै 3868 नियमहरू जाँच गर्दै। (प्रमाणीकरण पूरा भयो)
3. हामीले परीक्षण सेटमा सबै नियमहरूको लागि प्रदर्शन प्रोफाइल समावेश गर्दछ। (अपेक्षित: जुलाई १९)
4. नियमित अभिव्यक्ति इन्जिनमा स्विच गर्दै re2 वा खियाले - दुबै रनटाइम ग्यारेन्टीहरू प्रदान गर्दछ। (अपेक्षित: जुलाई 31)
5. हामी क्लाउडफ्लेयरमा अन्य सफ्टवेयरहरू जस्तै चरणहरूमा नियमहरू लागू गर्न SOP पुन: लेखिरहेका छौं, तर आक्रमणहरू सुरु भइसकेका खण्डमा एकै समयमा आपतकालीन विश्वव्यापी तैनाती गर्ने क्षमता छ।
6. हामी Cloudflare क्षेत्रबाट Cloudflare ड्यासबोर्ड र API लाई तुरुन्तै हटाउने क्षमता विकास गर्दैछौं।
7. स्वचालित पृष्ठ अद्यावधिकहरू Cloudflare स्थिति.

लामो अवधि हामी लुआ WAF बाट टाढा जाँदैछौं जुन मैले केहि वर्ष पहिले लेखेको थिएँ। WAF मा सार्दै नयाँ फायरवाल प्रणाली। यस तरिकाले WAF छिटो हुनेछ र सुरक्षाको अतिरिक्त स्तर प्राप्त गर्नेछ।

निष्कर्षमा

यो असफलताले हामीलाई र हाम्रा ग्राहकहरूलाई समस्या ल्यायो। हामीले परिस्थितिलाई सुधार्नको लागि द्रुत रूपमा कार्य गर्यौं र अहिले क्र्यास हुने प्रक्रियाहरूमा भएका त्रुटिहरूमा काम गर्दैछौं, साथै नयाँ प्रविधिमा माइग्रेट गर्दा भविष्यमा नियमित अभिव्यक्तिहरूसँग सम्भावित समस्याहरूबाट जोगाउन अझ गहिरो खन्ने काम गरिरहेका छौं।

हामी यस आउटेज को लागी धेरै लज्जित छौं र हाम्रा ग्राहकहरु संग माफी चाहन्छौं। हामी आशा गर्छौं कि यी परिवर्तनहरूले यस्तो कुरा फेरि नदोहोरियोस् भनेर सुनिश्चित गर्नेछ।

आवेदन। ब्याकट्र्याक नियमित अभिव्यक्ति

अभिव्यक्ति कसरी बुझ्नको लागि:

(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))

सबै CPU स्रोतहरू खाए, तपाईंलाई मानक नियमित अभिव्यक्ति इन्जिनले कसरी काम गर्छ भन्ने बारे थोरै जान्न आवश्यक छ। यहाँ समस्या ढाँचा हो .*(?:.*=.*). (?: र अनुरूप ) एक गैर-कैप्चरिंग समूह हो (अर्थात, कोष्ठकमा अभिव्यक्तिलाई एकल अभिव्यक्तिको रूपमा समूहबद्ध गरिएको छ)।

अत्यधिक CPU खपतको सन्दर्भमा, यो ढाँचाको रूपमा वर्णन गर्न सकिन्छ .*.*=.*। यस फारममा, ढाँचा अनावश्यक रूपमा जटिल देखिन्छ। तर अझ महत्त्वपूर्ण कुरा, वास्तविक संसारमा, अभिव्यक्तिहरू (जस्तै WAF नियमहरूमा जटिल अभिव्यक्तिहरू) जसले इन्जिनलाई एउटा टुक्रासँग मिलाउन सोध्ने अर्को टुक्राले विनाशकारी ब्याकट्र्याक गर्न सक्छ। र त्यही कारणले।

नियमित अभिव्यक्तिमा . यसको मतलब तपाईले एउटा क्यारेक्टरसँग मेल खानुपर्छ, .* - शून्य वा बढी क्यारेक्टरहरू "लोभपूर्वक" मिलाउनुहोस्, त्यो हो, अधिकतम क्यारेक्टरहरू क्याप्चर गर्दै, ताकि .*.*=.* मतलब शून्य वा बढी क्यारेक्टरहरू मिलाउनुहोस्, त्यसपछि शून्य वा बढी क्यारेक्टरहरू मिलाउनुहोस्, शाब्दिक = क्यारेक्टर फेला पार्नुहोस्, शून्य वा बढी क्यारेक्टरहरू मिलाउनुहोस्।

परीक्षण लाइन लिऔं x=x। यो अभिव्यक्ति संग मेल खान्छ .*.*=.*. .*.* बराबर चिन्ह पहिलोसँग मेल खानु अघि x (समूह मध्ये एक .* यससँग सम्बन्धित छ x, र दोस्रो - शून्य वर्ण)। .* पछि = अन्तिम मिलान x.

यो तुलना 23 चरणहरू आवश्यक छ। पहिलो समूह .* в .*.*=.* लोभपूर्वक कार्य गर्दछ र सम्पूर्ण स्ट्रिङसँग मेल खान्छ x=x। इन्जिन अर्को समूहमा जान्छ .*। हामीसँग मिलाउनको लागि कुनै पनि क्यारेक्टरहरू छैनन्, त्यसैले दोस्रो समूह .* शून्य क्यारेक्टरहरूसँग मेल खान्छ (यो अनुमति छ)। त्यसपछि इन्जिन चिन्हमा सर्छ =। त्यहाँ कुनै थप प्रतीकहरू छैनन् (पहिलो समूह .* सम्पूर्ण अभिव्यक्ति प्रयोग गरे x=x), कुनै तुलना हुँदैन।

र त्यसपछि नियमित अभिव्यक्ति इन्जिन सुरुमा फर्कन्छ। ऊ पहिलो समूहमा जान्छ .* र तुलना गर्छ с x= (सट्टा x=x), र त्यसपछि दोस्रो समूह लिन्छ .*। दोस्रो समूह .* दोस्रोसँग तुलना गरिन्छ x, र हामीसँग फेरि कुनै पात्रहरू बाँकी छैनन्। र जब इन्जिन फेरि पुग्छ = в .*.*=.*, केहि काम गर्दैन। र ऊ फेरि पछि हट्छ।

यस पटक समूह .* अझै मिल्छ x=, तर दोस्रो समूह .* अब छैन x, र शून्य वर्णहरू। इन्जिन शाब्दिक क्यारेक्टर फेला पार्न प्रयास गर्दैछ = ढाँचामा .*.*=.*, तर बाहिर आउँदैन (यसपछि, पहिलो समूहले यसलाई कब्जा गरिसकेको छ .*)। र ऊ फेरि पछि हट्छ।

यस पटक पहिलो समूह .* पहिलो x मात्र लिन्छ। तर दोस्रो समूह .* "लोभी" कब्जा =x। के तपाईंले पहिले नै अनुमान गर्नुभएको छ के हुनेछ? इन्जिन शाब्दिक मिलाउन प्रयास गर्दछ =, असफल हुन्छ र अर्को ब्याकट्र्याक गर्छ।

पहिलो समूह .* अझै पनि पहिलोसँग मेल खान्छ x। दोस्रो .* मात्र लिन्छ =। निस्सन्देह, इन्जिन शाब्दिक मेल गर्न सक्दैन =, किनभने दोस्रो समूहले पहिले नै यो गरिसकेको छ .*। र फेरि पछाडि हट्दै। र हामी तीन क्यारेक्टरहरूको स्ट्रिङ मिलाउन प्रयास गर्दैछौं!

फलस्वरूप, पहिलो समूह .* पहिलोसँग मात्र मेल खान्छ x, दोस्रो .* - शून्य वर्ण संग, र इन्जिन अन्ततः शाब्दिक मेल खान्छ = अभिव्यक्ति मा с = क्रममा। अर्को अन्तिम समूह हो .* पछिल्लो एक संग तुलना गरिएको छ x.

23 चरणहरूका लागि मात्र x=x। Perl प्रयोग गर्ने बारे छोटो भिडियो हेर्नुहोस् Regexp::Debugger, जसले चरणहरू र ब्याकट्र्याकिंग कसरी हुन्छ भनेर देखाउँछ।

यो पहिले नै धेरै काम छ, तर यसको सट्टा के हुन्छ x=x हामीसँग हुनेछ x=xx? त्यो 33 कदम हो। र यदि x=xxx? 45. सम्बन्ध रैखिक छैन। ग्राफले तुलना देखाउँछ x=x गर्न x=xxxxxxxxxxxxxxxxxxxx (20 x после =)। यदि हामीसँग २० x पछि छ =, इन्जिनले 555 चरणहरूमा मिलान पूरा गर्दछ! (यदि हामीले हारेका छौं भने x= र स्ट्रिङमा मात्र 20 हुन्छ x, इन्जिनले 4067 कदम लिन्छ कि त्यहाँ कुनै मिल्दो छैन भनेर बुझ्न)।

यो भिडियोले तुलनाको लागि सबै ब्याकट्र्याकिंग देखाउँछ x=xxxxxxxxxxxxxxxxxxxx:

समस्या यो हो कि स्ट्रिङ साइज बढ्दै जाँदा, मिल्दो समय सुपर-रेखीय रूपमा बढ्छ। तर नियमित अभिव्यक्ति अलिकति परिमार्जन गरियो भने चीजहरू अझ खराब हुन सक्छ। हामीसँग थियो भनौं .*.*=.*; (अर्थात, ढाँचाको अन्त्यमा शाब्दिक अर्धविराम थियो)। उदाहरणका लागि, जस्तै अभिव्यक्ति मिलाउन foo=bar;.

र यहाँ ब्याकट्र्याकिङ एक वास्तविक आपदा हुनेछ। तुलना को लागी x=x यसले 90 होइन, 23 कदम लिन्छ। र त्यो संख्या द्रुत रूपमा बढ्दैछ। तुलना गर्नु x= र 20 x, 5353 चरणहरू आवश्यक छ। यहाँ चार्ट छ। अक्ष मानहरू हेर्नुहोस् Y अघिल्लो चार्टको तुलनामा।

यदि तपाइँ इच्छुक हुनुहुन्छ भने, सबै 5353 असफल मिल्दो चरणहरू जाँच गर्नुहोस् x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;

लोभी मिलानको सट्टा अल्छी प्रयोग गरेर, ब्याकट्र्याकिंगको हदलाई नियन्त्रण गर्न सकिन्छ। यदि हामी मौलिक अभिव्यक्तिमा परिवर्तन गर्छौं .*?.*?=.*?, तुलना को लागी x=x यसले 11 चरणहरू लिनेछ (23 होइन)। को लागी x=xxxxxxxxxxxxxxxxxxxx। सबै कारण ? после .* इन्जिनलाई अगाडि बढ्नु अघि न्यूनतम अक्षरहरू मिलाउन भन्छ।

तर अल्छी म्यापिङहरूले ब्याकट्र्याकिङ समस्यालाई पूर्ण रूपमा समाधान गर्दैन। यदि हामी विनाशकारी उदाहरण प्रतिस्थापन गर्छौं .*.*=.*; मा .*?.*?=.*?;, कार्यान्वयन समय समान रहनेछ। x=x अझै 555 चरणहरू आवश्यक छ, र x= र 20 x - 5353।

एक मात्र कुरा गर्न सकिन्छ (बढी विशिष्टताको लागि ढाँचा पूर्ण रूपमा पुन: लेख्नु बाहेक) यसको ब्याकट्र्याकिङ मेकानिजमको साथ नियमित अभिव्यक्ति इन्जिन त्याग्नु हो। यो हामी आगामी केही हप्ताहरूमा के गर्दैछौं।

यस समस्याको समाधान 1968 देखि थाहा छ, जब केन्ट थम्पसनले एक लेख लेखे प्रोग्रामिङ प्रविधिहरू: नियमित अभिव्यक्ति खोज एल्गोरिथ्म ("प्रोग्रामिङ विधिहरू: नियमित अभिव्यक्ति खोज एल्गोरिथ्म")। लेखले एक संयन्त्रको वर्णन गर्दछ जसले तपाईंलाई नियमित अभिव्यक्तिलाई गैर-निर्धारित परिमित राज्य मेसिनहरूमा रूपान्तरण गर्न अनुमति दिन्छ, र गैर-निर्धारित परिमित राज्य मेसिनहरूमा राज्य परिवर्तन पछि, एल्गोरिदम प्रयोग गर्नुहोस् जसको कार्यान्वयन समय मिल्दो स्ट्रिङमा रैखिक रूपमा निर्भर हुन्छ।

प्रोग्रामिङ विधिहरू
नियमित अभिव्यक्ति खोज एल्गोरिथ्म
केन थम्पसन
बेल टेलिफोन प्रयोगशाला, इंक, मरे हिल, न्यू जर्सी

यसले पाठमा क्यारेक्टरहरूको विशिष्ट स्ट्रिङ खोज्ने विधिको वर्णन गर्दछ र कम्पाइलर फारममा यो विधिको कार्यान्वयनको बारेमा छलफल गर्दछ। कम्पाइलरले स्रोत कोडको रूपमा नियमित अभिव्यक्ति लिन्छ र वस्तु कोडको रूपमा IBM 7094 कार्यक्रम उत्पादन गर्दछ। वस्तु कार्यक्रमले खोज पाठको रूपमा इनपुट लिन्छ र प्रत्येक पटक पाठको स्ट्रिङ दिइएको रेगुलर एक्सप्रेशनसँग मेल खाँदा सिग्नल उत्सर्जन गर्दछ। लेख उदाहरण, समस्या र समाधान प्रदान गर्दछ।

एल्गोरिथ्म
अघिल्लो खोज एल्गोरिदमहरू ब्याकट्र्याकिङमा परिणत हुन्छ यदि आंशिक रूपमा सफल खोजले परिणाम उत्पादन गर्न असफल भयो।

संकलन मोडमा, एल्गोरिथ्मले प्रतीकहरूसँग काम गर्दैन। यसले संकलित कोडमा निर्देशनहरू पास गर्दछ। कार्यान्वयन धेरै छिटो छ - हालको सूचीको शीर्षमा डाटा पास गरेपछि, यसले स्वचालित रूपमा नियमित अभिव्यक्तिमा सबै सम्भावित लगातार क्यारेक्टरहरू खोज्छ।
कम्पाइलेशन र खोज एल्गोरिथ्मलाई समय-साझेदारी पाठ सम्पादकमा प्रासंगिक खोजको रूपमा समावेश गरिएको छ। निस्सन्देह, यो यस्तो खोज प्रक्रिया को एक मात्र आवेदन देखि टाढा छ। उदाहरण को लागी, यो एल्गोरिथ्म को एक भेरियन्ट एसेम्बलर मा तालिका मा प्रतीक खोज को रूप मा प्रयोग गरिन्छ।
यो मानिन्छ कि पाठक नियमित अभिव्यक्ति र IBM 7094 कम्प्युटर प्रोग्रामिङ भाषा संग परिचित छ।

कम्पाइलर
कम्पाइलरले समानान्तरमा चलिरहेको तीन चरणहरू समावेश गर्दछ। पहिलो चरण सिन्ट्याक्स फिल्टरिङ हो, जसले सिन्ट्याक्टिक रूपमा मात्र सही रेगुलर एक्सप्रेशनहरू पार गर्न अनुमति दिन्छ। यो चरणले नियमित अभिव्यक्तिहरू मिलाउन "·" अपरेटर पनि घुसाउँछ। दोस्रो चरणमा, नियमित अभिव्यक्ति पोस्टफिक्स फारममा रूपान्तरण हुन्छ। तेस्रो चरणमा, वस्तु कोड सिर्जना गरिएको छ। पहिलो 2 चरणहरू स्पष्ट छन्, र हामी तिनीहरूमा बस्ने छैनौं।

Thompson को लेख nondeterministic सीमित राज्य मिसिनहरु को बारे मा कुरा गर्दैन, तर यो रैखिक समय एल्गोरिथ्म राम्रो संग व्याख्या गर्दछ र IBM 60 को लागि विधानसभा भाषा कोड उत्पन्न गर्ने ALGOL-7094 कार्यक्रम प्रस्तुत गर्दछ। कार्यान्वयन कठिन छ, तर विचार धेरै सरल छ।

हालको खोज मार्ग। यो एक इनपुट र दुई आउटपुट संग ⊕ प्रतिमा द्वारा प्रतिनिधित्व गरिएको छ।
चित्र 1 ले नियमित अभिव्यक्ति उदाहरण रूपान्तरण गर्दा तेस्रो संकलन चरणको कार्यहरू देखाउँछ। उदाहरणमा पहिलो तीन क्यारेक्टरहरू a, b, c हुन्, र प्रत्येकले स्ट्याक प्रविष्टि S[i] र NNODE फिल्ड सिर्जना गर्दछ।

एकल स्ट्याक प्रविष्टिमा नतिजा नियमित अभिव्यक्ति उत्पन्न गर्न अवस्थित कोडमा NNODE (चित्र 5 हेर्नुहोस्)

यो नियमित अभिव्यक्ति जस्तो देखिन्छ .*.*=.*, यदि तपाइँ यसलाई थम्पसनको लेखबाट चित्रहरूमा जस्तै कल्पना गर्नुहुन्छ।

चित्रमा। ० त्यहाँ ० बाट सुरु हुने पाँच राज्यहरू छन्, र राज्य 0, 0 र 3 बाट सुरु हुने 1 चक्रहरू छन्। यी तीन चक्रहरू तीनसँग मेल खान्छ। .* नियमित अभिव्यक्तिमा। थोप्लाहरू भएका ३ ओभलहरू एउटा प्रतीकसँग मेल खान्छ। चिन्हको साथ ओवल = शाब्दिक क्यारेक्टरसँग मेल खान्छ =। प्रदेश ४ फाइनल छ । यदि हामी यसमा पुग्छौं भने, नियमित अभिव्यक्ति मिल्छ।

यस्तो अवस्था रेखाचित्र नियमित अभिव्यक्ति मिलानको लागि कसरी प्रयोग गर्न सकिन्छ भनेर हेर्नको लागि .*.*=.*, हामी स्ट्रिङ मिलान हेर्नेछौं x=x। कार्यक्रम राज्य ० बाट सुरु हुन्छ, जस्तै चित्रमा देखाइएको छ। १.

यो एल्गोरिदम काम गर्नको लागि, राज्य मेसिन एकै साथ धेरै राज्यहरूमा हुनुपर्छ। एक गैर-निर्धारित परिमित मेसिनले सबै सम्भावित संक्रमणहरू एकैसाथ गर्नेछ।

यसमा इनपुट डेटा पढ्नको लागि समय हुनु अघि, यो चित्रमा देखाइएझैं दुवै पहिलो अवस्था (1 र 2) मा जान्छ। २.

चित्रमा। 2 ले देखाउँछ के हुन्छ जब उसले पहिलो हेर्छ x в x=x. x राज्य १ बाट फर्केर राज्य १ मा जाँदै, शीर्ष बिन्दुमा नक्सा गर्न सक्छ। वा x राज्य 2 बाट र राज्य 2 मा फर्केर तलको बिन्दुमा नक्सा गर्न सक्छ।

पहिलो मिलेपछि x в x=x हामी अझै राज्य 1 र 2 मा छौं। हामी राज्य 3 वा 4 मा पुग्न सक्दैनौं किनभने हामीलाई शाब्दिक वर्ण चाहिन्छ =.

त्यसपछि एल्गोरिदमले विचार गर्छ = в x=x। यो भन्दा पहिले x जस्तै, यो राज्य 1 देखि राज्य 1 वा राज्य 2 देखि राज्य 2 मा शीर्ष दुई लूप मध्ये कुनै एकसँग मिलाउन सकिन्छ, तर एल्गोरिथ्मले शाब्दिकसँग मेल खान सक्छ। = र राज्य 2 बाट राज्य 3 मा जानुहोस् (र तुरुन्तै 4)। यो चित्र मा देखाइएको छ। ३.

एल्गोरिदम त्यसपछि अन्तिममा जान्छ x в x=x। राज्य १ र २ बाट राज्य १ र २ मा उही संक्रमण सम्भव छ। राज्य ३ बाट x दायाँको बिन्दुसँग मिलाउन सक्छ र राज्य 3 मा फर्कन सक्छ।

यस चरणमा, प्रत्येक पात्र x=x विचार गरियो, र हामी राज्य 4 मा पुगेकाले, नियमित अभिव्यक्ति त्यो स्ट्रिङसँग मेल खान्छ। प्रत्येक क्यारेक्टर एक पटक प्रशोधन गरिन्छ, त्यसैले यो एल्गोरिदम इनपुट स्ट्रिङको लम्बाइमा रैखिक हुन्छ। र पछाडि हट्ने छैन।

स्पष्ट रूपमा, राज्य 4 पुगेपछि (जब एल्गोरिथ्म मिलेको छ x=) सम्पूर्ण नियमित अभिव्यक्ति मिलेको छ, र एल्गोरिथ्म यसलाई विचार नगरी समाप्त हुन सक्छ x.

यो एल्गोरिदम इनपुट स्ट्रिङको आकारमा रैखिक रूपमा निर्भर गर्दछ।

स्रोत: www.habr.com