تفاصيل تعطل Cloudflare 2 يوليو 2019

منذ ما يقرب من 9 سنوات ، كانت Cloudflare شركة صغيرة ، لكنني لم أعمل فيها ، كنت مجرد عميل. بعد شهر من إطلاق Cloudflare ، تلقيت إشعارًا بأن DNS لا يبدو أنه يعمل على موقع الويب الخاص بي jgc.org. قام Cloudflare بإجراء تغيير على مخازن بروتوكول ، وكان هناك DNS مقطوعة.

كتبت على الفور إلى ماثيو برنس ، متوجهاً بالحرف "أين DNS الخاص بي؟" ، وأرسل إجابة طويلة ، مليئة بالتفاصيل التقنية ( اقرأ جميع المراسلات هنا ) ، والتي أجبت عليها:

من: جون غراهام كومينغ
التاريخ: 7 أكتوبر 2010 9:14
الموضوع: Re: أين هو DNS الخاص بي؟
إلى: ماثيو الأمير

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

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

ماذا حدث

لنبدأ بالترتيب. يشار إلى كل الوقت هنا بالتوقيت العالمي المنسق.

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

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

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

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

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

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

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

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

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

في الساعة 2:52 مساءً ، كنا مقتنعين بأننا فهمنا السبب وأدخلنا تصحيحًا ، وقمنا بتشغيل WAF مرة أخرى.

كيف يعمل Cloudflare

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

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

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

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

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

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

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

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. لقد اعتدنا على استخدام Kyoto Tycoon كمستودع موزع على مستوى العالم لأزواج القيمة الرئيسية ، ولكن كانت هناك مشاكل تشغيلية معه ، وكتبنا مستودعاتنا متكررة في أكثر من 180 مدينة. الآن ، مع Quicksilver ، نرسل تغييرات تكوين العميل ، نقوم بتحديث قواعد WAF ، ونقوم بتوزيع كود JavaScript المكتوب من قبل العملاء في Cloudflare Workers.

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

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

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

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

CloudFare WAF عملية النشر

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

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

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

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

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

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

استنتاج

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

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

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

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

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

أكلت جميع موارد المعالج ، تحتاج إلى معرفة القليل عن كيفية عمل محرك regex القياسي. المشكلة هنا هي النمط .*(?:.*=.*) . (?: والمجموعة المقابلة ) ليست مجموعة مثيرة (أي ، يتم تجميع التعبير بين قوسين كتعبير واحد).

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

في التعبير العادي . يعني أنك تحتاج إلى مطابقة حرف واحد ،. .* - تطابق الصفر أو أكثر من الأحرف "الجشع" ، أي ، التقاط أقصى عدد ممكن من الأحرف ، لذلك .*.*=.* يعني مطابقة الصفر أو أكثر من الأحرف ، ثم مطابقة الصفر أو أكثر من الأحرف ، والعثور على الحرف الحرفي = ، تطابق الصفر أو أكثر من الأحرف.

خذ خط الاختبار x=x . يطابق التعبير .*.*=.*. .*.* .*.*=.*. .*.* حتى علامة المساواة تتوافق مع أول x (إحدى المجموعات .* تقابل x ، والثانية إلى الصفر). .* بعد = يطابق الأخير x .

لمثل هذه المقارنة ، هناك حاجة إلى 23 خطوات. المجموعة الأولى .* .*.*=.* "بجشع" وتتطابق مع السطر بأكمله x=x . ينتقل المحرك إلى المجموعة التالية. لم يعد لدينا أحرف للمطابقة ، لذلك المجموعة الثانية .* يطابق صفر حرف (هذا مسموح به). ثم يذهب المحرك إلى علامة = . لا يوجد المزيد من الأحرف (المجموعة الأولى .* استخدم التعبير بالكامل x=x ) ، لا تحدث مطابقة.

وهنا محرك التعبير العادي يعود إلى البداية. يذهب إلى المجموعة الأولى .* ويقارنها x= (بدلاً من x=x ) ، ثم يأخذ المجموعة الثانية .* . المجموعة الثانية .* خرائط لل x الثاني ، ومرة ​​أخرى ليس لدينا أي أحرف اليسار. وعندما يصل المحرك إلى = v .*.*=.* مرة أخرى ، لا يحدث شيء. وهو يتراجع مرة أخرى.

هذه المرة ، المجموعة .* لا تزال تتطابق مع x= ، ولكن المجموعة الثانية .* لم تعد x ، ولكن صفر أحرف. يحاول المحرك العثور على الرمز الحرفي = في النموذج .*.*=.* ، لكنه لا يخرج (بعد كل شيء ، المجموعة الأولى قد احتلته بالفعل .* ). وهو يتراجع مرة أخرى.

هذه المرة المجموعة الأولى .* يأخذ فقط س الأول. لكن المجموعة الثانية .* "الجشع" تلتقط =x . خمنت بالفعل ماذا سيحدث؟ يحاول المحرك أن يتطابق مع الحرفي = ، يفشل ويفعل التراجع التالي.

المجموعة الأولى .* لا تزال تتطابق مع x الأولى. .* = . , = , .* . . !

.* x , .* — , = = . .* x .

23 x=x . Perl 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 , Programming Techniques: Regular expression search algorithm (« : »). , , , .

(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 .

.