Jane Street のリバースエンジニアリングチャレンジを解く

なぜいつも私は難しい方法を選ぶのだろうか？ Jane Street は定期的にチャレンジを提供しており、今回も私は完全に魅了され、1ヶ月にわたる深い探求に没頭し、ようやく抜け出そうとしています。この記事は、私の粘り強さと睡眠不足の組み合わせで、どのようにそれを解決したかの概要です。かなり技術的になりますが、もし興味があれば、各ステップの詳細については今後の投稿で触れる予定です。背景として、Jane Street のブログにある元の投稿「Can you reverse Engineer an ASIC?」を読むことをお勧めします。また、このチャレンジのために使った（ひどい）コードを読みたい場合は、私の github ページで見つけることができます。 チャレンジ受諾 私の脳のどこかに無駄になっている工学の学位があるので、チャレンジの言葉の多くは馴染みがあります。チャレンジは、ASIC を受け取り、それが何をするかを理解することです。ASIC に馴染みのない方のために説明すると、「ASIC」は Application-Specific Integrated-Circuit の略で、私たちが通常「コンピュータチップ」と呼ぶもののための派手な言葉です。Jane Street のような企業は、おそらく、通常のメーカーから購入できる機器と比較して追加のパフォーマンスを得るためにこれらを設計しています。いずれにせよ、チャレンジは「GDS」ファイル（チップを記述したもの）を受け取り、それを逆方向にたどって何をするかを理解し、おそらくそこにパスワードか何かがあるのだろうということです。私は「GDS」が何の略か知りませんでしたし、今でも知りません。チャレンジには2つのパートがあります。1つはウォームアップで、チップの実際の設計など、より多くの情報が提供されます。もう1つは実際のパズルで、しっかりとした握手と「幸運を祈る」という言葉だけが与えられ、今後3週間眠れない可能性に直面します。 ファイルの中身は？ なぜか、私は物事を難しい方法でやるのが好きなので、リサーチをする代わりにファイルの中を調べ始めました。「clk」（クロック）、「rst」（リセット）、「VGND」（グラウンド電圧）、「VPWR」（電源電圧）のような馴染みのある言葉が見えます。そして、sky130_fd_sc_hd__ という接頭辞を持つ何かがたくさんあり、その後に「or」や「not」のような論理要素のように聞こえるものが続きます。おそらく、ファイルから引き出す必要があるのはこれらでしょう？ Python の非常に優れたライブラリ「gdstk」を見つけました。これはそれらを読み取れるようです。ウォームアップパズルには27個の要素があると教えてくれます。 % python3 -c 'print(len(__import__("gdstk").read_gds("warmup/04_final.gds").cells))' 27 メインパズルには「vcd」ファイルもあります。これはテキストファイルで、おそらくシミュレーションの入力または出力のようなものです。「vcd」が何の略か、私は知りませんでしたし、今でも知りません。その中には、ASCII 文字のように見える疑わしいエントリがいくつか見えます。それをいじって、小さな C プログラムを書き、出力「TRY AGAIN」を得ました。ああ、つまり回路には何らかの方法でメッセージが埋め込まれているのです！ $ gcc what-is-this-thing.c && ./a.out T R Y A G A I N T R Y A G A I N よし、何か掴んだぞ 気を散らして時間を無駄にしている。そして私の人生を。ここでは、大きな脱線をしなければならず、もちろん、独自の回路シミュレータを構築しなければなりません。理由があって。このセクションはスキップしても構いません。私は確かにそうしたかった。数日後 よし、sqlite3 をドライバとして使って回路シミュレータを構築しました。本当にかなりクールです。しかし、Python で回路を設計するのは非常に難しいです！ハードウェアを記述するための言語があればいいのに。 数日後 よし、新しい言語のパーサーを構築したので、回路を設計できるようになりました。しかし、テストする必要があります！スクリプトで入力を与え、出力を検証する方法があればいいのに。 数日後 よし、回路シミュレータのハーネスを構築しました。しかし、それが何をしているのかを視覚化するのは非常に難しいです！もし〜があれば…まあ、どこに向かっているかはわかりますね。 数日後 よし、波形ビューアを書くのを諦めて、「surfer」を使うことにしました。しかし、これらの gds ファイルは扱いにくいです。どうすればそれを簡単にできるでしょうか？ 数日後 よし、raylib で基本的な GDS ビューアを書きましたが、ブロックを望むように配置できません。とにかく、私はあまりにも多くの脇道にそれていることに気づき、カスタムソフトウェアをすべてドロップする時が来ました。よし、そのセクションは終わりです。スキップしてくれて嬉しいでしょう？ 集中しろ、クリス、集中しろ。 Jane Street のブログは、実際には非常に便利な GDS ビューアを指しているので、私はそれにしばらくの間じっと見つめ、何か思いつくことを願っていました。入力のいくつかが何であるかを大まかに注釈付けすることができ、後でファイルのワイヤのおおよその位置を見ることでそれを確認できました。これがウォームアップだったので、私が回路について知っていることと、私が見ることができるものを比較することができました。これらのファイルは何を表しているのか？これらのファイルには、さまざまな種類の材料などの「レイヤー」の感覚があるようです。大きな3Dプリンターのようなもので、プリントヘッドをどこに動かすべきか、そしてどの深さに新しい材料を置く必要があるかを指示する必要があるようなものだと想像します。これらのファイルは機械への指示に近いのでしょうか？しかし、垂直空間に任意の配置があるのではなく、標準的な幅の標準レイヤーがあるように見えるので、それは物事を単純化します。少なくともこれらのファイルで操作できることを証明したかったので、右上隅にある Jane Street のロゴを抽出しようとしました。なぜかこれは思ったよりもはるかに難しく、Jane Street のロゴ以外のすべてを抽出してしまいましたか？でも、まあ、十分でしょう、先に進みましょう。 また、ある時点で、私が使用しているライブラリが要素を SVG ファイル形式に抽出できること、そして要素の部分を説明する多くのテキストが含まれていることを発見しました。これはチャレンジを実際に理解するための鍵となるでしょう。なぜなら、それらの情報を使って、どの部分が入力でどの部分が出力であるかを推測できるかもしれないからです。これらの要素について実際に読む時間です。推測でできるところまで来ました。まともなドキュメントを読む時間です。 「sky130-unofficial」という名前にもかかわらず、これが公式の場所のようです。ドキュメントには私の多くの質問への答えがありました。なぜいつも私は難しい方法を選ぶのだろうか？この「sky130」というものは、チップを作るための…標準？または何かのようです。チップを作るのは難しいので、共通のデザイン要素があるのは理にかなっていると思います。特に、要素が何をするかの説明も含まれています。「and」のような要素は「andゲート」である可能性が高いので簡単ですが、「o21bai」のような要素は…まあ、あまり心配しないでください。 ドキュメントの情報と SVG のラベルから、特定のジオメトリを回路要素の I/O にマッピングできるようになりました。これは、それを「実際の回路」に変換する最初のステップになるでしょう。ここで非常に幸運なことに、私のライブラリは2D空間で2つの要素が重なっているかどうかをチェックする機能を持っています（これらの gds ファイルは実際には3Dジオメトリの記述であることを思い出してください）。ラベルが正しい場所に重なっているという仮定がどれほど合理的かはわかりませんでしたが、予想よりもはるかにうまく機能しました！ラベルはすでに中心点で参照されているようです！視覚的には接続されていないように見えるジオメトリもいくつか検出されました。視覚的な検査では決して明らかにならなかったでしょう。そして、全体のデザインの IO ポートを見ると、視覚的なノイズがはるかに少なくなりました。グラフを作成できると思いますか？この gds ファイルから回路を抽出するために必要なものはすべて揃ったと思います。これは簡単ではありません。このものには、無視するすべてを無視した後でも、1k のパスとほぼ17k のポリゴンがあります。私は「接触している」ものを見つける方法を見つける必要があります。これは、それらが隣接するレイヤーにあり、かつ重なっていることを意味します。私のアルゴリズムはひどいものですが、今のところは機能します。また、「ワイヤセグメント」をすべて取り出して…圧縮？または統合？して単一のワイヤにする単純化ステップも導入します。ロジックは、2つのワイヤが接触している場合、それは私の視点からは実際には同じワイヤであるということです。幸いなことに、昨年失業中に数週間 LeetCode を grinding していたので、いくつかのグラフアルゴリズムが私を遅くさせることはありませんでした。数日後 次の数日間 o