פירוש מופשט מוסבר: מתורת הסריג ועד להסקה ואסטרה

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

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

מהי פרשנות מופשטת?

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

המילה "אבסטרקט" כאן אינה מתייחסת למעורפל או מושגי. היא מתייחסת לפעולה מתמטית ספציפית: הפשטת קבוצה של ערכים קונקרטיים לייצוג פשוט יותר ששומר על התכונות החשובות לך תוך הימנעות מפרטים מיותרים. ערך שלם קונקרטי כמו 42 הופכת, בהפשטה של ​​ניתוח סימנים, פשוט ל"חיובית". ההפשטה מאבדת מידע (אינך יודע עוד את הערך המדויק) אך מקבלת יכולת עקיבות (הסימן של כל מספר שלם הוא אחת משלוש אפשרויות: חיובי, שלילי או אפס).

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

פרשנות מופשטת לעומת ניתוח AST לעומת ניתוח דינמי

מונחים אלה מתבלבלים לעתים קרובות, "ניתוח קוד AST" מופיע בנתוני החיפוש עבור מאמר זה, והם מתארים דברים שונים.

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

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

רוב כלי ה-linter (ESLint, Checkstyle, Pylint) מבוססים בעיקר על AST. רוב כלי האימות הפורמליים (Infer, Astrée, Polyspace) משתמשים בפרשנות מופשטת. ניתוח דינמי (הרצת התוכנית ותצפית על התנהגות בפועל) מוצא רק באגים המופעלים על ידי קלטים ספציפיים. פרשנות מופשטת מוצאת באגים בכל הקלטים האפשריים מבלי להריץ את התוכנית כלל.

העקרונות המתמטיים העומדים מאחורי ניתוח סטטי

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

פרשנות מופשטת נשענת על שלושה מבנים מתמטיים:

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

        ⊤ (unknown -- could be anything)
       / \
   pos   neg
       \ /
        0
        |
        ⊥ (unreachable -- no possible value)

עלייה במעלה הסריג פירושה אובדן דיוק (ידיעה פחות). ירידה מטה פירושה שיפור דיוק (ידיעה יותר). האלמנט העליון ⊤ פירושו "אנחנו לא יודעים שום דבר מועיל". האלמנט התחתון ⊥ פירושו "מצב זה אינו ניתן להשגה".

קשרי גלואה. קשר גלואה הוא הקשר הפורמלי בין התחום הקונקרטי (ערכי התוכנית בפועל) לתחום המופשט (הייצוג הפשוט). הוא מורכב משתי פונקציות: פונקציית הפשטה α הממפה ערכים קונקרטיים לייצוג המופשט שלהם, ופונקציית קונקרטיזציה γ הממפה ערכים מופשטים בחזרה לקבוצת הערכים הקונקרטיים שהם מייצגים.

המאפיין הקריטי: התחום המופשט חייב להיות קירוב יתר בטוח. γ(α(S)) ⊇ S עבור כל קבוצה קונקרטית S. ההפשטה עשויה לכלול יותר ערכים ממה שמתרחש בפועל, וזה מה שיוצר תוצאות חיוביות שגויות, אך אסור לה אף פעם לא לשלול ערכים שמתרחשים בפועל. אי הכללת ערכים אמיתיים פירושה החמצת באגים אמיתיים.

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

c

int x = 0;
while (condition) {
    x = x + 1;
}

באיטרציה הראשונה, x is {0}אחרי גוף לולאה אחד, x יכול להיות {0, 1}אחרי שתיים, {0, 1, 2}קבוצה זו ממשיכה לגדול, היא לעולם לא מתייצבת מעצמה. הפתרון הוא הִתרַחֲבוּתאופרטור שכופה התכנסות על ידי קפיצה לקירוב רחב יותר (בדרך כלל [0, +∞) (לניתוח מרווחים). לאחר מכן הניתוח משתמש הֲצָרָה כדי לשחזר קצת דיוק.

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

תחומים מופשטים: בחירת מה לקרב

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

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

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

כיצד שלושה כלים אמיתיים משתמשים בפרשנות מופשטת

במקום לתאר את התיאוריה בפני עצמה, כלים קונקרטיים מבהירים את יישומה.

Facebook Infer משתמש בצורה של פרשנות מופשטת הנקראת bi-abduction כדי לנתח את Java, C, C++ ו-Objective-C עבור ניתוק מצביעי null, דליפות משאבים ותנאי מרוץ. Bi-abduction מגלה באופן אוטומטי תנאים מוקדמים ותנאי פוסט עבור פונקציות, ומאפשר ניתוח בין-פרוצדורי ללא צורך במפרטים ידניים. Infer פועל ב-CI בפייסבוק, ספוטיפיי, מוזילה ועשרות ארגונים גדולים אחרים מכיוון שהוא ניתן להרחבה לבסיסי קוד של מיליוני שורות תוך שמירה על תקינות עבור סוגי השגיאות שהוא בודק.

Astrée משתמשת בפרשנות מופשטת עם תחומים מופשטים מספריים כדי להוכיח את היעדר שגיאות זמן ריצה בתוכניות C. היא שימשה את איירבוס לאימות רשמי של תוכנת בקרת הטיסה העיקרית של ה-A380, והוכיחה היעדר שגיאות זמן ריצה בכל מערכת הבקרה, ערובה שאף תוכנית בדיקה לא יכלה לספק. Astré מוצאת אפס תוצאות שליליות שגויות עבור סוגי השגיאות שהיא בודקת, אם כי היא עשויה לייצר תוצאות חיוביות שגויות הדורשות סקירה ידנית.

Polyspace (MathWorks) מיישמת פרשנות מופשטת עבור קוד C ו-C++ מוטמע ביישומים קריטיים לבטיחות. היא מסווגת כל פעולה כ"ירוק" (ניתן להוכיח שאין שגיאה), "אדום" (בהחלט שגיאה) או "כתום" (שגיאה פוטנציאלית הדורשת סקירה). הסיווג הירוק הוא הוכחה פורמלית: שום ביצוע לא יכול לגרום לשגיאת זמן ריצה באותה פעולה.

משולש תקינות-דיוק-ביצועים

כלי פרשנות מופשטת מנווטים במשולש בסיסי של תכונות מתחרות. אף כלי אינו יכול למקסם את שלושתן בו זמנית.

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

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

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

יישומים שונים דורשים נקודות שונות במשולש זה:

• מוך IDE ו-CI/CDביצועים ראשונים, דיוק שני, תקינות אופציונלית
• סריקת אבטחהדיוק קודם כל (הפחתת עייפות ערנות המפתח), תקינות חשובה עבור קטגוריות חומרה גבוהות
• הסמכה קריטית לבטיחותתקינות תחילה (לא ניתן לפספס באגים אמיתיים), ביצועים משניים, תוצאות חיוביות שגויות מקובלות בתהליך בדיקה ידני

פרשנות מופשטת בפיתוח משובץ ובטיחות-קריטי

השאלה "יתרונות הניתוח הסטטי בפיתוח משובץ" מצביעה על אחד מתחומי היישום החשובים ביותר של פרשנות מופשטת. למערכות משובצות, יחידות בקרה לרכב, קושחה של מכשירים רפואיים ותוכנות בקרת טיסות בחלל, יש אילוצים שהופכים את הפרשנות המופשטת ליקרה במיוחד:

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

דרישות הסמכה. DO-178C (תעשיית התעופה וחלל), ISO 26262 (תעשיית הרכב) ו-IEC 62443 (תעשיית הבקרה) דורשים הוכחה שתוכנה פועלת כראוי בכל התנאים. אימות פורמלי באמצעות פרשנות מופשטת יכול לעמוד בדרישה זו באופן שדוחות כיסוי בדיקות אינם יכולים.

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

מנתחי Astrée ו-Polyspace קיימים במיוחד עבור ההקשר הזה. התכנון שלהם מקבל שיעורי חיוביים כוזבים גבוהים וניתוח איטי בתמורה לערבות שלא יחלחלו דרכם תוצאות שליליות כוזבות.

תוצאות חיוביות שגויות והבעיה המתרחבת

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

תוצאות חיוביות שגויות נובעות משני מקורות:

קירוב יתר בתחום המופשט. אם תחום המרווחים עוקב x ∈ [0, 100], הוא אינו יכול להבחין בין מקרים שבהם x תמיד קטן מ-50 בפועל. חילוק ב- x עשוי להיות מסומן כמחולק באפס גם כאשר לוגיקת התוכנית מבטיחה x > 0דומיין מדויק יותר (מעקב אחר הערך המדויק, או קישור אילוצים) x למשתנה אחר) יבטל את החיובי השגוי, אך בעלות חישובית גבוהה יותר.

הִתרַחֲבוּת. אופרטור ההתכנסות שהופך את ניתוח הלולאה לניתן לביצוע בהכרח מאבד מידע לאחר ההתרחבות. x החל מ- [0, 5] ל [0, +∞)המנתח כבר לא יודע את זה x נשאר מוגבל. אם הקוד בודק assert(x < 1000) לאחר הלולאה, טענה זו אינה ניתנת להוכחה עוד, גם אם בפועל x תמיד נשאר הרבה מתחת ל-1000.

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

איך SMART TS XL יישום ניתוח סטטי בקנה מידה ארגוני

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

במקום להחיל תחום מופשט יחיד על כל התוכניות, SMART TS XL"S ניתוח קוד סטטי משלבת טכניקות ניתוח מבני המתאימות לכל שפה בסביבה, COBOL, JCL, Java, Python, RPG, PL/I, SQL ו-stack מודרני, ומייצרת מדדי איכות, נתוני תלות וממצאי אבטחה בו זמנית על פני כל תיק העבודות.

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

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

עבור צוותים המנהלים מודרניזציה מורשת תוכניות, SMART TS XLהניתוח המבני של [שם חומר] סוגר את הפער בין כלי פרשנות מופשטים פורמליים (שהם ספציפיים לשפה ודורשים מומחיות בתחום כדי להגדיר אותם) לבין הצורך המעשי להבין מה מערכות מדור קודם גדולות, לא מתועדות ורב-לשוניות עושות בפועל, תנאי הכרחי לכל תוכנית מודרניזציה שלא רוצה לגלות את ההפתעות היקרות ביותר שלה באמצע הביצוע.

שאלות נפוצות

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

האם פירוש מופשט מיועד רק לתוכנה קריטית לבטיחות? לא, למרות שהוא מספק את הערך הברור ביותר שלו שם. Infer רץ בצינורות CI/CD סטנדרטיים בחברות טכנולוגיה גדולות, מוצא הפניות למצביעי null ודליפות משאבים בקוד Java ו-C יומיומי. מידת הקפדנות המיושמת היא בחירה: תקינות מלאה עם ערבויות פורמליות בקצה אחד, ניתוח היוריסטי קל משקל בקצה השני, כאשר רוב הכלים המעשיים נמצאים איפשהו באמצע.

האם פירוש מופשט יכול לנתח COBOL? פירוש מופשט הוא אגנוסטי לשפה כתיאוריה. יישומו על COBOL דורש יישום של פונקציות העברה מופשטות עבור פעולות COBOL, אריתמטיקה של שדות PIC, פסקאות REDEFINES, שמות תנאים ברמה 88 וכן הלאה. כלי פירוש מופשטים למטרות כלליות (Infer, Astrée) אינם תומכים ב-COBOL. פלטפורמות ניתוח מבני ארגוניות שמבינות COBOL מיישמות באופן טבעי טכניקות ניתוח סטטי קשורות כדי למצוא בעיות איכות, קוד מת ובעיות ארכיטקטוניות בבסיסי קוד COBOL.