የCloudflare ብልሽት ዝርዝሮች ጁላይ 2፣ 2019

የዛሬ 9 አመት ገደማ Cloudflare ትንሽ ኩባንያ ነበር እና አልሰራሁበትም ደንበኛ ነበርኩ። Cloudflare ከጀመረ ከአንድ ወር በኋላ በጣቢያዬ ላይ ማንቂያ ደረሰኝ። jgc.orgዲ ኤን ኤስ የሚሰራ አይመስልም። Cloudflare ለውጥ አድርጓል የፕሮቶኮል ማቋቋሚያዎች፣ እና የተሰበረ ዲ ኤን ኤስ ነበር።

ወዲያውኑ "የእኔ ዲ ኤን ኤስ የት አለ?" በሚል ርዕስ ለማቲው ፕሪንስ ኢሜል ላክሁ እና ረጅም መልስ ላከ ቴክኒካዊ ዝርዝሮች (ሁሉንም ደብዳቤዎች እዚህ ያንብቡ), እኔም መለስኩለት፡-

ከ: ጆን ግርሃም-ኩም
ቀን፡ ጥቅምት 7/2010 ከቀኑ 9፡14 ጥዋት
ርዕሰ ጉዳይ፡ ድጋሚ፡ የእኔ ዲ ኤን ኤስ የት ነው ያለው?
ለ፡ ማቲዎስ ልዑል

አሪፍ ዘገባ አመሰግናለሁ። ችግሮች ካሉ በእርግጠኝነት እደውላለሁ። ምናልባት ሁሉንም ቴክኒካዊ መረጃዎች በሚሰበስቡበት ጊዜ ስለዚህ ጉዳይ ጽሑፍ መጻፍ ጠቃሚ ነው። ሰዎች ግልጽ እና ታማኝ ታሪክን ይወዳሉ ብዬ አስባለሁ። በተለይ ከተጀመረበት ጊዜ ጀምሮ ትራፊክ እንዴት እንዳደገ ለማሳየት ግራፎችን ካያይዙት።

በጣቢያዬ ላይ ጥሩ ክትትል አለኝ, እና ስለ እያንዳንዱ ውድቀት ኤስኤምኤስ እቀበላለሁ. ክትትል እንደሚያሳየው ውድቀቱ ከ13፡03፡07 እስከ 14፡04፡12 ነበር። ፈተናዎች በየአምስት ደቂቃዎች ይካሄዳሉ.

እርግጠኛ ነኝ ሁሉንም ነገር ትረዳለህ። እርግጠኛ ነህ በአውሮፓ ውስጥ የራስህ ሰው እንደማትፈልግ? 🙂

እርሱም መልሶ።

ከ፡ ማቴዎስ ልዑል
ቀን፡ ጥቅምት 7/2010 ከቀኑ 9፡57 ጥዋት
ርዕሰ ጉዳይ፡ ድጋሚ፡ የእኔ ዲ ኤን ኤስ የት ነው ያለው?
ለ፡ ጆን ግርሃም-ከምሚንግ

አመሰግናለሁ. ለጻፉት ሁሉ ምላሽ ሰጥተናል። አሁን ወደ ቢሮ እየሄድኩ ነው እና በብሎግ ላይ የሆነ ነገር እንጽፋለን ወይም በማስታወቂያ ሰሌዳችን ላይ ይፋዊ ፖስት እንሰካለን። ሙሉ በሙሉ እስማማለሁ, ታማኝነት ሁሉም ነገር ነው.

አሁን Cloudflare በእውነት ትልቅ ኩባንያ ነው, ለእሱ እሰራለሁ, እና አሁን ስለ ስህተታችን, ውጤቶቹ እና ድርጊቶቻችን በግልፅ መጻፍ አለብኝ.

ጁላይ 2 ክስተቶች

በጁላይ 2፣ በ WAF የሚተዳደሩ ደንቦች ውስጥ አዲስ ህግ አውጥተናል፣ በዚህ ምክንያት የሲፒዩ ሀብቶች እያለቀባቸው ነው። በዓለም ዙሪያ ባለው የCloudflare አውታረመረብ ላይ በእያንዳንዱ ፕሮሰሰር ኮር አያያዝ HTTP/ኤችቲቲፒኤስ ትራፊክ ላይ። ለአዳዲስ ተጋላጭነቶች እና ስጋቶች ምላሽ ለመስጠት ለ WAF የሚተዳደሩ ደንቦችን በየጊዜው እያሻሻልን ነው። ለምሳሌ በግንቦት ወር ቸኩለናል። ደንብ ጨምርበ SharePoint ውስጥ ካለው ከባድ ተጋላጭነት ለመጠበቅ። የ WAFችን አጠቃላይ ይዘት ህጎችን በፍጥነት እና በአለምአቀፍ ደረጃ የማሰማራት ችሎታ ነው።

እንደ አለመታደል ሆኖ፣ ያለፈው ሐሙስ ዝማኔ ለኤችቲቲፒ/ኤችቲቲፒኤስ ከተመደበው ሲፒዩ ለኋላ ለመከታተል በጣም ብዙ የሚጠቀም regex ይዟል። የእኛ ዋና ተኪ፣ ሲዲኤን እና WAF ተግባራቶች በዚህ ተጎድተዋል። ግራፉ የሚያሳየው የኤችቲቲፒ/ኤችቲቲፒኤስ ትራፊክን ለማገልገል የሲፒዩ ሃብቶች በእኛ አውታረ መረብ ውስጥ ባሉ አገልጋዮች ላይ ወደ 100% ገደማ ይደርሳል።

በአደጋ ጊዜ ከሚገኙት ቦታዎች በአንዱ ላይ የአቀነባባሪ ሃብት አጠቃቀም

በውጤቱም፣ ደንበኞቻችን (እና የደንበኞቻችን ደንበኞቻችን) በCloudflare ጎራዎች ላይ የ502 የስህተት ገጽ መታ። 502 ስህተቶች የተፈጠሩት በCloudflare የፊት-መጨረሻ የድር አገልጋዮች፣ አሁንም ነፃ ኮሮች ነበሯቸው፣ ነገር ግን የኤችቲቲፒ/ኤችቲቲፒኤስ ትራፊክን ከሚቆጣጠሩ ሂደቶች ጋር መገናኘት አልቻሉም።

ይህ በደንበኞቻችን ላይ ምን ያህል ችግር እንደፈጠረ እናውቃለን። በጣም አፍረንብናል። እናም ይህ ውድቀት ክስተቱን በብቃት እንዳናስተናግድ አድርጎናል።

ከእነዚያ ደንበኞች አንዱ ከሆንክ ፈርተህ፣ ተቆጥተህ እና ተበሳጭተህ መሆን አለበት። ከዚህም በላይ ለ 6 ዓመታት አልነበረንም ዓለም አቀፍ ውድቀቶች. ከፍተኛው የሲፒዩ አጠቃቀም በአንድ WAF ህግ ምክንያት በቂ ያልሆነ የቃላት አገላለጽ ከመጠን በላይ ወደኋላ መመለስን አስከትሏል። የጥፋተኝነት መግለጫው እነሆ (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))

በራሱ የሚስብ ቢሆንም (እና ከዚህ በታች በዝርዝር እሸፍነዋለሁ)፣ የCloudflare የ27 ደቂቃ ጥቁር መቋረጥ በመጥፎ መደበኛ አገላለጽ ምክንያት ብቻ አልነበረም። ለአደጋው መንስኤ የሆኑትን ክስተቶች ቅደም ተከተል ለመግለጽ ትንሽ ጊዜ ወስዶብናል, ስለዚህ በፍጥነት ምላሽ አልሰጠንም. በጽሁፉ መጨረሻ ላይ፣ ወደ ኋላ መመለስን በመደበኛ አገላለጽ እገልጻለሁ እና ምን ማድረግ እንዳለቦት እነግርዎታለሁ።

ምን ሆነ

በቅደም ተከተል እንጀምር. እዚህ ያሉት ሁሉም ጊዜያት በUTC ውስጥ ናቸው።

በ13፡42 የፋየርዎል ቡድን መሐንዲስ የመለየት ደንቦቹ ላይ ትንሽ ለውጥ አድርጓል XSS በራስ-ሰር ሂደት. በዚህ መሠረት የለውጥ ጥያቄ ትኬት ተፈጥሯል። እንደዚህ ያሉ ቲኬቶችን በጂራ በኩል እናስተዳድራለን (ከታች ያለው ቅጽበታዊ ገጽ እይታ)።

ከ3 ደቂቃ በኋላ የፔጀርዱቲ የመጀመሪያ ገጽ ታየ፣ በWAF ላይ ችግር እንዳለ ሪፖርት አድርጓል። ይህ ከCloudflare ውጭ የWAFsን ተግባር የሚፈትሽ ሰው ሰራሽ ቤንችማርክ ነበር። ይህንን ተከትሎም ሌሎች ከጫፍ እስከ ጫፍ ያሉ የ Cloudflare አገልግሎቶች ፈተናዎች ውድቀቶች ገፆች፣ የአለምአቀፍ የትራፊክ ጉዳዮች፣ 502 የተስፋፉ ስህተቶች እና በአለም ዙሪያ ባሉ ከተሞች ከሚገኙት የእኛ የመገኘት ነጥቦች (PoP) ሪፖርቶች እጥረት መኖሩን ያመለክታሉ። የማቀነባበሪያ ሀብቶች.

ከእነዚህ ማንቂያዎች ውስጥ ጥቂቶቹ ደርሰውኛል፣ ከስብሰባ ወጥቼ፣ እና ወደ ጠረጴዛው እየሄድኩ ሳለ የመፍትሄ ሃሳቦች ልማት መሪያችን 80% የሚሆነውን የትራፊክ መጨናነቅ አጥተናል። ቀድሞውንም በችግሩ ላይ እየሰሩ ወደነበሩ የSRE መሐንዲሶቻችን ሮጥኩ። መጀመሪያ ላይ ያልታወቀ ጥቃት መስሎን ነበር።

የCloudflare SRE መሐንዲሶች በዓለም ዙሪያ ተበታትነው እና ሁኔታውን በሰዓቱ ይከታተላሉ. በተለምዶ እነዚህ ማንቂያዎች የተወሰነ ስፋት ያላቸውን የተወሰኑ የአካባቢ ችግሮችን ያሳውቃሉ፣ በውስጣዊ ዳሽቦርዶች ላይ ክትትል ይደረግባቸዋል እና በቀን ብዙ ጊዜ መፍትሄ ያገኛሉ። ነገር ግን እንደዚህ ያሉ ገጾች እና ማሳወቂያዎች ወደ አንድ ከባድ ነገር አመላክተዋል፣ እና የኤስአርኢ መሐንዲሶች ወዲያውኑ የP0 ከባድነት ደረጃን አውጀው ወደ አስተዳደር እና የስርዓት መሐንዲሶች ዞረዋል።

የለንደን መሐንዲሶቻችን በዚያን ጊዜ በዋናው አዳራሽ ውስጥ ንግግር ያዳምጡ ነበር። ንግግሩ መቋረጥ ነበረበት፣ ሁሉም በአንድ ትልቅ የስብሰባ አዳራሽ ውስጥ ተሰበሰቡ፣ እና ተጨማሪ ስፔሻሊስቶች ተጠሩ። ይህ SREዎች በራሳቸው ሊቋቋሙት የሚችሉት የተለመደ ችግር አልነበረም። ትክክለኛውን ስፔሻሊስቶች በአስቸኳይ ማገናኘት አስፈላጊ ነበር.

14፡00 ላይ በWAF ላይ ችግር እንዳለ እና ምንም አይነት ጥቃት እንደሌለ ወስነናል። የክዋኔ ክፍሉ የአቀነባባሪውን መረጃ አውጥቷል፣ እና ተጠያቂው WAF እንደሆነ ግልጽ ሆነ። ሌላ ሰራተኛ ይህንን ፅንሰ-ሀሳብ በስስት አረጋግጧል። ሌላ ሰው በWAF ላይ ችግር እንዳለ በምዝግብ ማስታወሻዎች ውስጥ አይቷል። ከምሽቱ 14፡02 ላይ፣ ዓለም አቀፋዊ ግድያ እንዲጠቀም በተጠቆመ ጊዜ መላው ቡድን ወደ እኔ መጡ፣ በ Cloudflare ውስጥ የተሰራውን ዘዴ በዓለም ዙሪያ አንድ አካልን ያሰናክላል።

ለ WAF ዓለም አቀፋዊ ግድያ እንዴት እንደሠራን የተለየ ታሪክ ነው። ይህን ያህል ቀላል አይደለም. እኛ የራሳችንን ምርቶች እንጠቀማለን, እና ከአገልግሎታችን ጀምሮ መዳረሻ አልሰራም ፣ ማረጋገጥ እና ወደ የውስጥ መቆጣጠሪያ ፓነል መግባት አልቻልንም (ሁሉም ነገር ሲስተካከል ፣ የውስጥ መቆጣጠሪያ ፓነል ለረጅም ጊዜ ጥቅም ላይ ካልዋለ አንዳንድ የቡድን አባላት በደህንነት ባህሪ ምክንያት መዳረሻ እንዳጡ ተምረናል) .

እና እንደ ጂራ ወይም የግንባታ ስርዓቱ ያሉ የውስጥ አገልግሎቶቻችን ማግኘት አልቻልንም። ብዙ ጊዜ የምንጠቀምበት መፍትሄ አስፈለገ (ይህም መሰራት አለበት)። በመጨረሻም አንድ መሐንዲስ ከሰዓት በኋላ 14፡07 ላይ WAF ማቋረጥ ችሏል፣ እና ከሰዓት በኋላ 14፡09 ላይ፣ የትራፊክ እና ፕሮሰሰር ደረጃ በየቦታው ወደ መደበኛው ተመልሷል። የተቀሩት የCloudflare የደህንነት ስልቶች እንደተለመደው ሰርተዋል።

ከዚያም WAF ን ወደነበረበት መመለስ ጀመርን. ሁኔታው ከተለመደው ውጭ ስለነበር አሉታዊ ፈተናዎችን (ይህ ለውጥ በእርግጥ ችግሩ እንደሆነ ራሳችንን እየጠየቅን) እና አዎንታዊ ሙከራዎችን (የመልሶ መመለሻው መስራቱን በማረጋገጥ) በአንድ ከተማ ውስጥ የተለየ ትራፊክ በማካሄድ ተከፋይ ደንበኞችን ከዚያ እያስተላለፍን ሄድን።

በ14፡52 ምክንያቱን መረዳታችንን እና እርማት እንዳደረግን እና WAFን መልሰን አብራ።

Cloudflare እንዴት እንደሚሰራ

Cloudflare ለ WAF ለሚተዳደሩ ህጎች የተሰጡ መሐንዲሶች ቡድን አለው። የመለየት መጠኖችን ለማሻሻል፣ የተሳሳቱ አወንታዊ ውጤቶችን ለመቀነስ እና ለአዳዲስ ማስፈራሪያዎች በፍጥነት ምላሽ ለመስጠት ይጥራሉ። ባለፉት 60 ቀናት ውስጥ፣ 476 WAF የሚተዳደር የደንብ ለውጥ ጥያቄዎች ተካሂደዋል (በአማካይ በየ3 ሰዓቱ አንድ)።

ይህ ልዩ ለውጥ እውነተኛ የደንበኛ ትራፊክ በደንቡ ውስጥ በሚያልፍበት የማስመሰል ሁነታ ላይ መሰማራት ነበረበት፣ ነገር ግን ምንም ነገር አልተከለከለም። ይህንን ዘዴ የምንጠቀመው የሕጎችን ውጤታማነት ለመፈተሽ እና የውሸት አዎንታዊ እና የውሸት አሉታዊዎችን መጠን ለመለካት ነው። ነገር ግን በማስመሰል ሁነታ ውስጥ እንኳን, ደንቦቹ በትክክል መፈፀም አለባቸው, እና በዚህ ሁኔታ, ደንቡ በጣም ብዙ የአቀነባባሪ ሀብቶችን የሚበላ መደበኛ አገላለጽ ይዟል.

ከላይ ካለው የለውጥ ጥያቄ ማየት እንደምትችለው፣ ለዚህ ​​አይነት ማሰማራት የማሰማራት እቅድ፣ የመመለሻ እቅድ እና ወደ ውስጣዊ መደበኛ የስራ ሂደት (SOP) አገናኝ አለን። ህግን ለማሻሻል SOP በአለም አቀፍ ደረጃ እንዲታተም ይፈቅዳል. በእርግጥ በ Cloudflare ውስጥ ሁሉም ነገር በተለየ መንገድ የተደራጀ ሲሆን SOP በመጀመሪያ ሶፍትዌሩን ለሙከራ እና ለውስጣዊ አጠቃቀም ወደ ውስጣዊ ቦታ (ፖፒ) (ሰራተኞቻችን የሚጠቀሙበት) እንዲያቀርቡ መመሪያ ይሰጣል, ከዚያም በ ውስጥ አነስተኛ ቁጥር ላላቸው ደንበኞች. ገለልተኛ ቦታ ፣ ከዚያ ለብዙ ደንበኞች ፣ እና ከዚያ በዓለም ዙሪያ ብቻ።

ምን እንደሚመስል እነሆ። በ BitBucket በኩል gitን ከውስጥ እንጠቀማለን። በለውጦች ላይ የሚሰሩ መሐንዲሶች ለ TeamCity የተሰራውን ኮድ ያስገባሉ፣ እና ግንባታው ሲያልፍ ገምጋሚዎች ይመደባሉ። የመሳብ ጥያቄ ሲጸድቅ ኮዱ ተሰብስቦ ተከታታይ ሙከራዎች (እንደገና) ይካሄዳሉ።

ግንባታው እና ሙከራው በተሳካ ሁኔታ ከተጠናቀቀ፣ በጅራ ውስጥ የለውጥ ጥያቄ ተፈጥሯል እና ለውጡ አግባብ ባለው ስራ አስኪያጅ ወይም መሪ መጽደቅ አለበት። ከፀደቀ በኋላ፣ ወደ "PoP menagerie" ወደሚባለው ያሰማራል፡ DOG፣ PIG፣ እና ካናሪ (ውሻ, አሳማ እና ካናሪ).

ዶግ ፖፕ የCloudflare ሰራተኞች ብቻ የሚጠቀሙበት Cloudflare PoP ነው (ልክ እንደሌሎች የእኛ ከተሞች)። ለውስጣዊ አጠቃቀም ፖፕ የደንበኞች ትራፊክ ወደ መፍትሄው ለመግባት ከመጀመሩ በፊት ችግሮችን እንዲይዙ ያስችልዎታል. ጠቃሚ ነገር.

የ DOG ፈተና ካለፈ, ኮዱ ወደ ፒጂ (ጊኒ አሳማ) ደረጃ ይንቀሳቀሳል. ይህ Cloudflare PoP ነው፣ አነስተኛ መጠን ያለው የነጻ ደንበኛ ትራፊክ በአዲሱ ኮድ ውስጥ ያልፋል።
ሁሉም ነገር ደህና ከሆነ, ኮዱ ወደ ካናሪ ይሄዳል. በተለያዩ የአለም ክፍሎች ሶስት የካናሪ ፖፒዎች አሉን። በእነሱ ውስጥ, የሚከፈልባቸው እና የነጻ ደንበኞች ትራፊክ በአዲሱ ኮድ ውስጥ ያልፋል, እና ይህ ለስህተቶች የመጨረሻው ፍተሻ ነው.

በCloudflare ውስጥ የሶፍትዌር የመልቀቅ ሂደት

ኮዱ በካናሪ ውስጥ ደህና ከሆነ እንለቃዋለን። በሁሉም ደረጃዎች ማለፍ - ዶግ ፣ ፒግ ፣ ካናሪ ፣ መላው ዓለም - እንደ ኮድ ለውጥ ላይ በመመስረት ብዙ ሰዓታት ወይም ቀናት ይወስዳል። በ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 ደንቦችን በበርካታ የኤችቲቲፒ ጥያቄዎች ሞከርን። የኤችቲቲፒ ጥያቄዎች የትኞቹ ጥያቄዎች በWAF መታገድ እንዳለባቸው (ጥቃቱን ለመጥለፍ) እና የትኞቹ ጥያቄዎች እንዲተላለፉ መፈቀድ እንዳለበት (ሁሉንም ነገር በተከታታይ ላለማገድ እና የውሸት አወንታዊ ውጤቶችን ለማስወገድ) ያረጋግጡ። ነገር ግን ከልክ ያለፈ የሲፒዩ አጠቃቀም ሙከራዎችን አላደረግንም፣ እና ከቀደምት የ WAF ግንባታዎች ምዝግብ ማስታወሻዎችን መመልከት እንደሚያሳየው ፈተናዎቹን ከደንቡ ጋር ለማስኬድ ጊዜው እንዳልጨመረ እና በቂ ሀብቶች ሊኖሩ እንደማይችሉ መጠራጠር ከባድ ነው። .

ፈተናዎቹ አልፈዋል እና TeamCity ለውጡን በ13፡42 ላይ በራስ ሰር ማሰማራት ጀመረ።

Quicksilver

የWAF ህጎች የተነደፉት አደጋዎችን በፍጥነት ለመፍታት ነው፡ ለዚህም ነው በአለምአቀፍ ደረጃ በሰከንዶች ውስጥ ለውጦችን የሚያሰራጭውን የ Quicksilver የተከፋፈለ የቁልፍ እሴት ማከማቻን በመጠቀም የምናሰማራቸው። ሁሉም ደንበኞቻችን ይህንን ቴክኖሎጂ የሚጠቀሙት በዳሽቦርዱ ላይ ወይም በኤፒአይ በኩል አወቃቀሩን ሲቀይሩ ነው፣ እና ለለውጦቹ በመብረቅ ፍጥነት ምላሽ ስለምንሰጥ ለዚህ ምስጋና ነው።

ስለ Quicksilver ብዙ አልተነጋገርንም። ከዚህ በፊት እንጠቀማለን ኪዮቶ ታይኮን እንደ ዓለም አቀፍ የተከፋፈለ የቁልፍ እሴት መደብር፣ ነገር ግን የአሠራር ችግሮች አጋጥሞታል እና ከ180 በላይ በሆኑ ከተሞች ውስጥ የራሳችንን መደብር ጻፍን። አሁን የውቅረት ለውጦችን ወደ ደንበኞች ለመግፋት፣ የWAF ደንቦችን ለማዘመን እና በደንበኛ የተጻፈ ጃቫስክሪፕትን ለ Cloudflare Workers ለማሰራጨት Quicksilverን እንጠቀማለን።

በዳሽቦርድ ላይ ያለውን አዝራር ጠቅ ከማድረግ ወይም ኤፒአይን ከመጥራት ጀምሮ በአለም ዙሪያ የውቅር ለውጥ ለማድረግ ጥቂት ሰከንዶች ብቻ ነው የሚወስደው። ደንበኞች ይህን የማዋቀር ፍጥነት ይወዳሉ። እና ሰራተኞች በቅጽበት የሚቀርብ አለምአቀፍ የሶፍትዌር ማሰማራትን ይሰጣቸዋል። በአማካይ፣ Quicksilver በሰከንድ 350 ያህል ለውጦችን ያሰራጫል።

እና Quicksilver በጣም ፈጣን ነው። በአማካይ በአለም ዙሪያ በሁሉም ኮምፒውተሮች ላይ ለውጦችን ለማሰራጨት ከ99 ሰከንድ 2,29ኛ ፐርሰንታይል ላይ ደርሰናል። ብዙውን ጊዜ ፍጥነት ጥሩ ነው። ደግሞም አንድ ባህሪን ሲያበሩ ወይም መሸጎጫውን ሲያጸዱ ወዲያውኑ እና በሁሉም ቦታ ይከሰታል። ኮድ በ Cloudflare Workers መላክ በተመሳሳይ ፍጥነት ይከናወናል። Cloudflare ለደንበኞቹ ፈጣን ማሻሻያዎችን በትክክለኛው ጊዜ ቃል ገብቷል።

ነገር ግን በዚህ ሁኔታ, ፍጥነቱ በእኛ ላይ ጭካኔ የተሞላበት ዘዴ ተጫውቷል, እና ደንቦቹ በጥቂት ሰከንዶች ውስጥ በሁሉም ቦታ ተለውጠዋል. የ WAF ኮድ Lua እንደሚጠቀም አስተውለህ ይሆናል። Cloudflare በምርት እና በዝርዝሮች ላይ ሉአንን በሰፊው ይጠቀማል ሉዋ ወደ WAF እኛ ነን አስቀድሞ ተወያይቷል።. Lua WAF ይጠቀማል PCRE ውስጥ እና ለማዛመድ ወደ ኋላ ትራኪንግ ይተገበራል። ከቁጥጥር ውጪ የሆኑ አባባሎችን ለመከላከል ምንም ዘዴዎች የሉትም. ስለዚህ ጉዳይ እና ስለእሱ ምን እያደረግን እንደሆነ ከዚህ በታች በዝርዝር እገልጻለሁ።

ህጎቹ ከመሰማራታቸው በፊት ሁሉም ነገር ያለ ችግር ነበር፡ የመሳብ ጥያቄ ተፈጥሯል እና ጸድቋል፣ የ CI/CD ቧንቧ መስመር ተገንብቶ ኮዱን ፈትኖ፣ ማሰማራት እና መመለስን በሚቆጣጠረው SOP መሰረት የለውጥ ጥያቄ ቀርቦ ስራው ተጠናቀቀ። .

Cloudflare WAF የማሰማራት ሂደት

የሆነ ስህተት ተከስቷል
አስቀድሜ እንዳልኩት በየሳምንቱ በደርዘኖች የሚቆጠሩ አዲስ የ WAF ህጎችን እናወጣለን፣ እና እንደዚህ አይነት ልቀት ከሚያስከትላቸው አሉታዊ ተፅእኖዎች ለመጠበቅ ብዙ ስርዓቶች አሉን። እና አንድ ነገር ሲሳሳት ብዙውን ጊዜ በአንድ ጊዜ የበርካታ ሁኔታዎች ጥምረት ነው። አንድ ምክንያት ብቻ ካገኘህ, ይህ, በእርግጥ, አረጋጋጭ ነው, ግን ሁልጊዜ እውነት አይደለም. የኤችቲቲፒ/ኤችቲቲፒኤስ አገልግሎታችን እንዲከሽፍ ያደረጉ ምክንያቶች እነዚህ ናቸው።

1. አንድ መሐንዲስ ወደ ከመጠን በላይ ሊያመራ የሚችል መደበኛ አገላለጽ ጽፏል ወደኋላ መመለስ.
2. መደበኛውን አገላለጽ ሲፒዩ ከመጠን በላይ እንዳይጠቀም የሚከለክለው ባህሪ ከጥቂት ሳምንታት በፊት በ WAF refactoring ወቅት በስህተት ተወግዷል - WAF አነስተኛ ሀብቶችን እንዲፈጅ ለማድረግ እንደገና መፈጠር ያስፈልግ ነበር።
3. የመደበኛ መግለጫ ሞተር ውስብስብነት ምንም ዋስትና አልነበረውም.
4. የሙከራ ስብስብ ከልክ ያለፈ የሲፒዩ አጠቃቀምን መለየት አልቻለም።
5. SOP አስቸኳይ ያልሆኑ የህግ ለውጦች ያለ ባለብዙ ደረጃ ሂደት በአለም አቀፍ ደረጃ እንዲሰማሩ ይፈቅዳል።
6. የመመለሻ ዕቅዱ ሙሉ የWAF ግንባታ ሁለት ጊዜ ያስፈልገዋል፣ ይህም ረጅም ጊዜ ነው።
7. የመጀመሪያው ዓለም አቀፍ የትራፊክ ችግር ማስጠንቀቂያ በጣም ዘግይቷል.
8. የሁኔታ ገጹን ለማዘመን ቀርፈናል።
9. በመጥፋቱ ምክንያት ስርዓቱን የማግኘት ችግር አጋጥሞናል እና የማለፊያው አሰራር በደንብ አልተሰራም.
10. SREዎች የአንዳንድ ስርዓቶች መዳረሻ አጥተዋል ምክንያቱም ምስክርነታቸው ለደህንነት ሲባል ጊዜው አልፎበታል።
11. ደንበኞቻችን በCloudflare ክልል ውስጥ ስለሚያልፉ የCloudflare Dashboard ወይም API መዳረሻ አልነበራቸውም።

ካለፈው ሀሙስ ጀምሮ ምን ተለውጧል

በመጀመሪያ፣ ለWAF የሚለቀቁትን ሁሉንም ስራዎች ሙሉ በሙሉ አቁመናል እና የሚከተሉትን አድርገናል፡

1. እኛ አስወግደነዋል ከመጠን ያለፈ የአቀነባባሪ ሃብቶች አጠቃቀም ጥበቃን እንደገና በማስተዋወቅ ላይ። (ዝግጁ)
2. በWAF የሚተዳደር ደንቦች ውስጥ ያሉትን ሁሉንም 3868 ደንቦች በእጅ በመፈተሽ ሌሎች ከመጠን ያለፈ ወደኋላ የመመለስ አጋጣሚዎችን ለማግኘት እና ለማስተካከል። (ማረጋገጫ ተጠናቅቋል)
3. በሙከራ ክፍል ውስጥ ለሁሉም ደንቦች የአፈጻጸም መገለጫን ያካትቱ። (የሚጠበቀው፡ ጁላይ 19)
4. ወደ መደበኛው ገላጭ ሞተር መቀየር re2 ወይም ዝገት ሁለቱም በሂደት አካባቢ ውስጥ ዋስትና ይሰጣሉ. (የሚጠበቀው፡ ጁላይ 31)
5. እንደ Cloudflare ውስጥ ያሉ ሌሎች ሶፍትዌሮችን በደረጃ ለማሰማራት SOP ን እንደገና መፃፍ፣ ነገር ግን ጥቃቶች አስቀድመው ከጀመሩ አሁንም ድንገተኛ አደጋን በአለም አቀፍ ደረጃ ማሰማራት ይችላሉ።
6. የCloudflare ዳሽቦርድን እና ኤፒአይን ከCloudflare ክልል በአስቸኳይ የማስወጣት ችሎታን እያዳበርን ነው።
7. ገጽን በራስ ሰር አድስ የደመና ነበልባል ሁኔታ.

በረጅም ጊዜ ውስጥ፣ ከጥቂት አመታት በፊት ከፃፍኩት ሉአ WAF እየራቅን ነው። WAF ወደ በማንቀሳቀስ ላይ አዲስ የፋየርዎል ስርዓት. ስለዚህ WAF ፈጣን ይሆናል እና ተጨማሪ የጥበቃ ንብርብር ያገኛል።

መደምደሚያ

ይህ ውድቀት በእኛ እና በደንበኞቻችን ላይ ችግር ፈጥሮብናል። ሁኔታውን ለማስተካከል አፋጣኝ ምላሽ የሰጠን ሲሆን በአሁኑ ወቅት ለአደጋው መንስኤ የሆኑ ሂደቶች ላይ ያሉ ጉድለቶችን እየሰራን እንገኛለን እንዲሁም ወደ አዲሱ ቴክኖሎጂ በመሸጋገር ወደፊት ሊፈጠሩ ከሚችሉ የሬጌክስ ጉዳዮች ለመጠበቅ የበለጠ ጥልቀት በመቆፈር ላይ እንገኛለን።

በዚህ ውድቀት በጣም አፍረን ደንበኞቻችንን ይቅርታ እንጠይቃለን። ተስፋ እናደርጋለን፣ እነዚህ ለውጦች ይህ ዳግም እንዳይከሰት ያረጋግጣሉ።

መተግበሪያ. መደበኛ አገላለጽ ወደ ኋላ መመለስ

አገላለጹ እንዴት እንደሆነ ለመረዳት፡-

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

ሁሉንም የሲፒዩ ሀብቶች በልተዋል ፣ ስለ መደበኛው መደበኛ መግለጫ ሞተር እንዴት እንደሚሰራ ትንሽ ማወቅ ያስፈልግዎታል። እዚህ ያለው ችግር በስርዓተ-ጥለት ውስጥ ነው .*(?:.*=.*). (?: እና ተዛማጅ ) የማይያዝ ቡድን ነው (ይህም በቅንፍ የተደረገው አገላለጽ እንደ ነጠላ አገላለጽ ይመደባል)።

የአቀነባባሪ ሀብቶች ከመጠን በላይ ፍጆታ አውድ ውስጥ ይህ ንድፍ እንደ ሊሰየም ይችላል። .*.*=.*. በዚህ ቅፅ, ንድፉ አላስፈላጊ ውስብስብ ይመስላል. በይበልጥ ግን፣ በገሃዱ ዓለም፣ ኤንጂኑ ከሌላ ክፍልፋዮች ጋር እንዲመሳሰል የሚጠይቁ አገላለጾች (እንደ ውስብስብ አገላለጾች በ 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. ፔርልን ስለመጠቀም አጭር ቪዲዮ ይመልከቱ 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 ጀምሮ ኬንት ቶምፕሰን አንድ ጽሑፍ ሲጽፍ ይታወቃል የፕሮግራም አወጣጥ ቴክኒኮች፡ መደበኛ የቃላት መፈለጊያ ስልተ ቀመር ("የፕሮግራም አወጣጥ ዘዴዎች፡ መደበኛ የአገላለጽ ፍለጋ አልጎሪዝም")። ጽሑፉ መደበኛውን አገላለጽ ወደ የማይወሰን ውሱን አውቶሜት እንዲቀይሩ የሚያስችልዎትን ዘዴ ይገልፃል፣ እና የስቴት ለውጦች በማይወስኑት ፊኒት automata ላይ ከተደረጉ በኋላ የማስፈጸሚያ ጊዜ በተዛመደው ሕብረቁምፊ ላይ በቀጥታ የሚወሰን አልጎሪዝምን ይጠቀሙ።

የፕሮግራም አወጣጥ ዘዴዎች
መደበኛ የቃላት ፍለጋ ስልተ ቀመር
ኬን ቶምፕሰን
የደወል ስልክ ላቦራቶሪዎች፣ Inc.፣ Murray Hill፣ NJ

ይህ በጽሁፍ ውስጥ የተወሰነ የቁምፊዎች ሕብረቁምፊን የመፈለግ ዘዴን ይገልፃል, እና የዚህን ዘዴ አተገባበር በአቀናባሪ መልክ ያብራራል. አቀናባሪው መደበኛውን አገላለጽ እንደ ምንጭ ኮድ ወስዶ IBM 7094 ፕሮግራምን እንደ ዕቃ ኮድ ያመነጫል። የነገር ፕሮግራሙ ግብአትን በፍለጋ ጽሁፍ መልክ ይይዛል እና የጽሑፍ ሕብረቁምፊ ከተሰጠው መደበኛ አገላለጽ ጋር በተዛመደ ቁጥር ምልክት ያወጣል። ጽሑፉ ምሳሌዎችን, ችግሮችን እና መፍትሄዎችን ያቀርባል.

አልጎሪዝም
በከፊል የተሳካ ፍለጋ ካልተሳካ የቀድሞ የፍለጋ ስልተ ቀመሮች ወደ ኋላ መመለስ አስከትለዋል።

በማጠናቀር ሁነታ, አልጎሪዝም ከምልክቶች ጋር አይሰራም. መመሪያዎችን ወደ ተዘጋጀው ኮድ ያስተላልፋል። አፈፃፀሙ በጣም ፈጣን ነው - ውሂቡን አሁን ባለው ዝርዝር አናት ላይ ካስተላለፈ በኋላ በመደበኛ አገላለጽ ውስጥ ሁሉንም ሊሆኑ የሚችሉ ተከታታይ ቁምፊዎችን በራስ-ሰር ይፈልጋል።
የማጠናቀር እና የፍለጋ አልጎሪዝም በጊዜ መጋራት የጽሑፍ አርታኢ ውስጥ እንደ አውድ ፍለጋ ተካትቷል። በእርግጥ ይህ ከእንደዚህ አይነት የፍለጋ አሰራር ብቸኛው አተገባበር በጣም የራቀ ነው. ለምሳሌ፣ የዚህ አልጎሪዝም ልዩነት በአሰባሳቢ ውስጥ በሰንጠረዥ ውስጥ እንደ ምልክት ፍለጋ ጥቅም ላይ ይውላል።
አንባቢው መደበኛ አገላለጾችን እና የ IBM 7094 ኮምፒዩተር የፕሮግራም አወጣጥ ቋንቋ ጠንቅቆ ያውቃል ተብሎ ይታሰባል።

አቀናባሪ
ማጠናከሪያው ሶስት ትይዩ ደረጃዎችን ያካትታል. የመጀመሪያው እርምጃ የአገባብ ማጣሪያ ነው፣ ይህም በአገባብ የተስተካከሉ መደበኛ አባባሎችን ብቻ ይፈቅዳል። ይህ እርምጃ ከመደበኛ አገላለጾች ጋር ​​ለማዛመድ የ"·" ኦፕሬተርንም ያስገባል። በሁለተኛው እርከን, የተለመደው አገላለጽ ወደ ፖስትፊክስ ቅፅ ይቀየራል. በሶስተኛ ደረጃ, የነገር ኮድ ተፈጠረ. የመጀመሪያዎቹ 2 ደረጃዎች ግልጽ ናቸው, እና በእነሱ ላይ አንቀመጥም.

የቶምፕሰን መጣጥፍ ስለ nondeterministic finite automata አይናገርም ነገር ግን መስመራዊ የጊዜ ስልተ ቀመርን በማብራራት እና ለ IBM 60 የመሰብሰቢያ ቋንቋ ኮድ የሚያመነጨውን ALGOL-7094 ፕሮግራም በማቅረብ ጥሩ ስራ ይሰራል። ቀላል

የአሁኑ የፍለጋ መንገድ. በአንድ ግብአት እና በሁለት ውጤቶች በ⊕ ይወከላል።
ምስል 1 የመደበኛውን አገላለጽ ምሳሌ ሲቀይሩ የሦስተኛውን የማጠናቀር ደረጃ ተግባራት ያሳያል. በምሳሌው ውስጥ ያሉት የመጀመሪያዎቹ ሦስት ቁምፊዎች a, b, c ናቸው, እና እያንዳንዳቸው የ S[i] ቁልል ግቤት እና የ NNODE መስክ ይፈጥራሉ.

NNODE ወደ ነባር ኮድ በአንድ ቁልል ውስጥ የመጨረሻውን መደበኛ አገላለጽ ለማመንጨት (ስእል 5 ይመልከቱ)

መደበኛው አገላለጽ ይህን ይመስላል .*.*=.*ከቶምፕሰን መጣጥፍ ላይ በሥዕሎች ላይ እንደሚታየው እርስዎ ካሰቡት።

በለስ ላይ. 0 ከክልሎች 0፣ 3 እና 1 የሚጀምሩ አምስት ክልሎች ከ2 እና 3 ዙሮች አሉ። እነዚህ ሶስት ዑደቶች ከሶስቱ ጋር ይዛመዳሉ። .* በመደበኛ አገላለጽ. ነጥብ ያላቸው 3 ovals ከአንድ ቁምፊ ጋር ይዛመዳሉ። ኦቫል ከምልክት ጋር = ከትክክለኛ ባህሪ ጋር ይዛመዳል =. ግዛት 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) ይሂዱ። ይህ በ fig. 3.

ከዚያም አልጎሪዝም ወደ መጨረሻው ይሸጋገራል x в x=x. ከክልሎች 1 እና 2 ተመሳሳይ ሽግግሮች ወደ ክፍለ ሀገር 1 እና 2 መመለስ ይቻላል. ከግዛት 3 x በቀኝ በኩል ካለው ነጥብ ጋር ማዛመድ እና ወደ ሁኔታ 3 መመለስ ይችላል።

በዚህ ደረጃ, እያንዳንዱ ቁምፊ x=x ግምት ውስጥ በማስገባት፣ እና ግዛት 4 ላይ ስለደረስን፣ መደበኛው አገላለጽ ከዚህ ሕብረቁምፊ ጋር ይዛመዳል። እያንዳንዱ ቁምፊ አንድ ጊዜ ነው የሚሰራው፣ ስለዚህ ይህ ስልተ ቀመር በመግቢያው ሕብረቁምፊ ርዝመት ላይ በቀጥታ ይወሰናል። እና ምንም ወደኋላ መመለስ የለም።

በግልጽ እንደሚታየው, ሁኔታ 4 ከደረሰ በኋላ (አልጎሪዝም ሲዛመድ x=) ጠቅላላው መደበኛ አገላለጽ ይዛመዳል, እና ስልተ ቀመር ምንም ሳያስብ ሊቋረጥ ይችላል x.

ይህ አልጎሪዝም በመግቢያው ሕብረቁምፊ መጠን ላይ በቀጥታ ይወሰናል.

ምንጭ: hab.com