ศึกษาและแฮก ptmalloc internal
เขียนขึ้นมาหลัก ๆ คือใช้เป็นโน๊ตส่วนตัว (ที่ยินดีให้คนอื่นอ่านด้วย) ดังนั้นจะไม่ปูพื้นฐานให้ assume ว่าผู้อ่านรู้จัก malloc อยู่แล้ว เขียนภาษา c เป็น และรู้จัก pointer เป็นอย่างดี ทั้งนี้สาย system นี่เปลี่ยนได้ตลอดเวลา หรือแตกต่างกันตาม arch, system ถ้าคิดว่าผมผิดชัดเจนแจ้งได้ทันทีจะขอบคุณมาก แต่ถ้าแค่ไม่ได้อัพเดทล่าสุด หรือบางระบบไม่เหมือนกัน ผมจะปล่อยๆไปนะครับ ถือว่าเป็นธรรมชาติของมัน บทความนี้จะใช้ glibc-2.31
ส่วนคนที่ไม่เคยเริ่มอ่าน heap เลยยยยย แนะนำว่าอย่าตื่นตระหนกมาก อันนี้เหมือนผมรวมทุกอันไว้ด้วยกันเลยยาวเกินไปหน่อย เริ่มจากแค่ tcache, fastbin ไปก่อน แล้วก็ใช้เวลาย่อยเป็นวันๆได้ เป็นเรื่องปกติ
** เหลือสรุป size table ขี้เกียจงะ -*- **
โดยสรุปคร่าวๆ ผมมองว่า ถ้าอยาก exploit heap overflow จริงๆเนี่ย ไปอ่าน write-up หรือ techniques ไปเลยตรงกว่า เพราะมันมีอะไรที่คิดไม่ถึง และไม่ได้ตรงมาจากการอ่าน src code เฉยๆ แต่ถ้าอยากเข้าใจเป๊ะๆว่าทำไมมันถึงต้องเป็น addr นั้นนี้ ทำไมต้องมีบรรทัดนี้ คิดว่าการอ่าน src code สำคัญมาก จะเห็นชัดเลยว่า ค่าไหนมันไปตรงกับ validation อะไรบ้าง วิธีที่เร็วคือหยิบ exploit มาแล้วโยนเข้า gdb ไล่ตาม src จะเร็วสุด รู้สึกว่าไม่แนะนำให้อ่าน src จากศูนย์เลย เสียเวลา (ผม fail เสียเวลาไปหลายสัปดาห์อยู่) ยกเว้นอยากเข้าใจ malloc จริงๆก็แล้วแต่ มีอะไรดีๆกระจายๆอยู่ในโค้ดเหมือนกัน
แนะนำ Reading Lists
ผมไปดูอ้างอิงหลายที่ พบว่ามี 4 อันที่ดีที่สุด ลองไปอ่านก่อนก็ได้ อาจจะเปลี่ยนใจไม่ต้องอ่านของผมมึนๆเลย
- https://sourceware.org/glibc/wiki/MallocInternals
- Source code ของ glibc malloc เอง — อันนี้ไม่ได้ประชด ในโค้ดมันมี comment ไว้เป็น document ยาวเปื้อยเลย บางครั้งการอ่าน doc ข้างนอกแล้วโครงสร้างมันเพี้ยนๆไม่เหมือนที่อ่านไว้นี่น่า อาจจะเกิดจาก platform constant ก็ได้ ซึ่งในโค้ดมีอธิบายไว้หมดแล้ว โชคดีที่มีคนเอาขึ้น online ให้ด้วย https://elixir.bootlin.com/glibc/latest/source/malloc/malloc.c
- อันนี้ผมว่าอ่านดีกว่าของผมเยอะเลย ผมแค่เป็นพวกอยากรู้ทุกเรื่อง ถ้าไม่ได้คำตอบมันจะโยงไม่ถูก ก็เลยต้องลงไปดูเอง แต่ผู้อ่านอาจจะอ่านอันนี้พอ https://azeria-labs.com/heap-exploitation-part-2-glibc-heap-free-bins/
- https://github.com/shellphish/how2heap รวม exploit น่าสนใจ
ภาพรวมของ malloc
malloc เป็น glibc function สำหรับให้ user allocate memory ที่ต้องการ โดย memory ที่ได้จะอยู่ในส่วน heap มีลักษณะเป็น dynamic ไม่ได้ขึ้นกับ stack
ตัว glibc malloc ถึงแม้เราจะเรียกสั้นๆแบบนั้น จริงๆแล้วมีตัวพื้นฐานมาจาก ptmalloc (pthread malloc) ที่บอกว่าเป็นพื้นฐาน เพราะไม่ได้หยิบมาใช้ตรงๆ แต่มีปรับแก้บ้างก่อนรวมเข้าใน glibc และ ptmalloc ก็มีพื้นฐานมาจาก dlmalloc (Doug Lea malloc) อีกที จะบอกว่าอยู่ในตระกูลเดียวกัน หรือใช้ชื่อสลับกันไปมาก็ไม่ผิดนัก
บางคนอาจจะเอะใจ จะเห็นว่า malloc อยู่ใน glibc เท่านั้น ไม่ได้เป็น kernel system call ของ operating system แปลได้ว่า
- จริงๆแล้ว operating system มี system call อื่น ที่มีหน้าที่เพิ่ม memory ให้ program ของเรา มันคือ brk, sbrk และ mmap
- malloc ทำงานใน user space คอยเรียกข้อ 1 อีกที — เราสามารถเข้าไปศึกษา internal ของ malloc ได้โดยไม่จำเป็นต้องมีสิทธิ kernel หรือ root เลย และแน่นอนว่าการเกิด heap overflow สามารถเข้าไปทับการทำงานของ malloc จนเพี้ยนได้เช่นกัน
- เราอาจจะแทน lib malloc ด้วย lib อื่นๆได้ เช่น jemalloc, tcmalloc ซึ่งเป็น memory allocation ที่พัฒนาต่อยอดจาก malloc อีกที ผมจะไม่ลงรายละเอียดสองตัวนี้ แต่แนะนำว่าน่าเอาไปลอง (ผมก็ไม่เคยลองนะ)
ทำไมถึงต้องมี malloc ผมเองก็ไม่แน่ใจความเป็นมาจริงๆของมันนะ แต่ถ้ามาดูที่ system call ที่ OS provide ให้เรา เช่น การทำงานของ sbrk กันก่อน มันจะสมเหตุสมผลมากเลยว่าทำไมต้องมี malloc มาครอบอีกที ref[]
sbrk มันคือการบอก OS ว่าขอ memory เพิ่มจากเดิมเท่าไร ถ้าใส่จำนวนลบก็คือ คืนให้ OS เท่าไร ตรงไปตรงมา แต่สาเหตุที่เราใช้ sbrk ตรงๆเลยไม่ได้ เพราะการขอใช้/คืน memory กับ OS จะต้องเป็นแบบ contiguous คือ ติดกันเป็นก้อนๆใหญ่ๆต่อเนื่อง ไม่ใช่ fragments ปัญหาจะเกิดขึ้นทันทีเลยตามรูปข้างล่าง ถ้าเราอยากคืน varA เราจะไม่สามารถทำได้เลย
อาจจะมีบางระบบที่สามารถย้าย pointer varB ลงมาแทน varA แล้ว sbrk(neg_value) ได้ แต่ระบบส่วนใหญ่ไม่สามารถทำแบบนั้นได้ เพราะ ptr address ถูก assign ออกมาไปแล้ว จะมาย้ายไปย้ายมาได้ยังไง มันเลยต้องมีระบบอะไรสักอย่างที่คอย track พวกนี้ แล้ว reuse memory ได้ โดยไม่ต้องหยิบคืนหยิบคืน OS บ่อยๆ นั่นก็คือ malloc นั่นเอง ส่วนจะใช้ mmap แทนได้ไหม มันใช้ได้ แต่มีเงื่อนไขว่าต้อง allocate เป็น page (4k, etc) เท่านั้น แปลว่าก็จะเหลือ fragment ที่ต้องจัดการ (และจะถูกจัดการด้วย malloc อยู่ดี)
แล้ว malloc มันจะจัดการเก็บข้อมูลพวกนี้ยังไงล่ะ ว่าตัวไหน free ไปแล้ว ตัวไหนใช้อยู่ มีขนาดเท่าไร fragment ยังไง malloc มันเลยจะต้องมี structure idea 2 อันคร่าวๆ คือ
- metadata/boundary/header ที่เอาไว้เก็บข้อมูล memory แต่ละก้อนว่า size เท่าไร กำลัง used อยู่หรือ free อะไรยังไง อาจจะเก็บแนบติดกับ memory ก้อนนั้นๆเลย หรือเก็บแยกก็แล้วแต่
- bins ตัวเก็บ ptr ว่ามี memory ก้อนไหนที่ free อยู่ เพื่อจะสามารถหยิบไป reuse ได้ ซึ่ง data structure มักจะเป็น linked list แต่ก็มีเก็บเป็น rb-tree ได้เหมือนกันแล้วแต่ implementation
เมื่อมี 2 ตัวนี้ เราก็จะสามารถ track ได้ว่า ช่องไหนมีขนาดเท่าไร ช่องไหน free ไปแล้ว ช่องไหนหยิบมาใช้ใหม่ได้ ถ้ายังมีช่องเหลืออยู่ก็ไม่ต้อง sbrk/mmap จาก OS เพิ่ม แต่สามารถหยิบจาก bin มาใช้ต่อได้เลย
แต่มันไม่ใช่แค่ว่าใช้งานได้แล้วจบ เราจะมีความต้องการอื่นๆจากระบบนี้ด้วย เช่น (หยิบมาบางส่วน ผู้อ่านอ่านตัวเต็มได้จาก ref[])
- Maximizing Compatibility and Portability ควรมีความ compat กับหลากหลายระบบ ยึดมาตรฐานตาม ANSI/POSIX และสามารถใช้งานกับ system ที่หลากหลายได้ เช่น มี alignment ต่างกัน, มี system calls ที่จำกัด เป็นต้น
- Minimizing Space การจัดการ memory ให้เกิด fragmentation น้อยที่สุด อันนี้ผมเพิ่มว่าควร minimize overhead ของการใช้งานเข้าไปด้วย (เช่น metadata size vs memory usable size)
- Minimizing Time คำสั่ง malloc, calloc, realloc, free ทำงานได้เร็ว
- Maximizing Locality การ allocate memory โดยคำนึงว่า minimize page load และ cache misses ให้ได้มากที่สุด
- อื่นๆที่ ref ไม่ได้ระบุ เช่น รองรับและใช้งานได้ดีใน multi-thread program เป็นต้น อันนี้เพราะ ref ต้นทางเป็นปี 1996 มันแอบๆ outdated ล่ะ
เมื่อมีความต้องการมากขึ้น เฉพาะ linked list เก็บ memory free/used หยิบเข้าหยิบออกเฉยๆเลยไม่พออีกต่อไป malloc เลยต้องหยิบ structure และ algorithm ที่ซับซ้อนมากขึ้นมาใช้ด้วยเพื่อตอบโจทย์ข้างบน ดังนั้นจึงไม่ต้องแปลกใจที่ทำไม malloc ถึงต้องมีแยก bin, แยก arena, มี cache, header แปลกๆ, รวม chunk memory ด้วยกันเป็นอันใหญ่ได้ บลาๆๆ เป็นต้น
Terms
ก่อนจะลงรายละเอียด จะมีคำที่ใช้บ่อยๆอยู่ที่ต้องตกลงกันให้เข้าใจก่อน จะคล้ายๆ glibc wiki ref[] นี้
Program heap หลายคนเรียกสั้นๆว่า heap ซึ่งมันจะไปแย้งกับบาง document โดยเฉพาะใน ref แต่อยากให้เข้าใจว่า ถ้าพูดถึง heap นี้มันจะคือ memory ของ program ที่ dynamic allocated อยู่เหนือ BSS segment และอยู่ล่าง stack เป็นอันใหญ่สุด และประกอบไปด้วยหนึ่งหรือหลาย arena
Arena ให้มองว่ามันเหมือนสนามอันใหญ่ที่ algorithm malloc จะทำงานภายในอันนี้ สามารถมีได้หลายสนาม เพื่อให้ตอบรับกับโจทย์ multi-thread programming แต่ละสนามจะถือครอง memory แยกกัน และเมื่อใช้งานจะถูก lock เพื่อไม่ให้ thread อื่นมารบกวน
Heap ถ้าจาก wiki ที่อ้างมา มันจะหมายถึง ก้อน memory ต่อเนื่องกัน (contiguous region of memory) ที่สามารถแบ่งเป็น chunked เพื่อเอาไปใช้งานต่อได้ ถูก manage โดย 1 arena เท่านั้น (ไม่ข้าม arena เพื่อไม่ให้ข้าม thread)
Chunk คือ ก้อน memory ที่สามารถถูก allocated, free หรือรวมกับ chunk อื่นกลายเป็นก้อน chunk ที่ใหญ่ขึ้นได้ ทั้งนี้เมื่อพูดถึง chunk เราจะพูดถึง wrapper ของ block memory ที่ให้ application ใช้ นั่นแปลว่าถ้า app สั่ง malloc แล้วได้ address 0x3050–0x3060 ไปใช้ chunk จริงๆจะอยู่ประมาณ 0x3040–0x3060 (รวมพื้นที่ metadata เข้าไปด้วย)
Memory จะใช้เรียกเป็น generic term เท่านั้น ว่าหมายถึง portion of application’s address space เพื่อป้องกันการสับสน
Arena & HeapInfo
ขอเริ่มจากตัวใหญ่ก่อน อย่างที่อธิบายไปก่อนหน้า Arena มีลักษณะเป็น working area ที่ข้างในมีข้อมูล chunks ต่างๆเก็บเอาไว้ โดยหน้าที่ของ Arena คือ มีไว้แยกการทำงานของแต่ละ thread ไม่ให้แย่งกัน allocate memory เพราะใน multithread programming จะต้องมีการใช้ mutex lock & wait และหากชนกับ thread อื่นจะทำให้ performance เสีย แต่ถ้าแต่ละ thread ถือคนละ arena ก็ไม่มีการ lock ชนกันเลย
โปรแกรมเริ่มมา จะมี arena และ heap เริ่มต้นไว้เสมอ เรียกว่า main arena ส่วน arena อื่นๆจะถูกสร้างมาเมื่อมี thread อื่นเรียกใช้ memory allocation function แล้วเกิด collision ขึ้น ประมาณว่าถ้า lock ชนเมื่อไรก็สร้าง arena ใหม่เลย และมี capped ไว้ที่จำนวน cpu_cores*8 แทน
ขอหยิบรูปจาก ref มาแล้วอธิบายตามที่ผมเข้าใจ ถึงดูรูปนี้จะเหมือนว่า arena เล็กกว่า heap แต่ไม่ใช่นะ มันเริ่มแบบนี้
- arena เดิมเกิด lock ชน เลยพยายามสร้าง arena ใหม่เพื่อแก้ collision ด้วยการสั่ง mmap ได้ Heap#1 มาเป็นก้อน
- เก็บข้อมูล Heap#1 ใน heap_info จากนั้นสร้างข้อมูลเกี่ยวกับ arena (สมมติว่าชื่อ Arena A) ใน Heap#1
- ar_ptr ซึ่งเป็นข้อมูลของ heap_info ชี้มาว่า heap นี้เป็นของ Arena A
- set arena ของ Arena A ให้เรียบร้อย รวมถึง update ค่า top chunk (เอาไว้ track bordering end of avail memory และคืน memory ให้ OS เมื่อมีขนาดใหญ่มาก) จากนั้น append ข้อมูลตัวเองลงใน linked list (main_arena.next) เท่านี้ main_arena ก็จะสามารถ track arena ทั้งหมดได้
- เกิด Heap#1 ใช้หมดแล้ว แต่ไม่ได้ต้องการ arena ใหม่ ต้องการแค่ memory เพิ่ม ก็ทำการ mmap จาก OS เพิ่ม ได้ Heap#2 ส่วน heap_info->ar_ptr ของ Heap#2 ชี้ว่าเป็น heap ของ Arena A นะ เหตุการณ์จะคล้ายกับข้อ 1–4
- เกิดเหตุการณ์เดียวกันกับ Heap#3, etc. top chunk ตอนนี้ชี้ไปที่ค่าท้ายสุด คือ Heap#3 ค่า ar_ptr ของทั้ง Heap#1,2,3 สุดท้ายชี้ไปที่ Arena A ที่เดียวกัน
ดังนั้นคงไม่ต้องแปลกใจถ้าเปิด memory mapping ของโปรแกรมออกมาแล้วพบว่า heap ของโปรแกรมมันไม่ได้ติดกันเป็นพรืดเดียว แต่เป็นก้อนใหญ่ๆหลายๆก้อนแทน
ส่วนสำหรับ hacker เนื่องจาก heap_info และ arena (mstate) อยู่ address ต่ำกว่า chunk ทำให้ overflow ตรงๆไปทับไม่ได้นะครับ ต่อให้ทับได้ ผมคิดว่าไม่น่าทับเท่าไร มันอยู่ไกลเกินอะ ไปทับ chunk metadata เล่นกับ bin ใกล้ตัวกว่า
เราใช้ gdb เข้าถึง main_arena ได้จาก
>>> p &main_arena
$1 = (struct malloc_state *) 0x7ffff7fc4b60 <main_arena>
>>> p &main_arena->flags
$2 = (int *) 0x7ffff7fc4b64 <main_arena+4>
>>> p &main_arena->fastbinsY
$3 = (mfastbinptr (*)[10]) 0x7ffff7fc4b70 <main_arena+16>Chunk
Chunk จะเป็นก้อน memory ที่สามารถถูก assign ให้โปรแกรมเอาไปใช้งาน / free ได้ โดยจะรวมพื้นที่ส่วน metadata เข้าไปด้วย ก่อนจะพูดถึงโครงสร้าง chunk ขอลง constant บางค่าก่อน เพราะแต่ละ system ไม่เหมือนกัน และโครงสร้างส่วนใหญ่ขึ้นกับขนาดของ 2 ค่านี้ครับ
Supported pointer representation: 4 or 8 bytes
Supported size_t representation: 4 or 8 bytes
สำหรับ x64 มักจะได้ว่า ptr 8 bytes และ size_t 8 bytes และสำหรับ x32 คือ ptr 4 bytes และ size_t 4 bytes เพื่อความง่ายผมจะยึดอันนี้เป็นหลัก สำหรับระบบอื่นๆ ผู้อ่านลองลงไปดู source malloc ได้ เขียนไว้ละเอียดมาก
Alignment ปกติเวลา malloc จะไม่ได้ค่า arbitrary ใดๆก็ได้ แต่จะเป็นค่าที่ปัดให้อยู่ใน pattern หนึ่งๆ เรียกว่า alignment เพื่อให้ system ทำงานได้เร็ว โดยทั่วไปอยู่ที่ 16 bytes (หรือ 8 bytes (x32)) คือ ถ้า malloc(35) ระบบจะปัดให้เป็น 48 เพื่อให้ตรง alignment แต่เราก็ไม่ควรใช้เกิน 35 นะ กรณี alignment 16 แปลว่า address จะลงท้ายด้วย x00
Chunk metadata overhead มีค่า minimum อยู่ที่ 8 bytes (4 bytes (x32)) ถือว่าค่อนข้างสูงสำหรับ chunk ขนาดเล็ก
Minimum allocated size อยู่ที่ 32 bytes (x64) และ 16 bytes (x32) แปลว่าต่อให้ malloc(1) หรือแม้แต่ malloc(0) ก็จะได้ Minimum allocatable size มาอยู่ดี **อันนี้เป็น implementation defined**
Maximum allocated size อยู่ประมาณ 2⁶⁴ (หรือ 2³² (x32)) - 2pages แต่อาจจะน้อยกว่านั้นมากขึ้นกับระบบ เช่น ระบบใช้ sbrk และ signed size_t เป็นต้น แต่ผมไปลอง 2⁶² ตอน runtime ก็ไม่รอดนะ ดูเหมือนว่า malloc จะอนุญาต แต่พอ runtime ไม่สามารถหาเคสที่ตอบโจทย์ได้เลย ก็ return error กลับไป
Chunk structure
รูปนี้ถือเป็นรูปที่ดีงามมาก กราบ glib wiki มา ณ ที่นี้ด้วย แต่ถ้าเกิดมีอะไรเปลี่ยนแปลง ก็ดู ascii art จาก malloc src code ได้เหมือนกัน ส่วนโค้ดนี่ดูง่ายเกินไปมาก
อันที่จริงก็มีความแตกต่างระหว่างการอธิบาย chunk ของ document นอก กับ struct ของ internal malloc อยู่นิดหน่อย
ถ้าดู src code malloc จะเห็นว่า เขาบอกว่า chunk เริ่มที่ mchunk_prev_size และมีความประหลาดตรงที่ nextchunk เริ่มแล้ว แต่ข้อมูลยังเป็น application data ของ chunk ที่แล้วอยู่ ตัว glibc wiki เลยนิยาม chunk ใหม่ให้มันเริ่มที่ size แทน เพราะดูง่ายกว่า ผมจะเรียก ptr ชี้ struct แบบใน malloc source code ว่า mchunk, ถ้าผมพูดว่า chunk จะหมายถึงชี้ที่ size, และถ้าพูดว่า user_mem คือชี้ที่ user data addr
ส่วนเหตุผลที่ minimum allocated size อยู่ที่ 32 bytes นั้นดูง่ายมาก เพราะ mchunk_prev_size (8) + mchunk_size (8) + ptr fd (8) + ptr bk (8) = 32 bytes ถ้ามันเล็กกว่านี้จะเก็บไม่หมด ส่วน fd_nextsize กับ bk_nextsize ก็ใช้เฉพาะกับ large block เท่านั้น (ไม่งั้นไม่มีที่เก็บ)
ส่วนภายใน size of chunk มีการเก็บ flag เพิ่มอีก 3 ตัวคือ AMP โดยเก็บเป็น bit-wised Least Significant Bit (และเนื่องจาก size chunk มัน align ที่ 8/16 ค่า flag จึงไม่ทำให้ size เพี้ยน)
A (0x04) NON_MAIN_ARENA — chunk บน main arena จะเป็น 0 ส่วน allocated arena (mmap มา) เป็น 1
M (0x02) MMap’d chunk — chunk ถูก allocated ด้วย mmap ถ้า bit นี้ถูก set จะ ignore flag อื่น (เพราะไม่ได้ถูกล้อมด้วย chunk อื่นๆแบบปกติ)
P (0x01) Previous chunk is in use — chunk ที่แล้วยังมีการใช้งานอยู่ และ prev_size field จะ invalid (ก็พื้นที่ตรงนั้นยังถูกใช้อยู่นิหว่า) มีข้อยกเว้น เช่น fastbin ที่ยัง set เป็น 1 แม้จะ freed ไปแล้ว อันนี้จะไปพูดต่อตรง algorithm ส่วนยุบรวม (consolidate chunks) ถ้าสาย hack heap overflow น่าจะเน้นไปที่ตัวนี้
ส่วนอันนี้ผมส่วนตัวคิดว่าสำคัญมาก ก่อนจะพูดต่อ เพราะจะเห็นว่าตัวโค้ดเอง ไม่ได้มอง chunk เป็นก้อนอย่างที่ wiki ตีกรอบเอาไว้ ในโค้ดมันคือชี้ prev_size (จุด start mchuck_ptr) หรือ user_mem_ptr ไม่มีชี้ที่ chunk_size นะครับ
ต่อๆไปมันจะมีความซับซ้อนในเรื่องการคำนวณ size/address/ptr ต่างๆ จะต้องแยกระหว่าง chunk_size กับ user_mem_size, mchunk_ptr, user_mem_ptr ให้ดี
Unsorted Chunks เป็น chunk ที่เป็น remainder จากการ split chunk ถูกเก็บไว้ใน UnsortedBin ก่อนจะถูกนำไปใช้โดย malloc ต่อไป (และหลังจากนั้นจะเข้า bin ปกติ) โดย chunk กลุ่มนี้จะไม่ถูก set ค่า A flag
Top Chunk เป็น chunk ที่ถูกจัดการแยกพิเศษ อยู่ขอบสุดของ memory ที่สามารถใช้งานได้ (the one bordering the end of available memory) ไม่ได้ถูกเก็บใน bin ไหนเลย มีไว้สำหรับ track เพื่อ sysmalloc (ขอ mem เพิ่ม) และ trim (คืน mem)
Bins
สำหรับ malloc internal ผมว่าจุดที่ซับซ้อนและยากที่สุดคือ bins และ algorithm เนี่ยแหละ โคตรมึน เอา Bins ก่อน
ตัว struct ด้านซ้ายจริงๆมันคือ mstate/arena นั่นแหละเอามาขยาย (struct จริงๆมีย่อยเยอะกว่านั้นแต่ช่างมัน) Bins เป็นตัวที่เก็บ freed chunks เอาไว้สำหรับ manage เพื่อไป allocate, coalesce, หรือส่งคืน OS โดย bins มีหลายประเภทแบ่งตามขนาดของ chunks และ algorithm ที่ใช้จัดการมัน แต่ละ bins จะถูกเก็บเป็น array ลงใน arena ที่เห็น bins[] อันนั้นคือเก็บ bins เกือบทุกประเภทเอาไว้ใน array นั้นแหละ แล้วเวลาเรียกใช้ค่อยไล่ index เอา ยกเว้น fastbins ที่แยกออกพิเศษ
ส่วนรูปนี้ส่วนที่เป็น chain ด้านขวา จริงๆเป็นตัวอย่างของ fastbins[idx] และ bins[idx] เท่านั้น เพราะ bins จริงๆเป็น array เก็บแยก size อีกที
FastBin
#define MAX_FAST_SIZE (80 * SIZE_SZ / 4)
#define NFASTBINS (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)เอา constant ง่ายๆไปก่อน อย่างอันล่างนี้แปลว่าสำหรับ x64 fastbin จะรองรับ user memory size มากสุดที่ 160 bytes และมีจำนวน 10 bins (32,48,…,144,160,176) แต่ max size for fast bin นี้สามารถ tune/set ให้น้อยลงได้ผ่านคำสั่ง mallopt
Chunk ใน Fastbin จะถูกเก็บแยกตาม size ของ chunk อย่างชัดเจน เก็บเป็น single linked list นำไปใช้งานได้เร็วแบบ LIFO (หยิบตัวใกล้สุดมาใช้เลย เพราะทุกตัวใน bin มี size เท่ากันอยู่แล้ว) ปกติจะไม่ consolidate (merge) กับ adjacent chunk (ยกเว้นใหญ่มากจนรวมแล้ว trim ได้) อาจมีการย้าย chunk ไป bin อื่นๆได้
ถ้าลองไล่ลำดับจากรูป
- memory สีเขียว (chunk a) ถูก free’d ตัว memory 0x555555559000 จะถูกเก็บใน arena->fastbin ส่วน mchunk->fd จะชี้ไป null
- memory สีแดง (chunk b) ถูก free’d ตัว memory 0x555555559020 จะถูกเก็บใน arena->fastbin ส่วนค่า ptr ที่ชี้ mchunk สีเขียวตอนแรก (0x555555559000) ถูกย้ายไปเก็บใน mchunk->fd ของสีแดงแทน
- สีส้ม เหมือนเดิม แง่มๆๆๆ
- ถ้ามี malloc ต่อจากสีส้ม addr ของ chunk c (arena->fastbin) จะถูกหยิบไปใช้ จากนั้น mchunk->fd ของสีส้ม (ชี้ไปสีแดง) ถูกย้ายไปเก็บใน arena->fastbin แทน ลักษณะโดยรวมจะคล้ายเป็น stack
ส่วนวิธี exploit ก็วุ่นวายนิดหน่อย เพราะ malloc fastbin มี overflow mitigation อยู่ (ข้ามไปอ่าน tcache ที่ง่ายกว่าก่อนแล้วค่อยกลับมาตรงนี้ก็ได้) การทดลองหลังจากนี้เกือบทั้งหมด (ยกเว้น tcache) ผมไปปิด USE_TCACHE ออกและ compile glibc ใหม่เอง ไม่งั้นจะติด tcache ตลอดเวลาเลย
ต่างจาก tcache ที่เอา mem ptr คืนให้ตรงๆเลย แต่อันนี้มันเอา mem ptr ไปเช็คก่อนอีกทีว่า size ถูกต้องไหม แปลว่า ถ้าผมอยาก hack malloc ให้ fastbin return addr บน stack ผมจะต้อง overflow heap แบบไม่ให้ size เปลี่ยนก่อน (scanf, gets คงพอได้) จากนั้นหาวิธีที่ทำให้ mem value ที่อยู่บน stack นั้นมีลักษณะคล้าย mchunk และค่าของ size จะต้องถูกต้องด้วย ผมว่าวุ่นวายเกินไปอะ ต้องทำทั้ง control stack และ overflow heap
ตัวโปรแกรม ผมทำคล้ายๆ tcache เลย แต่ส่วน overflow เนี่ย เอาจริงๆคือ คิดไม่ออกเลยว่าถ้าไม่ซับซ้อนแบบ JS engine/interpreter เนี่ย จะ control อะไรได้ทั้ง stack/heap แถมต้องมีเงื่อนไขเพิ่มด้วยว่าไม่เรียก function ที่ internal call malloc ไม่งั้นอาจจะไปโดน chunks consolidation ได้ ซึ่งผมยังไม่อยากเอามารวม อยากแยกศึกษามากกว่า ก็เลยช่างมัน เว้นไว้ให้ manual gdb edit memory เอาเป็น poc เบาๆแทนพอละ
สังเกตว่ามีเงื่อนไขเพิ่มจาก tcache มาพอสมควรเลย กับ ptr ชี้คนละที่กับ tcache ถ้าชี้ผิดก็ mem เบี้ยวนะฮะ ที่ผมเห็น exploit จริง เขาไล่หาและเลือก GOT จุดที่ memory 0x21, 0x31 อะไรแบบนั้นพอดี (อะไรจะโชคดีขนาดนั้น) ถ้าท่าง่ายกว่านั้นผมคิดว่าให้มันคืน ptr heap มาซ้ำ ก็พอแล้ว แล้วค่อยไป exploit แนว use-after-free/double-free อะไรก็ว่าไป อาจจะมีท่าอื่นอีก เช่น overwrite chunk size ก่อน free’d หรือ bypass double-free detection (เดาจากที่ไล่ src)
Thread Local Cache (tcache)
ใกล้เคียงกับ bin มาก แต่ต่างกันตรงที่ bin นั้นถูกเก็บข้อมูลอยู่กับ arena ส่วน tcache เก็บข้อมูลติดกับ thread (ประกาศแบบ global ติดกับ thread) สำหรับ chunk ส่วนใหญ่จะมี ptr ชี้ไปชี้มาไปที่ mchunk แต่สำหรับ chunks ใน tcache จะชี้ไปที่ user mem แทน ลักษณะจะเก็บเป็น single linked list เหมือน fastbin เลย วิธี link ตอน malloc/free ก็เหมือนกัน การเลือกใช้งานก็เป็น LIFO เหมือนกัน โดย tcache จะถูกพิจารณาก่อนเป็นอันดับแรก ถ้าเต็ม/ไม่มี ค่อย fallback กลับไปที่ lock arena และจัดการกับ bin (คำนวณก่อน fastbin อีก แต่ผมใส่ไว้ข้างหลัง เพราะต้องอธิบาย algorithm fastbin ก่อนง่ะ)
ส่วนเหตุผลว่าทำไม chunk ptr อื่นๆถึงชี้ไปที่ mchunk แต่ tcache ชี้ไปที่ user mem อันนี้ส่วนตัวผมคิดว่าเพราะเป้าหมายคือการแยก thread cache ถ้าไปชี้ mchunk ซึ่ง address ตรงนั้นอาจจะถูกใช้งานโดย chunk อื่นอยู่ จะเป็นการ access ข้าม thread แล้วเสีย performance ได้ ถ้าใครรู้เหตุผลชัดๆหรือมี ref ก็บอกผมด้วย
ปล. ระบาย สงสัยตั้งนาน ทำไมไล่ memory แล้วมันชี้ address ไม่ตรง document ฟร่ะ แต่เหมือน fastbin ค่ดๆ… อ่อ ก็มันไม่ใช่ fastbin ไงล่ะ!! -_-
สำหรับ heap exploit เท่าที่ไล่ดู มี 2 จุดที่น่าสนใจ คือ
1. size — ถ้า overflow ไปทับ “ก่อน” free’d อาจจะทำให้ chunk นั้นไปอยู่ใน bin size ที่ผิดได้ อันนี้ก็เหมาะกับ off-by-one byte เหมือนกันแหะ
2. mchunk->fd ถ้าไปทับ “ตอน” free’d อยู่ อาจจะทำให้ malloc ครั้งหน้าคืน arbitrary address มาได้ด้วย
ส่วน tcache key ไปทับก็ไม่มีประโยชน์ ไม่ได้ใช้นอกจากเก็บเอาไว้เช็คป้องกัน double free’d (free ซ้ำข้าม thread)
tcache bin มีวิธีเก็บ idx กับ size ที่แตกต่างจาก bin อื่นๆ ซึ่งผมก็ไม่ทราบว่าทำไมเหมือนกัน แต่เวลาใช้งาน แปลง user_request_size ให้เป็น chunk_size ก่อนเพื่อให้มั่นใจว่าไปอยู่ bin เดียวกันแน่ๆ ส่วน idx ปล่อยด้านหลังมันจัดการเองก็ได้ครับ
/* Only used to pre-fill the tunables. */
# define tidx2usize(idx) (((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ)
/* When "x" is from chunksize(). */
# define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)
/* When "x" is a user-provided size. */
# define usize2tidx(x) csize2tidx (request2size (x))Tcache bins and sizes ตาม define เลย
# define TCACHE_MAX_BINS 64
# define MAX_TCACHE_SIZE tidx2usize (TCACHE_MAX_BINS-1)
# define TCACHE_FILL_COUNT 7tcache จะเก็บ user mem size เป็น 24, 40, 56, …, 1032 (32–8+16*(idx)) ถ้าอยากลองเล่น fastbin/smallbin (ที่มี tcache enabled อยู่ และ size ไม่เกิน tcache max size) จะต้อง fill tcache ไป 7 chunks ก่อน
ลักษณะของ tcache กับ fastbin มี algorithm ใกล้เคียงกันมาก ต่างกันตรงที่ ptr ชี้คนละจุด ถ้าตอนจะทำ overflow ต้องชี้จุดให้ถูก
Filling tcache นอกจากการ fill tcache ตอนสั่ง free’d แล้ว tcache ยังถูก fill ตอนสั่ง malloc อีกด้วย โดยถ้าตอน malloc แล้วมีการ fallback ไป lock arena (ปกติเวลาใช้ tcache จะไม่ต้อง lock arena) แล้วพบว่า tcache (ที่ตรงกับ req size) นั้นไม่เต็มหรือ empty อยู่ จะย้าย chunksใน fastbin หรือ smallbin (ที่ตรงกับ req size) เข้าไปใน tcache แทน แปลว่ามีความเป็นไปได้ที่ metadata ของ memory จะเปลี่ยนในขณะที่สั่ง malloc ด้วย
SmallBin
ทั้ง smallbin, largebin กับ unsortedbin ถูกเก็บรวมกันใน array mstate->bins ชุดเดียวกันหมดครับ แยกด้วย size และ idx เอา เพราะว่ามีโครงสร้างคล้ายกัน (มี ptr fd, bk) ทั้งนี้โครงสร้างจะแตกต่างจาก fastbin อยู่ ตามภาพเลย
ดังนั้นเวลาไล่ ptr ต่างๆใน bins นี้มันจะเบี้ยวๆไป 0x10 เป็นเรื่องปกติ ส่วน ptr จาก arena->bin จะไม่ใช่ chunk ที่เอาไปใช้ได้เลย (ต่างจาก fastbin) แต่จะต้องเป็น bin->fd หรือ bin->bk ก่อน ในโค้ดจะ macro เป็น first(b) และ last(b)
ส่วนขนาดและจำนวนของ smallbin อยู่ที่ 64 โดยห่างทีละ 16 ตั้งแต่ 32,48,…,1016 (less than 1024) ส่วน sz ที่เอามาคิดคือ chuck size นะครับ ไม่ใช่ user req size
#define NBINS 128
#define NSMALLBINS 64
#define SMALLBIN_WIDTH MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
#define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH) // ค่านี้คือ 1024 สำหรับ x64#define in_smallbin_range(sz) \
((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)#define smallbin_index(sz) \
((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
+ SMALLBIN_CORRECTION)
พอเป็น chucksize จะเห็นว่า smallbin_index จะไม่มี 0 กับ 1 แน่ๆ ตอนประกาศเลยลบ 2 ออกสำหรับ 0 ส่วน 1 ใช้เก็บเป็น unsorted แทน
bin[0] = N/A
bin[1] = Unsortedbin
bin[2]-bin[63] = Smallbin
bin[64]-bin[127] = Largebinความประหลาดคือ แต่ถ้า size อยู่ระหว่าง 32–176 ปกติถ้า free เฉยๆมันจะไปตก fastbin เหตุผลที่มี smallbin ส่วนนี้ไว้ เพราะมันใช้จริงๆในกรณี chuck ถูกย้าย fastbin->unsortedbin->smallbin ซึ่งผมจะพูดอีกทีใน unsortedbin
แต่ละ smallbin จะเก็บ chunk size เดียวกันทั้งหมด (เหมือน fastbin) แต่ต่างจาก fastbin ตรงที่ในขณะ free’d จะมีการเช็คว่า adjacent chunks เป็น small/large และ free’d อยู่เหมือนกันหรือปล่าว ถ้าใช่จะมีการ consolidate รวมเป็น chunk เดียวที่ใหญ่ขึ้น (ดังนั้นสำหรับ chunk ใน smallbin จะไม่มีการอยู่ติดกันเองแน่ๆ เพราะโดน merge รวมตลอด) และเป็นเหตุผลที่ต้องมี ptr fd และ bk เอาไว้สำหรับแก้ middle chunk กลาง bin
จังหวะ malloc นั้นง่ายมาก ไล่ตาม arena->bins ไปตาม last ได้ victim chunk สีส้มมา เช็คว่า victim->bk->fd กับ bin->bk ชี้ไปตัวเดียวกันไหม (ถ้าไม่ corrupted ควรเป็นตัวเดียวกัน) แล้ว return victim ให้ user ใช้ต่อ
โอเค เอาแค่ตอน malloc ก่อนและเฉพาะกรณี malloc size ตรงพอดี (ตอน free แม่งซับซ้อนกว่านี้อีก) แล้วเราจะ exploit ยังไงดีละ ท่าที่ผมจะโชว์เหมือนอันนี้เปะเลย https://heap-exploitation.dhavalkapil.com/attacks/house_of_lore แต่ผมจะเอามา breakdown เป็น step ให้ง่ายขึ้น (หรือปล่าวหว่า)
ก่อนอีก จะ list เงื่อนไขที่จำเป็นออกมาก่อน
- เรา overflow ไปทับ arena->bins->bk ไม่ได้ ดังนั้น malloc ครั้งแรก ยังไงก็ได้ valid chunk สีส้มมาแน่ๆ ถ้าดูจาก link ที่ผมแปะ จะเห็นว่าบรรทัดที่ 47 มี malloc ทิ้งไปครั้งนึง เราคาดหวังว่าจะได้ arbitrary addr chunk ตอน malloc ครั้งที่สอง
- มีเช็คทุกครั้งที่ malloc ว่า victim->bk->fd กับ bin->bk ชี้ไปตัวเดียวกันไหม แปลว่าเราต้องไปตามไปแก้ victim->bk->fd ต่อด้วย แต่โชคดีที่เรายังสามารถ fake victim->bk ได้ เราสามารถ fake chunk ขึ้นมาได้ทั้งก้อนเลย โดยไม่ต้องกังวลว่า real victim->bk มันอยู่ไหนหรือเขียนทับได้ไหม โชคร้ายคือถ้าเราอยากให้ malloc เป็น address บน stack เราจะต้อง control value บน stack ด้วย
Exploit ภาพรวมเป็นตามรูปนี้
- สีม่วงคือ chunk a
- สีเขียวคือ chunk b (ถ้าไล่ offset จะได้ว่า b = a+208+32)
- สีส้มคือ stack area ที่เราอยากให้ malloc return chunk มา
- สีแดงจะเป็น fake chunk area ที่เราสร้างขึ้น
ขั้นตอนการคิดเริ่มจาก
- ตามเส้นสีเหลือง — เรา free(b) เป็นอันสุดท้าย ดังนั้น last(arena->bin) จะชี้ไปที่ b แน่นอน และเรา overflow ไปทับค่านี้ไม่ได้แน่ๆ แต่เราโกง malloc ครั้งต่อไปได้ เราเลยให้ green->bk ชี้ไปที่ mchunk orange โดยมีเงื่อนไขว่า orange->fd ต้องชี้กลับมาที่ mchunk green
เราจะ malloc ได้ green มาและตอนนี้ last(arena->bin) จะชี้ไปที่ orange ละ
จึงเป็นที่มาของ stackExp: p64(a+240–0x10) - ตามเส้นสีเขียว — malloc ครั้งนี้เราอยากได้ orange chunk มา แต่เนื่องจากมีการเช็ค linked list bk->fd ด้วย เราเลยต้องสร้าง fake chunk สีแดงขึ้นมา ซึ่งจริงๆอยู่ตรงไหนก็ได้ (แต่เพื่อให้ feasible เลยยัดเข้าไปในกล่องม่วง)
b’A’*50 ก็ได้ ผมแค่อยากทิ้งที่ว่างเผื่อไว้ ส่วนที่เหลือก็ตรงไปตรงมาคือ
stackExp: p64(a+0x50–0x10) เพื่อเอา mchunk ของสีแดง
heapExp: p64(stack-0x10) เพื่อชี้กลับไป stack
จากนั้นก็ไปเขียนทับสีเขียวต่อ คำนวณ offset ให้ถูกและให้ bk ชี้ไป p64(stack-0x10) เป็น term สุดท้าย จบละ
ถ้าอยากรู้ว่า payload ส่วนไหนสำคัญยังไง ทำไมต้องมี ก็ลองเอาออกได้ครับ พอมันพังก็ไปดูว่าพังตรงไหน
Freeing ขั้นตอนการ free จะแตกต่างจาก fastbin และ tcache ตรงที่ จะมีการเช็ค adjacent chunks เสมอเพื่อทำการ consolidate free’d chunks รวมเป็น chunk เดียว และ **เอาไปเก็บใน unsorted bin** ไม่ได้เก็บใน small/large bin ทันที โดยแทรก chuck ใหม่ไปที่ bin->fd (แทรกตัวแรก)
Consolidation เริ่มจากเช็ค chunk หน้าก่อน ถ้ารวมได้ก็รวม แล้วก็เช็ค chunk หลัง ถ้ารวมได้ก็รวมอีก วิธีรวมก็แค่ไปปรับขนาด chunk size ให้เพิ่มขึ้น แล้ว unlink chunk เดิมออกจาก linked list เก่า (chunk กลางไม่ต้อง unlink เพราะเพิ่งสั่ง free ยังไม่ได้อยู่ใน bin ไหนเลย) unlink ก็จินตนาการว่าคือการหยิบ node ออกจาก linked list แค่นั้นแหละ แต่โค้ดมันยาวเปื้อยเลยเพราะว่าใส่ validation ดักไว้เต็มไปหมด
ส่วนถ้า chunk บนเป็น top chunk ก็เอาไปรวมกับ top เลย (และไม่ต้อง unlink เพราะ top chunk ไม่อยู่ใน bin) จากนั้นก็จบด้วยการเอา chunk ใหญ่ที่ consolidate ครบเสร็จแล้วไปยัดใส่ unsorted bin
มันมีไอเดียน่าสนใจตรงนี้อยู่ เพราะเวลาเราสั่ง free เราจะโยนแค่ addr B เข้าไปเท่านั้น แล้วข้างล่างมันรู้ได้ยังไงล่ะ ว่า chunk A กับ chunk C มันอยู่ตรงไหน ถูกใช้อยู่หรือปล่าว มันหาได้เพราะว่าเราเอาค่าต่างๆของ chunk B ไปคำนวณ offset อีกที แปลว่าถ้าเราจะแฮกตรงนี้เนี่ย มันไม่ได้ขึ้นกับบริบท chunk A หรือ C เลย เราสามารถ consolidate chunk ปลอมได้จากการ tune attribute ต่างๆของ chunk B
แต่ก็ไม่ได้แปลว่าเราตั้ง B แล้วจะชี้ arbitrary addr อะไรเป็น chunk A, chunk C ได้นะ เพราะตัว chunk A และ C ยังต้องมีโครงสร้างถูกต้องตาม mchunk อยู่ (chunksize, flag, fd, bk) เพื่อให้มันผ่านการคำนวณต่างๆได้ โดยเฉพาะ Chunk C (forward chunk) ที่มันจะเช็คเลยไปอีก chunk นึงด้วย (chunk C + chunksize of chunk C) ว่าตัวเองถูกใช้งานอยู่หรือปล่าว (in_use flag มันเช็คตัวเองไม่ได้ ต้องเช็คจาก chunk ถัดไปอีกที)
วิธี exploit ง่ายสุดคือ consolidate กับ backward chunk (chunksize ของ A กับ prev_chucksize ของ B ต้องตรงกัน) ส่วนตอน unlink นั้น bypass ง่ายสุดคือให้ทั้ง fd และ bk ชี้ที่ A ทั้งหมดนั่นแหละ
สั้นๆไม่มีอะไร มันคือการที่เราเขียน buffer a โดยให้ data ใน a เนี่ยมี structure คล้าย chunk และ 8 bytes สุดท้ายให้ prev_size ถูกต้อง (ถึงตรงนี้ยังไม่นับว่า overflow) แล้วค่อย overflow ไปทับ flag prev_in_use ของ b ให้มันชี้กลับมา consolidate กับ fake chunk ที่เราจัดเอาไว้ ที่เหลือก็บวกลบเลขให้ลงล็อกละ (พูดง่ายแต่ผมก็บวกผิดไปหลายครั้งนะ อ๊าก ต้องระวังเรื่อง mchunk_ptr VS user_ mem_ptr ดีๆ)
ถ้าถามว่าแล้วมีประโยชน์ตรงไหน ในเมื่อ POC ผมก็ overflow จาก A ไปทับ B อยู่แล้ว จะไปแสดงให้เห็นว่าเขียน A ทับ buffer ans ได้อีกทำไม คำตอบนึงที่ผมคิดได้คือ ถ้าสังเกตเห็นตอน overflow ตอนแรกมัน overflow จริงๆแค่ 1–8 bytes เองนะ (ทับ B->chunksize) แปลว่า technique นี้เอามาใช้กับ off-by-one byte ได้ดีเลยทีเดียว แล้วค่อย overflow หนักๆหลังได้ malloc อีกที
เงื่อนไขของอันนี้คือ ต้อง leak address ได้ระดับนึง ไม่งั้นเราจะสร้าง mchunk ptr bk/fd ไม่ถูก มันน่าจะมีท่าไม่ต้องรู้ addr เลยด้วยแหละ แต่เทคนิคพวกนั้นข้ามไปก่อน อันนี้เอาเฉพาะพื้นฐาน
ส่วนอันนี้ WTF กว่ามากเลยเหมือนจะทำ integer overflow ด้วยมั้ง เด้งไป stack ได้ซะงั้น -..- https://heap-exploitation.dhavalkapil.com/attacks/house_of_einherjar
Unlink เป็นขั้นตอนหนึ่งใน consolidation ที่ผมอธิบายไปแล้ว หลักการมันแค่การเอา chunk ออกจาก bin linked list แหละ ซึ่งตอนแรกผมอ่านโค้ดก็คิดว่าไม่มีอะไรให้ exploit มีแต่ validation ที่ต้อง bypass แต่ๆๆๆๆ แอดกรรณส่งท่าใหม่มาให้ มันสุดยอดมาก คืองี้ ใน unlink มันมีขั้นตอนการเขียนเพื่อสลับ ptr บางตัว ซึ่งขั้นตอนพวกนั้นแค่ 1–2 บรรทัดมันก็สามารถเอามา exploit ได้แล้ว
https://github.com/shellphish/how2heap/blob/master/glibc_2.31/unsafe_unlink.c
วิธี exploit หลักการคือ เราไม่จำเป็นต้องให้ fd และ bk ชี้ไปที่ mchunk เดียวกัน มันเลื่อมได้คือ fd ชี้ไปที่ (some_ptr-3) และ bk ชี้ไปที่ (some_ptr-2) เราก็จะ bypass check ได้แน่นอน และได้ผลลัพธ์คือ value bk->fd จะถูกเปลี่ยนค่าไปชี้ mchunk แปลว่าเราสามารถเลือก address ไหนก็ได้ใน memory space แล้วเปลี่ยน value ให้เป็น var_addr-(size_t*3) ได้
ทีนี้ ถ้า addr นั้นมันเป็น addr ของ variable จะกลายเป็นว่า ptr มันชี้ไปที่ var_addr-(size_t*3) หรือตำแหน่ง chuck[0] ต่อมา เราอยากแก้ให้ var_addr ไปชี้ที่ arbitrary addr อื่นๆ เราก็สามารถแก้ (void*)chuck[3] ได้ (ซึ่งเป็นตำแหน่งของ var_addr เอง) เราก็จะสามารถ access arbitrary addr ได้ด้วย chunk แล้ว
ไม่น่าเชื่อเลย เป็นวิธีที่ overflow แค่ 1 byte แต่สามารถทำให้เกิด arbitrary write ได้ ตัวนี้มันก็ไม่ได้เกี่ยวกับ consolidate อะไร ตัวต้นทางเขาเลยตั้งชื่อว่า unsafe unlink
UnsortedBin
มีความมึนพอๆกับ top chunk เลย เพราะมันกระจายอยู่ทุกแห่งหน ไม่ได้ตรงไปตรงมาว่าหยิบลง bin นี้ตอน free และหยิบออกตอน malloc แต่มันหยิบโยนไปมาระหว่าง bin อื่นได้
หยิบใส่ (แบบแทรกไปที่ตัวแรก bin->fd) เมื่อ
- free small chunk (และ consolidate แล้ว)
- free large chunk (และ consolidate แล้ว)
- malloc large request (มากกว่า smallbin) จะ consolidate fastbin ทั้งหมด (แม้ chunk นั้นจะไม่ได้ merge กับอะไรเลยก็ตาม) แล้วโยนลง unsorted
** ตอนผมทำ poc exploit ก่อนหน้า ก็มาโดนข้อนี้บ่อยมาก เพราะว่าด้านล่าง fgets เอย sprintf เลยมันมี malloc(1000) สักอย่าง chunk fastbin เลยโดนโยนลง unsorted bin หมดเลย** - malloc small/large chunk แล้วมีเศษเหลือ จะเอาเศษใส่ unsorted
มีกรณีหยิบออกเพียงกรณีเดียว คือ ตอน malloc ดังนี้
malloc แล้ว condition ไม่ตรงกับการใช้ tcache, fastbin, smallbin จะถึงเวลาไล่ unsorted bin ไปเรื่อยๆเริ่มจาก bck จนกว่าจะหมดหรือตก condition ให้ return victim ได้ (หยิบใส่แบบแทรกตัวแรก หยิบออกแบบเริ่มจากตัวหลัง เลยเป็น FIFO)
- ถ้าอยู่ใน range smallbin, เป็น chunk อันเดียวใน unsorted, และขนาดมากกว่าที่ req จะเอา chunk นี้มาหั่น เก็บเศษเหลือไว้ใน unsorted เหมือนเดิมแล้ว *return victim*
- ถ้า size เท่ากับที่ req และยังมี tcache ว่างอยู่ ให้เอา chunk ที่กำลังพิจารณามาเติม tcache size นั้นก่อน (LIFO) แล้วไล่ไป chunk ถัดไป (continue loop) ซึ่งอาจจะไปตก condition อื่นแทนก็ได้ ถ้าเต็มอยู่แล้วให้ *return victim*
- ถ้า size ยัดลง smallbin ได้ก็ยัดไปเลย โดยใส่ไปที่ bin->fd (ตัวแรก)
- ไม่งั้นจะยัดลง largebin แทน แต่มีการพยายาม maintain sorted order ด้วย (พูดอีกทีตอน largebin)
- (ปกติไม่น่าเข้าอันนี้) ถ้า config memory_tunable_tcache_unsorted_limit ไว้ (ซึ่งผมก็ไม่เห็นจะมี public API ให้ tune -..-) แล้วหยิบ unsorted ลง tcache เยอะจนเกินไปแล้ว (ต่างจากเงื่อนไขบนตรงที่ อันนี้ไม่ได้ดูที่ idx bin ของ tcache แต่นับรวม) ให้หยิบ tcache ไป return แล้วจบเลย
- ออก loop ถ้า process เกิน 10k รอบ หรือไม่เหลือ unsorted แล้ว
หลังจากออกลูป ก็หมดขั้นตอนของ unsorted แล้ว เหลือเป็นขั้นตอนอื่นๆแทนว่าจะหยิบจาก tcache, จะหยิบ largebin, smallbin มาใช้ยังไงต่อไปอีกที
ดูวุ่นวายมาก สำหรับ exploit ก็เลยไม่ค่อยมีใครอยากมาจับตัวนี้เท่าไรแหละ สำหรับผมคิดว่าสำคัญที่สุดคือ รู้สึกว่ามันจะไปลง unsorted เมื่อไรและจะเอาออกมาเมื่อไรต่างหาก ตอนใส่ผม list ให้แล้ว ตรงไปตรงมา ส่วนตอนเอาออก หลักๆมันคือ หยิบออกไป fill bin ให้มากที่สุด มีแค่บางกรณีที่จะหยุดก่อนซึ่งผม bold ไว้ให้แล้ว
มาดูว่าถ้าผมไล่ถูกต้อง มันจะต้องอธิบาย behavior ของ memory ได้ อันนี้ผมทดลองแบบไม่มี tcache นะครับ ถ้ามีจะวุ่นวายกว่านี้อีก เห้ออออ~ เริ่มจาก
- memory a,b,c,d ถูก free ไปอยู่ใน fastbin แบบ stack [first,a,b,c,d,end]
- พอรันไปถึง fgets ซึ่งด้านล่างมี malloc(1024) อยู่ ทำให้ fastbin ถูก consolidate (ซึ่งเคสนี้ทำไม่ได้ เพราะโดน chuck อื่นคั่นอยู่) แล้วก็ย้ายไป unsorted แทน โดยวิธีย้ายก็ค่อยๆ pop fastbin ออกมาทีละตัวแล้ว เอาตัวนั้นแทรก bin->fd ไปเรื่อยๆ จะได้ผลสุดท้ายคือ unsortedbin fd->a->b->c->d->bk
- แต่กระบวนการ malloc ของ fgets ยังไม่จบ หลังจาก consolidate fastbin แล้ว มันจะทำการย้าย unsorted ไป smallbin ด้วย โดยหยิบ unsorted->bk ไปแทรก smallbin->fd ทีละตัว ผลสุดท้ายเลยออกมาเรียงลำดับเหมือนเดิม smallbin fd->a->b->c->d->bk
จะเห็นว่า chuck a->bk นั้นเปลี่ยนไปแล้ว เพราะย้าย bin แล้วนั่นเอง ส่วน bin ที่ย้ายจะย้ายจาก bin[1] (unsorted) ไป bin[2] (smallbin ที่เล็กสุด สำหรับ 32 bytes) ตัว addr มันเลยห่างกัน = 0x7ffff7fc4bd0 - 0x7ffff7fc4bc0 = 0x10 (2*size_t) นั่นเอง - และเนื่องจากไปอยู่ใน smallbin แล้ว ตอนหยิบออก ก็หยิบจากตัวหลังสุด จะได้ว่า tmp กับ d มี addr เดียวกัน
ลองเพิ่มอีกหน่อยนึง กรณี malloc size==chunk ใน unsorted พอดี
เนื่องจาก size พอดีเป๊ะ malloc จะ return unsorted chuck เลย โดยไม่ยุ่งกับตัวอื่นต่อ จะเห็นว่า chuck b,c ก็ยังคงอยู่ใน unsorted เหมือนเดิม
แต่ถ้าผมแก้บรรทัดที่ 25 จาก 536 เป็น 520 (521–535 ได้ผลเหมือน 536 เพราะ align16 อะ) จะได้ผลแบบรูปข้างล่างเลย (ส่วนค่าใน chuck a ไม่ได้ใช้แล้ว เพราะ allocate แล้ว เหลือเป็นซากไว้เฉยๆ) กรณีที่ size ไม่เป๊ะ มันจะพยายามย้าย unsorted ลง bin อื่นให้หมด แล้วค่อยไปเลือก size ที่เหมาะอีกทีตอนทำ bin map
ผมว่ามีรายละเอียดเยอะมากเลยว่า unsorted จะจัดการยังไง ให้ predict เป๊ะๆเป็นอะไรที่วุ่นวายมาก สำหรับ exploit ผมคิดว่าควรหลีกเลี่ยง ถ้ามีเวลาจะสรุปรวมอีกทีว่า bin ไหนใส่หน้าใส่หลัง ออกหน้าออกหลัง size ต่ำสุดสูงสุดเท่าไรอีกที
กรณี size ไม่เป๊ะ และ binmap
ไอเดียภาพรวมไม่ยาก เรารู้ว่า size ที่เรา req คือเท่าไร เราอยากใช้ algorithm best-fit คืออยากได้ chunk ที่เล็กที่สุดที่สามารถเอามาใช้ได้ เราก็ไล่จาก bin+1 นั้นแล้วเพิ่ม bin++ ไปเรื่อยๆ แน่นอนว่า chunk ที่เราได้มา จะใหญ่กว่า req size แน่ๆ โดยมี 2 เคส
- remainder ≥ min_size เราก็ทำการแตกออกเป็น 2 chunks แล้ว return chunk หลักให้ dev ใช้ ส่วน chunk เศษเหลือโยนเข้า unsorted
- remainder < min_size คือช่างแม่ง แตกไม่ได้ก็โยนทั้งก้อนให้ dev นั่นแหละ
ความที่โค้ดมันยาว เพราะว่าต้องมีการจัดการ ptr ต่างๆในการ split chunk
ส่วน binmap เนี่ย อารมณ์แทนที่จะมาไล่เช็ค ptr ทีละ bin ให้มี map ที่เก็บ bit 0/1 สำหรับ bin ที่ ไม่มี chunk/มี chunk เราก็จะสามารถเช็ครวดเดียวหลายๆ bin พร้อมกันได้ (ใช้พวก bit operation) ฟังดูแล้วก็น่าสงสัยนะว่าเร็วขึ้นคุ้มเหรอ แต่เขาบอกว่าเร็วขึ้นจริงๆนะ ส่วน binmap ก็ถูก set ตอนย้ายจาก unsorted->small/large bin ด้วยคำสั่ง mark_bin และจะ set flag ออกก็ตอนที่เข้าไปดูใน bin นั้นแล้วพบว่า empty (ไม่ได้ set ออกตอน remove chunk นะ เพราะต้องเพิ่ม if เช็คเข้าไปมันงานเยอะมั้ง?)
ไม่ค่อยมี ptr operation เกี่ยวกับ binmap เท่าไร ไม่น่ามีอะไรให้ exploit
LargeBin
ไอเดียภาพรวมคล้ายๆ smallbin เลย แต่มี fd_nextsize และ bk_nextsize โผล่มาด้วย เหตุผลหลักคือ เพราะใน large bin ไม่ได้มี size เดียวเท่ากันหมด เลยต้องมี nextsize ptr สำหรับเลือก bin size ด้วย (เวลาหา size แทนที่จะต้องไล่ทุก chunk ก็สามารถข้าม chunk ที่ size เดียวกันได้)
รายละเอียดอื่นๆ คือ
- ภายใน bin เดียวกัน จะมี linked list 2 ชุด คือ fd, bk เหมือน smallbin ที่ทุก chunk จะ link กัน กับ fd_nextsize และ bk_nextsize สำหรับกระโดดไป size ถัดไปเลย สภาพมันจะไม่ใช่ nested linked list structure นะ แต่จะเป็น 2 linked list ที่ซ้อนกันอยู่ (ดูรูปข้างล่างได้)
- ภายใน bin เดียวกัน จะเก็บ size ใหญ่สุดไว้หน้าสุด (bin->fd) และ size เล็กสุดไว้หลังสุด (bin->bk)
อันนี้ต้องระวังนิดหนึง ถ้าดูจากโค้ด บางครั้งใช้ bck แต่จริงๆแล้วยังชี้ที่ bin อยู่
bck = bin_at (av, victim_index); // อันนี้ชี้ bin
fwd = bck->fd; // อันนี้ชี้ตัวแรกละส่วนถ้ากรณี chuck เล็กกว่าตัวสุดท้ายของ bin นั้น (แปลว่าไม่ต้องไล่ linked list แล้ว มันต้องไปอยู่ท้ายสุดแน่นอน) https://elixir.bootlin.com/glibc/glibc-2.31/source/malloc/malloc.c#L3840 โค้ดประมาณนี้
if ((unsigned long) (size) < (unsigned long) chunksize_nomask (bck->bk)) {
fwd = bck; // ย้าย fwd มาชี้ bin
bck = bck->bk; // ย้าย bck มาชี้ตัวสุดท้าย เตรียมรอแทรกระหว่างตัวสุดท้ายกับ bin
- ภายใน size เดียวกัน ถ้ามี chunk ใหม่มา จะเอาไปแทรกตัวที่ 2 ของ size นั้นๆเสมอ เพราะว่าตัวแรกมันโดน link ด้วย fd_nextsize, bk_nextsize อยู่ ถ้าไปแทนตัวแรกมันต้อง link ใหม่วุ่นวาย
ตอน malloc หาตัว best-fit (เล็กที่สุดที่เพียงพอกับ req)
- largebin เนี่ยใน bin ตัวเองมันไม่ได้ chunk size เท่ากันหมด มันต้องวนลูปเช็คภายใน bin ตัวเองก่อน ถ้าไม่เจอ ก็ค่อยไปเช็ค binmap อีกที
- ตอนเช็ค binmap ไม่ต้องวนลูป fd_nextsize อีกแล้ว เพราะ bin+++ จะมี size ใหญ่กว่าที่เรา req แน่นอน และหยิบตัวหลังสุด bin->bk จะได้ chunk ที่เล็กที่สุดที่เป็น best-fit ด้วย (เลย reuse โค้ดร่วมกับ smallbin ได้เลย)
ตอน free ก็เหมือน smallbin เลย
- consolidate with nearby chunks and is put in unsortedbin
- แล้วมันจะไปลง largebin ตอนไหนละ? ตอนจังหวะ process unsortedbin ตอนที่ถูกสั่ง malloc (with few conditions) เหมือน small chunk เป๊ะ
Ok TESTING TIME!!
7 int main() {
8 char* a1 = (char*)malloc(5000);
9 malloc(16);
10 char* a11 = (char*)malloc(5000);
11 malloc(16);
12 char* a12 = (char*)malloc(5000);
13 malloc(16);
14 char* a2 = (char*)malloc(4900);
15 malloc(16);
16 char* a21 = (char*)malloc(4900);
17 malloc(16);
18 char* a22 = (char*)malloc(4900);
19 malloc(16);
20 char* a3 = (char*)malloc(5010);
21 malloc(16);
22 char* b1 = (char*)malloc(10000);
23 malloc(16);
24 char* b2 = (char*)malloc(11000);
25 malloc(16);
26 char* b3 = (char*)malloc(9900);
27 malloc(16);
28 free(a1);
29 free(a2);
30 free(a3);
31 free(a11);
32 free(a12);
33 free(a21);
34 free(a22);
35 free(b1);
36 free(b2);
37 free(b3);
38 char* tmp = (char*)malloc(40000); // trigger unsorted
39 return 0;
40 }เวลาเราอยาก confirm ว่าเราเข้าใจถูกจริงไหม วิธีที่ดีที่สุดคือ ทดลองจริงครับ เอาโค้ดง่ายๆข้างบน จากนั้นเอากระดาษมาทดๆวาดๆเลยว่า เมื่อสั่งบรรทัดที่ 38 แล้ว largebin ควรจะออกมาเป็นแบบไหน จากนั้นก็เทียบกับรัน gdb แล้วไล่เช็ค memory เอาครับ
1. Step แรก แยก bin ก่อน เพราะถ้ามันอยู่คนละ bin มันก็คืออยู่คนละ bin ไม่มี linked list ชี้ถึงกัน ไม่วุ่นวาย ดังนั้นผมจะตัด b1 b2 b3 ออกจากไปจากรูปเลย
2. เรารู้ว่า malloc จะจัดการให้ size ใหญ่อยู่หน้า และ size เล็กอยู่หลัง จัดไป!! ส่วน ptr nextsize ทั้งหลาย จะไม่มีชี้กลับไปที่ bin แต่จะเป็น circular linked list ระหว่าง chunks (ในรูปขอละ ptr bk, bk_nextsize ไว้ในฐานที่เข้าใจว่าตรงข้ามกับ fd)
เรารู้ order ว่า put/get จาก unsorted มันเป็น FIFO (กลับไปทบทวนด้านบนได้) ดังนั้นจากโค้ด เราจะได้ว่าตอน get chunks ออกมายัดลง largebin เราจะได้ chunk a1 a2 a3 ก่อนพวก a11, a12, etc. เอา a1, a2, a3 มาสร้าง structure ใหญ่ๆก่อน
3. เหมือนเดิม เรารู้ order ว่าเป็น FIFO ดังนั้นเมื่อเรา free(a11) ก่อน a(12) เวลา get ออกมายัดลง largebin ก็จะเอา a11 ลงไปก่อน a12 เช่นกัน และ เรารู้ว่า largebin จะเอาตัว size ซ้ำไปไว้ในตำแหน่งที่สองเสมอ (ไม่กระทบโครงหลักพวก fd_nextsize) จะได้ว่า a11 ถูกดันลงไปอยู่ข้างล่าง a12 แล้วก็ทำเหมือนกันกับ a22, a21
แล้วก็ลองไปเช็คกับ gdb ดู น่าจะถูกต้อง (ใครมีท่า debug ง่ายกว่านี้ แบบ beauty print ทักผมด้วยนะครับ จะซาบซึ้งใจมาก) เหมือนจะง่าย แต่ชีวิตจริงยากกว่านี้แน่นอน เพราะมีทั้ง consolidate กันเอง consolidate ข้าม bin ไปมา มีทั้ง malloc size อื่นๆที่จะไปตกกับ bin อื่นๆอีก ถ้าสำหรับ exploit แล้วคิดว่า… มันพอมีให้ exploit ตอน unlink ได้ ท่าน่าจะคล้ายกับ smallbin เลย แค่ไป overwrite fd_nextsize และ bk_nextsize แทน แต่โดยส่วนตัวผมว่าวุ่นวายกว่า ยิ่งถ้าให้ทำ full chain แบบ smallbin ด้วยนี่เหนื่อยอะ
TopChunk
เป็นตัวพิเศษที่มีการจัดการแบบพิเศษเหมือนกัน
ตอน Free
- กรณีที่ size > small และมี next_chuck เป็น top chunk จะทำการ consolidate แบบปกติกับ top chunk นั่นแหละ แต่ย้าย ptr top ของ arena ด้วย ง่ายๆ ไม่มีอะไร
ตอน Malloc
- ทำตัวเหมือนเป็น bin ใหญ่ที่สุด ใช้ก็ต่อเมื่อ binmap แล้วไม่เจอ chunk ให้ใช้เลย ค่อยมาใช้อันนี้ (best-fit ตัวสุดท้าย ใหญ่มาก เศษเหลือเยอะ) กลับกันกับกรณี free คือ ตรวจว่าเหลือที่พอไหม จากนั้นก็ split ออกมา, update ptr arena->top แล้วคืน victim ให้ user
- กรณีไม่พอ กรณีที่ 1 — consolidate fastbin แล้วกลับไปเริ่มคำนวณ unsorted bin ใหม่อีกรอบ ถ้าดูดีๆ มันไม่ได้ใช้ goto แต่ใช้วิธีครอบ for (;;) ก่อนเริ่มคำนวณ unsorted แทน da fuck!!?
- กรณีไม่พอ กรณีที่ 2 — sysmalloc ขอ memory จาก operating system เพิ่ม
ความแตกต่างของ version
แต่ละเวอร์ชั่นมีความแตกต่างกัน ทั้งด้าน feature และ security mitigation อย่างเช่น เวอร์ชั่นเก่าๆจะไม่มี tcache ดังนั้นถ้าไปอ่าน writeup เก่าๆแล้วทำตามใน Ubuntu ใหม่ๆพังแน่นอน อย่างผมต้องไปนั่ง compile ใหม่เองเอา tcache ออก
ส่วน mitigation ก็เหมือนกัน มันมีเพิ่มมาเรื่อยๆเลย ถ้าไปอ่านอันเก่ามากๆ บางอันอาจจะใช้ตรงๆไม่ได้แล้ว ต้องเพิ่มเงื่อนไขอะไรต่างๆเข้าไปด้วยเหมือนกัน
ส่วน glibc-2.32 (ซึ่ง ubuntu-20 ยังใช้ 2.31 อยู่) จะมีป้องกัน fastbin กับ tcache เข้าไปอีกชั้น เข้าใจว่าเป็นการ protect ptr ใน metadata ให้มี randomness มากขึ้น (มั้ง?) แปลว่า overflow ที่ผมอุตส่าห์ลองผ่านๆมา เวอร์ชั่นหน้าก็ต้องไปงมใหม่อีก เสียเวลาดีจริงๆ -..-
sysmalloc
เป็น function สำหรับ handle malloc case ที่ต้องการ memory เพิ่มจาก system โดย assumption คือ av->top มี space ไม่พอความต้องการแล้ว จึงจำเป็นต้อง extend หรือ replace ตัว av->top
/*ข้ามไปก่อนไม่ไหวแหละะะะ*/
Configurables
ค่าพวกนี้ผมไล่มาจาก malloc_opt ซึ่งเป็น public interface สำหรับ tune ครับ ถ้าไล่ใน src มันจะมีค่าอื่นๆอีกที่ document ระบุไว้ว่า tunable แต่ดันไม่มี public interface ให้แก้ (ยกเว้นจะ compile ใหม่) ซะงั้น
M_MXFAST: Max size สำหรับ fast bins (ระหว่าง min_size ถึง 80*(SIZE_SZ/4))M_TRIM_THRESHOLD:M_TOP_PAD:M_MMAP_THRESHOLD:M_MMAP_MAX:M_CHECK_ACTION:M_PERTURB:M_ARENA_TEST:M_ARENA_MAX:
https://danluu.com/malloc-tutorial/
https://sourceware.org/glibc/wiki/MallocInternals
http://gee.cs.oswego.edu/dl/html/malloc.html
https://stackoverflow.com/questions/8870008/what-if-i-allocate-memory-using-mmap-instead-of-malloc
https://stackoverflow.com/questions/29955609/include-source-code-of-malloc-c-in-gdb
https://azeria-labs.com/heap-exploitation-part-2-glibc-heap-free-bins/
