Амаль 9 гадоў таму Cloudflare была малюсенькай кампаніяй, а я не працаваў у ёй, быў проста кліентам. Праз месяц пасля запуску Cloudflare я атрымаў апавяшчэнне аб тым, што на маім сайтіку , здаецца, не працуе DNS. У Cloudflare занеслі змену ў , а там быў паламаны DNS.
Я адразу напісаў Мэцью Прынсу (Matthew Prince), азагалоўіўшы ліст «Дзе мой DNS?», а ён даслаў доўгі адказ, поўны тэхнічных падрабязнасьцяў (), на што я адказаў:
Ад: Джон Грэхэм-Камінг
Дата: 7 кастрычніка 2010 года, 9:14
Тэма: Re: Дзе мой DNS?
Каму: Мэцью ПрынсКласная справаздача, дзякуй. Я абавязкова пазваню, калі будуць праблемы. Мусіць, варта напісаць аб гэтым пост, калі збераце ўсю тэхнічную інфу. Думаю, людзям спадабаецца адкрытае і сумленнае апавяданне. Асабліва калі прыкласці да яго графікі, каб паказаць, як вырас трафік пасля запуску.
У мяне на сайце добры маніторынг, і мне прыходзіць SMS аб кожным збоі. Маніторынг паказвае, што збой быў з 13:03:07 да 14:04:12. Тэсты праводзяцца кожныя пяць хвілін.
Упэўнены, вы з усім разбярэцеся. Вам сапраўды не патрэбен свой чалавек у Еўропе? 🙂
А ён адказаў:
Ад: Мэцью Прынс
Дата: 7 кастрычніка 2010 года, 9:57
Тэма: Re: Дзе мой DNS?
Каму: Джон Грэхэм-КамінгДзякуй. Мы адказалі ўсім, хто напісаў. Я зараз еду ў офіс, і мы напішам што-небудзь у блогу або замацуем афіцыйную пасаду на нашай дошцы аб'яваў. Цалкам згодзен, сумленнасць - наша ўсё.
Цяпер Cloudflare — рэальна вялікая кампанія, я працую ў ёй, і цяпер мне даводзіцца адкрыта пісаць пра нашу памылку, яе наступствы і нашы дзеянні.
Падзеі 2 ліпеня
2 ліпеня мы разгарнулі новае правіла ў кіраваных правілах для WAF, з-за якіх на кожным ядры працэсара, які апрацоўвае трафік HTTP/HTTPS у сетцы Cloudflare па ўсім свеце. Мы ўвесь час паляпшаем кіраваныя правілы для WAF у адказ на новыя ўразлівасці і пагрозы. У траўні, напрыклад, мы паспяшаліся , каб абараніцца ад сур'ёзнай уразлівасці ў SharePoint. Уся сутнасць нашага WAF – у магчымасці хуткага і глабальнага разгортвання правілаў.
Нажаль, абнаўленне мінулага чацвярга ўтрымоўвала рэгулярны выраз, якое марнавала на бэктрэкінг занадта шмат працэсарных рэсурсаў, вылучаных для HTTP/HTTPS. Ад гэтага пацярпелі нашыя асноўныя функцыі проксі, CDN і WAF. На графіцы відаць, што працэсарныя рэсурсы для абслугоўвання трафіку HTTP/HTTPS даходзяць амаль да 100% на серверах у нашай сетцы.
Выкарыстанне працэсарных рэсурсаў у адной з кропак прысутнасці падчас інцыдэнту
У выніку нашы кліенты (і кліенты нашых кліентаў) упіраліся ў старонку з памылкай 502 у даменах Cloudflare. Памылкі 502 генераваліся франтальнымі вэб-серверамі Cloudflare, у якіх яшчэ былі вольныя ядры, але яны не маглі звязацца з працэсамі, якія апрацоўваюць трафік HTTP/HTTPS.
Мы ведаем, колькі нязручнасцяў гэта даставіла нашым кліентам. Нам вельмі сорамна. І гэты збой перашкаджаў нам эфектыўна разабрацца з інцыдэнтам.
Калі вы былі адным з такіх кліентаў, вас гэта, мусіць, напалохала, раззлавала і знервавала. Больш за тое, у нас ужо 6 гадоў не было . Высокі выдатак працэсарных рэсурсаў адбыўся з-за аднаго правіла WAF з дрэнна сфармуляваным рэгулярным выразам, якое прывяло да празмернага бэктрэкінгу. Вось вінаваты выраз: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Хоць яно само па сабе цікавае (і ніжэй я раскажу пра яго падрабязней), сэрвіс Cloudflare адсек на 27 хвілін не толькі з-за непрыдатнага рэгулярнага выразы. Нам спатрэбіўся час, каб апісаць паслядоўнасць падзей, якія прывялі да збою, таму мы адказалі няхутка. У канцы посту я апішу бэктрэкінг у рэгулярным выразе і раскажу, што з гэтым рабіць.
Што здарылася
Пачнём па парадку. Увесь час тут пазначана ў UTC.
У 13:42 інжынер з каманды, якая займаецца міжсеткавымі экранамі, унёс невялікія змены ў правілы для выяўлення. з дапамогай аўтаматычнага працэсу. Адпаведна, быў створаны тыкет запыту на змену. Такімі тыкетамі мы кіруем праз Jira (скрыншот ніжэй).
Праз 3 хвіліны з'явілася першая старонка PagerDuty, якая паведамляла аб праблеме з WAF. Гэта быў сінтэтычны тэст, які правярае функцыянальнасць WAF (у нас такіх сотні) за межамі Cloudflare, каб кантраляваць нармальную працу. Затым адразу рушылі ўслед старонкі з абвесткамі аб збоях іншых скразных тэстаў сэрвісаў Cloudflare, глабальных праблемах з трафікам, паўсюдных памылках 502, і куча справаздач з нашых кропак прысутнасці (PoP) у гарадах па ўсім свеце, якія паказвалі на недахоп працэсарных рэсурсаў.
Я атрымаў некалькі такіх апавяшчэнняў, сарваўся з сустрэчы і ўжо ішоў да стала, калі кіраўнік нашага аддзела распрацоўкі рашэнняў сказаў, што мы страцілі 80% трафіку. Я пабег да нашых SRE-інжынераў, які ўжо працавалі над праблемай. Спачатку мы падумалі, што гэта нейкая невядомая атака.
SRE-інжынеры Cloudflare раскіданыя па ўсім свеце і кантралююць сітуацыю кругласутачна. Звычайна такія абвесткі апавяшчаюць аб пэўных лакальных праблемах абмежаванага маштабу, адсочваюцца на ўнутраных панэлях маніторынгу і вырашаюцца шмат разоў за дзень. Але такія старонкі і апавяшчэнні паказвалі на нешта рэальна сур'ёзнае, і SRE-інжынеры адразу абвясцілі ўзровень сур'ёзнасці P0 і звярнуліся да кіраўніцтва і сістэмным інжынерам.
Нашы лонданскія інжынеры ў гэты момант слухалі лекцыю ў галоўнай зале. Лекцыю прыйшлося перапыніць, усе сабраліся ў вялікай канферэнц-зале, паклікалі яшчэ адмыслоўцаў. Гэта не была звычайная праблема, зь якой SRE маглі разабрацца самі. Трэба было тэрмінова падлучаць правільных спяцоў.
У 14:00 мы вызначылі, што праблема з WAF і ніякага нападу няма. Аддзел прадукцыйнасці дастаў дадзеныя аб працэсарах, і стала відавочна, што вінаваты WAF. Іншы супрацоўнік пацвердзіў гэтую тэорыю з дапамогай strace. Яшчэ нехта ўбачыў у логах, што з WAF бяда. У 14:02 уся каманда з'явілася да мяне, калі было прапанавана выкарыстоўваць global kill - механізм, убудаваны ў Cloudflare, які адключае адзін кампанент па ўсім свеце.
Як мы зрабілі global kill для WAF – гэта асобная гісторыя. Усё не так проста. Мы выкарыстоўваем уласныя прадукты, а раз наш сэрвіс не працаваў, мы не маглі прайсці аўтэнтыфікацыю і ўвайсці ў панэль унутранага кантролю (калі ўсё паправілася, мы даведаліся, што некаторыя члены каманды страцілі доступ з-за функцыі бяспекі, якая адключае уліковыя дадзеныя, калі доўга не выкарыстоўваць панэль унутранага кантролю).
І мы не маглі дабрацца да сваіх унутраных сэрвісаў, накшталт Jira ці сістэмы зборкі. Патрэбны быў абыходны механізм, які мы выкарыстоўвалі нячаста (гэта таксама трэба будзе адпрацаваць). Нарэшце, аднаму інжынеру ўдалося адсекчы WAF у 14:07, а ў 14:09 узровень трафіку і працэсара ўсюды вярнуўся ў норму. Астатнія ахоўныя механізмы Cloudflare працавалі ў штатным рэжыме.
Затым мы заняліся аднаўленнем працы WAF. Сітуацыя была з шэрагу прэч, таму мы выканалі негатыўныя тэсты (спытаўшы сябе, ці сапраўды праблема ў гэтай змене) і пазітыўныя (пераканаўшыся, што адкат спрацаваў) у адным горадзе з дапамогай асобнага трафіку, перанёсшы адтуль платных кліентаў.
У 14:52 мы пераканаліся, што зразумелі прычыну і ўнеслі выпраўленне, і зноў уключылі WAF.
Як працуе Cloudflare
У Cloudflare ёсць каманда інжынераў, якія займаюцца кіраванымі правіламі для WAF. Яны імкнуцца павысіць працэнт выяўлення, скараціць колькасць прытворнададатных вынікаў і хутка рэагаваць на новыя пагрозы па меры іх з'яўлення. За апошнія 60 дзён было апрацавана 476 запытаў на змены для кіраваных правіл для WAF (у сярэднім, па адным кожныя 3 гадзіны).
Гэтая канкрэтная змена трэба было разгарнуць у рэжыме сімуляцыі, дзе рэальны трафік кліента праходзіць праз правіла, але нічога не блакуецца. Мы выкарыстоўваем гэты рэжым для праверкі эфектыўнасці правілаў і вымярэння долі прытворнададатных і ілжываадмоўных вынікаў. Але нават у рэжыме сімуляцыі правілы павінны фактычна выконвацца, а ў гэтым выпадку правіла ўтрымоўвала рэгулярнае выраз, якое спажывала занадта шмат працэсарных рэсурсаў.
Як відаць з запыту на змену вышэй, у нас ёсць план разгортвання, план адкату і спасылка на ўнутраную стандартную працоўную працэдуру (SOP) для гэтага тыпу разгортвання. SOP для змены правіла дазваляе публікаваць яго глабальна. Наогул-то ў Cloudflare усё ўладкована зусім інакш, і SOP загадвае спачатку адправіць ПА на тэставанне і ўнутранае выкарыстанне ва ўнутраную кропку прысутнасці (PoP) (якую выкарыстоўваюць нашы супрацоўнікі), потым невялікай колькасці кліентаў у ізаляваным месцы, потым вялікай колькасці кліентаў і толькі потым ўсім свеце.
Вось як гэта выглядае. Мы выкарыстоўваем git ва ўнутранай сістэме праз BitBucket. Інжынеры, якія працуюць над зменамі, адпраўляюць код, які збіраецца ў TeamCity, і калі зборка праходзіць, прызначаюцца рэўюеры. Калі пул-рэквест ухваляецца, код збіраецца і праводзіцца шэраг тэстаў (яшчэ раз).
Калі зборка і тэсты завяршаюцца паспяхова, ствараецца запыт на змену ў Jira, і змена павінен ухваліць адпаведны кіраўнік або вядучы спецыяліст. Пасля адабрэння адбываецца разгортванне ў так званы "PoP-звярынец": DOG, PIG і (сабака, свінка і канарэйка).
DOG PoP - гэта Cloudflare PoP (як любы іншы з нашых гарадоў), які выкарыстоўваюць толькі супрацоўнікі Cloudflare. PoP для ўнутранага выкарыстання дазваляе вылавіць праблемы яшчэ да таго, як у рашэнне пачне паступаць трафік кліентаў. Карысная штука.
Калі DOG-тэст праходзіць паспяхова, код пераходзіць на стадыю PIG (паддоследная свінка). Гэта Cloudflare PoP, дзе невялікі аб'ём трафіку бясплатных кліентаў праходзіць праз новы код.
Калі ўсё добра, код пераходзіць у Canary. У нас тры Canary PoP у розных кропках свету. У іх праз новы код праходзіць трафік платных і бясплатных кліентаў, і гэта апошняя праверка на памылкі.
Працэс рэлізу ПЗ у Cloudflare
Калі з кодам усё нармальна ў Canary, мы яго выпускаем. Праходжанне праз усе стадыі - DOG, PIG, Canary, увесь свет - займае некалькі гадзін або дзён, у залежнасці ад змены кода. Дзякуючы разнастайнасці сеткі і кліентаў Cloudflare мы старанна тэсціруем код перад глабальным рэлізам для ўсіх кліентаў. Але WAF спецыяльна не прытрымліваецца гэтага працэсу, таму што на пагрозы трэба рэагаваць хутка.
Пагрозы WAF
У апошнія некалькі гадоў у звычайных дадатках пагроз стала значна больш. Гэта звязана з большай даступнасцю інструментаў тэсціравання ПЗ. Напрыклад, нядаўна мы пісалі пра ).
Крыніца:
Вельмі часта пацверджанне канцэпцыі ствараецца і тут жа публікуецца на Github, каб каманды, якія абслугоўваюць дадатак, маглі хутка пратэставаць яго і пераканацца, што яно адэкватна абаронена. Таму Cloudflare патрэбна магчымасць як мага хутчэй рэагаваць на новыя напады, каб у кліентаў была магчымасць выправіць сваё ПЗ.
Выдатны прыклад хуткай рэакцыі ад Cloudflare - разгортванне сродкаў абароны ад уразлівасці SharePoint у траўні (). Амаль адразу пасля публікацыі аб'яваў мы заўважылі вялікую колькасць спроб выкарыстоўваць уразлівасць ва ўсталёўках SharePoint нашых кліентаў. Нашы хлопцы ўвесь час адсочваюць новыя пагрозы і пішуць правілы, каб абараніць нашых кліентаў.
Правіла, з-за якога ў чацвер узнікла праблема, павінна было абараняць ад міжсайтавага скрыптынгу (XSS). Такіх нападаў таксама стала куды больш за апошнія гады.
Крыніца:
Стандартная працэдура для змены кіраванага правіла для WAF загадвае праводзіць тэставанне бесперапыннай інтэграцыі (CI) да глабальнага разгортвання. У мінулы чацвер мы гэта зрабілі і разгарнулі правілы. У 13:31 адзін інжынер адправіў ухвалены пул-рэквест са зменай.
У 13:37 TeamCity сабраў правілы, прагнаў тэсты і даў дабро. Набор тэстаў для WAF правярае асноўны функцыянал WAF і складаецца з вялікай колькасці модульных тэстаў для індывідуальных функцый. Пасля модульных тэстаў мы праверылі правілы для WAF з дапамогай вялікай колькасці HTTP-запытаў. HTTP-запыты правяраюць, якія запыты павінны блакавацца WAF (каб перахапіць атаку), а якія можна прапускаць (каб не блакаваць усё запар і пазбегнуць прытворнададатных вынікаў). Але мы не правялі тэсты на празмернае выкарыстанне працэсарных рэсурсаў, і вывучэнне логаў папярэдніх зборак WAF паказвае, што час выканання тэстаў з правілам не павялічылася, і складана было западозрыць, што рэсурсаў не хопіць.
Тэсты былі пройдзеныя, і TeamCity пачаў аўтаматычна разгортваць змену ў 13:42.
Ртуць
Правілы 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, якая рэгулюе разгортванне і адкат, і разгортванне было выканана.
Працэс разгортвання WAF у Cloudflare
Што пайшло не так
Як я ўжо казаў, мы кожны тыдзень разгортваем дзясяткі новых правіл WAF, і ў нас ёсць мноства сістэм абароны ад негатыўных наступстваў такога разгортвання. І калі нешта ідзе не так, звычайна гэты збег адразу некалькіх абставін. Калі знайсці ўсяго адзін чыннік, гэта, вядома супакойвае, але не заўсёды адпавядае рэчаіснасці. Вось прычыны, якія разам прывялі да збою нашага сервісу HTTP/HTTPS.
- Інжынер напісаў рэгулярны выраз, які можа прывесці да празмернага .
- Сродак, які мог бы прадухіліць празмерны выдатак працэсарных рэсурсаў, якія выкарыстоўваюцца рэгулярным выразам, быў памылкова выдалены пры рэфактарынгу WAF за некалькі тыдняў да гэтага — рэфакторынг быў патрэбны, каб WAF спажываў менш рэсурсаў.
- Рухавічок рэгулярных выразаў не меў гарантый складанасці.
- Набор тэстаў не мог выявіць празмернае спажыванне працэсарных рэсурсаў.
- Працэдура SOP дазваляе глабальнае разгортванне нетэрміновых змен правіл без шматэтапнага працэсу.
- План адкату патрабаваў выкананне поўнай зборкі WAF двойчы, а гэта доўга.
- Першае апавяшчэнне аб глабальных праблемах з трафікам спрацавала занадта позна.
- Мы прамарудзілі з абнаўленнем старонкі статуту.
- У нас былі праблемы з доступам да сістэм з-за збою, а працэдура абыходу была недастаткова добра адпрацаваная.
- SRE-інжынеры страцілі доступ да некаторых сістэм, таму што тэрмін дзеяння іх уліковых дадзеных скончыўся па меркаваннях бяспекі.
- У нашых кліентаў не было доступу да панэлі маніторынгу Cloudflare ці API, таму што яны праходзяць праз рэгіён Cloudflare.
Што змянілася з мінулага чацвярга
Спачатку мы цалкам спынілі ўсе працы над рэлізамі для WAF і які робіцца наступнае:
- Паўторна ўводзім абарону ад празмернага спажывання працэсарных рэсурсаў, якую мы выдалілі. (Гатова)
- Уручную правяраем усе 3868 правілаў у кіраваных правілах для WAF, каб знайсці і выправіць іншыя патэнцыйныя выпадкі празмернага бэктрэкінга. (Праверка завершана)
- Уключаем у набор тэстаў прафіляванне прадукцыйнасці для ўсіх правіл. (Чакаецца: 19 ліпеня)
- Пераходзім на рухавічок рэгулярных выразаў або - Абодва падаюць гарантыі ў асяроддзі выканання. (Чакаецца: 31 ліпеня)
- Перапісваем SOP, каб разгортваць правілы паэтапна, як і іншае ПЗ у Cloudflare, але пры гэтым мець магчымасць экстранага глабальнага разгортвання, калі напады ўжо пачаліся.
- Распрацоўваем магчымасць тэрміновай вываду панэлі маніторынгу Cloudflare і API з рэгіёну Cloudflare.
- Аўтаматызуем абнаўленне старонкі .
У доўгатэрміновай перспектыве мы адмаўляемся ад Lua 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 года, калі Кент Томпсан напісаў артыкул («Метады праграмавання: алгарытм пошуку рэгулярных выразаў»). У артыкуле апісаны механізм, якія дазваляе пераўтварыць рэгулярны выраз у недэтэрмінаваныя канчатковыя аўтаматы, а пасля змен стану ў недэтэрмінаваных канчатковых аўтаматах выкарыстоўваць алгарытм, час выканання якога лінейна залежыць ад супастаўляемага радка.
Метады праграмавання
Алгарытм пошуку рэгулярных выразаў
Кен Томпсан (Ken Thompson)
Bell Telephone Laboratories, Inc., Мюрэй-Хіл, штат Нью-ДжэрсіТут апісваецца метад пошуку вызначанага радка знакаў у тэксце і абмяркоўваецца рэалізацыя гэтага метаду ў форме кампілятара. Кампілятар прымае рэгулярны выраз у якасці зыходнага кода і стварае праграму для IBM 7094 у якасці аб'ектнага кода. Аб'ектная праграма прымае ўваходныя дадзеныя ў выглядзе тэксту для пошуку і падае сігнал кожны раз, калі радок з тэксту супастаўляецца з зададзеным рэгулярным выразам. У артыкуле прыводзяцца прыклады, праблемы і рашэнні.
Алгарытм
Папярэднія алгарытмы пошуку прыводзілі да бэктрэкінгу, калі часткова паспяховы пошук не даваў выніку.У рэжыме кампіляцыі алгарытм працуе не са знакамі. Ён перадае інструкцыі ў кампіляваны код. Выкананне адбываецца вельмі хутка - пасля перадачы дадзеных у верхнюю частку бягучага спісу аўтаматычна выконваецца пошук усіх магчымых паслядоўных знакаў у рэгулярным выразе.
Алгарытм кампіляцыі і пошуку ўключаны ў тэкставы рэдактар з падзелам часу як кантэкстны пошук. Зразумела, гэта далёка не адзінае ўжыванне падобнай працэдуры пошуку. Напрыклад, варыянт гэтага алгарытму выкарыстоўваецца як пошук сімвалаў па табліцы ў асэмблеры.
Мяркуецца, што чытач знаёмы з рэгулярнымі выразамі і мовай праграмавання кампутара IBM 7094.Кампілятар
Кампілятар складаецца з трох раўналежна выкананых этапаў. Першы этап - фільтраванне па сінтаксісе, якая прапускае толькі сінтаксічна правільныя рэгулярныя выразы. На гэтым этапе таксама ўстаўляецца аператар "·" для супастаўлення рэгулярных выразаў. На другім этапе рэгулярнае выраз пераўтворыцца ў постфіксную форму. На трэцім этапе ствараецца аб'ектны код. Першыя 2 этапы відавочныя, і мы не будзем на іх спыняцца.
У артыкуле Томпсана не гаворыцца аб недэтэрмінаваных канчатковых аўтаматах, але добра растлумачаны алгарытм лінейнага часу і прадстаўлена праграма на ALGOL-60, якая стварае код мовы зборкі для IBM 7094. Рэалізацыя складаная, але сама ідэя вельмі простая.
бягучы шлях пошуку. Ён прадстаўлены значком ⊕ з адным уваходам і двума выхадамі.
На малюнку 1 паказаны функцыі трэцяга этапа кампіляцыі пры пераўтварэнні прыкладу рэгулярнага выразы. Першыя тры знакі ў прыкладзе — a, b, c, і кожны стварае стэкавы запіс S[i] і поле NNODE.NNODE да існага кода, каб згенераваць выніковае рэгулярнае выраз у адзіным стэкавым запісе (гл. мал. 5)
Вось як выглядала б рэгулярны выраз .*.*=.*, калі ўявіць яго, як на карцінках з артыкула Томпсана.
На мал. 0 ёсць пяць станаў, пачынаючы з 0, і 3 цыклу, якія пачынаюцца з станаў 1, 2 і 3. Гэтыя тры цыклы адпавядаюць тром .* у рэгулярным выразе. 3 авала з кропкамі адпавядаюць аднаму сімвалу. Авал са знакам = адпавядае літаральнаму сімвалу =. Стан 4 з'яўляецца канчатковым. Калі мы яго дасягнулі, значыць рэгулярны выраз супастаўлены.
Каб убачыць, як такую дыяграму станаў можна выкарыстоўваць для супастаўлення рэгулярнага выразы .*.*=.*, мы разгледзім супастаўленне радка x=x. Праграма пачынаецца са стану 0, як паказана на мал. 1.
Каб гэты алгарытм працаваў, канчатковая машына павінна знаходзіцца ў некалькіх станах адначасова. Недэтэрмінаваны канчатковы аўтамат зробіць усе магчымыя пераходы адначасова.
Яшчэ не паспеўшы лічыць уваходныя дадзеныя, ён пераходзіць у абодва першых станы (1 і 2), як паказана на мал. 2.
На мал. 2 відаць, што адбываецца, калі ён разглядае першы x в x=x. x можа супаставіцца з верхняй кропкай, перайшоўшы са стану 1 і назад у стан 1. Або x можа супаставіцца з кропкай ніжэй, перайшоўшы са стану 2 і назад у стан 2.
Пасля супастаўлення першага x в x=x мы па-ранейшаму ў станах 1 і 2. Мы не можам дасягнуць стану 3 ці 4, таму што нам патрэбен літаральны сімвал =.
Затым алгарытм разглядае = в x=x. Як і x да гэтага, яго можна супаставіць з любым з двух верхніх цыклаў з пераходам са стану 1 і ў стан 1 ці са стану 2 у стан 2, але пры гэтым алгарытм можа супаставіць літаральнае = і перайсці са стан 2 у стан 3 (і адразу 4). Гэта паказана на мал. 3.
Затым алгарытм пераходзіць да апошняга x в x=x. Са станаў 1 і 2 тыя ж пераходы магчымыя назад у станы 1 і 2. Са стану 3 x можа супаставіцца з кропкай справа і перайсці назад у стан 3.
На гэтым этапе кожны сімвал x=x разгледжаны, а раз мы дасягнулі стану 4, рэгулярнае выраз адпавядае гэтым радку. Кожны сімвал апрацаваны адзін раз, так што гэты алгарытм лінейна залежыць ад даўжыні ўваходнага радка. І ніякага бэктрэкінгу.
Відавочна, што пасля дасягнення стану 4 (калі алгарытм супаставіў x=) усё рэгулярнае выраз супастаўлена, і алгарытм можа завяршыцца, наогул не разглядаючы x.
Гэты алгарытм лінейна залежыць ад памеру ўваходнага радка.
Крыніца: habr.com