Jane Street'in ASIC bulmacası bir geliştirici tarafından bir ayda çözüldü

Jane Street'in kamuya açık görevleri mühendisleri uzun dolambaçlara sürüklemesiyle bilinir. Bunlardan biri, "Can you reverse engineer an ASIC?" başlıklı donanım bulmacası, Jestoph adıyla blog yazan geliştirici Chris'i yaklaşık bir ay meşgul etti; 4 Eylül'de çözümünü ayrıntılı biçimde yayımladı.

Bulmaca ne istiyordu

Görev, bir GDS dosyasını — silikon yerleşiminin tanımını — alıp devrenin ne yaptığını tersten bulmak. ASIC, yani uygulamaya özel tümleşik devre, genel hesaplama yerine tek bir iş için tasarlanmış bir çiptir. Bulmaca iki bölümden oluşuyordu: çipin gerçek tasarımının verildiği bir ısınma turu ve yazarın ifadesiyle yalnızca "sıkı bir tokalaşma ve bir 'iyi şanslar'" ile gelen asıl bulmaca.

Ham yerleşimden çalışan simülasyona

İlk ipucu bulmacayla birlikte verilen VCD dosyasıydı. Kısa bir C programıyla okunması "TRY AGAIN" mesajını üretti; yani devre metin taşıyor. Ardından yerleşim dosyalarını açmak için Python'un gdstk kütüphanesini kullandı, ancak sonrasında kendi devre simülatörünü, bir donanım tanımlama dili ayrıştırıcısını ve test ortamını yazdı — bugün bu sapmaları büyük ölçüde boşa harcanmış zaman olarak tanımlıyor. Isınma turunda 27 eleman vardı; asıl bulmacada ise 81 tipten yaklaşık 10.000 bileşen (ısınmada 20 kadar tip) bulunuyordu; filtrelemeden sonra yaklaşık 1.000 hat yolu ve 17.000 poligon kaldı.

Bulmacanın kendi içindeki hata

Simülasyon, yalnızca iki giriş pinine bağlı, sürülmemiş bir tel ile ne giriş ne de çıkış olan bir pini ortaya çıkardı. Durumu Jane Street'e bildirdi ve ertesi gün haklı olduğuna dair onay aldı; ancak bu kusur bulmacanın sonucunu etkilemiyor. Bu hata bildirimini en sevdiği teknik başarılarından biri olarak niteliyor.

Kısıt çözücüyle tersten çözüm

120 bitlik bir girdiyi tümüyle taramak gerçekçi olmadığından tasarımı zamanda geriye doğru çalıştırdı ve istenen sinyalleri kısıt olarak z3 çözücüsüne verdi. Aynı anda yaklaşık 24 telin yüksek olması gerekiyordu; 22'sini tek tek elde etti, kalanlar ise çoğu eleman girişinin 11'in katlarında yalnızca iki darbeye ihtiyaç duyduğunu fark edince çözüldü. Tam simülasyon kazandıran çıktıyı verdi: "(* TWO STARS *)". Devre ayrıca tümü sıfır girdiye "EMPTY SKY", tümü bir girdiye "BIG BANG" yanıtını veriyor. Yazar, Jane Street'in önümüzdeki aylarda yeni bir bulmaca ima ettiğini belirtiyor.