- PROJEKT: OVERFLOW เป็นเกมเพื่อการเรียนรู้ที่นำภาษาแอสเซมบลี RISC-V และ buffer overflow มาแปลงเป็นกติกาบอร์ดเกม ให้ผู้เล่นได้ไล่ตามการจัดการหน่วยความจำ, stack และ return address ด้วยตัวเอง
- ผู้เล่นแข่งขันกันโดยใช้ หน่วยความจำและโปรแกรมเดียวกัน ร่วมกัน ไม่มี virtual memory และใช้การจัดตารางแบบ preemptive ที่รันได้เทิร์นละ 10 คำสั่ง
- ผลแพ้ชนะตัดสินจากกระบวนการคัดลอกคำสั่งเดิมเพื่อสร้าง shellcode แล้วเขียนทับ return address ของคู่แข่งให้ส่งไปยัง
game_over() - การเข้าถึงหน่วยความจำผิดพลาด, การอ่าน/เขียนแบบไม่จัดแนว และคำสั่งผิดกฎหมาย จะนำไปสู่ crash และการรัน exception handler โดยการเปลี่ยน trap address และ
nopmonkeypatch เป็นตัวแปรสำคัญของกลยุทธ์ - มีการเล่นผ่านเว็บ, บอร์ดสำหรับพิมพ์, ตัวช่วยเกมบน ESP32 และมือถือ แต่กติกาบางส่วนยังอยู่ระหว่างปรับ จึงใกล้เคียงกับพัซเซิลแฮ็กเชิงทดลอง
เป้าหมายของเกมและโมเดลการรัน
- PROJEKT: OVERFLOW เป็นโปรเจกต์ที่นำภาษาแอสเซมบลี RISC-V และ buffer overflow มาทำเป็นบอร์ดเกมตั้งโต๊ะ
- เป้าหมายหลักคือคัดลอกคำสั่งเดิมเพื่อสร้าง shellcode ขนาดเล็กในหน่วยความจำ จากนั้นใช้ buffer overflow เพื่อกระโดดไปยังโค้ดนั้น แล้วเขียนทับ return address ของคู่แข่งให้เรียกฟังก์ชัน
game_over() - กลยุทธ์ไม่ได้มีแค่การรันโค้ดธรรมดา แต่รวมถึงการตั้งค่า exception handler และ monkeypatch ด้วย
- ผู้เล่นทุกคนใช้หน่วยความจำเดียวกันและโปรแกรมเดียวกันร่วมกัน และใช้โปรเซสเซอร์เดียวกันแบบแบ่งเวลา
- ในหนึ่งเทิร์นจะรัน 10 คำสั่ง
- stack pointer ของผู้เล่นแต่ละคนเริ่มจากตำแหน่งต่างกัน
- ไม่มี virtual memory
ขั้นตอนการบิลด์และสร้างบอร์ด
- โค้ดถูกคอมไพล์ด้วย
riscv64-unknown-elf-gccให้เป็นเป้าหมาย RV32- ตัวเลือกหลักรวมถึง
-march=rv32g,-mabi=ilp32,-ffreestanding,-nostdlib,-nostartfiles,-O0เป็นต้น - ด้วย
-O0ทำให้ machine code ยืดยาว แต่เป็นรูปแบบที่ตามได้ง่าย
- ตัวเลือกหลักรวมถึง
- สื่อสำหรับบอร์ดสร้างจากการ parse เอาต์พุตของ
riscv64-unknown-elf-objdump -S -l -fd game- แก้ไขคำสั่ง
▲และ✎ - แปลง jump offset จากเลขฐาน 16 เป็นเลขฐาน 10
- จัดระเบียบแอสเซมบลีและจับคู่กับซอร์สโค้ด
- สร้าง SVG แล้วแปลงเป็น PDF ด้วย Inkscape
- แก้ไขคำสั่ง
การพิมพ์และอุปกรณ์ที่ต้องเตรียม
- บอร์ดใช้โดยพิมพ์ PDF ที่แบ่งเป็นฝั่งซ้ายและฝั่งขวา
- แนะนำให้พิมพ์บน A3 ส่วน A4 ก็ใช้ได้แต่จะเล็ก
- อุปกรณ์ที่ต้องเตรียมคือหมากสำหรับคำสั่ง
nop1 ตัว, หมากสำหรับ trap address 1 ตัว, หมากสำหรับ program counter และ stack pointer อย่างละ 2 ตัวต่อผู้เล่น, ดินสอและยางลบ - เวอร์ชันเว็บรองรับทั้งการเล่นคนเดียวและเล่นกับเพื่อน และยังมีตัวช่วยเกมสำหรับ ESP32 และมือถือด้วย
กติกาพื้นฐานและการเดินเทิร์น
- สถานะเริ่มต้นมีดังนี้
- รีจิสเตอร์ทั้งหมดเริ่มที่ 0 แต่ return address register
raเริ่มที่ 1000 spของ Player 1 ถูกตั้งต้นเป็น 2244 และspของ Player 2 เป็น 3844pcของผู้เล่นทั้งสองเริ่มที่ 1000 ซึ่งเป็น address เริ่มต้นของฟังก์ชันmain- หมาก trap วางไว้ที่ address 1000
- address หน่วยความจำทั้งหมดเป็น 0 ยกเว้นโปรแกรมที่โหลดไว้ล่วงหน้า
- หมากคำสั่ง
nopยังไม่วางบนบอร์ดในตอนแรก
- รีจิสเตอร์ทั้งหมดเริ่มที่ 0 แต่ return address register
- ในหนึ่งเทิร์นต้องรัน 10 คำสั่ง และต้องตามการกระโดดอย่าง
jal,beqไปตามนั้น - ผู้เล่นสามารถหยุดเทิร์นหลังจากรันอย่างน้อย 1 คำสั่ง แล้วส่งต่อจำนวนคำสั่งที่เหลือไปยังเทิร์นถัดไปได้
- จำนวนคำสั่งที่สะสมได้สูงสุดคือ 20 คำสั่ง
Monkeypatch และเงื่อนไขชนะ
- ตอนเริ่มแต่ละเทิร์น หลังจากรันคำสั่งพอดี 1 คำสั่งแล้ว สามารถย้ายหมากคำสั่ง
nopไปยัง address ใดก็ได้ในฟังก์ชันที่ผู้เล่นปัจจุบันไม่ได้กำลังรันอยู่ - เมื่อ
pcไปถึง address นั้น คำสั่งดังกล่าวจะทำงานเป็น no-operation - หากย้ายหมาก
nopจะเสียเทิร์นปัจจุบันและเทิร์นถัดไป และคู่แข่งจะรันได้สูงสุด 20 คำสั่งในเทิร์นถัดไป - กติกา monkeypatch ยังไม่สมดุล จึงมีการเปลี่ยนแปลงเล็กน้อยทุกไม่กี่วัน
- ใน hard mode เกมจะจบเมื่อแฮ็กคู่แข่งให้เรียกฟังก์ชัน
game_over()ได้ - หากไม่มีฝ่ายใดส่งคู่แข่งไปยัง
game_over()ได้อีก จะเสมอกัน - ใน easy mode ผู้เล่นคนแรกที่รัน
retในmainเพื่อออกจาก main loop จะเป็นผู้ชนะ
สัญลักษณ์พิเศษและการจัดการข้อยกเว้น
✎ทำให้เลือกเลข 12 บิตใดก็ได้ตั้งแต่ 0 ถึง 4095 เป็นค่า immediate ของคำสั่งli▲ทำให้เลือกค่าภายในช่วง ±128 ไบต์จาก stack pointer ของตนเองในคำสั่ง load ได้- ตัวอย่างเช่น ถ้า
spเป็น 2180 จะเลือกได้ตั้งแต่ 2052 ถึง 2308
- ตัวอย่างเช่น ถ้า
- การกระทำต้องห้ามจะทำให้โปรแกรม crash
- เขียนทับ memory address ที่ต่ำกว่า 1192
- อ่านหรือเขียนแบบไม่จัดแนวไปยัง address ที่ไม่ใช่พหุคูณของ 4
- รันคำสั่งผิดกฎหมาย
- หากเกิด crash จะรัน exception handler และกระโดดไปยัง trap address
- trap address เริ่มต้นคือ 1000 แต่สามารถเขียนทับได้ในฟังก์ชัน
set_trap() - เมื่อเกิด exception program counter จะถูกตั้งเป็นค่าหนึ่งแล้วรันต่อ
- trap address เริ่มต้นคือ 1000 แต่สามารถเขียนทับได้ในฟังก์ชัน
- หากตรวจพบการโกงหรือความผิดพลาด สถานะโปรแกรม, หน่วยความจำ และรีจิสเตอร์ของผู้เล่นคนนั้นจะถูกรีเซ็ต
กติกาขยายสำหรับ 3–4 คน
spของ Player 3 ถูกตั้งเป็น 2116spของ Player 4 ถูกตั้งเป็น 3716- เมื่อมีผู้เล่น 3 คนขึ้นไป สัญลักษณ์
▲จะใช้ได้เฉพาะช่วงที่ห่างจาก stack pointer ไป -128 ไบต์เท่านั้น - หากเล่นด้วยจำนวนผู้เล่นมากกว่า 2 คน เกมจะค่อนข้างไม่เสถียรและเสียหายอย่างรวดเร็ว
- การไปถึงเงื่อนไขชนะจะยากขึ้น แต่การเล่นจะสนุกและวุ่นวายกว่าเดิม
ตัวอย่างกลยุทธ์การแฮ็ก
- สามารถใช้ crash เป็น กลยุทธ์โจมตี เพื่อหยุดความคืบหน้าของคู่แข่งได้
- หากเปลี่ยน trap handler เป็นฟังก์ชัน
game_overผู้เล่นคนแรกที่ crash จะแพ้- ในสถานะนี้ หมาก
nopจะทรงพลังมาก - หากคู่แข่งวาง
nopบนretของฟังก์ชันที่กำลังรันอยู่ ผู้เล่นอาจแพ้ได้
- ในสถานะนี้ หมาก
- หาก overflow ค่า index เป็น 400 หรือ -400 ในฟังก์ชัน
bug()จะเข้าถึง stack ของคู่แข่งและเขียนทับ return address ได้- ตัวอย่างเช่น หากต้องการย้ายจาก address 3784 ไป 2184 จะได้
(3784 - 2184) / 4 = 400ดังนั้นต้องใช้ index-400
- ตัวอย่างเช่น หากต้องการย้ายจาก address 3784 ไป 2184 จะได้
- สามารถใช้ฟังก์ชัน
copy()เพื่อคัดลอกคำสั่งบางคำสั่งไปสร้าง shellcode สั้น ๆ ในหน่วยความจำได้- ตัวอย่าง shellcode ใช้ชุด
li a4, ✎,li a5, ✎,sw a4, 0(a5),retเพื่อเขียนค่าใดก็ได้ - หากคัดลอกคำสั่ง
retreturn address จะถูกตั้งเป็นจุดเริ่มต้นของ shellcode ทำให้เกิดลูปไม่รู้จบ
- ตัวอย่าง shellcode ใช้ชุด
- หากตั้ง index เป็น 6 ในฟังก์ชัน
bug()จะเขียนตัวแปรvalueทับ return address ที่บันทึกไว้บน stack คือ28(sp)ได้- เมื่อ return จาก
bug()ค่า28(sp)จะถูกคัดลอกไปยัง return address register - หากใส่ address ของ shellcode ที่สร้างไว้ในค่านี้ ก็สามารถกระโดดไปยังหน่วยความจำได้
- เมื่อ return จาก
การตีความคำสั่งและการเปลี่ยนแปลง
- jump ทั้งหมดเป็น relative jump ตาม program counter ปัจจุบัน แม้จะดูเหมือน absolute address ใน disassembler
- ตัวอย่างเช่น machine code 1903 ของ
jal a4, 0เมื่อรันจะกลายเป็น ลูปไม่รู้จบ
- ตัวอย่างเช่น machine code 1903 ของ
- รายการคำสั่งที่ใช้ได้ในเกมถูกรวบรวมจากคำสั่ง RV32 JRI ที่มี machine code ตั้งแต่ 0 ถึง 4095 และใช้
a0,a4,a5,sp,raเป็นต้น - changelog 0.0.6 รวมการเปลี่ยนจาก
while(run)เป็นwhile(*prun)- ทำให้คู่แข่งสามารถบังคับให้เกิด crash ได้ด้วยการชักนำให้ dereference แบบไม่จัดแนว
- กติกา NOP เปลี่ยนเป็นวางได้เฉพาะในฟังก์ชันที่ไม่ได้กำลังรันอยู่เท่านั้น
การออกแบบและสื่อการเรียนรู้
- สี่เหลี่ยมทางซ้ายและขวาของบอร์ดเป็นข้อความไบนารีที่ encode เป็น ASCII
- สี่เหลี่ยมสีขาวคือ 1 และสี่เหลี่ยมสีดำคือ 0
- สีที่ใช้มีเพียงแดง, น้ำเงิน, ดำ และขาว เพื่อให้อ่านง่ายเมื่อพิมพ์ราคาถูกและด้วยเครื่องพิมพ์ขาวดำ
- ไม่ใช้ syntax highlighting
- เป็นการเลือกเพื่อหลีกเลี่ยงผลที่ทำให้บางส่วนของโค้ดดูสำคัญกว่าเพราะธีม และเพื่อให้ผู้เล่นตัดสินและโฟกัสเอง
- สื่อเรียนภาษาแอสเซมบลี RISC-V มีเช่น riscv-programming.org, cs3410 risc-v interpreter, rvcodecjs ของ luplab เป็นต้น
- สำหรับสื่อเรียน C ใช้ส่วนต้นของ Beej's Guide to C Programming
- มี PDF แบบฝึกหัดแอสเซมบลีสำหรับพิมพ์ที่ครอบคลุมตัวแปร, การเรียกฟังก์ชัน, pointer, string, struct, array, recursion ฯลฯ และเวอร์ชัน “assembly hangman” แบบเติมคำในช่องว่าง
1 ความคิดเห็น
ความคิดเห็นใน Hacker News
น่าประทับใจมาก โดยเฉพาะตรงที่ทำให้ลูกสาววัย 12 ขวบมาเล่นด้วยกันได้นี่แหละที่ดูสุดยอดที่สุด
แล้วเวอร์ชัน CHERI จะคาดหวังได้เมื่อไหร่? :-D
Core War เป็นเกมที่เล่นกันในสนามประลองหน่วยความจำของเครื่องเสมือนที่รองรับภาษาแอสเซมบลีจำลองแบบง่าย ๆ ฉันเห็นมันครั้งแรกใน Scientific American ปี 1984 และตอนนั้นฉันเขียนโปรแกรมมาแล้วราว 15 ปี เลยดูออกว่ามันได้แรงบันดาลใจจากเกมที่เก่ากว่าของ Bell Labs ชื่อ Darwin
Darwin ถูกสร้างขึ้นในปี 1961 และรันบน IBM 7090 โปรแกรมจะต่อสู้แย่งทรัพยากรกัน และโปรแกรมที่ชนะคือโปรแกรมที่สามารถคัดลอกตัวเองเข้าครอบครองพื้นที่ที่ได้รับทั้งหมดได้ Robert Morris Sr. เคยสร้างโปรแกรมที่เอาชนะไม่ได้ขึ้นมา แต่ก็อยู่ได้ไม่นาน ดู [2]
ช่วงกลางทศวรรษ 1970 นิตยสาร Software Practice and Experience เป็นหนึ่งในวารสารวิทยาการคอมพิวเตอร์ที่ฉันชอบที่สุด และมีคอลัมน์ Computer Recreations ที่เขียนภายใต้นามแฝง Aleph-Null ลงอยู่บ่อย ๆ ตอนเรียนบัณฑิตศึกษา ฉันสนุกกับการลองสร้างเกมหลายเกมจากคอลัมน์นั้นขึ้นมาเอง วารสารนี้ราคาแพง แต่ถ้าเป็นนักศึกษา ก็น่าจะพอหาอ่านได้ในห้องสมุดมหาวิทยาลัยเหมือนที่ฉันเคยทำ ฉบับในยุค 1970 มีหัวข้ออย่าง Pascal compiler, Algol 68, การเขียนโปรแกรมพร้อมกัน ซึ่งอ่านง่ายและสนุก และจากบทความของ N. Wirth ฉันก็ได้รู้จัก Module[3,4] และต่อมาคือ 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...
ฉันมีเพื่อนคนหนึ่งที่บอกว่าชอบเกมแต่ไม่มีหัวด้านการเขียนโค้ด แต่พอเล่น Human Resource Machine ก็กลายเป็นว่ากำลังเขียนโค้ดอยู่โดยพฤตินัย และบางวิธีแก้ของเขาก็ดีกว่าของฉันที่มีประสบการณ์มาหลายปีเสียอีก
ลูกวัย 12 ของฉันเกลียดคณิตศาสตร์ แต่เล่น Human Resource Machine กับ SpaceChem ได้ดีอย่างน่าทึ่ง เลยสงสัยว่าคณิตศาสตร์ในโรงเรียนมัธยมกับคณิตศาสตร์ในงานเขียนโปรแกรมนั้นต่างกันโดยพื้นฐานหรือเปล่า
น่าสนใจมาก เมื่อคิดถึงขนาดหน่วยความจำของคอมพิวเตอร์ทุกวันนี้ ฉันรู้สึกมาตลอดว่าmnemonic แบบสั้นเป็นทางเลือกที่ไม่ดีในเชิงวิศวกรรม
ตรงนี้เอง สิ่งแรกที่ต้องทำก็คือเรียนรู้และจำให้ได้ว่าคำสั่งแต่ละตัวทำอะไร ถ้าเปลี่ยนชื่อให้เขียนออกมายาวกว่านี้ ก็จะเรียนง่าย จำง่าย และอ่านโค้ดง่ายขึ้นมาก ฉันเลยแปลกใจที่คนไม่ได้ทำกันบ่อยกว่านี้
ผมยังมองว่าความจริงที่ว่าช่องโหว่แบบนี้เกิดขึ้นได้ ก็บ่งชี้ถึงความล้มเหลวในการออกแบบระบบโดยรวม ไม่ได้แปลว่ามันไม่ใช่เกมที่สนุกหรือไม่ใช่วิธีเรียนรู้ที่ดีนะ แต่ในงานวิศวกรรม เรากลับยอมรับปัญหาเชิงโครงสร้างกันง่ายเกินไป คนส่วนใหญ่ถึงขั้นมองไม่เห็นข้อบกพร่องเชิงโครงสร้างนั้นด้วยซ้ำ
ฉันคิดว่าเด็ก ๆ ตอบสนองได้ดีมากเมื่อเราไม่ดูถูกพวกเขา อย่างน้อยลูกของฉันก็เป็นแบบนั้น
มีคนที่ไม่มองว่าการอ่านและเขียนได้ตามอำเภอใจเป็นข้อบกพร่องเชิงโครงสร้างด้วยเหรอ? มีคนนับพันกำลังจัดการปัญหานั้นอยู่และก็มีความคืบหน้าพอสมควร ขณะเดียวกัน ฉันก็ยังคิดว่า peek กับ poke สนุกอยู่ดี
อันนี้เจ๋งมาก อยากลองเอาไปเล่นที่บริษัท
ดูน่าสนุกทีเดียว คิดว่าเหมาะกับช่วงอายุไหน?
bug()ฉันคิดว่าเด็กอายุ 10–15 ก็ทำได้ลูกสาวฉันอายุ 12 และเราก็เล่นด้วยกันอย่างสนุก เงื่อนไขชนะที่ยากกว่า คือทำให้อีกฝ่ายกระโดดไปที่ฟังก์ชัน
game_over()นั้นยากกว่า แต่ก็น่าจะไปถึงจุดนั้นได้ภายใน 5–6 เดือนส่วนผู้ใหญ่ฉันไม่แน่ใจ บางคนกลัวแอสเซมบลีราวกับเป็นสิ่งที่ปีศาจสร้างขึ้น เลยอาจทำให้พวกเขายอมเล่นยากกว่าเด็กเสียอีก
สิ่งที่น่าสนใจก็คือเรามักมองโลกเป็นภาพสะท้อนของตัวเอง
ถ้าฉันสนใจ buffer overflow และการเขียนโปรแกรม ฉันจะมองว่าลูกสาวของฉันต้องสนใจมากด้วยเป็นเรื่องแน่นอนสักแค่ไหน? ยิ่งเป็นลูกคนแรก และเป็นลูกสาวคนที่สองด้วยแล้ว ความน่าจะเป็นยิ่งดูต่ำ แต่ถึงอย่างนั้นก็ยังเห็นพ่อหลายคนผลักดันต่อไป
เวลาทำโปรเจกต์แบบนี้ ฉันสงสัยว่าคุณเคยตระหนักบ้างไหมว่าอย่างน้อยในระดับหนึ่งมันก็เป็นโปรเจกต์สนองอัตตาอยู่ดี ไม่ว่ายังไงฉันก็สนใจเรื่องแบบนี้อยู่แล้ว เลยดีใจที่คุณเอามาเผยแพร่
คุณกำลังสื่อว่าคนทำโปรเจกต์นี้ยัดเยียดมันให้ลูกสาวเพราะความทะนงตัวของตัวเอง แต่มีหลักฐานอะไร? ฉันลองดูอยู่หลายหน้าบนเว็บแล้ว ไม่เห็นมีอะไรชวนให้คิดแบบนั้นเลย ตรงกันข้ามกลับมีถ้อยคำอ่อนโยนหลายจุดที่บอกว่าลูกสาวกำลังสนุกและสนใจมันมาก
ทำไมถึงตัดความเป็นไปได้ที่ว่าลูกสาวอาจเริ่มจากการสงสัยอยู่เรื่อย ๆ ว่าพ่อทำอะไรกับคอมพิวเตอร์ออกไปล่ะ? มันอาจเริ่มจากเรื่องเล็ก ๆ แล้วค่อย ๆ เติบโตเป็นกระบวนการสองทางระหว่างคนที่มีความสนใจร่วมกันกับนักสำรวจตัวน้อยก็ได้
ความจริงเป็นอย่างไรฉันก็ไม่รู้ แต่คุณก็ไม่รู้เหมือนกัน จากประสบการณ์ที่ทำงานเกี่ยวกับการศึกษามาหลายปี เด็ก ๆ เรียนรู้เก่งกว่าที่คนทั่วไปเชื่อกันมาก โครงสร้างของโรงเรียนอาจเป็นส่วนหนึ่ง แต่ลึก ๆ แล้วอาจมีความเชื่อที่จำกัดแบบนี้อยู่ด้วย ฉันอยากปรบมือให้พ่อคนนี้ที่พยายามแบ่งปันความสนใจและความหลงใหลของตัวเองให้ลูกสาวและโลกได้รับรู้
บางอย่างก็คงมีคุณค่า บางอย่างก็อาจไม่มี โอกาสมันไม่เคยเข้าข้างอยู่แล้ว ชีวิตก็เป็นแบบนี้แหละ
ถ้า เส้นทางโค้ด RISC-V แบบ 64 บิตเสถียรและทำงานได้ดีพอจนแม้แต่ “buffer overflow” ก็หายไปแล้ว แล้วในสถานการณ์ที่ C/C++ ไม่คอยเปลี่ยนไวยากรณ์ให้ตลอด จะวางแผนการล้าสมัยไว้ล่วงหน้ากันยังไงล่ะ? น่าสงสารจริง ๆ…
เดี๋ยวก่อน
เกมกระดานแบบ tabletop ที่มีการเขียนแอสเซมบลีด้วยงั้นเหรอ? ทำไมฉันไม่เคยคิดแบบนี้มาก่อนนะ? :D
PL/I จัดการเรื่องอย่างการตรวจขอบเขตสตริง/อาร์เรย์ และสแตกที่เติบโตขึ้นแทนที่จะลงล่าง ได้อย่างถูกต้อง
https://www.acsac.org/2002/papers/classic-multics.pdf