جزئیات قطعی Cloudflare در 2 ژوئیه 2019

تقریباً 9 سال پیش Cloudflare یک شرکت کوچک بود، و من برای آن کار نکردم، من فقط یک مشتری بودم. یک ماه پس از راه اندازی Cloudflare، یک اعلان دریافت کردم که وب سایت من است jgc.orgبه نظر می رسد DNS کار نمی کند. Cloudflare تغییری در آن ایجاد کرده است بافرهای پروتکلو یک DNS خراب بود.

من بلافاصله به متیو پرینس با عنوان "DNS من کجاست؟" نامه نوشتم و او یک پاسخ طولانی پر از جزئیات فنی را ارسال کرد (کل مکاتبات را اینجا بخوانید) که من پاسخ دادم:

از: جان گراهام-کامینگ
تاریخ: 7 مهر 2010 ساعت 9:14
موضوع: پاسخ: DNS من کجاست؟
به: متیو پرنس

گزارش جالبی بود، ممنون در صورت بروز مشکل حتما تماس خواهم گرفت. وقتی تمام اطلاعات فنی را جمع آوری کردید، احتمالاً ارزش نوشتن یک پست در این مورد را دارد. من فکر می کنم مردم از یک داستان باز و صادقانه لذت خواهند برد. به خصوص اگر نمودارهایی را به آن ضمیمه کنید تا نشان دهید که ترافیک از زمان راه اندازی چگونه رشد کرده است.

من روی سایتم نظارت خوبی دارم و در مورد هر خرابی پیامک دریافت می کنم. پایش نشان می دهد که خرابی از ساعت 13:03:07 تا 14:04:12 رخ داده است. آزمایشات هر پنج دقیقه انجام می شود.

مطمئنم متوجه میشی آیا مطمئن هستید که به شخص خود در اروپا نیاز ندارید؟ 🙂

و او پاسخ داد:

از: متیو پرنس
تاریخ: 7 مهر 2010 ساعت 9:57
موضوع: پاسخ: DNS من کجاست؟
به: جان گراهام-کامینگ

متشکرم. ما به همه کسانی که نوشتند پاسخ دادیم. من اکنون در راه دفتر هستم و چیزی در وبلاگ می نویسیم یا یک پست رسمی را در تابلوی اعلانات خود پین می کنیم. من کاملا موافقم، صداقت همه چیز است.

اکنون Cloudflare یک شرکت واقعاً بزرگ است، من برای آن کار می کنم و اکنون باید آشکارا در مورد اشتباه خود، عواقب آن و اقداماتمان بنویسم.

رویدادهای 2 جولای

در 2 ژوئیه یک قانون جدید در قوانین مدیریت شده برای WAF ها ارائه کردیم که به همین دلیل است منابع CPU در حال اتمام بود در هر هسته پردازنده که ترافیک HTTP/HTTPS را در شبکه Cloudflare در سراسر جهان پردازش می کند. ما دائما در حال بهبود قوانین مدیریت شده برای WAF ها در پاسخ به آسیب پذیری ها و تهدیدات جدید هستیم. مثلاً اردیبهشت ماه عجله داشتیم قانون اضافه کنبرای محافظت در برابر یک آسیب پذیری جدی در شیرپوینت. تمام هدف WAF ما توانایی استقرار سریع و جهانی قوانین است.

متأسفانه، به‌روزرسانی پنج‌شنبه گذشته حاوی یک عبارت معمولی بود که منابع CPU HTTP/HTTPS زیادی را برای عقب‌نشینی تلف می‌کرد. پروکسی اصلی ما، توابع CDN و WAF در نتیجه آسیب دیدند. نمودار نشان می دهد که منابع پردازنده برای ارائه ترافیک HTTP/HTTPS تقریباً به 100٪ در سرورهای شبکه ما می رسد.

استفاده از CPU در یک نقطه از حضور در طول یک حادثه

در نتیجه، مشتریان ما (و مشتریان مشتریان ما) با یک صفحه خطای 502 در دامنه های Cloudflare مواجه شدند. 502 خطا توسط وب سرورهای جلویی Cloudflare ایجاد شد که هنوز هسته های رایگان داشتند اما قادر به برقراری ارتباط با فرآیندهای مدیریت ترافیک HTTP/HTTPS نبودند.

ما می دانیم که این موضوع چقدر برای مشتریان ما ناراحتی ایجاد کرده است. ما به طرز وحشتناکی شرمنده هستیم. و این شکست ما را از برخورد موثر با حادثه باز داشت.

اگر شما یکی از این مشتریان بودید، احتمالاً ترسیده، عصبانی و ناراحت بودید. علاوه بر این، ما یک اختلالات جهانی. مصرف بالای CPU به دلیل یک قانون WAF با عبارت منظم ضعیف بود که منجر به عقب نشینی بیش از حد می شد. این عبارت گناهکار است: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))

در حالی که این به خودی خود جالب است (و در ادامه با جزئیات بیشتر در مورد آن صحبت خواهم کرد)، سرویس Cloudflare به مدت 27 دقیقه از کار افتاد نه تنها به دلیل یک بیان منظم بد. مدتی طول کشید تا توالی وقایعی را که منجر به شکست شد، توصیف کنیم، بنابراین در پاسخ به آن دیر بودیم. در پایان پست، بازگشت به عقب را با یک عبارت معمولی شرح خواهم داد و به شما خواهم گفت که با آن چه کار کنید.

چتو اتفاقلوسь

بیایید به ترتیب شروع کنیم. همه زمان‌ها در اینجا به UTC است.

در ساعت 13:42 بعد از ظهر، یک مهندس در تیم فایروال یک تغییر کوچک در قوانین تشخیص ایجاد کرد. XSS با استفاده از یک فرآیند خودکار بر این اساس، یک بلیط درخواست تغییر ایجاد شد. ما چنین بلیط هایی را از طریق Jira مدیریت می کنیم (تصویر زیر).

پس از 3 دقیقه، صفحه اول PagerDuty ظاهر شد که مشکل WAF را گزارش می کرد. این یک آزمایش مصنوعی بود که عملکرد WAF ها (ما صدها مورد از آنها را داریم) در خارج از Cloudflare برای نظارت بر عملکرد عادی آزمایش می کند. بلافاصله پس از آن صفحاتی از هشدارها در مورد شکست سایر تست‌های سرویس پایان به انتها Cloudflare، مشکلات ترافیکی جهانی، خطاهای گسترده 502 و تعداد زیادی گزارش از نقاط حضور ما (PoP) در شهرهای سراسر جهان منتشر شد که نشان دهنده کمبود بود. از منابع CPU

من چندین مورد از این هشدارها را دریافت کردم، از یک جلسه بیرون آمدم و در حال حرکت به سمت میز بودم که رئیس بخش توسعه راه حل های ما گفت که ما 80 درصد از ترافیک خود را از دست داده ایم. من نزد مهندسان SRE خود دویدم که قبلاً روی مشکل کار می کردند. در ابتدا فکر کردیم که این یک نوع حمله ناشناخته است.

مهندسان Cloudflare SRE در سراسر جهان پراکنده هستند و وضعیت را به صورت شبانه روزی زیر نظر دارند. به طور معمول، این هشدارها شما را از مسائل محلی خاص با دامنه محدود مطلع می کنند، در داشبوردهای داخلی ردیابی می شوند و چندین بار در روز حل می شوند. اما این صفحات و اعلان‌ها نشان‌دهنده چیزی واقعا جدی بود و مهندسان SRE بلافاصله سطح شدت P0 را اعلام کردند و با مهندسین مدیریت و سیستم تماس گرفتند.

مهندسان لندنی ما در آن لحظه در سالن اصلی به سخنرانی گوش می دادند. سخنرانی باید قطع می شد، همه در یک اتاق کنفرانس بزرگ جمع می شدند و متخصصان بیشتری فراخوانده می شدند. این یک مشکل معمولی نبود که SREها بتوانند خودشان با آن مقابله کنند. درگیر کردن متخصصان مناسب ضروری بود.

ساعت 14:00 متوجه شدیم که مشکل از WAF است و حمله ای صورت نگرفته است. تیم عملکرد داده های CPU را جمع آوری کردند و مشخص شد که WAF مقصر است. کارمند دیگری این نظریه را با استفاده از strace تایید کرد. شخص دیگری در لاگ ها دید که مشکلی با WAF وجود دارد. در ساعت 14:02 بعد از ظهر، کل تیم به سراغ من آمدند که پیشنهاد شد از kill global استفاده شود، مکانیزمی که در Cloudflare تعبیه شده است که یک جزء را در سراسر جهان خاموش می کند.

اینکه چگونه برای WAF کشتار جهانی انجام دادیم داستان متفاوتی است. آنقدر ها هم ساده نیست. ما از محصولات خودمان و از آنجایی که خدمات ما استفاده می کنیم دسترسی کار نکرد، نتوانستیم احراز هویت کنیم و وارد کنترل پنل داخلی شویم (وقتی همه چیز درست شد، متوجه شدیم که برخی از اعضای تیم به دلیل یک ویژگی امنیتی که در صورت عدم استفاده از پنل کنترل داخلی برای مدت زمان طولانی).

و ما نتوانستیم به خدمات داخلی خود مانند Jira یا سیستم ساخت دسترسی پیدا کنیم. ما به یک مکانیسم راه حل نیاز داشتیم که به ندرت از آن استفاده می کردیم (این نیز باید بررسی شود). سرانجام، یک مهندس موفق شد WAF را در ساعت 14:07 غیرفعال کند و در ساعت 14:09، سطح ترافیک و CPU در همه جا به حالت عادی بازگشت. بقیه مکانیسم های حفاظتی 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 می شود. ما سه قناری PoP در نقاط مختلف جهان داریم. در آنها، ترافیک مشتریان پولی و رایگان از کد جدید عبور می کند و این آخرین بررسی برای خطا است.

فرآیند انتشار نرم افزار در Cloudflare

اگر کد در قناری اوکی بود، آن را آزاد می کنیم. گذراندن تمام مراحل - DOG، PIG، Canary، کل جهان - بسته به تغییر کد، چندین ساعت یا روز طول می کشد. با توجه به تنوع شبکه و کلاینت های Cloudflare، ما کد را قبل از انتشار جهانی برای همه مشتریان، به طور کامل آزمایش می کنیم. اما WAF به طور خاص از این روند پیروی نمی کند زیرا تهدیدات باید به سرعت پاسخ داده شوند.

تهدیدات WAF
در چند سال گذشته، افزایش قابل توجهی در تهدیدات در برنامه های کاربردی رایج وجود داشته است. این به دلیل در دسترس بودن بیشتر ابزارهای تست نرم افزار است. به عنوان مثال، ما اخیراً در مورد آن نوشتیم گیج شدن).

منبع: https://cvedetails.com/

اغلب اوقات، یک اثبات مفهوم ایجاد می‌شود و بلافاصله در Github منتشر می‌شود تا تیم‌های نگهدارنده برنامه بتوانند به سرعت آن را آزمایش کنند و از ایمن بودن آن اطمینان حاصل کنند. بنابراین، Cloudflare به توانایی پاسخگویی به حملات جدید در سریع ترین زمان ممکن نیاز دارد تا مشتریان این فرصت را داشته باشند که نرم افزار خود را تعمیر کنند.

یک مثال عالی از پاسخ سریع Cloudflare، استقرار محافظت‌های آسیب‌پذیری SharePoint در ماه مه است.در اینجا بخوانید). تقریباً بلافاصله پس از اعلامیه ها، ما متوجه تعداد زیادی تلاش برای سوء استفاده از آسیب پذیری در نصب شیرپوینت مشتریانمان شدیم. بچه های ما دائماً تهدیدات جدید را زیر نظر دارند و قوانینی را برای محافظت از مشتریان خود می نویسند.

قاعده ای که باعث ایجاد مشکل در روز پنجشنبه شد، قرار بود در برابر اسکریپت بین سایتی (XSS) محافظت کند. چنین حملاتی نیز در سال های اخیر بسیار بیشتر شده است.

منبع: https://cvedetails.com/

روش استاندارد برای تغییر یک قانون مدیریت شده برای یک WAF، انجام آزمایش یکپارچه سازی مداوم (CI) قبل از استقرار جهانی است. پنجشنبه گذشته ما این کار را انجام دادیم و قوانین را تنظیم کردیم. در ساعت 13:31 بعد از ظهر، یک مهندس یک درخواست کشش تایید شده با تغییر ارائه کرد.

در ساعت 13:37 تیم سیتی قوانین را جمع آوری کرد، آزمایش هایی را انجام داد و مجوز داد. مجموعه تست WAF عملکرد اصلی WAF را آزمایش می کند و از تعداد زیادی تست واحد برای عملکردهای فردی تشکیل شده است. پس از تست های واحد، قوانین WAF را با استفاده از تعداد زیادی درخواست HTTP آزمایش کردیم. درخواست‌های HTTP بررسی می‌کنند که کدام درخواست‌ها باید توسط WAF مسدود شوند (برای رهگیری حمله) و کدام درخواست‌ها می‌توانند اجازه ورود به آن‌ها را بدهند (تا همه چیز مسدود نشود و از مثبت‌های کاذب جلوگیری شود). اما ما برای استفاده بیش از حد از CPU تست نکردیم و بررسی لاگ‌های ساخت‌های قبلی WAF نشان می‌دهد که زمان اجرای تست قانون افزایش نیافته است و به سختی می‌توان گمان برد که منابع کافی وجود نخواهد داشت.

تست ها با موفقیت پشت سر گذاشتند و تیم سیتی به طور خودکار تغییر را در ساعت 13:42 بعد از ظهر شروع کرد.

جیوه

قوانین WAF بر رفع فوری تهدید تمرکز می کنند، بنابراین ما آنها را با استفاده از ذخیره ارزش کلید توزیع شده Quicksilver که تغییرات را در عرض چند ثانیه در سطح جهانی منتشر می کند، مستقر می کنیم. همه مشتریان ما هنگام تغییر پیکربندی در داشبورد یا از طریق API از این فناوری استفاده می کنند و به لطف آن است که ما به تغییرات با سرعت رعد و برق پاسخ می دهیم.

ما در مورد Quicksilver زیاد صحبت نکرده ایم. قبلا استفاده می کردیم سرمایه دار کیوتو به عنوان یک فروشگاه با ارزش کلیدی توزیع شده در سطح جهانی، اما مشکلات عملیاتی با آن وجود داشت، و ما فروشگاه خود را نوشتیم که در بیش از 180 شهر تکرار شد. ما اکنون از Quicksilver برای اعمال تغییرات پیکربندی به کلاینت ها، به روز رسانی قوانین WAF و توزیع کد جاوا اسکریپت نوشته شده توسط کلاینت ها در Cloudflare Workers استفاده می کنیم.

از کلیک کردن روی یک دکمه روی داشبورد یا فراخوانی یک API تا ایجاد تغییر پیکربندی در سراسر جهان، تنها چند ثانیه طول می‌کشد. مشتریان این سرعت راه اندازی را دوست داشتند. و Workers به ​​آنها استقرار نرم افزار جهانی تقریباً فوری می دهد. به طور متوسط، Quicksilver حدود 350 تغییر در ثانیه منتشر می کند.

و Quicksilver بسیار سریع است. به طور متوسط، ما به صدک 99 2,29 ثانیه ای رسیدیم تا تغییرات را در هر رایانه در سراسر جهان منتشر کنیم. سرعت معمولا چیز خوبی است. از این گذشته، هنگامی که یک تابع را فعال می کنید یا حافظه پنهان را پاک می کنید، تقریباً بلافاصله و در همه جا اتفاق می افتد. ارسال کد از طریق Cloudflare Workers با همان سرعت انجام می شود. Cloudflare به مشتریان خود قول به روز رسانی سریع در زمان مناسب را می دهد.

اما در این مورد، سرعت با ما شوخی بی رحمانه ای کرد و قوانین همه جا در عرض چند ثانیه تغییر کرد. شاید متوجه شده باشید که کد WAF از Lua استفاده می کند. Cloudflare از Lua به طور گسترده در تولید و جزئیات استفاده می کند لوا در WAF ما قبلا بحث شده است. Lua WAF استفاده می کند PCRE به صورت داخلی و برای تطبیق، عقبگرد را اعمال می کند. هیچ مکانیزمی برای محافظت در برابر عباراتی که از کنترل خارج می شوند ندارد. در زیر بیشتر در مورد این و آنچه که در مورد آن انجام می دهیم صحبت خواهم کرد.

قبل از استقرار قوانین، همه چیز به آرامی پیش می رفت: درخواست کشش ایجاد و تأیید شد، خط لوله CI/CD کد را جمع آوری و آزمایش کرد، درخواست تغییر طبق SOP که استقرار و بازگشت را کنترل می کند، ارسال شد و استقرار کامل شد.

فرآیند استقرار WAF Cloudflare

مشکلی پیش آمد
همانطور که گفتم، ما هر هفته ده‌ها قانون جدید WAF را مستقر می‌کنیم و سیستم‌های زیادی برای محافظت در برابر پیامدهای منفی چنین استقراری در اختیار داریم. و هنگامی که مشکلی پیش می آید، معمولاً ترکیبی از چندین شرایط در یک زمان است. اگر فقط یک دلیل بیابید، مطمئناً این اطمینان‌بخش است، اما همیشه درست نیست. اینها دلایلی هستند که با هم منجر به شکست سرویس HTTP/HTTPS ما شدند.

1. یک مهندس یک عبارت منظم نوشت که ممکن است منجر به بیش از حد شود عقب نشینی.
2. ویژگی‌ای که می‌توانست از هدر رفتن بیش از حد CPU در بیان منظم جلوگیری کند، به‌اشتباه در یک بازسازی مجدد WAF چندین هفته قبل حذف شد - بازسازی مجدد برای اینکه WAF منابع کمتری مصرف کند، مورد نیاز بود.
3. موتور بیان منظم هیچ ضمانت پیچیدگی نداشت.
4. مجموعه آزمایشی نتوانست مصرف بیش از حد CPU را تشخیص دهد.
5. SOP اجازه می دهد تا تغییرات غیر فوری قوانین در سطح جهانی بدون فرآیند چند مرحله ای اجرا شود.
6. طرح بازگشت مستلزم اجرای یک ساخت کامل WAF دو بار بود که زمان زیادی طول کشید.
7. اولین هشدار در مورد مشکلات ترافیکی جهانی خیلی دیر اعلام شد.
8. مدتی طول کشید تا صفحه وضعیت را به روز کنیم.
9. ما در دسترسی به سیستم ها به دلیل یک نقص مشکل داشتیم و رویه بای پس به خوبی مشخص نشده بود.
10. مهندسان SRE دسترسی به برخی از سیستم ها را از دست دادند زیرا اعتبار آنها به دلایل امنیتی منقضی شده است.
11. مشتریان ما به داشبورد یا API Cloudflare دسترسی نداشتند زیرا از یک منطقه Cloudflare عبور می کنند.

چه چیزی از پنجشنبه گذشته تغییر کرده است

اول، ما به طور کامل همه کار بر روی نسخه های WAF را متوقف کردیم و کارهای زیر را انجام می دهیم:

1. ما در حال معرفی مجدد حفاظت از استفاده بیش از حد CPU هستیم که حذف کردیم. (آماده)
2. بررسی دستی تمام 3868 قانون در قوانین مدیریت شده برای WAF برای یافتن و اصلاح سایر موارد احتمالی عقب نشینی بیش از حد. (تأیید کامل شد)
3. ما پروفایل عملکرد را برای همه قوانین در مجموعه آزمایشی گنجانده ایم. (مورد پیش بینی: 19 جولای)
4. تغییر به موتور بیان منظم re2 یا زنگ - هر دو تضمین زمان اجرا را ارائه می دهند. (مورد پیش بینی شده: 31 ژوئیه)
5. ما در حال بازنویسی SOP هستیم تا قوانین را مانند سایر نرم‌افزارها در Cloudflare به صورت مرحله‌ای استقرار دهیم، اما در عین حال توانایی استقرار جهانی اضطراری را در صورتی که حملات قبلاً شروع شده باشد، داشته باشیم.
6. ما در حال توسعه توانایی حذف فوری داشبورد Cloudflare و API از منطقه Cloudflare هستیم.
7. به روز رسانی خودکار صفحه وضعیت Cloudflare.

دراز مدت ما از Lua WAF که چند سال پیش نوشتم دور می شویم. انتقال WAF به سیستم فایروال جدید. به این ترتیب WAF سریعتر خواهد بود و سطح حفاظت بیشتری دریافت می کند.

نتیجه

این شکست برای ما و مشتریانمان دردسر ایجاد کرد. ما به سرعت برای اصلاح وضعیت اقدام کردیم و اکنون در حال کار بر روی نقص‌های فرآیندهایی هستیم که باعث سقوط شده است، و همچنین در حال حفاری عمیق‌تر برای محافظت در برابر مشکلات احتمالی با عبارات منظم در آینده هنگام مهاجرت به فناوری جدید هستیم.

ما بابت این قطعی بسیار شرمنده هستیم و از مشتریان خود عذرخواهی می کنیم. امیدواریم این تغییرات تضمین کند که چنین چیزی دیگر تکرار نشود.

کاربرد. عقب نشینی عبارات منظم

برای درک نحوه بیان:

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

تمام منابع CPU را خورده است، شما باید کمی در مورد نحوه عملکرد موتور استاندارد بیان منظم بدانید. مشکل اینجا الگوست .*(?:.*=.*). (?: و مربوطه ) یک گروه غیر گرفتن است (یعنی عبارت داخل پرانتز به عنوان یک عبارت واحد گروه بندی می شود).

در زمینه مصرف بیش از حد CPU، این الگو را می توان به عنوان توصیف کرد .*.*=.*. در این شکل، الگوی غیر ضروری پیچیده به نظر می رسد. اما مهم‌تر از آن، در دنیای واقعی، عباراتی (مانند عبارات پیچیده در قوانین 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::Debugger، که نشان می دهد چگونه مراحل و عقب نشینی رخ می دهد.

این قبلاً کار زیادی است، اما اگر در عوض چه می‌شد 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., Murray Hill, New Jersey

روشی را برای جستجوی رشته خاصی از کاراکترها در متن توصیف می کند و پیاده سازی این روش را در قالب کامپایلر مورد بحث قرار می دهد. کامپایلر عبارت منظم را به عنوان کد منبع می گیرد و برنامه 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.

این الگوریتم به صورت خطی به اندازه رشته ورودی بستگی دارد.

منبع: www.habr.com