ລາຍລະອຽດຂອງການຢຸດ Cloudflare ໃນວັນທີ 2 ກໍລະກົດ 2019

ເກືອບ 9 ປີກ່ອນ Cloudflare ເປັນບໍລິສັດນ້ອຍໆ, ແລະຂ້ອຍບໍ່ໄດ້ເຮັດວຽກໃຫ້ມັນ, ຂ້ອຍເປັນພຽງລູກຄ້າເທົ່ານັ້ນ. ເດືອນຫຼັງຈາກການເປີດຕົວ Cloudflare, ຂ້ອຍໄດ້ຮັບການແຈ້ງເຕືອນວ່າເວັບໄຊທ໌ຂອງຂ້ອຍ jgc.orgDNS ເບິ່ງຄືວ່າບໍ່ເຮັດວຽກ. Cloudflare ໄດ້ປ່ຽນແປງ Protocol Buffers, ແລະມີ DNS ທີ່ແຕກຫັກ.

ຂ້າພະເຈົ້າທັນທີໄດ້ຂຽນໄປຫາ Matthew Prince ດ້ວຍຫົວຂໍ້ວ່າ "DNS ຂອງຂ້ອຍຢູ່ໃສ?" ແລະລາວໄດ້ສົ່ງຄືນຄໍາຕອບທີ່ເຕັມໄປດ້ວຍລາຍລະອຽດດ້ານວິຊາການ (ອ່ານຈົດໝາຍທັງໝົດ ທີ່ນີ້), ເຊິ່ງຂ້າພະເຈົ້າຕອບວ່າ:

ຈາກ: John Graham-Cumming
ວັນທີ: 7 ຕຸລາ 2010, 9:14
Subject: Re: Where is my DNS?
ເຖິງ: Matthew Prince

ບົດລາຍງານເຢັນ, ຂອບໃຈ. ຂ້ອຍຈະໂທຫາແນ່ນອນຖ້າມີບັນຫາ. ມັນອາດຈະເປັນມູນຄ່າການຂຽນຂໍ້ຄວາມກ່ຽວກັບເລື່ອງນີ້ເມື່ອທ່ານໄດ້ລວບລວມຂໍ້ມູນດ້ານວິຊາການທັງຫມົດ. ຂ້າ​ພະ​ເຈົ້າ​ຄິດ​ວ່າ​ປະ​ຊາ​ຊົນ​ຈະ​ມີ​ຄວາມ​ສຸກ​ເລື່ອງ​ເປີດ​ແລະ​ຊື່​ສັດ​. ໂດຍສະເພາະຖ້າທ່ານແນບກາຟໃສ່ມັນເພື່ອສະແດງໃຫ້ເຫັນວ່າການຈະລາຈອນເພີ່ມຂຶ້ນນັບຕັ້ງແຕ່ການເປີດຕົວ.

ຂ້າ​ພະ​ເຈົ້າ​ມີ​ການ​ຕິດ​ຕາມ​ກວດ​ກາ​ທີ່​ດີ​ຢູ່​ໃນ​ເວັບ​ໄຊ​ຂອງ​ຂ້າ​ພະ​ເຈົ້າ​, ແລະ​ຂ້າ​ພະ​ເຈົ້າ​ໄດ້​ຮັບ SMS ກ່ຽວ​ກັບ​ຄວາມ​ລົ້ມ​ເຫຼວ​ທຸກ​. ການຕິດຕາມສະແດງໃຫ້ເຫັນວ່າຄວາມລົ້ມເຫຼວເກີດຂຶ້ນຈາກ 13:03:07 ຫາ 14:04:12. ການທົດສອບແມ່ນດໍາເນີນທຸກໆຫ້ານາທີ.

ຂ້ອຍແນ່ໃຈວ່າເຈົ້າຈະຄິດອອກ. ເຈົ້າແນ່ໃຈບໍ່ວ່າເຈົ້າບໍ່ຕ້ອງການຄົນຂອງເຈົ້າໃນເອີຣົບ? 🙂

ແລະລາວຕອບວ່າ:

ຈາກ: Matthew Prince
ວັນທີ: 7 ຕຸລາ 2010, 9:57
Subject: Re: Where is my DNS?
ເຖິງ: John Graham-Cumming

ຂອບ​ໃຈ. ພວກເຮົາຕອບສະຫນອງກັບທຸກຄົນທີ່ຂຽນ. ຂ້ອຍ ກຳ ລັງເດີນທາງໄປຫ້ອງການດຽວນີ້ແລະພວກເຮົາຈະຂຽນບາງສິ່ງບາງຢ່າງລົງໃນ blog ຫຼື pin post ຢ່າງເປັນທາງການໃນກະດານຂ່າວຂອງພວກເຮົາ. ຂ້າພະເຈົ້າຕົກລົງເຫັນດີຢ່າງສົມບູນ, ຄວາມຊື່ສັດແມ່ນທຸກສິ່ງທຸກຢ່າງ.

ໃນປັດຈຸບັນ Cloudflare ເປັນບໍລິສັດໃຫຍ່ແທ້ໆ, ຂ້ອຍເຮັດວຽກສໍາລັບມັນ, ແລະຕອນນີ້ຂ້ອຍຕ້ອງຂຽນຢ່າງເປີດເຜີຍກ່ຽວກັບຄວາມຜິດພາດຂອງພວກເຮົາ, ຜົນສະທ້ອນແລະການກະທໍາຂອງພວກເຮົາ.

ເຫດການ 2 ກໍລະກົດ

ໃນວັນທີ 2 ເດືອນກໍລະກົດພວກເຮົາໄດ້ອອກກົດລະບຽບໃຫມ່ໃນກົດລະບຽບການຄຸ້ມຄອງສໍາລັບ WAFs ເນື່ອງຈາກສິ່ງທີ່ ຊັບພະຍາກອນ CPU ໝົດແລ້ວ ໃນທຸກໆການປະມວນຜົນຫຼັກຂອງໂປເຊດເຊີ HTTP/HTTPS ການຈະລາຈອນໃນເຄືອຂ່າຍ Cloudflare ທົ່ວໂລກ. ພວກເຮົາປັບປຸງກົດລະບຽບທີ່ມີການຄຸ້ມຄອງຢ່າງຕໍ່ເນື່ອງສໍາລັບ WAFs ເພື່ອຕອບສະຫນອງຕໍ່ຄວາມສ່ຽງແລະໄພຂົ່ມຂູ່ໃຫມ່. ຕົວຢ່າງໃນເດືອນພຶດສະພາ, ພວກເຮົາຮີບຮ້ອນ ເພີ່ມ​ກົດ​ລະ​ບຽບ​ເພື່ອປົກປ້ອງຄວາມສ່ຽງທີ່ຮ້າຍແຮງໃນ 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 ນາທີບໍ່ພຽງແຕ່ຍ້ອນການສະແດງອອກທີ່ບໍ່ດີປົກກະຕິ. ມັນໃຊ້ເວລາພວກເຮົາໄລຍະຫນຶ່ງເພື່ອອະທິບາຍລໍາດັບເຫດການທີ່ນໍາໄປສູ່ຄວາມລົ້ມເຫລວ, ດັ່ງນັ້ນພວກເຮົາຈຶ່ງຊ້າທີ່ຈະຕອບສະຫນອງ. ໃນຕອນທ້າຍຂອງການຕອບ, ຂ້າພະເຈົ້າຈະອະທິບາຍ backtracking ໃນການສະແດງອອກເປັນປົກກະຕິແລະບອກທ່ານວ່າຈະເຮັດແນວໃດກັບມັນ.

тослучилось

ໃຫ້ເລີ່ມຕົ້ນໃນຄໍາສັ່ງ. ເວລາທັງໝົດນີ້ແມ່ນຢູ່ໃນ UTC.

ໃນເວລາ 13:42 ໂມງແລງ, ວິສະວະກອນໃນທີມ firewall ໄດ້ປ່ຽນແປງກົດລະບຽບການກວດພົບເລັກນ້ອຍ XSS ໃຊ້ຂະບວນການອັດຕະໂນມັດ. ຕາມ​ນັ້ນ​ແລ້ວ, ໃບ​ຮ້ອງ​ຂໍ​ການ​ປ່ຽນ​ແປງ​ໄດ້​ຖືກ​ສ້າງ​ຂຶ້ນ. ພວກເຮົາຈັດການປີ້ດັ່ງກ່າວຜ່ານ Jira (ພາບຫນ້າຈໍຂ້າງລຸ່ມນີ້).

ຫຼັງຈາກ 3 ນາທີ, ຫນ້າທໍາອິດຂອງ PagerDuty ປາກົດ, ລາຍງານບັນຫາກັບ WAF. ນີ້ແມ່ນການທົດສອບສັງເຄາະທີ່ທົດສອບການເຮັດວຽກຂອງ WAFs (ພວກເຮົາມີຫຼາຍຮ້ອຍຄົນ) ຢູ່ນອກ Cloudflare ເພື່ອຕິດຕາມການເຮັດວຽກປົກກະຕິ. ນີ້ໄດ້ຖືກປະຕິບັດຕາມທັນທີໂດຍຫນ້າຂອງການແຈ້ງເຕືອນກ່ຽວກັບການທົດສອບການບໍລິການ end-to-end ອື່ນໆຂອງ Cloudflare ລົ້ມເຫລວ, ບັນຫາການຈະລາຈອນທົ່ວໂລກ, ຄວາມຜິດພາດ 502 ທີ່ແຜ່ຫຼາຍ, ແລະບົດລາຍງານຫຼາຍໂຕນຈາກຈຸດທີ່ພົບເຫັນຂອງພວກເຮົາ (PoP) ໃນເມືອງຕ່າງໆທົ່ວໂລກທີ່ຊີ້ໃຫ້ເຫັນເຖິງການຂາດແຄນ. ຂອງ​ຊັບ​ພະ​ຍາ​ກອນ CPU​.

ຂ້າພະເຈົ້າໄດ້ຮັບການແຈ້ງເຕືອນເຫຼົ່ານີ້ຫຼາຍໆຄັ້ງ, ອອກຈາກກອງປະຊຸມ, ແລະຢູ່ໃນເສັ້ນທາງຂອງຂ້ອຍໄປຫາໂຕະໃນເວລາທີ່ຫົວຫນ້າພະແນກພັດທະນາການແກ້ໄຂຂອງພວກເຮົາກ່າວວ່າພວກເຮົາໄດ້ສູນເສຍ 80% ຂອງການຈະລາຈອນຂອງພວກເຮົາ. ຂ້າພະເຈົ້າໄດ້ແລ່ນໄປຫາວິສະວະກອນ SRE ຂອງພວກເຮົາ, ຜູ້ທີ່ເຮັດວຽກຢູ່ແລ້ວກ່ຽວກັບບັນຫາ. ທຳອິດ ພວກເຮົາຄິດວ່າມັນເປັນການໂຈມຕີທີ່ບໍ່ຮູ້ຈັກບາງປະເພດ.

ວິສະວະກອນ Cloudflare SRE ແມ່ນກະແຈກກະຈາຍໄປທົ່ວໂລກແລະຕິດຕາມສະຖານະການຕະຫຼອດໂມງ. ໂດຍປົກກະຕິ, ການແຈ້ງເຕືອນເຫຼົ່ານີ້ແຈ້ງເຕືອນທ່ານກ່ຽວກັບບັນຫາທ້ອງຖິ່ນສະເພາະຂອງຂອບເຂດຈໍາກັດ, ຖືກຕິດຕາມຢູ່ໃນ dashboards ພາຍໃນ, ແລະຖືກແກ້ໄຂຫຼາຍຄັ້ງຕໍ່ມື້. ແຕ່ຫນ້າແລະການແຈ້ງເຕືອນເຫຼົ່ານີ້ຊີ້ໃຫ້ເຫັນບາງສິ່ງບາງຢ່າງທີ່ຮຸນແຮງ, ແລະວິສະວະກອນ SRE ທັນທີທັນໃດປະກາດລະດັບຄວາມຮ້າຍແຮງ P0 ແລະຕິດຕໍ່ກັບຜູ້ບໍລິຫານແລະວິສະວະກອນລະບົບ.

ວິສະວະກອນລອນດອນຂອງພວກເຮົາໄດ້ຟັງການບັນຍາຍຢູ່ໃນຫ້ອງໂຖງໃຫຍ່ໃນຂະນະນັ້ນ. ການບັນຍາຍຕ້ອງຖືກຂັດຂວາງ, ທຸກຄົນໄດ້ມາເຕົ້າໂຮມກັນຢູ່ໃນຫ້ອງປະຊຸມໃຫຍ່, ແລະຜູ້ຊ່ຽວຊານເພີ່ມເຕີມໄດ້ຖືກເອີ້ນ. ນີ້ບໍ່ແມ່ນບັນຫາປົກກະຕິທີ່ SREs ສາມາດຈັດການກັບຕົນເອງໄດ້. ມັນເປັນການຮີບດ່ວນທີ່ຈະມີສ່ວນຮ່ວມກັບຜູ້ຊ່ຽວຊານທີ່ຖືກຕ້ອງ.

ໃນເວລາ 14:00 ພວກເຮົາກໍານົດວ່າບັນຫາແມ່ນຂຶ້ນກັບ WAF ແລະບໍ່ມີການໂຈມຕີ. ທີມງານປະຕິບັດໄດ້ດຶງຂໍ້ມູນ CPU ແລະມັນໄດ້ກາຍເປັນທີ່ຊັດເຈນວ່າ WAF ແມ່ນເພື່ອຕໍານິ. ພະນັກງານອີກຄົນຫນຶ່ງຢືນຢັນທິດສະດີນີ້ໂດຍໃຊ້ strace. ຄົນອື່ນເຫັນຢູ່ໃນບັນທຶກທີ່ມີບັນຫາກັບ WAF. ໃນເວລາ 14:02 ໂມງແລງ, ທີມງານທັງຫມົດໄດ້ມາຫາຂ້ອຍເມື່ອມັນຖືກສະເຫນີໃຫ້ໃຊ້ການຂ້າທົ່ວໂລກ, ກົນໄກທີ່ສ້າງຂຶ້ນໃນ Cloudflare ທີ່ປິດອົງປະກອບຫນຶ່ງໃນທົ່ວໂລກ.

ວິທີທີ່ພວກເຮົາໄດ້ຂ້າທົ່ວໂລກສໍາລັບ WAF ແມ່ນເລື່ອງທີ່ແຕກຕ່າງກັນ. ມັນບໍ່ແມ່ນເລື່ອງງ່າຍດາຍ. ພວກເຮົາໃຊ້ຜະລິດຕະພັນຂອງພວກເຮົາເອງ, ແລະນັບຕັ້ງແຕ່ການບໍລິການຂອງພວກເຮົາ ການເຂົ້າເຖິງ ບໍ່ໄດ້ຜົນ, ພວກເຮົາບໍ່ສາມາດກວດສອບຄວາມຖືກຕ້ອງ ແລະເຂົ້າສູ່ລະບົບແຜງຄວບຄຸມພາຍໃນໄດ້ (ເມື່ອທຸກຢ່າງຖືກແກ້ໄຂ, ພວກເຮົາໄດ້ຮຽນຮູ້ວ່າສະມາຊິກທີມງານບາງຄົນສູນເສຍການເຂົ້າເຖິງເນື່ອງຈາກຄຸນສົມບັດຄວາມປອດໄພທີ່ປິດການໃຊ້ງານຂໍ້ມູນປະຈໍາຕົວ ຖ້າແຜງຄວບຄຸມພາຍໃນບໍ່ໄດ້ໃຊ້ສໍາລັບ ເວ​ລາ​ດົນ​ນານ).

ແລະພວກເຮົາບໍ່ສາມາດໄປຫາບໍລິການພາຍໃນຂອງພວກເຮົາເຊັ່ນ Jira ຫຼືລະບົບການກໍ່ສ້າງ. ພວກ​ເຮົາ​ຕ້ອງ​ການ​ກົນ​ໄກ​ແກ້​ໄຂ, ທີ່​ພວກ​ເຮົາ​ໄດ້​ນໍາ​ໃຊ້​ເລື້ອຍໆ (ອັນ​ນີ້​ຍັງ​ຈະ​ຕ້ອງ​ໄດ້​ຮັບ​ການ​ແກ້​ໄຂ). ໃນທີ່ສຸດ, ວິສະວະກອນຄົນຫນຶ່ງໄດ້ປິດການໃຊ້ງານ WAF ໃນເວລາ 14:07, ແລະໃນເວລາ 14:09, ລະດັບການຈະລາຈອນແລະ CPU ໄດ້ກັບຄືນສູ່ປົກກະຕິຢູ່ທົ່ວທຸກແຫ່ງ. ສ່ວນທີ່ເຫຼືອຂອງກົນໄກການປົກປ້ອງ Cloudflare ເຮັດວຽກເປັນປົກກະຕິ.

ຫຼັງຈາກນັ້ນ, ພວກເຮົາກໍານົດກ່ຽວກັບການຟື້ນຟູ WAF. ສະຖານະການບໍ່ທໍາມະດາ, ດັ່ງນັ້ນພວກເຮົາໄດ້ດໍາເນີນການທົດສອບທາງລົບ (ຖາມຕົວເອງວ່າການປ່ຽນແປງແມ່ນບັນຫາແທ້ໆບໍ) ແລະການທົດສອບໃນທາງບວກ (ໃຫ້ແນ່ໃຈວ່າ rollback ເຮັດວຽກ) ໃນເມືອງຫນຶ່ງໂດຍໃຊ້ການຈະລາຈອນແຍກຕ່າງຫາກ, ການໂອນລູກຄ້າທີ່ຈ່າຍຈາກບ່ອນນັ້ນ.

ໃນເວລາ 14:52 ພວກເຮົາເຊື່ອວ່າພວກເຮົາເຂົ້າໃຈເຫດຜົນແລະແກ້ໄຂ, ແລະເປີດໃຊ້ WAF ອີກເທື່ອຫນຶ່ງ.

Cloudflare ເຮັດວຽກແນວໃດ

Cloudflare ມີທີມງານວິສະວະກອນທີ່ອຸທິດຕົນເພື່ອການຄຸ້ມຄອງກົດລະບຽບສໍາລັບ WAFs. ພວກເຂົາພະຍາຍາມປັບປຸງອັດຕາການກວດພົບ, ຫຼຸດຜ່ອນຜົນບວກທີ່ບໍ່ຖືກຕ້ອງ, ແລະຕອບສະຫນອງຢ່າງໄວວາຕໍ່ກັບໄພຂົ່ມຂູ່ໃຫມ່ເມື່ອພວກເຂົາເກີດຂື້ນ. ໃນ 60 ມື້ທີ່ຜ່ານມາ, ມີ 476 ຄໍາຮ້ອງຂໍການປ່ຽນແປງທີ່ດໍາເນີນການສໍາລັບກົດລະບຽບທີ່ມີການຄຸ້ມຄອງສໍາລັບ WAF (ສະເລ່ຍຫນຶ່ງຄັ້ງໃນທຸກໆ 3 ຊົ່ວໂມງ).

ການປ່ຽນແປງໂດຍສະເພາະນີ້ຈໍາເປັນຕ້ອງຖືກນໍາໄປໃຊ້ໃນຮູບແບບການຈໍາລອງ, ບ່ອນທີ່ການຈະລາຈອນຂອງລູກຄ້າທີ່ແທ້ຈິງຜ່ານກົດລະບຽບ, ແຕ່ບໍ່ມີຫຍັງຖືກສະກັດ. ພວກເຮົາໃຊ້ໂຫມດນີ້ເພື່ອທົດສອບປະສິດທິພາບຂອງກົດລະບຽບແລະການວັດແທກອັດຕາບວກທີ່ບໍ່ຖືກຕ້ອງແລະບໍ່ຖືກຕ້ອງ. ແຕ່ເຖິງແມ່ນວ່າຢູ່ໃນຮູບແບບການຈໍາລອງ, ກົດລະບຽບຈະຕ້ອງຖືກປະຕິບັດຢ່າງແທ້ຈິງ, ແລະໃນກໍລະນີນີ້ກົດລະບຽບປະກອບດ້ວຍການສະແດງອອກປົກກະຕິທີ່ບໍລິໂພກຊັບພະຍາກອນຂອງໂປເຊດເຊີຫຼາຍເກີນໄປ.

ດັ່ງທີ່ເຈົ້າສາມາດເຫັນໄດ້ຈາກຄໍາຮ້ອງຂໍການປ່ຽນແປງຂ້າງເທິງ, ພວກເຮົາມີແຜນປະຕິບັດການ, ແຜນການ rollback, ແລະການເຊື່ອມຕໍ່ກັບຂັ້ນຕອນການປະຕິບັດມາດຕະຖານພາຍໃນ (SOP) ສໍາລັບປະເພດນີ້. SOP ສໍາລັບການປ່ຽນແປງກົດລະບຽບອະນຸຍາດໃຫ້ມັນຖືກເຜີຍແຜ່ທົ່ວໂລກ. ຕົວຈິງແລ້ວ, ຢູ່ Cloudflare, ສິ່ງຕ່າງໆແມ່ນເຮັດໄດ້ແຕກຕ່າງກັນຢ່າງສິ້ນເຊີງ, ແລະ SOP ກໍານົດວ່າພວກເຮົາທໍາອິດສົ່ງຊອບແວສໍາລັບການທົດສອບແລະການນໍາໃຊ້ພາຍໃນໄປຫາຈຸດພາຍໃນ (PoP) (ທີ່ພະນັກງານຂອງພວກເຮົາໃຊ້), ຫຼັງຈາກນັ້ນໃຫ້ກັບລູກຄ້າຈໍານວນນ້ອຍໃນ. ສະຖານທີ່ທີ່ໂດດດ່ຽວ, ຫຼັງຈາກນັ້ນໃຫ້ກັບລູກຄ້າຈໍານວນຫລາຍ, ແລະພຽງແຕ່ຫຼັງຈາກນັ້ນທົ່ວໂລກ.

ນີ້ແມ່ນສິ່ງທີ່ມັນຄ້າຍຄື. ພວກເຮົາໃຊ້ git ພາຍໃນຜ່ານ BitBucket. ວິສະວະກອນທີ່ເຮັດວຽກກ່ຽວກັບການປ່ຽນແປງສົ່ງລະຫັດ, ເຊິ່ງປະກອບເຂົ້າໄປໃນ TeamCity, ແລະເມື່ອການກໍ່ສ້າງຜ່ານ, ຜູ້ທົບທວນຖືກມອບຫມາຍ. ເມື່ອການຮ້ອງຂໍການດຶງໄດ້ຖືກອະນຸມັດ, ລະຫັດຈະຖືກລວບລວມແລະຊຸດການທົດສອບຖືກດໍາເນີນການ (ອີກເທື່ອຫນຶ່ງ).

ຖ້າການກໍ່ສ້າງແລະການທົດສອບສໍາເລັດສົມບູນ, ການຮ້ອງຂໍການປ່ຽນແປງແມ່ນຖືກສ້າງຂຶ້ນໃນ Jira ແລະຜູ້ຈັດການທີ່ເຫມາະສົມຫຼືຜູ້ນໍາຕ້ອງອະນຸມັດການປ່ຽນແປງ. ຫຼັງ​ຈາກ​ການ​ອະ​ນຸ​ມັດ​, ການ​ນໍາ​ໃຊ້​ເກີດ​ຂຶ້ນ​ໃນ​ອັນ​ທີ່​ເອີ້ນ​ວ່າ "PoP menagerie​"​: DOG​, PIG ແລະ Canary (ຫມາ, ຫມູແລະ canary).

DOG PoP ແມ່ນ Cloudflare PoP (ຄືກັນກັບທຸກໆເມືອງຂອງພວກເຮົາ) ທີ່ຖືກນໍາໃຊ້ໂດຍພະນັກງານ Cloudflare ເທົ່ານັ້ນ. PoP ສໍາລັບການນໍາໃຊ້ພາຍໃນຊ່ວຍໃຫ້ທ່ານສາມາດຈັບບັນຫາກ່ອນທີ່ການຈະລາຈອນຂອງລູກຄ້າຈະໄຫຼເຂົ້າໄປໃນການແກ້ໄຂ. ສິ່ງທີ່ເປັນປະໂຫຍດ.

ຖ້າການທົດສອບ DOG ປະສົບຜົນສໍາເລັດ, ລະຫັດຍ້າຍໄປຢູ່ໃນຂັ້ນຕອນ PIG (guinea pig). ນີ້ແມ່ນ Cloudflare PoP, ບ່ອນທີ່ຈໍານວນຂະຫນາດນ້ອຍຂອງການຈະລາຈອນຂອງລູກຄ້າຟຣີໄຫຼຜ່ານລະຫັດໃຫມ່.
ຖ້າທັງຫມົດແມ່ນດີ, ລະຫັດເຂົ້າໄປໃນ Canary. ພວກເຮົາມີສາມ Canary PoPs ຢູ່ໃນພາກສ່ວນຕ່າງໆຂອງໂລກ. ໃນພວກເຂົາ, ການຈະລາຈອນຂອງລູກຄ້າທີ່ຈ່າຍແລະບໍ່ເສຍຄ່າຜ່ານລະຫັດໃຫມ່, ແລະນີ້ແມ່ນການກວດສອບຄວາມຜິດພາດຄັ້ງສຸດທ້າຍ.

ຂະບວນການປ່ອຍຊອບແວຢູ່ Cloudflare

ຖ້າລະຫັດແມ່ນດີໃນ Canary, ພວກເຮົາປ່ອຍມັນ. ຜ່ານທຸກຂັ້ນຕອນ - DOG, PIG, Canary, ໂລກທັງຫມົດ - ໃຊ້ເວລາຫຼາຍຊົ່ວໂມງຫຼືຫຼາຍມື້, ຂຶ້ນກັບການປ່ຽນແປງລະຫັດ. ເນື່ອງຈາກຄວາມຫຼາກຫຼາຍຂອງເຄືອຂ່າຍ ແລະລູກຄ້າຂອງ Cloudflare, ພວກເຮົາທົດສອບລະຫັດຢ່າງລະອຽດກ່ອນທີ່ຈະປ່ອຍມັນທົ່ວໂລກໃຫ້ກັບລູກຄ້າທັງໝົດ. ແຕ່ WAF ບໍ່ໄດ້ປະຕິບັດຕາມຂະບວນການນີ້ໂດຍສະເພາະເພາະວ່າໄພຂົ່ມຂູ່ຕ້ອງໄດ້ຮັບການຕອບສະຫນອງຢ່າງໄວວາ.

ໄພຂົ່ມຂູ່ຕໍ່ WAF
ໃນຊຸມປີມໍ່ໆມານີ້, ໄພຂົ່ມຂູ່ຕໍ່ການນໍາໃຊ້ທົ່ວໄປເພີ່ມຂຶ້ນຢ່າງຫຼວງຫຼາຍ. ນີ້ແມ່ນເນື່ອງມາຈາກຄວາມພ້ອມຫຼາຍຂອງເຄື່ອງມືທົດສອບຊອບແວ. ຕົວຢ່າງ, ພວກເຮົາບໍ່ດົນມານີ້ໄດ້ຂຽນກ່ຽວກັບ fuzzing).

ແຫຼ່ງຂໍ້ມູນ: https://cvedetails.com/

ເລື້ອຍໆ, ຫຼັກຖານສະແດງແນວຄວາມຄິດຖືກສ້າງຂື້ນແລະເຜີຍແຜ່ທັນທີໃນ Github ເພື່ອໃຫ້ທີມງານທີ່ຮັກສາຄໍາຮ້ອງສະຫມັກສາມາດທົດສອບມັນໄດ້ໄວແລະຮັບປະກັນວ່າມັນມີຄວາມຫມັ້ນຄົງພຽງພໍ. ດັ່ງນັ້ນ, Cloudflare ຕ້ອງການຄວາມສາມາດໃນການຕອບສະຫນອງຕໍ່ການໂຈມຕີໃຫມ່ໄວເທົ່າທີ່ຈະໄວໄດ້ເພື່ອໃຫ້ລູກຄ້າມີໂອກາດແກ້ໄຂຊອບແວຂອງພວກເຂົາ.

ຕົວຢ່າງທີ່ດີຂອງການຕອບໂຕ້ໄວຂອງ Cloudflare ແມ່ນການນຳໃຊ້ການປົກປ້ອງຊ່ອງໂຫວ່ SharePoint ໃນເດືອນພຶດສະພາ (ອ່ານຢູ່ທີ່ນີ້). ເກືອບທັນທີຫຼັງຈາກການປະກາດດັ່ງກ່າວ, ພວກເຮົາສັງເກດເຫັນຄວາມພະຍາຍາມທີ່ຈະຂຸດຄົ້ນຄວາມອ່ອນແອໃນການຕິດຕັ້ງ SharePoint ຂອງລູກຄ້າຂອງພວກເຮົາ. guys ຂອງພວກເຮົາແມ່ນຢ່າງຕໍ່ເນື່ອງຕິດຕາມໄພຂົ່ມຂູ່ໃຫມ່ແລະຂຽນກົດລະບຽບເພື່ອປົກປ້ອງລູກຄ້າຂອງພວກເຮົາ.

ກົດລະບຽບທີ່ເຮັດໃຫ້ເກີດບັນຫາໃນວັນພະຫັດແມ່ນຄາດວ່າຈະປ້ອງກັນການສະຄິບຂ້າມເວັບໄຊທ໌ (XSS). ການ​ໂຈມ​ຕີ​ດັ່ງ​ກ່າວ​ຍັງ​ໄດ້​ກາຍ​ເປັນ​ເລື້ອຍໆ​ໃນ​ຊຸມ​ປີ​ມໍ່ໆ​ມາ​ນີ້.

ແຫຼ່ງຂໍ້ມູນ: https://cvedetails.com/

ຂັ້ນຕອນມາດຕະຖານສໍາລັບການປ່ຽນແປງກົດລະບຽບການຄຸ້ມຄອງສໍາລັບ WAF ແມ່ນເພື່ອດໍາເນີນການທົດສອບການເຊື່ອມໂຍງຢ່າງຕໍ່ເນື່ອງ (CI) ກ່ອນທີ່ຈະນໍາໃຊ້ທົ່ວໂລກ. ວັນພະຫັດທີ່ຜ່ານມາພວກເຮົາໄດ້ເຮັດສິ່ງນີ້ແລະອອກກົດລະບຽບ. ເວລາ 13:31 ໂມງແລງ, ວິສະວະກອນໄດ້ຍື່ນຄໍາຮ້ອງຂໍການດຶງທີ່ໄດ້ຮັບການອະນຸມັດໂດຍມີການປ່ຽນແປງ.

ເວລາ 13:37 ທີມຊິຕີ້ເກັບກຳກົດ, ແລ່ນທົດສອບ ແລະ ເດີນໜ້າ. ຊຸດທົດສອບ WAF ທົດສອບການທໍາງານຫຼັກຂອງ WAF ແລະປະກອບດ້ວຍການທົດສອບຫນ່ວຍງານຈໍານວນຫລາຍສໍາລັບຫນ້າທີ່ແຕ່ລະຄົນ. ຫຼັງຈາກການທົດສອບຫນ່ວຍ, ພວກເຮົາໄດ້ທົດສອບກົດລະບຽບສໍາລັບ WAF ໂດຍໃຊ້ຄໍາຮ້ອງຂໍ HTTP ຈໍານວນຫລາຍ. ຄໍາຮ້ອງຂໍ HTTP ກວດເບິ່ງຄໍາຮ້ອງຂໍໃດທີ່ຄວນຈະຖືກບລັອກໂດຍ WAF (ເພື່ອຂັດຂວາງການໂຈມຕີ) ແລະທີ່ສາມາດອະນຸຍາດໃຫ້ຜ່ານ (ເພື່ອບໍ່ໃຫ້ຂັດຂວາງທຸກສິ່ງທຸກຢ່າງແລະຫຼີກເວັ້ນຜົນບວກທີ່ບໍ່ຖືກຕ້ອງ). ແຕ່ພວກເຮົາບໍ່ໄດ້ທົດສອບການໃຊ້ CPU ຫຼາຍເກີນໄປ, ແລະການກວດສອບບັນທຶກຂອງການກໍ່ສ້າງ WAF ທີ່ຜ່ານມາສະແດງໃຫ້ເຫັນວ່າເວລາປະຕິບັດການທົດສອບກົດລະບຽບບໍ່ໄດ້ເພີ່ມຂຶ້ນ, ແລະມັນຍາກທີ່ຈະສົງໃສວ່າບໍ່ມີຊັບພະຍາກອນພຽງພໍ.

ການທົດສອບຜ່ານໄປ ແລະ TeamCity ເລີ່ມນຳໃຊ້ການປ່ຽນແປງໂດຍອັດຕະໂນມັດໃນເວລາ 13:42 ໂມງແລງ.

Quicksilver

ກົດລະບຽບຂອງ WAF ສຸມໃສ່ການແກ້ໄຂໄພຂົ່ມຂູ່ໃນທັນທີ, ດັ່ງນັ້ນພວກເຮົານໍາໃຊ້ພວກມັນໂດຍໃຊ້ຮ້ານຂາຍກະແຈທີ່ແຈກຢາຍຂອງ Quicksilver, ເຊິ່ງແຜ່ຂະຫຍາຍການປ່ຽນແປງທົ່ວໂລກໃນວິນາທີ. ລູກຄ້າຂອງພວກເຮົາທຸກຄົນໃຊ້ເທກໂນໂລຍີນີ້ເມື່ອພວກເຂົາປ່ຽນການຕັ້ງຄ່າໃນ dashboard ຫຼືຜ່ານ API, ແລະມັນຂໍຂອບໃຈກັບມັນທີ່ພວກເຮົາຕອບສະຫນອງຕໍ່ການປ່ຽນແປງດ້ວຍຄວາມໄວຂອງຟ້າຜ່າ.

ພວກເຮົາບໍ່ໄດ້ເວົ້າຫຼາຍກ່ຽວກັບ Quicksilver. ໃນເມື່ອກ່ອນພວກເຮົາໃຊ້ Kyoto Tycoon ໃນຖານະທີ່ເປັນຮ້ານຂາຍກະແຈທີ່ແຈກຢາຍທົ່ວໂລກ, ແຕ່ມີບັນຫາໃນການປະຕິບັດງານກັບມັນ, ແລະພວກເຮົາຂຽນຮ້ານຂອງພວກເຮົາເອງ, ສຳເນົາຢູ່ໃນຫຼາຍກວ່າ 180 ເມືອງ. ໃນປັດຈຸບັນພວກເຮົາໃຊ້ Quicksilver ເພື່ອຊຸກຍູ້ການປ່ຽນແປງການຕັ້ງຄ່າໃຫ້ກັບລູກຄ້າ, ປັບປຸງກົດລະບຽບ WAF, ແລະແຈກຢາຍລະຫັດ JavaScript ທີ່ຂຽນໂດຍລູກຄ້າໃຫ້ກັບ Cloudflare Workers.

ມັນໃຊ້ເວລາພຽງແຕ່ສອງສາມວິນາທີຈາກການຄລິກປຸ່ມເທິງ dashboard ຫຼືໂທຫາ API ເພື່ອເຮັດໃຫ້ການປ່ຽນແປງການຕັ້ງຄ່າທົ່ວໂລກ. ລູກຄ້າມັກຄວາມໄວຂອງການຕິດຕັ້ງນີ້. ແລະຜູ້ເຮັດວຽກເຮັດໃຫ້ພວກເຂົາໃຊ້ຊອບແວທົ່ວໂລກເກືອບທັນທີ. ໂດຍສະເລ່ຍ, Quicksilver ຂະຫຍາຍພັນປະມານ 350 ການປ່ຽນແປງຕໍ່ວິນາທີ.

ແລະ Quicksilver ແມ່ນໄວຫຼາຍ. ໂດຍສະເລ່ຍແລ້ວ, ພວກເຮົາບັນລຸອັດຕາສ່ວນຮ້ອຍທີ 99 ຂອງ 2,29 ວິນາທີເພື່ອເຜີຍແຜ່ການປ່ຽນແປງຂອງຄອມພິວເຕີທຸກໜ່ວຍໃນທົ່ວໂລກ. ຄວາມໄວມັກຈະເປັນສິ່ງທີ່ດີ. ຫຼັງຈາກທີ່ທັງຫມົດ, ເມື່ອທ່ານເປີດໃຊ້ຟັງຊັນຫຼືລ້າງແຄດ, ມັນຈະເກີດຂື້ນເກືອບທັນທີແລະຢູ່ທົ່ວທຸກແຫ່ງ. ການສົ່ງລະຫັດຜ່ານ Cloudflare Workers ເກີດຂຶ້ນໃນຄວາມໄວດຽວກັນ. Cloudflare ສັນຍາລູກຄ້າຂອງຕົນໃຫ້ປັບປຸງໄວໃນເວລາທີ່ເຫມາະສົມ.

ແຕ່ໃນກໍລະນີນີ້, ຄວາມໄວແມ່ນເປັນເລື່ອງຕະຫລົກທີ່ໂຫດຮ້າຍຕໍ່ພວກເຮົາ, ແລະກົດລະບຽບໄດ້ປ່ຽນແປງຢູ່ທົ່ວທຸກແຫ່ງໃນສອງສາມວິນາທີ. ທ່ານອາດຈະສັງເກດເຫັນວ່າລະຫັດ WAF ໃຊ້ Lua. Cloudflare ໃຊ້ Lua ຢ່າງກວ້າງຂວາງໃນການຜະລິດແລະລາຍລະອຽດ Lua ໃນ WAF мы ສົນທະນາແລ້ວ. Lua WAF ໃຊ້ ERCP ພາຍໃນແລະນໍາໃຊ້ backtracking ສໍາລັບການຈັບຄູ່. ມັນບໍ່ມີກົນໄກເພື່ອປ້ອງກັນການສະແດງອອກທີ່ອອກຈາກການຄວບຄຸມ. ຂ້າງລຸ່ມນີ້ຂ້າພະເຈົ້າຈະສົນທະນາເພີ່ມເຕີມກ່ຽວກັບເລື່ອງນີ້ແລະສິ່ງທີ່ພວກເຮົາກໍາລັງເຮັດກ່ຽວກັບມັນ.

ກ່ອນທີ່ກົດລະບຽບຈະຖືກນໍາໄປໃຊ້, ທຸກສິ່ງທຸກຢ່າງໄດ້ດໍາເນີນໄປຢ່າງລຽບງ່າຍ: ການຮ້ອງຂໍການດຶງໄດ້ຖືກສ້າງຂື້ນແລະອະນຸມັດ, ທໍ່ CI / CD ໄດ້ເກັບກໍາແລະທົດສອບລະຫັດ, ການຮ້ອງຂໍການປ່ຽນແປງໄດ້ຖືກສົ່ງຕາມ SOP ທີ່ຄວບຄຸມການປະຕິບັດແລະ rollback, ແລະການຕິດຕັ້ງໄດ້ຖືກສໍາເລັດ.

ຂະບວນການນຳໃຊ້ Cloudflare WAF

ມີບາງຢ່າງຜິດພາດ
ດັ່ງທີ່ຂ້າພະເຈົ້າເວົ້າ, ພວກເຮົາປະຕິບັດກົດລະບຽບ WAF ໃຫມ່ຫຼາຍສິບຂໍ້ໃນທຸກໆອາທິດ, ແລະພວກເຮົາມີລະບົບຫຼາຍຢ່າງເພື່ອປ້ອງກັນຜົນສະທ້ອນທາງລົບຂອງການປະຕິບັດດັ່ງກ່າວ. ແລະໃນເວລາທີ່ບາງສິ່ງບາງຢ່າງຜິດພາດ, ມັນປົກກະຕິແລ້ວແມ່ນປະສົມປະສານຂອງສະຖານະການຫຼາຍຄັ້ງ. ຖ້າທ່ານຊອກຫາເຫດຜົນດຽວ, ແນ່ນອນ, ນີ້ແມ່ນການຮັບປະກັນ, ແຕ່ມັນບໍ່ແມ່ນຄວາມຈິງສະເຫມີ. ເຫຼົ່ານີ້ແມ່ນເຫດຜົນຮ່ວມກັນນໍາໄປສູ່ຄວາມລົ້ມເຫຼວຂອງການບໍລິການ HTTP / HTTPS ຂອງພວກເຮົາ.

1. ວິສະວະກອນຂຽນການສະແດງອອກເປັນປົກກະຕິທີ່ອາດຈະເຮັດໃຫ້ຫຼາຍເກີນໄປ ການຕິດຕາມຄືນ.
2. ຄຸນສົມບັດທີ່ສາມາດປ້ອງກັນການສະແດງອອກປົກກະຕິຈາກການເສຍ CPU ຫຼາຍເກີນໄປໄດ້ຖືກໂຍກຍ້າຍອອກຢ່າງຜິດພາດໃນການ refactoring ຂອງ WAF ຫຼາຍອາທິດກ່ອນຫນ້ານີ້ - ການ refactoring ແມ່ນຈໍາເປັນເພື່ອເຮັດໃຫ້ WAF ໃຊ້ຊັບພະຍາກອນຫນ້ອຍ.
3. ເຄື່ອງຈັກການສະແດງອອກປົກກະຕິບໍ່ມີການຮັບປະກັນຄວາມສັບສົນ.
4. ຊຸດທົດສອບບໍ່ສາມາດກວດພົບການບໍລິໂພກ CPU ຫຼາຍເກີນໄປ.
5. SOP ອະນຸຍາດໃຫ້ການປ່ຽນແປງກົດລະບຽບບໍ່ສຸກເສີນຖືກເຜີຍແຜ່ທົ່ວໂລກໂດຍບໍ່ມີຂະບວນການຫຼາຍຂັ້ນຕອນ.
6. ແຜນການ rollback ຮຽກຮ້ອງໃຫ້ດໍາເນີນການສ້າງ WAF ເຕັມສອງຄັ້ງ, ເຊິ່ງໃຊ້ເວລາດົນ.
7. ການແຈ້ງເຕືອນທຳອິດກ່ຽວກັບບັນຫາການສັນຈອນທົ່ວໂລກໄດ້ຖືກກະຕຸ້ນໃຫ້ຊ້າເກີນໄປ.
8. ພວກເຮົາໃຊ້ເວລາໄລຍະໜຶ່ງເພື່ອອັບເດດໜ້າສະຖານະ.
9. ພວກ​ເຮົາ​ມີ​ບັນ​ຫາ​ໃນ​ການ​ເຂົ້າ​ເຖິງ​ລະ​ບົບ​ເນື່ອງ​ຈາກ​ຄວາມ​ຜິດ​ພາດ​, ແລະ​ຂັ້ນ​ຕອນ​ການ bypass ບໍ່​ໄດ້​ສ້າງ​ຕັ້ງ​ຂຶ້ນ​ໄດ້​ດີ​.
10. ວິສະວະກອນ SRE ສູນເສຍການເຂົ້າເຖິງບາງລະບົບເພາະວ່າຂໍ້ມູນປະຈໍາຕົວຂອງພວກເຂົາຫມົດອາຍຸຍ້ອນເຫດຜົນດ້ານຄວາມປອດໄພ.
11. ລູກຄ້າຂອງພວກເຮົາບໍ່ມີການເຂົ້າເຖິງ dashboard Cloudflare ຫຼື API ເພາະວ່າພວກເຂົາຜ່ານພາກພື້ນ Cloudflare.

ສິ່ງທີ່ມີການປ່ຽນແປງນັບຕັ້ງແຕ່ວັນພະຫັດທີ່ຜ່ານມາ

ທໍາອິດ, ພວກເຮົາຢຸດເຊົາການເຮັດວຽກທັງຫມົດກ່ຽວກັບການປ່ອຍສໍາລັບ WAF ແລະກໍາລັງເຮັດດັ່ງຕໍ່ໄປນີ້:

1. ພວກເຮົາກຳລັງແນະນຳການປ້ອງກັນການໃຊ້ CPU ເກີນຂອບເຂດທີ່ພວກເຮົາເອົາອອກ. (ພ້ອມ)
2. ຄູ່ມືການກວດສອບທັງຫມົດ 3868 ກົດລະບຽບໃນກົດລະບຽບທີ່ຄຸ້ມຄອງສໍາລັບ WAF ເພື່ອຊອກຫາແລະແກ້ໄຂກໍລະນີອື່ນໆທີ່ເປັນໄປໄດ້ຂອງ backtracking ຫຼາຍເກີນໄປ. (ການ​ກວດ​ສອບ​ສໍາ​ເລັດ​)
3. ພວກເຮົາລວມເອົາໂປຣໄຟລ໌ປະສິດທິພາບສໍາລັບກົດລະບຽບທັງຫມົດໃນຊຸດທົດສອບ. (ຄາດການ: 19 ກໍລະກົດ)
4. ປ່ຽນເປັນເຄື່ອງຈັກໃນການສະແດງອອກປົກກະຕິ re2 ຫຼື rust - ທັງສອງສະຫນອງການຮັບປະກັນ runtime. (ຄາດການ: ວັນທີ 31 ກໍລະກົດ)
5. ພວກເຮົາກຳລັງຂຽນ SOP ຄືນໃໝ່ເພື່ອນຳໃຊ້ກົດລະບຽບໃນຂັ້ນຕອນຕ່າງໆ, ຄືກັບຊອບແວອື່ນໆໃນ Cloudflare, ແຕ່ໃນຂະນະດຽວກັນກໍມີຄວາມສາມາດໃນການນຳໃຊ້ຢ່າງຮີບດ່ວນໃນທົ່ວໂລກ ຖ້າການໂຈມຕີໄດ້ເລີ່ມຂຶ້ນແລ້ວ.
6. ພວກເຮົາກຳລັງພັດທະນາຄວາມສາມາດໃນການລຶບ Cloudflare dashboard ແລະ API ອອກຈາກພາກພື້ນ Cloudflare ຢ່າງຮີບດ່ວນ.
7. ການອັບເດດໜ້າອັດຕະໂນມັດ ສະຖານະ Cloudflare.

ໄລຍະຍາວພວກເຮົາກໍາລັງຍ້າຍອອກໄປຈາກ Lua WAF ຂ້າພະເຈົ້າໄດ້ຂຽນສອງສາມປີກ່ອນ. ຍ້າຍ WAF ໄປ ລະບົບໄຟວໍໃໝ່. ດ້ວຍວິທີນີ້ WAF ຈະໄວຂຶ້ນແລະໄດ້ຮັບການປົກປ້ອງເພີ່ມເຕີມ.

ສະຫລຸບ

ຄວາມລົ້ມເຫຼວນີ້ເຮັດໃຫ້ເກີດບັນຫາສໍາລັບພວກເຮົາແລະລູກຄ້າຂອງພວກເຮົາ. ພວກເຮົາປະຕິບັດຢ່າງໄວວາເພື່ອແກ້ໄຂສະຖານະການແລະປະຈຸບັນກໍາລັງເຮັດວຽກກ່ຽວກັບຂໍ້ບົກພ່ອງໃນຂະບວນການທີ່ເຮັດໃຫ້ເກີດອຸປະຕິເຫດ, ເຊັ່ນດຽວກັນກັບການຂຸດຂຸມເລິກຕື່ມອີກເພື່ອປ້ອງກັນບັນຫາທີ່ອາດຈະເກີດຂື້ນດ້ວຍການສະແດງອອກເປັນປົກກະຕິໃນອະນາຄົດໃນເວລາທີ່ການເຄື່ອນຍ້າຍໄປສູ່ເຕັກໂນໂລຢີໃຫມ່.

ພວກເຮົາມີຄວາມອັບອາຍຫຼາຍກ່ຽວກັບບັນຫານີ້ ແລະຂໍໂທດລູກຄ້າຂອງພວກເຮົາ. ພວກເຮົາຫວັງວ່າການປ່ຽນແປງເຫຼົ່ານີ້ຈະຮັບປະກັນວ່າບາງສິ່ງບາງຢ່າງເຊັ່ນນີ້ຈະບໍ່ເກີດຂຶ້ນອີກ.

ຄໍາຮ້ອງສະຫມັກ. Backtracking ການສະແດງອອກປົກກະຕິ

ເພື່ອເຂົ້າໃຈວິທີການສະແດງອອກ:

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

ກິນຊັບພະຍາກອນ CPU ທັງຫມົດ, ທ່ານຈໍາເປັນຕ້ອງຮູ້ຫນ້ອຍຫນຶ່ງກ່ຽວກັບວິທີທີ່ເຄື່ອງຈັກສະແດງອອກປົກກະຕິມາດຕະຖານເຮັດວຽກ. ບັນຫາຢູ່ທີ່ນີ້ແມ່ນຮູບແບບ .*(?:.*=.*). (?: ແລະທີ່ສອດຄ້ອງກັນ ) ແມ່ນກຸ່ມທີ່ບໍ່ແມ່ນການຈັບພາບ (ຄືການສະແດງອອກໃນວົງເລັບຖືກຈັດກຸ່ມເປັນການສະແດງຜົນດຽວ).

ໃນສະພາບການຂອງການບໍລິໂພກ CPU ຫຼາຍເກີນໄປ, ຮູບແບບນີ້ສາມາດຖືກອະທິບາຍເປັນ .*.*=.*. ໃນຮູບແບບນີ້, ຮູບແບບເບິ່ງຄືວ່າສະລັບສັບຊ້ອນທີ່ບໍ່ຈໍາເປັນ. ແຕ່ສໍາຄັນກວ່ານັ້ນ, ໃນໂລກທີ່ແທ້ຈິງ, ການສະແດງອອກ (ເຊັ່ນການສະແດງອອກທີ່ສັບສົນໃນກົດລະບຽບ WAF) ທີ່ຂໍໃຫ້ເຄື່ອງຈັກກົງກັບຊິ້ນສ່ວນທີ່ປະຕິບັດຕາມໂດຍຊິ້ນສ່ວນອື່ນສາມາດນໍາໄປສູ່ໄພພິບັດທາງຫລັງ. ແລະວ່າເປັນຫຍັງ.

ໃນການສະແດງອອກເປັນປົກກະຕິ . ຫມາຍຄວາມວ່າທ່ານຈໍາເປັນຕ້ອງຈັບຄູ່ຫນຶ່ງລັກສະນະ, .* - ຈັບຄູ່ຕົວອັກສອນສູນຫຼືຫຼາຍກວ່າ "greedily", ນັ້ນແມ່ນ, ຈັບຕົວສູງສຸດ, ດັ່ງນັ້ນ .*.*=.* ຫມາຍ​ຄວາມ​ວ່າ​ຈັບ​ຄູ່​ສູນ​ຫຼື​ຫຼາຍ​ຕົວ​ອັກ​ສອນ​, ຫຼັງ​ຈາກ​ນັ້ນ​ຈັບ​ຄູ່​ສູນ​ຫຼື​ຫຼາຍ​ຕົວ​ອັກ​ສອນ​, ຊອກ​ຫາ​ຕົວ​ອັກ​ສອນ = ຕົວ​ອັກ​ສອນ​, ກົງ​ສູນ​ຫຼື​ຫຼາຍ​ຕົວ​ອັກ​ສອນ​.

ໃຫ້ເອົາເສັ້ນການທົດສອບ x=x. ມັນກົງກັນກັບການສະແດງອອກ .*.*=.*. .*.* ກ່ອນເຄື່ອງໝາຍເທົ່າກັນຈະກົງກັບຕົວທຳອິດ x (ຫນຶ່ງ​ໃນ​ກຸ່ມ​ .* ກົງກັບ x, ແລະທີສອງ - ຕົວອັກສອນສູນ). .* after = matches last x.

ການປຽບທຽບນີ້ຮຽກຮ້ອງໃຫ້ມີ 23 ຂັ້ນຕອນ. ກຸ່ມທໍາອິດ .* в .*.*=.* ປະຕິບັດຢ່າງໂລບມາກແລະກົງກັບສາຍທັງ ໝົດ x=x. ເຄື່ອງຈັກຍ້າຍໄປຫາກຸ່ມຕໍ່ໄປ .*. ພວກ​ເຮົາ​ບໍ່​ມີ​ຕົວ​ອັກ​ສອນ​ໃດ​ທີ່​ຈະ​ກົງ​ກັນ​, ດັ່ງ​ນັ້ນ​ກຸ່ມ​ທີ​ສອງ​ .* ກົງກັບສູນຕົວອັກສອນ (ອັນນີ້ແມ່ນອະນຸຍາດ). ຫຼັງຈາກນັ້ນ, ເຄື່ອງຈັກເຄື່ອນຍ້າຍໄປທີ່ປ້າຍ =. ບໍ່ມີສັນຍາລັກເພີ່ມເຕີມ (ກຸ່ມທໍາອິດ .* ໃຊ້ການສະແດງອອກທັງຫມົດ x=x), ບໍ່ມີການປຽບທຽບເກີດຂຶ້ນ.

ແລະຫຼັງຈາກນັ້ນເຄື່ອງຈັກການສະແດງອອກປົກກະຕິກັບຄືນສູ່ຈຸດເລີ່ມຕົ້ນ. ລາວກ້າວໄປສູ່ກຸ່ມທໍາອິດ .* ແລະປຽບທຽບມັນ с x= (ແທນທີ່ຈະ x=x), ແລະຫຼັງຈາກນັ້ນໃຊ້ເວລາໃນກຸ່ມທີສອງ .*. ກຸ່ມທີສອງ .* ແມ່ນປຽບທຽບກັບຄັ້ງທີສອງ x, ແລະພວກເຮົາອີກເທື່ອຫນຶ່ງບໍ່ມີຕົວອັກສອນປະໄວ້. ແລະໃນເວລາທີ່ເຄື່ອງຈັກໄປຮອດອີກເທື່ອຫນຶ່ງ = в .*.*=.*, ບໍ່ມີຫຍັງເຮັດວຽກ. ແລະ​ເຂົາ​ໄດ້​ກັບ​ຄືນ​ໄປ​ບ່ອນ​ອີກ​ເທື່ອ​ຫນຶ່ງ.

ເວລານີ້ກຸ່ມ .* ຍັງກົງກັນ x=, ແຕ່ກຸ່ມທີສອງ .* ບໍ່​ມີ​ອີກ​ແລ້ວ x, ແລະສູນຕົວອັກສອນ. ເຄື່ອງຈັກກໍາລັງພະຍາຍາມຊອກຫາຕົວຫນັງສື = ໃນ​ຮູບ​ແບບ​ການ​ .*.*=.*, ແຕ່ບໍ່ໄດ້ອອກມາ (ຫຼັງຈາກທັງຫມົດ, ກຸ່ມທໍາອິດໄດ້ຄອບຄອງມັນແລ້ວ .*). ແລະ​ເຂົາ​ໄດ້​ກັບ​ຄືນ​ໄປ​ບ່ອນ​ອີກ​ເທື່ອ​ຫນຶ່ງ.

ຄັ້ງນີ້ເປັນກຸ່ມທຳອິດ .* ໃຊ້ເວລາພຽງແຕ່ x ທໍາອິດ. ແຕ່ກຸ່ມທີສອງ .* "greedily" captures =x. ເຈົ້າເດົາແລ້ວບໍ່ວ່າມັນຈະເກີດຫຍັງຂຶ້ນ? ເຄື່ອງຈັກພະຍາຍາມທີ່ຈະກົງກັບຕົວຫນັງສື =, ລົ້ມເຫລວແລະເຮັດໃຫ້ backtracking ອື່ນ.

ກຸ່ມ ທຳ ອິດ .* ຍັງກົງກັບອັນທໍາອິດ x. ທີສອງ .* ພຽງແຕ່ໃຊ້ເວລາ =. ແນ່ນອນ, ເຄື່ອງຈັກບໍ່ສາມາດກົງກັບຕົວຫນັງສືໄດ້ =, ເນື່ອງຈາກວ່າກຸ່ມທີສອງໄດ້ເຮັດແລ້ວນີ້ .*. ແລະອີກເທື່ອຫນຶ່ງ backtracking. ແລະພວກເຮົາກໍາລັງພະຍາຍາມຈັບຄູ່ສາຍຂອງສາມຕົວອັກສອນ!

ດັ່ງນັ້ນ, ກຸ່ມທໍາອິດ .* ກົງກັບພຽງແຕ່ອັນທໍາອິດ x, ທີສອງ .* - ມີລັກສະນະສູນ, ແລະເຄື່ອງຈັກສຸດທ້າຍກົງກັບຕົວຫນັງສື = ໃນການສະແດງອອກ с = ໃນແຖວ. ຕໍ່ໄປແມ່ນກຸ່ມສຸດທ້າຍ .* ແມ່ນປຽບທຽບກັບອັນສຸດທ້າຍ x.

23 ຂັ້ນ​ຕອນ​ພຽງ​ແຕ່​ສໍາ​ລັບ​ການ​ x=x. ເບິ່ງວິດີໂອສັ້ນກ່ຽວກັບການໃຊ້ Perl Regexp::Debugger, ເຊິ່ງສະແດງໃຫ້ເຫັນວິທີການຂັ້ນຕອນແລະ backtracking ເກີດຂຶ້ນ.

ນີ້ແມ່ນແລ້ວຫຼາຍຂອງການເຮັດວຽກ, ແຕ່ສິ່ງທີ່ຖ້າຫາກວ່າແທນທີ່ຈະ x=x ພວກ​ເຮົາ​ຈະ​ມີ x=xx? ນັ້ນແມ່ນ 33 ຂັ້ນຕອນ. ແລະຖ້າ x=xxx? 45. ຄວາມສໍາພັນບໍ່ແມ່ນເສັ້ນ. ເສັ້ນສະແດງການປຽບທຽບຈາກ x=x ການ x=xxxxxxxxxxxxxxxxxxxx (20 x после =). ຖ້າພວກເຮົາມີ 20 x ຫຼັງຈາກ =, ເຄື່ອງຈັກສໍາເລັດການຈັບຄູ່ໃນ 555 ຂັ້ນຕອນ! (ນອກຈາກນັ້ນ, ຖ້າພວກເຮົາສູນເສຍ x= ແລະສາຍພຽງແຕ່ປະກອບດ້ວຍ 20 x, ເຄື່ອງຈັກຈະໃຊ້ເວລາ 4067 ຂັ້ນຕອນເພື່ອເຂົ້າໃຈວ່າບໍ່ມີການແຂ່ງຂັນກັນ).

ວິດີໂອນີ້ສະແດງໃຫ້ເຫັນ backtracking ທັງຫມົດສໍາລັບການປຽບທຽບ x=xxxxxxxxxxxxxxxxxxxx:

ບັນຫາແມ່ນວ່າເມື່ອຂະຫນາດຂອງສະຕຣິງເພີ່ມຂຶ້ນ, ເວລາການຈັບຄູ່ຈະເຕີບໂຕ super-linearly. ແຕ່ສິ່ງທີ່ອາດຈະຮ້າຍແຮງກວ່າເກົ່າຖ້າຫາກວ່າການສະແດງອອກເປັນປົກກະຕິໄດ້ຖືກດັດແກ້ເລັກນ້ອຍ. ໃຫ້ເວົ້າວ່າພວກເຮົາມີ .*.*=.*; (ນັ້ນ​ແມ່ນ​ວ່າ​ມີ semicolon ຕົວ​ໜັງ​ສື​ຢູ່​ທ້າຍ​ຂອງ​ຮູບ​ແບບ). ຕົວຢ່າງ, ເພື່ອຈັບຄູ່ການສະແດງອອກເຊັ່ນ foo=bar;.

ແລະທີ່ນີ້ backtracking ຈະເປັນໄພພິບັດທີ່ແທ້ຈິງ. ສໍາລັບການປຽບທຽບ x=x ມັນຈະໃຊ້ເວລາ 90 ຂັ້ນຕອນ, ບໍ່ແມ່ນ 23. ແລະຈໍານວນນັ້ນກໍາລັງເຕີບໂຕຢ່າງໄວວາ. ເພື່ອປຽບທຽບ x= ແລະ 20 x, 5353 ຂັ້ນຕອນແມ່ນຈໍາເປັນ. ນີ້ແມ່ນຕາຕະລາງ. ເບິ່ງຄ່າແກນ Y ເມື່ອປຽບທຽບກັບຕາຕະລາງທີ່ຜ່ານມາ.

ຖ້າ​ຫາກ​ວ່າ​ທ່ານ​ມີ​ຄວາມ​ສົນ​ໃຈ​, ກວດ​ສອບ​ການ​ອອກ​ທັງ​ຫມົດ 5353 ຂັ້ນ​ຕອນ​ທີ່​ບໍ່​ສໍາ​ເລັດ​ການ​ຈັບ​ຄູ່​ x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;

ໂດຍການໃຊ້ຄົນຂີ້ຄ້ານຫຼາຍກວ່າການຈັບຄູ່ທີ່ໂລບມາກ, ຂອບເຂດຂອງການຕິດຕາມຫຼັງສາມາດຄວບຄຸມໄດ້. ຖ້າພວກເຮົາປ່ຽນການສະແດງອອກຕົ້ນສະບັບເປັນ .*?.*?=.*?, ສໍາລັບການປຽບທຽບ x=x ມັນຈະໃຊ້ເວລາ 11 ຂັ້ນຕອນ (ບໍ່ແມ່ນ 23). ສໍາລັບ x=xxxxxxxxxxxxxxxxxxxx. ທັງຫມົດເພາະວ່າ ? после .* ບອກເຄື່ອງຈັກໃຫ້ກົງກັບຕົວເລກຕໍາ່ສຸດທີ່ຂອງຕົວອັກສອນກ່ອນທີ່ຈະດໍາເນີນຕໍ່ໄປ.

ແຕ່ແຜນທີ່ຂີ້ກຽດບໍ່ໄດ້ແກ້ໄຂບັນຫາ backtracking ຢ່າງສົມບູນ. ຖ້າພວກເຮົາປ່ຽນແທນຕົວຢ່າງໄພພິບັດ .*.*=.*; ສຸດ .*?.*?=.*?;, ເວລາປະຕິບັດຈະຍັງຄົງຢູ່ຄືກັນ. x=x ຍັງຕ້ອງການ 555 ຂັ້ນຕອນ, ແລະ x= ແລະ 20 x - 5353.

ສິ່ງດຽວທີ່ສາມາດເຮັດໄດ້ (ນອກເຫນືອຈາກການຂຽນຄືນໃຫມ່ຢ່າງສົມບູນແບບສໍາລັບຄວາມສະເພາະຫຼາຍກວ່າເກົ່າ) ແມ່ນການປະຖິ້ມເຄື່ອງຈັກການສະແດງອອກປົກກະຕິທີ່ມີກົນໄກ backtracking ຂອງມັນ. ນີ້ແມ່ນສິ່ງທີ່ພວກເຮົາຈະເຮັດໃນສອງສາມອາທິດຂ້າງຫນ້າ.

ການແກ້ໄຂບັນຫານີ້ແມ່ນເປັນທີ່ຮູ້ຈັກນັບຕັ້ງແຕ່ 1968, ໃນເວລາທີ່ Kent Thompson ຂຽນບົດຄວາມ ເຕັກນິກການຂຽນໂປລແກລມ: ສູດການຄິດໄລ່ການຊອກຫາແບບປົກກະຕິ (“ວິທີການຂຽນໂປຣແກຣມ: ສູດການຄິດໄລ່ການຊອກຫາແບບປົກກະຕິ”). ບົດຄວາມອະທິບາຍກົນໄກທີ່ອະນຸຍາດໃຫ້ທ່ານສາມາດປ່ຽນການສະແດງອອກປົກກະຕິເຂົ້າໄປໃນເຄື່ອງລັດທີ່ບໍ່ມີກໍານົດຂອບເຂດກໍານົດ, ແລະຫຼັງຈາກການປ່ຽນແປງຂອງລັດໃນເຄື່ອງຈັກຂອງລັດທີ່ບໍ່ມີກໍານົດ, ໃຊ້ສູດການຄິດໄລ່ທີ່ເວລາປະຕິບັດແມ່ນຂຶ້ນກັບສາຍທີ່ກົງກັນ.

ວິທີການຂຽນໂປລແກລມ
ສູດການຄິດໄລ່ການຊອກຫາແບບປົກກະຕິ
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New Jersey

ມັນອະທິບາຍວິທີການຄົ້ນຫາຕົວອັກສອນສະເພາະໃນຂໍ້ຄວາມແລະປຶກສາຫາລືກ່ຽວກັບການປະຕິບັດວິທີການນີ້ໃນຮູບແບບ compiler. compiler ເອົາການສະແດງອອກປົກກະຕິເປັນລະຫັດແຫຼ່ງແລະຜະລິດໂຄງການ IBM 7094 ເປັນລະຫັດວັດຖຸ. ໂປຣແກມວັດຖຸເອົາການປ້ອນຂໍ້ມູນໃນຮູບແບບຂອງຂໍ້ຄວາມຄົ້ນຫາ ແລະສົ່ງສັນຍານແຕ່ລະຄັ້ງທີ່ສາຍຂອງຂໍ້ຄວາມຖືກຈັບຄູ່ກັບການສະແດງຜົນປົກກະຕິ. ບົດຄວາມໃຫ້ຕົວຢ່າງ, ບັນຫາແລະວິທີແກ້ໄຂ.

ລະບົບວິເຄາະ
ສູດການຄິດໄລ່ການຄົ້ນຫາທີ່ຜ່ານມາສົ່ງຜົນໃຫ້ backtracking ຖ້າການຄົ້ນຫາທີ່ປະສົບຜົນສໍາເລັດບາງສ່ວນບໍ່ໄດ້ຜົນ.

ໃນຮູບແບບການລວບລວມ, ສູດການຄິດໄລ່ບໍ່ໄດ້ເຮັດວຽກກັບສັນຍາລັກ. ມັນຜ່ານຄໍາແນະນໍາເພື່ອລວບລວມລະຫັດ. ການປະຕິບັດແມ່ນໄວຫຼາຍ - ຫຼັງຈາກຖ່າຍທອດຂໍ້ມູນໄປທາງເທີງຂອງບັນຊີລາຍຊື່ປະຈຸບັນ, ມັນອັດຕະໂນມັດຊອກຫາຕົວອັກສອນຕິດຕໍ່ກັນທີ່ເປັນໄປໄດ້ທັງຫມົດໃນການສະແດງຜົນປົກກະຕິ.
ການລວບລວມແລະວິທີການຄົ້ນຫາແມ່ນລວມຢູ່ໃນຕົວແກ້ໄຂຂໍ້ຄວາມທີ່ແບ່ງປັນເວລາເປັນການຄົ້ນຫາແບບບໍລິບົດ. ແນ່ນອນ, ນີ້ແມ່ນຢູ່ໄກຈາກຄໍາຮ້ອງສະຫມັກດຽວຂອງຂະບວນການຄົ້ນຫາດັ່ງກ່າວ. ຕົວຢ່າງ, ຕົວແປຂອງ algorithm ນີ້ຖືກນໍາໃຊ້ເປັນການຄົ້ນຫາສັນຍາລັກໃນຕາຕະລາງໃນ assembler.
ມັນສົມມຸດວ່າຜູ້ອ່ານຈະຄຸ້ນເຄີຍກັບການສະແດງອອກປົກກະຕິແລະພາສາການຂຽນໂປຼແກຼມຄອມພິວເຕີ IBM 7094.

ຜູ້ສັງລວມ
compiler ປະກອບດ້ວຍສາມຂັ້ນຕອນທີ່ເຮັດວຽກຂະຫນານ. ຂັ້ນຕອນທໍາອິດແມ່ນການກັ່ນຕອງ syntax, ເຊິ່ງອະນຸຍາດໃຫ້ພຽງແຕ່ syntactically ແກ້ໄຂການສະແດງອອກປົກກະຕິຜ່ານ. ຂັ້ນຕອນນີ້ຍັງໃສ່ຕົວປະຕິບັດການ "·" ເພື່ອໃຫ້ກົງກັບຄໍາເວົ້າປົກກະຕິ. ໃນຂັ້ນຕອນທີສອງ, ການສະແດງອອກປົກກະຕິຈະຖືກປ່ຽນເປັນແບບຟອມ postfix. ໃນຂັ້ນຕອນທີສາມ, ລະຫັດວັດຖຸຖືກສ້າງຂື້ນ. 2 ຂັ້ນຕອນທໍາອິດແມ່ນເຫັນໄດ້ຊັດເຈນ, ແລະພວກເຮົາຈະບໍ່ຢູ່ກັບພວກມັນ.

ບົດຄວາມຂອງ Thompson ບໍ່ໄດ້ເວົ້າກ່ຽວກັບເຄື່ອງຈັກຂອງລັດ finite ທີ່ບໍ່ຖືກກໍານົດ, ແຕ່ມັນອະທິບາຍວິທີການກໍານົດເວລາເສັ້ນໄດ້ດີແລະນໍາສະເຫນີໂຄງການ ALGOL-60 ທີ່ສ້າງລະຫັດພາສາປະກອບສໍາລັບ IBM 7094. ການປະຕິບັດແມ່ນ tricky, ແຕ່ແນວຄວາມຄິດແມ່ນງ່າຍດາຍຫຼາຍ.

ເສັ້ນທາງຄົ້ນຫາໃນປະຈຸບັນ. ມັນຖືກສະແດງໂດຍໄອຄອນ ⊕ ທີ່ມີການປ້ອນຂໍ້ມູນໜຶ່ງອັນ ແລະສອງຜົນໄດ້ຮັບ.
ຮູບທີ 1 ສະແດງຫນ້າທີ່ຂອງຂັ້ນຕອນການລວບລວມທີສາມເມື່ອປ່ຽນຕົວຢ່າງການສະແດງອອກປົກກະຕິ. ສາມຕົວອັກສອນທໍາອິດໃນຕົວຢ່າງແມ່ນ a, b, c, ແລະແຕ່ລະຕົວສ້າງ stack entry S[i] ແລະຊ່ອງຂໍ້ມູນ NNODE.

NNODE ໄປຫາລະຫັດທີ່ມີຢູ່ເພື່ອສ້າງການສະແດງອອກປົກກະຕິຜົນໄດ້ຮັບໃນການເຂົ້າ stack ດຽວ (ເບິ່ງຮູບ 5)

ນີ້ແມ່ນສິ່ງທີ່ສະແດງອອກເປັນປົກກະຕິ .*.*=.*, ຖ້າທ່ານຈິນຕະນາການມັນຄືກັບຮູບພາບຈາກບົດຄວາມຂອງ Thompson.

ໃນຮູບ. 0 ມີຫ້າລັດທີ່ເລີ່ມຕົ້ນຈາກ 0, ແລະ 3 ວົງຈອນທີ່ເລີ່ມຕົ້ນຈາກລັດ 1, 2 ແລະ 3. ສາມວົງຈອນນີ້ເທົ່າກັບສາມ .* ໃນ​ການ​ສະ​ແດງ​ອອກ​ເປັນ​ປົກ​ກະ​ຕິ​. ຮູບໄຂ່ 3 ອັນທີ່ມີຈຸດກົງກັນກັບສັນຍາລັກອັນດຽວ. ຮູບໄຂ່ທີ່ມີສັນຍາລັກ = ກົງກັບຕົວອັກສອນ =. ລັດ 4 ແມ່ນສຸດທ້າຍ. ຖ້າພວກເຮົາບັນລຸມັນ, ຫຼັງຈາກນັ້ນການສະແດງອອກປົກກະຕິແມ່ນກົງກັນ.

ເພື່ອເບິ່ງວ່າແຜນວາດລັດດັ່ງກ່າວສາມາດໃຊ້ສໍາລັບການຈັບຄູ່ການສະແດງອອກປົກກະຕິໄດ້ແນວໃດ .*.*=.*, ພວກເຮົາຈະເບິ່ງການຈັບຄູ່ສະຕຣິງ x=x. ໂຄງການເລີ່ມຕົ້ນຈາກລັດ 0, ດັ່ງທີ່ສະແດງຢູ່ໃນຮູບ. 1.

ເພື່ອໃຫ້ algorithm ນີ້ເຮັດວຽກ, ເຄື່ອງຈັກຂອງລັດຈະຕ້ອງຢູ່ໃນຫຼາຍລັດພ້ອມໆກັນ. ເຄື່ອງກໍານົດຂອບເຂດທີ່ບໍ່ກໍານົດຈະເຮັດການຫັນປ່ຽນທີ່ເປັນໄປໄດ້ທັງຫມົດພ້ອມໆກັນ.

ກ່ອນທີ່ມັນຈະມີເວລາທີ່ຈະອ່ານຂໍ້ມູນການປ້ອນຂໍ້ມູນ, ມັນຈະເຂົ້າໄປໃນທັງສອງລັດທໍາອິດ (1 ແລະ 2), ດັ່ງທີ່ສະແດງຢູ່ໃນຮູບ. 2.

ໃນຮູບ. 2 ສະແດງໃຫ້ເຫັນສິ່ງທີ່ເກີດຂື້ນເມື່ອລາວເບິ່ງຄັ້ງທໍາອິດ x в x=x. x ສາມາດສ້າງແຜນທີ່ໄປຫາຈຸດສູງສຸດ, ໄປຈາກລັດ 1 ແລະກັບຄືນໄປຫາລັດ 1. ຫຼື x ສາມາດສ້າງແຜນທີ່ໄປຫາຈຸດຂ້າງລຸ່ມນີ້, ການເຄື່ອນຍ້າຍຈາກລັດ 2 ແລະກັບຄືນໄປບ່ອນລັດ 2.

ຫຼັງຈາກຈັບຄູ່ທໍາອິດ x в x=x ພວກເຮົາຍັງຢູ່ໃນລັດ 1 ແລະ 2. ພວກເຮົາບໍ່ສາມາດເຂົ້າຫາລັດ 3 ຫຼື 4 ໄດ້ເພາະວ່າພວກເຮົາຕ້ອງການຕົວໜັງສື. =.

ສູດການຄິດໄລ່ຫຼັງຈາກນັ້ນພິຈາລະນາ = в x=x. ເຊັ່ນດຽວກັນກັບ x ກ່ອນ, ມັນສາມາດຖືກຈັບຄູ່ກັບທັງສອງ loops ເທິງສຸດຈາກລັດ 1 ຫາລັດ 1 ຫຼືຈາກລັດ 2 ຫາລັດ 2, ແຕ່ສູດການຄິດໄລ່ສາມາດຈັບຄູ່ຕົວຫນັງສືໄດ້. = ແລະຍ້າຍຈາກລັດ 2 ໄປລັດ 3 (ແລະທັນທີ 4). ນີ້ແມ່ນສະແດງຢູ່ໃນຮູບ. 3.

ຫຼັງຈາກນັ້ນ, algorithm ຍ້າຍໄປອັນສຸດທ້າຍ x в x=x. ຈາກລັດ 1 ແລະ 2 ການຫັນປ່ຽນອັນດຽວກັນແມ່ນເປັນໄປໄດ້ກັບລັດ 1 ແລະ 2. ຈາກລັດ 3. x ສາ​ມາດ​ຈັບ​ຄູ່​ຈຸດ​ຢູ່​ທາງ​ຂວາ​ແລະ​ກັບ​ຄືນ​ໄປ​ບ່ອນ 3 ລັດ​.

ໃນຂັ້ນຕອນນີ້, ແຕ່ລະລັກສະນະ x=x ພິຈາລະນາ, ແລະນັບຕັ້ງແຕ່ພວກເຮົາໄດ້ມາຮອດລັດ 4, ການສະແດງອອກປົກກະຕິຈະກົງກັບສະຕຣິງນັ້ນ. ແຕ່ລະຕົວລະຄອນຖືກປະມວນຜົນຄັ້ງດຽວ, ສະນັ້ນ ສູດການຄິດໄລ່ນີ້ແມ່ນເສັ້ນຊື່ຕາມຄວາມຍາວຂອງສາຍປ້ອນຂໍ້ມູນ. ແລະບໍ່ມີ backtracking.

ແນ່ນອນ, ຫຼັງຈາກເຖິງລັດ 4 (ເມື່ອ algorithm ໄດ້ກົງກັນ x=) ການສະແດງອອກປົກກະຕິທັງຫມົດແມ່ນກົງກັນ, ແລະ algorithm ອາດຈະຢຸດເຊົາໂດຍບໍ່ມີການພິຈາລະນາມັນທັງຫມົດ x.

ສູດການຄິດໄລ່ນີ້ຂຶ້ນກັບຂະໜາດຂອງສາຍເຂົ້າ.

ແຫຼ່ງຂໍ້ມູນ: www.habr.com