Реверс-інжиніринг ASIC від Jane Street: як розробник розв'язав задачу за місяць

Публічні завдання Jane Street відомі тим, що затягують інженерів у довгі мандри. Одне з них — апаратна головоломка «Can you reverse engineer an ASIC?» — зайняло в розробника Кріса, який веде блог під іменем Jestoph, близько місяця; 4 вересня він опублікував докладний звіт про своє рішення.

Що вимагалося

Завдання полягає в тому, щоб узяти GDS-файл — опис кремнієвої топології — і зворотним шляхом визначити, що робить схема. ASIC (application-specific integrated circuit) — це чип, розрахований на одне вузьке завдання, а не на загальні обчислення. Головоломка мала дві частини: розминку, де надавався сам дизайн чипа, і основну задачу, яка, за словами автора, супроводжувалася лише «міцним рукостисканням і побажанням удачі».

Від топології до робочої симуляції

Першою підказкою став VCD-файл, доданий до головоломки. Читання його невеликою програмою на C дало повідомлення «TRY AGAIN», тобто схема передає текст. Далі він використав бібліотеку gdstk для Python, щоб відкривати файли топології, хоча згодом написав власний симулятор схем, парсер мови опису апаратури та тестовий стенд — ці відхилення він тепер вважає переважно марно витраченим часом. У розминці було 27 елементів; в основній головоломці — приблизно 10 000 компонентів 81 типу (у розминці близько 20 типів), а після фільтрації залишилося близько 1000 трас і 17 000 полігонів.

Помилка в самій головоломці

Симуляція виявила незаведений дріт, з'єднаний лише з двома вхідними виводами, поруч із виводом, який не був ні входом, ні виходом. Про це він повідомив Jane Street і наступного дня отримав підтвердження, що має рацію, хоч цей дефект не впливає на результат головоломки. Сам звіт він називає одним зі своїх найцікавіших технічних досягнень.

Розв'язок зворотним ходом, через розв'язувач обмежень

Маючи 120-бітний вхід і жодного реального способу перебрати його повністю, він запустив дизайн у зворотному часі, описавши потрібні сигнали як обмеження для розв'язувача z3. Одночасно високими мали бути близько 24 дротів; 22 з них вдалося отримати окремо, а решту — коли він помітив, що більшості входів елементів потрібні лише два імпульси з кратністю 11. Повна симуляція видала переможний результат «(* TWO STARS *)». Схема також відповідає «EMPTY SKY» на нульовий вхід і «BIG BANG» на всі одиниці. Jane Street натякнула на нове завдання в найближчі місяці, зазначає автор.