โมเดลแบบย่อของ Fil-C

 (corsix.org)
2 คะแนน โดย GN⁺ 11 일 전 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • โครงสร้างที่ติดตาม เมทาดาทา AllocationRecord ไปพร้อมกับพอยน์เตอร์ C/C++ และทำ การตรวจสอบขอบเขตหน่วยความจำ ตอน dereference
  • วิธีที่ย้ายค่าพอยน์เตอร์เดิมและเมทาดาทาที่สอดคล้องกันไปด้วยกัน หรือแปลงเป็น การเรียกเฉพาะของ Fil-C ตั้งแต่การกำหนดค่าพอยน์เตอร์ การคำนวณเลขคณิต การส่งอาร์กิวเมนต์เข้าฟังก์ชัน การคืนค่า ตลอดจนการเรียก malloc และ free
  • เมทาดาทาของพอยน์เตอร์ภายในหน่วยความจำฮีปจะเก็บแยกไว้ใน invisible_bytes และเมื่อโหลด/เก็บพอยน์เตอร์ก็จะอ่านเขียนค่ากับเมทาดาทาไปพร้อมกัน รวมถึงเพิ่ม การตรวจสอบการจัดแนว
  • filc_free จะปลดปล่อยเฉพาะ visible_bytes และ invisible_bytes โดย คง AllocationRecord เองไว้ หลังจากนั้นให้ garbage collector จัดการต่อ และตัวแปรโลคัลที่มีความเป็นไปได้ว่าที่อยู่จะหลุดออกไปจะถูก ยกระดับขึ้นฮีป
  • แม้ยังมีความซับซ้อนของการติดตั้งใช้งานจริง เช่น เธรด ฟังก์ชันพอยน์เตอร์ และการปรับแต่งหน่วยความจำ/ประสิทธิภาพ แต่ก็ยังใช้เป็นตัวอย่างระบบรูปธรรมสำหรับ การตรวจสอบความปลอดภัยหน่วยความจำ ของโค้ด C/C++ ขนาดใหญ่ หรือสำหรับ pointer provenance ได้

โมเดล Fil-C แบบย่อ

  • Fil-C ใช้โครงสร้างที่ติดตามเมทาดาทา AllocationRecord* ควบคู่กับพอยน์เตอร์เพื่อจัดการโค้ด C/C++ ให้ปลอดภัยด้านหน่วยความจำ
    • การติดตั้งใช้งานจริงเป็นการเขียน LLVM IR ใหม่ แต่โมเดลแบบย่ออยู่ในรูปการแปลงซอร์สโค้ด C/C++ อัตโนมัติ
    • เพิ่มตัวแปรโลคัล AllocationRecord* ที่สอดคล้องกันสำหรับตัวแปรโลคัลชนิดพอยน์เตอร์แต่ละตัวในทุกฟังก์ชัน
    • ตัวอย่างเช่น สำหรับ T1* p1 จะเพิ่ม AllocationRecord* p1ar = NULL
  • การกำหนดค่าและการคำนวณอย่างง่ายกับตัวแปรโลคัลชนิดพอยน์เตอร์จะย้าย AllocationRecord* ไปพร้อมกับค่าพอยน์เตอร์เดิม
    • p1 = p2 จะถูกแปลงเป็น p1 = p2, p1ar = p2ar
    • p1 = p2 + 10 ก็จะมาพร้อม p1ar = p2ar
    • การ cast จากจำนวนเต็มเป็นพอยน์เตอร์จะตั้งเมทาดาทาเป็น NULL
    • การ cast จากพอยน์เตอร์เป็นจำนวนเต็มคงไว้เหมือนเดิม
  • ตอนส่งอาร์กิวเมนต์เข้าฟังก์ชันและตอนคืนค่าก็จะส่ง AllocationRecord* เพิ่มไปพร้อมกับพอยน์เตอร์ และบางการเรียกของไลบรารีมาตรฐานจะถูกแทนที่ด้วย ฟังก์ชันเฉพาะของ Fil-C
    • การเรียก malloc และ free จะถูกแปลงเป็น filc_malloc และ filc_free
    • ตัวอย่างเช่น p1 = malloc(x); free(p1); จะกลายเป็น {p1, p1ar} = filc_malloc(x); filc_free(p1, p1ar);
  • filc_malloc ไม่ได้จัดสรรแค่หน่วยความจำที่ขอ แต่ทำ การจัดสรรสามส่วน
    • จัดสรรออบเจ็กต์ AllocationRecord
    • จัดสรร visible_bytes สำหรับข้อมูลจริง
    • จัดสรร invisible_bytes ด้วย calloc สำหรับเก็บเมทาดาทาที่มองไม่เห็น
    • AllocationRecord มีฟิลด์ visible_bytes, invisible_bytes, length

การ dereference และการตรวจสอบขอบเขต

  • ตอน dereference พอยน์เตอร์ จะใช้ AllocationRecord* ที่มากับพอยน์เตอร์เพื่อทำ การตรวจสอบขอบเขต
    • ตรวจสอบว่าเมทาดาทาของพอยน์เตอร์ไม่ใช่ NULL
    • คำนวณผลต่างระหว่างตำแหน่งพอยน์เตอร์ปัจจุบันกับตำแหน่งเริ่มต้นของ visible_bytes
    • ตรวจสอบว่า offset เล็กกว่าความยาวทั้งหมด
    • ตรวจสอบว่าความยาวที่เหลือเพียงพอกับขนาดของเป้าหมายที่กำลัง dereference
  • ทั้งการอ่านและการเขียนใช้ขั้นตอนตรวจสอบเดียวกัน
    • มีการตรวจสอบก่อน x = *p1
    • และตรวจสอบในรูปแบบเดียวกันก่อน *p2 = x
  • โครงสร้างนี้ช่วยบล็อกการเข้าถึงที่พอยน์เตอร์ชี้ออกนอกช่วงที่จัดสรรไว้

พอยน์เตอร์ในฮีปและ invisible_bytes

  • พอยน์เตอร์ที่เก็บอยู่ในหน่วยความจำฮีปไม่สามารถให้คอมไพเลอร์จัดการเป็นตัวแปรแยกเหมือนตัวแปรโลคัลได้โดยตรง จึงใช้ invisible_bytes
    • ถ้ามีพอยน์เตอร์อยู่ที่ตำแหน่ง visible_bytes + i ค่า AllocationRecord* ที่สอดคล้องกันจะถูกเก็บที่ invisible_bytes + i
    • กล่าวคือ invisible_bytes จะทำงานเหมือนอาร์เรย์ที่มีชนิดสมาชิกเป็น AllocationRecord*
  • เมื่ออ่านหรือเขียนค่าพอยน์เตอร์จากหน่วยความจำ จะมี การตรวจสอบการจัดแนว เพิ่มจากการตรวจสอบขอบเขตทั่วไป
    • ตรวจสอบว่า offset i เป็นพหุคูณของ sizeof(AllocationRecord*)
    • ต้องเป็นจริงจึงจะเข้าถึง invisible_bytes อย่างปลอดภัยในฐานะอาร์เรย์ AllocationRecord** ได้
  • ตอนโหลดพอยน์เตอร์ จะโหลดทั้ง data pointer และเมทาดาทาไปพร้อมกัน
    • p2 = *p1 จะมี p2ar = *(AllocationRecord**)(p1ar->invisible_bytes + i) เพิ่มตามหลัง p2 = *p1
  • ตอนเก็บพอยน์เตอร์ จะเก็บไม่ใช่แค่ค่าพอยน์เตอร์ แต่รวมเมทาดาทาที่สอดคล้องกันด้วย
    • *p1 = p2 หลังเก็บข้อมูลจริงแล้วจะทำ *(AllocationRecord**)(p1ar->invisible_bytes + i) = p2ar

filc_free และ garbage collector

  • filc_free เมื่อพอยน์เตอร์ไม่ใช่ NULL จะตรวจสอบความสอดคล้องกับ AllocationRecord แล้วปลดปล่อยหน่วยความจำเพียงสองส่วน
    • ตรวจสอบ par != NULL
    • ตรวจสอบ p == par->visible_bytes
    • ปลดปล่อย visible_bytes และ invisible_bytes
    • จากนั้นตั้ง visible_bytes, invisible_bytes เป็น NULL และตั้ง length เป็น 0
  • แม้ filc_malloc จะจัดสรรสามส่วน แต่ filc_free จะ ไม่ปลดปล่อยออบเจ็กต์ AllocationRecord เอง
    • ความต่างนี้จัดการโดย garbage collector
  • สำหรับโมเดลแบบย่อ GC แบบ stop-the-world ก็เพียงพอ ส่วน Fil-C จริงใช้ตัวเก็บกวาดแบบขนาน ทำงานพร้อมกัน และค่อยเป็นค่อยไป
    • GC จะติดตามโดยไล่ตามออบเจ็กต์ AllocationRecord
    • AllocationRecord ที่เข้าถึงไม่ได้จะถูกทำเครื่องหมายเพื่อปลดปล่อย
  • GC ยังทำงานเพิ่มอีกสองอย่าง
    • เมื่อจะปลดปล่อย AllocationRecord ที่เข้าถึงไม่ได้ จะเรียก filc_free
    • พอยน์เตอร์ทั้งหมดที่ชี้ไปยัง AllocationRecord ที่มี length เป็น 0 จะถูกเปลี่ยนให้ชี้ไปยัง AllocationRecord ปกติเดี่ยวที่มีความยาว 0
  • ด้วยพฤติกรรมนี้ แม้ไม่เรียก free ก็จะไม่กลายเป็นหน่วยความจำรั่ว
    • GC จะปลดปล่อยให้อัตโนมัติ
    • แต่การเรียก free ยังช่วยให้ปล่อยหน่วยความจำได้เร็วกว่ารอ GC
  • หลัง free แล้ว AllocationRecord นั้นจะกลายเป็นสถานะเข้าถึงไม่ได้ในที่สุด และเก็บกวาดทีหลังได้

การหลุดออกของที่อยู่ตัวแปรโลคัลและการยกระดับขึ้นฮีป

  • เมื่อมี GC ขอบเขตของการจัดการที่อยู่ของตัวแปรโลคัลอย่างปลอดภัยจะกว้างขึ้น
    • หากคอมไพเลอร์พิสูจน์ไม่ได้ว่าที่อยู่ของตัวแปรโลคัลที่ถูกนำไปใช้นั้น จะไม่หลุดออก นอกช่วงอายุของตัวแปร ก็จะยกระดับไปจัดสรรบนฮีป
  • ตัวแปรโลคัลประเภทนี้จะถูกจัดสรรผ่าน malloc แทนสแตก
    • ไม่จำเป็นต้องแทรก free ที่สอดคล้องกันแยกต่างหาก
    • GC จะเป็นผู้เก็บกวาด

memmove เวอร์ชัน Fil-C

  • memmove ในไลบรารีมาตรฐานของ C จัดการหน่วยความจำแบบ arbitrary จึงมีปัญหาว่าคอมไพเลอร์ไม่รู้ว่าข้างในมีพอยน์เตอร์หรือไม่
  • เพื่อแก้ปัญหานี้จึงใช้ heuristic
    • พอยน์เตอร์ภายในหน่วยความจำ arbitrary ต้อง อยู่ครบทั้งตัว ภายในช่วงหน่วยความจำนั้น
    • พอยน์เตอร์ต้องจัดแนวอย่างถูกต้อง
  • กฎนี้ทำให้แม้ย้ายข้อมูล 8 ไบต์เท่ากันก็อาจทำงานต่างกัน
    • ถ้า memmove ข้อมูล 8 ไบต์ที่จัดแนวดีในครั้งเดียว invisible_bytes ของช่วงที่สอดคล้องกันจะถูกย้ายไปด้วย
    • แต่ถ้าแบ่ง memmove ทีละ 1 ไบต์ 8 ครั้ง invisible_bytes จะไม่ถูกย้าย

ความซับซ้อนเพิ่มเติมในการติดตั้งใช้งานจริง

  • เธรด

    • การทำงานพร้อมกันเป็นปัจจัยที่เพิ่ม ความซับซ้อนของ GC
    • filc_free ไม่สามารถปล่อยหน่วยความจำได้ทันที
      • เพราะอาจเกิด race condition ระหว่างเธรดที่กำลังปล่อยกับเธรดอื่นที่เข้าถึงหน่วยความจำเดียวกัน
    • การดำเนินการแบบอะตอมมิกกับพอยน์เตอร์ก็ต้องมีการจัดการเพิ่ม
      • เพราะการเขียนใหม่พื้นฐานจะเปลี่ยนการโหลด/เก็บพอยน์เตอร์หนึ่งครั้งให้เป็นการโหลด/เก็บสองครั้ง จึงทำลายความเป็นอะตอมมิก

  • ฟังก์ชันพอยน์เตอร์

    • เพิ่มเมทาดาทาใน AllocationRecord เพื่อระบุว่า visible_bytes ไม่ใช่ข้อมูลทั่วไป แต่เป็น พอยน์เตอร์ไปยังโค้ดที่รันได้
    • การเรียกผ่านฟังก์ชันพอยน์เตอร์ p1 จะตรวจสอบทั้ง p1 == p1ar->visible_bytes และตรวจว่า p1ar แทนฟังก์ชันพอยน์เตอร์จริง
    • เพื่อป้องกันการโจมตีแบบ type confusion กับฟังก์ชันพอยน์เตอร์ ยังต้องมี การตรวจสอบ type signature ใน ABI ตอนเรียกด้วย
    • วิธีหนึ่งคือทำให้ทุกฟังก์ชันมี type signature เดียวกัน
      • เช่น จัดทุกอาร์กิวเมนต์ลงใน struct แล้วส่งผ่านหน่วยความจำ
      • ที่ขอบเขต ABI แต่ละฟังก์ชันจะรับเพียง AllocationRecord เดียวที่สอดคล้องกับ struct นั้น

  • การปรับใช้หน่วยความจำให้เหมาะสม

    • อาจพิจารณาให้ filc_malloc ยังไม่จัดสรร invisible_bytes ทันที แต่ค่อยจัดสรรเมื่อจำเป็น
    • อาจพิจารณาวาง AllocationRecord กับ visible_bytes รวมไว้ในการจัดสรรครั้งเดียว
    • หาก malloc ชั้นล่างติดเมทาดาทาไว้ด้านหน้าของแต่ละการจัดสรร ก็อาจนำเมทาดาทานั้นมาใส่ใน AllocationRecord ได้เช่นกัน

  • การเพิ่มประสิทธิภาพ

    • ความปลอดภัยด้านหน่วยความจำของ Fil-C มาพร้อม ต้นทุนด้านประสิทธิภาพ
    • ยังมีช่องให้ใช้เทคนิคต่าง ๆ เพื่อดึงประสิทธิภาพที่เสียไปกลับคืนมาบางส่วน

ช่วงเวลาที่เหมาะกับการใช้ Fil-C

  • ใช้ได้ในกรณีที่โค้ด C/C++ ขนาดใหญ่ดูเหมือนทำงานได้ แต่ยัง ไม่มีการตรวจสอบความปลอดภัยหน่วยความจำ และยอมรับการนำ GC มาใช้รวมถึงการลดลงของประสิทธิภาพจำนวนมากได้
    • มีการกล่าวถึงความเป็นไปได้ที่จะใช้เป็นมาตรการชั่วคราวก่อนเขียนใหม่เป็น Java, Go, Rust
  • สามารถรัน Fil-C เพื่อจุดประสงค์ในการตรวจหาบั๊กหน่วยความจำแบบ ASan ได้ด้วย
    • สามารถรันโค้ด C/C++ ภายใต้ Fil-C เพื่อตรวจสอบบั๊กหน่วยความจำ
  • ในภาษาที่ภาษาตอนคอมไพล์และภาษารันไทม์เป็นภาษาเดียวกัน และมีความปลอดภัยตอนคอมไพล์สูง ก็อาจใช้สำหรับ การประเมินผลตอนคอมไพล์อย่างปลอดภัย ได้
    • มีการยก Zig เป็นตัวอย่าง
    • แม้การประเมินตอนรันไทม์จะไม่ปลอดภัย แต่การประเมินตอนคอมไพล์สามารถใช้โครงแบบ Fil-C ได้
  • ยังมีความหมายในฐานะกรณีศึกษาระบบรูปธรรมที่จัดการ pointer provenance
    • มีการตั้งคำถามถึงความเป็นไปได้ของการทำ optimization จาก if (p1 == p2) { f(p1); } เป็น if (p1 == p2) { f(p2); } เมื่อ p1 และ p2 มีชนิดเดียวกัน
    • ใน Fil-C คำตอบคือไม่อย่างชัดเจน เพราะ AllocationRecord* ที่ส่งเข้า f ต่างกัน
    • ในจุดนี้ Fil-C จึงทำหน้าที่เป็นตัวอย่างระบบรูปธรรมที่มี pointer provenance

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

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

 
GN⁺ 11 일 전
ความคิดเห็นบน Hacker News
  • น่าจะเป็นการทดลองที่น่าสนุกพอสมควรถ้าลองเอา invisicaps ไปใส่กับอะไรอย่าง chibicc หรือ slimcc
    ก็น่าจะมีพื้นที่ให้ลองทั้ง reference counting หรือรูปแบบดัดแปลงของ invisible capability system และอาจประหยัดหน่วยความจำได้โดยแลกกับต้นทุนของการอ้างอิงทางอ้อมเพิ่มขึ้นเล็กน้อย
  • ฉันทำ filc-bazel-template ขึ้นมาแล้วห่อไว้เป็น Bazel target
    หวังว่าจะช่วยคนที่อยากใช้สองอย่างนี้ร่วมกันเพื่อทำ hermetic builds ได้
  • ฉันไม่ค่อยเข้าใจว่าประโยคนี้หมายถึงอะไร
    Upon freeing an unreachable AllocationRecord, call filc_free on it.
    เท่าที่ฉันเข้าใจ สิ่งที่ตั้งใจจะสื่อคือน่าจะให้ปล่อยหน่วยความจำที่ฟิลด์ visible_bytes และ invisible_bytes ชี้อยู่ก่อน แล้วค่อยปล่อย AR ที่ไม่สามารถเข้าถึงได้
  • ฉันรู้สึกว่า Fil-C เป็นหนึ่งในโปรเจ็กต์ที่ถูกประเมินค่าต่ำที่สุดเท่าที่เคยเห็นมา
    แทนที่จะบอกว่าเพื่อความปลอดภัยให้ “rewrite it in Rust” ฉันกลับมองว่าการที่สามารถคอมไพล์โปรแกรม C เดิมให้ปลอดภัยด้านหน่วยความจำได้แบบสมบูรณ์นั้นน่าสนใจกว่า
    • ผมว่ามีอยู่หลายอย่างที่ต้องพิจารณาร่วมกัน
      อย่างแรก Fil-C ช้ากว่าและตัวใหญ่กว่า ถ้าสิ่งนั้นโอเค งั้นตลอด 10 ปีที่ผ่านมาเราก็น่าจะหันไปใช้ Java หรือ C# ก่อน Rust แล้ว
      อย่างที่สอง มันก็ยังคงเป็นการเขียน C อยู่ดี เหมาะกับการดูแลโค้ดเดิม แต่ถ้าจะเขียนโค้ดใหม่เยอะ ๆ ผมรู้สึกว่า Rust ใช้งานสบายกว่ามาก
      อย่างที่สาม Fil-C เป็นความปลอดภัยตอนรันไทม์ ขณะที่ Rust สามารถแสดงบางอย่างได้ตั้งแต่คอมไพล์ไทม์ และยิ่งไปกว่านั้น ภาษาอย่าง WUFFS ยังพยายามพิสูจน์ความปลอดภัยตั้งแต่ขั้นคอมไพล์โดยไม่ต้องมี runtime checks ดังนั้นแม้โค้ดอาจผิดเชิงตรรกะได้ แต่จะมุ่งป้องกันการแครชหรือการรันโค้ดโดยพลการ ซึ่งเป็นคนละแนวทางกัน
    • ผมไม่คิดว่ามันถูกประเมินค่าต่ำนะ มีการพูดคุยเกี่ยวกับมันมาเยอะพอสมควรแล้ว
      มีทั้งเธรดอย่าง Fil-Qt: A Qt Base build with Fil-C experience, Linux Sandboxes and Fil-C, Ported freetype, fontconfig, harfbuzz, and graphite to Fil-C, A Note on Fil-C, Notes by djb on using Fil-C, Fil-C: A memory-safe C implementation, Fil's Unbelievable Garbage Collector
    • สำหรับผม ข้อจำกัดหลักของ Fil-C คือมันเป็น runtime memory safety
      คุณยังคงเขียนโค้ดที่ไม่ปลอดภัยด้านหน่วยความจำได้อยู่ และตอนนี้ผลลัพธ์ก็เพียงแค่เปลี่ยนจากช่องโหว่ไปเป็นการแครชอย่างแน่นอน
      ถ้าคุณกำลังสร้างอะไรอย่างเว็บ API ที่รับอินพุตจากผู้ไม่หวังดี ปัญหาแบบนี้สุดท้ายก็อาจกลายเป็น denial-of-service ได้ ดังนั้นแม้จะดีกว่าเดิม แต่ผมก็ยังไม่คิดว่าดีพอ
      ไม่ได้จะลดคุณค่างานของ Fil-C นะ แค่คิดว่าวิธีแบบรันไทม์มีข้อจำกัดที่ชัดเจนจริง ๆ
    • ขอบคุณที่สนใจ
      แต่ถ้าจะพูดกันอย่างยุติธรรม Fil-C ช้ากว่า Rust พอสมควร และใช้หน่วยความจำมากกว่า
      ในทางกลับกัน Fil-C รองรับ safe dynamic linking และในบางแง่มุมก็อาจพูดได้ว่าปลอดภัยกว่า Rust เสียอีก
      สุดท้ายแล้วมันคือ trade-off ดังนั้นก็คงต้องเลือกให้เหมาะกับสถานการณ์ของตัวเอง
    • ความรู้สึกของผมคือ เวลาคุณบอกโปรแกรมเมอร์ C/C++ ว่าเขาสามารถใส่ garbage collector ลงในโปรแกรมของตัวเองได้ แววตาเป็นประกายนั้นเกิดขึ้นไม่บ่อยนัก
      เพราะงั้นถึงไอเดียนี้จะน่าสนใจในเชิงเทคนิค แต่ในเชิงอารมณ์ความรู้สึกมันอาจขายได้ไม่ง่าย
  • ในมุมมองของผม Fil-C ยังไม่ปลอดภัยด้านหน่วยความจำในสถานการณ์ data race
    เพราะค่า capability กับค่า pointer อาจถูกเขียนขาดกลางได้ และถ้าการสลับการทำงานของเธรดเกิดขึ้นในจังหวะที่แย่ ก็อาจเข้าถึงอ็อบเจ็กต์ด้วยพอยน์เตอร์ที่ผิดจนเกิด การทำงานผิดพลาดโดยพลการ ได้
    ตัวข้อจำกัดแบบนี้ผมพอรับได้ แต่สิ่งที่น่าเสียดายคือบรรยากาศที่แม้แต่ผู้สนับสนุนก็ยังร่วมกันตอบโต้คนที่ชี้ปัญหาอย่างรุนแรง
    • เท่าที่ผมรู้ เขาจัดการส่วนนี้ด้วย atomic ops
      แต่น่าเสียดายที่นั่นก็เป็นหนึ่งในต้นตอสำคัญของโอเวอร์เฮดด้วย
  • ผมมองว่าสุดท้ายแล้วนี่ก็คืออีกหนึ่งรูปแบบของเทคนิคตระกูล fat pointers
    วิธีแบบนี้เคยถูกนำไปทำหลายครั้งแล้วก็ถูกตัดทิ้งไปบ่อย เพราะไม่ให้หลักประกันด้านความปลอดภัยที่เพียงพอ หรือข้าม non-fat ABI boundaries ได้ยาก หรือไม่ก็มีโอเวอร์เฮดสูง
    • แต่ช่วงนี้ก็เริ่มมีแนวโน้มที่ ฮาร์ดแวร์รองรับ fat pointers โดยตรง กลับมาอีกครั้ง ดังนั้นอาจจะยังไม่ควรปัดตกเร็วเกินไป
      อีกอย่างผมคิดว่า filc เองก็อธิบายได้ไม่หมดด้วยแนวคิด fat pointer แบบธรรมดา
    • และผมคิดว่าควรดูควบคู่ไปด้วยว่า ปัจจุบันหลายแพลตฟอร์มก็มี hardware memory tagging ให้ใช้แล้วด้วย