פרטים על הפסקת Cloudflare ב-2 ביולי 2019

לפני כמעט 9 שנים Cloudflare הייתה חברה זעירה, ולא עבדתי בה, הייתי רק לקוח. חודש לאחר השקת Cloudflare, קיבלתי הודעה שהאתר שלי jgc.orgנראה שה-DNS לא עובד. Cloudflare ביצעה שינוי ב חוצצי פרוטוקול, והיה DNS שבור.

מיד כתבתי למתיו פרינס עם הכותרת "איפה ה-DNS שלי?" והוא שלח בחזרה תשובה ארוכה מלאה בפרטים טכניים (קרא את כל ההתכתבות כאן), ועליו השבתי:

מאת: ג'ון גרהם-קאמינג
תאריך: 7 באוקטובר 2010, 9:14
נושא: Re: איפה ה-DNS שלי?
אל: מתיו פרינס

דיווח מגניב, תודה. אני בהחלט אתקשר אם יהיו בעיות. כנראה שכדאי לכתוב על זה פוסט לאחר שאספתם את כל המידע הטכני. אני חושב שאנשים ייהנו מסיפור פתוח וכנה. במיוחד אם אתה מצרף אליו גרפים כדי להראות כיצד התנועה גדלה מאז ההשקה.

יש לי ניטור טוב באתר שלי, ואני מקבל הודעת SMS על כל תקלה. מהניטור עולה כי התקלה אירעה מ-13:03:07 עד 14:04:12. בדיקות מבוצעות כל חמש דקות.

אני בטוח שתבין את זה. האם אתה בטוח שאתה לא צריך אדם משלך באירופה? 🙂

והוא ענה:

מאת: מתיו פרינס
תאריך: 7 באוקטובר 2010, 9:57
נושא: Re: איפה ה-DNS שלי?
אל: ג'ון גרהם-קאמינג

תודה. הגבנו לכל מי שכתב. אני בדרך למשרד עכשיו ונכתוב משהו בבלוג או נצמד פוסט רשמי ללוח המודעות שלנו. אני מסכים לחלוטין, כנות היא הכל.

עכשיו Cloudflare היא חברה ממש גדולה, אני עובד בה, ועכשיו אני צריך לכתוב בגלוי על הטעות שלנו, ההשלכות שלה והפעולות שלנו.

אירועים של 2 ביולי

ב-2 ביולי השקנו כלל חדש ב-Managed Rules for WAFs בשל כך משאבי המעבד אזלו על כל ליבת מעבד המעבד תעבורת HTTP/HTTPS ברשת Cloudflare ברחבי העולם. אנו משפרים כל הזמן חוקים מנוהלים עבור WAFs בתגובה לפרצות ואיומים חדשים. במאי, למשל, מיהרנו הוסף כללכדי להגן מפני פגיעות חמורה ב-SharePoint. כל הפואנטה של ​​ה-WAF שלנו היא היכולת לפרוס חוקים במהירות ובגלובליות.

למרבה הצער, העדכון של יום חמישי האחרון הכיל ביטוי רגולרי שבזבז יותר מדי משאבי מעבד HTTP/HTTPS על מעקב לאחור. פונקציות ה-Proxy הליבה, CDN ו-WAF שלנו סבלו כתוצאה מכך. הגרף מראה שמשאבי מעבד להגשת תעבורת HTTP/HTTPS מגיעים לכמעט 100% בשרתים ברשת שלנו.

שימוש במעבד בנקודת נוכחות אחת במהלך תקרית

כתוצאה מכך, הלקוחות שלנו (ולקוחות הלקוחות שלנו) קיבלו דף שגיאה 502 בדומיינים של Cloudflare. שגיאות 502 נוצרו על ידי שרתי אינטרנט קדמיים של Cloudflare שעדיין היו להם ליבות פנויות אך לא היו מסוגלים לתקשר עם תהליכים המטפלים בתעבורת HTTP/HTTPS.

אנחנו יודעים כמה אי נוחות זה גרם ללקוחות שלנו. אנחנו נורא מתביישים. והכשל הזה מנע מאיתנו להתמודד ביעילות עם האירוע.

אם היית אחד מהלקוחות האלה, כנראה היית מפחד, כועס וכועס. יתר על כן, לא היה לנו א שיבושים גלובליים. צריכת ה-CPU הגבוהה נבעה מכלל WAF אחד עם ביטוי רגולרי מנוסח בצורה גרועה שהביאה לעקיבה לאחור מוגזמת. הנה הביטוי האשם: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))

אמנם זה מעניין בפני עצמו (ואני אדבר על זה ביתר פירוט בהמשך), שירות Cloudflare היה מושבת למשך 27 דקות לא רק בגלל ביטוי רגולרי גרוע. לקח לנו זמן לתאר את השתלשלות האירועים שהובילה לכשל, ולכן איחרנו להגיב. בסוף הפוסט אתאר את החזרה לאחור בביטוי רגיל ואומר לכם מה לעשות עם זה.

מה קרה

בואו נתחיל לפי הסדר. כל הזמנים כאן הם ב-UTC.

בשעה 13:42, מהנדס בצוות חומת האש ביצע שינוי קטן בכללי הזיהוי XSS באמצעות תהליך אוטומטי. בהתאם לכך, נוצר כרטיס בקשת שינוי. אנחנו מנהלים כרטיסים כאלה דרך Jira (צילום מסך למטה).

לאחר 3 דקות הופיע העמוד הראשון של PagerDuty, ודיווח על בעיה ב-WAF. זה היה בדיקה סינתטית שבודקת את הפונקציונליות של WAFs (יש לנו מאות כאלה) מחוץ ל-Cloudflare כדי לנטר פעולה רגילה. מיד לאחר מכן הגיעו דפי התראות על בדיקות שירות מקצה לקצה אחרות של Cloudflare שנכשלו, בעיות תעבורה גלובליות, שגיאות 502 נפוצות והמון דיווחים מנקודות הנוכחות שלנו (PoP) בערים ברחבי העולם שהצביעו על חוסר של משאבי מעבד.

קיבלתי כמה מההתראות האלה, יצאתי בסערה מפגישה והייתי בדרכי לשולחן כשראש מחלקת פיתוח הפתרונות שלנו אמר שאיבדנו 80% מהתנועה שלנו. רצתי למהנדסי SRE שלנו, שכבר עבדו על הבעיה. בהתחלה חשבנו שזה סוג של התקפה לא ידועה.

מהנדסי Cloudflare SRE פזורים ברחבי העולם ועוקבים אחר המצב מסביב לשעון. בדרך כלל, התראות אלו מודיעות לך על בעיות מקומיות ספציפיות בהיקף מוגבל, עוקבות אחר לוחות מחוונים פנימיים ונפתרות מספר פעמים ביום. אבל הדפים וההודעות האלה הצביעו על משהו רציני באמת, ומהנדסי SRE הכריזו מיד על רמת החומרה P0 ויצרו קשר עם מהנדסי ההנהלה והמערכת.

המהנדסים שלנו בלונדון האזינו להרצאה באולם המרכזי באותו רגע. היה צריך להפסיק את ההרצאה, כולם התאספו בחדר ישיבות גדול, והוזעקו מומחים נוספים. זו לא הייתה בעיה טיפוסית שאנשי SRE יכלו להתמודד איתה בעצמם. היה דחוף לערב את המומחים הנכונים.

בשעה 14:00 קבענו שהבעיה היא ב-WAF ולא הייתה תקיפה. צוות הביצועים משך את נתוני המעבד והתברר שה-WAF אשם. עובד אחר אישר את התיאוריה הזו באמצעות strace. מישהו אחר ראה ביומנים שיש בעיה עם WAF. בשעה 14:02, כל הצוות הגיע אלי כשהציעו להשתמש ב- global kill, מנגנון המובנה ב-Cloudflare שמכבה רכיב אחד ברחבי העולם.

איך עשינו הרג גלובלי עבור WAF זה סיפור אחר. זה לא כל כך פשוט. אנו משתמשים במוצרים שלנו, ומאז השירות שלנו גִישָׁה לא עבד, לא הצלחנו לאמת ולהיכנס ללוח הבקרה הפנימי (כשהכל תוקן, למדנו שחלק מחברי הצוות איבדו גישה עקב תכונת אבטחה שמנטרלת אישורים אם לוח הבקרה הפנימי אינו משמש עבור הרבה זמן).

ולא יכולנו להגיע לשירותים הפנימיים שלנו, כמו Jira או מערכת הבנייה. היינו צריכים מנגנון עוקף, שבו השתמשנו לעתים רחוקות (גם את זה צריך לפתור). לבסוף, מהנדס אחד הצליח להשבית את ה-WAF בשעה 14:07, ובשעה 14:09, רמות התעבורה והמעבד חזרו לקדמותו בכל מקום. שאר מנגנוני ההגנה של Cloudflare פעלו כרגיל.

ואז התחלנו לשחזר את ה-WAF. המצב היה יוצא דופן, אז הרצנו בדיקות שליליות (ששאלנו את עצמנו אם השינוי הוא באמת הבעיה) ובדיקות חיוביות (לוודא שהחזרה עובדת) בעיר אחת תוך שימוש בתנועה נפרדת, תוך העברת לקוחות משלמים משם.

בשעה 14:52 השתכנענו שהבנו את הסיבה ועשינו תיקון, ואפשרנו את WAF שוב.

איך Cloudflare עובד

ל-Cloudflare צוות מהנדסים המוקדש לניהול כללים עבור WAFs. הם שואפים לשפר את שיעורי הזיהוי, להפחית תוצאות חיוביות כוזבות ולהגיב במהירות לאיומים חדשים כשהם מופיעים. ב-60 הימים האחרונים, עובדו 476 בקשות לשינוי עבור כללים מנוהלים עבור WAF (בממוצע אחת כל 3 שעות).

צריך היה לפרוס את השינוי המסוים הזה במצב סימולציה, שבו תעבורת לקוח אמיתית עוברת דרך הכלל, אבל שום דבר לא חסום. אנו משתמשים במצב זה כדי לבדוק את האפקטיביות של הכללים ולמדוד את שיעורי החיובים השגויים והשליליים השגויים. אבל אפילו במצב סימולציה, הכללים חייבים להתבצע בפועל, ובמקרה זה הכלל הכיל ביטוי רגולרי שצורך יותר מדי משאבי מעבד.

כפי שניתן לראות מבקשת השינוי לעיל, יש לנו תוכנית פריסה, תוכנית החזרה וקישור לנוהל הפעלה סטנדרטי פנימי (SOP) עבור פריסה מסוג זה. ה-SOP לשינוי כלל מאפשר לפרסם אותו ברחבי העולם. למעשה, ב-Cloudflare הדברים נעשים אחרת לגמרי, וה-SOP מכתיב שקודם כל נשלח את התוכנה לבדיקה ושימוש פנימי לנקודת נוכחות פנימית (PoP) (שהעובדים שלנו משתמשים בה), ואז למספר קטן של לקוחות ב מיקום מבודד, אחר כך למספר רב של לקוחות, ורק אז לכל העולם.

כך זה נראה. אנו משתמשים ב-git באופן פנימי באמצעות BitBucket. מהנדסים שעובדים על שינויים מגישים קוד, אשר מורכב לתוך TeamCity, וכאשר ה-build עובר, סוקרים מוקצים. לאחר אישור בקשת משיכה, הקוד מורכב ומופעלת (שוב) סדרת בדיקות.

אם הבנייה והבדיקות מסתיימות בהצלחה, נוצרת בקשת שינוי ב-Jira והמנהל או ההובלה המתאימים חייבים לאשר את השינוי. לאחר האישור, הפריסה מתרחשת במה שנקרא "מנג'רי PoP": DOG, PIG ו כנרית (כלב, חזיר וקנרית).

DOG PoP הוא Cloudflare PoP (כמו כל אחת מהערים שלנו) המשמש רק עובדי Cloudflare. PoP לשימוש פנימי מאפשר לך לתפוס בעיות לפני שתעבורת לקוחות מתחילה לזרום לפתרון. דבר שימושי.

אם מבחן ה-DOG מצליח, הקוד עובר לשלב PIG (שפן ניסיונות). זהו Cloudflare PoP, שבו כמות קטנה של תעבורת לקוחות בחינם זורמת דרך קוד חדש.
אם הכל בסדר, הקוד נכנס לקנרי. יש לנו שלושה PoPs Canary בחלקים שונים של העולם. בהם עוברת התעבורה של לקוחות בתשלום וחינמי דרך הקוד החדש, וזוהי הבדיקה האחרונה לאיתור שגיאות.

תהליך שחרור תוכנה ב-Cloudflare

אם הקוד בסדר בקנרי, נשחרר אותו. לעבור על כל השלבים - 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 (כדי ליירט את המתקפה) ואילו ניתן לאפשר לעבור (כדי לא לחסום הכל ולהימנע מתוצאות שגויות). אבל לא בדקנו שימוש מופרז ב-CPU, ובחינת היומנים של בניית WAF קודמת מראה שזמן ביצוע בדיקת החוקים לא גדל, והיה קשה לחשוד שלא יהיו מספיק משאבים.

הבדיקות עברו ו-TeamCity החלה לפרוס אוטומטית את השינוי בשעה 13:42.

כַּספִּית

כללי WAF מתמקדים בתיקון איומים מיידי, ולכן אנו פורסים אותם באמצעות מאגר ערך המפתח המבוזר של קוויקסילבר, אשר מפיץ שינויים גלובליים בשניות. כל הלקוחות שלנו משתמשים בטכנולוגיה הזו כשהם משנים את התצורה בלוח המחוונים או דרך ה-API, ובזכותה אנחנו מגיבים לשינויים במהירות הבזק.

לא דיברנו הרבה על קוויקסילבר. בעבר השתמשנו טייקון קיוטו כחנות בעלת ערך מפתח הפצה גלובלית, אבל היו איתה בעיות תפעוליות, וכתבנו חנות משלנו, משוכפלת ביותר מ-180 ערים. כעת אנו משתמשים ב-Quicksilver כדי לדחוף שינויים בתצורה ללקוחות, לעדכן כללי WAF ולהפיץ קוד JavaScript שנכתב על ידי לקוחות ל-Cloudflare Workers.

זה לוקח רק כמה שניות מלחיצה על כפתור בלוח המחוונים או קריאה ל-API ועד ביצוע שינוי תצורה ברחבי העולם. לקוחות אהבו את מהירות ההגדרה הזו. ו-Workers נותן להם פריסת תוכנה גלובלית כמעט מיידית. בממוצע, קוויקסילבר מפיצה כ-350 שינויים בשנייה.

וקוויקסילבר מהיר מאוד. בממוצע, השגנו את האחוזון ה-99 של 2,29 שניות כדי להפיץ שינויים לכל מחשב ברחבי העולם. מהירות היא בדרך כלל דבר טוב. אחרי הכל, כשאתה מפעיל פונקציה או מנקה את המטמון, זה קורה כמעט באופן מיידי ובכל מקום. שליחת קוד דרך Cloudflare Workers מתרחשת באותה מהירות. Cloudflare מבטיחה ללקוחותיה עדכונים מהירים בזמן הנכון.

אבל במקרה הזה, המהירות שיחקה עלינו בדיחה אכזרית, והחוקים השתנו בכל מקום תוך שניות בודדות. אולי שמתם לב שקוד WAF משתמש ב-Lua. Cloudflare משתמש ב-Lua באופן נרחב בייצור ובפרטים לואה ב-WAF אנחנו כבר דנו. Lua WAF משתמש PCRE באופן פנימי ומחיל מעקב לאחור לצורך התאמה. אין לו מנגנונים להגנה מפני ביטויים שיוצאים משליטה. להלן אדבר יותר על זה ומה אנחנו עושים בנידון.

לפני פריסת הכללים, הכל הלך חלק: בקשת המשיכה נוצרה ואושרה, צינור ה-CI/CD אסף ובדק את הקוד, בקשת השינוי הוגשה לפי ה-SOP שקובע את הפריסה והחזרה, והפריסה הושלמה.

תהליך פריסת WAF של Cloudflare

משהו השתבש
כפי שאמרתי, אנו פורסים עשרות כללי WAF חדשים מדי שבוע, ויש לנו מערכות רבות כדי להגן מפני ההשלכות השליליות של פריסה כזו. וכשמשהו משתבש, זה בדרך כלל שילוב של כמה נסיבות בבת אחת. אם אתה מוצא רק סיבה אחת, זה, כמובן, מרגיע, אבל זה לא תמיד נכון. אלו הסיבות שביחד הובילו לכישלון שירות ה-HTTP/HTTPS שלנו.

1. מהנדס כתב ביטוי רגולרי שעלול לגרום להגזמה חזרה לאחור.
2. תכונה שיכולה הייתה למנוע מהביטוי הרגולרי לבזבז יותר מדי מעבד הוסרה בטעות ב-refactoring של ה-WAF מספר שבועות קודם לכן - ה-refactoring היה נחוץ כדי לגרום ל-WAF לצרוך פחות משאבים.
3. למנוע הביטוי הרגולרי לא היו ערבויות מורכבות.
4. חבילת הבדיקה לא הצליחה לזהות צריכת מעבד מוגזמת.
5. ה-SOP מאפשר להחיל שינויים כללים לא דחופים ברחבי העולם ללא תהליך רב-שלבי.
6. תוכנית ההחזרה לאחור דרשה להפעיל מבנה WAF מלא פעמיים, מה שנמשך זמן רב.
7. ההתראה הראשונה על בעיות תעבורה גלובליות הופעלה מאוחר מדי.
8. לקח לנו זמן לעדכן את דף הסטטוס.
9. היו לנו בעיות בגישה למערכות עקב תקלה, ונוהל העקיפה לא היה מבוסס היטב.
10. מהנדסי SRE איבדו גישה למערכות מסוימות מכיוון שתוקף האישורים שלהם פג מסיבות אבטחה.
11. ללקוחות שלנו לא הייתה גישה ללוח המחוונים או ל-API של Cloudflare מכיוון שהם עוברים אזור של Cloudflare.

מה השתנה מאז יום חמישי שעבר

ראשית, הפסקנו לחלוטין את כל העבודה על מהדורות עבור WAF ועושים את הפעולות הבאות:

1. אנו מציגים מחדש את הגנת שימוש יתר במעבד שהסרנו. (מוּכָן)
2. בדיקה ידנית של כל 3868 הכללים בכללים המנוהלים עבור ה-WAF כדי למצוא ולתקן מקרים פוטנציאליים אחרים של חזרה לאחור מוגזמת. (האימות הושלם)
3. אנו כוללים פרופיל ביצועים עבור כל הכללים במערך הבדיקות. (צפוי: 19 ביולי)
4. מעבר למנוע ביטוי רגיל Re2 או חלודה - שניהם מספקים ערבויות זמן ריצה. (צפוי: 31 ביולי)
5. אנו משכתבים את ה-SOP כדי לפרוס כללים בשלבים, כמו תוכנות אחרות ב-Cloudflare, אך במקביל יש לנו את היכולת לפרוס עולמי חירום אם כבר החלו התקפות.
6. אנו מפתחים את היכולת להסיר בדחיפות את לוח המחוונים ואת ה-API של Cloudflare מאזור Cloudflare.
7. אוטומציה של עדכוני דפים מצב Cloudflare.

לטווח ארוך אנחנו מתרחקים מה-Lua WAF שכתבתי לפני כמה שנים. העברת WAF ל מערכת חומת אש חדשה. כך ה-WAF יהיה מהיר יותר ויקבל רמת הגנה נוספת.

מסקנה

כישלון זה גרם לנו וללקוחותינו צרות. פעלנו במהירות כדי לתקן את המצב וכעת עובדים על הפגמים בתהליכים שגרמו לקריסה, כמו גם חפירה עמוקה עוד יותר כדי להתגונן מפני בעיות פוטנציאליות בביטויים רגולריים בעתיד בעת הגירה לטכנולוגיה חדשה.

אנחנו מאוד נבוכים מההפסקה הזו ומתנצלים בפני הלקוחות שלנו. אנו מקווים שהשינויים הללו יבטיחו שדבר כזה לא יקרה שוב.

יישום. חזרה לאחור של ביטויים רגולריים

כדי להבין איך הביטוי:

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

אכל את כל משאבי המעבד, אתה צריך לדעת קצת על איך פועל מנוע הביטוי הרגיל הסטנדרטי. הבעיה כאן היא הדפוס .*(?:.*=.*). (?: ומתאים ) היא קבוצה שאינה לוכדת (כלומר, הביטוי בסוגריים מקובץ כביטוי בודד).

בהקשר של צריכת CPU מוגזמת, ניתן לתאר דפוס זה כ .*.*=.*. בצורה זו, הדפוס נראה מורכב שלא לצורך. אבל חשוב מכך, בעולם האמיתי, ביטויים (כמו ביטויים מורכבים בכללי WAF) המבקשים מהמנוע להתאים לפרגמנט ואחריו פרגמנט אחר עלולים להוביל לעקיבה קטסטרופלית. וזה למה.

בביטוי רגיל . אומר שאתה צריך להתאים דמות אחת, .* - התאם אפס או יותר תווים "בתאווה", כלומר, לכידת מקסימום תווים, כך .*.*=.* פירושו התאמת אפס או יותר תווים, ואז התאם אפס או יותר תווים, מצא את התו המילולי =, התאם אפס או יותר תווים.

בוא ניקח את קו המבחן x=x. זה מתאים לביטוי .*.*=.*. .*.* לפני שסימן השוויון מתאים לראשון x (אחת הקבוצות .* מתאים x, והשני - אפס תווים). .* אחרי = משחקים אחרונים x.

השוואה זו דורשת 23 שלבים. קבוצה ראשונה .* в .*.*=.* פועל בחמדנות ומתאים לכל המיתר x=x. המנוע עובר לקבוצה הבאה .*. אין לנו עוד דמויות להתאים, אז הקבוצה השנייה .* תואם אפס תווים (זה מותר). ואז המנוע נע אל השלט =. אין יותר סמלים (קבוצה ראשונה .* השתמש בכל הביטוי x=x), לא מתרחשת השוואה.

ואז מנוע הביטוי הרגולרי חוזר להתחלה. הוא עובר לקבוצה הראשונה .* ומשווה את זה с x= (במקום x=x), ולאחר מכן לוקח על עצמו את הקבוצה השנייה .*. קבוצה שניה .* מושווה לשני x, ושוב לא נשארו לנו דמויות. וכשהמנוע מגיע שוב = в .*.*=.*, כלום לא עובד. והוא חוזר שוב לאחור.

הפעם הקבוצה .* עדיין תואמים x=, אלא הקבוצה השנייה .* לא עוד x, ואפס תווים. המנוע מנסה למצוא דמות מילולית = בתבנית .*.*=.*, אבל לא יוצא (אחרי הכל, הקבוצה הראשונה כבר כבשה אותו .*). והוא חוזר שוב לאחור.

הפעם הקבוצה הראשונה .* לוקח רק את ה-X הראשון. אבל הקבוצה השנייה .* לוכד "בחמדנות". =x. כבר ניחשתם מה יקרה? המנוע מנסה להתאים את המילולי =, נכשל ועושה נסיגה נוספת.

קבוצה ראשונה .* עדיין תואם את הראשון x... השני .* לוקח רק =. כמובן, המנוע לא יכול להתאים את המילולי =, כי הקבוצה השנייה כבר עשתה זאת .*. ושוב חוזרים לאחור. ואנחנו מנסים להתאים מחרוזת של שלוש דמויות!

כתוצאה מכך, הקבוצה הראשונה .* תואם רק את הראשון x, שניה .* - עם אפס תווים, והמנוע סוף סוף תואם את המילולי = בביטוי с = בשורה. הבאה היא הקבוצה האחרונה .* מושווה לזה האחרון x.

23 שלבים בלבד עבור x=x. צפה בסרטון קצר על השימוש ב-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, כאשר קנט תומפסון כתב מאמר טכניקות תכנות: אלגוריתם חיפוש ביטוי רגולרי ("שיטות תכנות: אלגוריתם חיפוש ביטוי רגולרי"). המאמר מתאר מנגנון המאפשר להמיר ביטוי רגולרי למכונות מצב סופי לא דטרמיניסטיות, ולאחר שינויי מצב במכונות מצב סופי לא דטרמיניסטיות, השתמש באלגוריתם שזמן הביצוע שלו תלוי באופן ליניארי במחרוזת המותאמת.

שיטות תכנות
אלגוריתם חיפוש ביטוי רגולרי
קן תומפסון
Bell Telephone Laboratories, Inc., Murray Hill, New Jersey

הוא מתאר שיטה לחיפוש אחר מחרוזת ספציפית של תווים בטקסט ודן ביישום שיטה זו בצורת מהדר. המהדר לוקח את הביטוי הרגולרי כקוד מקור ומייצר את תוכנית IBM 7094 כקוד אובייקט. תוכנית האובייקט לוקחת קלט בצורה של טקסט חיפוש ופולטת אות בכל פעם שמחרוזת טקסט מותאמת לביטוי רגולרי נתון. המאמר מספק דוגמאות, בעיות ופתרונות.

אלגוריתם
אלגוריתמי חיפוש קודמים הביאו לעקיבה לאחור אם חיפוש מוצלח חלקית לא הצליח להניב תוצאה.

במצב קומפילציה, האלגוריתם לא עובד עם סמלים. הוא מעביר הוראות לקוד הידור. הביצוע מהיר מאוד - לאחר העברת נתונים לראש הרשימה הנוכחית, הוא מחפש אוטומטית את כל התווים האפשריים העוקבים בביטוי הרגולרי.
אלגוריתם ההידור והחיפוש נכלל בעורך הטקסט של שיתוף הזמן כחיפוש הקשרי. כמובן, זה רחוק מלהיות היישום היחיד של הליך חיפוש כזה. לדוגמה, גרסה של אלגוריתם זה משמשת כחיפוש סמלים בטבלה ב-assembler.
ההנחה היא שהקורא מכיר את הביטויים הרגולריים ואת שפת התכנות המחשב IBM 7094.

מַהְדֵר
המהדר מורכב משלושה שלבים הפועלים במקביל. השלב הראשון הוא סינון תחביר, המאפשר לעבור רק לביטויים רגולריים נכונים תחבירית. שלב זה מוסיף גם את האופרטור "·" כדי להתאים לביטויים רגולריים. בשלב השני, הביטוי הרגולרי מומר לצורת postfix. בשלב השלישי נוצר קוד אובייקט. 2 השלבים הראשונים ברורים, ולא נתעכב עליהם.

המאמר של תומפסון לא מדבר על מכונות מצב סופי לא דטרמיניסטיות, אבל הוא מסביר היטב את אלגוריתם הזמן הליניארי ומציג תוכנית ALGOL-60 המייצרת קוד שפת assembly עבור 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