تفاصيل تحطم 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 ، بسبب ذلك موارد وحدة المعالجة المركزية تنفد على كل نواة معالج يتعامل مع حركة مرور HTTP / HTTPS على شبكة Cloudflare حول العالم. نعمل باستمرار على تحسين القواعد المُدارة لـ WAF استجابةً لنقاط الضعف والتهديدات الجديدة. في مايو ، على سبيل المثال ، سارعنا أضف القاعدةللحماية من ثغرة أمنية خطيرة في SharePoint. يتمثل جوهر WAF بالكامل في القدرة على نشر القواعد بسرعة وعلى مستوى العالم.

لسوء الحظ ، احتوى تحديث الخميس الماضي على regex يستخدم الكثير من وحدة المعالجة المركزية المخصصة لـ 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 دقيقة لم يكن فقط بسبب تعبير عادي سيء. لقد استغرقنا بعض الوقت لوصف تسلسل الأحداث التي أدت إلى الانهيار ، لذلك لم نرد بسرعة. في نهاية المنشور ، سأصف التراجع بتعبير عادي وأخبرك بما يجب فعله به.

ماذا حدث

لنبدأ بالترتيب. جميع الأوقات هنا بالتوقيت العالمي المنسق.

في الساعة 13:42 ، قام مهندس من فريق جدار الحماية بإجراء تغيير طفيف على قواعد الكشف XSS من خلال عملية تلقائية. وفقًا لذلك ، تم إنشاء بطاقة طلب التغيير. ندير مثل هذه التذاكر من خلال Jira (لقطة الشاشة أدناه).

بعد 3 دقائق ، ظهرت الصفحة الأولى من PagerDuty ، للإبلاغ عن مشكلة في WAF. كان هذا معيارًا اصطناعيًا يختبر وظائف WAFs (لدينا المئات منها) خارج Cloudflare للتحقق من التشغيل العادي. تبع ذلك على الفور صفحات من إخفاقات الاختبارات الشاملة الأخرى لخدمات Cloudflare ، ومشكلات حركة المرور العالمية ، وأخطاء 502 واسعة الانتشار ، ومجموعة من التقارير من نقاط تواجدنا (PoP) في مدن حول العالم والتي أشارت إلى وجود نقص. من موارد المعالج.

تلقيت عددًا قليلاً من هذه التنبيهات ، وخرجت من الاجتماع ، وكنت في طريقي إلى الطاولة عندما قال قائد تطوير الحلول لدينا أننا فقدنا 80٪ من حركة المرور لدينا. ركضت إلى مهندسي SRE الذين كانوا يعملون بالفعل على حل المشكلة. في البداية اعتقدنا أنه هجوم غير معروف.

ينتشر مهندسو Cloudflare SRE في جميع أنحاء العالم ويراقبون الوضع على مدار الساعة. عادةً ما تُعلم هذه التنبيهات بمشكلات محلية محددة ذات نطاق محدود ، ويتم تعقبها على لوحات المعلومات الداخلية ، ويتم حلها عدة مرات في اليوم. لكن مثل هذه الصفحات والإشعارات أشارت إلى شيء خطير حقًا ، وأعلن مهندسو SRE على الفور مستوى خطورة P0 وتحولوا إلى مهندسي الإدارة والأنظمة.

كان مهندسو لندن في تلك اللحظة يستمعون إلى محاضرة في القاعة الرئيسية. كان لا بد من مقاطعة المحاضرة ، وتجمع الجميع في غرفة اجتماعات كبيرة ، وتم استدعاء المزيد من المتخصصين. لم تكن هذه مشكلة شائعة يمكن أن تتعامل معها SREs بمفردها. كان من الضروري الاتصال بشكل عاجل بالمتخصصين المناسبين.

في الساعة 14:00 قررنا أن هناك مشكلة مع WAF ولم يكن هناك هجوم. استخرج قسم الأداء بيانات المعالج ، وأصبح من الواضح أن WAF هو المسؤول. موظف آخر أكد هذه النظرية بصرامة. رأى شخص آخر في السجلات أن هناك مشكلة في WAF. في الساعة 14:02 مساءً ، أتى الفريق بأكمله إلي عندما تم اقتراح استخدام القتل الشامل - آلية مدمجة في Cloudflare تعطل مكونًا واحدًا في جميع أنحاء العالم.

كيف قمنا بقتل عالمي لـ WAF هي قصة مختلفة. انه ليس بتلك البساطة. نحن نستخدم منتجاتنا الخاصة ، ومنذ خدمتنا الوصول للتعاليم لم تنجح ، لم نتمكن من المصادقة وتسجيل الدخول إلى لوحة التحكم الداخلية (عندما تم إصلاح كل شيء ، علمنا أن بعض أعضاء الفريق فقدوا الوصول بسبب ميزة الأمان التي تعطل بيانات الاعتماد إذا لم يتم استخدام لوحة التحكم الداخلية لفترة طويلة) .

ولم نتمكن من الوصول إلى خدماتنا الداخلية مثل Jira أو نظام البناء. كانت هناك حاجة إلى حل بديل ، والذي استخدمناه بشكل غير متكرر (سيحتاج هذا أيضًا إلى حل). أخيرًا ، تمكن أحد المهندسين من قطع WAF في الساعة 14:07 مساءً ، وفي الساعة 14:09 مساءً ، عادت حركة المرور ومستويات المعالج إلى طبيعتها في كل مكان. عملت بقية آليات أمان Cloudflare كالمعتاد.

ثم بدأنا في استعادة WAF. كان الوضع خارجًا عن المألوف ، لذلك أجرينا اختبارات سلبية (سألنا أنفسنا ما إذا كان هذا التغيير هو المشكلة حقًا) واختبارات إيجابية (للتأكد من نجاح التراجع) في مدينة واحدة بحركة مرور منفصلة ، ونقل العملاء المدفوعين من هناك.

في الساعة 14:52 تأكدنا من فهمنا للسبب وقمنا بتصحيحه ، وأعدنا تشغيل WAF.

كيف يعمل Cloudflare

لدى Cloudflare فريق من المهندسين مكرس للقواعد المُدارة لـ WAF. إنهم يسعون جاهدين لتحسين معدلات الاكتشاف ، وتقليل الإيجابيات الكاذبة ، والاستجابة بسرعة للتهديدات الجديدة عند ظهورها. في الأيام الستين الماضية ، تمت معالجة 60 طلبًا لتغيير القواعد المُدارة لـ WAF (في المتوسط ​​، طلب واحد كل 476 ساعات).

يجب نشر هذا التغيير المحدد في وضع المحاكاة ، حيث تمر حركة مرور العميل الحقيقية من خلال القاعدة ، ولكن لا يتم حظر أي شيء. نستخدم هذا الوضع لاختبار فعالية القواعد ولقياس نسبة الإيجابيات الكاذبة والسلبيات الكاذبة. ولكن حتى في وضع المحاكاة ، يجب تنفيذ القواعد فعليًا ، وفي هذه الحالة ، احتوت القاعدة على تعبير عادي استهلك الكثير من موارد المعالج.

كما ترى من طلب التغيير أعلاه ، لدينا خطة نشر وخطة تراجع ورابط لإجراء تشغيل قياسي داخلي (SOP) لهذا النوع من النشر. يسمح الإجراء التشغيلي الموحد الخاص بتعديل القاعدة بنشرها عالميًا. في الواقع ، في Cloudflare ، يتم ترتيب كل شيء بشكل مختلف تمامًا ، ويوجه SOP أولاً إرسال البرنامج للاختبار والاستخدام الداخلي إلى نقطة التواجد الداخلية (PoP) (التي يستخدمها موظفونا) ، ثم إلى عدد صغير من العملاء في مكان منعزل ، ثم لعدد كبير من العملاء ، وعندها فقط حول العالم.

هذا ما يبدو عليه. نستخدم git داخليًا عبر BitBucket. يقوم المهندسون الذين يعملون على التغييرات بإرسال التعليمات البرمجية التي تم إنشاؤها إلى TeamCity ، وعندما يمر الإصدار ، يتم تعيين المراجعين. عند الموافقة على طلب السحب ، يتم تجميع الكود وتشغيل سلسلة من الاختبارات (مرة أخرى).

إذا اكتمل البناء والاختبارات بنجاح ، يتم إنشاء طلب تغيير في Jira ويجب الموافقة على التغيير من قبل المدير أو العميل المتوقع المناسب. بمجرد الموافقة عليه ، يتم نشره في ما يسمى "PoP menagerie": DOG و PIG و كناري (الكلب والخنزير والكناري).

DOG PoP هو Cloudflare PoP (تمامًا مثل أي مدينة أخرى في مدننا) يستخدمه موظفو Cloudflare فقط. يتيح لك PoP للاستخدام الداخلي اكتشاف المشكلات حتى قبل أن تبدأ حركة مرور العملاء في الدخول إلى الحل. شيء مفيد.

إذا نجح اختبار DOG ، ينتقل الكود إلى مرحلة PIG (خنزير غينيا). هذا هو Cloudflare PoP ، حيث يمر قدر صغير من حركة مرور العميل المجانية عبر الكود الجديد.
إذا كان كل شيء على ما يرام ، فإن الكود يذهب إلى Canary. لدينا ثلاث نقاط اتصال من جزر الكناري في أجزاء مختلفة من العالم. في نفوسهم ، تمر حركة العملاء المدفوعة والمجانية عبر الكود الجديد ، وهذا هو آخر فحص للأخطاء.

عملية إصدار البرنامج في Cloudflare

إذا كان الرمز على ما يرام في Canary ، فسنطلقه. يستغرق المرور عبر جميع المراحل - DOG و PIG و Canary والعالم بأسره - عدة ساعات أو أيام ، اعتمادًا على تغيير الرمز. نظرًا لتنوع شبكة Cloudflare وعملائها ، فإننا نختبر الكود جيدًا قبل إصدار عالمي لجميع العملاء. لكن WAF على وجه التحديد لا تتبع هذه العملية لأن التهديدات تحتاج إلى التعامل معها بسرعة.

تهديدات WAF
في السنوات القليلة الماضية ، كانت هناك زيادة كبيرة في التهديدات للتطبيقات العادية. هذا يرجع إلى زيادة توافر أدوات اختبار البرامج. على سبيل المثال ، كتبنا مؤخرًا عن التشويش).

المصدر: https://cvedetails.com/

في كثير من الأحيان ، يتم إنشاء إثبات المفهوم ونشره على الفور على Github حتى تتمكن الفرق التي تحافظ على التطبيق من اختباره بسرعة والتأكد من تأمينه بشكل كافٍ. لذلك ، يجب أن تكون Cloudflare قادرة على الاستجابة للهجمات الجديدة بأسرع ما يمكن حتى تتاح للعملاء فرصة إصلاح برامجهم.

أحد الأمثلة الرائعة للاستجابة السريعة من Cloudflare هو طرح الحماية ضد ثغرة أمنية في SharePoint في مايو (قراءة هنا). فور نشر الإعلانات تقريبًا ، لاحظنا عددًا كبيرًا من المحاولات لاستغلال الثغرة الأمنية في عمليات تثبيت SharePoint الخاصة بعملائنا. يراقب رجالنا باستمرار التهديدات الجديدة ويكتبون القواعد لحماية عملائنا.

كان من المفترض أن تحمي القاعدة التي تسببت في المشكلة يوم الخميس من البرمجة النصية عبر المواقع (XSS). كما أصبحت مثل هذه الهجمات أكثر بكثير في السنوات الأخيرة.

المصدر: https://cvedetails.com/

الإجراء القياسي لتعديل قاعدة مُدارة WAF هو اختبار التكامل المستمر (CI) قبل النشر العالمي. لقد فعلنا ذلك يوم الخميس الماضي وطرحنا القواعد. في الساعة 13:31 ، قدم أحد المهندسين طلب سحب معتمد مع تغيير.

في تمام الساعة 13:37 ، جمعت TeamCity القواعد وأجرى الاختبارات وأعطت الضوء الأخضر. تختبر مجموعة اختبار WAF الوظائف الأساسية لـ WAF وتتكون من عدد كبير من اختبارات الوحدة للوظائف الفردية. بعد اختبار الوحدة ، اختبرنا قواعد WAF بعدد كبير من طلبات HTTP. تتحقق طلبات HTTP من الطلبات التي يجب حظرها بواسطة WAF (من أجل اعتراض الهجوم) وأي الطلبات يجب السماح لها بالمرور (من أجل عدم حظر كل شيء على التوالي وتجنب الإيجابيات الخاطئة). لكننا لم نجري اختبارات للاستخدام المفرط لوحدة المعالجة المركزية ، ويظهر النظر في السجلات من إصدارات WAF السابقة أن الوقت اللازم لإجراء الاختبارات وفقًا للقاعدة لم يزد ، ومن الصعب الشك في عدم توفر موارد كافية .

اجتازت الاختبارات وبدأت TeamCity في نشر التغيير تلقائيًا في الساعة 13:42.

زئبق

تم تصميم قواعد WAF للتعامل مع التهديدات بسرعة ، وهذا هو السبب في أننا ننشرها باستخدام مخزن قيمة المفتاح الموزع الخاص بـ Quicksilver ، والذي ينشر التغييرات عالميًا في ثوانٍ. يستخدم جميع عملائنا هذه التقنية عندما يغيرون التكوين على لوحة القيادة أو من خلال واجهة برمجة التطبيقات ، وبفضلها نستجيب للتغييرات بسرعة البرق.

لم نتحدث كثيرًا عن Quicksilver. استخدمنا سابقا كيوتو تايكون كمتجر ذي قيمة مفاتيح موزع عالميًا ، لكنه واجه مشاكل تشغيلية وكتبنا متجرنا الخاص الذي تم نسخه في أكثر من 180 مدينة. نحن الآن نستخدم Quicksilver لدفع تغييرات التكوين إلى العملاء ، وتحديث قواعد WAF ، وتوزيع JavaScript المكتوب من قبل العميل على Cloudflare Workers.

من النقر فوق زر في لوحة المعلومات أو استدعاء واجهة برمجة التطبيقات لإجراء تغيير في التكوين حول العالم ، يستغرق الأمر بضع ثوانٍ فقط. يحب العملاء سرعة الإعداد هذه. ويوفر لهم العمال نشرًا شبه فوري للبرامج العالمية. في المتوسط ​​، ينشر Quicksilver حوالي 350 تغييرًا في الثانية.

و Quicksilver سريع جدا. في المتوسط ​​، وصلنا إلى النسبة المئوية 99 البالغة 2,29 ثانية لنشر التغييرات على كل جهاز كمبيوتر حول العالم. عادة السرعة جيدة. بعد كل شيء ، عند تشغيل ميزة أو مسح ذاكرة التخزين المؤقت ، يحدث ذلك على الفور تقريبًا وفي كل مكان. يتم إرسال الكود عبر Cloudflare Workers بنفس السرعة. تعد Cloudflare عملاءها بتحديثات سريعة في الوقت المناسب.

لكن في هذه الحالة ، لعبت السرعة خدعة قاسية علينا ، وتغيرت القواعد في كل مكان في غضون ثوانٍ. ربما لاحظت أن كود WAF يستخدم Lua. يستخدم Cloudflare Lua على نطاق واسع في الإنتاج والتفاصيل Lua إلى WAF نحن ناقش بالفعل. يستخدم Lua WAF PCRE في الداخل ويطبق التراجع عن المطابقة. ليس لديها آليات للحماية من التعبيرات الخارجة عن السيطرة. سأخوض في مزيد من التفاصيل حول هذا وما نفعله حيال ذلك أدناه.

قبل نشر القواعد ، كان كل شيء يسير بسلاسة: تم إنشاء طلب سحب والموافقة عليه ، وبناء خط أنابيب CI / CD واختبار الكود ، وتم تقديم طلب التغيير وفقًا لإجراءات التشغيل القياسية التي تحكم النشر والتراجع ، وتم الانتهاء من النشر .

عملية نشر Cloudflare WAF

هناك خطأ ما
كما قلت من قبل ، نطرح العشرات من قواعد WAF الجديدة كل أسبوع ، ولدينا العديد من الأنظمة للحماية من الآثار السلبية لمثل هذا التطبيق. وعندما يحدث خطأ ما ، فإنه عادة ما يكون مزيجًا من عدة ظروف في وقت واحد. إذا وجدت سببًا واحدًا فقط ، فهذا بالطبع مطمئن ، لكنه ليس صحيحًا دائمًا. فيما يلي الأسباب التي أدت معًا إلى فشل خدمة HTTP / HTTPS.

1. كتب المهندس تعبيرا عاديا يمكن أن يؤدي إلى المبالغة التراجع.
2. تمت إزالة الميزة التي كان من الممكن أن تمنع التعبير العادي من الإفراط في استخدام وحدة المعالجة المركزية عن طريق الخطأ في إعادة هيكلة WAF قبل بضعة أسابيع - كانت هناك حاجة إلى إعادة البناء لجعل WAF يستهلك موارد أقل.
3. لم يكن لمحرك التعبير العادي أي ضمانات بالتعقيد.
4. لم تتمكن مجموعة الاختبار من اكتشاف الاستخدام المفرط لوحدة المعالجة المركزية.
5. يسمح الإجراء التشغيلي الموحد بنشر تغييرات القواعد غير العاجلة على مستوى العالم دون الحاجة إلى عملية متعددة الخطوات.
6. تتطلب خطة التراجع بنية WAF كاملة مرتين ، وهي فترة طويلة.
7. جاء أول تنبيه لمشكلة المرور العالمية بعد فوات الأوان.
8. لقد كنا بطيئين في تحديث صفحة الحالة.
9. واجهتنا مشاكل في الوصول إلى الأنظمة بسبب الفشل ولم تتم ممارسة إجراءات التجاوز بشكل جيد.
10. فقدت SREs إمكانية الوصول إلى بعض الأنظمة بسبب انتهاء صلاحية بيانات اعتمادها لأسباب أمنية.
11. لم يتمكن عملاؤنا من الوصول إلى Cloudflare Dashboard أو API لأنهم يمرون عبر منطقة Cloudflare.

ما الذي تغير منذ الخميس الماضي

أولاً ، قمنا بإيقاف جميع الأعمال المتعلقة بإصدارات WAF تمامًا وقمنا بما يلي:

1. إعادة تقديم الحماية ضد الاستهلاك المفرط لموارد المعالج ، والتي قمنا بإزالتها. (مستعد)
2. التحقق يدويًا من جميع القواعد البالغ عددها 3868 في القواعد المُدارة لـ WAF لإيجاد وإصلاح الحالات المحتملة الأخرى للتراجع المفرط. (اكتمل التحقق)
3. قم بتضمين ملف تعريف الأداء لجميع القواعد في مجموعة الاختبار. (متوقع: 19 يوليو)
4. التحول إلى محرك التعبير العادي re2 أو Rust كلاهما يوفر ضمانات في بيئة وقت التشغيل. (متوقع: 31 يوليو)
5. إعادة كتابة SOP لنشر القواعد على مراحل ، مثل البرامج الأخرى في Cloudflare ، ولكن لا يزال بإمكانك نشر الطوارئ على مستوى العالم إذا بدأت الهجمات بالفعل.
6. نحن نعمل على تطوير القدرة على سحب لوحة معلومات Cloudflare وواجهة برمجة التطبيقات بشكل عاجل من منطقة Cloudflare.
7. أتمتة تحديث الصفحة حالة Cloud Flare.

على المدى الطويل ، نحن نبتعد عن Lua WAF الذي كتبته قبل بضع سنوات. نقل WAF إلى نظام جدار الحماية الجديد. لذلك سيكون WAF أسرع وسيحصل على طبقة إضافية من الحماية.

اختتام

تسبب هذا الفشل في مشاكل لنا ولعملائنا. لقد استجبنا بسرعة لتصحيح الموقف ونعمل حاليًا على معالجة العيوب في العمليات التي تسببت في الانهيار ، بالإضافة إلى التعمق أكثر للحماية من مشكلات regex المحتملة في المستقبل من خلال الانتقال إلى التكنولوجيا الجديدة.

نشعر بالخجل الشديد من هذا الفشل ونعتذر لعملائنا. نأمل أن تضمن هذه التغييرات عدم حدوث ذلك مرة أخرى.

طلب. تراجع التعبير العادي

لفهم كيفية التعبير:

(?:(?:"|'|]|}||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 ، عندما كتب كينت طومسون مقالاً تقنيات البرمجة: خوارزمية البحث عن التعبير العادي ("طرق البرمجة: خوارزمية البحث عن التعبير العادي"). تصف المقالة آلية تسمح لك بتحويل تعبير عادي إلى أوتوماتيكية محدودة غير حتمية ، وبعد تغييرات الحالة في أوتوماتيكية محدودة غير حتمية ، استخدم خوارزمية يعتمد وقت تنفيذها خطيًا على السلسلة المتطابقة.

طرق البرمجة
خوارزمية البحث عن التعبير العادي
كين طومسون
مختبرات هاتف بيل ، إنك ، موراي هيل ، نيوجيرسي

يصف هذا طريقة للبحث عن سلسلة محددة من الأحرف في النص ، ويناقش تنفيذ هذه الطريقة في شكل مترجم. يأخذ المحول البرمجي التعبير العادي كرمز مصدر ويقوم بإنشاء برنامج IBM 7094 كرمز كائن. يأخذ برنامج الكائن المدخلات في شكل نص بحث ويبعث إشارة في كل مرة تتطابق سلسلة من النص مع التعبير العادي المحدد. تقدم المقالة أمثلة ومشاكل وحلول.

خوارزمية
أدت خوارزميات البحث السابقة إلى التراجع إذا فشل بحث ناجح جزئيًا.

في وضع الترجمة ، لا تعمل الخوارزمية مع الرموز. يقوم بتمرير التعليمات إلى الكود المترجم. التنفيذ سريع جدًا - بعد تمرير البيانات إلى أعلى القائمة الحالية ، يبحث تلقائيًا عن جميع الأحرف المتتالية الممكنة في التعبير العادي.
يتم تضمين خوارزمية التجميع والبحث في محرر نص مشاركة الوقت كبحث سياقي. بالطبع ، هذا ليس التطبيق الوحيد لإجراء البحث هذا. على سبيل المثال ، يتم استخدام متغير من هذه الخوارزمية كبحث عن رمز في جدول في المجمع.
من المفترض أن القارئ على دراية بالتعابير العادية ولغة البرمجة الخاصة بحاسوب IBM 7094.

مترجم
يتكون المترجم من ثلاث مراحل متوازية. الخطوة الأولى هي تصفية بناء الجملة ، والتي تسمح فقط بالتعبيرات العادية الصحيحة من الناحية النحوية بالمرور. تُدرج هذه الخطوة أيضًا عامل التشغيل "·" لمطابقة التعبيرات العادية. في الخطوة الثانية ، يتم تحويل التعبير النمطي إلى نموذج postfix. في المرحلة الثالثة ، يتم إنشاء رمز الكائن. المرحلتان الأوليان واضحتان ، ولن نتطرق إليهما.

لا تتحدث مقالة طومسون عن الأوتوماتا المحدودة غير المحددة ، لكنها تقوم بعمل جيد في شرح خوارزمية الوقت الخطي وتقديم برنامج ALGOL-60 الذي يولد رمز لغة التجميع لـ IBM 7094. التنفيذ صعب ، لكن الفكرة شديدة بسيط.

مسار البحث الحالي. يتم تمثيله بـ بإدخال واحد ومخرجين.
يوضح الشكل 1 وظائف خطوة الترجمة الثالثة عند تحويل مثال التعبير العادي. الأحرف الثلاثة الأولى في المثال هي أ ، ب ، ج ، ويقوم كل منها بإنشاء إدخال مكدس 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