Show HN: Hack đối thủ bằng trò chơi cờ bàn assembly RISC-V

 (punkx.org)
3 điểm bởi GN⁺ 2023-10-01 | 1 bình luận | Chia sẻ qua WhatsApp
  • PROJEKT: OVERFLOW là một trò chơi học tập biến assembly RISC-V và buffer overflow thành luật chơi cờ bàn, để người chơi trực tiếp lần theo việc thao tác bộ nhớ, stack và địa chỉ trả về
  • Người chơi chia sẻ cùng một bộ nhớ và cùng một chương trình, rồi cạnh tranh theo kiểu lập lịch ưu tiên ngắt quãng, không có bộ nhớ ảo và chỉ thực thi 10 lệnh mỗi lượt
  • Cục diện thắng thua được quyết định ở quá trình sao chép các lệnh có sẵn để tạo shellcode, rồi ghi đè return address của đối thủ để đưa họ tới game_over()
  • Truy cập bộ nhớ sai, đọc/ghi không căn chỉnh và lệnh bất hợp pháp sẽ dẫn tới crash và chạy exception handler; việc đổi địa chỉ trap và monkeypatch nop là các biến số chiến lược then chốt
  • Có bản chơi trên web, bàn cờ để in, cùng game helper cho ESP32 và di động, nhưng một số luật vẫn đang được điều chỉnh nên hiện khá giống một câu đố hack mang tính thử nghiệm

Mục tiêu trò chơi và mô hình thực thi

  • PROJEKT: OVERFLOW là một dự án đưa assembly RISC-V và buffer overflow lên bàn cờ tabletop
  • Mục tiêu cốt lõi là sao chép các lệnh sẵn có để tạo một shellcode nhỏ trong bộ nhớ, nhảy tới đoạn mã đó bằng buffer overflow, rồi ghi đè return address của đối thủ để buộc họ gọi hàm game_over()
  • Chiến lược không chỉ dừng ở thực thi mã đơn thuần mà còn bao gồm thiết lập exception handler và cả monkeypatch
  • Tất cả người chơi chia sẻ cùng một bộ nhớ, cùng một chương trình, và dùng chung một bộ xử lý theo kiểu chia lát thời gian
    • Mỗi lượt thực thi 10 lệnh
    • stack pointer của mỗi người chơi bắt đầu ở vị trí khác nhau
    • Không có bộ nhớ ảo

Quy trình build và tạo bàn cờ

  • Mã được biên dịch bằng riscv64-unknown-elf-gcc cho đích RV32
    • Các tùy chọn chính gồm -march=rv32g, -mabi=ilp32, -ffreestanding, -nostdlib, -nostartfiles, -O0
    • Nhờ -O0, mã máy trở nên dài dòng hơn nhưng dễ lần theo hơn
  • Tài liệu cho bàn cờ được tạo bằng cách parse đầu ra riscv64-unknown-elf-objdump -S -l -fd game
    • Chỉnh sửa các lệnh ▲ và ✎
    • Đổi offset nhảy từ hệ 16 sang hệ 10
    • Dọn lại assembly và ghép với mã nguồn
    • Tạo SVG rồi chuyển sang PDF bằng Inkscape

In ấn và vật dụng cần chuẩn bị

  • Bàn cờ được dùng bằng cách in PDF phần trái và phải
  • Khổ A3 là lựa chọn được khuyến nghị, A4 cũng dùng được nhưng khá nhỏ
  • Cần chuẩn bị 1 quân cho lệnh nop, 1 quân cho địa chỉ trap, mỗi người chơi 2 quân cho program counter và stack pointer, cùng bút chì và tẩy
  • Bản web hỗ trợ chơi một mình hoặc cùng bạn bè, đồng thời cũng có game helper cho ESP32 và di động

Luật cơ bản và diễn tiến lượt chơi

  • Trạng thái ban đầu như sau
    • Tất cả thanh ghi bắt đầu từ 0, nhưng thanh ghi return address ra bắt đầu ở 1000
    • sp của Player 1 khởi tạo là 2244, sp của Player 2 là 3844
    • pc của cả hai người chơi bắt đầu ở 1000, là địa chỉ bắt đầu của hàm main
    • Quân trap được đặt ở địa chỉ 1000
    • Mọi địa chỉ bộ nhớ ngoài chương trình được nạp sẵn đều là 0
    • Quân lệnh nop ban đầu không được đặt lên bàn cờ
  • Mỗi lượt phải thực thi 10 lệnh, và các nhảy như jal, beq cũng phải được đi theo đúng như vậy
  • Người chơi có thể dừng lượt sau khi đã thực thi ít nhất 1 lệnh và chuyển số lệnh còn lại sang lượt sau
    • Số lệnh có thể tích lũy tối đa là 20

Monkeypatch và điều kiện chiến thắng

  • Ở đầu mỗi lượt, sau khi thực thi đúng 1 lệnh, người chơi có thể di chuyển quân lệnh nop tới một địa chỉ bất kỳ trong một hàm mà không có người chơi nào đang thực thi
  • Khi pc tới địa chỉ đó, lệnh tại đó sẽ hoạt động như no-operation
  • Nếu di chuyển quân nop, bạn sẽ mất lượt hiện tại và lượt kế tiếp, còn đối thủ có thể thực thi tối đa 20 lệnh ở lượt tiếp theo
  • Luật monkeypatch hiện vẫn chưa cân bằng và đang được chỉnh nhẹ vài ngày một lần
  • Ở chế độ khó, trò chơi kết thúc khi bạn hack đối thủ để buộc họ gọi hàm game_over()
  • Nếu không bên nào còn có thể đưa đối thủ vào game_over(), kết quả là hòa
  • Ở chế độ dễ, người chơi đầu tiên thực thi ret trong main để thoát vòng lặp chính sẽ thắng

Ký hiệu đặc biệt và xử lý ngoại lệ

  • ✎ cho phép chọn một số 12-bit bất kỳ từ 0 đến 4095 làm giá trị immediate của lệnh li
  • ▲ cho phép chọn một giá trị trong phạm vi ±128 byte tính từ stack pointer của chính mình ở lệnh load
    • Ví dụ, nếu sp là 2180 thì có thể chọn từ 2052 đến 2308
  • Các hành vi bị cấm sẽ dẫn tới crash chương trình
    • Ghi đè địa chỉ bộ nhớ thấp hơn 1192
    • Đọc hoặc ghi không căn chỉnh ở địa chỉ không chia hết cho 4
    • Thực thi lệnh bất hợp pháp
  • Khi crash xảy ra, exception handler sẽ chạy và nhảy tới địa chỉ trap
    • Địa chỉ trap ban đầu là 1000 nhưng có thể bị ghi đè trong hàm set_trap()
    • Khi ngoại lệ xảy ra, program counter được đặt thành một giá trị nhất định rồi tiếp tục thực thi
  • Nếu bị phát hiện gian lận hoặc mắc lỗi, trạng thái chương trình, bộ nhớ và thanh ghi của người chơi đó sẽ bị reset

Luật mở rộng cho 3~4 người chơi

  • sp của Player 3 được đặt là 2116
  • sp của Player 4 được đặt là 3716
  • Khi có từ 3 người trở lên, ký hiệu ▲ chỉ có thể dùng trong vùng cách stack pointer 128 byte về phía âm
  • Khi chơi với hơn 2 người, trò chơi trở nên khá bất ổn và xuống cấp rất nhanh
  • Việc đạt điều kiện chiến thắng sẽ khó hơn, nhưng trải nghiệm chơi lại vui và hỗn loạn hơn

Ví dụ chiến lược hack

  • Crash có thể được dùng như một chiến lược tấn công để chặn tiến trình của đối thủ
  • Nếu đổi trap handler thành hàm game_over, người chơi crash đầu tiên sẽ thua
    • Trong trạng thái này, quân nop trở nên cực kỳ mạnh
    • Nếu đối thủ đặt nop lên lệnh ret của hàm mà bạn đang thực thi, bạn có thể thua
  • Trong hàm bug(), nếu làm overflow chỉ số thành 400 hoặc -400 thì có thể truy cập stack của đối thủ và ghi đè return address của họ
    • Ví dụ, để đi từ địa chỉ 3784 tới 2184 thì (3784 - 2184) / 4 = 400, nên cần chỉ số -400
  • Có thể dùng hàm copy() để sao chép các lệnh cụ thể và dựng một shellcode ngắn trong bộ nhớ
    • Một shellcode ví dụ dùng tổ hợp li a4, ✎, li a5, ✎, sw a4, 0(a5), ret để thực hiện ghi tùy ý
    • Nếu sao chép lệnh ret, return address sẽ được đặt thành điểm bắt đầu shellcode và gây ra vòng lặp vô hạn
  • Trong hàm bug(), nếu đặt chỉ số là 6 thì có thể ghi biến value đè lên địa chỉ return đã lưu trên stack là 28(sp)
    • Khi bug() trả về, giá trị ở 28(sp) sẽ được chép vào thanh ghi return address
    • Nếu ghi địa chỉ shellcode đã tạo vào đó, bạn có thể nhảy vào bộ nhớ

Diễn giải lệnh và các thay đổi

  • Mọi lệnh nhảy đều là nhảy tương đối theo program counter hiện tại, dù trong disassembler chúng có thể trông như địa chỉ tuyệt đối
    • Ví dụ, mã máy 1903 của jal a4, 0 khi thực thi sẽ thành vòng lặp vô hạn
  • Danh sách các lệnh hợp lệ trong game được tổng hợp từ các lệnh RV32 JRI có mã máy từ 0 đến 4095, ở các dạng dùng a0, a4, a5, sp, ra v.v.
  • Nhật ký thay đổi 0.0.6 có thay đổi từ while(run) sang while(*prun)
    • Đối thủ giờ có thể ép crash bằng cách dẫn tới dereference không căn chỉnh
    • Luật NOP cũng đã đổi để chỉ cho phép đặt trong các hàm hiện không được thực thi

Thiết kế và tài liệu học tập

  • Các hình chữ nhật ở hai bên bàn cờ là một thông điệp nhị phân được mã hóa bằng ASCII
    • Hình chữ nhật trắng là 1, hình chữ nhật đen là 0
  • Màu sắc chỉ dùng đỏ, xanh dương, đen và trắng để phù hợp với in ấn giá rẻ và khả năng đọc trên máy in đen trắng
  • Không dùng syntax highlighting
    • Đây là lựa chọn để tránh việc một số phần mã trông có vẻ quan trọng hơn chỉ vì theme, và để người chơi tự đánh giá, tự tập trung
  • Tài liệu học assembly RISC-V gồm riscv-programming.org, cs3410 risc-v interpreter, rvcodecjs của luplab
  • Tài liệu học C sử dụng phần đầu của Beej's Guide to C Programming
  • Ngoài ra còn có PDF bài tập assembly để in về biến, gọi hàm, con trỏ, chuỗi, struct, mảng, đệ quy, cùng một phiên bản “assembly hangman” kiểu điền vào chỗ trống

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-10-01
Các ý kiến trên Hacker News

  • Thật sự ấn tượng. Đặc biệt, điều tuyệt nhất có vẻ là đã khiến cô con gái 12 tuổi cùng chơi trò này
    Khi nào có thể kỳ vọng phiên bản CHERI? :-D

    • Kiểu như “CHERI có ba mục tiêu thiết kế cốt lõi nhằm cải thiện đáng kể tính bảo mật của TCB C hiện đại thông qua hỗ trợ từ bộ xử lý cho bảo vệ bộ nhớ chi tiết và cách ly phần mềm có khả năng mở rộng; các yêu cầu đôi khi xung đột nhau này đòi hỏi phải cân chỉnh cẩn thận trong thiết kế”, nên có lẽ phiên bản CHERI sẽ khó đấy :)
    • Hồi 12 tuổi tôi đã viết assembly 6502. Trong môi trường máy tính ngày nay, một đứa trẻ 12 tuổi không dễ làm như vậy
    • Thời 8-bit, đó là độ tuổi khá phổ biến để bắt đầu làm quen với máy tính

  • Core War là trò chơi diễn ra trong đấu trường bộ nhớ của một máy ảo hỗ trợ một ngôn ngữ assembly mô phỏng đơn giản. Tôi thấy nó lần đầu trên Scientific American năm 1984, và vì khi đó đã lập trình khoảng 15 năm nên tôi nhận ra nó được lấy cảm hứng từ trò chơi cũ hơn của Bell Labs là Darwin
    Darwin được tạo ra năm 1961 và chạy trên IBM 7090. Các chương trình cạnh tranh tài nguyên với nhau; chương trình nào sao chép để chiếm toàn bộ không gian được cấp phát sẽ thắng. Sau khi Robert Morris Sr. tạo ra một chương trình không thể bị đánh bại, nó không tồn tại được lâu. Xem [2]
    Vào giữa thập niên 1970, Software Practice and Experience là một trong những tạp chí khoa học máy tính tôi thích nhất, và thường có chuyên mục Computer Recreations viết dưới bút danh Aleph-Null. Hồi học cao học, tôi đã rất vui khi tự triển khai vài trò chơi trong chuyên mục đó. Tạp chí thì đắt, nhưng nếu là sinh viên đại học, nhiều khả năng bạn có thể tìm thấy nó trong thư viện trường như tôi ngày trước. Các số thập niên 1970 có những chủ đề như trình biên dịch Pascal, Algol 68, lập trình đồng thời; đọc dễ hiểu và thú vị, và qua các bài viết của N. Wirth tôi đã biết đến Module[3,4] rồi sau đó là Oberon[5]
    [1] https://en.wikipedia.org/wiki/Core_War
    [2] https://en.wikipedia.org/wiki/Darwin_(programming_game)
    [3] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43800701...
    [4] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43800701...
    [5] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43801909...

  • Tôi từng có một người bạn nói rằng thích game nhưng không có đầu óc lập trình; thế mà qua Human Resource Machine, về cơ bản anh ấy đã lập trình, và một số lời giải còn tốt hơn của tôi dù tôi có nhiều năm kinh nghiệm

    • Đôi khi một góc nhìn mới giúp ích nhiều hơn ta tưởng
      Đứa con 12 tuổi của tôi ghét toán, nhưng lại chơi Human Resource Machine và SpaceChem giỏi đáng kinh ngạc. Điều đó khiến tôi tự hỏi liệu toán ở phổ thông và toán trong lập trình có khác nhau về căn bản không

  • Rất thú vị. Nhìn vào dung lượng bộ nhớ máy tính ngày nay, tôi luôn cảm thấy mnemonic ngắn là một lựa chọn kỹ thuật không hay
    Ở đây cũng vậy, việc đầu tiên phải làm là học và nhớ từng lệnh làm gì. Nếu đổi tên sang dạng diễn giải đầy đủ hơn, việc học, ghi nhớ và đọc mã sẽ dễ hơn nhiều. Việc mọi người không thường làm như vậy khiến tôi thấy đáng nghi
    Việc loại lỗ hổng này có thể tồn tại cũng cho thấy sự thất bại trong thiết kế toàn hệ thống. Điều đó không có nghĩa đây không phải là trò chơi vui hay cách học tốt, nhưng trong kỹ thuật, các vấn đề mang tính cấu trúc đang được chấp nhận quá dễ dàng. Phần lớn thậm chí còn không nhìn thấy khiếm khuyết cấu trúc đó

    • Ở phiên bản đầu có một dạng pseudo-assembly dễ đọc hơn nhiều, và tôi cũng đã nghĩ theo hướng đó. Nhưng cuối cùng tôi muốn con gái mình đọc đầu ra objdump một cách thoải mái, và tôi không nghĩ học vài mnemonic là vấn đề lớn
      Tôi nghĩ trẻ em phản hồi rất tốt khi ta không coi thường chúng. Ít nhất con tôi là như vậy
      Bạn có nghĩ có người không xem đọc và ghi tùy ý là khiếm khuyết cấu trúc không? Hàng nghìn người đang xử lý vấn đề đó và cũng đã đạt được khá nhiều tiến bộ. Đồng thời, tôi vẫn thấy peek và poke rất vui

  • Cái này thật sự tuyệt. Muốn thử ở công ty

  • Trông khá thú vị. Bạn nghĩ phù hợp với độ tuổi nào?

    • Điều kiện thắng dễ, tức thoát khỏi vòng lặp chính bằng một buffer overflow nhanh trong bug(), tôi nghĩ trẻ 10–15 tuổi cũng làm được
      Con gái tôi 12 tuổi và chúng tôi đang chơi rất vui cùng nhau. Điều kiện thắng khó, tức khiến đối thủ nhảy đến hàm game_over(), thì khó hơn, nhưng tôi nghĩ có thể đạt tới trong 5–6 tháng
      Người lớn thì tôi không chắc. Một số người sợ assembly như thể nó do quỷ tạo ra, nên có khi còn khó khiến họ chơi hơn trẻ con

  • Điều thú vị là chúng ta có xu hướng nhìn thế giới như tấm gương phản chiếu chính mình
    Việc tôi quan tâm đến buffer overflow và lập trình rồi cho rằng con gái mình đương nhiên cũng sẽ rất quan tâm thì có xác suất đến mức nào? Nếu lại còn là con đầu lòng và là con gái thứ hai thì xác suất có vẻ thấp hơn nữa, nhưng tôi vẫn thấy nhiều ông bố cứ thúc đẩy
    Khi làm những dự án kiểu này, tôi tò mò liệu ít nhất ở mức nào đó người ta có ý thức rằng đây là một dự án hư vinh hay không. Dù sao thì tôi cũng quan tâm đến những thứ như vậy, nên rất vui vì nó được công bố

    • Điều còn thú vị hơn là người ta có thể vô tư đưa ra những giả định lớn đến đâu để làm cho lập luận của mình nghe có vẻ hợp lý
      Bạn đang ám chỉ rằng người tạo dự án ép con gái làm việc này vì tính hư vinh của mình, nhưng căn cứ ở đâu? Tôi đã xem vài trang trên site mà chẳng thấy gì gợi ý như vậy; ngược lại còn có nhiều cách diễn đạt nhẹ nhàng cho thấy cô bé vui vẻ và rất hứng thú
      Vì sao lại loại trừ khả năng cô bé là người bắt đầu, vì cứ tò mò bố mình làm gì trên máy tính? Có thể nó bắt đầu nhỏ thôi, rồi phát triển thành một quá trình hai chiều giữa người chia sẻ mối quan tâm và một bạn đồng hành khám phá nhỏ tuổi
      Thực tế thế nào thì tôi cũng không biết, nhưng bạn cũng không biết. Từ góc nhìn của người từng tham gia giáo dục vài năm, trẻ em nói chung là những người học giỏi hơn nhiều so với niềm tin phổ biến. Cấu trúc trường học có lẽ cũng là một lý do, nhưng cốt lõi có thể là kiểu niềm tin giới hạn như thế này. Tôi muốn vỗ tay cho người cha đã cố chia sẻ mối quan tâm và niềm đam mê của mình với con gái và với thế giới
    • Là một người cha, tôi chỉ đang cố dạy mọi thứ mình có thể. Đôi khi là lập trình, đôi khi là võ thuật, đôi khi là thiền
      Một số trong đó sẽ có giá trị, một số thì không. Xác suất luôn bất lợi. Cuộc sống vốn là vậy

  • Khi đường mã RISC-V 64-bit ổn định, hoạt động đủ tốt và ngay cả “buffer overflow” cũng biến mất, trong bối cảnh C/C++ không phải lúc nào cũng chịu thay đổi cú pháp, các bạn định xử lý sự lỗi thời có kế hoạch thế nào? Những linh hồn tội nghiệp…

  • Khoan đã.
    Một board game để bàn có viết code assembly ư? Sao trước giờ mình không nghĩ ra nhỉ? :D

  • PL/I đã làm đúng các phần như kiểm tra biên chuỗi/mảng, stack tăng lên trên thay vì xuống dưới
    https://www.acsac.org/2002/papers/classic-multics.pdf