2 جولائی 2019 کو Cloudflare کی بندش کی تفصیلات

تقریباً 9 سال پہلے Cloudflare ایک چھوٹی سی کمپنی تھی، اور میں نے اس کے لیے کام نہیں کیا، میں صرف ایک گاہک تھا۔ Cloudflare شروع کرنے کے ایک ماہ بعد، مجھے ایک اطلاع موصول ہوئی کہ میری ویب سائٹ jgc.orgایسا لگتا ہے کہ DNS کام نہیں کر رہا ہے۔ Cloudflare نے میں تبدیلی کی ہے۔ پروٹوکول بفرز، اور ایک ٹوٹا ہوا DNS تھا۔

میں نے فوری طور پر میتھیو پرنس کو "میرا ڈی این ایس کہاں ہے؟" کے عنوان سے لکھا اور اس نے تکنیکی تفصیلات سے بھرا ایک لمبا جواب واپس بھیجا (پوری خط و کتابت یہاں پڑھیںجس کا میں نے جواب دیا:

منجانب: جان گراہم-کمنگ
تاریخ: 7 اکتوبر 2010، 9:14
موضوع: Re: میرا DNS کہاں ہے؟
بنام: میتھیو پرنس

ٹھنڈی رپورٹ، شکریہ۔ اگر کوئی مسئلہ ہوا تو میں ضرور فون کروں گا۔ ایک بار جب آپ تمام تکنیکی معلومات اکٹھا کر لیں تو اس کے بارے میں ایک پوسٹ لکھنا شاید قابل قدر ہے۔ مجھے لگتا ہے کہ لوگ ایک کھلی اور ایماندار کہانی سے لطف اندوز ہوں گے۔ خاص طور پر اگر آپ اس کے ساتھ گراف منسلک کرتے ہیں تاکہ یہ ظاہر کیا جا سکے کہ لانچ کے بعد سے ٹریفک کیسے بڑھی ہے۔

میری سائٹ پر اچھی نگرانی ہے، اور مجھے ہر ناکامی کے بارے میں ایک SMS موصول ہوتا ہے۔ مانیٹرنگ سے پتہ چلتا ہے کہ ناکامی 13:03:07 سے 14:04:12 تک ہوئی۔ ٹیسٹ ہر پانچ منٹ میں کئے جاتے ہیں۔

مجھے یقین ہے کہ آپ اس کا پتہ لگا لیں گے۔ کیا آپ کو یقین ہے کہ آپ کو یورپ میں اپنے شخص کی ضرورت نہیں ہے؟ 🙂

اور اس نے جواب دیا:

منجانب: میتھیو پرنس
تاریخ: 7 اکتوبر 2010، 9:57
موضوع: Re: میرا DNS کہاں ہے؟
بنام: جان گراہم کمنگ

شکریہ ہم نے ہر ایک کو جواب دیا جس نے لکھا۔ میں ابھی دفتر جا رہا ہوں اور ہم بلاگ پر کچھ لکھیں گے یا اپنے بلیٹن بورڈ پر کوئی آفیشل پوسٹ پن کریں گے۔ میں مکمل طور پر متفق ہوں، ایمانداری ہی سب کچھ ہے۔

اب Cloudflare واقعی ایک بڑی کمپنی ہے، میں اس کے لیے کام کرتا ہوں، اور اب مجھے اپنی غلطی، اس کے نتائج اور اپنے اعمال کے بارے میں کھل کر لکھنا ہوگا۔

2 جولائی کے واقعات

2 جولائی کو ہم نے WAFs کے لیے منیجڈ رولز میں ایک نیا قاعدہ نافذ کیا جس کی وجہ سے CPU کے وسائل ختم ہو رہے تھے۔ دنیا بھر میں Cloudflare نیٹ ورک پر ہر پروسیسر کور پروسیسنگ HTTP/HTTPS ٹریفک پر۔ ہم نئی کمزوریوں اور خطرات کے جواب میں WAFs کے لیے منظم قوانین کو مسلسل بہتر کر رہے ہیں۔ مئی میں، مثال کے طور پر، ہم نے جلدی کی۔ اصول شامل کریںSharePoint میں سنگین خطرے سے بچانے کے لیے۔ ہمارے WAF کا سارا نقطہ تیزی سے اور عالمی سطح پر قوانین کو نافذ کرنے کی صلاحیت ہے۔

بدقسمتی سے، گزشتہ جمعرات کے اپ ڈیٹ میں ایک باقاعدہ اظہار تھا جس نے بیک ٹریکنگ پر بہت زیادہ HTTP/HTTPS CPU وسائل ضائع کر دیے۔ اس کے نتیجے میں ہمارے بنیادی پراکسی، CDN، اور WAF افعال کو نقصان پہنچا۔ گراف دکھاتا ہے کہ HTTP/HTTPS ٹریفک کی خدمت کے لیے پروسیسر کے وسائل ہمارے نیٹ ورک کے سرورز پر تقریباً 100% تک پہنچ جاتے ہیں۔

ایک واقعہ کے دوران موجودگی کے ایک مقام پر CPU کا استعمال

نتیجے کے طور پر، ہمارے کلائنٹس (اور ہمارے کلائنٹس کے کلائنٹس) Cloudflare ڈومینز پر 502 ایرر پیج کے ساتھ ختم ہوئے۔ Cloudflare فرنٹ اینڈ ویب سرورز کے ذریعہ 502 غلطیاں پیدا کی گئیں جن میں ابھی بھی مفت کور موجود تھے لیکن HTTP/HTTPS ٹریفک کو سنبھالنے والے عمل کے ساتھ بات چیت کرنے سے قاصر تھے۔

ہم جانتے ہیں کہ اس سے ہمارے صارفین کو کتنی تکلیف ہوئی ہے۔ ہم بہت شرمندہ ہیں۔ اور اس ناکامی نے ہمیں اس واقعے سے مؤثر طریقے سے نمٹنے سے روک دیا۔

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

اگرچہ یہ اپنے طور پر دلچسپ ہے (اور میں ذیل میں اس کے بارے میں مزید تفصیل سے بات کروں گا)، Cloudflare سروس نہ صرف خراب ریگولر ایکسپریشن کی وجہ سے 27 منٹ کے لیے بند تھی۔ ناکامی کا باعث بننے والے واقعات کی ترتیب کو بیان کرنے میں ہمیں تھوڑا وقت لگا، اس لیے ہم جواب دینے میں سست تھے۔ پوسٹ کے آخر میں، میں ریگولر ایکسپریشن میں بیک ٹریکنگ کو بیان کروں گا اور آپ کو بتاؤں گا کہ اس کے ساتھ کیا کرنا ہے۔

случилось случилось

آئیے ترتیب سے شروع کریں۔ یہاں تمام اوقات UTC میں ہیں۔

دوپہر 13:42 پر، فائر وال ٹیم کے ایک انجینئر نے پتہ لگانے کے قواعد میں ایک چھوٹی سی تبدیلی کی XSS ایک خودکار عمل کا استعمال کرتے ہوئے. اس کے مطابق تبدیلی کی درخواست کا ٹکٹ بنایا گیا۔ ہم ایسے ٹکٹوں کا انتظام جیرا کے ذریعے کرتے ہیں (نیچے اسکرین شاٹ)۔

3 منٹ کے بعد، PagerDuty کا پہلا صفحہ نمودار ہوا، جس میں WAF کے ساتھ کسی مسئلے کی اطلاع تھی۔ یہ ایک مصنوعی ٹیسٹ تھا جو عام آپریشن کی نگرانی کے لیے Cloudflare کے باہر WAFs (ہمارے پاس سینکڑوں ہیں) کی فعالیت کو جانچتا ہے۔ اس کے فوراً بعد دیگر کلاؤڈ فلیئر اینڈ ٹو اینڈ سروس ٹیسٹوں میں ناکامی، عالمی ٹریفک کے مسائل، وسیع پیمانے پر 502 غلطیاں، اور دنیا بھر کے شہروں میں ہمارے پوائنٹس آف پریزنس (پی او پی) کی ایک ٹن رپورٹس کے بارے میں انتباہات کے صفحات سامنے آئے جس میں کمی کی نشاندہی کی گئی۔ CPU وسائل کا۔

مجھے ان میں سے کئی انتباہات موصول ہوئے، ایک میٹنگ سے باہر نکلا، اور میں میز کی طرف جا رہا تھا جب ہمارے سولیوشن ڈیولپمنٹ ڈیپارٹمنٹ کے سربراہ نے کہا کہ ہم نے اپنی 80% ٹریفک کھو دی ہے۔ میں اپنے SRE انجینئرز کے پاس بھاگا، جو پہلے ہی اس مسئلے پر کام کر رہے تھے۔ پہلے ہم نے سوچا کہ یہ کوئی نامعلوم حملہ ہے۔

Cloudflare SRE انجینئرز پوری دنیا میں پھیلے ہوئے ہیں اور چوبیس گھنٹے صورتحال پر نظر رکھتے ہیں۔ عام طور پر، یہ انتباہات آپ کو محدود دائرہ کار کے مخصوص مقامی مسائل کے بارے میں مطلع کرتے ہیں، اندرونی ڈیش بورڈز پر ٹریک کیے جاتے ہیں، اور روزانہ کئی بار حل کیے جاتے ہیں۔ لیکن ان صفحات اور اطلاعات نے واقعی کچھ سنجیدہ ہونے کی نشاندہی کی، اور SRE انجینئرز نے فوری طور پر شدت کی سطح P0 کا اعلان کیا اور مینجمنٹ اور سسٹم انجینئرز سے رابطہ کیا۔

ہمارے لندن کے انجینئر اس وقت مین ہال میں ایک لیکچر سن رہے تھے۔ لیکچر کو روکنا پڑا، سب ایک بڑے کانفرنس روم میں جمع ہوئے، اور مزید ماہرین کو بلایا گیا۔ یہ کوئی عام مسئلہ نہیں تھا جس سے SREs خود نمٹ سکتے تھے۔ صحیح ماہرین کو شامل کرنا ضروری تھا۔

14:00 بجے ہم نے طے کیا کہ مسئلہ WAF کے ساتھ تھا اور کوئی حملہ نہیں ہوا تھا۔ کارکردگی ٹیم نے CPU ڈیٹا کھینچ لیا اور یہ واضح ہو گیا کہ WAF قصوروار تھا۔ ایک اور ملازم نے سٹریس کا استعمال کرتے ہوئے اس تھیوری کی تصدیق کی۔ کسی اور نے نوشتہ جات میں دیکھا کہ WAF میں کوئی مسئلہ ہے۔ دوپہر 14:02 بجے، پوری ٹیم میرے پاس آئی جب اسے گلوبل کِل استعمال کرنے کی تجویز پیش کی گئی، ایک ایسا طریقہ کار جو Cloudflare میں بنایا گیا ہے جو دنیا بھر میں ایک جزو کو بند کر دیتا ہے۔

ہم نے WAF کے لیے عالمی سطح پر قتل کیسے کیا یہ ایک الگ کہانی ہے۔ یہ اتنا آسان نہیں ہے۔ ہم اپنی مصنوعات کا استعمال کرتے ہیں، اور ہماری خدمت کے بعد سے تک رسائی کام نہیں ہوا، ہم داخلی کنٹرول پینل کی توثیق اور لاگ ان نہیں کر سکے (جب سب کچھ ٹھیک ہو گیا تھا، ہمیں معلوم ہوا کہ ٹیم کے کچھ ممبران نے حفاظتی خصوصیت کی وجہ سے رسائی کھو دی ہے جو کہ اگر داخلی کنٹرول پینل کا استعمال نہیں کیا جاتا ہے تو اسناد کو غیر فعال کر دیتی ہے طویل وقت)۔

اور ہم اپنی داخلی خدمات، جیسے جیرا یا بلڈ سسٹم تک نہیں پہنچ سکے۔ ہمیں ایک ورک آراؤنڈ میکانزم کی ضرورت تھی، جسے ہم کبھی کبھار استعمال کرتے تھے (اس پر بھی کام کرنے کی ضرورت ہوگی)۔ آخر کار، ایک انجینئر 14:07 پر WAF کو غیر فعال کرنے میں کامیاب ہو گیا، اور 14:09 پر، ٹریفک اور CPU کی سطح ہر جگہ معمول پر آ گئی۔ Cloudflare کے باقی تحفظ کے طریقہ کار نے معمول کے مطابق کام کیا۔

پھر ہم نے WAF کو بحال کرنے کا فیصلہ کیا۔ صورتحال معمول سے ہٹ کر تھی، اس لیے ہم نے ایک شہر میں منفی ٹیسٹ (اپنے آپ سے یہ پوچھتے ہوئے کہ کیا واقعی یہ مسئلہ تھا) اور مثبت ٹیسٹ (اس بات کو یقینی بنانے کے لیے کہ رول بیک نے کام کیا) الگ ٹریفک کا استعمال کرتے ہوئے، ادائیگی کرنے والے صارفین کو وہاں سے منتقل کیا۔

14:52 پر ہمیں یقین ہو گیا کہ ہم نے وجہ سمجھ لی اور اصلاح کی، اور WAF کو دوبارہ فعال کر دیا۔

Cloudflare کیسے کام کرتا ہے۔

Cloudflare کے پاس انجینئرز کی ایک ٹیم ہے جو WAFs کے قوانین کے انتظام کے لیے وقف ہے۔ وہ پتہ لگانے کی شرح کو بہتر بنانے، غلط مثبت کو کم کرنے، اور نئے خطرات کے سامنے آنے کے ساتھ ہی ان کا فوری جواب دینے کی کوشش کرتے ہیں۔ گزشتہ 60 دنوں میں، WAF کے لیے منظم قوانین کے لیے 476 تبدیلی کی درخواستوں پر کارروائی کی گئی ہے (ہر 3 گھنٹے میں اوسطاً ایک)۔

اس خاص تبدیلی کو سمولیشن موڈ میں تعینات کرنے کی ضرورت ہے، جہاں حقیقی کلائنٹ ٹریفک اصول سے گزرتا ہے، لیکن کچھ بھی بلاک نہیں ہوتا ہے۔ ہم اس موڈ کو قواعد کی تاثیر کو جانچنے اور غلط مثبت اور غلط منفی شرحوں کی پیمائش کرنے کے لیے استعمال کرتے ہیں۔ لیکن نقلی موڈ میں بھی، اصولوں کو درحقیقت عمل میں لایا جانا چاہیے، اور اس معاملے میں اصول میں ایک باقاعدہ اظہار ہوتا ہے جو پروسیسر کے بہت زیادہ وسائل استعمال کر رہا تھا۔

جیسا کہ آپ اوپر کی تبدیلی کی درخواست سے دیکھ سکتے ہیں، ہمارے پاس اس قسم کی تعیناتی کے لیے ایک تعیناتی منصوبہ، ایک رول بیک پلان، اور اندرونی معیاری آپریٹنگ طریقہ کار (SOP) کا لنک ہے۔ کسی اصول کو تبدیل کرنے کا SOP اسے عالمی سطح پر شائع کرنے کی اجازت دیتا ہے۔ درحقیقت، Cloudflare میں، چیزیں بالکل مختلف طریقے سے کی جاتی ہیں، اور SOP یہ حکم دیتا ہے کہ ہم پہلے ٹیسٹنگ اور اندرونی استعمال کے لیے سافٹ ویئر کو داخلی مقام (PoP) پر بھیجتے ہیں (جسے ہمارے ملازمین استعمال کرتے ہیں)، پھر اس میں کلائنٹس کی ایک چھوٹی سی تعداد کو ایک الگ تھلگ جگہ، پھر گاہکوں کی ایک بڑی تعداد کے لیے، اور تب ہی پوری دنیا کے لیے۔

یہ ایسا ہی لگتا ہے۔ ہم بٹ بکٹ کے ذریعے گٹ کو اندرونی طور پر استعمال کرتے ہیں۔ تبدیلیوں پر کام کرنے والے انجینئرز کوڈ جمع کراتے ہیں، جو TeamCity میں بنایا گیا ہے، اور جب بلڈ پاس ہوجاتا ہے، تو جائزہ لینے والوں کو تفویض کیا جاتا ہے۔ ایک بار پل کی درخواست منظور ہونے کے بعد، کوڈ کو جمع کیا جاتا ہے اور ٹیسٹوں کا ایک سلسلہ چلایا جاتا ہے (دوبارہ)۔

اگر تعمیر اور ٹیسٹ کامیابی کے ساتھ مکمل ہو جاتے ہیں، تو جیرا میں تبدیلی کی درخواست کی جاتی ہے اور مناسب مینیجر یا لیڈ کو تبدیلی کی منظوری دینی چاہیے۔ منظوری کے بعد، تعیناتی نام نہاد "PoP menagerie" میں ہوتی ہے: DOG، PIG اور کینری (کتا، سور اور کینری)

DOG PoP ایک Cloudflare PoP ہے (ہمارے دوسرے شہروں کی طرح) جو صرف Cloudflare کے ملازمین استعمال کرتے ہیں۔ داخلی استعمال کے لیے PoP آپ کو مسائل کو پکڑنے کی اجازت دیتا ہے اس سے پہلے کہ گاہک کی ٹریفک حل میں آنے لگے۔ مفید چیز۔

اگر DOG ٹیسٹ کامیاب ہو جاتا ہے، تو کوڈ PIG (گنی پگ) کے مرحلے میں چلا جاتا ہے۔ یہ Cloudflare PoP ہے، جہاں مفت کسٹمر ٹریفک کی ایک چھوٹی سی رقم نئے کوڈ سے گزرتی ہے۔
اگر سب ٹھیک ہے تو، کوڈ کینری میں جاتا ہے۔ ہمارے پاس دنیا کے مختلف حصوں میں تین Canary PoPs ہیں۔ ان میں، ادا شدہ اور مفت کلائنٹس کی ٹریفک نئے کوڈ سے گزرتی ہے، اور یہ غلطیوں کی آخری جانچ ہے۔

Cloudflare پر سافٹ ویئر کی رہائی کا عمل

اگر کینری میں کوڈ ٹھیک ہے تو ہم اسے جاری کر دیتے ہیں۔ تمام مراحل سے گزرنا - DOG, PIG, Canary, پوری دنیا - کوڈ کی تبدیلی کے لحاظ سے کئی گھنٹے یا دن لگتے ہیں۔ Cloudflare کے نیٹ ورک اور کلائنٹس کے تنوع کی وجہ سے، ہم عالمی سطح پر تمام کلائنٹس کو جاری کرنے سے پہلے کوڈ کی اچھی طرح جانچ کرتے ہیں۔ لیکن WAF خاص طور پر اس عمل کی پیروی نہیں کرتا ہے کیونکہ دھمکیوں کا فوری جواب دینے کی ضرورت ہے۔

ڈبلیو اے ایف کی دھمکیاں
پچھلے کچھ سالوں میں، عام ایپلی کیشنز میں خطرات میں نمایاں اضافہ ہوا ہے۔ یہ سافٹ ویئر ٹیسٹنگ ٹولز کی زیادہ دستیابی کی وجہ سے ہے۔ مثال کے طور پر، ہم نے حال ہی میں لکھا مبہم).

ماخذ: https://cvedetails.com/

اکثر، تصور کا ثبوت بنایا جاتا ہے اور اسے گیتھب پر فوری طور پر شائع کیا جاتا ہے تاکہ ایپلیکیشن کو برقرار رکھنے والی ٹیمیں اس کی فوری جانچ کر سکیں اور اس بات کو یقینی بنا سکیں کہ یہ مناسب طور پر محفوظ ہے۔ لہذا، Cloudflare کو جلد از جلد نئے حملوں کا جواب دینے کی صلاحیت کی ضرورت ہے تاکہ صارفین کو اپنے سافٹ ویئر کو ٹھیک کرنے کا موقع ملے۔

Cloudflare کے فوری ردعمل کی ایک بہترین مثال مئی میں شیئرپوائنٹ کے خطرے سے متعلق تحفظات کی تعیناتی ہے (یہاں پڑھیں)۔ اعلانات کیے جانے کے تقریباً فوراً بعد، ہم نے اپنے صارفین کی شیئرپوائنٹ تنصیبات میں موجود کمزوری سے فائدہ اٹھانے کی ایک بڑی تعداد کو دیکھا۔ ہمارے لوگ مسلسل نئے خطرات کی نگرانی کر رہے ہیں اور اپنے صارفین کی حفاظت کے لیے قواعد لکھ رہے ہیں۔

جمعرات کو جو قاعدہ اس مسئلے کا سبب بنتا ہے اسے کراس سائٹ اسکرپٹنگ (XSS) سے تحفظ فراہم کرنا تھا۔ اس طرح کے حملے بھی حالیہ برسوں میں بہت زیادہ ہو گئے ہیں۔

ماخذ: https://cvedetails.com/

WAF کے لیے منظم اصول کو تبدیل کرنے کا معیاری طریقہ کار یہ ہے کہ عالمی تعیناتی سے پہلے مسلسل انضمام (CI) ٹیسٹنگ کروائی جائے۔ گزشتہ جمعرات کو ہم نے یہ کیا اور قوانین کو نافذ کیا۔ دوپہر 13:31 بجے، ایک انجینئر نے تبدیلی کے ساتھ ایک منظور شدہ پل کی درخواست جمع کرائی۔

13:37 پر TeamCity نے قواعد جمع کیے، ٹیسٹ چلائے اور آگے بڑھنے کا فیصلہ کیا۔ WAF ٹیسٹ سویٹ WAF کی بنیادی فعالیت کو جانچتا ہے اور انفرادی افعال کے لیے یونٹ ٹیسٹ کی ایک بڑی تعداد پر مشتمل ہوتا ہے۔ یونٹ ٹیسٹ کے بعد، ہم نے بہت بڑی تعداد میں HTTP درخواستوں کا استعمال کرتے ہوئے WAF کے لیے قواعد کی جانچ کی۔ HTTP درخواستیں چیک کرتی ہیں کہ کون سی درخواستوں کو WAF (حملے کو روکنے کے لیے) کے ذریعے بلاک کیا جانا چاہیے اور کن کے ذریعے اجازت دی جا سکتی ہے (تاکہ ہر چیز کو بلاک نہ کیا جائے اور جھوٹے مثبتات سے بچنا پڑے)۔ لیکن ہم نے CPU کے ضرورت سے زیادہ استعمال کی جانچ نہیں کی، اور سابقہ ​​WAF تعمیرات کے لاگز کی جانچ کرنے سے یہ ظاہر ہوتا ہے کہ رول ٹیسٹ پر عمل درآمد کے وقت میں اضافہ نہیں ہوا، اور یہ شک کرنا مشکل تھا کہ کافی وسائل نہیں ہوں گے۔

ٹیسٹ پاس ہو گئے اور ٹیم سٹی نے خود بخود تبدیلی کو 13:42 پر تعینات کرنا شروع کر دیا۔

پارا

WAF کے قوانین فوری خطرے کے تدارک پر توجہ مرکوز کرتے ہیں، اس لیے ہم انہیں Quicksilver کے تقسیم شدہ کلیدی قدر والے اسٹور کا استعمال کرتے ہوئے تعینات کرتے ہیں، جو عالمی سطح پر تبدیلیوں کو سیکنڈوں میں پھیلاتا ہے۔ ہمارے تمام کلائنٹس اس ٹیکنالوجی کو استعمال کرتے ہیں جب وہ ڈیش بورڈ میں یا API کے ذریعے کنفیگریشن کو تبدیل کرتے ہیں، اور یہ اس کی بدولت ہے کہ ہم بجلی کی رفتار سے تبدیلیوں کا جواب دیتے ہیں۔

ہم نے Quicksilver کے بارے میں زیادہ بات نہیں کی ہے۔ پہلے ہم استعمال کرتے تھے۔ کیوٹو ٹائکون عالمی سطح پر تقسیم شدہ کلیدی قدر والے اسٹور کے طور پر، لیکن اس کے ساتھ آپریشنل مسائل تھے، اور ہم نے اپنا اسٹور لکھا، جسے 180 سے زیادہ شہروں میں نقل کیا گیا۔ اب ہم Quicksilver کا استعمال کلائنٹس میں کنفیگریشن کی تبدیلیوں کو آگے بڑھانے، WAF قوانین کو اپ ڈیٹ کرنے، اور کلائنٹس کے ذریعے لکھا ہوا JavaScript کوڈ Cloudflare ورکرز میں تقسیم کرنے کے لیے استعمال کرتے ہیں۔

ڈیش بورڈ پر بٹن پر کلک کرنے یا کسی API کو کال کرنے سے لے کر دنیا بھر میں کنفیگریشن تبدیلی کرنے میں صرف چند سیکنڈ لگتے ہیں۔ صارفین نے سیٹ اپ کی اس رفتار کو پسند کیا۔ اور ورکرز انہیں تقریباً فوری طور پر عالمی سافٹ ویئر کی تعیناتی فراہم کرتے ہیں۔ اوسطا، Quicksilver فی سیکنڈ تقریباً 350 تبدیلیاں پھیلاتا ہے۔

اور Quicksilver بہت تیز ہے۔ اوسطاً، ہم نے دنیا بھر میں ہر کمپیوٹر میں تبدیلیاں پھیلانے کے لیے 99 سیکنڈز کا 2,29 واں فیصد حاصل کیا۔ رفتار عام طور پر ایک اچھی چیز ہے۔ بہر حال، جب آپ کسی فنکشن کو فعال کرتے ہیں یا کیشے کو صاف کرتے ہیں، تو یہ تقریباً فوری طور پر اور ہر جگہ ہوتا ہے۔ Cloudflare ورکرز کے ذریعے کوڈ بھیجنا اسی رفتار سے ہوتا ہے۔ Cloudflare اپنے صارفین سے صحیح وقت پر تیز رفتار اپڈیٹس کا وعدہ کرتا ہے۔

لیکن اس معاملے میں، رفتار نے ہم پر ایک ظالمانہ مذاق کھیلا، اور چند سیکنڈوں میں ہر جگہ اصول بدل گئے۔ آپ نے دیکھا ہوگا کہ WAF کوڈ Lua کا استعمال کرتا ہے۔ Cloudflare پیداوار اور تفصیلات میں Lua کو بڑے پیمانے پر استعمال کرتا ہے۔ WAF میں Lua ہم ہیں پہلے ہی بات چیت کی. Lua WAF استعمال کرتا ہے۔ PCRE اندرونی طور پر اور ملاپ کے لیے بیک ٹریکنگ کا اطلاق ہوتا ہے۔ اس کے پاس ایسے تاثرات سے بچانے کا کوئی طریقہ کار نہیں ہے جو قابو سے باہر ہو جائیں۔ ذیل میں میں اس کے بارے میں مزید بات کروں گا اور ہم اس کے بارے میں کیا کر رہے ہیں۔

قواعد کی تعیناتی سے پہلے، سب کچھ آسانی سے چلا گیا: پل کی درخواست بنائی گئی اور منظور کی گئی، CI/CD پائپ لائن نے کوڈ کو اکٹھا کیا اور اس کی جانچ کی، تبدیلی کی درخواست SOP کے مطابق جمع کرائی گئی جو تعیناتی اور رول بیک کو کنٹرول کرتی ہے، اور تعیناتی مکمل ہو گئی۔

Cloudflare WAF تعیناتی کا عمل

کچھ غلط ہو گیا
جیسا کہ میں نے کہا، ہم ہر ہفتے WAF کے درجنوں نئے قوانین تعینات کرتے ہیں، اور اس طرح کی تعیناتی کے منفی نتائج سے بچانے کے لیے ہمارے پاس بہت سے نظام موجود ہیں۔ اور جب کچھ غلط ہو جاتا ہے، تو یہ عام طور پر ایک ساتھ کئی حالات کا مجموعہ ہوتا ہے۔ اگر آپ کو صرف ایک وجہ مل جاتی ہے، تو یہ یقیناً تسلی بخش ہے، لیکن یہ ہمیشہ سچ نہیں ہوتا۔ یہ وہ وجوہات ہیں جو مل کر ہماری HTTP/HTTPS سروس کی ناکامی کا باعث بنیں۔

1. ایک انجینئر نے ایک باقاعدہ اظہار لکھا جس کا نتیجہ ضرورت سے زیادہ ہو سکتا ہے۔ پیچھے ہٹنا.
2. ایک ایسی خصوصیت جو ریگولر ایکسپریشن کو بہت زیادہ CPU کو ضائع ہونے سے روک سکتی تھی اسے WAF کی ری فیکٹرنگ میں غلطی سے کئی ہفتے پہلے ہٹا دیا گیا تھا — WAF کو کم وسائل استعمال کرنے کے لیے ری فیکٹرنگ کی ضرورت تھی۔
3. ریگولر ایکسپریشن انجن میں پیچیدگی کی کوئی ضمانت نہیں تھی۔
4. ٹیسٹ سویٹ ضرورت سے زیادہ CPU استعمال کا پتہ نہیں لگا سکا۔
5. SOP غیر فوری اصول کی تبدیلیوں کو عالمی سطح پر کثیر مرحلہ عمل کے بغیر نافذ کرنے کی اجازت دیتا ہے۔
6. رول بیک پلان کے لیے مکمل WAF بلڈ کو دو بار چلانے کی ضرورت تھی، جس میں کافی وقت لگا۔
7. عالمی ٹریفک کے مسائل کے بارے میں پہلا انتباہ بہت دیر سے شروع ہوا تھا۔
8. ہمیں اسٹیٹس پیج کو اپ ڈیٹ کرنے میں کچھ وقت لگا۔
9. ہمیں خرابی کی وجہ سے سسٹم تک رسائی میں دشواری کا سامنا کرنا پڑا، اور بائی پاس کا طریقہ کار اچھی طرح سے قائم نہیں تھا۔
10. SRE انجینئرز نے کچھ سسٹمز تک رسائی کھو دی کیونکہ سیکورٹی وجوہات کی بنا پر ان کی اسناد کی میعاد ختم ہو گئی تھی۔
11. ہمارے صارفین کو Cloudflare ڈیش بورڈ یا API تک رسائی حاصل نہیں تھی کیونکہ وہ Cloudflare کے علاقے سے گزرتے ہیں۔

گزشتہ جمعرات کے بعد سے کیا بدلا ہے۔

سب سے پہلے، ہم نے WAF کے لیے ریلیز کے تمام کام کو مکمل طور پر روک دیا اور درج ذیل کام کر رہے ہیں:

1. ہم CPU کے زیادہ استعمال کے تحفظ کو دوبارہ پیش کر رہے ہیں جسے ہم نے ہٹا دیا ہے۔ (تیار)
2. ضرورت سے زیادہ بیک ٹریکنگ کے دیگر ممکنہ کیسز کو تلاش کرنے اور درست کرنے کے لیے WAF کے انتظام کردہ قواعد میں تمام 3868 قواعد کو دستی طور پر چیک کرنا۔ (تصدیق مکمل)
3. ہم ٹیسٹ سیٹ میں تمام قواعد کے لیے کارکردگی کی پروفائلنگ شامل کرتے ہیں۔ (متوقع: 19 جولائی)
4. ریگولر ایکسپریشن انجن پر سوئچ کرنا RE2 یا مورچا - دونوں رن ٹائم گارنٹی فراہم کرتے ہیں۔ (متوقع: 31 جولائی)
5. ہم Cloudflare میں دوسرے سافٹ ویئر کی طرح مراحل میں قوانین کو تعینات کرنے کے لیے SOP کو دوبارہ لکھ رہے ہیں، لیکن اگر حملے پہلے ہی شروع ہو چکے ہیں تو اس کے ساتھ ساتھ ہنگامی عالمی تعیناتی کی صلاحیت بھی رکھتے ہیں۔
6. ہم Cloudflare ریجن سے Cloudflare ڈیش بورڈ اور API کو فوری طور پر ہٹانے کی صلاحیت تیار کر رہے ہیں۔
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.

صرف کے لیے 23 قدم x=x. پرل کے استعمال کے بارے میں ایک مختصر ویڈیو دیکھیں Regexp::Debugger، جو دکھاتا ہے کہ کس طرح قدم اور پیچھے ہٹنا ہوتا ہے۔

یہ پہلے سے ہی بہت کام ہے، لیکن اس کے بجائے کیا ہوگا؟ x=x ہمارے پاس ہو گا x=xx? یہ 33 مراحل ہیں۔ اور اگر x=xxx? 45. رشتہ خطی نہیں ہے۔ گراف سے موازنہ دکھاتا ہے۔ x=x پر x=xxxxxxxxxxxxxxxxxxxx (20 x کے بعد =)۔ اگر ہمارے پاس 20 ایکس کے بعد ہے۔ =، انجن 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 کمپیوٹر پروگرامنگ لینگویج سے واقف ہے۔

مرتب کرنے والا
کمپائلر تین مراحل پر مشتمل ہے جو متوازی طور پر چل رہے ہیں۔ پہلا مرحلہ نحوی فلٹرنگ ہے، جو صرف نحوی طور پر درست ریگولر ایکسپریشنز کو گزرنے دیتا ہے۔ یہ مرحلہ ریگولر ایکسپریشنز سے ملنے کے لیے "·" آپریٹر بھی داخل کرتا ہے۔ دوسرے مرحلے میں، ریگولر ایکسپریشن پوسٹ فکس فارم میں تبدیل ہو جاتا ہے۔ تیسرے مرحلے پر آبجیکٹ کوڈ بنایا جاتا ہے۔ پہلے 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 میں دکھایا گیا ہے۔ XNUMX.

تصویر میں 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