Giải mã thử thách đảo ngược ASIC của Jane Street: Hành trình từ GDS đến thông điệp bí ẩn
Một kỹ sư đã chiến thắng thử thách đảo ngược kỹ thuật ASIC của Jane Street, biến các tệp GDS phức tạp thành một mạch điện hoạt động. Bài viết hé lộ quá trình gian nan từ việc tự xây dựng trình mô phỏng, học Verilog, cho đến dùng trình giải ràng buộc Z3 để tìm ra thông điệp cuối cùng (* TWO STARS *).
Giải mã thử thách đảo ngược ASIC của Jane Street: Hành trình từ GDS đến thông điệp bí ẩn
Jane Street thường xuyên tung ra các thử thách kỹ thuật, và lần này đã khiến một kỹ sư tên Chris lao vào một cuộc phiêu lưu kéo dài cả tháng trời. Thử thách yêu cầu người chơi phân tích ngược một con chip ASIC từ tệp GDS để tìm ra thông điệp ẩn giấu. Hành trình này trải qua vô số khó khăn, từ việc tự xây dựng công cụ cho đến việc sử dụng các trình giải toán phức tạp.
Thử thách bắt đầu
Chris, một kỹ sư có bằng cấp về kỹ thuật, đã quen thuộc với các thuật ngữ như ASIC (Application-Specific Integrated Circuit) – một loại chip được thiết kế riêng cho các tác vụ cụ thể để đạt hiệu suất cao hơn. Thử thách đưa ra một tệp GDS (mô tả thiết kế hình học của chip) và yêu cầu làm ngược lại để hiểu chức năng của nó. Thậm chí, tác giả còn không biết GDS là viết tắt của từ gì, nhưng vẫn bắt tay vào khám phá.
“Tôi có một tấm bằng kỹ thuật đang mục nát trong đầu, nên nhiều từ ngữ trong thử thách khá quen thuộc.”
Thử thách có hai phần: một phần khởi động với nhiều thông tin hỗ trợ và một phần chính với độ khó cao hơn nhiều, khiến tác giả mất ngủ suốt ba tuần.
Khám phá các tệp GDS
Ban đầu, Chris mở các tệp GDS và thấy những từ quen thuộc như clk (clock), rst (reset), VGND (điện áp đất) và VPWR (điện áp nguồn). Ngoài ra, có các thành phần với tiền tố sky130_fd_sc_hd__ kèm theo các tên logic như or, not – dường như là các cổng logic. Sử dụng thư viện Python gdstk, tác giả xác định có 27 phần tử trong bài khởi động.
Có một tệp vcd (mô phỏng tín hiệu) trong bài chính, và khi viết một chương trình C nhỏ để đọc, Chris nhận được kết quả TRY AGAIN. Điều này chứng tỏ mạch điện có chứa các thông điệp được mã hóa bên trong.
Lạc lối trong những ngã rẽ kỹ thuật
Thay vì nghiên cứu tài liệu, Chris quyết định tự xây dựng mọi thứ từ đầu – một cách tiếp cận mà anh thừa nhận là “chọn con đường khó”. Điều này dẫn đến việc viết một trình mô phỏng mạch điện bằng cách sử dụng sqlite3 làm nền tảng. Sau đó, anh lại viết thêm một ngôn ngữ mô tả phần cứng để thiết kế mạch dễ dàng hơn, và tiếp tục xây dựng một bộ khung kiểm thử.
Chưa dừng lại ở đó, Chris còn viết một trình xem GDS bằng thư viện raylib, nhưng cuối cùng nhận ra mình đã đi quá xa so với mục tiêu ban đầu. Tác giả khuyên người đọc: “Bạn có thể bỏ qua phần này. Tôi ước gì mình đã làm vậy.”
Tìm kiếm tài liệu và hiểu cấu trúc
Sau khi từ bỏ các công cụ tự viết, Chris quay lại với các công cụ có sẵn như trình xem GDS được giới thiệu trên blog của Jane Street. Anh dành thời gian quan sát các lớp vật liệu khác nhau trong tệp GDS, tưởng tượng nó giống như một máy in 3D với các lớp và chiều sâu chuẩn hóa.
Chìa khóa đến từ việc chuyển tệp GDS sang định dạng SVG – nó chứa văn bản mô tả về các thành phần. Điều này giúp Chris xác định được đâu là đầu vào và đầu ra. Sau đó, tác giả tìm đến tài liệu chính thức của sky130 – một tiêu chuẩn thiết kế chip cho phép hiểu chức năng của từng phần tử logic.
“Tôi nhận ra rằng tài liệu có câu trả lời cho nhiều câu hỏi của mình. Tại sao tôi luôn chọn con đường khó?”
Sử dụng thông tin từ tài liệu và nhãn từ SVG, Chris có thể ánh xạ hình học đến các cổng I/O. Điều may mắn là thư viện hỗ trợ kiểm tra sự chồng lấn giữa các thành phần trong không gian 2D. Kết quả hoạt động tốt hơn mong đợi vì nhãn được tham chiếu từ trung tâm của chúng.
Sơ đồ minh họa quá trình phân tích
Xây dựng mô hình mạch điện
Với hơn 1k đường dẫn và gần 17k đa giác, việc trích xuất một mạch điện từ tệp GDS không hề dễ dàng. Chris phát triển một thuật toán để tìm các thành phần “chạm nhau” – tức nằm trên các lớp liền kề và chồng lấn. Anh cũng thêm bước đơn giản hóa bằng cách “nén” các đoạn dây thành một dây duy nhất nếu chúng chạm nhau.
Nhờ kinh nghiệm luyện giải thuật trên LeetCode trong thời gian thất nghiệp, Chris xử lý các thuật toán đồ thị một cách khá trôi chảy. Anh dần chuyển đổi mạng lưới thành mô tả phần cứng bằng ngôn ngữ Verilog, cho phép chạy mô phỏng cơ bản.
Kiến trúc tổng thể của mạch
Sau nhiều ngày vật lộn và sửa lỗi, Chris hiểu được các thành phần chính của bài khởi động: hai thanh ghi dịch, một bộ cộng và một bộ so sánh được đặt tên là comparitor496. Anh biết rằng đầu vào cần tổng bằng 496, và sau vài giờ cố gắng, mô phỏng đã chạy thành công. Đây là cột mốc quan trọng cho thấy khả năng giải quyết thử thách chính.
Bước vào thử thách thực sự
Phần chính của thử thách có nhiều loại thành phần hơn (81 so với 20) và số lượng lớn hơn (gần 10k so với 1k). Quá trình trích xuất mạch mất gần một phút thay vì hai giây như trước. Chris tối ưu hóa bằng cách sắp xếp lại bước thu thập đoạn dây, giúp tăng tốc 100 lần, nhưng bước tìm thành phần kết nối vẫn là điểm nghẽn.
Một trong những phát hiện thú vị nhất là khi Chris tìm thấy một dây không được điều khiển – một điều bất thường vì ngay cả khi không quan tâm đến giá trị, người ta vẫn thường kéo nó về một mức xác định. Sau khi kiểm tra trực quan, anh xác định rằng mã của mình đang đọc đúng một dây chỉ kết nối với hai chân đầu vào. Điều kỳ lạ hơn là có một kết nối ở chân lân cận không phải đầu vào hay đầu ra.
Chris đã báo cáo lỗi này cho Jane Street và nhận được phản hồi xác nhận rằng anh đã đúng! Dù lỗi không ảnh hưởng đến kết quả thử thách, tác giả tự hào coi đây là một trong những thành tựu kỹ thuật đáng nhớ nhất của mình.
Tầm nhìn tổng quan
Sau khi lập bản đồ các mạch con và dây kết nối, Chris nhận ra rằng phần kích hoạt tín hiệu thành công có 6 dây. Hai trong số chúng tự động chuyển trạng thái sau một số chu kỳ xung đồng hồ nhất định, nên thực tế chỉ cần giải quyết 4 dây còn lại.
Các mạch con ở phía bên trái hoạt động như một bộ tạo tín hiệu, nuôi các phần khác của mạch. Kết hợp các yếu tố, tác giả thấy mạch cần 120 hoặc 121 xung trước khi đầu ra chuyển trạng thái cao, khớp với dạng sóng được cung cấp trong ví dụ.
Ngã rẽ bất ngờ
Chris mất 2-3 ngày không thể làm cho mô phỏng tổng thể hoạt động dù đã kiểm tra từng thành phần con. Cuối cùng, anh phát hiện ra mình quên thiết lập chân reset – giống như quên khởi động xe và tự hỏi tại sao xe không chạy. Khi khắc phục, tín hiệu TRY AGAIN xuất hiện ngay lập tức.
Thử nghiệm thêm với các đầu vào khác nhau, Chris phát hiện nhiều thông điệp ẩn:
| Đầu vào | Đầu ra |
|---|---|
| Sai | TRY AGAIN |
| Tất cả là 0 | EMPTY SKY |
| Tất cả là 1 | BIG BANG |
| Đúng |
Giải mã câu đố ngược
Thử thách lớn nhất là đầu vào có 120 bit và không thể thử nghiệm toàn bộ các khả năng trong thời gian sống của con người. Chris có một ý tưởng táo bạo: chạy mô phỏng ngược. Thay vì tìm đầu ra từ đầu vào, anh biết đầu ra mong muốn ở bước 120 và mạch bắt đầu với tất cả đầu ra bằng 0. Bằng cách viết lại đầu ra mong muốn thành hàm của bước trước đó, vấn đề trở thành một bài toán có thể giải được bằng toán học.
Chris tập trung vào thanh ghi dịch – thành phần quen thuộc từ bài khởi động. Vì mạch phụ thuộc vào các giá trị trước đó, anh cần một trình giải ràng buộc. Trước khi học cách sử dụng công cụ chuyên dụng, anh thử dùng bảng tính (spreadsheet) để viết Verilog – một cách tiếp cận “quái dị” nhưng bất ngờ hoạt động cho hai dây đầu tiên.
Sức mạnh của trình giải Z3
Sau khi chứng minh phương pháp giải ngược khả thi, Chris chuyển sang công cụ mạnh mẽ hơn: Z3 – một trình giải ràng buộc thỏa mãn (SAT solver). Anh có thể đưa ra hàng nghìn ràng buộc như “dây này không bao giờ ở mức thấp” hay “dây này phải ở mức cao ở bước 120” và Z3 sẽ tìm giải pháp trong nháy mắt.
“Mỗi lần nó tìm ra giải pháp, tôi lại trào dâng niềm vui. Thật kỳ diệu!”
Việc dịch mạch điện sang các ràng buộc cho Z3 được làm thủ công từng bước. Chris lần lượt xử lý khoảng 24 dây cần ở mức cao cùng lúc. Một phát hiện quan trọng: cấu trúc đầu vào nhiều thành phần dường như chỉ cần hai xung ở bội số của 11, xác định bởi giá trị bộ đếm.
Khi kết hợp tất cả các ràng buộc thành một tập lệnh duy nhất và sửa hết lỗi, kết quả xuất hiện chính là thông điệp cuối cùng: *( TWO STARS *)**.
Kết quả cuối cùng của mạch
Kết luận và bài học
Sau khi gửi giải pháp cho Jane Street và nhận xác nhận vào sáng hôm sau, Chris hoàn thành thử thách. Anh chia sẻ rằng mặc dù có thể giải quyết nhanh hơn bằng cách nghiên cứu tài liệu kỹ lưỡng hơn từ đầu, nhưng hành trình tự mò mẫm đã mang lại những kiến thức và kinh nghiệm quý giá.
“Tôi nhận ra rằng nếu nhìn vào đầu vào lâu hơn một chút, tôi có thể nhận ra quy luật sớm hơn. Nhưng tôi đã quá lao sâu vào lớp dưới cùng mà quên quan sát những gì hiện ngay trước mắt.”
Câu chuyện của Chris là minh chứng cho sự kiên trì, đam mê và khả năng giải quyết vấn đề sáng tạo. Với những ai quan tâm đến kỹ thuật đảo ngược hoặc các thử thách tương tự, đây là một nguồn cảm hứng tuyệt vời.
Jane Street có thể sẽ sớm tung ra thử thách mới trong vài tháng tới, và Chris cho biết anh sẵn sàng đón nhận. Còn bạn, nếu có hứng thú với những thử thách kỹ thuật, hãy bắt đầu từ những điều nhỏ nhất và đừng ngại chọn “con đường khó” – vì đôi khi nó lại dẫn đến những khám phá bất ngờ nhất.
