ஜூலை 2, 2019 அன்று கிளவுட்ஃப்ளேர் செயலிழப்பின் விவரங்கள்

ஏறக்குறைய 9 ஆண்டுகளுக்கு முன்பு Cloudflare ஒரு சிறிய நிறுவனமாக இருந்தது, நான் அதற்காக வேலை செய்யவில்லை, நான் ஒரு வாடிக்கையாளர் மட்டுமே. கிளவுட்ஃப்ளேரைத் தொடங்கி ஒரு மாதத்திற்குப் பிறகு, எனது இணையதளம் குறித்த அறிவிப்பைப் பெற்றேன் jgc.orgDNS வேலை செய்வதாகத் தெரியவில்லை. Cloudflare ஒரு மாற்றத்தை செய்துள்ளது நெறிமுறை இடையகங்கள், மற்றும் உடைந்த DNS இருந்தது.

"எனது DNS எங்கே?" என்ற தலைப்பில் நான் உடனடியாக மத்தேயு பிரின்ஸ்க்கு எழுதினேன், அவர் தொழில்நுட்ப விவரங்கள் நிறைந்த நீண்ட பதிலை அனுப்பினார்.முழு கடிதத்தையும் இங்கே படிக்கவும்), அதற்கு நான் பதிலளித்தேன்:

அனுப்பியவர்: ஜான் கிரஹாம்-கம்மிங்
தேதி: அக்டோபர் 7, 2010, 9:14
தலைப்பு: மறு: எனது DNS எங்கே?
செய்ய: மேத்யூ பிரின்ஸ்

அருமையான அறிக்கை, நன்றி. பிரச்சனைகள் இருந்தால் கண்டிப்பாக அழைப்பேன். நீங்கள் அனைத்து தொழில்நுட்ப தகவல்களையும் சேகரித்தவுடன் இதைப் பற்றி ஒரு இடுகையை எழுதுவது மதிப்புக்குரியது. திறந்த மற்றும் நேர்மையான கதையை மக்கள் ரசிப்பார்கள் என்று நினைக்கிறேன். குறிப்பாக நீங்கள் அதில் வரைபடங்களை இணைத்தால், தொடங்கப்பட்டதிலிருந்து போக்குவரத்து எவ்வாறு வளர்ந்துள்ளது என்பதைக் காட்டவும்.

எனது தளத்தில் எனக்கு நல்ல கண்காணிப்பு உள்ளது, மேலும் ஒவ்வொரு தோல்வி குறித்தும் எனக்கு SMS அனுப்பப்படும். 13:03:07 முதல் 14:04:12 வரை தோல்வி ஏற்பட்டதாக கண்காணிப்பு காட்டுகிறது. ஒவ்வொரு ஐந்து நிமிடங்களுக்கும் சோதனைகள் மேற்கொள்ளப்படுகின்றன.

நீங்கள் அதைக் கண்டுபிடிப்பீர்கள் என்று நான் நம்புகிறேன். ஐரோப்பாவில் உங்கள் சொந்த நபர் உங்களுக்குத் தேவையில்லை என்பதில் உறுதியாக இருக்கிறீர்களா? 🙂

மேலும் அவர் பதிலளித்தார்:

அனுப்பியவர்: மத்தேயு பிரின்ஸ்
தேதி: அக்டோபர் 7, 2010, 9:57
தலைப்பு: மறு: எனது DNS எங்கே?
பெறுநர்: ஜான் கிரஹாம்-கம்மிங்

நன்றி. எழுதிய அனைவருக்கும் நாங்கள் பதிலளித்தோம். நான் இப்போது அலுவலகத்திற்குச் செல்கிறேன், நாங்கள் வலைப்பதிவில் ஏதாவது எழுதுவோம் அல்லது அதிகாரப்பூர்வ இடுகையை எங்கள் புல்லட்டின் போர்டில் பின் செய்வோம். நான் முற்றிலும் ஒப்புக்கொள்கிறேன், நேர்மை தான் எல்லாம்.

இப்போது Cloudflare ஒரு பெரிய நிறுவனம், நான் அதற்காக வேலை செய்கிறேன், இப்போது நான் எங்கள் தவறு, அதன் விளைவுகள் மற்றும் எங்கள் செயல்களைப் பற்றி வெளிப்படையாக எழுத வேண்டும்.

ஜூலை 2 நிகழ்வுகள்

ஜூலை 2 ஆம் தேதி WAFகளுக்கான நிர்வகிக்கப்பட்ட விதிகளில் ஒரு புதிய விதியை நாங்கள் வெளியிட்டோம் CPU ஆதாரங்கள் தீர்ந்துவிட்டன உலகளாவிய கிளவுட்ஃப்ளேர் நெட்வொர்க்கில் HTTP/HTTPS ட்ராஃபிக்கை செயலாக்கும் ஒவ்வொரு செயலி மையத்திலும். புதிய பாதிப்புகள் மற்றும் அச்சுறுத்தல்களுக்கு பதிலளிக்கும் வகையில் WAFகளுக்கான நிர்வகிக்கப்பட்ட விதிகளை நாங்கள் தொடர்ந்து மேம்படுத்தி வருகிறோம். உதாரணமாக, மே மாதத்தில், நாங்கள் விரைந்தோம் விதி சேர்க்கஷேர்பாயிண்டில் ஒரு தீவிர பாதிப்புக்கு எதிராக பாதுகாக்க. எங்கள் WAF இன் முழுப் புள்ளியும் விதிகளை விரைவாகவும் உலகளவில் வரிசைப்படுத்தவும் முடியும்.

துரதிர்ஷ்டவசமாக, கடந்த வியாழன் புதுப்பிப்பில் வழக்கமான வெளிப்பாடு உள்ளது, இது பின்தங்கியதில் அதிக HTTP/HTTPS CPU ஆதாரங்களை வீணடித்தது. இதன் விளைவாக எங்களின் முக்கிய ப்ராக்ஸி, CDN மற்றும் WAF செயல்பாடுகள் பாதிக்கப்பட்டன. HTTP/HTTPS ட்ராஃபிக்கை வழங்குவதற்கான செயலி ஆதாரங்கள் எங்கள் நெட்வொர்க்கில் உள்ள சர்வர்களில் கிட்டத்தட்ட 100% ஐ அடைவதை வரைபடம் காட்டுகிறது.

ஒரு சம்பவத்தின் போது ஒரு இடத்தில் CPU பயன்பாடு

இதன் விளைவாக, எங்கள் வாடிக்கையாளர்கள் (மற்றும் எங்கள் வாடிக்கையாளர்களின் வாடிக்கையாளர்கள்) Cloudflare டொமைன்களில் 502 பிழைப் பக்கத்துடன் முடிந்தது. 502 பிழைகள் கிளவுட்ஃப்ளேர் முன்-இறுதி வலை சேவையகங்களால் உருவாக்கப்பட்டன, அவை இன்னும் இலவச கோர்களைக் கொண்டிருந்தன, ஆனால் HTTP/HTTPS ட்ராஃபிக்கைக் கையாளும் செயல்முறைகளுடன் தொடர்பு கொள்ள முடியவில்லை.

இது எங்கள் வாடிக்கையாளர்களுக்கு எவ்வளவு சிரமத்தை ஏற்படுத்தியுள்ளது என்பது எங்களுக்குத் தெரியும். நாங்கள் மிகவும் வெட்கப்படுகிறோம். இந்த தோல்வி சம்பவத்தை திறம்பட கையாள்வதிலிருந்து எங்களைத் தடுத்தது.

நீங்கள் இந்த வாடிக்கையாளர்களில் ஒருவராக இருந்தால், நீங்கள் பயமாகவும், கோபமாகவும், வருத்தமாகவும் இருக்கலாம். மேலும், எங்களிடம் இல்லை உலகளாவிய இடையூறுகள். அதிக CPU நுகர்வு ஒரு WAF விதியின் காரணமாக ஒரு மோசமான வார்த்தைகள் கொண்ட வழக்கமான வெளிப்பாடாக இருந்தது, இதன் விளைவாக அதிகப்படியான பின்னடைவு ஏற்பட்டது. குற்றவாளியின் வெளிப்பாடு இதோ: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))

இது அதன் சொந்த உரிமையில் சுவாரஸ்யமானது (மேலும் நான் அதைப் பற்றி கீழே விரிவாகப் பேசுகிறேன்), கிளவுட்ஃப்ளேர் சேவையானது மோசமான வழக்கமான வெளிப்பாடு காரணமாக மட்டும் 27 நிமிடங்களுக்கு செயலிழந்தது. தோல்விக்கு வழிவகுத்த நிகழ்வுகளின் வரிசையை விவரிக்க எங்களுக்கு சிறிது நேரம் பிடித்தது, எனவே நாங்கள் பதிலளிக்க மெதுவாக இருந்தோம். இடுகையின் முடிவில், நான் ஒரு வழக்கமான வெளிப்பாட்டில் பின்னடைவை விவரித்து, அதை என்ன செய்வது என்று உங்களுக்குச் சொல்கிறேன்.

என்ன நடந்தது

வரிசையில் ஆரம்பிக்கலாம். இங்கே எல்லா நேரங்களும் UTC இல் உள்ளன.

மதியம் 13:42 மணிக்கு, ஃபயர்வால் குழுவில் உள்ள ஒரு பொறியாளர் கண்டறிதல் விதிகளில் சிறிய மாற்றத்தை செய்தார். XSS என ஒரு தானியங்கி செயல்முறையைப் பயன்படுத்தி. அதன்படி, மாற்ற கோரிக்கை டிக்கெட் உருவாக்கப்பட்டது. அத்தகைய டிக்கெட்டுகளை நாங்கள் ஜிரா மூலம் நிர்வகிக்கிறோம் (கீழே உள்ள ஸ்கிரீன்ஷாட்).

3 நிமிடங்களுக்குப் பிறகு, பேஜர் டூட்டியின் முதல் பக்கம் தோன்றியது, WAF இல் ஒரு சிக்கலைப் புகாரளிக்கிறது. இது சாதாரண செயல்பாட்டைக் கண்காணிக்க கிளவுட்ஃப்ளேருக்கு வெளியே WAF களின் செயல்பாட்டைச் சோதிக்கும் ஒரு செயற்கை சோதனையாகும் (எங்களிடம் நூற்றுக்கணக்கானவை உள்ளன). இதைத் தொடர்ந்து பிற Cloudflare எண்ட்-டு-எண்ட் சேவை சோதனைகள் தோல்வி, உலகளாவிய போக்குவரத்து சிக்கல்கள், பரவலான 502 பிழைகள் மற்றும் உலகெங்கிலும் உள்ள நகரங்களில் உள்ள எங்கள் புள்ளிகள் (PoP) இல் இருந்து ஒரு டன் அறிக்கைகள் பற்றிய விழிப்பூட்டல் பக்கங்கள் வந்தன. CPU வளங்கள்.

இந்த விழிப்பூட்டல்களில் பலவற்றைப் பெற்றேன், கூட்டத்திலிருந்து வெளியேறி, மேசைக்குச் சென்றுகொண்டிருந்தபோது, ​​எங்கள் தீர்வுகள் மேம்பாட்டுத் துறையின் தலைவர் எங்களின் போக்குவரத்தில் 80% இழந்துவிட்டோம் என்று கூறினார். ஏற்கனவே பிரச்சனையில் வேலை செய்து கொண்டிருந்த எங்கள் SRE பொறியாளர்களிடம் ஓடினேன். இது ஏதோ தெரியாத தாக்குதல் என்று முதலில் நினைத்தோம்.

Cloudflare SRE இன்ஜினியர்கள் உலகம் முழுவதும் சிதறிக்கிடக்கின்றனர் மற்றும் கடிகாரத்தைச் சுற்றி நிலைமையைக் கண்காணிக்கின்றனர். பொதுவாக, இந்த விழிப்பூட்டல்கள் வரையறுக்கப்பட்ட நோக்கத்தின் குறிப்பிட்ட உள்ளூர் சிக்கல்களை உங்களுக்குத் தெரிவிக்கும், உள் டாஷ்போர்டுகளில் கண்காணிக்கப்படும், மேலும் ஒரு நாளைக்கு பலமுறை தீர்க்கப்படும். ஆனால் இந்தப் பக்கங்கள் மற்றும் அறிவிப்புகள் மிகவும் தீவிரமான ஒன்றைக் குறிக்கின்றன, மேலும் SRE பொறியாளர்கள் உடனடியாக P0 தீவிரத்தன்மையை அறிவித்து மேலாண்மை மற்றும் கணினி பொறியாளர்களைத் தொடர்பு கொண்டனர்.

எங்கள் லண்டன் பொறியாளர்கள் அந்த நேரத்தில் பிரதான மண்டபத்தில் ஒரு சொற்பொழிவைக் கேட்டுக் கொண்டிருந்தனர். விரிவுரை குறுக்கிடப்பட்டது, அனைவரும் ஒரு பெரிய மாநாட்டு அறையில் கூடினர், மேலும் நிபுணர்கள் அழைக்கப்பட்டனர். இது SRE கள் தங்களைத் தாங்களே சமாளிக்கக்கூடிய பொதுவான பிரச்சனை அல்ல. சரியான நிபுணர்களை ஈடுபடுத்துவது அவசரமானது.

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 அதை உலகளவில் வெளியிட அனுமதிக்கிறது. உண்மையில், Cloudflare இல், விஷயங்கள் முற்றிலும் வித்தியாசமாக செய்யப்படுகின்றன, மேலும் SOP ஆனது சோதனை மற்றும் உள் பயன்பாட்டிற்கான மென்பொருளை முதலில் ஒரு உள் இருப்புக்கு (PoP) (எங்கள் பணியாளர்கள் பயன்படுத்தும்) பின்னர் குறைந்த எண்ணிக்கையிலான வாடிக்கையாளர்களுக்கு அனுப்ப வேண்டும் என்று ஆணையிடுகிறது. ஒரு தனிமைப்படுத்தப்பட்ட இடம், பின்னர் அதிக எண்ணிக்கையிலான வாடிக்கையாளர்களுக்கு, பின்னர் மட்டுமே உலகம் முழுவதும்.

இப்படித்தான் தெரிகிறது. பிட்பக்கெட் வழியாக ஜிட்டை உள்நாட்டில் பயன்படுத்துகிறோம். மாற்றங்களில் பணிபுரியும் பொறியாளர்கள் குறியீட்டை சமர்ப்பிப்பார்கள், இது TeamCity க்கு கட்டமைக்கப்பட்டுள்ளது, மேலும் உருவாக்கம் முடிந்ததும், மதிப்பாய்வாளர்கள் நியமிக்கப்படுவார்கள். ஒரு இழுப்புக் கோரிக்கை அங்கீகரிக்கப்பட்டால், குறியீடு அசெம்பிள் செய்யப்பட்டு, தொடர்ச்சியான சோதனைகள் (மீண்டும்) இயக்கப்படும்.

உருவாக்கம் மற்றும் சோதனைகள் வெற்றிகரமாக முடிந்தால், ஜிராவில் மாற்றக் கோரிக்கை உருவாக்கப்பட்டு, பொருத்தமான மேலாளர் அல்லது முன்னணி மாற்றத்தை அங்கீகரிக்க வேண்டும். ஒப்புதலுக்குப் பிறகு, "PoP மெனகேரி" என்று அழைக்கப்படுவதில் வரிசைப்படுத்தல் ஏற்படுகிறது: DOG, PIG மற்றும் கேனரி (நாய், பன்றி மற்றும் கேனரி).

DOG PoP என்பது Cloudflare PoP ஆகும் (எங்கள் நகரங்களில் உள்ள மற்ற எல்லா நகரங்களையும் போல) இது Cloudflare பணியாளர்களால் மட்டுமே பயன்படுத்தப்படுகிறது. உள் பயன்பாட்டிற்கான PoP வாடிக்கையாளர் ட்ராஃபிக் தீர்வுக்கு வரத் தொடங்கும் முன் சிக்கல்களைப் பிடிக்க உங்களை அனுமதிக்கிறது. பயனுள்ள விஷயம்.

DOG சோதனை வெற்றிகரமாக இருந்தால், குறியீடு PIG (கினிப் பன்றி) நிலைக்கு நகரும். இது Cloudflare PoP ஆகும், இங்கு ஒரு சிறிய அளவு இலவச வாடிக்கையாளர் போக்குவரத்து புதிய குறியீடு மூலம் பாய்கிறது.
எல்லாம் நன்றாக இருந்தால், குறியீடு கேனரிக்கு செல்கிறது. உலகின் பல்வேறு பகுதிகளில் மூன்று கேனரி PoPகள் உள்ளன. அவற்றில், பணம் செலுத்திய மற்றும் இலவச வாடிக்கையாளர்களின் போக்குவரத்து புதிய குறியீடு வழியாக செல்கிறது, மேலும் இது பிழைகளுக்கான கடைசி காசோலை ஆகும்.

Cloudflare இல் மென்பொருள் வெளியீட்டு செயல்முறை

கேனரியில் குறியீடு சரியாக இருந்தால், அதை வெளியிடுவோம். அனைத்து நிலைகளையும் கடந்து செல்ல - நாய், பன்றி, கேனரி, உலகம் முழுவதும் - குறியீடு மாற்றத்தைப் பொறுத்து பல மணிநேரங்கள் அல்லது நாட்கள் ஆகும். Cloudflare இன் நெட்வொர்க் மற்றும் கிளையண்டுகளின் பன்முகத்தன்மை காரணமாக, குறியீட்டை உலகளவில் அனைத்து வாடிக்கையாளர்களுக்கும் வெளியிடுவதற்கு முன் அதை முழுமையாகச் சோதிப்போம். ஆனால் WAF குறிப்பாக இந்த செயல்முறையை பின்பற்றவில்லை, ஏனெனில் அச்சுறுத்தல்களுக்கு விரைவாக பதிலளிக்க வேண்டும்.

WAF அச்சுறுத்தல்கள்
கடந்த சில ஆண்டுகளில், பொதுவான பயன்பாடுகளில் அச்சுறுத்தல்களில் குறிப்பிடத்தக்க அதிகரிப்பு உள்ளது. மென்பொருள் சோதனைக் கருவிகள் அதிக அளவில் கிடைப்பதே இதற்குக் காரணம். உதாரணமாக, நாங்கள் சமீபத்தில் எழுதியது குழப்பம்).

ஆதாரம்: https://cvedetails.com/

பெரும்பாலும், கருத்தின் ஆதாரம் உருவாக்கப்பட்டு உடனடியாக Github இல் வெளியிடப்படுகிறது, இதனால் பயன்பாட்டைப் பராமரிக்கும் குழுக்கள் அதை விரைவாகச் சோதித்து, அது போதுமான அளவு பாதுகாப்பாக இருப்பதை உறுதிசெய்ய முடியும். எனவே, Cloudflare க்கு முடிந்தவரை விரைவாக புதிய தாக்குதல்களுக்கு பதிலளிக்கும் திறன் தேவைப்படுகிறது, இதனால் வாடிக்கையாளர்கள் தங்கள் மென்பொருளை சரிசெய்ய வாய்ப்பு உள்ளது.

Cloudflare இன் விரைவான பதிலுக்கான சிறந்த உதாரணம் மே மாதத்தில் ஷேர்பாயிண்ட் பாதிப்பு பாதுகாப்புகளை பயன்படுத்துவதாகும் (இங்கே வாசிக்கவும்) அறிவிப்புகள் வெளியிடப்பட்ட உடனேயே, எங்கள் வாடிக்கையாளர்களின் ஷேர்பாயிண்ட் நிறுவல்களில் உள்ள பாதிப்பைப் பயன்படுத்திக் கொள்ள ஏராளமான முயற்சிகளை நாங்கள் கவனித்தோம். எங்கள் தோழர்கள் தொடர்ந்து புதிய அச்சுறுத்தல்களைக் கண்காணித்து, எங்கள் வாடிக்கையாளர்களைப் பாதுகாக்க விதிகளை எழுதுகிறார்கள்.

வியாழன் அன்று சிக்கலை ஏற்படுத்திய விதி குறுக்கு-தள ஸ்கிரிப்டிங்கிலிருந்து (XSS) பாதுகாக்க வேண்டும். இதுபோன்ற தாக்குதல்கள் சமீப வருடங்களில் அடிக்கடி நடந்து வருகின்றன.

ஆதாரம்: https://cvedetails.com/

WAF க்கான நிர்வகிக்கப்பட்ட விதியை மாற்றுவதற்கான நிலையான செயல்முறையானது உலகளாவிய வரிசைப்படுத்தலுக்கு முன் தொடர்ச்சியான ஒருங்கிணைப்பு (CI) சோதனையை நடத்துவதாகும். கடந்த வியாழக்கிழமை நாங்கள் இதைச் செய்து விதிகளை உருவாக்கினோம். மதியம் 13:31 மணியளவில், ஒரு பொறியாளர் ஒரு மாற்றத்துடன் அங்கீகரிக்கப்பட்ட இழுப்பு கோரிக்கையை சமர்ப்பித்தார்.

13:37 மணிக்கு TeamCity விதிகளைச் சேகரித்து, சோதனைகளை நடத்தி, முன்னோக்கிச் சென்றது. WAF சோதனைத் தொகுப்பு WAF இன் முக்கிய செயல்பாட்டைச் சோதிக்கிறது மற்றும் தனிப்பட்ட செயல்பாடுகளுக்கான அதிக எண்ணிக்கையிலான யூனிட் சோதனைகளைக் கொண்டுள்ளது. யூனிட் சோதனைகளுக்குப் பிறகு, அதிக எண்ணிக்கையிலான HTTP கோரிக்கைகளைப் பயன்படுத்தி WAF க்கான விதிகளைச் சோதித்தோம். HTTP கோரிக்கைகள் WAF ஆல் எந்த கோரிக்கைகளை தடுக்க வேண்டும் (தாக்குதலை இடைமறிக்க) மற்றும் எதன் மூலம் அனுமதிக்கலாம் (எல்லாவற்றையும் தடுக்காமல் மற்றும் தவறான நேர்மறைகளைத் தவிர்க்க). ஆனால் அதிகப்படியான CPU உபயோகத்தை நாங்கள் சோதிக்கவில்லை, மேலும் முந்தைய WAF பில்ட்களின் பதிவுகளை ஆராய்வது விதி சோதனை செயல்படுத்தும் நேரம் அதிகரிக்கவில்லை என்பதைக் காட்டுகிறது, மேலும் போதுமான ஆதாரங்கள் இல்லை என்று சந்தேகிப்பது கடினம்.

சோதனைகள் கடந்துவிட்டன மற்றும் TeamCity தானாகவே மாற்றத்தை 13:42 p.m.க்கு பயன்படுத்தத் தொடங்கியது.

குவிக்சில்வரின்

WAF விதிகள் உடனடி அச்சுறுத்தல் நிவர்த்தி செய்வதில் கவனம் செலுத்துகின்றன, எனவே Quicksilver இன் விநியோகிக்கப்பட்ட முக்கிய மதிப்பு அங்காடியைப் பயன்படுத்தி அவற்றைப் பயன்படுத்துகிறோம், இது உலகளவில் சில நொடிகளில் மாற்றங்களைப் பரப்புகிறது. டாஷ்போர்டில் அல்லது API வழியாக உள்ளமைவை மாற்றும் போது எங்கள் வாடிக்கையாளர்கள் அனைவரும் இந்தத் தொழில்நுட்பத்தைப் பயன்படுத்துகின்றனர், மேலும் மின்னல் வேகத்தில் மாற்றங்களுக்கு நாங்கள் பதிலளிப்பதற்கு நன்றி.

Quicksilver பற்றி நாங்கள் அதிகம் பேசவில்லை. முன்பு நாங்கள் பயன்படுத்தினோம் கியோட்டோ டைகூன் உலகளவில் விநியோகிக்கப்பட்ட முக்கிய மதிப்புக் கடையாக, ஆனால் அதில் செயல்பாட்டு சிக்கல்கள் இருந்தன, மேலும் நாங்கள் எங்கள் சொந்த கடையை எழுதினோம், 180 க்கும் மேற்பட்ட நகரங்களில் நகலெடுக்கப்பட்டது. வாடிக்கையாளர்களுக்கு உள்ளமைவு மாற்றங்களைத் தள்ளவும், WAF விதிகளைப் புதுப்பிக்கவும், க்ளவுட்ஃப்ளேர் பணியாளர்களுக்கு வாடிக்கையாளர்களால் எழுதப்பட்ட JavaScript குறியீட்டை விநியோகிக்கவும் இப்போது Quicksilver ஐப் பயன்படுத்துகிறோம்.

டாஷ்போர்டில் உள்ள பட்டனைக் கிளிக் செய்வதன் மூலம் அல்லது API ஐ அழைப்பதன் மூலம் உலகம் முழுவதும் உள்ளமைவு மாற்றத்தை உருவாக்க சில வினாடிகள் ஆகும். வாடிக்கையாளர்கள் இந்த அமைப்பின் வேகத்தை விரும்பினர். தொழிலாளர்கள் அவர்களுக்கு கிட்டத்தட்ட உடனடி உலகளாவிய மென்பொருள் வரிசைப்படுத்தலை வழங்குகிறார்கள். சராசரியாக, Quicksilver வினாடிக்கு சுமார் 350 மாற்றங்களை பரப்புகிறது.

மற்றும் குவிக்சில்வர் மிக வேகமாக உள்ளது. உலகெங்கிலும் உள்ள ஒவ்வொரு கணினியிலும் மாற்றங்களைப் பரப்புவதற்கு சராசரியாக, 99 வினாடிகளில் 2,29வது சதவீதத்தை அடைந்துள்ளோம். வேகம் பொதுவாக ஒரு நல்ல விஷயம். எல்லாவற்றிற்கும் மேலாக, நீங்கள் ஒரு செயல்பாட்டை இயக்கும்போது அல்லது தற்காலிக சேமிப்பை அழிக்கும்போது, ​​அது கிட்டத்தட்ட உடனடியாக மற்றும் எல்லா இடங்களிலும் நடக்கும். Cloudflare Workers மூலம் குறியீட்டை அனுப்புவது அதே வேகத்தில் நிகழ்கிறது. Cloudflare அதன் வாடிக்கையாளர்களுக்கு சரியான நேரத்தில் விரைவான புதுப்பிப்புகளை உறுதியளிக்கிறது.

ஆனால் இந்த விஷயத்தில், வேகம் எங்களுக்கு ஒரு கொடூரமான நகைச்சுவையாக விளையாடியது, மேலும் விதிகள் எல்லா இடங்களிலும் சில நொடிகளில் மாறிவிட்டன. WAF குறியீடு லுவாவைப் பயன்படுத்துவதை நீங்கள் கவனித்திருக்கலாம். Cloudflare உற்பத்தி மற்றும் விவரங்களில் லுவாவை விரிவாகப் பயன்படுத்துகிறது WAF இல் லுவா мы ஏற்கனவே விவாதிக்கப்பட்டது. 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க்கான அணுகல் இல்லை, ஏனெனில் அவர்கள் Cloudflare பகுதி வழியாகச் செல்கிறார்கள்.

கடந்த வியாழன் முதல் என்ன மாறிவிட்டது

முதலில், WAFக்கான வெளியீடுகளின் அனைத்து வேலைகளையும் நாங்கள் முற்றிலுமாக நிறுத்திவிட்டு, பின்வருவனவற்றைச் செய்கிறோம்:

1. நாங்கள் அகற்றிய CPU அதிகப்படியான பாதுகாப்பை மீண்டும் அறிமுகப்படுத்துகிறோம். (தயார்)
2. WAF க்கான நிர்வகிக்கப்பட்ட விதிகளில் உள்ள அனைத்து 3868 விதிகளையும் கைமுறையாகச் சரிபார்த்து, அதிகப்படியான பின்னடைவுக்கான பிற சாத்தியமான நிகழ்வுகளைக் கண்டறிந்து சரிசெய்யவும். (சரிபார்ப்பு முடிந்தது)
3. சோதனைத் தொகுப்பில் உள்ள அனைத்து விதிகளுக்கும் செயல்திறன் விவரக்குறிப்பைச் சேர்த்துள்ளோம். (எதிர்பார்க்கப்படும்: ஜூலை 19)
4. வழக்கமான எக்ஸ்பிரஷன் எஞ்சினுக்கு மாறுகிறது re2 அல்லது துரு - இரண்டும் இயக்க நேர உத்தரவாதங்களை வழங்குகின்றன. (எதிர்பார்க்கப்படும்: ஜூலை 31)
5. கிளவுட்ஃப்ளேரில் உள்ள மற்ற மென்பொருட்களைப் போல, நிலைகளில் விதிகளை வரிசைப்படுத்த SOP ஐ மீண்டும் எழுதுகிறோம், ஆனால் அதே நேரத்தில் தாக்குதல்கள் ஏற்கனவே தொடங்கப்பட்டிருந்தால் அவசரகால உலகளாவிய வரிசைப்படுத்தல் திறனைக் கொண்டுள்ளது.
6. Cloudflare பகுதியிலிருந்து Cloudflare டாஷ்போர்டு மற்றும் API ஐ அவசரமாக அகற்றும் திறனை நாங்கள் உருவாக்கி வருகிறோம்.
7. பக்க புதுப்பிப்புகளை தானியங்குபடுத்துகிறது கிளவுட்ஃப்ளேர் நிலை.

சில வருடங்களுக்கு முன்பு நான் எழுதிய Lua 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 после =) எங்களிடம் 20 x இருந்தால் =, இன்ஜின் பொருத்தத்தை 555 படிகளில் நிறைவு செய்கிறது! (மேலும், நாம் இழந்திருந்தால் x= மற்றும் சரம் வெறுமனே 20 ஐக் கொண்டுள்ளது x, எஞ்சின் பொருத்தங்கள் இல்லை என்பதை புரிந்து கொள்ள 4067 படிகளை எடுக்கும்).

இந்த வீடியோ ஒப்பிடுவதற்கான அனைத்து பின்னடைவுகளையும் காட்டுகிறது x=xxxxxxxxxxxxxxxxxxxx:

பிரச்சனை என்னவென்றால், சரத்தின் அளவு அதிகரிக்கும் போது, ​​பொருந்தும் நேரம் மிக நேர்கோட்டில் வளரும். ஆனால் வழக்கமான வெளிப்பாடு சிறிது மாற்றப்பட்டால் விஷயங்கள் இன்னும் மோசமாகிவிடும். நம்மிடம் இருந்தது என்று வைத்துக்கொள்வோம் .*.*=.*; (அதாவது, வடிவத்தின் முடிவில் ஒரு நேரடி அரைப்புள்ளி இருந்தது). எடுத்துக்காட்டாக, போன்ற ஒரு வெளிப்பாட்டைப் பொருத்துவதற்கு foo=bar;.

இங்கே பின்வாங்குவது ஒரு உண்மையான பேரழிவாக இருக்கும். ஒப்பிட்டு x=x அது 90 படிகளை எடுக்கும், 23 அல்ல. அந்த எண்ணிக்கை வேகமாக வளர்ந்து வருகிறது. ஒப்பிடுவதற்கு x= மற்றும் xnumx x, 5353 படிகள் தேவை. இதோ விளக்கப்படம். அச்சு மதிப்புகளைப் பாருங்கள் Y முந்தைய விளக்கப்படத்துடன் ஒப்பிடும்போது.

நீங்கள் ஆர்வமாக இருந்தால், 5353 தோல்வியுற்ற பொருந்தும் படிகளைப் பார்க்கவும் x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;

பேராசை பொருந்தியதை விட சோம்பேறியைப் பயன்படுத்துவதன் மூலம், பின்வாங்கலின் அளவைக் கட்டுப்படுத்தலாம். அசல் வெளிப்பாட்டை மாற்றினால் .*?.*?=.*?, ஒப்பிட்டு x=x இது 11 படிகளை எடுக்கும் (23 அல்ல). போன்ற x=xxxxxxxxxxxxxxxxxxxx. அனைத்து ஏனெனில் ? после .* நகரும் முன் குறைந்தபட்ச எண்ணிக்கையிலான எழுத்துக்களை பொருத்துமாறு இயந்திரத்தை கூறுகிறது.

ஆனால் சோம்பேறி மேப்பிங்குகள் பின்னடைவு சிக்கலை முழுமையாக தீர்க்காது. நாம் பேரழிவு உதாரணத்தை மாற்றினால் .*.*=.*; மீது .*?.*?=.*?;, செயல்படுத்தும் நேரம் அப்படியே இருக்கும். x=x இன்னும் 555 படிகள் தேவை, மற்றும் x= மற்றும் xnumx x - 5353.

செய்யக்கூடிய ஒரே விஷயம் (அதிக விவரக்குறிப்புக்கான வடிவத்தை முழுவதுமாக மீண்டும் எழுதுவதைத் தவிர) வழக்கமான எக்ஸ்பிரஷன் எஞ்சினை அதன் பின்னடைவு பொறிமுறையுடன் கைவிடுவதாகும். இதைத்தான் அடுத்த சில வாரங்களில் செய்வோம்.

1968 ஆம் ஆண்டு கென்ட் தாம்சன் ஒரு கட்டுரை எழுதியதில் இருந்தே இந்த பிரச்சனைக்கான தீர்வு அறியப்பட்டது நிரலாக்க நுட்பங்கள்: வழக்கமான வெளிப்பாடு தேடல் அல்காரிதம் (“நிரலாக்க முறைகள்: வழக்கமான வெளிப்பாடு தேடல் அல்காரிதம்”). வழக்கமான வெளிப்பாட்டை நிர்ணயம் செய்யாத வரையறுக்கப்பட்ட நிலை இயந்திரங்களாக மாற்ற உங்களை அனுமதிக்கும் ஒரு பொறிமுறையை கட்டுரை விவரிக்கிறது.

நிரலாக்க முறைகள்
வழக்கமான வெளிப்பாடு தேடல் அல்காரிதம்
கென் தாம்சன்
பெல் டெலிபோன் லேபரட்டரீஸ், இன்க்., முர்ரே ஹில், நியூ ஜெர்சி

இது உரையில் ஒரு குறிப்பிட்ட எழுத்துக்களைத் தேடுவதற்கான ஒரு முறையை விவரிக்கிறது மற்றும் இந்த முறையை கம்பைலர் வடிவத்தில் செயல்படுத்துவது பற்றி விவாதிக்கிறது. கம்பைலர் வழக்கமான வெளிப்பாட்டை மூலக் குறியீடாக எடுத்துக்கொள்கிறது மற்றும் IBM 7094 நிரலை பொருள் குறியீடாக உருவாக்குகிறது. பொருள் நிரல் தேடல் உரை வடிவில் உள்ளீட்டை எடுத்து ஒவ்வொரு முறையும் கொடுக்கப்பட்ட வழக்கமான வெளிப்பாட்டிற்கு எதிராக உரையின் சரம் பொருத்தப்படும் போது ஒரு சமிக்ஞையை வெளியிடுகிறது. கட்டுரை எடுத்துக்காட்டுகள், சிக்கல்கள் மற்றும் தீர்வுகளை வழங்குகிறது.

வழிமுறை
முந்தைய தேடல் அல்காரிதம்கள், ஓரளவு வெற்றிகரமான தேடல் முடிவைத் தரத் தவறினால், பின்னடைவை ஏற்படுத்தியது.

தொகுத்தல் முறையில், அல்காரிதம் குறியீடுகளுடன் வேலை செய்யாது. இது தொகுக்கப்பட்ட குறியீட்டிற்கான வழிமுறைகளை அனுப்புகிறது. செயல்படுத்தல் மிக வேகமாக உள்ளது - தற்போதைய பட்டியலின் மேல் தரவை அனுப்பிய பிறகு, வழக்கமான வெளிப்பாட்டின் சாத்தியமான அனைத்து தொடர்ச்சியான எழுத்துக்களையும் தானாகவே தேடுகிறது.
தொகுத்தல் மற்றும் தேடல் அல்காரிதம் நேரப் பகிர்வு உரை திருத்தியில் சூழல் தேடலாக சேர்க்கப்பட்டுள்ளது. நிச்சயமாக, இது அத்தகைய தேடல் நடைமுறையின் ஒரே பயன்பாட்டிலிருந்து வெகு தொலைவில் உள்ளது. எடுத்துக்காட்டாக, இந்த அல்காரிதத்தின் மாறுபாடு, அசெம்பிளரில் உள்ள அட்டவணையில் குறியீட்டுத் தேடலாகப் பயன்படுத்தப்படுகிறது.
வழக்கமான வெளிப்பாடுகள் மற்றும் IBM 7094 கணினி நிரலாக்க மொழியை வாசகர் நன்கு அறிந்திருப்பதாகக் கருதப்படுகிறது.

தொகுப்பாளர்
கம்பைலர் இணையாக இயங்கும் மூன்று நிலைகளைக் கொண்டுள்ளது. முதல் நிலை தொடரியல் வடிகட்டுதல் ஆகும், இது தொடரியல் ரீதியாக சரியான வழக்கமான வெளிப்பாடுகளை மட்டுமே கடந்து செல்ல அனுமதிக்கிறது. இந்த படி வழக்கமான வெளிப்பாடுகளுடன் பொருந்த "·" ஆபரேட்டரையும் செருகுகிறது. இரண்டாவது கட்டத்தில், வழக்கமான வெளிப்பாடு போஸ்ட்ஃபிக்ஸ் வடிவத்திற்கு மாற்றப்படுகிறது. மூன்றாவது கட்டத்தில், பொருள் குறியீடு உருவாக்கப்பட்டது. முதல் 2 நிலைகள் வெளிப்படையானவை, நாங்கள் அவற்றில் வசிக்க மாட்டோம்.

தாம்சனின் கட்டுரை நிர்ணயம் செய்யாத வரையறுக்கப்பட்ட நிலை இயந்திரங்களைப் பற்றி பேசவில்லை, ஆனால் அது நேரியல் நேர அல்காரிதத்தை நன்றாக விளக்குகிறது மற்றும் IBM 60 க்கான அசெம்பிளி மொழி குறியீட்டை உருவாக்கும் ALGOL-7094 நிரலை வழங்குகிறது. செயல்படுத்துவது தந்திரமானது, ஆனால் யோசனை மிகவும் எளிமையானது.

தற்போதைய தேடல் பாதை. இது ஒரு உள்ளீடு மற்றும் இரண்டு வெளியீடுகளைக் கொண்ட ⊕ ஐகானால் குறிக்கப்படுகிறது.
வழக்கமான வெளிப்பாடு உதாரணத்தை மாற்றும் போது மூன்றாவது தொகுத்தல் படியின் செயல்பாடுகளை படம் 1 காட்டுகிறது. எடுத்துக்காட்டில் முதல் மூன்று எழுத்துகள் a, b, c, மற்றும் ஒவ்வொன்றும் ஒரு அடுக்கு உள்ளீடு S[i] மற்றும் NNODE புலத்தை உருவாக்குகிறது.

ஒரு ஒற்றை அடுக்கு உள்ளீட்டில் வழக்கமான வெளிப்பாட்டை உருவாக்க ஏற்கனவே உள்ள குறியீட்டிற்கு NNODE (படம் 5 ஐப் பார்க்கவும்)

வழக்கமான வெளிப்பாடு இப்படித்தான் இருக்கும் .*.*=.*, தாம்சனின் கட்டுரையில் உள்ள படங்களில் உள்ளதைப் போல நீங்கள் கற்பனை செய்தால்.

படத்தில். 0 0 முதல் ஐந்து நிலைகள் உள்ளன, மேலும் 3, 1 மற்றும் 2 நிலைகளில் இருந்து தொடங்கும் 3 சுழற்சிகள் உள்ளன. இந்த மூன்று சுழற்சிகளும் மூன்றிற்கு ஒத்திருக்கும். .* வழக்கமான வெளிப்பாட்டில். புள்ளிகள் கொண்ட 3 ஓவல்கள் ஒரு சின்னத்திற்கு ஒத்திருக்கும். ஒரு அடையாளத்துடன் ஓவல் = ஒரு நேரடியான தன்மையுடன் பொருந்துகிறது =. மாநிலம் 4 இறுதியானது. நாம் அதை அடைந்தால், வழக்கமான வெளிப்பாடு பொருந்துகிறது.

வழக்கமான வெளிப்பாடு பொருத்தத்திற்கு அத்தகைய நிலை வரைபடத்தை எவ்வாறு பயன்படுத்தலாம் என்பதைப் பார்க்க .*.*=.*, சரம் பொருத்தத்தைப் பார்ப்போம் x=x. படத்தில் காட்டப்பட்டுள்ளபடி நிரல் நிலை 0 இலிருந்து தொடங்குகிறது. 1.

இந்த அல்காரிதம் வேலை செய்ய, அரசு இயந்திரம் ஒரே நேரத்தில் பல மாநிலங்களில் இருக்க வேண்டும். ஒரு தீர்மானமற்ற வரையறுக்கப்பட்ட இயந்திரம் ஒரே நேரத்தில் சாத்தியமான அனைத்து மாற்றங்களையும் செய்யும்.

உள்ளீட்டுத் தரவைப் படிக்க நேரம் கிடைக்கும் முன், படம் 1 இல் காட்டப்பட்டுள்ளபடி, அது இரண்டு முதல் நிலைகளுக்கு (2 மற்றும் 2) செல்கிறது. XNUMX.

படத்தில். அவர் முதலில் பார்க்கும்போது என்ன நடக்கிறது என்பதை 2 காட்டுகிறது x в x=x. x மாநிலம் 1 இலிருந்து மாநிலம் 1 க்கு செல்லும், மேல் புள்ளி வரை வரைபடத்தை செய்யலாம். அல்லது x மாநிலம் 2 இலிருந்து மாநிலம் 2 க்கு செல்லும், கீழே உள்ள புள்ளிக்கு வரைபடமாக்கலாம்.

முதலில் பொருந்திய பிறகு x в x=x நாங்கள் இன்னும் 1 மற்றும் 2 நிலைகளில் இருக்கிறோம். 3 அல்லது 4 நிலையை எங்களால் அடைய முடியாது, ஏனென்றால் நமக்கு ஒரு எழுத்துப்பூர்வ எழுத்து தேவை. =.

அல்காரிதம் பின்னர் கருதுகிறது = в x=x. இதற்கு முன் x ஐப் போலவே, இது நிலை 1 முதல் நிலை 1 வரை அல்லது நிலை 2 முதல் நிலை 2 வரையிலான முதல் இரண்டு சுழல்களில் ஒன்றைப் பொருத்தலாம், ஆனால் அல்காரிதம் எழுத்துமுறையுடன் பொருந்தலாம் = மற்றும் நிலை 2 இலிருந்து மாநிலம் 3 க்கு நகர்த்தவும் (மற்றும் உடனடியாக 4). இது படத்தில் காட்டப்பட்டுள்ளது. 3.

அல்காரிதம் பின்னர் கடைசி வரை செல்கிறது x в x=x. 1 மற்றும் 2 மாநிலங்களில் இருந்து அதே மாற்றங்கள் 1 மற்றும் 2 மாநிலங்களுக்கு மீண்டும் சாத்தியமாகும். மாநிலம் 3 இலிருந்து x வலதுபுறத்தில் உள்ள புள்ளியை பொருத்தி, நிலை 3 க்கு செல்லலாம்.

இந்த கட்டத்தில், ஒவ்வொரு பாத்திரமும் x=x கருதப்பட்டது, மற்றும் நாம் நிலை 4 ஐ அடைந்துவிட்டதால், வழக்கமான வெளிப்பாடு அந்த சரத்துடன் பொருந்துகிறது. ஒவ்வொரு எழுத்தும் ஒரு முறை செயலாக்கப்படும், எனவே இந்த வழிமுறை உள்ளீட்டு சரத்தின் நீளத்தில் நேர்கோட்டில் இருக்கும். மற்றும் பின்னடைவு இல்லை.

வெளிப்படையாக, நிலை 4 ஐ அடைந்த பிறகு (அல்காரிதம் பொருந்தும் போது x=) முழு வழக்கமான வெளிப்பாடும் பொருந்துகிறது, மேலும் அல்காரிதம் அதைக் கருத்தில் கொள்ளாமல் நிறுத்தப்படலாம் x.

இந்த அல்காரிதம் உள்ளீட்டு சரத்தின் அளவைப் பொறுத்தது.

ஆதாரம்: www.habr.com