เหตุการณ์ที่ Malloc ทำให้ JPGLoader ของ Serenity พัง หรือ: เคล็ดลับถูกรางวัลลอตเตอรี่ (2021)

 (sin-ack.github.io)
1 คะแนน โดย GN⁺ 2024-07-08 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • ปัญหา สีเพี้ยนใน JPG ของ SerenityOS ดูเผินๆ เหมือนเป็นปัญหาลำดับอาร์กิวเมนต์ RGB/BGR แต่จริงๆ แล้วมีต้นตอมาจากการที่ JPGLoader ปล่อยให้คอมโพเนนต์ที่ต้องมีลำดับแน่นอนไปขึ้นอยู่กับลำดับการวนซ้ำของ HashTable
  • การเพิ่ม malloc_good_size() ใน AK+LibC ทำให้ Vector และ HashTable ใช้ขนาดชังก์ที่ malloc จัดสรรจริงได้ และผลลัพธ์คือ จำนวนบัคเก็ตของ HashTable เปลี่ยนไปจนบั๊กที่ซ่อนอยู่โผล่ออกมา
  • โค้ดเดิมอ่านคอมโพเนนต์ Y, Cb, Cr ของ JPG ได้ถูกลำดับโดยบังเอิญ และเพราะผลของ int_hash กับจำนวนบัคเก็ตลงตัวพอดี จึงทำให้ข้อผิดพลาดในการจัดการ สตรีม Huffman ถูกกลบไว้
  • การไล่หาสาเหตุเริ่มจากข้อเท็จจริงที่ว่า JPGLoader.cpp ไม่ได้เปลี่ยนล่าสุด และการ bisect กว่า 1000 คอมมิตก็ต้องรีบิลด์ทั้งระบบปฏิบัติการขนาดราว 3400 ไฟล์ หลายรอบ เพราะมีการเปลี่ยนแปลงฝั่ง AK
  • การแก้สุดท้ายคือทำให้การวนคอมโพเนนต์เป็นแบบ กำหนดลำดับได้แน่นอน และถ้าแก้แบบชั่วคราวด้วยการสลับลำดับอาร์กิวเมนต์สีอย่างเดียว ปัญหาเดิมก็อาจกลับมาอีกเมื่อมีการเปลี่ยนลำดับครั้งถัดไป

ปัญหาสี JPG ที่ดูเหมือนสับสนระหว่าง RGB/BGR

  • เมื่อเปิดภาพ JPG ใน SerenityOS จะเกิดปัญหาที่สีแสดงผลผิดเพี้ยน
  • ใน JPGLoader.cpp ถ้าสลับลำดับอาร์กิวเมนต์ของคอนสตรักเตอร์ Color ภาพจะดูเหมือนกลับมาเป็นปกติ
    • โค้ดเดิม: ส่งตามลำดับ Y, Cb, Cr
    • การแก้ชั่วคราว: เปลี่ยนเป็น Cr, Cb, Y
  • แต่การเปลี่ยนแปลงล่าสุดใน JPGLoader.cpp ที่ไม่ใช่การ revert นั้นเกิดขึ้นก่อนหน้านั้นมากกว่าหนึ่งเดือนตาม Git และยังจำได้ว่าเมื่อ 1–2 สัปดาห์ก่อน ภาพพื้นหลัง JPG ยังแสดงผลปกติดี
  • จึงมีแนวโน้มสูงว่าไม่ใช่แค่ ข้อผิดพลาดเรื่องลำดับช่องสี แบบตรงไปตรงมา แต่เป็นการเปลี่ยนแปลงอื่นที่ไปเปิดเผยบั๊กเดิมที่มีอยู่แล้ว

การทำ bisect ที่ยากขึ้นเพราะ AK

  • SerenityOS ใช้ AK (Agnostic Kit) ซึ่งเป็นไลบรารีมาตรฐานของตัวเอง
    • AK มีบทบาทคล้าย C++ STL แต่เปลี่ยนแปลงร่วมกับโค้ดระบบปฏิบัติการในรีโพเดียวกัน
  • เมื่อ AK เปลี่ยน ผลกระทบจะกว้างมาก
    • ไลบรารีมาตรฐานถูก include อยู่แทบทุกส่วนของโค้ด
    • เทมเพลตของ C++ ต้องมีนิยามอยู่ใน header จึงทำให้การเปลี่ยน header ของ AK กระตุ้นการคอมไพล์ใหม่ในวงกว้าง
  • ทุกครั้งที่ bisect ผ่านคอมมิตที่มีการเปลี่ยน AK จำเป็นต้องบิลด์ระบบปฏิบัติการทั้งชุดใหม่
    • ณ เวลาที่เขียนบทความ มีขนาดประมาณ 3400 ไฟล์
    • ระหว่าง bisect ช่วง 1000 คอมมิต ผู้เขียนต้อง full build 4–5 รอบบนโน้ตบุ๊ก Sandy Bridge Mobile ปี 2011
  • แม้แต่ ccache ก็ช่วยกรณีนี้ไม่ได้ และด้วยความเร็วในการเปลี่ยนแปลงของโปรเจกต์ SerenityOS ทำให้ AK มีการเปลี่ยนประมาณทุกๆ 100 คอมมิต

malloc_good_size() ที่เปิดโปงปัญหาที่ซ่อนอยู่

  • หลัง bisect กว่า 1000 คอมมิต ในที่สุดก็พบว่าการเปลี่ยนแปลงที่ทำให้สี JPG พังคือฝั่ง AK+LibC ไม่ใช่ JPGLoader
  • คอมมิตที่ทำให้ปัญหาโผล่ออกมาคือ f89e8fb71a4893911ee5125f34bd5bbb99327d33
    • ชื่อ: AK+LibC: Implement malloc_good_size() and use it for Vector/HashTable
    • เวลาสร้าง: 15 พฤษภาคม 2021
  • คอมมิตนี้เพิ่มการทำงานของ malloc_good_size() ซึ่งเป็น API ของ macOS
    • มันคืนค่าขนาดการจัดสรรจริงสำหรับคำขอจองหน่วยความจำที่ระบุ
    • ตัวอย่างเช่น ถ้าขอ 35 ไบต์แต่ภายในใช้ชังก์ 64 ไบต์ ก็จะสามารถใช้ประโยชน์จากส่วนที่เหลืออีก 29 ไบต์ได้
  • หลังการเปลี่ยนนี้ Vector, HashTable และโครงสร้างอื่นๆ ใช้หน่วยความจำที่มีอยู่จริงในชังก์ malloc ได้มากขึ้น
  • เพราะคอมมิตก่อนหน้านั้นยังแสดงภาพ JPG ได้ปกติ จึงสรุปวงให้แคบลงได้ว่าการเปลี่ยนนี้เป็นตัวที่เผยให้เห็นปัญหาเก่าที่ซ่อนอยู่

การถอดรหัสที่พึ่งพาความจุของ HashTable โดยไม่รู้ตัว

  • ตอนแรกสงสัยว่าอาจเป็นปัญหาที่ JPGLoader หรือโค้ดชั้นบนไปพึ่งพาความจุของ Vector ผิดวิธีแล้วเขียนข้อมูลตรงลงไป
  • การเปลี่ยนที่เกี่ยวข้องกระทบทั้ง HashTable และ Vector และทั้งคู่ก็ถูกใช้ในโค้ดของ JPGLoader
  • เมื่อสุ่มลบบรรทัดที่ใช้ kmalloc_good_size() ฝั่ง HashTable แล้วคอมไพล์ใหม่ ปัญหาก็หายไป
    • โค้ดที่ลบคือส่วนที่ปรับความจุบัคเก็ตใหม่ให้สอดคล้องกับขนาดการจัดสรรจริง
  • จากผลนี้จึงยืนยันได้ว่า การเปลี่ยนจำนวนบัคเก็ตของ HashTable ส่งผลต่อผลลัพธ์การถอดรหัส JPG
  • โดยธรรมชาติแล้ว HashTable ไม่ใช่คอนเทนเนอร์ที่ใช้เหมือนสตรีมข้อมูลต่อเนื่อง ดังนั้นจึงไม่ควรพึ่งพาความจุหรือลำดับการวนซ้ำของมัน

วิธีที่คอมโพเนนต์ JPG ถูกประมวลผล

  • JPGLoader เดิมจะอ่านข้อมูลคอมโพเนนต์จากส่วน Start of Frame ของไฟล์ JPG แล้วเก็บลงในโครงสร้าง Component
  • Component แต่ละตัวมี serial_id ที่บอกตำแหน่งของมันภายในไฟล์ JPG
    • โดยทั่วไปลำดับคอมโพเนนต์ของ JPG ควรเป็น Y, Cb, Cr
  • คอมโพเนนต์เหล่านี้ถูกเก็บไว้ใน HashTable
    • ต่อมาถูกใช้เพื่อตรวจสอบว่าลำดับคอมโพเนนต์ในส่วน Start of Scan ตรงกับลำดับที่คาดไว้หรือไม่
  • ในขั้นตอนถอดรหัส จะมีการวนผ่านคอมโพเนนต์เหล่านี้เพื่อนำข้อมูลไปใช้กับการแปลงแมโครบล็อก
  • ปัญหาคือคอมโพเนนต์ที่ลำดับมีความสำคัญถูกเก็บไว้ใน HashTable แล้ววนด้วย iterator ปกติ

ความต่างของลำดับการวนซ้ำระหว่างคอมมิตที่พังกับคอมมิตที่ปกติ

  • ในคอมมิตที่สีพัง ข้อความ debug แสดงว่ามีการวนคอมโพเนนต์ตามลำดับดังนี้
    • 0
    • 2
    • 1
  • ส่วนคอมมิตก่อนหน้าที่ยังปกติ ลำดับเป็นดังนี้
    • 0
    • 1
    • 2
  • ความต่างนี้เชื่อมโยงโดยตรงกับผลลัพธ์ที่ดูเหมือนช่องสีถูกสลับ
  • ระหว่างที่ทดลองสลับลำดับคอมโพเนนต์ด้วยมือร่วมกับ CxByte ก็พบข้อผิดพลาดต่อไปนี้
    • Huffman stream exhausted. This could be an error!
    • Failed to build Macroblock 3277
  • ข้อผิดพลาดนี้เผยให้เห็นว่าการถอดรหัส JPG ไวต่อ ลำดับของสตรีม และยืนยันว่าลำดับการวนคอมโพเนนต์คือสาเหตุหลัก

ลำดับของ HashTable ที่บังเอิญลงตัวพอดี

  • สาเหตุแท้จริงคือการเก็บอ็อบเจ็กต์ที่ต้องมีลำดับแน่นอนไว้ใน HashTable แล้ววนด้วย iterator ปกติ
  • แฮชของ ID คอมโพเนนต์ JPG ถูกส่งผ่าน int_hash เพื่อนำไปใช้เลือกบัคเก็ต
  • เดิมทีมีเรื่องบังเอิญสองอย่างที่ลงตัวพร้อมกัน
    • ผลของ int_hash สำหรับค่า 0, 1, 2 มีความคงที่
    • จำนวนบัคเก็ตของ AK::HashTable พอดีกับการวางคอมโพเนนต์ให้อยู่ในลำดับที่ถูกต้อง
  • เพราะความบังเอิญนี้ JPGLoader จึงอ่านสตรีม Huffman ให้แต่ละคอมโพเนนต์ตามลำดับที่ถูกต้อง และทำให้บั๊กถูกซ่อนไว้มาตั้งแต่แรก
  • เมื่อมีการเพิ่ม malloc_good_size() แล้วจำนวนบัคเก็ตของ HashTable เปลี่ยน ลำดับคอมโพเนนต์ก็เปลี่ยนตาม และภาพที่ได้จึงมีช่องสีแดงกับน้ำเงินสลับกัน

การแก้สุดท้ายด้วยการวนซ้ำแบบกำหนดลำดับแน่นอน

  • หลังดีบักอยู่นานประมาณ 10 ชั่วโมง ก็ได้คอมมิตแก้ไขออกมา
  • คอมมิตแก้ไขคือ a10ad24c760bfe713f1493e49dff7da16d14bf39
    • ชื่อ: LibGfx: Make JPGLoader iterate components deterministically
    • เวลาสร้าง: 31 พฤษภาคม 2021
  • แก่นของการแก้คือทำให้ JPGLoader วนคอมโพเนนต์ในแบบ กำหนดลำดับได้แน่นอน
  • การสลับลำดับอาร์กิวเมนต์ของ Color อย่างเดียว แม้จะทำให้ภาพดูเหมือนถูกต้องในตอนนั้น แต่ถ้าในอนาคตมีการเปลี่ยนแปลงอื่นที่ทำให้ลำดับการวนเปลี่ยนอีก ก็อาจพังได้เหมือนเดิม
  • นี่เป็นตัวอย่างของปัญหาที่ดูเหมือนเป็นแค่ข้อผิดพลาดเล็กๆ ด้านการแสดงผล แต่จริงๆ แล้วเกิดจากการพึ่งพาลำดับการวนของคอนเทนเนอร์อย่างผิดวิธี ร่วมกับการเปลี่ยนแปลงขนาดการจัดสรรหน่วยความจำที่ไปเปิดโปงมัน

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-07-08
ความคิดเห็นบน Hacker News

  • นี่คือหนึ่งในเหตุผลที่การใช้งาน hash table จำนวนมากใส่องค์ประกอบแบบสุ่มเข้าไปในอัลกอริทึม
    เพราะลำดับขององค์ประกอบจะเปลี่ยนไปทุกครั้งที่รัน หากเผลอพึ่งพาลำดับโดยไม่ตั้งใจ ปัญหาก็จะโผล่มาให้เห็นอย่างรวดเร็ว
    ถ้าอัลกอริทึมแฮชคงที่ ก็สามารถสร้างคีย์ที่ไปรวมอยู่ในบักเก็ตเดียวกันเพื่อใช้โจมตีแบบ denial-of-service ได้ ซึ่งวิธีนี้ยังช่วยป้องกันปัญหาด้านความปลอดภัยแบบนั้นได้ค่อนข้างดีด้วย

    • ช่วงนี้กลับกัน มีการใช้งาน hash table จำนวนมากที่รับประกันว่าจะ วนลูปตามลำดับการแทรก เสมอ
      ผมชอบแบบนี้มากกว่า เพราะไม่ต้องตัดสินใจทุกครั้งว่าต้องใช้ map ที่เรียงลำดับแล้วหรือ map ที่ไม่เรียงลำดับ
      เคยมีหลายครั้งที่คิดว่าใช้ map แบบไม่เรียงลำดับก็พอ แต่กลับผิดด้วยเหตุผลเล็ก ๆ น้อย ๆ
    • ถ้าองค์ประกอบสุ่มนั้นเป็น seed ที่บังคับกำหนด บันทึก ล็อก และทำซ้ำได้ ก็โอเค
      ไม่อย่างนั้นมันเป็นความคิดที่แย่มาก เพราะจะทำให้การดีบักปัญหาอื่นยากขึ้นมาก
      ความสุ่มไม่ใช่เพื่อน แต่เป็นศัตรู
      ประมาณ 20 ปีก่อน มีวิธีโจมตีเว็บเซิร์ฟเวอร์ Java โดยปรับแต่งพารามิเตอร์ URL ให้ทั้งหมดตกไปอยู่ในบักเก็ตเดียวกัน และกลายเป็นการโจมตี denial-of-service ครั้งใหญ่
      ถ้าจำไม่ผิด เว็บเซิร์ฟเวอร์ PHP ก็เจอปัญหาความปลอดภัยแบบเดียวกันเป๊ะ
      แก้ด้วยการใส่ seed ให้ hash table และแน่นอนว่า seed นั้นนักพัฒนาควบคุมได้ เพราะความสุ่มไม่ใช่เพื่อน แต่เป็นศัตรู

  • เรื่องนี้ดูเหมือนเป็นกรณีที่ถ้าดีบักเพิ่มอีกหน่อย แทนที่จะทำ bisect แบบ binary search ไปเรื่อย ๆ ก็น่าจะประหยัดเวลาได้
    สุดท้ายก็ยังต้องใส่ log ที่พิมพ์ลำดับของคอมโพเนนต์อยู่ดี

  • การดีบักก็ดี แต่ ข้อความ commit ก็ยอดเยี่ยมเช่นกัน
    สรุปสาเหตุและการแก้ไขไว้ได้ดีภายในไม่กี่ย่อหน้า

  • ถ้ารอนานพอ C++ ก็จะมีฟีเจอร์ที่เทียบเท่ากับ malloc_good_size เข้ามา
    https://github.com/cplusplus/papers/issues/18

  • ชื่อเรื่องต้องมี [2021]

  • นี่ไม่ใช่ความผิดของ Gunnar ปัญหาอยู่ที่คนที่เอา ข้อมูลที่มีลำดับ ไปเก็บไว้ในไฟล์แฮช
    ตลอดหลายสิบปีที่ทำงานนี้มา ผมเจอสถานการณ์ที่เมื่อ layout หน่วยความจำเปลี่ยนแล้วบั๊กที่ซ่อนอยู่ก็ถูกเผยออกมาหลายครั้ง
    แต่ละครั้งต้องใช้เวลาดีบักตั้งแต่หลายชั่วโมงไปจนถึงหลายวัน
    ถ้าการเขียนโปรแกรมไม่ยาก เราก็คงไม่จำเป็น แต่ก็ไม่รู้ว่าประโยคนี้จะยืนอยู่ได้นานแค่ไหนในยุคของ large language models

    • ใช่ ต่อให้เป็นความผิดของ Gunnar จริง ๆ ก็ดูไม่จำเป็นต้องเขียนไว้ในข้อความ commit
      Gunnar ปรับปรุงบางอย่างให้ดีขึ้น และในกระบวนการนั้นก็แค่ทำให้ปัญหาของโค้ดเก่าที่พังอยู่แล้วโผล่ออกมา
      แต่รางวัลตอบแทนของความพยายามนั้นกลับเป็นคำพูดอย่าง “Gunnar, I like you, but please don't make me go through this again. :^)”
    • ตราบใดที่ large language models ถูกฝึกด้วย โค้ดที่มีบั๊ก มันก็จะเสนอแต่โค้ดที่มีบั๊ก
    • ใช่ และตรงข้ามกับชื่อเรื่อง นี่ก็ไม่ใช่ความผิดของ malloc() เช่นกัน

  • เท่าที่รู้ SerenityOS มีทรัพยากรสำหรับทดสอบ หรือมีคนที่ช่วยกันเรื่องพีซีอยู่

  • การบอกว่าสร้าง SerenityOS ตั้งแต่ต้น 4–5 ครั้งบนแล็ปท็อป Sandy Bridge Mobile ปี 2011 ก็คล้ายกับการพยายาม พัฒนา Windows Vista บนคอมพิวเตอร์ที่ออกมาในช่วงระหว่าง Windows 3.1 กับ Windows 95

    • ถ้าวัดตามระยะเวลาก็ใช่ แต่ถ้าวัดตามประสิทธิภาพจริงไม่เหมือนกัน
      หลังปี 2011 CPU ไม่ได้เปลี่ยนไปมากขนาดนั้นในเชิงสัมพัทธ์ แต่ช่วงระหว่าง Windows 3.1 ถึง Vista นั้น x64 เริ่มแพร่หลาย และ CPU หลายคอร์ ก็กลายเป็นเรื่องปกติ
    • เป็นการเปรียบเทียบที่ดี CPU ของนักพัฒนามีอายุราว 13 ปี
      Vista เปิดตัวทั่วโลกต้นปี 2007 ดังนั้น CPU ที่มีอายุ 13 ปี ณ เวลาที่เปิดตัว ก็คือรุ่นปี 1994 ซึ่งเป็นช่วงประมาณหนึ่งปีหลังจาก Pentium รุ่นแรกออกมา
      ตอนนั้นยังมีคนจำนวนมากใช้ 486 DX2-66 ที่ไว้ใจได้อยู่
      น่าประทับใจทีเดียวที่ CPU อายุ 13 ปียังใช้ทำงานกับโปรเจกต์สมัยใหม่ในปัจจุบันได้ ตอนนั้นคงพูดแบบเดียวกันได้ยาก
      หวังว่า CPU ที่ออกวันนี้จะยังใช้งานได้อย่างน่าพอใจไปจนหลังปี 2037
    • ตลอดปีที่ผ่านมา ผมใช้ Lenovo i5 ปี 2011 ลง Windows 11 เป็นเดสก์ท็อปหลักกับจอคู่
      Visual Studio ก็รันได้ดี Photoshop ก็มีแค่เครื่องมือ AI ในระบบที่หน่วงนิดหน่อย
      น่าจะเปิดแท็บ Chrome ไว้ราว 200 แท็บ พร้อมกับ Slack, WhatsApp และเบราว์เซอร์สำหรับทดสอบอีก 3 ตัว
      CapCut ถ้าตัดต่อ 4K ก็อยากให้เร็วขึ้นอีกหน่อย แต่โปรเจกต์ 2K ที่ซับซ้อนก็ยังรับไหวสบาย
      มีแค่โปรเจกต์ After Effects ที่ซับซ้อนเท่านั้นที่เริ่มชนขีดจำกัด มันไม่ค่อยชอบงานนั้น
      คงต้องอัปเกรดแล้ว แต่สำหรับระบบที่แทบจะเก็บมาจากถังขยะ ถือว่าใช้ได้ดีทีเดียว

  • เห็น “Alien Lenna” แล้วรู้สึก เดจาวู ที่แท้ก็เป็นบทความที่เคยอ่านและเคยคอมเมนต์ไว้ก่อนหน้านี้จริง ๆ
    https://news.ycombinator.com/item?id=27374942 (2021)