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

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

מקורות לאקראיות אמתית

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

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

מקור מעניין נוסף שנתקלתי בו בחיפושיי הוא זיכרון ה-RAM של המיקרו-בקר עצמו. זהו הרי זיכרון נדיף, שמאבד את תוכנו כאשר אין אספקת חשמל (אם כי צריך להיזהר – "אספקת חשמל" היא לא תמיד מה שחשבתם). איבוד תוכן אין פירושו שתאי זיכרון ה-RAM מתאפסים כולם לערך אחד ספציפי, אלא שכל אחד מהם יכול לקבל כל ערך שהוא – וזה בדיוק מה שאנחנו מחפשים בשביל ה-Seed שלנו. אפשר, אם כן, לעבור באמצעות pointer על אזורי RAM שאינם בשימוש הקוד וליצור מהבייטים שבהם, באמצעות פעולת XOR או אחרת, מספר אקראי לא רע.

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

שילוב של מספר אקראי שמבוסס על ה-RAM עם ביטים אקראיים מהקריאות האנלוגיות מספק לנו Seed נחמד לשימוש יומיומי, אבל הסיפור עדיין לא נגמר.

מגבלת ה-Seed (או: בעיית יום ההולדת)

הפונקציה randomSeed בארדואינו מקבלת כפרמטר משתנה מטיפוס unsigned long, כלומר בן 32 ביטים. בפרויקט שלי, לעומת זאת, המיקרו-בקר הוא ממשפחת PIC, והקומפיילר הוא xc8 של Microchip. בקומפיילר זה (כך גיליתי במדריך למשתמש שלו) הפונקציה srand המקבילה מקבלת פרמטר בן 16 ביטים בלבד. זה אומר שיש רק 65,536 ערכי Seed אפשריים. למשתמש חסר הידע הסטטיסטי זה עשוי להיראות מספיק בהחלט – הרי הסיכוי לקבל במקרה את אותו המספר הוא 1 חלקי 65,536, וזה נמוך מאוד. לא ככה?

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

הדרך הנוחה, יחסית, לגשת לפתרון החידה היא להתחיל מאדם אחד ולחשב הפוך – מה הסיכוי שלכל אדם נוסף אין יום הולדת בתאריך זהה לאחד מהאנשים הקודמים. עבור האיש השני, הסיכוי שיום ההולדת שלו שונה מזה של הראשון הוא 364/365 (אנחנו מניחים שהתפלגות ימי ההולדת בשנה היא אחידה, אם כי בפועל זה לא מדויק). עבור האיש השלישי, הסיכוי שיום ההולדת שלו שונה משל השניים הקודמים הוא 363/365, וכדי "לצרף" את ההסתברויות הללו אנחנו צריכים להכפיל אותן. אם נמשיך להוסיף אנשים ולהכפיל את ההסתברויות, באיש ה-24 ההסתברות למצוא "יום הולדת כפול" כבר תהיה גבוהה מחצי!

עכשיו נחזור ל-Seed שלנו עם 16 ביט ונשאל, לא "מה הסיכוי לקבל את אותו מספר" אלא "מה הסיכוי שמספר כלשהו יחזור על עצמו ב-x אתחולים". באותה שיטת חישוב כמו עם ימי ההולדת, מסתבר שההסתברות לקבל מספר כפול תהיה גדולה מחצי כבר באתחול ה-302. כלומר, אם במערכת שלי יהיו 302 מיקרו-בקרים בלבד, יש סיכוי של 1:2 שייווצר לי איפשהו מספר זיהוי כפול!

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

זמן תמורת אקראיות

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

כמה חישובים לגלגל? ברור שאם נבחר את אותו Seed ונגלגל אותו מספר חישובים, נגיע לאותה תוצאה בדיוק. אנחנו צריכים לבחור מספר אקראי של גלגולים – ולשם כך אנחנו יכולים להיעזר בביטים אקראיים נוספים שנלקחים מהחומרה. אם ניקח 8 ביטים כאלה נקבל 256 אפשרויות, ולמעשה נכפיל פי 256 את מרחב האפשרויות שלנו, מ-65,536 ל-16,777,216. על התוספת הזו אנחנו משלמים בזמן החישוב של שרשרת המספרים האקראיים, אבל גם במקרה הכי גרוע מדובר בזמן סביר לרוב השימושים.

מה הרווחנו מבחינת הסיכוי למזהים כפולים? כעת, הסיכוי מגיע לחצי באתחול ה-4,823, וזה כבר הרבה יותר טוב מ-302. אפרופו, בפונקציות הארדואינו שמקבלות Seed עם 32 ביט, הסיכוי למזהה כפול מגיע לחצי באתחול ה-77,164.

ואם יש כפילות למרות הכול

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