הכחשת שירות (ReDoS) והתחקות קטסטרופלית בביטויים רגולריים
אמ;לק
המאמר מסביר את מושג הכחשת שירות באמצעות ביטויים רגולריים (ReDoS) ואת תופעת ה'Catastrophic Backtracking'. הוא מתאר את הסיכונים הביטחוניים הכרוכים בכך ומציע דרכים למנוע אותם.
סיכום בעברית: מערכת VibeSec · מדיניות המקורות
נוסף ל-VibeSec:
כותרת מקורית: Regular Expression Denial of Service (ReDoS) and Catastrophic Backtracking
התוכן המלא בעברית
תרגום אוטומטי מהמקור; מונחים טכניים נשארו באנגלית. לנוסח המחייב — הכתבה המקורית.
ביטויים רגולריים (Regular Expressions) הם חזקים להפליא, אך יהיה לך קשה למצוא מישהו שמאמין שהם אינטואיטיביים. בטח, יש את המפתח האחד שאתה מכיר שמצטיין בזה, אבל רוב המפתחים יודעים רק מספיק כדי לעשות נזק. למרבה הצער, רמת הסכנה בכל הנוגע לביטויים רגולריים ואבטחה גבוהה למדי. אי-הבנה של ביטויים רגולריים עלולה בסופו של דבר להקל על תוקפים להפיל את האתר שלך. ניקח את הביטוי הרגולרי הבא כדוגמה:
regex = / A(B|C + ) + D /
אם נפרק את זה, הנה מה שהביטוי הרגולרי הזה משיג:
• A המחרוזת חייבת להתחיל באות 'A'
• (B|C+)+ המחרוזת חייבת לאחר האות A להכיל את האות 'B' או מספר כלשהו של הופעות של האות 'C' (ה-+ תואם פעם אחת או יותר). ה-+ בסוף מקטע זה מציין שאנחנו יכולים לחפש התאמה אחת או יותר של מקטע זה.
• D לבסוף, אנו מוודאים שמקטע זה של המחרוזת מסתיים ב-'D'.
הביטוי יתאים לקלט כגון הדוגמאות הבאות:
ABBD ABCCCCD ABCBCCCD ACCCCCD
באופן כללי, לא לוקח הרבה זמן למנוע Regex למצוא התאמה. לדוגמה, בואו נראה מה קורה כשאנחנו בודקים אותו מול מחרוזת באורך 30 תווים: "ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD".
$ time node - e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD")' 0.04 s user 0.01 s system 95 % cpu 0.052 total
כצפוי, המחרוזת תואמת ומתאמת במהירות. התהליך כולו לוקח בערך 52ms (כפי שנבדק על MacBook Air). עכשיו בואו נראה מה קורה כשאנחנו בודקים מחרוזת נוספת באורך 30 תווים. הפעם, במקום לספק מחרוזת חוקית, בואו נספק מחרוזת שאינה חוקית על ידי החלפת ה-"D" בסוף ב-"X": "ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX".
$ time node - e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX")' 1.79 s user 0.02 s system 99 % cpu 1.812 total
פתאום לוקח כמעט שתי שניות להשלים את הבדיקה — יותר מפי עשרה מהזמן שנדרש לבדיקת מחרוזת חוקית! ההבדל הדרמטי נובע מהאופן שבו ביטויים רגולריים מוערכים. בקיצור, הם לא אוהבים לוותר.
איך מנועי RegEx עובדים
מנועי Regex נבדלים זה מזה, אך רובם פועלים בצורה דומה מאוד. המנוע יתאים לדרך האפשרית הראשונה לקבל את התו הנוכחי וימשיך לתו הבא. אם הוא נכשל בהתאמת התו הבא, הוא יבצע חזרה לאחור (backtrack) כדי לבדוק אם הייתה דרך אחרת לעבד את התו הקודם. אם הוא מעמיק מדי לתוך 'חור הארנב' רק כדי לגלות שבסופו של דבר המחרוזת לא תואמת, ואם לתווים רבים יש נתיבי Regex תקפים מרובים, מספר שלבי החזרה לאחור עלול להפוך לגדול מאוד, וכתוצאה מכך נוצר מה שמכונה "Catastrophic Backtracking" (חזרה לאחור קטסטרופלית). בואו נבחן כיצד הביטוי שלנו נתקל בבעיה זו באמצעות מחרוזת קצרה יותר: "ACCCX". למרות שזה נראה די פשוט, ישנן ארבע דרכים שונות שבהן המנוע יכול להתאים לשלושת ה-C הללו:
המנוע צריך לנסות כל אחד מהשילובים הללו כדי לראות אם מי מהם עשוי להתאים לביטוי. כאשר משלבים זאת עם השלבים האחרים שעל המנוע לבצע, נוכל להשתמש ב-debugger של RegEx 101 כדי לראות שהמנוע צריך לבצע בסך הכל 38 שלבים לפני שהוא יכול לקבוע שהמחרוזת אינה תואמת. משם, מספר הצעדים שהמנוע נדרש לבצע כדי לאמת מחרוזת רק ממשיך לגדול.
עד שהמחרוזת כוללת 14 תווים של C, המנוע צריך לבצע מעל 65,000 צעדים רק כדי לראות אם המחרוזת תקינה. כעת דמיינו את התהליך הזה כפי שהוא יחול על המחרוזת המקורית שלנו: "ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX". ניתן לראות כיצד החזרה לאחור הזו יכולה לצאת משליטה מהר מאוד. צילום המסך הבא מציג רק חלק קטן מהעבודה שהמנוע ביצע, כפי שדווח על ידי ה-debugger של RegEx101.
בהתחשב באופן שבו המנוע מעריך ביטוי רגולרי, הסיבה לזינוק העצום בזמן הדרוש לעיבוד ביטוי לא חוקי הופכת ברורה יותר: יש קשר אקספוננציאלי בין אורך המחרוזת למספר הנתיבים שעל המנוע להעריך. אם נוסיף רק עוד תו אחד לרצף הלא חוקי שלנו, זמן ההערכה כמעט מוכפל.
$ time node - e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX")' 3.51 s user 0.06 s system 95 % cpu 3.732 total
Node and ReDoS
גורמים עוינים יכולים לנצל את המורכבות של ניתוח ביטויים רגולריים על ידי הזנת מחרוזת ארוכה ומסובכת שגורמת למנוע להשקיע זמן מוגזם בתהליך ההערכה, וכתוצאה מכך נוצרת מתקפת מניעת שירות מבוססת ביטויים רגולריים (ReDoS).
זה בהחלט לא אידיאלי באף סביבה, אך גרוע אף יותר בסביבות JavaScript, כולל Node. כפי שהסברנו כשדיברנו על התקפות תזמון (timing attacks) בפוסט קודם, Node.js (ו-JavaScript באופן כללי) מונעים על ידי אירועים (event driven).
המשמעות היא שאם שרשור (thread) תפוס על ידי בקשת ReDoS מוצלחת, בקשה זו תחסום את כל לולאת האירועים (event loop) והאפליקציה לא תוכל לבצע שום עיבוד אחר.
דוגמה מהעולם האמיתי
בואו נסתכל על דוגמה עדכנית מהעולם האמיתי שנמצאה בספריית ה-moment הפופולרית. moment משמשת לניתוח, אימות, מניפולציה ועיצוב תאריכים. באמצעות הכלי, ניתן לציין את הפורמט שבו תרצה לקבל את פלט התאריך באמצעות מתודת format():
moment (). format ( 'MMM Do YY' ); //example output: Nov 22nd 16
כאשר מגדירים פורמט, moment משתמשת בביטוי רגולרי כדי לאמת אותו. בגרסאות של moment הישנות מ-2.15.2, הביטוי הרגולרי נראה כך:
var MONTHS_IN_FORMAT = / D[oD] ? (\[[^\[\]] * \]|\s + ) + MMMM ? / ;
המפתח כאן הוא החלק ((\[[^\[\]]*\]|\s+)+) בביטוי. ראוי לציין במיוחד ש-\s+ בודק קיום של רווח אחד או יותר. עם זאת, ה-+ שנמצא ממש מחוץ לקבוצה זו אומר שניתן למצוא את הקבוצה המקוננת בתוך הסוגריים פעם אחת או יותר. היגיון זה אומר שישנן דרכים רבות ושונות שבהן מנוע הביטויים הרגולריים יכול לנסות לקבץ את התווים הללו כדי למצוא התאמה, אם יש מספר גבוה של רווחים בפורמט. הם יכולים להיתפס יחד כקבוצה אחת גדולה שהותאמה פעם אחת, להיות מפורקים לקבוצות בודדות שכל אחת תואמת בפני עצמה, או כל דבר שביניהם. התוצאה היא שיכול לקחת זמן רב להעריך מחרוזת שקרובה מאוד להיות תקינה.
שקול את הדוגמה הזו שפרסמנו כשמצאנו את הפגיעות:
var m = require ( "moment" ); m . locale ( "be" ); m (). format ( "D MMN MMMM" ); // Normal date format, other than the 31 spaces included in the string
במקרה זה, אנו מעבירים מחרוזת באורך 40 תווים עם תווי רווח רבים. הפעלת זה על מחשב נייד סטנדרטי הראתה שהביטוי חוסם את לולאת האירוע למשך כ-20 שניות.
$ time node - e '/D[oD]?( \[ [^ \[\] ]* \] | \s +)+MMMM?/.test("D MMN MMMM");' 21.24 s user 0.14 s system 96 % cpu 22.079 total
לאחר שחשפנו את הפגיעות בפני moment, המחבר יצר תיקון (ניתן לבדוק כעת אם התיקון חל עליך) שמסיר את האופרטור + מחוץ לסוגריים:
var MONTHS_IN_FORMAT = / D[oD] ? (\[[^\[\]] * \]|\s) + MMMM ? / ;
על ידי כך, ביטלת את קיומן של שתי קבוצות התאמה שונות שכל אחת מהן יכלה להכיל כל מספר מהרווחים הכלולים בה. מכיוון שהאופרטור + כבר לא עוקב אחרי ה-s, הוא יכול להתאים רק לרווח בודד בכל פעם. אם תבדוק את המחרוזת שוב באמצעות הביטוי הרגולרי החדש, ייקח למנוע אלפיות שניות בלבד להבין שזו אי-התאמה.
$ time node - e '/D[oD]?( \[ [^ \[\] ]* \] | \s )+MMMM?/.test("D MMN MMMM");' 0.05 s user 0.02 s system 53 % cpu 0.135 total
Preventing Catastrophic Backtracking
כדי למנוע חזרה לאחור קטסטרופלית, כדאי לשים לב לכל פעם שבה אתה משתמש באופרטורים '+' או '*' בקרבת מקום זה לזה. אם כן, רוב הסיכויים שהם יסתיימו ב"משיכת חבל" שתגרום לחזרה לאחור קטסטרופלית. ודא ששני האופרטורים אכן נחוצים. ניתן גם לשקול להחליף אחד מהם בקבוצה מוגבלת. אם אתה זוכר את פגיעות ה-ReDoS ב-moment, תיקנו אותה על ידי ביטול אחד מאופרטורים ה-'+'. יכולנו גם להחליף אחד מהם בטווח, ובכך להגביל את מספר הרווחים שנאפשר במחרוזת תקינה:
var MONTHS_IN_FORMAT = / D[oD] ? (\[[^\[\]] * \]|\s + ) {0,10} MMMM ? / ;
ניתוח Regex הוא די נאיבי, אך שפות מסוימות הציגו תכונות מתקדמות שיכולות לעזור להימנע מחזרה לאחור קטסטרופלית. לדוגמה, בואו נבחן את הביטוי הפשוט שהתחלנו איתו:
regex = / A(B|C + ) + D /
Atomic Groups
כפי שדיברנו, הביטוי עלול לגרום לחזרה לאחור קטסטרופלית. במנתח הביטויים הרגולריים הנתמך ב-Node.js, אין תכונה מובנית שניתן להשתמש בה כדי לפתור את הבעיה. זה לא המקרה בשפות אחרות. קחו את Ruby למשל; Ruby תומכת במשהו שנקרא "קבוצות אטומיות" (atomic groups). קבוצות אטומיות מאפשרות לך לומר למנתח ה-regex לא לחזור אחורה כאשר קבוצה כבר התאימה. אתה עושה זאת על ידי הקדמת הקבוצה ב-?> , כך:
/ A( ? >B|C + ) + D /
הוספת ?> לקבוצה שמחפשת מספר מסוים של "C" הופכת אותה לקבוצה אטומית. בעבר, למנתח ה-regex היו שני אופרטורים מתחרים לשקול. ה-"C" בתוך הקבוצה יכול להתאים כל מספר פעמים, או שהקבוצה עצמה יכולה להתאים כל מספר פעמים. לכן, אם מוזן ביטוי לא תקין שמכיל מספר גבוה של תווים מסוג "C", המנתח יילכד בקרב בין שתי הקבוצות, וינסה שוב ושוב לראות אם יש איזה שילוב "קסום" שיהפוך את הביטוי לתקין.
עם זאת, עם החלת קיבוץ אטומי, המנתח ינעל את ההתאמה של אותה קבוצה במקומה. במקרה זה, הוא יתאים לכל כמות של תווי "C" שקיימים. כאשר הביטוי אינו תקין, הוא לא יוכל לחזור אחורה מעבר לקבוצה הזו — זה סופי לחלוטין בשלב זה. ללא צורך "להטט" בתווי "C" בין שני האופרטורים התואמים הפוטנציאליים, ביטוי לא תקין יזוהה במהירות רבה, תוך הימנעות מכל חזרה לאחור קטסטרופלית.
מבט קדימה
בעוד JavaScript אינו תומך בקבוצות אטומיות, הוא כן תומך ב-LookAhead שניתן להשתמש בהן כדי להשיג את אותה השפעה כללית של קיבוץ אטומי.
A ( ? = ( B | C + ))\ 1 + D
במקרה זה, אנו משתמשים ב-?= כדי לציין LookAhead. המשמעות היא שהביטוי הרגולרי יתאים לקבוצה ההיא רק אם מיד אחריה מופיעה הקבוצה הבאה. על ידי שימוש ב-\1, אנו לוכדים את הקבוצה שהותאמה, ויוצרים למעשה קבוצה אטומית. בשלב זה, המנתח יתייחס להתאמה זו כאילו הייתה קבוצה אטומית וימנע מכל חזרה לאחור קטסטרופלית.
אם נבדוק את המחרוזת שלנו מול הביטוי כעת באמצעות LookAhead, נראה שהזמן לבטל את המחרוזת ירד באופן דרמטי (מ-1.8 שניות ללא שימוש ב-LookAhead ל-94ms איתה):
$ time node - e '/A(?=(B|C+)) \1 +D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX")' 0.05 s user 0.02 s system 51 % cpu 0.094 total
הפשרה שאתה עושה כאן היא מורכבות. אתה נמנע מחזרה לאחור קטסטרופלית, אך אתה מוסיף מורכבות לביטוי שלך, מה שלא רק הופך אותו לקשה יותר לפענוח עבור חברי צוות אחרים, אלא גם מגדיל את הסיכוי לטעויות. אם אתה יכול לזהות את שילוב האופרטורים שעלול לגרום לחזרה לאחור (במקרה זה, שני ה-+'ים), אולי עדיף לך פשוט לנסח מחדש את הביטוי כדי לשפר את הבהירות והקריאות.
תַקצִיר
התקפות ReDoS יכולות להביא להפסקת יישום. זה נכון במיוחד בעולם של Node.js שבו לולאת האירועים רק מעצימה את ההשפעה של מעקב לאחור קטסטרופלי.
מניעת פגיעויות ReDoS כוללת ניטור של הביטויים הרגולריים שלך, כמו גם בדיקת התלויות (dependencies) שלך עבור פגיעויות ReDoS כלשהן.
היו כמה ניסיונות ליצור כלים לזיהוי אוטומטי של ביטויים הרגישים להתקפות ReDoS (הבולט שבהם הוא safe-regex), אך אפילו בבדיקות מוגבלות מצאנו מספר התראות שווא (false positives), כמו גם כמה ביטויים שנקבעו כבטוחים למרות שהם לא היו כאלה.