אימות מבוסס-מודל (Model-based Verification) במנועי אחסון Key-Value
אמ;לק
פוסט הנדסי עמוק על שימוש ב-Formal Verification כדי לוודא שמימוש מנוע האחסון ב-MongoDB תואם לפרוטוקול הטרנזקציות המבוזרות. מודלים פורמליים עוזרים למנוע באגים קריטיים של עקביות ודליפת מידע. תוכן מתקדם באבטחת נכונות קוד (Software Correctness).
סיכום בעברית: מערכת VibeSec · מדיניות המקורות
נוסף ל-VibeSec:
כותרת מקורית: Towards Model-based Verification of a Key-Value Storage Engine
>פוסט הנדסי עמוק על שימוש ב-Formal Verification כדי לוודא שמימוש מנוע האחסון ב-MongoDB תואם לפרוטוקול הטרנזקציות המבוזרות. מודלים פורמליים…
התוכן המלא בעברית
תרגום אוטומטי מהמקור; מונחים טכניים נשארו באנגלית. לנוסח המחייב — הכתבה המקורית.
בפוסט הקודם שלנו, דנו בתהליך הגדרת פרוטוקול העסקאות המבוזר של MongoDB ובאופן שבו הוא אפשר ניתוח חדשני של מאפייני הביצועים שלו. בפוסט המשך זה, אנו מסבירים כיצד המודולריות של המפרט שלנו אפשרה לנו לבדוק האם הטמעת מנוע האחסון הבסיסית אכן תואמת להתנהגות המופשטת שהגדרנו במפרט הפורמלי. כלומר, אנו מסוגלים למדל את גבול הממשק בין פרוטוקול הטרנזקציות המבוזר לבין WiredTiger, מנוע האחסון מסוג key-value, ולפתח דרך אוטומטית ליצירת בדיקות שמוודאות התאמה בין הסמנטיקה של שכבת מנוע האחסון לבין המודל המופשט הזה.
כפי שהוזכר בפוסט הקודם, חקירה מעמיקה יותר של המושגים המכוסים בפוסט זה מכוסה במאמר VLDB '25 שפורסם לאחרונה, Design and Modular Verification of Distributed Transactions ב-MongoDB .
מודולרי, Model-Based Verification
כפי שנדון ב-Part 1, פיתחנו מפרט TLA+ עבור פרוטוקול העסקאות המבוזרות של MongoDB באופן קומפוזיציוני. המפרט מתאר את התנהגות הפרוטוקול ברמה גבוהה תוך ביצוע פורמליזציה לגבול שבין ההיבט המבוזר של פרוטוקול העסקאות לבין רכיב מנוע האחסון WiredTiger הפועל על צומת יחיד. כאמור, ניתן לראות בפרוטוקול העסקאות המבוזר ככזה שפועל על גבי שכבת האחסון ברמה התחתונה.
כאשר בוחנים את ערבויות הנכונות של פרוטוקול העסקאות המבוזרות, היבט עדין הוא האינטראקציה שלו עם מנגנוני בקרת המקביליות (concurrency control) בכל שכבה של המערכת. בפרט, האינטראקציה שלו עם ה-API של מנוע האחסון WiredTiger, שבו מיושמות פעולות שונות מבוססות חותמות זמן (timestamp-based) כדי לתמוך כראוי בפעולה התקינה של פרוטוקול העסקאות המבוזרות.
המודל הפורמלי של פרוטוקול העסקאות המבוזר היה שימושי לבדיקת הערבויות שלו, אך רצינו גם לנסח חוזה בין פרוטוקול מבוזר זה לבין מנוע האחסון הבסיסי, כדי לוודא שגבול הממשק הזה, כפי שהוגדר במפרט המופשט שלנו, אכן תואם את המימוש בפועל. תוך ניצול גבול הממשק הנקי במפרט שלנו, פיתחנו כלי לבדיקת התאמה אוטומטית בין המימוש של WiredTiger לבין מפרט האחסון המופשט (Storage) שהגדרנו. מפרט שכבת האחסון שלנו משמש כהגדרה שימושית ומדויקת של תת-קבוצה מהסמנטיקה של מנוע האחסון WiredTiger, אך אנו יכולים להשתמש בו גם ליצירה אוטומטית של מקרי בדיקה כדי לבדוק את התאמת הסמנטיקה של WiredTiger למפרט שלנו.
איור 1. מפרט הרכב של עסקאות מבוזרות ב-TLA+ ורכיב מנוע אחסון.
יצירת מקרה בדיקה מבוסס נתיב
לשם כך, אנו משתמשים בגרסה שונה של בודק המודלים TLC כדי ליצור תחילה את הגרף המלא של מצבים ברי-השגה (reachable states) עבור פרמטרים סופיים במפרט רכיב האחסון. לאחר מכן, אנו מחשבים קבוצה של כיסויי נתיבים בגרף זה, כאשר כל נתיב מומר למקרה בדיקה בודד כרצף של קריאות API למנוע האחסון. טכניקת אימות מבוססת מודלים זו מאפשרת לנו ליצור אוטומטית עשרות אלפי מקרי בדיקה בודדים עבור WiredTiger, שכל אחד מהם בודק האם המימוש תואם את ההתנהגות המוגדרת במפרט המופשט שלנו — שהינו גם החוזה שעליו מסתמך פרוטוקול העסקאות המבוזר ברמה הגבוהה.
איור 2. זרימת עבודה ליצירת מקרה בדיקה מבוסס מודל.
עבור מודל סופי קטן ושלם (2 מפתחות ו-2 עסקאות), אנו יכולים לבדוק התאמה עם WiredTiger עם חבילה שנוצרה של 87,143 בדיקות, אשר נוצרות ומבוצעות מול מנוע האחסון תוך כ-40 דקות.
איור 3. סטטיסטיקות יצירת מקרה מבחן עבור מודל שכבת האחסון.
מפרט שכבת האחסון הנוכחי שלנו זמין ב-Github, וקישור לגרסה אינטראקטיבית וניתנת לחקירה שלו זמין גם הוא ב-Github. בעתיד, אנו מקווים לחקור מידול של תת-קבוצה נרחבת יותר של ה-API של WiredTiger ולבחון אסטרטגיות חלופיות לחקירת מרחב המצבים לצורך הפקת בדיקות, למשל דגימת נתיבים אקראית או אסטרטגיות אחרות הדורשות רק כיסוי משוער של מודל מרחב המצבים. לגישה זו יש דמיון למאמצי בדיקה אחרים שחקרנו בעבר.
מַסְקָנָה
מידול פרוטוקול העסקאות המבוזר אפשר את אימות תקינות הפרוטוקול, והשימוש שלנו במודולריות ובאימות קומפוזיציוני היה מכריע ביכולתנו להסיק מסקנות לגבי מאפייני נכונות ברמה גבוהה אלה, תוך יכולת לבדוק אוטומטית שממשק האחסון המופשט שלנו תואם נכונה את הסמנטיקה של המימוש. גישות דומות נחקרו לאחרונה עבור אימות מבוסס מודלים של מערכות מבוזרות, לצד שיטות נוספות לבדיקת מערכות באמצעות טכניקות יצירת מקרי בדיקה מבוססות נתיב. בעתיד, אנו נותרים אופטימיים לגבי התפקיד ש-LLMs יכולים למלא בסוג זה של זרימת עבודה לאימות. לדוגמה, לאחר פיתוח תשתית בדיקות שכזו, פיתוח אוטונומי של מודל התנהגות המערכת הבסיסית על ידי LLMs יאפשר אפיון התנהגות מדויק, לצד יכולות יצירת חבילות בדיקה אוטומטיות.
תוכל למצוא פרטים נוספים על עבודה זו במאמר VLDB '25 שפורסם לאחרונה, ובמאגר Github המשויך שמכיל את המפרטים והקוד שלנו, כמו גם קישורים לגרסאות חקירה בדפדפן של המפרטים שלנו.