รายละเอียดการหยุดทำงานของ Cloudflare ในวันที่ 2 กรกฎาคม 2019

เกือบ 9 ปีที่แล้ว Cloudflare เป็นบริษัทเล็กๆ และฉันไม่ได้ทำงานให้ ฉันเป็นเพียงลูกค้าเท่านั้น หนึ่งเดือนหลังจากเปิดตัว Cloudflare ฉันได้รับการแจ้งเตือนว่าเว็บไซต์ของฉัน jgc.orgดูเหมือนว่า DNS จะไม่ทำงาน Cloudflare ได้ทำการเปลี่ยนแปลง โปรโตคอลบัฟเฟอร์และมี DNS ที่เสียหาย

ฉันเขียนถึง Matthew Prince ทันทีพร้อมหัวข้อ “DNS ของฉันอยู่ที่ไหน” และเขาก็ตอบกลับยาวๆ เต็มไปด้วยรายละเอียดทางเทคนิค (อ่านจดหมายทั้งหมดที่นี่) ซึ่งฉันตอบกลับไปว่า:

จาก: จอห์น เกรแฮม-คัมมิง
วันที่: 7 ตุลาคม 2010, 9:14 น
หัวข้อ: Re: DNS ของฉันอยู่ที่ไหน
ถึง: แมทธิว พรินซ์

รายงานเยี่ยมครับ ขอบคุณครับ ฉันจะโทรไปแน่นอนหากมีปัญหา มันอาจจะคุ้มค่าที่จะเขียนโพสต์เกี่ยวกับเรื่องนี้เมื่อคุณรวบรวมข้อมูลทางเทคนิคทั้งหมดแล้ว ฉันคิดว่าผู้คนจะเพลิดเพลินกับเรื่องราวที่เปิดกว้างและตรงไปตรงมา โดยเฉพาะอย่างยิ่งหากคุณแนบกราฟเพื่อแสดงให้เห็นว่าปริมาณการเข้าชมเพิ่มขึ้นนับตั้งแต่เปิดตัว

ฉันมีการตรวจสอบที่ดีบนเว็บไซต์ของฉัน และฉันได้รับ SMS เกี่ยวกับความล้มเหลวทุกครั้ง การตรวจสอบแสดงให้เห็นว่าความล้มเหลวเกิดขึ้นตั้งแต่ 13:03:07 น. ถึง 14:04:12 น. การทดสอบจะดำเนินการทุกๆ ห้านาที

ฉันแน่ใจว่าคุณจะเข้าใจมัน คุณแน่ใจหรือว่าคุณไม่ต้องการคนของคุณเองในยุโรป? 🙂

และเขาก็ตอบว่า:

จาก: แมทธิว พรินซ์
วันที่: 7 ตุลาคม 2010, 9:57 น
หัวข้อ: Re: DNS ของฉันอยู่ที่ไหน
ถึง: จอห์น เกรแฮม-คัมมิง

ขอบคุณ เราตอบกลับทุกคนที่เขียน ตอนนี้ฉันกำลังเดินทางไปออฟฟิศ เราจะเขียนอะไรบางอย่างในบล็อกหรือปักหมุดโพสต์อย่างเป็นทางการบนกระดานข่าวของเรา ฉันเห็นด้วยอย่างยิ่ง ความซื่อสัตย์คือทุกสิ่ง

ตอนนี้ Cloudflare เป็นบริษัทที่ใหญ่มาก ฉันทำงานเพื่อมัน และตอนนี้ฉันต้องเขียนอย่างเปิดเผยเกี่ยวกับความผิดพลาดของเรา ผลที่ตามมา และการกระทำของเรา

เหตุการณ์ในวันที่ 2 กรกฎาคม

ในวันที่ 2 กรกฎาคม เราได้เผยแพร่กฎใหม่ในกฎที่ได้รับการจัดการสำหรับ WAF ด้วยเหตุนี้ ทรัพยากร CPU กำลังจะหมด บนโปรเซสเซอร์ทุกคอร์ที่ประมวลผลการรับส่งข้อมูล HTTP/HTTPS บนเครือข่าย Cloudflare ทั่วโลก เรากำลังปรับปรุงกฎที่ได้รับการจัดการสำหรับ WAF อย่างต่อเนื่องเพื่อตอบสนองต่อช่องโหว่และภัยคุกคามใหม่ๆ เช่น ในเดือนพฤษภาคม เรารีบ เพิ่มกฎเพื่อป้องกันช่องโหว่ร้ายแรงใน SharePoint จุดรวมของ WAF ของเราคือความสามารถในการปรับใช้กฎทั่วโลกได้อย่างรวดเร็ว

น่าเสียดายที่การอัปเดตเมื่อวันพฤหัสบดีที่ผ่านมามีนิพจน์ทั่วไปที่สิ้นเปลืองทรัพยากร CPU HTTP/HTTPS มากเกินไปในการย้อนรอย ส่งผลให้ฟังก์ชันพร็อกซีหลัก, CDN และ WAF ของเราได้รับผลกระทบ กราฟแสดงให้เห็นว่าทรัพยากรตัวประมวลผลสำหรับการให้บริการการรับส่งข้อมูล HTTP/HTTPS เข้าถึงเกือบ 100% บนเซิร์ฟเวอร์ในเครือข่ายของเรา

การใช้งาน CPU ณ จุดหนึ่งที่ปรากฏระหว่างเหตุการณ์

ด้วยเหตุนี้ ลูกค้าของเรา (และลูกค้าของเรา) จึงพบหน้าข้อผิดพลาด 502 ในโดเมน Cloudflare ข้อผิดพลาด 502 ถูกสร้างขึ้นโดยเว็บเซิร์ฟเวอร์ส่วนหน้าของ Cloudflare ซึ่งยังคงมีคอร์ที่ว่าง แต่ไม่สามารถสื่อสารกับกระบวนการที่จัดการการรับส่งข้อมูล HTTP/HTTPS

เรารู้ว่าสิ่งนี้ทำให้เกิดความไม่สะดวกแก่ลูกค้าของเรามากเพียงใด เราละอายใจอย่างยิ่ง และความล้มเหลวนี้ทำให้เราไม่สามารถรับมือกับเหตุการณ์ดังกล่าวได้อย่างมีประสิทธิภาพ

หากคุณเป็นหนึ่งในลูกค้าเหล่านี้ คุณอาจรู้สึกกลัว โกรธ และอารมณ์เสีย ยิ่งกว่านั้นเรายังไม่มี การหยุดชะงักทั่วโลก. ปริมาณการใช้ CPU สูงเกิดจากกฎ WAF หนึ่งกฎที่มีนิพจน์ทั่วไปที่ใช้คำไม่ดี ซึ่งส่งผลให้มีการย้อนรอยมากเกินไป นี่คือการแสดงออกถึงความผิด: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))

แม้ว่าสิ่งนี้จะน่าสนใจในตัวมันเอง (และฉันจะพูดถึงมันโดยละเอียดด้านล่าง) บริการ Cloudflare หยุดทำงานเป็นเวลา 27 นาที ไม่เพียงเพราะนิพจน์ทั่วไปที่ไม่ดีเท่านั้น เราใช้เวลาสักพักในการอธิบายลำดับเหตุการณ์ที่นำไปสู่ความล้มเหลว ดังนั้นเราจึงตอบกลับช้า ในตอนท้ายของโพสต์ ฉันจะอธิบายการย้อนรอยด้วยสำนวนปกติและบอกคุณว่าต้องทำอย่างไร

เกิดอะไรขึ้น

มาเริ่มกันตามลำดับ เวลาทั้งหมดที่นี่เป็นเวลา UTC

เมื่อเวลา 13:42 น. วิศวกรในทีมไฟร์วอลล์ได้ทำการเปลี่ยนแปลงกฎการตรวจจับเล็กน้อย XSS โดยใช้กระบวนการอัตโนมัติ ดังนั้นจึงมีการสร้างตั๋วคำขอเปลี่ยนแปลง เราจัดการตั๋วดังกล่าวผ่าน Jira (ภาพหน้าจอด้านล่าง)

หลังจากผ่านไป 3 นาที หน้าแรกของ PagerDuty ก็ปรากฏขึ้น โดยรายงานปัญหากับ WAF นี่เป็นการทดสอบสังเคราะห์ที่ทดสอบการทำงานของ WAF (เรามีหลายร้อยรายการ) นอก Cloudflare เพื่อตรวจสอบการทำงานปกติ ตามมาด้วยหน้าการแจ้งเตือนเกี่ยวกับความล้มเหลวในการทดสอบบริการแบบ end-to-end อื่นๆ ของ Cloudflare ปัญหาการรับส่งข้อมูลทั่วโลก ข้อผิดพลาด 502 ที่แพร่หลาย และรายงานมากมายจาก Points of Presence (PoP) ของเราในเมืองต่างๆ ทั่วโลกที่บ่งชี้ถึงการขาด ของทรัพยากร CPU

ฉันได้รับการแจ้งเตือนเหล่านี้หลายครั้ง รีบออกจากการประชุม และกำลังเดินไปที่โต๊ะ เมื่อหัวหน้าแผนกพัฒนาโซลูชันของเราบอกว่าเราสูญเสียการรับส่งข้อมูลไป 80% ฉันรีบไปพบวิศวกร SRE ของเราซึ่งกำลังแก้ไขปัญหาอยู่แล้ว ตอนแรกเราคิดว่ามันเป็นการโจมตีที่ไม่รู้จัก

วิศวกร Cloudflare SRE กระจายอยู่ทั่วโลกและติดตามสถานการณ์ตลอดเวลา โดยทั่วไปแล้ว การแจ้งเตือนเหล่านี้จะแจ้งให้คุณทราบถึงปัญหาเฉพาะในพื้นที่ซึ่งมีขอบเขตจำกัด มีการติดตามบนแดชบอร์ดภายใน และได้รับการแก้ไขหลายครั้งต่อวัน แต่หน้าและการแจ้งเตือนเหล่านี้บ่งชี้ถึงบางสิ่งที่ร้ายแรงจริงๆ และวิศวกร SRE ก็ประกาศระดับความรุนแรง P0 ทันที และติดต่อฝ่ายบริหารและวิศวกรระบบ

วิศวกรในลอนดอนของเรากำลังฟังการบรรยายในห้องโถงใหญ่ในขณะนั้น การบรรยายต้องหยุดชะงักลง ทุกคนมารวมตัวกันในห้องประชุมขนาดใหญ่ และเรียกผู้เชี่ยวชาญมาเพิ่ม นี่ไม่ใช่ปัญหาทั่วไปที่ SRE สามารถจัดการได้ด้วยตนเอง เป็นเรื่องเร่งด่วนที่จะต้องเกี่ยวข้องกับผู้เชี่ยวชาญที่เหมาะสม

เมื่อเวลา 14:00 น. เราพบว่าปัญหาอยู่ที่ WAF และไม่มีการโจมตี ทีมประสิทธิภาพดึงข้อมูล CPU และเห็นได้ชัดว่า WAF เป็นผู้ตำหนิ พนักงานอีกคนยืนยันทฤษฎีนี้โดยใช้ strace มีคนอื่นเห็นในบันทึกว่ามีปัญหากับ WAF เมื่อเวลา 14:02 น. ทีมงานทั้งหมดมาหาฉันเมื่อมีการเสนอให้ใช้การฆ่าทั่วโลก ซึ่งเป็นกลไกที่สร้างไว้ใน Cloudflare ที่จะปิดองค์ประกอบเดียวทั่วโลก

วิธีที่เราสังหาร WAF ทั่วโลกเป็นอีกเรื่องหนึ่ง มันไม่ง่ายอย่างนั้น เราใช้ผลิตภัณฑ์ของเราเองและเนื่องจากบริการของเรา ทางเข้า ใช้งานไม่ได้ เราไม่สามารถตรวจสอบสิทธิ์และเข้าสู่แผงควบคุมภายในได้ (เมื่อทุกอย่างได้รับการแก้ไขแล้ว เราได้เรียนรู้ว่าสมาชิกในทีมบางคนสูญเสียการเข้าถึงเนื่องจากคุณลักษณะด้านความปลอดภัยที่ปิดใช้งานข้อมูลประจำตัวหากไม่ได้ใช้แผงควบคุมภายในสำหรับ เวลานาน).

และเราไม่สามารถเข้าถึงบริการภายในของเรา เช่น Jira หรือระบบบิลด์ได้ เราต้องการกลไกการแก้ปัญหาซึ่งเราใช้ไม่บ่อยนัก (ซึ่งจะต้องมีการแก้ไขด้วย) ในที่สุด วิศวกรคนหนึ่งสามารถปิดการใช้งาน WAF ได้ในเวลา 14:07 น. และเวลา 14:09 น. ระดับการรับส่งข้อมูลและ CPU กลับมาเป็นปกติทุกที่ กลไกการป้องกันที่เหลือของ Cloudflare ทำงานตามปกติ

จากนั้นเราก็เริ่มกู้คืน WAF สถานการณ์ไม่ปกติ ดังนั้นเราจึงทำการทดสอบเชิงลบ (ถามตัวเองว่าการเปลี่ยนแปลงเป็นปัญหาจริงๆ หรือไม่) และการทดสอบเชิงบวก (ตรวจสอบให้แน่ใจว่าการย้อนกลับใช้งานได้) ในเมืองหนึ่งโดยใช้การจราจรแยกกัน และโอนลูกค้าที่ชำระเงินจากที่นั่น

เมื่อเวลา 14:52 น. เรามั่นใจว่าเราเข้าใจเหตุผลแล้ว และทำการแก้ไข และเปิดใช้งาน WAF อีกครั้ง

Cloudflare ทำงานอย่างไร

Cloudflare มีทีมวิศวกรที่ทุ่มเทในการจัดการกฎสำหรับ WAF พวกเขามุ่งมั่นที่จะปรับปรุงอัตราการตรวจจับ ลดผลบวกลวง และตอบสนองต่อภัยคุกคามใหม่ๆ อย่างรวดเร็วเมื่อเกิดขึ้น ในช่วง 60 วันที่ผ่านมา มีคำขอเปลี่ยนแปลง 476 คำขอที่ประมวลผลสำหรับกฎที่ได้รับการจัดการสำหรับ WAF (โดยเฉลี่ย 3 คำขอทุกๆ XNUMX ชั่วโมง)

การเปลี่ยนแปลงเฉพาะนี้จำเป็นต้องปรับใช้ในโหมดจำลอง ซึ่งการรับส่งข้อมูลไคลเอนต์จริงผ่านกฎ แต่ไม่มีสิ่งใดถูกบล็อก เราใช้โหมดนี้เพื่อทดสอบประสิทธิภาพของกฎและวัดอัตราผลบวกลวงและผลลบลวง แต่แม้จะอยู่ในโหมดการจำลอง กฎก็ต้องถูกดำเนินการจริง และในกรณีนี้ กฎนั้นมีนิพจน์ทั่วไปที่ใช้ทรัพยากรตัวประมวลผลมากเกินไป

ดังที่คุณเห็นจากคำขอเปลี่ยนแปลงข้างต้น เรามีแผนการปรับใช้ แผนการย้อนกลับ และลิงก์ไปยังขั้นตอนการปฏิบัติงานมาตรฐานภายใน (SOP) สำหรับการปรับใช้ประเภทนี้ SOP สำหรับการเปลี่ยนแปลงกฎทำให้สามารถเผยแพร่ได้ทั่วโลก จริงๆ แล้ว ที่ Cloudflare สิ่งต่างๆ ต่างไปจากเดิมอย่างสิ้นเชิง และ SOP กำหนดให้เราจัดส่งซอฟต์แวร์สำหรับการทดสอบและการใช้งานภายในไปยัง Internal Point of Presence (PoP) ก่อน (ซึ่งพนักงานของเราใช้) จากนั้นจึงจัดส่งให้กับลูกค้าจำนวนไม่มากใน สถานที่ที่ห่างไกลจากลูกค้าจำนวนมาก และเฉพาะทั่วโลกเท่านั้น

นี่คือสิ่งที่ดูเหมือน เราใช้ git ภายในผ่าน BitBucket วิศวกรที่ทำงานเกี่ยวกับการเปลี่ยนแปลงจะส่งโค้ดซึ่งสร้างขึ้นสำหรับ TeamCity และเมื่อการสร้างผ่าน จะมีการกำหนดผู้ตรวจสอบ เมื่อคำขอการดึงได้รับการอนุมัติ โค้ดจะถูกรวบรวมและรันชุดการทดสอบ (อีกครั้ง)

หากการสร้างและการทดสอบเสร็จสมบูรณ์ ระบบจะสร้างคำขอเปลี่ยนแปลงใน Jira และผู้จัดการหรือลูกค้าเป้าหมายที่เหมาะสมจะต้องอนุมัติการเปลี่ยนแปลง หลังจากได้รับอนุมัติแล้ว การปรับใช้จะเกิดขึ้นในส่วนที่เรียกว่า "โรงเลี้ยงสัตว์ PoP": DOG, PIG และ นกขมิ้น (สุนัข หมู และนกคีรีบูน)

DOG PoP คือ Cloudflare PoP (เช่นเดียวกับเมืองอื่นๆ ของเรา) ที่พนักงาน Cloudflare ใช้เท่านั้น PoP สำหรับการใช้งานภายในช่วยให้คุณตรวจพบปัญหาก่อนที่การรับส่งข้อมูลของลูกค้าจะเริ่มไหลเข้าสู่โซลูชัน สิ่งที่มีประโยชน์

หากการทดสอบ DOG สำเร็จ โค้ดจะย้ายไปยังระยะ PIG (หนูตะเภา) นี่คือ Cloudflare PoP ที่ปริมาณการรับส่งข้อมูลของลูกค้าฟรีจำนวนเล็กน้อยไหลผ่านโค้ดใหม่
หากทุกอย่างเรียบร้อยดี โค้ดจะเข้าสู่ Canary เรามี Canary PoP สามแห่งในส่วนต่างๆ ของโลก ในนั้นการรับส่งข้อมูลของลูกค้าแบบชำระเงินและฟรีจะผ่านรหัสใหม่และนี่คือการตรวจสอบข้อผิดพลาดครั้งสุดท้าย

กระบวนการเผยแพร่ซอฟต์แวร์ที่ Cloudflare

หากรหัสนั้นใช้ได้ใน Canary เราจะปล่อยมัน การผ่านทุกด่าน - DOG, PIG, Canary, ทั่วโลก - ใช้เวลาหลายชั่วโมงหรือหลายวัน ขึ้นอยู่กับการเปลี่ยนแปลงรหัส เนื่องจากความหลากหลายของเครือข่ายและไคลเอนต์ของ Cloudflare เราจึงทดสอบโค้ดอย่างละเอียดก่อนที่จะเผยแพร่ให้กับลูกค้าทุกคนทั่วโลก แต่ WAF ไม่ได้ปฏิบัติตามกระบวนการนี้โดยเฉพาะ เนื่องจากภัยคุกคามจำเป็นต้องได้รับการตอบสนองอย่างรวดเร็ว

ภัยคุกคามจาก WAF
ในช่วงไม่กี่ปีที่ผ่านมา มีภัยคุกคามเพิ่มขึ้นอย่างมากในแอปพลิเคชันทั่วไป นี่เป็นเพราะเครื่องมือทดสอบซอฟต์แวร์มีความพร้อมใช้งานมากขึ้น ตัวอย่างเช่นเราเพิ่งเขียนเกี่ยวกับ คลุมเครือ).

ที่มา: https://cvedetails.com/

บ่อยครั้งที่มีการพิสูจน์แนวคิดและเผยแพร่ทันทีบน Github เพื่อให้ทีมที่ดูแลแอปพลิเคชันสามารถทดสอบได้อย่างรวดเร็วและมั่นใจได้ว่ามีความปลอดภัยเพียงพอ ดังนั้น Cloudflare จึงต้องการความสามารถในการตอบสนองต่อการโจมตีใหม่ๆ โดยเร็วที่สุด เพื่อให้ลูกค้ามีโอกาสซ่อมแซมซอฟต์แวร์ของตน

ตัวอย่างที่ดีของการตอบสนองที่รวดเร็วของ Cloudflare คือการปรับใช้การป้องกันช่องโหว่ของ SharePoint ในเดือนพฤษภาคม (อ่านที่นี่). เกือบจะในทันทีหลังจากมีการประกาศ เราสังเกตเห็นความพยายามจำนวนมากในการใช้ประโยชน์จากช่องโหว่ในการติดตั้ง SharePoint ของลูกค้าของเรา พวกเราคอยติดตามภัยคุกคามใหม่ๆ และเขียนกฎเกณฑ์เพื่อปกป้องลูกค้าของเราอย่างต่อเนื่อง

กฎที่ทำให้เกิดปัญหาในวันพฤหัสบดีควรจะป้องกันการเขียนสคริปต์ข้ามไซต์ (XSS) การโจมตีดังกล่าวเกิดขึ้นบ่อยครั้งมากขึ้นในช่วงไม่กี่ปีที่ผ่านมา

ที่มา: https://cvedetails.com/

ขั้นตอนมาตรฐานสำหรับการเปลี่ยนแปลงกฎที่ได้รับการจัดการสำหรับ WAF คือการดำเนินการทดสอบการรวมอย่างต่อเนื่อง (CI) ก่อนที่จะปรับใช้ทั่วโลก เมื่อวันพฤหัสบดีที่แล้ว เราทำสิ่งนี้และเปิดตัวกฎเกณฑ์ต่างๆ เมื่อเวลา 13:31 น. วิศวกรได้ส่งคำขอดึงที่ได้รับอนุมัติพร้อมการเปลี่ยนแปลง

เวลา 13:37 น. TeamCity รวบรวมกฎ ดำเนินการทดสอบ และดำเนินการต่อไป ชุดทดสอบ WAF จะทดสอบฟังก์ชันการทำงานหลักของ WAF และประกอบด้วยการทดสอบหน่วยจำนวนมากสำหรับแต่ละฟังก์ชัน หลังจากการทดสอบหน่วย เราได้ทดสอบกฎสำหรับ WAF โดยใช้คำขอ HTTP จำนวนมาก คำขอ HTTP ตรวจสอบว่าคำขอใดควรถูกบล็อกโดย WAF (เพื่อสกัดกั้นการโจมตี) และคำขอใดที่สามารถอนุญาตได้ (เพื่อไม่ให้บล็อกทุกอย่างและหลีกเลี่ยงผลบวกลวง) แต่เราไม่ได้ทดสอบการใช้งาน CPU มากเกินไป และการตรวจสอบบันทึกของ WAF บิวด์ก่อนหน้านี้แสดงให้เห็นว่าเวลาดำเนินการทดสอบกฎไม่เพิ่มขึ้น และเป็นการยากที่จะสงสัยว่าจะมีทรัพยากรไม่เพียงพอ

การทดสอบผ่านไป และ TeamCity เริ่มปรับใช้การเปลี่ยนแปลงโดยอัตโนมัติเมื่อเวลา 13:42 น.

ปรอท

กฎ WAF มุ่งเน้นไปที่การแก้ไขภัยคุกคามในทันที ดังนั้นเราจึงปรับใช้โดยใช้การจัดเก็บคีย์-ค่าแบบกระจายของ Quicksilver ซึ่งเผยแพร่การเปลี่ยนแปลงทั่วโลกในไม่กี่วินาที ลูกค้าของเราทุกคนใช้เทคโนโลยีนี้เมื่อพวกเขาเปลี่ยนการกำหนดค่าในแดชบอร์ดหรือผ่านทาง API และต้องขอบคุณสิ่งนี้ที่เราตอบสนองต่อการเปลี่ยนแปลงอย่างรวดเร็ว

เราไม่ค่อยได้พูดถึง Quicksilver มากนัก เมื่อก่อนเราใช้ เกียวโต ไทคูน ในฐานะร้านค้าคีย์-ค่าที่กระจายทั่วโลก แต่มีปัญหาในการดำเนินงาน และเราจึงเขียนร้านค้าของเราเอง ซึ่งจำลองแบบในกว่า 180 เมือง ตอนนี้เราใช้ Quicksilver เพื่อส่งการเปลี่ยนแปลงการกำหนดค่าไปยังไคลเอนต์ อัปเดตกฎ WAF และแจกจ่ายโค้ด JavaScript ที่ไคลเอนต์เขียนไปยัง Cloudflare Workers

ใช้เวลาเพียงไม่กี่วินาทีในการคลิกปุ่มบนแดชบอร์ดหรือการเรียก API ไปจนถึงการเปลี่ยนแปลงการกำหนดค่าทั่วโลก ลูกค้าชื่นชอบความเร็วของการตั้งค่านี้ และ Workers ช่วยให้พวกเขาปรับใช้ซอฟต์แวร์ทั่วโลกได้แทบจะในทันที โดยเฉลี่ยแล้ว Quicksilver เผยแพร่การเปลี่ยนแปลงประมาณ 350 รายการต่อวินาที

และควิกซิลเวอร์ก็เร็วมาก โดยเฉลี่ยแล้ว เราบรรลุเปอร์เซ็นไทล์ที่ 99 ที่ 2,29 วินาทีในการเผยแพร่การเปลี่ยนแปลงไปยังคอมพิวเตอร์ทุกเครื่องทั่วโลก ความเร็วมักจะเป็นสิ่งที่ดี ท้ายที่สุดแล้ว เมื่อคุณเปิดใช้งานฟังก์ชันหรือล้างแคช มันจะเกิดขึ้นแทบจะในทันทีและทุกที่ การส่งโค้ดผ่าน Cloudflare Workers เกิดขึ้นที่ความเร็วเท่ากัน Cloudflare สัญญาว่าลูกค้าจะอัปเดตอย่างรวดเร็วในเวลาที่เหมาะสม

แต่ในกรณีนี้ ความเร็วเป็นเรื่องตลกร้ายสำหรับเรา และกฎเกณฑ์ก็เปลี่ยนไปทุกที่ในเวลาไม่กี่วินาที คุณอาจสังเกตเห็นว่าโค้ด WAF ใช้ Lua Cloudflare ใช้ Lua อย่างกว้างขวางในการผลิตและรายละเอียด ลัวะใน 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. ลูกค้าของเราไม่สามารถเข้าถึงแดชบอร์ดหรือ API ของ Cloudflare ได้เนื่องจากพวกเขาผ่านภูมิภาค Cloudflare

สิ่งที่เปลี่ยนแปลงไปตั้งแต่วันพฤหัสบดีที่แล้ว

อันดับแรก เราหยุดการทำงานทั้งหมดเกี่ยวกับการเผยแพร่ WAF โดยสมบูรณ์ และกำลังดำเนินการดังต่อไปนี้:

1. เรากำลังเปิดตัวการป้องกันการใช้งาน CPU มากเกินไปที่เราลบออกไปอีกครั้ง (พร้อม)
2. ตรวจสอบกฎทั้งหมด 3868 ข้อในกฎที่ได้รับการจัดการด้วยตนเองสำหรับ WAF เพื่อค้นหาและแก้ไขกรณีอื่น ๆ ที่อาจเกิดขึ้นของการย้อนรอยมากเกินไป (การยืนยันเสร็จสมบูรณ์)
3. เรารวมโปรไฟล์ประสิทธิภาพสำหรับกฎทั้งหมดไว้ในชุดทดสอบ (คาดว่า: 19 กรกฎาคม)
4. การสลับไปใช้เอ็นจิ้นนิพจน์ทั่วไป re2 หรือ สนิม - ทั้งสองให้การรับประกันรันไทม์ (คาดว่า: 31 กรกฎาคม)
5. เรากำลังเขียน SOP ใหม่เพื่อปรับใช้กฎเป็นระยะ เช่นเดียวกับซอฟต์แวร์อื่นๆ ใน Cloudflare แต่ในขณะเดียวกันก็มีความสามารถในการปรับใช้ทั่วโลกในกรณีฉุกเฉินหากการโจมตีได้เริ่มขึ้นแล้ว
6. เรากำลังพัฒนาความสามารถในการลบแดชบอร์ด Cloudflare และ API ออกจากภูมิภาค Cloudflare อย่างเร่งด่วน
7. การอัปเดตหน้าอัตโนมัติ สถานะคลาวด์แฟลร์.

ในระยะยาวเรากำลังจะย้ายออกจาก Lua WAF ที่ฉันเขียนเมื่อไม่กี่ปีก่อน กำลังย้าย WAF ไปที่ ระบบไฟร์วอลล์ใหม่. วิธีนี้จะทำให้ WAF เร็วขึ้นและได้รับการปกป้องอีกระดับหนึ่ง

ข้อสรุป

ความล้มเหลวนี้ทำให้เกิดปัญหากับเราและลูกค้าของเรา เราดำเนินการอย่างรวดเร็วเพื่อแก้ไขสถานการณ์ และตอนนี้กำลังดำเนินการกับข้อบกพร่องในกระบวนการที่ทำให้เกิดข้อขัดข้อง เช่นเดียวกับการขุดลึกลงไปอีกเพื่อป้องกันปัญหาที่อาจเกิดขึ้นด้วยนิพจน์ทั่วไปในอนาคตเมื่อย้ายไปยังเทคโนโลยีใหม่

เรารู้สึกเขินอายมากกับการหยุดทำงานครั้งนี้ และขออภัยลูกค้าของเรา เราหวังว่าการเปลี่ยนแปลงเหล่านี้จะช่วยให้แน่ใจว่าเหตุการณ์เช่นนี้จะไม่เกิดขึ้นอีก

แอปพลิเคชัน. การย้อนรอยนิพจน์ทั่วไป

เพื่อทำความเข้าใจวิธีการแสดงออก:

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

กินทรัพยากร CPU ทั้งหมดคุณจำเป็นต้องรู้เพียงเล็กน้อยเกี่ยวกับการทำงานของเอ็นจิ้นนิพจน์ทั่วไปมาตรฐาน ปัญหาที่นี่คือรูปแบบ .*(?:.*=.*). (?: และสอดคล้องกัน ) เป็นกลุ่มที่ไม่จับภาพ (นั่นคือ นิพจน์ในวงเล็บจะถูกจัดกลุ่มเป็นนิพจน์เดี่ยว)

ในบริบทของการใช้ CPU มากเกินไป รูปแบบนี้สามารถอธิบายได้ว่าเป็น .*.*=.*. ในรูปแบบนี้ รูปแบบจะดูซับซ้อนโดยไม่จำเป็น แต่ที่สำคัญกว่านั้น ในโลกแห่งความเป็นจริง นิพจน์ (เช่น นิพจน์ที่ซับซ้อนในกฎ WAF) ที่ขอให้กลไกจับคู่แฟรกเมนต์ที่ตามด้วยแฟรกเมนต์อื่นสามารถนำไปสู่การย้อนรอยหายนะได้ และนั่นคือเหตุผล

ในการแสดงออกปกติ . หมายความว่าคุณต้องจับคู่อักขระหนึ่งตัว .* - จับคู่อักขระตั้งแต่ศูนย์ขึ้นไป "อย่างตะกละ" นั่นคือจับอักขระได้สูงสุดดังนั้น .*.*=.* หมายถึง จับคู่อักขระศูนย์หรือมากกว่า จากนั้นจับคู่อักขระศูนย์หรือมากกว่า ค้นหาอักขระตัวอักษร = จับคู่อักขระศูนย์หรือมากกว่า

มาทำแบบทดสอบกันเถอะ x=x. มันสอดคล้องกับการแสดงออก .*.*=.*. .*.* ก่อนที่เครื่องหมายเท่ากับจะตรงกับเครื่องหมายแรก x (หนึ่งในกลุ่ม .* สอดคล้องกับ xและอักขระตัวที่สอง - ศูนย์) .* after = การแข่งขันครั้งสุดท้าย x.

การเปรียบเทียบนี้ต้องใช้ 23 ขั้นตอน กลุ่มแรก .* в .*.*=.* ทำหน้าที่อย่างตะกละตะกลามและจับคู่สตริงทั้งหมด x=x. เครื่องยนต์จะเคลื่อนไปยังกลุ่มถัดไป .*. เราไม่มีตัวละครที่จะจับคู่อีกแล้ว ดังนั้นกลุ่มที่สอง .* ตรงกับอักขระศูนย์ (อนุญาตให้ทำได้) จากนั้นเครื่องยนต์ก็เคลื่อนตัวไปที่ป้าย =. ไม่มีสัญลักษณ์อีกต่อไป (กลุ่มแรก .* ใช้สำนวนทั้งหมด x=x) ไม่มีการเปรียบเทียบเกิดขึ้น

จากนั้นเอ็นจิ้นนิพจน์ทั่วไปจะกลับสู่จุดเริ่มต้น เขาย้ายไปยังกลุ่มแรก .* และเปรียบเทียบมัน с x= (แทน x=x) จากนั้นจึงเข้ากลุ่มที่สอง .*. กลุ่มที่สอง .* จะถูกเปรียบเทียบกับครั้งที่สอง xและเราก็ไม่มีตัวละครเหลืออีกแล้ว และเมื่อเครื่องยนต์ถึงอีกครั้ง = в .*.*=.*ไม่มีอะไรทำงาน และเขาก็ถอยหลังอีกครั้ง

ครั้งนี้กลุ่ม .* ยังคงตรงกัน x=แต่กลุ่มที่สอง .* ไม่มีอีกแล้ว xและอักขระศูนย์ เครื่องยนต์พยายามค้นหาอักขระตามตัวอักษร = ในรูปแบบ .*.*=.*แต่ก็ไม่ออกมา(เพราะกลุ่มแรกได้ครอบครองไปแล้ว) .*). และเขาก็ถอยหลังอีกครั้ง

ครั้งนี้เป็นกลุ่มแรก .* ใช้เวลาเพียง x แรกเท่านั้น แต่กลุ่มที่สอง .* "ตะกละ" จับ =x. คุณเดาแล้วว่าจะเกิดอะไรขึ้น? เครื่องยนต์พยายามจับคู่ตามตัวอักษร =ล้มเหลวและย้อนรอยอีกครั้ง

กลุ่มแรก .* ยังคงตรงกับอันแรก x. ที่สอง .* ใช้เวลาเท่านั้น =. แน่นอนว่าเครื่องยนต์ไม่สามารถตรงกับตัวอักษรได้ =เพราะกลุ่มที่ XNUMX ได้ทำไปแล้ว .*. และเป็นการย้อนรอยอีกครั้ง และเรากำลังพยายามจับคู่สตริงอักขระสามตัว!

ส่งผลให้กลุ่มแรก .* ตรงกับอันแรกเท่านั้น x, ที่สอง .* - ไม่มีอักขระ และเครื่องยนต์ก็ตรงกับตัวอักษรในที่สุด = ในการแสดงออก с = ในบรรทัด ต่อไปเป็นกลุ่มสุดท้าย .* จะถูกเปรียบเทียบกับอันสุดท้าย x.

23 ขั้นตอนเท่านั้นสำหรับ x=x. ชมวิดีโอสั้น ๆ เกี่ยวกับการใช้ Perl Regexp::ดีบักเกอร์ซึ่งแสดงให้เห็นว่าขั้นตอนและการย้อนรอยเกิดขึ้นได้อย่างไร

นี่เป็นงานจำนวนมากอยู่แล้ว แต่จะเกิดอะไรขึ้นถ้าแทน 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= และ 20 xจำเป็นต้องมีขั้นตอน 5353 นี่คือแผนภูมิ ดูค่าแกน Y เมื่อเทียบกับแผนภูมิก่อนหน้า

หากคุณสนใจ ลองดูขั้นตอนการจับคู่ที่ล้มเหลวทั้งหมด 5353 ขั้นตอน x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;

การใช้การจับคู่แบบขี้เกียจมากกว่าการจับคู่แบบละโมบ ขอบเขตของการย้อนรอยสามารถควบคุมได้ ถ้าเราเปลี่ยนสำนวนเดิมเป็น .*?.*?=.*?เพื่อการเปรียบเทียบ x=x จะใช้เวลา 11 ขั้นตอน (ไม่ใช่ 23) ส่วน x=xxxxxxxxxxxxxxxxxxxx. ทั้งหมดเพราะว่า ? หลังจาก .* บอกให้เอ็นจิ้นจับคู่จำนวนอักขระขั้นต่ำก่อนดำเนินการต่อ

แต่การแมปที่ขี้เกียจไม่สามารถแก้ปัญหาการย้อนรอยได้อย่างสมบูรณ์ ถ้าเราแทนที่ตัวอย่างหายนะ .*.*=.*; บน .*?.*?=.*?;เวลาในการดำเนินการจะยังคงเหมือนเดิม x=x ยังคงต้องใช้ขั้นตอน 555 และ x= และ 20 x - 5353

สิ่งเดียวที่สามารถทำได้ (นอกเหนือจากการเขียนรูปแบบใหม่ทั้งหมดเพื่อความเฉพาะเจาะจงมากขึ้น) คือการละทิ้งเอ็นจิ้นนิพจน์ทั่วไปที่มีกลไกการย้อนรอย นี่คือสิ่งที่เราจะทำในอีกไม่กี่สัปดาห์ข้างหน้า

วิธีแก้ปัญหานี้เป็นที่รู้จักมาตั้งแต่ปี 1968 เมื่อ Kent Thompson เขียนบทความ เทคนิคการเขียนโปรแกรม: อัลกอริธึมการค้นหานิพจน์ทั่วไป (“วิธีการเขียนโปรแกรม: อัลกอริธึมการค้นหานิพจน์ทั่วไป”) บทความนี้อธิบายถึงกลไกที่ช่วยให้คุณสามารถแปลงนิพจน์ทั่วไปเป็นเครื่องสถานะไฟไนต์ที่ไม่ได้กำหนดไว้ และหลังจากการเปลี่ยนแปลงสถานะในเครื่องสถานะไฟไนต์ที่ไม่ได้กำหนดไว้ ให้ใช้อัลกอริทึมซึ่งเวลาในการดำเนินการขึ้นอยู่กับสตริงที่ตรงกันเชิงเส้นตรง

วิธีการเขียนโปรแกรม
อัลกอริทึมการค้นหานิพจน์ทั่วไป
เคน ทอมป์สัน
Bell Telephone Laboratories, Inc., เมอร์เรย์ฮิลล์, นิวเจอร์ซีย์

โดยจะอธิบายวิธีการค้นหาสตริงอักขระเฉพาะในข้อความ และอธิบายการนำวิธีการนี้ไปใช้ในรูปแบบคอมไพเลอร์ คอมไพลเลอร์ใช้นิพจน์ทั่วไปเป็นซอร์สโค้ดและสร้างโปรแกรม IBM 7094 เป็นโค้ดอ็อบเจ็กต์ โปรแกรมอ็อบเจ็กต์รับอินพุตในรูปแบบของข้อความค้นหาและส่งสัญญาณทุกครั้งที่สตริงข้อความถูกจับคู่กับนิพจน์ทั่วไปที่กำหนด บทความนี้มีตัวอย่าง ปัญหา และแนวทางแก้ไข

ขั้นตอนวิธี
อัลกอริธึมการค้นหาก่อนหน้านี้ส่งผลให้เกิดการย้อนรอยหากการค้นหาที่ประสบความสำเร็จบางส่วนไม่สามารถสร้างผลลัพธ์ได้

ในโหมดคอมไพล์ อัลกอริธึมจะไม่ทำงานกับสัญลักษณ์ มันส่งคำแนะนำไปยังโค้ดที่คอมไพล์แล้ว การดำเนินการรวดเร็วมาก - หลังจากส่งข้อมูลไปที่ด้านบนของรายการปัจจุบันแล้ว ระบบจะค้นหาอักขระต่อเนื่องที่เป็นไปได้ทั้งหมดในนิพจน์ทั่วไปโดยอัตโนมัติ
อัลกอริธึมการคอมไพล์และการค้นหารวมอยู่ในโปรแกรมแก้ไขข้อความการแบ่งเวลาเป็นการค้นหาตามบริบท แน่นอนว่านี่ไม่ใช่แอปพลิเคชันเดียวของขั้นตอนการค้นหาดังกล่าว ตัวอย่างเช่น ตัวแปรของอัลกอริธึมนี้ถูกใช้เป็นการค้นหาสัญลักษณ์ในตารางในแอสเซมเบลอร์
สันนิษฐานว่าผู้อ่านคุ้นเคยกับนิพจน์ทั่วไปและภาษาการเขียนโปรแกรมคอมพิวเตอร์ IBM 7094

คอมไพเลอร์
คอมไพเลอร์ประกอบด้วยสามขั้นตอนที่ทำงานแบบขนาน ขั้นแรกคือการกรองไวยากรณ์ ซึ่งอนุญาตให้เฉพาะนิพจน์ทั่วไปที่ถูกต้องทางไวยากรณ์เท่านั้นที่จะผ่านได้ ขั้นตอนนี้จะแทรกตัวดำเนินการ "·" เพื่อให้ตรงกับนิพจน์ทั่วไปด้วย ในขั้นตอนที่สอง นิพจน์ทั่วไปจะถูกแปลงเป็นรูปแบบ postfix ในขั้นตอนที่สาม รหัสวัตถุจะถูกสร้างขึ้น 2 ขั้นตอนแรกนั้นชัดเจน และเราจะไม่จมอยู่กับมัน

บทความของ Thompson ไม่ได้พูดถึงเครื่องจักรสถานะจำกัดที่ไม่สามารถกำหนดได้ แต่จะอธิบายอัลกอริธึมเวลาเชิงเส้นได้ดี และนำเสนอโปรแกรม ALGOL-60 ที่สร้างโค้ดภาษาแอสเซมบลีสำหรับ IBM 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.

ในรูป 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.

อัลกอริธึมนี้ขึ้นอยู่กับขนาดของสตริงอินพุตเป็นเส้นตรง

ที่มา: will.com