Kusan shekaru 9 da suka gabata Cloudflare ƙaramin kamfani ne, kuma ban yi aiki da shi ba, abokin ciniki ne kawai. Wata daya bayan ƙaddamar da Cloudflare, na sami sanarwa cewa gidan yanar gizona DNS da alama baya aiki. Cloudflare ya yi canji zuwa , kuma an sami karyewar DNS.
Nan da nan na rubuta wa Matthew Prince tare da taken "Ina DNS na?" kuma ya mayar da martani mai tsawo cike da cikakkun bayanai na fasaha (), na amsa masa da cewa:
Daga: John Graham-Cumming
Rana: Oktoba 7, 2010, 9:14
Maudu'i: Sake: Ina DNS na?
Zuwa: Matthew PrinceSannun rahoto, na gode. Tabbas zan kira idan akwai matsaloli. Wataƙila yana da daraja rubuta rubutu game da wannan da zarar kun tattara duk bayanan fasaha. Ina tsammanin mutane za su ji daɗin buɗaɗɗen labari da gaskiya. Musamman idan kun haɗa hotuna zuwa gare shi don nuna yadda zirga-zirga ta haɓaka tun lokacin ƙaddamarwa.
Ina da kyakkyawan saka idanu akan rukunin yanar gizona, kuma ina karɓar SMS game da kowace gazawar. Sa ido ya nuna cewa gazawar ta faru ne daga 13:03:07 zuwa 14:04:12. Ana yin gwaje-gwaje kowane minti biyar.
Na tabbata za ku gane shi. Shin kun tabbata ba kwa buƙatar mutumin ku a Turai? 🙂
Sai ya amsa da cewa:
Daga: Matthew Prince
Rana: Oktoba 7, 2010, 9:57
Maudu'i: Sake: Ina DNS na?
Zuwa: John Graham-CummingNa gode. Mun amsa ga duk wanda ya rubuta. Ina kan hanyara ta zuwa ofis yanzu kuma za mu rubuta wani abu a kan bulogi ko kuma mu saka wani rubutu na hukuma a kan allo na mu. Na yarda kwata-kwata, gaskiya ita ce komai.
Yanzu Cloudflare babban kamfani ne na gaske, ina yi masa aiki, kuma yanzu dole in yi rubutu a sarari game da kuskurenmu, sakamakonsa da ayyukanmu.
Abubuwan da suka faru na Yuli 2
A ranar 2 ga Yuli mun fitar da sabuwar doka a cikin Dokokin Gudanarwa don WAFs saboda wanda akan kowane zirga-zirgar HTTP/HTTPS mai sarrafawa akan hanyar sadarwar Cloudflare a duk duniya. Muna ci gaba da inganta ƙa'idodin sarrafawa don WAFs don mayar da martani ga sabbin lahani da barazana. A watan Mayu, alal misali, mun yi sauri don karewa daga mummunan rauni a cikin SharePoint. Gabaɗayan batu na WAF ɗin mu shine ikon aiwatar da dokoki cikin sauri da kuma duniya baki ɗaya.
Abin takaici, sabuntawar ranar Alhamis ɗin da ta gabata ta ƙunshi magana ta yau da kullun wacce ta ɓata yawancin albarkatun HTTP/HTTPS akan ja da baya. Babban wakilin mu, CDN, da WAF sun sha wahala a sakamakon haka. Jadawalin ya nuna cewa albarkatun sarrafawa don hidimar zirga-zirgar HTTP/HTTPS sun kai kusan 100% akan sabar a cikin hanyar sadarwar mu.
Amfani da CPU a wuri ɗaya na kasancewar yayin wani lamari
Sakamakon haka, abokan cinikinmu (da abokan cinikinmu) sun ƙare tare da shafin kuskure 502 a cikin yankunan Cloudflare. Kurakurai 502 an haifar da sabar gidan yanar gizo na gaba-gaba na Cloudflare waɗanda har yanzu suna da muryoyi kyauta amma sun kasa sadarwa tare da hanyoyin sarrafa zirga-zirgar HTTP/HTTPS.
Mun san yawan rashin jin daɗi wannan ya haifar da abokan cinikinmu. Mun ji kunya sosai. Kuma wannan gazawar ta hana mu shawo kan lamarin yadda ya kamata.
Idan kana ɗaya daga cikin waɗannan kwastomomin, tabbas kun ji tsoro, fushi da bacin rai. Bugu da ƙari, ba mu da wani . Babban yawan amfani da CPU ya kasance saboda ƙa'idar WAF ɗaya tare da ƙarancin kalmomi na yau da kullun wanda ya haifar da koma baya da yawa. Ga maganar laifin: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Duk da yake wannan yana da ban sha'awa a cikin kansa (kuma zan yi magana game da shi daki-daki a ƙasa), sabis ɗin Cloudflare ya ragu na mintuna 27 ba kawai saboda mummunar magana ta yau da kullun ba. Ya ɗauki ɗan lokaci don bayyana jerin abubuwan da suka haifar da gazawar, don haka mun yi jinkirin amsawa. A ƙarshen post ɗin, zan bayyana koma baya a cikin magana ta yau da kullun kuma in gaya muku abin da za ku yi da shi.
Me ya faru
Bari mu fara cikin tsari. Duk lokutan nan suna cikin UTC.
Da karfe 13:42 na rana, wani injiniya a cikin tawagar ta wuta ya yi ɗan canji ga ƙa'idodin ganowa. ta amfani da tsari ta atomatik. Saboda haka, an ƙirƙiri tikitin neman canji. Muna sarrafa irin waɗannan tikiti ta Jira (hoton da ke ƙasa).
Bayan mintuna 3, shafin farko na PagerDuty ya bayyana, yana ba da rahoton matsala tare da WAF. Wannan gwaji ne na roba wanda ke gwada aikin WAFs (muna da ɗaruruwan su) a wajen Cloudflare don saka idanu akan aiki na yau da kullun. Nan da nan ya biyo bayan shafuffukan faɗakarwa game da gazawar gwajin sabis na ƙarshen-zuwa-ƙarshe na Cloudflare, matsalolin zirga-zirgar ababen hawa na duniya, kurakurai 502 da yaɗuwa, da tarin rahotanni daga wuraren Kasancewar mu (PoP) a cikin biranen duniya waɗanda ke nuna rashin ƙarfi. na albarkatun CPU.
Na sami da yawa daga cikin waɗannan faɗakarwa, na fita daga taro, kuma ina kan hanyata ta zuwa teburin lokacin da shugaban sashen samar da mafitarmu ya ce mun yi asarar kashi 80% na zirga-zirgar mu. Na gudu zuwa ga injiniyoyinmu na SRE, waɗanda suka riga sun yi aiki a kan matsalar. Da farko mun zaci wani irin hari ne da ba a san shi ba.
Injiniyoyin Cloudflare SRE sun warwatse a duniya kuma suna lura da halin da ake ciki a kowane lokaci. Yawanci, waɗannan faɗakarwar suna sanar da ku takamaiman al'amurran gida na ƙayyadaddun iyaka, ana bin su akan dashboards na ciki, kuma ana warware su sau da yawa kowace rana. Amma waɗannan shafuka da sanarwar sun nuna wani abu mai mahimmanci sosai, kuma injiniyoyin SRE nan da nan sun bayyana matakin P0 mai tsanani kuma sun tuntubi gudanarwa da injiniyoyin tsarin.
Injiniyoyin mu na Landan suna sauraron lacca a babban falo a lokacin. Sai da aka katse karatun, kowa ya hallara a wani katon dakin taro, aka kara kiran kwararru. Wannan ba matsala ce ta al'ada da SREs za su iya magance kansu ba. Ya kasance cikin gaggawa don haɗa ƙwararrun kwararru.
Karfe 14:00 muka tantance cewa matsalar WAF ce kuma babu wani hari. Ƙungiyar wasan kwaikwayon ta jawo bayanan CPU kuma ya bayyana a fili cewa WAF ce ke da laifi. Wani ma'aikaci ya tabbatar da wannan ka'idar ta amfani da strace. Wani kuma ya gani a cikin rajistan ayyukan cewa akwai matsala tare da WAF. Da karfe 14:02 na rana, dukan tawagar sun zo wurina lokacin da aka ba da shawarar yin amfani da kisa na duniya, tsarin da aka gina a cikin Cloudflare wanda ke rufe sassa ɗaya a duniya.
Yadda muka yi kisa na duniya don WAF wani labari ne daban. Ba haka ba ne mai sauki. Muna amfani da namu kayayyakin, kuma tun da sabis bai yi aiki ba, ba za mu iya tantancewa ba kuma mu shiga cikin kwamitin kula da ciki (lokacin da aka gyara komai, mun koyi cewa wasu membobin ƙungiyar sun rasa damar shiga saboda yanayin tsaro wanda ke hana takaddun shaida idan ba a yi amfani da kwamitin kula da ciki ba don kwana biyu).
Kuma ba za mu iya zuwa ayyukanmu na ciki ba, kamar Jira ko tsarin gini. Muna buƙatar tsarin aiki, wanda ba mu yi amfani da shi ba sau da yawa (wannan kuma zai buƙaci a yi aiki da shi). A ƙarshe, injiniya ɗaya ya yi nasarar kashe WAF a 14:07, kuma a 14:09, zirga-zirga da matakan CPU sun dawo daidai a ko'ina. Sauran hanyoyin kariya na Cloudflare sunyi aiki kamar yadda aka saba.
Sa'an nan kuma muka tashi game da maido da WAF. Halin ya kasance ba na yau da kullun ba, don haka mun gudanar da gwaje-gwaje mara kyau (tambayi kanmu ko canjin shine ainihin matsalar) da gwaje-gwaje masu inganci (tabbatar da cewa jujjuyawar ta yi aiki) a cikin birni ɗaya ta hanyar amfani da zirga-zirga daban-daban, canja wurin abokan ciniki masu biyan kuɗi daga can.
A 14:52 mun gamsu cewa mun fahimci dalilin kuma mun yi gyara, kuma mun sake kunna WAF.
Yadda Cloudflare ke aiki
Cloudflare yana da ƙungiyar injiniyoyi da aka sadaukar don sarrafa dokoki don WAFs. Suna ƙoƙari don haɓaka ƙimar ganowa, rage ƙimar ƙarya, da sauri amsa sabbin barazanar yayin da suke fitowa. A cikin kwanaki 60 da suka gabata, an sami buƙatun canji 476 da aka sarrafa don ka'idojin gudanarwa don WAF (matsakaicin ɗaya kowane awa 3).
Wannan canji na musamman yana buƙatar tura shi cikin yanayin kwaikwayo, inda ainihin zirga-zirgar abokin ciniki ke wucewa ta cikin ƙa'idar, amma babu abin da aka toshe. Muna amfani da wannan yanayin don gwada tasiri na ƙa'idodin kuma mu auna ƙimar ƙimar ƙarya da ƙima. Amma ko da a cikin yanayin kwaikwayo, dole ne a aiwatar da ƙa'idodin a zahiri, kuma a wannan yanayin dokar ta ƙunshi furci na yau da kullun wanda ke cinye albarkatun sarrafawa da yawa.
Kamar yadda kuke gani daga buƙatun canjin da ke sama, muna da shirin turawa, shirin juyawa, da hanyar haɗi zuwa daidaitaccen tsarin aiki na ciki (SOP) don wannan nau'in turawa. SOP don canza ƙa'ida yana ba da damar buga shi a duniya. A zahiri, a Cloudflare, ana yin abubuwa gaba ɗaya daban, kuma SOP ya ba da shawarar cewa mu fara jigilar software don gwaji da amfani da ciki zuwa wurin kasancewar ciki (PoP) (wanda ma'aikatanmu ke amfani da shi), sannan zuwa ƙaramin adadin abokan ciniki a ciki. keɓe wuri, sa'an nan zuwa ga babban adadin abokan ciniki, kuma kawai sai ga dukan duniya.
Wannan shi ne yadda abin yake. Muna amfani da git a ciki ta BitBucket. Injiniyoyin da ke aiki akan canje-canje suna ƙaddamar da lamba, wanda aka gina zuwa TeamCity, kuma lokacin da ginin ya wuce, ana sanya masu dubawa. Da zarar an amince da buƙatar ja, za a haɗa lambar kuma ana gudanar da jerin gwaje-gwaje (sake).
Idan ginin da gwaje-gwajen sun kammala cikin nasara, an ƙirƙiri buƙatun canji a Jira kuma dole ne mai gudanarwa ko jagorar da ya dace ya amince da canjin. Bayan amincewa, turawa yana faruwa cikin abin da ake kira "PoP menagerie": DOG, PIG da (kare, alade da canary).
DOG PoP shine Cloudflare PoP (kamar kowane ɗayan garuruwanmu) wanda ma'aikatan Cloudflare ke amfani dashi kawai. PoP don amfani na ciki yana ba ku damar kama matsaloli kafin zirga-zirgar abokin ciniki ya fara kwarara cikin mafita. Abu mai amfani.
Idan gwajin DOG ya yi nasara, lambar ta motsa zuwa matakin PIG (guinea pig). Wannan shine Cloudflare PoP, inda ƙaramin adadin zirga-zirgar abokin ciniki kyauta ke gudana ta sabon lamba.
Idan komai yayi kyau, lambar tana shiga Canary. Muna da Canary PoPs guda uku a sassa daban-daban na duniya. A cikinsu, zirga-zirgar abokan ciniki da aka biya da kyauta suna wucewa ta sabon lambar, kuma wannan shine binciken ƙarshe na kurakurai.
Tsarin Sakin software a Cloudflare
Idan lambar ta yi kyau a Canary, mun sake shi. Yin tafiya cikin dukkan matakai - DOG, PIG, Canary, duk duniya - yana ɗaukar sa'o'i da yawa ko kwanaki, dangane da canjin lambar. Saboda bambancin hanyar sadarwar Cloudflare da abokan ciniki, muna gwada lambar sosai kafin mu fitar da ita a duniya ga duk abokan ciniki. Amma WAF ba ta bin wannan tsari musamman saboda barazanar na bukatar a mayar da martani ga gaggawa.
barazanar WAF
A cikin 'yan shekarun da suka gabata, an sami karuwa mai yawa a cikin barazana a aikace-aikacen gama gari. Wannan ya faru ne saboda yawan samun kayan aikin gwajin software. Misali, kwanan nan mun rubuta game da ).
source:
Sau da yawa, ana ƙirƙira hujjar ra'ayi kuma nan da nan an buga shi akan Github don ƙungiyoyin da ke riƙe da aikace-aikacen su iya gwada shi cikin sauri da tabbatar da cewa an amintar da shi sosai. Saboda haka, Cloudflare yana buƙatar ikon amsa sabbin hare-hare da sauri don abokan ciniki su sami damar gyara software.
Babban misali na saurin amsawar Cloudflare shine jigilar kariyar rashin lahani na SharePoint a watan Mayu (). Kusan nan da nan bayan sanarwar da aka yi, mun lura da ɗimbin yunƙurin yin amfani da rauni a cikin kayan aikin SharePoint na abokan cinikinmu. Mutanenmu koyaushe suna sa ido kan sabbin barazanar da rubuta dokoki don kare abokan cinikinmu.
Dokar da ta haifar da matsalar a ranar Alhamis ya kamata ta kare kariya daga rubutun yanar gizo (XSS). Irin wadannan hare-hare ma sun yawaita a 'yan shekarun nan.
source:
Daidaitaccen tsari don canza ƙa'idar sarrafawa don WAF shine gudanar da gwajin haɗin kai (CI) mai ci gaba kafin tura duniya. A ranar Alhamis din da ta gabata mun yi haka kuma muka fitar da ka'idoji. Da ƙarfe 13:31 na rana, wani injiniya ya ƙaddamar da buƙatar ja da aka amince da shi tare da canji.
A 13:37 TeamCity ya tattara dokoki, yayi gwaje-gwaje kuma ya ba da ci gaba. Gidan gwajin WAF yana gwada ainihin aikin WAF kuma ya ƙunshi adadi mai yawa na gwaje-gwajen naúrar don ayyuka ɗaya. Bayan gwajin naúrar, mun gwada ƙa'idodin WAF ta amfani da ɗimbin buƙatun HTTP. Buƙatun HTTP duba waɗanne buƙatun yakamata WAF ta toshe su (don tsallaka harin) kuma waɗanda za'a iya ba da izini ta hanyar (don kar a toshe komai kuma a guje wa ƙimar ƙarya). Amma ba mu gwada amfani da CPU da ya wuce kima ba, kuma nazarin rajistan ayyukan ginin WAF na baya ya nuna cewa lokacin aiwatar da gwajin ƙa'idar bai ƙaru ba, kuma yana da wahala a yi zargin cewa ba za a sami isassun albarkatu ba.
Gwaje-gwajen sun wuce kuma TeamCity ta fara tura canjin ta atomatik a 13:42 na rana.
Quicksilver
Dokokin WAF sun mayar da hankali kan gyaran barazanar nan take, don haka muna tura su ta amfani da mabuɗin darajar maɓalli na Quicksilver, wanda ke yada canje-canje a duniya cikin daƙiƙa. Duk abokan cinikinmu suna amfani da wannan fasaha lokacin da suka canza saiti a cikin dashboard ko ta API, kuma godiya gareshi ne muke amsa canje-canje tare da saurin walƙiya.
Ba mu yi magana da yawa game da Quicksilver ba. A baya mun yi amfani da shi a matsayin kantin sayar da ƙima mai mahimmanci a duniya, amma akwai matsalolin aiki tare da shi, kuma mun rubuta kantin sayar da kanmu, wanda aka yi a cikin fiye da birane 180. Yanzu muna amfani da Quicksilver don tura canje-canje na sanyi ga abokan ciniki, sabunta dokokin WAF, da rarraba lambar JavaScript da abokan ciniki suka rubuta zuwa Ma'aikatan Cloudflare.
Yana ɗaukar ƴan daƙiƙa kaɗan kawai daga danna maɓalli akan dashboard ko kiran API don yin canjin tsari a duk duniya. Abokan ciniki suna son wannan saurin saitin. Kuma Ma'aikata suna ba su kusan tura software na duniya nan take. A matsakaita, Quicksilver yana yaɗa kusan canje-canje 350 a sakan daya.
Kuma Quicksilver yana da sauri sosai. A matsakaita, mun sami kashi 99 na kashi 2,29 don yada canje-canje ga kowace kwamfuta a duk duniya. Gudu yawanci abu ne mai kyau. Bayan haka, lokacin da kuka kunna aiki ko share cache, yana faruwa kusan nan take kuma ko'ina. Aika lambar ta Ma'aikatan Cloudflare yana faruwa a cikin gudu ɗaya. Cloudflare yayi alƙawarin sabunta abokan cinikinsa cikin sauri a daidai lokacin.
Amma a wannan yanayin, gudun ya yi mana mugun wasa, kuma ƙa'idodin sun canza ko'ina cikin daƙiƙa kaɗan. Wataƙila kun lura cewa lambar WAF tana amfani da Lua. Cloudflare yana amfani da Lua sosai wajen samarwa da cikakkun bayanai mu ne . Lua WAF yana amfani ciki kuma yana amfani da baya don daidaitawa. Ba ta da hanyoyin kariya daga maganganun da suka fita daga sarrafawa. A ƙasa zan yi magana game da wannan da abin da muke yi game da shi.
Kafin a ƙaddamar da ƙa'idodin, komai ya tafi daidai: an ƙirƙiri buƙatun cirewa kuma an amince da su, an tattara bututun CI / CD kuma an gwada lambar, an ƙaddamar da buƙatar canjin bisa ga SOP wanda ke kula da turawa da sake dawowa, kuma an kammala aikin.
Cloudflare WAF Tsarin Aikawa
Wani abu ya faru
Kamar yadda na fada, muna tura sabbin dokokin WAF da yawa a kowane mako, kuma muna da tsare-tsare da yawa don kare mugun sakamakon irin wannan turawa. Kuma idan wani abu ya yi kuskure, yawanci haɗuwa ne na yanayi da yawa lokaci guda. Idan ka sami dalili ɗaya kawai, wannan, ba shakka, yana ƙarfafawa, amma ba koyaushe gaskiya ba ne. Waɗannan su ne dalilan da suka haifar da gazawar sabis na HTTP/HTTPS.
- Wani injiniya ya rubuta magana akai-akai wanda zai iya haifar da wuce gona da iri .
- Wani fasalin da zai iya hana magana ta yau da kullun daga ɓata CPU da yawa an cire shi cikin kuskure a cikin sake fasalin WAF makonni da yawa da suka gabata - ana buƙatar sake fasalin don sa WAF ta cinye ƙasa da albarkatu.
- Injin magana na yau da kullun ba shi da garanti mai rikitarwa.
- Gidan gwajin ba zai iya gano yawan amfani da CPU ba.
- SOP yana ba da damar sauye-sauyen ƙa'idodin ƙa'idodin da ba na gaggawa ba don fitar da su a duniya ba tare da tsari mai matakai da yawa ba.
- Tsarin jujjuyawar yana buƙatar gudanar da cikakken ginin WAF sau biyu, wanda ya ɗauki lokaci mai tsawo.
- Fargawar farko game da matsalolin zirga-zirgar ababen hawa na duniya ya jawo a makara.
- Mun dauki lokaci don sabunta shafin matsayi.
- Mun sami matsalolin shiga tsarin saboda rashin daidaituwa, kuma hanyar wucewa ba ta da kyau.
- Injiniyoyin SRE sun rasa damar yin amfani da wasu tsare-tsare saboda takardun shaidarsu ya ƙare saboda dalilan tsaro.
- Abokan cinikinmu ba su sami damar yin amfani da dashboard ɗin Cloudflare ko API ba saboda sun ratsa yankin Cloudflare.
Me ya canza tun ranar Alhamis din da ta gabata
Na farko, mun dakatar da duk wani aiki akan sakewa don WAF kuma muna yin abubuwa masu zuwa:
- Muna sake gabatar da kariyar yawan amfani da CPU da muka cire. (Shirya)
- Da hannu duba duk dokokin 3868 a cikin dokokin da aka sarrafa don WAF don nemo da gyara wasu yuwuwar yiwuwar koma baya. (An gama tabbatarwa)
- Mun haɗa bayanin martaba ga duk ƙa'idodi a cikin saitin gwaji. (An yi tsammanin: Yuli 19)
- Juyawa zuwa injin magana na yau da kullun ko - Dukansu suna ba da garantin lokacin aiki. (An yi tsammanin: Yuli 31)
- Muna sake rubuta SOP don ƙaddamar da dokoki a matakai, kamar sauran software a cikin Cloudflare, amma a lokaci guda suna da ikon yin gaggawa a duniya idan an riga an fara kai hare-hare.
- Muna haɓaka ikon cire dashboard ɗin Cloudflare da API cikin gaggawa daga yankin Cloudflare.
- Sabuntawar shafi ta atomatik .
Na dogon lokaci muna ƙaura daga Lua WAF da na rubuta a ƴan shekaru da suka gabata. Motsa WAF zuwa . Ta wannan hanyar WAF za ta yi sauri kuma ta sami ƙarin matakin kariya.
ƙarshe
Wannan gazawar ta haifar da matsala ga mu da abokan cinikinmu. Mun yi aiki da sauri don gyara halin da ake ciki kuma yanzu muna aiki a kan kurakurai a cikin hanyoyin da suka haifar da hadarin, da kuma yin zurfafawa har ma da zurfi don karewa daga matsalolin da za su iya haifar da maganganu na yau da kullum a nan gaba lokacin ƙaura zuwa sabuwar fasaha.
Muna matukar jin kunyar wannan katsewar tare da neman afuwar abokan cinikinmu. Muna fatan waɗannan canje-canjen za su tabbatar da wani abu makamancin haka ba zai sake faruwa ba.
Aikace-aikace. Bayar da maganganu na yau da kullun
Don fahimtar yadda zance:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))cinye duk albarkatun CPU, kuna buƙatar sanin kaɗan game da yadda ingin magana ta yau da kullun ke aiki. Matsalar a nan ita ce tsarin .*(?:.*=.*). (?: kuma masu dacewa ) kungiya ce wadda ba ta kamawa ba (wato, ana hada furcin da ke cikin baka a matsayin magana daya).
A cikin mahallin yawan amfani da CPU, ana iya siffanta wannan ƙirar azaman .*.*=.*. A cikin wannan nau'i, ƙirar tana kallon hadaddun da ba dole ba. Amma mafi mahimmanci, a cikin duniyar gaske, maganganu (kamar maganganu masu rikitarwa a cikin dokokin WAF) waɗanda ke neman injin ya dace da guntu da wani guntu ya biyo baya zai iya haifar da koma baya. Kuma shi ya sa.
A cikin magana akai-akai . yana nufin kuna buƙatar daidaita hali ɗaya, .* - daidaita sifili ko fiye da haruffa "na zari", wato, ɗaukar iyakar haruffa, don haka .*.*=.* yana nufin daidaita sifili ko fiye da haruffa, sa'an nan daidaita sifili ko fiye da haruffa, nemo zahiri = hali, daidaita sifili ko fiye da haruffa.
Mu dauki layin gwaji x=x. Ya dace da magana .*.*=.*. .*.* kafin alamar daidai ta yi daidai da na farko x (daya daga cikin kungiyoyin .* соответствует x, da kuma na biyu - sifili haruffa). .* bayan = matches na karshe x.
Wannan kwatanta yana buƙatar matakai 23. Rukunin farko .* в .*.*=.* yana yin zari kuma ya dace da dukan kirtani x=x. Injin yana motsawa zuwa rukuni na gaba .*. Ba mu da sauran haruffa da za mu daidaita, don haka rukuni na biyu .* yayi daidai da haruffa sifili (an yarda da wannan). Sa'an nan injin ya matsa zuwa alamar =. Babu sauran alamomi (ƙungiyar farko .* yayi amfani da dukan magana x=x), babu kwatanta faruwa.
Sannan injin magana na yau da kullun yana komawa farkon. Ya ci gaba zuwa rukuni na farko .* da kwatanta shi с x= (maimakon x=x), sa'an nan kuma ɗauka a kan rukuni na biyu .*. Rukuni na biyu .* ana kwatanta shi da na biyu x, kuma ba mu da sauran haruffa. Kuma idan injin ya sake kaiwa = в .*.*=.*, babu abin da ke aiki. Ya sake ja da baya.
Wannan karon kungiyar .* har yanzu yana daidaitawa x=, amma rukuni na biyu .* babu kuma x, da sifili. Injin yana ƙoƙarin nemo ainihin hali = a cikin tsari .*.*=.*, amma bai fito ba (bayan haka, rukunin farko ya riga ya mamaye shi .*). Ya sake ja da baya.
Wannan karon rukuni na farko .* yana ɗaukan farko x. Amma rukuni na biyu .* "cikin zari" yana kamawa =x. Kun riga kun yi hasashen abin da zai faru? Injin yana ƙoƙarin daidaitawa na zahiri =, kasa kuma yayi wani ja da baya.
Rukuni na farko .* har yanzu yayi daidai da na farko x. Na biyu .* kawai dauka =. Tabbas, injin ba zai iya daidaita na zahiri ba =, domin rukuni na biyu sun riga sun yi wannan .*. Kuma sake ja da baya. Kuma muna ƙoƙarin daidaita jerin haruffa uku!
A sakamakon haka, rukuni na farko .* yayi daidai da na farko kawai x, na biyu .* - tare da haruffan sifili, kuma injin a ƙarshe ya dace da ainihin = cikin magana с = a layi. Na gaba shine rukuni na ƙarshe .* ana kwatanta shi da na ƙarshe x.
Matakai 23 kawai don x=x. Kalli ɗan gajeren bidiyo game da amfani da Perl , wanda ke nuna yadda matakai da ja da baya ke faruwa.
Wannan ya rigaya aiki mai yawa, amma menene idan maimakon haka x=x za mu samu x=xx? Matakai 33 kenan. Kuma idan x=xxx? 45. Alakar ba ta layi ba ce. Hoton yana nuna kwatancen daga x=x to x=xxxxxxxxxxxxxxxxxxxx (20 x после =). Idan muna da 20x bayan =, injin ya kammala daidaitawa cikin matakai 555! (Bugu da ƙari, idan mun yi hasara x= kuma kirtani kawai ta ƙunshi 20 x, injin zai ɗauki matakai 4067 don fahimtar cewa babu matches).
Wannan bidiyon yana nuna duk ja da baya don kwatantawa x=xxxxxxxxxxxxxxxxxxxx:
Matsalar ita ce yayin da girman kirtani ya ƙaru, lokacin daidaitawa yana girma sosai. Amma abubuwa na iya yin muni idan an gyaggyara magana ta yau da kullun. A ce muna da .*.*=.*; (wato, akwai wani yanki na zahiri a ƙarshen ƙirar). Misali, don dacewa da magana kamar foo=bar;.
Kuma a nan ja da baya zai zama babban bala'i. Don kwatanta x=x zai dauki matakai 90, ba 23. Kuma adadin yana karuwa da sauri. Don kwatanta x= da 20 x, 5353 matakai ake bukata. Ga ginshiƙi. Dubi ƙimar axis Y idan aka kwatanta da ginshiƙi na baya.
Idan kuna sha'awar, duba duk matakan daidaita 5353 da suka gaza x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Ta hanyar amfani da kasala maimakon haɗama, ana iya sarrafa iyakar ja da baya. Idan muka canza ainihin magana zuwa .*?.*?=.*?, don kwatanta x=x zai dauki matakai 11 (ba 23 ba). Amma game da x=xxxxxxxxxxxxxxxxxxxx. Duk saboda ? после .* yana gaya wa injin ya dace da ƙaramin adadin haruffa kafin ya ci gaba.
Amma taswirorin kasala ba su warware matsalar ja da baya gaba daya. Idan muka maye gurbin misalin bala'i .*.*=.*; a kan .*?.*?=.*?;, lokacin aiwatarwa zai kasance iri ɗaya. x=x har yanzu yana buƙatar matakai 555, kuma x= da 20 x - 5353.
Iyakar abin da za a iya yi (ban da sake rubuta tsarin gaba ɗaya don ƙayyadaddun ƙayyadaddun ƙayyadaddun ƙayyadaddun bayanai) shine barin injin faɗakarwa na yau da kullun tare da hanyar dawo da baya. Wannan shi ne abin da za mu yi a cikin 'yan makonni masu zuwa.
An san maganin wannan matsala tun 1968, lokacin da Kent Thompson ya rubuta labarin ("Hanyoyin Shirye-Shirye: Algorithm na Bincike na yau da kullum"). Labarin ya bayyana wata hanyar da ke ba ku damar canza magana ta yau da kullun zuwa injunan ƙasa mara iyaka, kuma bayan canje-canje na jihohi a cikin injunan ƙarancin ƙarancin ƙima, yi amfani da algorithm wanda lokacin aiwatarwa ya dogara da layi akan layin da ya dace.
Hanyoyin Shirye-shiryen
Binciken Algorithm na Magana akai-akai
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyYana bayyana hanyar nemo takamaiman zaren haruffa a cikin rubutu kuma yayi magana akan aiwatar da wannan hanyar a sigar mai tarawa. Mai tarawa yana ɗaukar furci na yau da kullun azaman lambar tushe kuma yana samar da shirin IBM 7094 azaman lambar abu. Shirin abu yana ɗaukar shigarwa ta hanyar rubutun bincike kuma yana fitar da sigina a duk lokacin da zaren rubutu ya dace da wani furci na yau da kullun. Labarin ya ba da misalai, matsaloli da mafita.
Algorithm
Algorithms bincike na baya sun haifar da ja da baya idan wani ɓangaren bincike na nasara ya kasa samar da sakamako.A cikin yanayin haɗawa, algorithm ba ya aiki tare da alamomi. Yana ƙetare umarni zuwa harhada lamba. Kisa yana da sauri sosai - bayan ƙaddamar da bayanai zuwa saman jerin abubuwan da ke yanzu, yana bincika ta atomatik don duk yiwuwar haruffa a jere a cikin magana ta yau da kullun.
An haɗa haɗawa da algorithm bincike a cikin editan rubutun raba lokaci azaman bincike na mahallin. Tabbas, wannan yayi nisa da kawai aikace-aikacen irin wannan hanyar bincike. Misali, ana amfani da bambance-bambancen wannan algorithm azaman bincike na alama a cikin tebur a cikin masu tarawa.
Ana ɗauka cewa mai karatu ya san maganganu na yau da kullun da kuma IBM 7094 na shirye-shiryen kwamfuta.Mai tarawa
Mai tarawa ya ƙunshi matakai guda uku da ke gudana a layi daya. Mataki na farko shine tacewa syntax, wanda ke ba da damar kawai daidaitattun maganganu na yau da kullun don wucewa. Wannan matakin kuma yana saka ma'aikacin "·" don dacewa da maganganun yau da kullun. A mataki na biyu, ana jujjuya magana ta yau da kullun zuwa sigar postfix. A mataki na uku, an ƙirƙiri lambar abu. Matakai guda 2 na farko a bayyane suke, kuma ba za mu dakata a kansu ba.
Labarin Thompson ba ya magana game da na'urori masu iyakacin iyaka, amma yana bayyana madaidaicin lokacin algorithm da kyau kuma yana gabatar da shirin ALGOL-60 wanda ke haifar da lambar yaren taro don IBM 7094. Aiwatar da aiwatarwa yana da wahala, amma ra'ayin yana da sauƙi.
hanyar bincike na yanzu. Ana wakilta shi da alamar ⊕ tare da shigarwa ɗaya da fitarwa guda biyu.
Hoto na 1 yana nuna ayyukan mataki na tarawa na uku lokacin da ake canza misalin magana ta yau da kullun. Haruffa uku na farko a cikin misalin sune a, b, c, kuma kowannensu yana haifar da tari S[i] da filin NNODE.NNODE zuwa lambar data kasance don samar da sakamako na yau da kullun a cikin shigarwa guda ɗaya (duba Hoto 5)
Wannan shine abin da magana ta yau da kullun zata yi kama .*.*=.*, idan kun yi tunanin shi kamar a cikin hotuna daga labarin Thompson.
A cikin siffa. 0 akwai jihohi biyar da suka fara daga 0, da kuma zagayowar 3 waɗanda ke farawa daga jihohi 1, 2 da 3. Waɗannan zagayowar uku sun dace da uku. .* a cikin magana akai-akai. Ovals 3 masu dige-dige sun dace da alama ɗaya. Oval tare da alama = yayi daidai da ainihin hali =. Jiha 4 ta ƙare. Idan muka isa gare shi, to, magana ta yau da kullum ta dace.
Don ganin yadda za a iya amfani da irin wannan zane na jaha don daidaita magana akai-akai .*.*=.*, za mu duba string matching x=x. Shirin yana farawa daga jiha 0, kamar yadda aka nuna a Fig. 1.
Domin wannan algorithm yayi aiki, dole ne injin jihar ya kasance cikin jihohi da yawa a lokaci guda. Na'ura mai iyaka mara iyaka zai yi duk yuwuwar sauyawa a lokaci guda.
Kafin ya sami lokacin karanta bayanan shigarwa, yana shiga cikin jihohin farko (1 da 2), kamar yadda aka nuna a cikin siffa. 2.
A cikin siffa. 2 yana nuna abin da ke faruwa idan ya kalli farko x в x=x. x iya taswira zuwa saman batu, tafiya daga jiha 1 da baya zuwa jiha 1. Ko x zai iya taswira zuwa wurin da ke ƙasa, yana tafiya daga jiha 2 kuma komawa zuwa jiha 2.
Bayan daidaita na farko x в x=x har yanzu muna cikin jahohi 1 da 2. Ba za mu iya isa jiha ta 3 ko 4 ba saboda muna bukatar hali na zahiri. =.
Algorithm sai yayi la'akari = в x=x. Kamar x a gabansa, ana iya daidaita shi da ɗayan manyan madaukai biyu daga jiha 1 zuwa jiha 1 ko daga jiha 2 zuwa jiha 2, amma algorithm na iya daidaita madaidaicin. = kuma matsa daga jiha 2 zuwa jiha 3 (kuma nan da nan 4). Ana nuna wannan a cikin Fig. 3.
Algorithm ɗin sai ya matsa zuwa na ƙarshe x в x=x. Daga Jihohi 1 da 2 ana iya yin sauye-sauye iri ɗaya zuwa jihohi 1 da 2. Daga jiha ta 3 x zai iya daidaita batu a hannun dama kuma ya koma jihar 3.
A wannan mataki, kowane hali x=x la'akari, kuma tun da mun kai jihar 4, magana ta yau da kullun ta yi daidai da wannan kirtani. Ana sarrafa kowane hali sau ɗaya, don haka wannan algorithm ɗin layi ne a cikin tsayin igiyoyin shigarwa. Kuma babu ja da baya.
Babu shakka, bayan isa jihar 4 (lokacin da algorithm ya dace x=) Dukkan maganganun yau da kullum sun dace, kuma algorithm na iya ƙare ba tare da la'akari da shi ba x.
Wannan algorithm din ya dogara da kai tsaye akan girman kirtan shigarwar.
source: www.habr.com