2 জুলাই, 2019-এ ক্লাউডফ্লেয়ার বিভ্রাটের বিশদ বিবরণ

প্রায় 9 বছর আগে ক্লাউডফ্লেয়ার একটি ছোট কোম্পানি ছিল এবং আমি এটির জন্য কাজ করিনি, আমি কেবল একজন গ্রাহক ছিলাম। Cloudflare চালু করার এক মাস পরে, আমি একটি বিজ্ঞপ্তি পেয়েছি যে আমার ওয়েবসাইট jgc.orgDNS কাজ করছে বলে মনে হচ্ছে না। Cloudflare একটি পরিবর্তন করেছে প্রোটোকল বাফার, এবং একটি ভাঙা DNS ছিল.

আমি অবিলম্বে ম্যাথু প্রিন্সকে "আমার ডিএনএস কোথায়?" শিরোনামে লিখেছিলাম এবং তিনি প্রযুক্তিগত বিবরণে পূর্ণ একটি দীর্ঘ উত্তর ফেরত পাঠিয়েছিলেন (এখানে সম্পূর্ণ চিঠিপত্র পড়ুন), যার আমি উত্তর দিয়েছিলাম:

থেকে: জন গ্রাহাম-কামিং
তারিখ: 7 অক্টোবর, 2010, 9:14
বিষয়: Re: আমার DNS কোথায়?
প্রতি: ম্যাথু প্রিন্স

দুর্দান্ত প্রতিবেদন, ধন্যবাদ। সমস্যা হলে অবশ্যই ফোন করব। আপনি যখন সমস্ত প্রযুক্তিগত তথ্য সংগ্রহ করবেন তখন সম্ভবত এই বিষয়ে একটি পোস্ট লেখার মূল্য। আমি মনে করি মানুষ একটি খোলামেলা এবং সৎ গল্প পছন্দ করবে। বিশেষ করে যদি আপনি এটিতে গ্রাফ সংযুক্ত করেন তা দেখাতে যে লঞ্চের পর থেকে কীভাবে ট্রাফিক বেড়েছে।

আমার সাইটে আমার ভালো মনিটরিং আছে, এবং আমি প্রতিটি ব্যর্থতার বিষয়ে একটি SMS পাই। মনিটরিং দেখায় যে ব্যর্থতা 13:03:07 থেকে 14:04:12 পর্যন্ত ঘটেছে। প্রতি পাঁচ মিনিটে পরীক্ষা করা হয়।

আমি নিশ্চিত আপনি এটা সব খুঁজে বের করতে হবে. আপনি কি নিশ্চিত যে ইউরোপে আপনার নিজের লোকের প্রয়োজন নেই? 🙂

এবং তিনি উত্তর দিলেন:

থেকে: ম্যাথু প্রিন্স
তারিখ: 7 অক্টোবর, 2010, 9:57
বিষয়: Re: আমার DNS কোথায়?
প্রতি: জন গ্রাহাম-কামিং

ধন্যবাদ. আমরা যারা লিখেছিলাম তাদের প্রত্যেককে সাড়া দিয়েছি। আমি এখন অফিসে যাচ্ছি এবং আমরা ব্লগে কিছু লিখব বা আমাদের বুলেটিন বোর্ডে একটি অফিসিয়াল পোস্ট পিন করব৷ আমি সম্পূর্ণরূপে একমত, সততা সবকিছু.

এখন ক্লাউডফ্লেয়ার সত্যিই একটি বড় কোম্পানি, আমি এটির জন্য কাজ করি এবং এখন আমাকে আমাদের ভুল, এর পরিণতি এবং আমাদের ক্রিয়াকলাপ সম্পর্কে খোলাখুলি লিখতে হবে।

ঘটনা 2 জুলাই

২ জুলাই, আমরা WAF এর জন্য পরিচালিত নিয়মে একটি নতুন নিয়ম চালু করেছি, যার কারণে CPU সম্পদ ফুরিয়ে যাচ্ছিল বিশ্বব্যাপী ক্লাউডফ্লেয়ার নেটওয়ার্কে প্রতিটি প্রসেসর কোর প্রসেসিং HTTP/HTTPS ট্র্যাফিকের উপর। আমরা ক্রমাগত নতুন দুর্বলতা এবং হুমকির প্রতিক্রিয়া হিসাবে WAF-এর জন্য পরিচালিত নিয়মগুলিকে উন্নত করছি। মে মাসে, উদাহরণস্বরূপ, আমরা তাড়াহুড়ো করেছিলাম নিয়ম যোগ করুনSharePoint এ একটি গুরুতর দুর্বলতা থেকে রক্ষা করতে। আমাদের WAF-এর পুরো বিষয় হল দ্রুত এবং বিশ্বব্যাপী নিয়মগুলি স্থাপন করার ক্ষমতা।

দুর্ভাগ্যবশত, গত বৃহস্পতিবারের আপডেটে একটি নিয়মিত অভিব্যক্তি রয়েছে যা ব্যাকট্র্যাকিংয়ে খুব বেশি HTTP/HTTPS CPU সম্পদ নষ্ট করেছে। আমাদের মূল প্রক্সি, CDN, এবং WAF ফাংশন ফলস্বরূপ ক্ষতিগ্রস্ত হয়েছে। গ্রাফটি দেখায় যে HTTP/HTTPS ট্র্যাফিক পরিবেশনের জন্য প্রসেসর সংস্থানগুলি আমাদের নেটওয়ার্কের সার্ভারগুলিতে প্রায় 100% পৌঁছেছে৷

একটি ঘটনার সময় উপস্থিতির এক পর্যায়ে CPU ব্যবহার

ফলস্বরূপ, আমাদের ক্লায়েন্ট (এবং আমাদের ক্লায়েন্টদের ক্লায়েন্ট) ক্লাউডফ্লেয়ার ডোমেনে একটি 502 ত্রুটি পৃষ্ঠার সাথে শেষ হয়েছে। ক্লাউডফ্লেয়ার ফ্রন্ট-এন্ড ওয়েব সার্ভারের দ্বারা 502টি ত্রুটি তৈরি হয়েছিল যেগুলিতে এখনও বিনামূল্যে কোর ছিল কিন্তু HTTP/HTTPS ট্র্যাফিক পরিচালনার প্রক্রিয়াগুলির সাথে যোগাযোগ করতে অক্ষম ছিল৷

আমরা জানি এটি আমাদের গ্রাহকদের কতটা অসুবিধার কারণ হয়েছে। আমরা ভয়ানক লজ্জিত. এবং এই ব্যর্থতা আমাদের কার্যকরভাবে ঘটনার সাথে মোকাবিলা করতে বাধা দেয়।

আপনি যদি এই গ্রাহকদের মধ্যে একজন হন তবে আপনি সম্ভবত ভীত, রাগান্বিত এবং বিচলিত ছিলেন। তাছাড়া, আমরা একটি ছিল না বিশ্বব্যাপী ব্যর্থতা. উচ্চ সিপিইউ খরচ একটি WAF নিয়মের কারণে ছিল একটি খারাপ শব্দযুক্ত রেগুলার এক্সপ্রেশন যার ফলে অতিরিক্ত ব্যাকট্র্যাকিং হয়েছে। এখানে দোষী অভিব্যক্তি: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))

যদিও এটি নিজেই আকর্ষণীয় (এবং আমি নীচে আরও বিশদে এটি কভার করব), ক্লাউডফ্লেয়ারের 27-মিনিটের ব্ল্যাকআউট কেবল একটি খারাপ নিয়মিত অভিব্যক্তির কারণে হয়নি। ক্র্যাশের দিকে পরিচালিত ঘটনাগুলির ক্রম বর্ণনা করতে আমাদের কিছু সময় লেগেছে, তাই আমরা দ্রুত প্রতিক্রিয়া জানাইনি৷ পোস্টের শেষে, আমি একটি রেগুলার এক্সপ্রেশনে ব্যাকট্র্যাকিং বর্ণনা করব এবং এর সাথে কী করতে হবে তা আপনাকে বলব।

কি হলো

এর ক্রম শুরু করা যাক. এখানে সব সময় UTC তে আছে।

13:42 এ, ফায়ারওয়াল টিমের একজন প্রকৌশলী সনাক্তকরণের নিয়মে একটি ছোট পরিবর্তন করেছেন পদ্ধতি এটা XSS একটি স্বয়ংক্রিয় প্রক্রিয়া ব্যবহার করে। তদনুসারে, একটি পরিবর্তন অনুরোধ টিকিট তৈরি করা হয়েছিল। আমরা জিরা (নীচের স্ক্রিনশট) এর মাধ্যমে এই জাতীয় টিকিট পরিচালনা করি।

3 মিনিট পর, PagerDuty-এর প্রথম পৃষ্ঠাটি উপস্থিত হয়েছিল, WAF-এর সাথে একটি সমস্যা প্রতিবেদন করেছে। এটি একটি সিন্থেটিক পরীক্ষা যা স্বাভাবিক ক্রিয়াকলাপ নিরীক্ষণের জন্য ক্লাউডফ্লেয়ারের বাইরে WAFs (আমাদের শত শত আছে) কার্যকারিতা পরীক্ষা করে। এটি অবিলম্বে অন্যান্য ক্লাউডফ্লেয়ার এন্ড-টু-এন্ড পরিষেবা পরীক্ষায় ব্যর্থতা, বিশ্বব্যাপী ট্র্যাফিক সমস্যা, ব্যাপক 502 ত্রুটি, এবং বিশ্বজুড়ে শহরগুলিতে আমাদের পয়েন্টস অফ প্রেজেন্স (PoP) থেকে এক টন রিপোর্ট যা অভাব নির্দেশ করে সে সম্পর্কে সতর্কতার পৃষ্ঠাগুলি অনুসরণ করেছিল CPU সম্পদের।

আমি এই সতর্কতাগুলির মধ্যে বেশ কয়েকটি পেয়েছি, একটি মিটিং থেকে বেরিয়ে এসে আমি টেবিলের দিকে যাচ্ছিলাম যখন আমাদের সমাধান উন্নয়ন বিভাগের প্রধান বলেছিলেন যে আমরা আমাদের ট্রাফিকের 80% হারিয়ে ফেলেছি। আমি আমাদের এসআরই ইঞ্জিনিয়ারদের কাছে ছুটে গিয়েছিলাম, যারা ইতিমধ্যেই সমস্যা নিয়ে কাজ করছিল। প্রথমে আমরা ভেবেছিলাম এটা কোনো অজানা হামলা।

ক্লাউডফ্লেয়ার এসআরই ইঞ্জিনিয়াররা সারা বিশ্বে ছড়িয়ে ছিটিয়ে রয়েছে এবং চব্বিশ ঘন্টা পরিস্থিতি পর্যবেক্ষণ করছে। সাধারণত, এই সতর্কতাগুলি আপনাকে সীমিত সুযোগের নির্দিষ্ট স্থানীয় সমস্যার বিষয়ে অবহিত করে, অভ্যন্তরীণ ড্যাশবোর্ডে ট্র্যাক করা হয় এবং প্রতিদিন একাধিকবার সমাধান করা হয়। কিন্তু এই পৃষ্ঠাগুলি এবং বিজ্ঞপ্তিগুলি সত্যিই গুরুতর কিছু নির্দেশ করে, এবং SRE প্রকৌশলীরা অবিলম্বে তীব্রতা স্তর P0 ঘোষণা করেন এবং ব্যবস্থাপনা এবং সিস্টেম ইঞ্জিনিয়ারদের সাথে যোগাযোগ করেন।

আমাদের লন্ডন প্রকৌশলীরা সেই মুহুর্তে প্রধান হলের একটি বক্তৃতা শুনছিলেন। বক্তৃতাটি বাধা দিতে হয়েছিল, সবাই একটি বড় কনফারেন্স রুমে জড়ো হয়েছিল এবং আরও বিশেষজ্ঞদের ডাকা হয়েছিল। এটি একটি সাধারণ সমস্যা ছিল না যা SREs তাদের নিজেরাই মোকাবেলা করতে পারে। জরুরীভাবে সঠিক বিশেষজ্ঞদের সাথে সংযোগ করা প্রয়োজন ছিল।

14:00 এ আমরা নির্ধারণ করেছি যে সমস্যাটি WAF এর সাথে ছিল এবং কোন আক্রমণ হয়নি। পারফরম্যান্স টিম সিপিইউ ডেটা টেনে নিয়েছিল এবং এটি পরিষ্কার হয়ে গিয়েছিল যে WAF দায়ী ছিল। অন্য একজন কর্মচারী স্ট্রেস ব্যবহার করে এই তত্ত্বটি নিশ্চিত করেছেন। অন্য কেউ লগগুলিতে দেখেছে যে WAF এর সাথে একটি সমস্যা রয়েছে৷ দুপুর 14:02 টায়, পুরো দলটি আমার কাছে এসেছিল যখন এটিকে গ্লোবাল কিল ব্যবহার করার প্রস্তাব দেওয়া হয়েছিল, ক্লাউডফ্লেয়ারে তৈরি একটি মেকানিজম যা বিশ্বব্যাপী একটি উপাদান বন্ধ করে দেয়।

কিভাবে আমরা WAF এর জন্য একটি বিশ্বব্যাপী হত্যা করেছি একটি ভিন্ন গল্প। এটা যে সহজ নয়. আমরা আমাদের নিজস্ব পণ্য ব্যবহার করি, এবং আমাদের পরিষেবা থেকে প্রবেশ কাজ করেনি, আমরা অভ্যন্তরীণ কন্ট্রোল প্যানেলে প্রমাণীকরণ এবং লগ ইন করতে পারিনি (যখন সবকিছু ঠিক করা হয়েছিল, আমরা শিখেছি যে কিছু টিমের সদস্য একটি সুরক্ষা বৈশিষ্ট্যের কারণে অ্যাক্সেস হারিয়েছে যা অভ্যন্তরীণ নিয়ন্ত্রণ প্যানেলটি ব্যবহার না করা হলে শংসাপত্রগুলি অক্ষম করে। অনেকক্ষণ).

এবং আমরা জিরা বা বিল্ড সিস্টেমের মতো আমাদের অভ্যন্তরীণ পরিষেবাগুলিতে যেতে পারিনি। একটি সমাধানের প্রয়োজন ছিল, যা আমরা কদাচিৎ ব্যবহার করি (এটিও কাজ করতে হবে)। অবশেষে, একজন প্রকৌশলী দুপুর 14:07 টায় WAF কেটে ফেলতে সক্ষম হন এবং দুপুর 14:09 টায়, ট্র্যাফিক এবং প্রসেসরের স্তর সর্বত্র স্বাভাবিক অবস্থায় ফিরে আসে। ক্লাউডফ্লেয়ারের বাকি নিরাপত্তা ব্যবস্থা স্বাভাবিক হিসাবে কাজ করেছে।

তারপরে আমরা ডাব্লুএএফ পুনরুদ্ধার করতে শুরু করি। পরিস্থিতি সাধারণের বাইরে ছিল, তাই আমরা নেতিবাচক পরীক্ষা চালিয়েছিলাম (নিজেকে জিজ্ঞাসা করে যে পরিবর্তনটি আসলেই সমস্যা ছিল কিনা) এবং ইতিবাচক পরীক্ষা (নিশ্চিত করা যে রোলব্যাক কাজ করেছে) একটি শহরে আলাদা ট্রাফিক ব্যবহার করে, সেখান থেকে অর্থপ্রদানকারী গ্রাহকদের স্থানান্তর করে।

14:52-এ আমরা নিশ্চিত হয়েছিলাম যে আমরা কারণ বুঝতে পেরেছি এবং একটি সংশোধন করেছি এবং আবার WAF সক্ষম করেছি।

ক্লাউডফ্লেয়ার কীভাবে কাজ করে

ক্লাউডফ্লেয়ারের একটি প্রকৌশলী দল রয়েছে যারা WAF-এর নিয়ম পরিচালনার জন্য নিবেদিত। তারা সনাক্তকরণের হার উন্নত করতে, মিথ্যা ইতিবাচক কমাতে এবং নতুন হুমকির আবির্ভাবের সাথে সাথে দ্রুত সাড়া দেওয়ার চেষ্টা করে। গত 60 দিনে, WAF এর জন্য পরিচালিত নিয়মগুলির জন্য 476টি পরিবর্তনের অনুরোধ প্রক্রিয়া করা হয়েছে (প্রতি 3 ঘন্টায় একটি করে)।

এই বিশেষ পরিবর্তনটি সিমুলেশন মোডে স্থাপন করা প্রয়োজন, যেখানে প্রকৃত ক্লায়েন্ট ট্র্যাফিক নিয়মের মধ্য দিয়ে যায়, কিন্তু কিছুই ব্লক করা হয় না। আমরা নিয়মের কার্যকারিতা পরীক্ষা করতে এবং মিথ্যা ইতিবাচক এবং মিথ্যা নেতিবাচক হার পরিমাপ করতে এই মোডটি ব্যবহার করি। কিন্তু এমনকি সিমুলেশন মোডেও, নিয়মগুলি অবশ্যই কার্যকর করা উচিত এবং এই ক্ষেত্রে নিয়মটিতে একটি নিয়মিত অভিব্যক্তি রয়েছে যা খুব বেশি প্রসেসর সংস্থান গ্রহণ করছে।

আপনি উপরের পরিবর্তনের অনুরোধ থেকে দেখতে পাচ্ছেন, এই ধরনের স্থাপনার জন্য আমাদের কাছে একটি স্থাপনার পরিকল্পনা, একটি রোলব্যাক পরিকল্পনা এবং একটি অভ্যন্তরীণ স্ট্যান্ডার্ড অপারেটিং পদ্ধতির (SOP) একটি লিঙ্ক রয়েছে৷ একটি নিয়ম পরিবর্তনের জন্য SOP এটিকে বিশ্বব্যাপী প্রকাশ করার অনুমতি দেয়। প্রকৃতপক্ষে, ক্লাউডফ্লেয়ারে, জিনিসগুলি সম্পূর্ণ ভিন্নভাবে করা হয়, এবং এসওপি নির্দেশ করে যে আমরা প্রথমে সফ্টওয়্যারটিকে পরীক্ষার জন্য এবং অভ্যন্তরীণ ব্যবহারের জন্য একটি অভ্যন্তরীণ অবস্থানে (পিওপি) (যা আমাদের কর্মীরা ব্যবহার করে), তারপরে অল্প সংখ্যক ক্লায়েন্টের কাছে প্রেরণ করি। একটি বিচ্ছিন্ন অবস্থান, তারপরে বিপুল সংখ্যক ক্লায়েন্টের কাছে এবং শুধুমাত্র তারপর সমগ্র বিশ্বের কাছে।

এটা কি মত দেখায়. আমরা বিটবাকেটের মাধ্যমে অভ্যন্তরীণভাবে গিট ব্যবহার করি। পরিবর্তনের বিষয়ে কাজ করা প্রকৌশলীরা কোড জমা দেন, যা টিমসিটিতে তৈরি করা হয় এবং বিল্ড পাস হয়ে গেলে পর্যালোচকদের নিয়োগ করা হয়। একবার একটি পুল অনুরোধ অনুমোদিত হলে, কোডটি একত্রিত হয় এবং একটি সিরিজ পরীক্ষা চালানো হয় (আবার)।

বিল্ড এবং পরীক্ষা সফলভাবে সম্পন্ন হলে, জিরাতে একটি পরিবর্তনের অনুরোধ তৈরি করা হয় এবং উপযুক্ত ব্যবস্থাপক বা লিডকে অবশ্যই পরিবর্তনটি অনুমোদন করতে হবে। অনুমোদনের পরে, তথাকথিত "PoP মেনাজেরি"-এ মোতায়েন ঘটে: DOG, PIG এবং হলদে (কুকুর, শূকর এবং ক্যানারি)।

DOG PoP হল একটি Cloudflare PoP (আমাদের প্রতিটি শহরের মতো) যা শুধুমাত্র Cloudflare কর্মীরা ব্যবহার করে। অভ্যন্তরীণ ব্যবহারের জন্য PoP আপনাকে গ্রাহকের ট্র্যাফিক সমাধানে প্রবাহিত হওয়ার আগে সমস্যাগুলি ধরতে দেয়। দরকারি জিনিস।

যদি DOG পরীক্ষা পাস হয়, কোডটি PIG (গিনিপিগ) পর্যায়ে চলে যায়। এটি হল ক্লাউডফ্লেয়ার PoP, যেখানে অল্প পরিমাণ বিনামূল্যের ক্লায়েন্ট ট্রাফিক নতুন কোডের মধ্য দিয়ে যায়।
সব ঠিক থাকলে, কোড ক্যানারিতে যায়। বিশ্বের বিভিন্ন স্থানে আমাদের তিনটি ক্যানারি PoP আছে। তাদের মধ্যে, প্রদত্ত এবং বিনামূল্যের ক্লায়েন্টদের ট্র্যাফিক নতুন কোডের মধ্য দিয়ে যায় এবং এটি ত্রুটিগুলির জন্য শেষ চেক।

Cloudflare এ সফ্টওয়্যার রিলিজ প্রক্রিয়া

কোডটি ক্যানারিতে ঠিক থাকলে, আমরা এটি ছেড়ে দিই। কোড পরিবর্তনের উপর নির্ভর করে সমস্ত পর্যায়ে - DOG, PIG, Canary, সমগ্র বিশ্ব - কয়েক ঘন্টা বা দিন সময় নেয়৷ ক্লাউডফ্লেয়ার নেটওয়ার্ক এবং ক্লায়েন্টদের বৈচিত্র্যের কারণে, আমরা সমস্ত ক্লায়েন্টের জন্য বিশ্বব্যাপী প্রকাশের আগে কোডটি পুঙ্খানুপুঙ্খভাবে পরীক্ষা করি। কিন্তু WAF বিশেষভাবে এই প্রক্রিয়াটি অনুসরণ করে না কারণ হুমকিগুলি দ্রুত মোকাবেলা করা প্রয়োজন।

WAF হুমকি
গত কয়েক বছর ধরে, সাধারণ অ্যাপ্লিকেশনগুলিতে হুমকিতে উল্লেখযোগ্য বৃদ্ধি পেয়েছে। এটি সফ্টওয়্যার পরীক্ষার সরঞ্জামগুলির বৃহত্তর প্রাপ্যতার কারণে। উদাহরণস্বরূপ, আমরা সম্প্রতি সম্পর্কে লিখেছেন অস্পষ্ট).

উত্স: https://cvedetails.com/

খুব প্রায়ই, ধারণার একটি প্রমাণ তৈরি করা হয় এবং অবিলম্বে গিথুবে প্রকাশিত হয় যাতে অ্যাপ্লিকেশনটি রক্ষণাবেক্ষণকারী দলগুলি দ্রুত এটি পরীক্ষা করতে পারে এবং নিশ্চিত করতে পারে যে এটি পর্যাপ্তভাবে সুরক্ষিত। অতএব, ক্লাউডফ্লেয়ারের যত তাড়াতাড়ি সম্ভব নতুন আক্রমণের প্রতিক্রিয়া জানানোর ক্ষমতা প্রয়োজন যাতে গ্রাহকরা তাদের সফ্টওয়্যার ঠিক করার সুযোগ পান।

ক্লাউডফ্লেয়ার থেকে দ্রুত প্রতিক্রিয়ার একটি দুর্দান্ত উদাহরণ হল মে মাসে শেয়ারপয়েন্ট দুর্বলতার বিরুদ্ধে সুরক্ষার রোলআউট (এখানে পড়ুন) ঘোষণাগুলি হওয়ার প্রায় সঙ্গে সঙ্গে, আমরা আমাদের গ্রাহকদের SharePoint ইনস্টলেশনের দুর্বলতা কাজে লাগানোর জন্য বিপুল সংখ্যক প্রচেষ্টা লক্ষ্য করেছি৷ আমাদের ছেলেরা ক্রমাগত নতুন হুমকি পর্যবেক্ষণ করছে এবং আমাদের গ্রাহকদের রক্ষা করার জন্য নিয়ম লিখছে।

বৃহস্পতিবার যে নিয়মটি সমস্যা সৃষ্টি করেছিল তা ক্রস-সাইট স্ক্রিপ্টিং (এক্সএসএস) থেকে রক্ষা করার কথা ছিল। সাম্প্রতিক বছরগুলোতে এ ধরনের হামলার ঘটনাও অনেক বেশি হয়েছে।

উত্স: https://cvedetails.com/

একটি WAF এর জন্য একটি পরিচালিত নিয়ম পরিবর্তন করার জন্য আদর্শ পদ্ধতি হল বিশ্বব্যাপী স্থাপনার আগে একটানা ইন্টিগ্রেশন (CI) পরীক্ষা করা। গত বৃহস্পতিবার আমরা এটি করেছি এবং নিয়ম চালু করেছি। 13:31 pm এ, একজন প্রকৌশলী একটি পরিবর্তন সহ একটি অনুমোদিত পুল অনুরোধ জমা দিয়েছেন।

13:37 এ টিমসিটি নিয়ম সংগ্রহ করেছে, পরীক্ষা চালিয়েছে এবং এগিয়ে দিয়েছে। WAF টেস্ট স্যুট WAF এর মূল কার্যকারিতা পরীক্ষা করে এবং পৃথক ফাংশনের জন্য প্রচুর সংখ্যক ইউনিট পরীক্ষা নিয়ে গঠিত। ইউনিট পরীক্ষার পর, আমরা বিপুল সংখ্যক HTTP অনুরোধের সাথে WAF নিয়মগুলি পরীক্ষা করেছি। HTTP অনুরোধগুলি পরীক্ষা করে যে কোন অনুরোধগুলি WAF দ্বারা ব্লক করা উচিত (আক্রমণকে বাধা দেওয়ার জন্য) এবং কোন অনুরোধগুলিকে পাস করার অনুমতি দেওয়া উচিত (যার জন্য একটি সারিতে সবকিছু ব্লক না করা এবং মিথ্যা ইতিবাচক এড়াতে)। কিন্তু আমরা অত্যধিক সিপিইউ ব্যবহারের জন্য পরীক্ষা চালাইনি, এবং পূর্ববর্তী WAF বিল্ডগুলির লগগুলি দেখলে দেখায় যে নিয়মের সাথে পরীক্ষা চালানোর সময় বাড়েনি, এবং এটি সন্দেহ করা কঠিন যে যথেষ্ট সংস্থান থাকবে না। .

পরীক্ষায় উত্তীর্ণ হয়েছে এবং TeamCity স্বয়ংক্রিয়ভাবে পরিবর্তনটি 13:42 p.m. এ স্থাপন করা শুরু করেছে।

ক্ষিপ্র

WAF নিয়মগুলি অবিলম্বে হুমকির প্রতিকারের উপর ফোকাস করে, তাই আমরা Quicksilver-এর বিতরণ করা কী-ভ্যালু স্টোর ব্যবহার করে সেগুলি স্থাপন করি, যা সেকেন্ডের মধ্যে বিশ্বব্যাপী পরিবর্তনগুলি প্রচার করে। আমাদের সমস্ত ক্লায়েন্ট এই প্রযুক্তি ব্যবহার করে যখন তারা ড্যাশবোর্ডে বা API এর মাধ্যমে কনফিগারেশন পরিবর্তন করে, এবং এটিকে ধন্যবাদ যে আমরা বিদ্যুতের গতিতে পরিবর্তনের প্রতিক্রিয়া জানাই।

আমরা কুইকসিলভার সম্পর্কে বেশি কথা বলিনি। আগে আমরা ব্যবহার করতাম কিয়োটো টাইকুন একটি বিশ্বব্যাপী বিতরণ করা মূল-মূল্যের দোকান হিসাবে, কিন্তু এটির সাথে অপারেশনাল সমস্যা ছিল এবং আমরা আমাদের নিজস্ব স্টোর লিখেছি, 180 টিরও বেশি শহরে প্রতিলিপি করা হয়েছে৷ আমরা এখন ক্লায়েন্টদের কনফিগারেশন পরিবর্তন করতে, WAF নিয়ম আপডেট করতে এবং ক্লাউডফ্লেয়ার কর্মীদের কাছে ক্লায়েন্টদের দ্বারা লেখা জাভাস্ক্রিপ্ট কোড বিতরণ করতে Quicksilver ব্যবহার করি।

একটি ড্যাশবোর্ডে একটি বোতামে ক্লিক করা বা একটি API কল করা থেকে শুরু করে বিশ্বজুড়ে একটি কনফিগারেশন পরিবর্তন করা পর্যন্ত, এটি মাত্র কয়েক সেকেন্ড সময় নেয়৷ গ্রাহকরা সেটআপের এই গতি পছন্দ করেন। এবং শ্রমিকরা তাদের কাছে তাত্ক্ষণিক বিশ্বব্যাপী সফ্টওয়্যার স্থাপনা সরবরাহ করে। গড়ে, Quicksilver প্রতি সেকেন্ডে প্রায় 350টি পরিবর্তন প্রচার করে।

এবং Quicksilver খুব দ্রুত. গড়ে, আমরা বিশ্বব্যাপী প্রতিটি কম্পিউটারে পরিবর্তনগুলি প্রচার করতে 99 সেকেন্ডের 2,29 তম পার্সেন্টাইল অর্জন করেছি৷ গতি সাধারণত একটি ভাল জিনিস। সর্বোপরি, আপনি যখন একটি ফাংশন সক্ষম করেন বা ক্যাশে সাফ করেন, এটি প্রায় তাত্ক্ষণিকভাবে এবং সর্বত্র ঘটে। ক্লাউডফ্লেয়ার ওয়ার্কারদের মাধ্যমে কোড পাঠানো একই গতিতে ঘটে। ক্লাউডফ্লেয়ার তার গ্রাহকদের সঠিক সময়ে দ্রুত আপডেট দেওয়ার প্রতিশ্রুতি দেয়।

কিন্তু এই ক্ষেত্রে, গতি আমাদের উপর একটি নিষ্ঠুর রসিকতা খেলেছে, এবং নিয়ম কয়েক সেকেন্ডের মধ্যে সর্বত্র পরিবর্তিত হয়েছে। আপনি হয়তো লক্ষ্য করেছেন যে WAF কোড Lua ব্যবহার করে। ক্লাউডফ্লেয়ার উত্পাদন এবং বিবরণে ব্যাপকভাবে লুয়া ব্যবহার করে WAF এ লুয়া আমরা হলাম ইতিমধ্যে আলোচনা করা হয়েছে. Lua WAF ব্যবহার করে PCRE অভ্যন্তরীণভাবে এবং মিলের জন্য ব্যাকট্র্যাকিং প্রয়োগ করে। নিয়ন্ত্রণের বাইরে চলে যাওয়া অভিব্যক্তি থেকে রক্ষা করার জন্য এটির কোন ব্যবস্থা নেই। নীচে আমি এই সম্পর্কে আরও কথা বলব এবং আমরা এটি সম্পর্কে কী করছি।

নিয়মগুলি মোতায়েন করার আগে, সবকিছু মসৃণভাবে চলছিল: পুল অনুরোধ তৈরি করা হয়েছিল এবং অনুমোদিত হয়েছিল, CI/CD পাইপলাইন কোডটি সংগ্রহ এবং পরীক্ষা করেছিল, পরিবর্তনের অনুরোধটি এসওপি অনুসারে জমা দেওয়া হয়েছিল যা স্থাপনা এবং রোলব্যাককে নিয়ন্ত্রণ করে, এবং স্থাপনা সম্পন্ন হয়েছিল।

ক্লাউডফ্লেয়ার ডাব্লুএএফ স্থাপনার প্রক্রিয়া

কিছু ভুল হয়েছে
আমি যেমন বলেছি, আমরা প্রতি সপ্তাহে কয়েক ডজন নতুন WAF নিয়ম মোতায়েন করি, এবং এই ধরনের স্থাপনার নেতিবাচক পরিণতি থেকে রক্ষা করার জন্য আমাদের কাছে অনেক সিস্টেম রয়েছে। এবং যখন কিছু ভুল হয়ে যায়, এটি সাধারণত একবারে বেশ কয়েকটি পরিস্থিতির সংমিশ্রণ হয়। আপনি যদি কেবল একটি কারণ খুঁজে পান তবে এটি অবশ্যই আশ্বস্ত, তবে এটি সর্বদা সত্য নয়। এই কারণগুলি একসাথে আমাদের HTTP/HTTPS পরিষেবার ব্যর্থতার দিকে পরিচালিত করে৷

1. একজন প্রকৌশলী একটি নিয়মিত অভিব্যক্তি লিখেছেন যার ফলে অতিরিক্ত হতে পারে ব্যাকট্র্যাকিং.
2. একটি বৈশিষ্ট্য যা রেগুলার এক্সপ্রেশনকে অত্যধিক সিপিইউ নষ্ট করা থেকে বিরত রাখতে পারে তা ভুলবশত WAF এর একটি রিফ্যাক্টরিংয়ে বেশ কয়েক সপ্তাহ আগে সরিয়ে দেওয়া হয়েছিল- WAF যাতে কম সম্পদ ব্যবহার করে তার জন্য রিফ্যাক্টরিংয়ের প্রয়োজন ছিল।
3. রেগুলার এক্সপ্রেশন ইঞ্জিনের কোন জটিলতার গ্যারান্টি ছিল না।
4. পরীক্ষা স্যুট অত্যধিক CPU খরচ সনাক্ত করতে পারে না.
5. এসওপি অ-জরুরি নিয়ম পরিবর্তনগুলিকে বহু-পদক্ষেপ প্রক্রিয়া ছাড়াই বিশ্বব্যাপী চালু করার অনুমতি দেয়।
6. রোলব্যাক প্ল্যানের জন্য দুবার একটি সম্পূর্ণ WAF বিল্ডের প্রয়োজন, যা দীর্ঘ সময়।
7. বিশ্বব্যাপী ট্র্যাফিক সমস্যা সম্পর্কে প্রথম সতর্কতা খুব দেরিতে শুরু হয়েছিল।
8. আমরা স্ট্যাটাস পেজ আপডেট করতে একটু সময় নিয়েছি।
9. একটি ত্রুটির কারণে আমাদের সিস্টেমগুলি অ্যাক্সেস করতে সমস্যা হয়েছিল এবং বাইপাস পদ্ধতিটি ভালভাবে প্রতিষ্ঠিত হয়নি।
10. SREs কিছু সিস্টেমে অ্যাক্সেস হারিয়েছে কারণ তাদের শংসাপত্র নিরাপত্তার কারণে মেয়াদ শেষ হয়ে গেছে।
11. আমাদের গ্রাহকদের ক্লাউডফ্লেয়ার ড্যাশবোর্ড বা API-তে অ্যাক্সেস ছিল না কারণ তারা ক্লাউডফ্লেয়ার অঞ্চলের মধ্য দিয়ে যায়।

গত বৃহস্পতিবার থেকে কী পরিবর্তন হয়েছে

প্রথমত, আমরা WAF এর জন্য রিলিজের সমস্ত কাজ সম্পূর্ণরূপে বন্ধ করে দিয়েছি এবং নিম্নলিখিতগুলি করি:

1. প্রসেসর সংস্থানগুলির অত্যধিক ব্যবহারের বিরুদ্ধে সুরক্ষা পুনরায় চালু করা, যা আমরা সরিয়ে দিয়েছি। (প্রস্তুত)
2. অত্যধিক ব্যাকট্র্যাকিংয়ের অন্যান্য সম্ভাব্য কেসগুলি খুঁজে পেতে এবং সংশোধন করতে WAF-এর পরিচালিত নিয়মগুলিতে ম্যানুয়ালি সমস্ত 3868 নিয়মগুলি পরীক্ষা করা হচ্ছে। (যাচাই সম্পন্ন)
3. আমরা পরীক্ষার সেটে সমস্ত নিয়মের জন্য কর্মক্ষমতা প্রোফাইলিং অন্তর্ভুক্ত করি। (প্রত্যাশিত: জুলাই 19)
4. রেগুলার এক্সপ্রেশন ইঞ্জিনে স্যুইচ করা হচ্ছে re2 বা জং - উভয়ই রানটাইম গ্যারান্টি প্রদান করে। (প্রত্যাশিত: জুলাই 31)
5. আমরা ক্লাউডফ্লেয়ারের অন্যান্য সফ্টওয়্যারগুলির মতো পর্যায়ক্রমে নিয়ম স্থাপনের জন্য SOP পুনরায় লিখছি, তবে আক্রমণ ইতিমধ্যে শুরু হয়ে গেলে একই সাথে জরুরি বৈশ্বিক স্থাপনার ক্ষমতা রয়েছে।
6. আমরা ক্লাউডফ্লেয়ার অঞ্চল থেকে জরুরীভাবে ক্লাউডফ্লেয়ার ড্যাশবোর্ড এবং API সরানোর ক্ষমতা বিকাশ করছি।
7. স্বয়ংক্রিয় পৃষ্ঠা রিফ্রেশ ক্লাউডফ্লেয়ার স্ট্যাটাস.

দীর্ঘমেয়াদে, আমরা কয়েক বছর আগে যে লুয়া WAF লিখেছিলাম তা থেকে আমরা দূরে সরে যাচ্ছি। WAF এ সরানো হচ্ছে নতুন ফায়ারওয়াল সিস্টেম. সুতরাং WAF দ্রুত হবে এবং সুরক্ষার একটি অতিরিক্ত স্তর পাবে।

উপসংহার

এই ব্যর্থতা আমাদের এবং আমাদের গ্রাহকদের জন্য সমস্যা সৃষ্টি করেছে। আমরা পরিস্থিতি সংশোধন করার জন্য দ্রুত সাড়া দিয়েছি এবং বর্তমানে ক্র্যাশের কারণ হওয়া প্রক্রিয়াগুলির ত্রুটিগুলি নিয়ে কাজ করছি, সেইসাথে নতুন প্রযুক্তিতে স্থানান্তরিত করে ভবিষ্যতে সম্ভাব্য রেজেক্স সমস্যাগুলি থেকে রক্ষা করার জন্য আরও গভীর খনন করছি৷

আমরা এই ব্যর্থতার জন্য খুব লজ্জিত এবং আমরা আমাদের গ্রাহকদের কাছে ক্ষমাপ্রার্থী। আশা করি, এই পরিবর্তনগুলি নিশ্চিত করবে যে এটি আবার ঘটবে না।

আবেদন। নিয়মিত অভিব্যক্তি ব্যাকট্র্যাকিং

কিভাবে অভিব্যক্তি বুঝতে:

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

সমস্ত সিপিইউ রিসোর্স খেয়ে ফেলেছে, স্ট্যান্ডার্ড রেগুলার এক্সপ্রেশন ইঞ্জিন কীভাবে কাজ করে সে সম্পর্কে আপনাকে কিছুটা জানতে হবে। এখানে সমস্যা হল প্যাটার্ন .*(?:.*=.*). (?: এবং সংশ্লিষ্ট ) একটি নন-ক্যাপচারিং গ্রুপ (অর্থাৎ, বন্ধনীতে অভিব্যক্তিটি একক অভিব্যক্তি হিসাবে গোষ্ঠীবদ্ধ)।

প্রসেসর সম্পদের অত্যধিক খরচ প্রসঙ্গে, এই প্যাটার্ন হিসাবে মনোনীত করা যেতে পারে .*.*=.*. এই ফর্মে, প্যাটার্নটি অপ্রয়োজনীয়ভাবে জটিল দেখায়। কিন্তু আরও গুরুত্বপূর্ণ, বাস্তব জগতে, এই ধরনের অভিব্যক্তি (WAF নিয়মে জটিল অভিব্যক্তির মতো) যেগুলি ইঞ্জিনকে একটি খণ্ডের সাথে মিল করতে বলে এবং অন্য একটি খণ্ড দ্বারা অনুসরণ করে বিপর্যয়কর ব্যাকট্র্যাকিং হতে পারে। আর এই কারণে.

নিয়মিত অভিব্যক্তিতে . মানে এক অক্ষরের সাথে মিলে যাওয়া, .* - শূন্য বা তার বেশি অক্ষর "লোভের সাথে" মেলে, অর্থাৎ সর্বাধিক অক্ষর ক্যাপচার করা, যাতে .*.*=.* মানে শূন্য বা তার বেশি অক্ষর মেলে, তারপর শূন্য বা তার বেশি অক্ষর মেলে, আক্ষরিক = অক্ষর খুঁজুন, শূন্য বা তার বেশি অক্ষর মেলে।

পরীক্ষার লাইন নেওয়া যাক x=x. এটি অভিব্যক্তির সাথে মিলে যায় .*.*=.*. .*.* সমান চিহ্ন পর্যন্ত প্রথমটির সাথে মেলে x (দলগুলির মধ্যে একটি .* অনুরূপ x, এবং দ্বিতীয় - শূন্য অক্ষর)। .* after = শেষ ম্যাচ 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 এক্স পরে =, ইঞ্জিনটি 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.

চিত্রে। 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