הנדסה לאחור של ASIC: כך פתר מפתח את האתגר של Jane Street בתוך חודש

האתגרים הציבוריים של Jane Street ידועים בכך שהם מושכים מהנדסים להסתעפויות ארוכות. אחד מהם, חידת חומרה בשם "Can you reverse engineer an ASIC?", העסיק את המפתח כריס, שכותב בלוג בשם Jestoph, כחודש ימים; ב-4 בספטמבר הוא פרסם תיאור מפורט של הפתרון.

מה דרשה החידה

המשימה היא לקחת קובץ GDS — תיאור של פריסת סיליקון — ולשחזר בדרך הפוכה מה עושה המעגל. ASIC, כלומר מעגל משולב ייעודי, הוא שבב שתוכנן למשימה צרה אחת ולא לחישוב כללי. החידה הורכבה משני שלבים: תרגיל חימום שבו ניתן תכנון השבב עצמו, והחידה המרכזית, שלפי תיאורו הגיעה עם "לחיצת יד נחושה ו'בהצלחה'".

מפריסה גולמית לסימולציה עובדת

הרמז הראשון היה קובץ VCD שצורף לחידה. קריאתו בתוכנית C קצרה הניבה את ההודעה "TRY AGAIN", כלומר המעגל מעביר טקסט. לאחר מכן השתמש בספריית gdstk של פייתון לקריאת קבצי הפריסה, אך בהמשך כתב סימולטור מעגלים משלו, מנתח לשפת תיאור חומרה וסביבת בדיקות — הסתעפויות שהוא מתאר כיום כבזבוז זמן בעיקרו. בתרגיל החימום היו 27 רכיבים; בחידה האמיתית כ-10,000 רכיבים מ-81 סוגים (לעומת כ-20 סוגים בחימום), ולאחר סינון נותרו כ-1,000 מסלולי חיווט ו-17,000 פוליגונים.

באג בתוך החידה עצמה

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

פתרון לאחור באמצעות פותר אילוצים

מול קלט של 120 סיביות ובלי דרך מעשית לסרוק אותו במלואו, הוא הריץ את התכנון לאחור בזמן, תיאר את האותות הרצויים כאילוצים והעביר אותם לפותר z3. היה צורך בכ-24 תילים במצב גבוה בו-זמנית; 22 מהם הושגו בנפרד, והשאר נפתרו כאשר הבחין שרוב כניסות הרכיבים זקוקות לשני פולסים בלבד בכפולות של 11. הסימולציה המלאה החזירה את הפלט המנצח, "(* TWO STARS *)". המעגל גם משיב "EMPTY SKY" לקלט של אפסים בלבד ו-"BIG BANG" לקלט של אחדות בלבד. לדבריו, Jane Street רמזה על חידה חדשה בחודשים הקרובים.