9 жыл бұрын Cloudflare кішкентай компания болды, мен ол үшін жұмыс істемедім, мен жай ғана тұтынушы болдым. Cloudflare іске қосылғаннан кейін бір айдан кейін мен веб-сайтым туралы хабарлама алдым DNS жұмыс істемейтін сияқты. Cloudflare өзгеріс енгізді , және бұзылған DNS болды.
Мен бірден Мэтью Принске «Менің DNS қайда?» деген тақырыппен жаздым, ол техникалық мәліметтерге толы ұзақ жауап жіберді (), оған мен жауап бердім:
Кімнен: Джон Грэм-Камминг
Күні: 7 қазан 2010 жыл, 9:14
Тақырып: Re: Менің DNS қайда?
Кімге: Мэттью ПринсКеремет есеп, рахмет. Мәселелер болса міндетті түрде хабарласамын. Барлық техникалық ақпаратты жинағаннан кейін бұл туралы жазба жазу керек шығар. Менің ойымша, адамдарға ашық және шынайы әңгіме ұнайды. Әсіресе, іске қосылғаннан бері трафиктің қалай өскенін көрсету үшін оған графиктерді тіркесеңіз.
Менің сайтымда жақсы мониторинг бар, мен әрбір сәтсіздік туралы SMS аламын. Мониторинг көрсеткендей, ақау 13:03:07 мен 14:04:12 аралығында болған. Тесттер әрбір бес минут сайын жүргізіледі.
Сіз мұны түсінетініңізге сенімдімін. Еуропада өз адамыңыздың қажеті жоқ екеніне сенімдісіз бе? 🙂
Және ол жауап берді:
Кімнен: Мэттью Принс
Күні: 7 қазан 2010 жыл, 9:57
Тақырып: Re: Менің DNS қайда?
Кімге: Джон Грэм-КаммингРақмет сізге. Жазғандардың бәріне жауап бердік. Мен қазір кеңсеге бара жатырмын, біз блогқа бірдеңе жазамыз немесе хабарландыру тақтасына ресми жазбаны бекітеміз. Толықтай келісемін, адалдық бәрі.
Қазір Cloudflare шынымен үлкен компания, мен ол үшін жұмыс істеймін, енді мен өз қателігіміз туралы, оның салдары мен әрекеттеріміз туралы ашық жазуым керек.
2 шілдедегі оқиғалар
2 шілдеде біз WAF үшін басқарылатын ережелерде жаңа ережені шығардық, соның арқасында бүкіл әлем бойынша Cloudflare желісіндегі HTTP/HTTPS трафигін өңдейтін әрбір процессор өзегінде. Біз жаңа осалдықтар мен қауіптерге жауап ретінде WAF үшін басқарылатын ережелерді үнемі жетілдіріп отырамыз. Мысалы, мамыр айында біз асығыс болдық SharePoint бағдарламасындағы маңызды осалдықтан қорғау үшін. Біздің WAF-тың барлық мәні - ережелерді жылдам және жаһандық түрде орналастыру мүмкіндігі.
Өкінішке орай, өткен бейсенбідегі жаңартуда кері бақылауға тым көп HTTP/HTTPS CPU ресурстарын жұмсайтын тұрақты өрнек болды. Нәтижесінде біздің негізгі прокси, CDN және WAF функциялары бұзылды. График HTTP/HTTPS трафигіне қызмет көрсетуге арналған процессор ресурстары біздің желіміздегі серверлерде 100% дерлік жететінін көрсетеді.
Оқиға кезінде бір нүктеде CPU пайдалану
Нәтижесінде біздің клиенттеріміз (және біздің клиенттеріміздің клиенттері) Cloudflare домендерінде 502 қате бетімен аяқталды. 502 қате әлі де бос ядролары бар, бірақ HTTP/HTTPS трафигін өңдейтін процестермен байланыса алмайтын Cloudflare фронтальды веб-серверлері арқылы жасалды.
Бұл тұтынушыларымызға қаншалықты қолайсыздықтар тудырғанын білеміз. Біз қатты ұялдық. Және бұл сәтсіздік оқиғамен тиімді күресуге кедергі болды.
Егер сіз осы тұтынушылардың бірі болсаңыз, сіз қорқып, ашуланған және ренжіген боларсыз. Оның үстіне, бізде болған жоқ . Орталық процессордың жоғары тұтынылуы нашар тұжырымдалған тұрақты өрнекпен бір WAF ережесіне байланысты болды, бұл шамадан тыс кері кетуге әкелді. Міне, кінәлі өрнек: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Бұл өзінше қызық болғанымен (және мен бұл туралы төменде толығырақ айтатын боламын), Cloudflare қызметі қалыпты өрнектің нашарлығынан ғана емес, 27 минутқа жұмыс істемеді. Сәтсіздікке әкелген оқиғалар тізбегін сипаттау үшін бізге біраз уақыт қажет болды, сондықтан біз жауап беруге баяу болдық. Жазбаның соңында мен кері кетуді тұрақты өрнекте сипаттаймын және онымен не істеу керектігін айтамын.
Не болды
Тәртіппен бастайық. Мұндағы барлық уақыт UTC бойынша.
Сағат 13:42-де брандмауэр тобының инженері анықтау ережелеріне кішкене өзгеріс енгізді. автоматты процесті қолдану. Сәйкесінше, өзгерту сұрау билеті жасалды. Біз мұндай билеттерді Jira арқылы басқарамыз (төмендегі скриншот).
3 минуттан кейін WAF ақаулығы туралы хабарлайтын PagerDuty бірінші беті пайда болды. Бұл қалыпты жұмысты бақылау үшін Cloudflare қолданбасынан тыс WAF құрылғыларының (бізде олардың жүздегені) функционалдығын сынайтын синтетикалық сынақ болды. Осыдан кейін бірден басқа Cloudflare сервистік сынақтарының сәтсіздікке ұшырауы, жаһандық трафик мәселелері, кең таралған 502 қателер және дүние жүзіндегі қалалардағы біздің қатысу нүктелерімізден (PoP) көптеген есептер жетіспейтіндігі туралы ескертулер беттері пайда болды. CPU ресурстары.
Мен осы ескертулердің бірнешеуін алдым, жиналыстан шығып, үстелге бара жатқанда, шешімдерді әзірлеу бөлімінің басшысы трафиктің 80% жоғалтқанымызды айтты. Мен мәселемен айналысып жатқан SRE инженерлеріне жүгірдім. Басында біз бұл белгісіз шабуыл деп ойладық.
Cloudflare SRE инженерлері бүкіл әлем бойынша шашыраңқы және тәулік бойы жағдайды бақылайды. Әдетте, бұл ескертулер шектеулі ауқымдағы нақты жергілікті мәселелер туралы хабарлайды, ішкі бақылау тақталарында бақыланады және күніне бірнеше рет шешіледі. Бірақ бұл беттер мен хабарландырулар шын мәнінде маңызды нәрсені көрсетті және SRE инженерлері бірден P0 ауырлық деңгейін жариялады және басшылық пен жүйе инженерлеріне хабарласты.
Бұл кезде біздің лондондық инженерлер үлкен залда лекция тыңдап отырған. Лекцияны үзуге тура келді, барлығы үлкен мәжіліс залына жиналды, тағы да мамандар шақырылды. Бұл SRE өздері шеше алатын әдеттегі мәселе емес еді. Тиісті мамандарды тарту қажет болды.
Сағат 14:00-де мәселенің WAF-та екенін және ешқандай шабуыл болмағанын анықтадық. Өнімділік тобы CPU деректерін алып тастады және WAF кінәлі екені белгілі болды. Басқа қызметкер бұл теорияны strace көмегімен растады. Басқа біреу журналдарда WAF ақаулығы бар екенін көрді. Сағат 14:02-де бүкіл команда бүкіл әлем бойынша бір компонентті өшіретін Cloudflare жүйесіне енгізілген жаһандық өлтіруді пайдалануды ұсынған кезде маған келді.
WAF үшін жаһандық өлтіруді қалай жасағанымыз басқа әңгіме. Бұл қарапайым емес. Біз өз өнімдерімізді пайдаланамыз және біздің қызметімізден бері жұмыс істемеді, ішкі басқару тақтасына аутентификация және кіре алмадық (бәрі түзетілгенде, ішкі басқару тақтасы пайдаланылмаса, тіркелгі деректерін өшіретін қауіпсіздік мүмкіндігіне байланысты кейбір топ мүшелері кіру мүмкіндігін жоғалтқанын білдік. ұзақ уақыт).
Біз Jira немесе құрастыру жүйесі сияқты ішкі қызметтерімізге қол жеткізе алмадық. Бізге сирек қолданатын уақытша шешу механизмі қажет болды (бұл да пысықталуды қажет етеді). Соңында бір инженер 14:07-де WAF-ты өшіре алды, ал 14:09-да трафик пен процессор деңгейі барлық жерде қалыпты жағдайға оралды. Cloudflare қорғанысының қалған механизмдері қалыпты жұмыс істеді.
Содан кейін біз WAF қалпына келтіруге кірістік. Жағдай әдеттегіден тыс болды, сондықтан біз бір қалада жеке трафикті пайдаланып, ақылы тұтынушыларды сол жерден аударып, теріс сынақтарды (өзгеріс шынымен проблема ма деп сұрадық) және оң сынақтарды (қайтару жұмыс істейтініне көз жеткізу) жүргіздік.
14:52-де біз оның себебін түсініп, түзету енгізгенімізге көз жеткіздік және WAF қайта қосылды.
Cloudflare қалай жұмыс істейді
Cloudflare-де WAF ережелерін басқаруға арналған инженерлер тобы бар. Олар анықтау жылдамдығын жақсартуға, жалған позитивтерді азайтуға және пайда болған жаңа қауіптерге тез жауап беруге тырысады. Соңғы 60 күнде WAF үшін басқарылатын ережелер үшін өңделген 476 өзгерту сұрауы болды (орта есеппен әр 3 сағат сайын бір).
Бұл нақты өзгерісті модельдеу режимінде қолдану қажет болды, мұнда нақты клиент трафигі ереже арқылы өтеді, бірақ ештеңе бұғатталмайды. Біз бұл режимді ережелердің тиімділігін тексеру және жалған оң және жалған теріс көрсеткіштерді өлшеу үшін пайдаланамыз. Бірақ модельдеу режимінде де ережелер шын мәнінде орындалуы керек және бұл жағдайда ережеде процессор ресурстарын тым көп тұтынатын тұрақты өрнек бар.
Жоғарыдағы өзгерту сұрауынан көріп отырғаныңыздай, бізде орналастыру жоспары, кері қайтару жоспары және осы орналастыру түріне арналған ішкі стандартты операциялық процедураға (SOP) сілтеме бар. Ережені өзгертуге арналған SOP оны ғаламдық деңгейде жариялауға мүмкіндік береді. Шын мәнінде, Cloudflare-де бәрі басқаша жасалады және SOP алдымен тестілеу және ішкі пайдалану үшін бағдарламалық жасақтаманы ішкі қатысу нүктесіне (PoP) (біздің қызметкерлер пайдаланатын), содан кейін клиенттердің аз санына жіберуді талап етеді. оқшауланған орынға, содан кейін көптеген клиенттерге, содан кейін ғана бүкіл әлемге.
Бұл осылай көрінеді. Біз git-ті BitBucket арқылы іштей қолданамыз. Өзгерістермен жұмыс істейтін инженерлер TeamCity жүйесіне құрастырылған кодты жібереді және құрастыру өткен кезде рецензенттер тағайындалады. Тарту сұрауы мақұлданғаннан кейін код жиналады және бірқатар сынақтар орындалады (қайтадан).
Егер құрастыру және сынақтар сәтті аяқталса, Jira жүйесінде өзгерту сұрауы жасалады және сәйкес менеджер немесе жетекші өзгертуді мақұлдауы керек. Бекітілгеннен кейін орналастыру «PoP menagerie» деп аталады: DOG, PIG және (ит, шошқа және канарей).
DOG PoP – бұл Cloudflare PoP (біздің қалаларымыздың басқалары сияқты), оны тек Cloudflare қызметкерлері пайдаланады. Ішкі пайдалануға арналған PoP тұтынушы трафигі шешімге түсе бастағанға дейін мәселелерді шешуге мүмкіндік береді. Пайдалы нәрсе.
DOG сынағы сәтті болса, код PIG (теңіз шошқасы) кезеңіне өтеді. Бұл Cloudflare PoP, мұнда жаңа код арқылы аздаған тегін тұтынушы трафигі өтеді.
Егер бәрі жақсы болса, код Канарияға түседі. Бізде әлемнің әртүрлі бөліктерінде үш Canary PoP бар. Оларда ақылы және тегін клиенттердің трафигі жаңа код арқылы өтеді және бұл қателерді соңғы тексеру.
Cloudflare-де бағдарламалық құралды шығару процесі
Канарияда код дұрыс болса, біз оны шығарамыз. Барлық кезеңдерден өту - DOG, PIG, Canary, бүкіл әлем - кодтың өзгеруіне байланысты бірнеше сағат немесе күн қажет. Cloudflare желісі мен клиенттерінің әртүрлілігіне байланысты біз оны барлық клиенттерге жаһандық деңгейде шығармас бұрын кодты мұқият тексереміз. Бірақ WAF бұл процесті арнайы орындамайды, себебі қауіптерге тез жауап беру керек.
WAF қауіптері
Соңғы бірнеше жылда жалпы қолданбаларда қауіптердің айтарлықтай өсуі байқалды. Бұл бағдарламалық жасақтаманы тестілеу құралдарының көбірек қолжетімділігіне байланысты. Мысалы, біз жақында жазғанбыз ).
Ақпарат көзі:
Көбінесе тұжырымдаманың дәлелі жасалады және бірден Github сайтында жарияланады, осылайша қолданбаны қолдайтын топтар оны жылдам тексеріп, оның тиісті түрде қорғалғанына көз жеткізе алады. Сондықтан Cloudflare жаңа шабуылдарға мүмкіндігінше тез жауап беру мүмкіндігін қажет етеді, осылайша тұтынушылар өздерінің бағдарламалық жасақтамасын түзетуге мүмкіндік алады.
Cloudflare жылдам әрекет етуінің тамаша үлгісі мамыр айында SharePoint осалдықты қорғау құралдарын қолдану болып табылады (). Хабарландырулар жасалғаннан кейін бірден дерлік біз тұтынушыларымыздың SharePoint орнатуларындағы осалдықты пайдалану әрекеттерінің көп санын байқадық. Біздің жігіттер тұтынушыларымызды қорғау үшін жаңа қауіптерді және жазу ережелерін үнемі қадағалап отырады.
Бейсенбіде проблеманы тудырған ереже сайтаралық сценарийден (XSS) қорғауы керек еді. Соңғы жылдары мұндай шабуылдар да жиілеп кетті.
Ақпарат көзі:
WAF үшін басқарылатын ережені өзгертудің стандартты процедурасы жаһандық орналастыру алдында үздіксіз интеграция (CI) сынақтарын жүргізу болып табылады. Өткен бейсенбіде біз мұны жасадық және ережелерді шығардық. Сағат 13:31-де инженер өзгерісі бар мақұлданған тарту сұрауын жіберді.
Сағат 13:37-де TeamCity ережелерді жинап, сынақтар өткізді және рұқсат берді. WAF сынақ жинағы WAF негізгі функционалдығын тексереді және жеке функцияларға арналған бірлік сынақтарының көп санынан тұрады. Бірлік сынақтарынан кейін біз HTTP сұрауларының үлкен санын пайдаланып WAF ережелерін сынадық. HTTP сұраулары WAF қандай сұрауларды бұғаттау керектігін (шабуылға тосқауыл қою үшін) және қайсысы арқылы рұқсат беруге болатынын (бәрін блоктамау және жалған позитивтерді болдырмау үшін) тексереді. Бірақ біз процессорды шамадан тыс пайдалануды сынамадық және алдыңғы WAF құрастыруларының журналдарын зерттеу ереже сынағының орындалу уақыты артпағанын көрсетеді және ресурстар жеткіліксіз болады деп күдіктену қиын болды.
Сынақтар өтті және TeamCity 13:42-де өзгерісті автоматты түрде енгізе бастады.
Quicksilver
WAF ережелері қауіп-қатерді дереу жоюға бағытталған, сондықтан біз оларды өзгерістерді секундтар ішінде жаһандық деңгейде тарататын Quicksilver-тің бөлінген кілт-мән қоймасын пайдаланып орналастырамыз. Біздің барлық клиенттеріміз бұл технологияны бақылау тақтасындағы немесе API арқылы конфигурацияны өзгерткен кезде пайдаланады және соның арқасында біз өзгерістерге найзағай жылдамдығымен жауап береміз.
Біз Quicksilver туралы көп сөйлескен жоқпыз. Бұрын қолданатынбыз жаһандық деңгейде таратылған негізгі құндылық дүкені ретінде, бірақ онымен операциялық мәселелер туындады және біз 180-нен астам қалада көшірілген өз дүкенімізді жаздық. Біз қазір Quicksilver қолданбасын конфигурация өзгерістерін клиенттерге жіберу, WAF ережелерін жаңарту және клиенттер жазған JavaScript кодын Cloudflare Workers қызметіне тарату үшін пайдаланамыз.
Бақылау тақтасындағы түймені басу немесе API шақырудан бүкіл әлем бойынша конфигурацияны өзгертуге бірнеше секунд кетеді. Клиенттерге орнатудың бұл жылдамдығы ұнады. Ал Workers оларға дерлік ғаламдық бағдарламалық құралды орналастыруды береді. Орташа алғанда, Quicksilver секундына шамамен 350 өзгерістерді таратады.
Ал Quicksilver өте жылдам. Орташа алғанда, біз әлемдегі әрбір компьютерге өзгерістерді тарату үшін 99 секундтың 2,29-процентильіне қол жеткіздік. Жылдамдық әдетте жақсы нәрсе. Өйткені, сіз функцияны қосқанда немесе кэшті тазартқанда, ол бірден және барлық жерде болады. Cloudflare Workers арқылы кодты жіберу бірдей жылдамдықта жүреді. Cloudflare өз тұтынушыларына қажетті уақытта жылдам жаңартуларды уәде етеді.
Бірақ бұл жағдайда жылдамдық бізді қатал әзілге айналдырды және ережелер барлық жерде бірнеше секундта өзгерді. WAF кодын Lua қолданатынын байқаған боларсыз. Cloudflare Lua-ны өндірісте және бөлшектерде кеңінен пайдаланады біз бармыз . Lua WAF пайдаланады ішкі және сәйкестендіру үшін кері бақылауды қолданады. Оның бақылаудан шығып кететін өрнектерден қорғайтын механизмдері жоқ. Төменде мен бұл туралы және бұл туралы не істеп жатқанымыз туралы көбірек айтатын боламын.
Ережелер орналастырылғанға дейін бәрі бірқалыпты өтті: тарту сұрауы жасалды және бекітілді, CI/CD құбыры кодты жинап, сынады, өзгерту сұрауы орналастыру мен кері қайтаруды реттейтін SOP сәйкес жіберілді және орналастыру аяқталды.
Cloudflare WAF орналастыру процесі
Неліктен дұрыс емес болды
Мен айтқанымдай, біз апта сайын ондаған жаңа WAF ережелерін енгіземіз және бізде мұндай орналастырудың жағымсыз салдарынан қорғайтын көптеген жүйелер бар. Ал бірдеңе дұрыс болмаса, бұл әдетте бірден бірнеше жағдайдың жиынтығы. Егер сіз бір ғана себеп тапсаңыз, бұл, әрине, сендіреді, бірақ бұл әрқашан дұрыс емес. Бұл HTTP/HTTPS қызметіміздің істен шығуына әкелген себептер.
- Инженер шамадан тыс болуы мүмкін тұрақты өрнек жазды .
- Тұрақты өрнектің тым көп процессорды ысырап етуіне жол бермеуі мүмкін мүмкіндік бірнеше апта бұрын WAF рефакторингінде қате жойылды - WAF ресурстарды аз тұтыну үшін рефакторинг қажет болды.
- Тұрақты өрнек қозғалтқышында күрделілік кепілдіктері болмады.
- Сынақ жинағы процессорды шамадан тыс тұтынуды анықтай алмады.
- SOP шұғыл емес ереже өзгерістерін көп сатылы процесссіз жаһандық деңгейде таратуға мүмкіндік береді.
- Қайтару жоспары толық WAF құрастыруын екі рет іске қосуды талап етті, бұл ұзақ уақытқа созылды.
- Жаһандық жол қозғалысы проблемалары туралы алғашқы ескерту тым кеш іске қосылды.
- Күй бетін жаңартуға біраз уақыт кетті.
- Бізде ақауға байланысты жүйелерге кіруде қиындықтар туындады және айналып өту процедурасы дұрыс орнатылмаған.
- SRE инженерлері кейбір жүйелерге кіру мүмкіндігін жоғалтты, себебі олардың тіркелгі деректері қауіпсіздік себептеріне байланысты аяқталды.
- Біздің тұтынушылар Cloudflare бақылау тақтасына немесе API интерфейсіне қол жеткізе алмады, себебі олар Cloudflare аймағы арқылы өтеді.
Өткен бейсенбіден бері не өзгерді
Біріншіден, біз WAF үшін шығарылымдар бойынша барлық жұмыстарды толығымен тоқтаттық және келесі әрекеттерді орындаймыз:
- Біз алып тастаған орталық процессорды шамадан тыс пайдаланудан қорғауды қайта енгіземіз. (Дайын)
- WAF үшін басқарылатын ережелердегі барлық 3868 ережені қолмен тексеру, шамадан тыс кері шегінудің басқа ықтимал жағдайларын табу және түзету. (Тексеру аяқталды)
- Сынақ жиынындағы барлық ережелер үшін өнімділік профилін жасауды қосамыз. (Күтілетін: 19 шілде)
- Тұрақты өрнек механизміне ауысу немесе - екеуі де орындау уақытына кепілдік береді. (Күтілетін: 31 шілде)
- Біз Cloudflare-дегі басқа бағдарламалық жасақтама сияқты ережелерді кезең-кезеңмен орналастыру үшін SOP-ны қайта жазып жатырмыз, бірақ сонымен бірге шабуылдар әлдеқашан басталған болса, төтенше жағдайда жаһандық орналастыру мүмкіндігіне ие боламыз.
- Біз Cloudflare бақылау тақтасын және API интерфейсін Cloudflare аймағынан шұғыл түрде жою мүмкіндігін дамытамыз.
- Бет жаңартуларын автоматтандыру .
Ұзақ мерзімді перспективада біз бірнеше жыл бұрын жазған Луа 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. Perl пайдалану туралы қысқаша бейнені қараңыз , ол қадамдар мен кері тректердің қалай болатынын көрсетеді.
Бұл қазірдің өзінде көп жұмыс, бірақ оның орнына не істеу керек 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 жылдан бері белгілі («Бағдарламалау әдістері: тұрақты өрнектерді іздеу алгоритмі»). Мақалада тұрақты өрнекті детерминирленген емес соңғы күй машиналарына түрлендіруге мүмкіндік беретін механизм сипатталған және детерминирленген емес соңғы күй машиналарында күй өзгергеннен кейін орындалу уақыты сәйкес келетін жолға сызықтық тәуелді алгоритмді қолданыңыз.
Бағдарламалау әдістері
Тұрақты өрнектерді іздеу алгоритмі
Кен Томпсон
Bell Telephone Laboratories, Inc., Мюррей Хилл, Нью-ДжерсиОл мәтіндегі таңбалардың белгілі бір жолын іздеу әдісін сипаттайды және бұл әдісті компилятор түрінде жүзеге асыруды талқылайды. Компилятор тұрақты өрнекті бастапқы код ретінде қабылдайды және IBM 7094 бағдарламасын нысан коды ретінде шығарады. Нысандық бағдарлама іздеу мәтіні түрінде енгізуді қабылдайды және мәтін жолы берілген тұрақты өрнекке сәйкес келген сайын сигнал шығарады. Мақалада мысалдар, мәселелер және шешімдер берілген.
Алгоритм
Алдыңғы іздеу алгоритмдері ішінара сәтті іздеу нәтиже бермесе, кері қайтаруға әкелді.Компиляция режимінде алгоритм символдармен жұмыс істемейді. Ол құрастырылған кодқа нұсқауларды жібереді. Орындау өте жылдам – деректерді ағымдағы тізімнің жоғарғы жағына жібергеннен кейін ол қалыпты өрнектегі барлық ықтимал дәйекті таңбаларды автоматты түрде іздейді.
Құрастыру және іздеу алгоритмі мәтінмәндік іздеу ретінде уақытты бөлісу мәтіндік редакторында қамтылған. Әрине, бұл мұндай іздеу процедурасының жалғыз қолданылуынан алыс. Мысалы, бұл алгоритмнің нұсқасы ассемблердегі кестеде символдық іздеу ретінде пайдаланылады.
Оқырман тұрақты тіркестермен және IBM 7094 компьютерлік бағдарламалау тілімен таныс деп болжанады.Құрастырушы
Компилятор параллель жұмыс істейтін үш кезеңнен тұрады. Бірінші кезең – синтаксистік сүзгілеу, ол тек синтаксистік түзетілген тұрақты тіркестердің өтуіне мүмкіндік береді. Бұл қадам қалыпты өрнектерді сәйкестендіру үшін «·» операторын да кірістіреді. Екінші қадамда тұрақты өрнек постфикс пішініне түрлендіріледі. Үшінші кезеңде объект коды жасалады. Алғашқы 2 кезең айқын, біз оларға тоқталмаймыз.
Томпсонның мақаласы анықталмаған соңғы күй машиналары туралы айтылмайды, бірақ ол сызықтық уақыт алгоритмін жақсы түсіндіреді және IBM 60 үшін ассемблер тілінің кодын генерациялайтын ALGOL-7094 бағдарламасын ұсынады. Іске асыру қиын, бірақ идея өте қарапайым.
ағымдағы іздеу жолы. Ол бір кіріс және екі шығысы бар ⊕ белгішесі арқылы көрсетіледі.
1-сурет тұрақты өрнек үлгісін түрлендіру кезінде үшінші құрастыру қадамының функцияларын көрсетеді. Мысалдағы алғашқы үш таңба a, b, c және әрқайсысы S[i] стек жазбасын және NNODE өрісін жасайды.Бір стек жазбасында нәтижелі тұрақты өрнекті жасау үшін бар кодқа NNODE (5-суретті қараңыз)
Тұрақты өрнек осылай көрінеді .*.*=.*, егер сіз оны Томпсонның мақаласындағы суреттердегідей елестетсеңіз.
Суретте. 0 0-ден басталатын бес күй және 3, 1 және 2 күйлерден басталатын 3 цикл бар. Бұл үш цикл үшке сәйкес келеді. .* тұрақты өрнекте. Бір таңбаға нүктелері бар 3 сопақ сәйкес келеді. Белгісі бар сопақ = әріптік таңбаға сәйкес келеді =. 4-ші мемлекет соңғы болып табылады. Егер біз оған жетсек, онда тұрақты өрнек сәйкес келеді.
Осындай күй диаграммасын тұрақты өрнектерді сәйкестендіру үшін қалай пайдалануға болатынын көру .*.*=.*, біз жолды сәйкестендіруді қарастырамыз x=x. Бағдарлама суретте көрсетілгендей 0 күйінен басталады. 1.
Бұл алгоритм жұмыс істеуі үшін күй машинасы бір уақытта бірнеше күйде болуы керек. Детерминирленген емес соңғы машина барлық мүмкін ауысуларды бір уақытта жасайды.
Енгізілген деректерді оқып үлгермей тұрып, ол суретте көрсетілгендей бірінші екі күйге де (1 және 2) өтеді. 2.
Суретте. 2 біріншіге қараған кезде не болатынын көрсетеді x в x=x. x 1-күйден және 1-күйге қайта отырып, жоғарғы нүктені салыстыра алады. Немесе x 2-жағдайдан 2-жағдайға өтіп, төмендегі нүктені картаға түсіре алады.
Біріншіге сәйкестендірілгеннен кейін x в x=x біз әлі 1 және 2 күйдеміз. Біз 3 немесе 4 күйге жете алмаймыз, себебі бізге әріптік таңба қажет =.
Содан кейін алгоритм қарастырады = в x=x. Оның алдындағы x сияқты, оны 1-күйден 1-күйге немесе 2-күйден 2-күйге дейінгі жоғарғы екі циклдің кез келгеніне сәйкестендіруге болады, бірақ алгоритм литералды мәнге сәйкес келуі мүмкін. = және 2 күйден 3 күйге (және бірден 4) ауысыңыз. Бұл суретте көрсетілген. 3.
Содан кейін алгоритм соңғысына көшеді x в x=x. 1 және 2 күйлерден 1 және 2 күйлерге бірдей ауысулар мүмкін. 3 күйден x оң жақтағы нүктені сәйкестендіре алады және 3 күйге оралады.
Бұл кезеңде әрбір кейіпкер x=x қарастырылады және біз 4-күйге жеткендіктен, тұрақты өрнек сол жолға сәйкес келеді. Әрбір таңба бір рет өңделеді, сондықтан бұл алгоритм енгізу жолының ұзындығы бойынша сызықтық болады. Және кері қайтару жоқ.
Әлбетте, 4-күйге жеткеннен кейін (алгоритм сәйкес келген кезде x=) бүкіл тұрақты өрнек сәйкес келеді және алгоритм оны мүлде қарастырмай аяқталуы мүмкін x.
Бұл алгоритм енгізу жолының өлшеміне сызықтық тәуелді.
Ақпарат көзі: www.habr.com