כתיבת תבניות בטוחות ב-ReDoS

ReDoS (מניעת שירות של ביטוי רגיל) הוא סוג של התקפות שבהן קלט מעוצב בקפידה גורם לזמן ההתאמה של ביטוי רגיל להתפוצץ. מנוע JS משתמש ב-backtracking: אם דפוס הוא "דו-משמעי", ב-an קלט חסר מזל זה יכול לבצע מספר אקספוננציאלי של ניסיונות.

הדפוס הקטסטרופלי הקלאסי

Pattern: ^(a+)+$
Input:   "aaaaaaaaaaaaaaaaaaaaab"

כדי להתאים, המנוע מנסה כל מחיצה אפשרית של "a" בין שני המכמתים +. ב-20 "a" זה 2^20 = ~1 מיליון ניסיונות. ב-30 א', מיליארד.

דוגמאות מסוכנות נוספות:

• (a*)*b -- "כוכבים מקוננים".
• (a|a)* -- חלופות חופפות.
• (\w+)+@ -- קבוצות חמדניות עם מכמת חיצוני.

איך לזהות את הסכנה

חפש את המבנים הבאים:

1. מכמת בתוך מכמת: (...+)+, (...*)*, (...{n,})+.
2. חלופות חופפות תחת מכמת: (a|ab)*, (\w|\d)+.
3. הסתכלות קדימה/הסתכלות אחורה עם חלופות מורכבות חוזרת על עצמה.

שכתוב הגנתי

Dangerous:  ^(\w+\s+)+$
Safe:       ^(?:\w+\s+)*\w+$

הגרסה הבטוחה מפרידה את מארז הבסיס מהמארז החוזר, מסיר את העמימות. טכניקות אחרות:

• מכמתים רכושיים ​​(a++) -- לא נתמך ב-JS, אבל זמין במנועים אחרים.
• דפוסים אטומיים ​​((?>...)) -- לא ב-JS.
• הגביל את אורך הקלט לפני ההתאמה.
• זמן קצוב בהתאמה (עורך הקורס הזה משתמש בעובד עם פסק זמן של 500 אלפיות השנייה).

המלצות לדפוסים בטוחים ב-ReDoS

1. ודא שהאפשרויות לסירוגין סותרות זו את זו (למשל, אל תשתמש ב-(a|a+)).
2. הימנע מהחלת כימות מקוננות על ביטויים חופפים (למשל (\\s*)*).
3. העדיפו תמיד מחלקות תווים מסוימות ([^\\n]*) על פני הנקודה הכללית של התווים הכלליים (.*).

נסה את זה

סקירת התרגיל

אתגר נוסף