Mô hình đơn giản hóa của Fil-C

 (corsix.org)
2 điểm bởi GN⁺ 4 ngày trước | 1 bình luận | Chia sẻ qua WhatsApp
  • Cấu trúc theo dõi con trỏ C/C++ bằng cách gắn kèm siêu dữ liệu AllocationRecord và thực hiện kiểm tra biên bộ nhớ khi dereference
  • Với gán con trỏ, phép toán số học, truyền tham số hàm, giá trị trả về, cho tới các lệnh gọi malloc·free, giá trị con trỏ gốc và siêu dữ liệu tương ứng được di chuyển cùng nhau hoặc được chuyển thành lời gọi chuyên dụng của Fil-C
  • Siêu dữ liệu con trỏ trong bộ nhớ heap được lưu riêng trong invisible_bytes; khi tải/lưu con trỏ thì đọc và ghi cả giá trị lẫn siêu dữ liệu, đồng thời áp dụng thêm kiểm tra căn chỉnh
  • filc_free chỉ giải phóng visible_bytes và invisible_bytes, còn bản thân AllocationRecord vẫn được giữ lại; phần dọn dẹp về sau do bộ gom rác đảm nhiệm, còn biến cục bộ có khả năng để lộ địa chỉ sẽ được nâng lên heap
  • Dù vẫn còn các độ phức tạp triển khai thực tế như luồng, con trỏ hàm, tối ưu bộ nhớ và hiệu năng, mô hình này vẫn có thể được dùng như một ví dụ hệ thống cụ thể cho việc kiểm chứng an toàn bộ nhớ của mã C/C++ quy mô lớn hoặc cho pointer provenance

Mô hình Fil-C đơn giản hóa

  • Fil-C sử dụng cấu trúc theo dõi siêu dữ liệu AllocationRecord* đi kèm con trỏ để xử lý mã C/C++ theo hướng an toàn bộ nhớ
    • Bản triển khai thực tế dùng cách viết lại LLVM IR, nhưng mô hình đơn giản là tự động biến đổi mã nguồn C/C++
    • Với mỗi biến cục bộ kiểu con trỏ trong hàm, thêm một biến cục bộ AllocationRecord* tương ứng
    • Ví dụ, với T1* p1 thì thêm AllocationRecord* p1ar = NULL
  • Các phép gán và tính toán đơn giản trên biến cục bộ kiểu con trỏ sẽ di chuyển cả AllocationRecord* cùng với giá trị con trỏ gốc
    • p1 = p2 được biến đổi thành p1 = p2, p1ar = p2ar
    • p1 = p2 + 10 cũng đi kèm p1ar = p2ar
    • Cast từ số nguyên sang con trỏ sẽ đặt siêu dữ liệu thành NULL
    • Cast từ con trỏ sang số nguyên được giữ nguyên
  • Khi truyền tham số hàm và trả về giá trị, AllocationRecord* cũng được truyền bổ sung cùng con trỏ; một số lời gọi thư viện chuẩn cụ thể sẽ được thay bằng hàm chuyên dụng của Fil-C
    • Các lời gọi malloc và free được chuyển thành filc_malloc, filc_free
    • Ví dụ, p1 = malloc(x); free(p1); trở thành {p1, p1ar} = filc_malloc(x); filc_free(p1, p1ar);
  • filc_malloc không chỉ cấp phát một vùng nhớ được yêu cầu mà thực hiện ba lần cấp phát
    • Cấp phát đối tượng AllocationRecord
    • Cấp phát visible_bytes cho dữ liệu thực
    • Cấp phát invisible_bytes bằng calloc để lưu siêu dữ liệu vô hình
    • AllocationRecord gồm các trường visible_bytes, invisible_bytes, length

Dereference và kiểm tra biên

  • Khi dereference con trỏ, dùng AllocationRecord* đi kèm để thực hiện kiểm tra biên
    • Kiểm tra siêu dữ liệu con trỏ có khác NULL hay không
    • Tính chênh lệch giữa vị trí con trỏ hiện tại và địa chỉ bắt đầu của visible_bytes
    • Kiểm tra offset có nhỏ hơn tổng chiều dài hay không
    • Kiểm tra phần chiều dài còn lại có đủ cho kích thước đối tượng bị dereference hay không
  • Cả đọc lẫn ghi đều áp dụng cùng quy trình kiểm tra
    • Trước x = *p1 cũng thực hiện kiểm tra
    • Trước *p2 = x cũng thực hiện kiểm tra cùng dạng
  • Cấu trúc này ngăn chặn việc truy cập vượt ra ngoài phạm vi cấp phát của đối tượng mà con trỏ đang trỏ tới

Con trỏ trong heap và invisible_bytes

  • Các con trỏ được lưu trong bộ nhớ heap không thể được compiler quản lý bằng biến riêng như biến cục bộ, nên dùng invisible_bytes
    • Nếu tại vị trí visible_bytes + i có một con trỏ, thì AllocationRecord* tương ứng sẽ được lưu tại vị trí invisible_bytes + i
    • Tức là invisible_bytes hoạt động như một mảng có kiểu phần tử là AllocationRecord*
  • Khi đọc hoặc ghi giá trị con trỏ từ bộ nhớ, ngoài kiểm tra biên thông thường còn thêm kiểm tra căn chỉnh
    • Kiểm tra offset i có là bội số của sizeof(AllocationRecord*) hay không
    • Chỉ khi điều kiện này đúng mới có thể truy cập invisible_bytes an toàn như mảng AllocationRecord**
  • Khi load con trỏ, siêu dữ liệu cũng được load cùng với con trỏ dữ liệu
    • p2 = *p1 sẽ được thêm p2ar = *(AllocationRecord**)(p1ar->invisible_bytes + i) sau p2 = *p1
  • Khi store con trỏ, không chỉ giá trị con trỏ mà cả siêu dữ liệu tương ứng cũng được lưu lại
    • *p1 = p2 sau khi lưu dữ liệu thực sẽ thực hiện *(AllocationRecord**)(p1ar->invisible_bytes + i) = p2ar

filc_free và bộ gom rác

  • filc_free khi con trỏ khác NULL sẽ kiểm tra tính khớp với AllocationRecord rồi chỉ giải phóng hai vùng nhớ
    • Kiểm tra par != NULL
    • Kiểm tra p == par->visible_bytes
    • Giải phóng visible_bytes và invisible_bytes
    • Sau đó đặt visible_bytes, invisible_bytes thành NULL, còn length thành 0
  • Dù filc_malloc cấp phát ba đối tượng, filc_free không giải phóng chính đối tượng AllocationRecord
    • Phần khác biệt này do bộ gom rác xử lý
  • Trong mô hình đơn giản, GC stop-the-world là đủ; Fil-C thực tế dùng bộ thu gom song song, đồng thời, tăng dần
    • GC lần theo các đối tượng AllocationRecord
    • Các AllocationRecord không còn reachable sẽ được đưa vào diện giải phóng
  • GC còn thực hiện thêm hai công việc
    • Khi giải phóng AllocationRecord không còn reachable thì gọi filc_free
    • Mọi con trỏ trỏ tới AllocationRecord có length bằng 0 sẽ được đổi sang một AllocationRecord chuẩn duy nhất có độ dài 0
  • Nhờ cách này, kể cả không gọi free thì cũng không dẫn đến rò rỉ bộ nhớ
    • GC sẽ tự động giải phóng
    • Tuy vậy, gọi free vẫn cho phép giải phóng bộ nhớ sớm hơn so với chờ GC
  • Sau free, AllocationRecord tương ứng cuối cùng sẽ trở thành không còn reachable và có thể được dọn dẹp về sau

Địa chỉ biến cục bộ thoát ra ngoài và nâng lên heap

  • Khi có GC, phạm vi có thể xử lý an toàn địa chỉ biến cục bộ được mở rộng
    • Nếu địa chỉ của biến cục bộ đã bị lấy, và compiler không thể chứng minh rằng địa chỉ đó không thoát ra ngoài vòng đời của biến, thì biến sẽ được nâng lên thành cấp phát trên heap
  • Những biến cục bộ kiểu này được cấp phát bằng malloc thay vì stack
    • Không cần chèn riêng lệnh free tương ứng
    • GC sẽ đảm nhiệm việc thu gom

Phiên bản memmove của Fil-C

  • memmove trong thư viện chuẩn C xử lý bộ nhớ tùy ý, nên compiler không thể biết bên trong có con trỏ hay không
  • Để xử lý điều này, áp dụng heuristic
    • Các con trỏ trong vùng nhớ tùy ý phải nằm trọn vẹn trong phạm vi vùng nhớ đó
    • Con trỏ phải được căn chỉnh đúng
  • Vì quy tắc này, ngay cả khi cùng di chuyển 8 byte vẫn có thể có khác biệt trong hành vi
    • Nếu memmove một khối 8 byte đã căn chỉnh trong một lần, thì phần invisible_bytes tương ứng cũng được di chuyển theo
    • Nếu chia thành 8 lần memmove, mỗi lần 1 byte, thì invisible_bytes sẽ không di chuyển

Độ phức tạp bổ sung trong triển khai thực tế

  • Luồng

    • Tính đồng thời làm tăng độ phức tạp của GC
    • filc_free không thể giải phóng bộ nhớ ngay lập tức
      • Vì có thể tồn tại race condition giữa luồng đang giải phóng và luồng khác đang truy cập cùng vùng nhớ
    • Các phép toán nguyên tử trên con trỏ cũng cần xử lý bổ sung
      • Việc viết lại cơ bản biến load/store con trỏ thành hai lần load/store nên làm mất tính nguyên tử

  • Con trỏ hàm

    • Siêu dữ liệu bổ sung trong AllocationRecord đánh dấu visible_bytes không phải dữ liệu thông thường mà là con trỏ tới mã thực thi
    • Khi gọi qua con trỏ hàm p1, cần kiểm tra p1 == p1ar->visible_bytes và đồng thời kiểm tra p1ar có đại diện cho con trỏ hàm hay không
    • Để ngăn tấn công nhầm lẫn kiểu trên con trỏ hàm, còn cần xác minh type signature ở ABI gọi hàm
    • Một cách là làm cho mọi hàm đều có cùng một type signature
      • Xử lý như việc gói toàn bộ tham số vào một struct và truyền qua bộ nhớ
      • Ở biên ABI, mỗi hàm sẽ chỉ nhận một AllocationRecord duy nhất tương ứng với struct đó

  • Tối ưu sử dụng bộ nhớ

    • Có thể cân nhắc để filc_malloc không cấp phát invisible_bytes ngay mà trì hoãn tới khi cần
    • Cũng có thể cân nhắc đặt AllocationRecord và visible_bytes chung trong một lần cấp phát
    • Nếu malloc nền tảng gắn siêu dữ liệu ở phần đầu mỗi vùng cấp phát, thì cũng có thể đưa siêu dữ liệu đó vào AllocationRecord

  • Tối ưu hiệu năng

    • Tính an toàn bộ nhớ của Fil-C đi kèm chi phí hiệu năng
    • Vẫn còn dư địa áp dụng nhiều kỹ thuật để lấy lại một phần hiệu năng đã mất

Khi nào dùng Fil-C

  • Có thể dùng khi mã C/C++ quy mô lớn trông như vẫn chạy được nhưng chưa có kiểm chứng an toàn bộ nhớ, và có thể chấp nhận việc đưa vào GC cùng suy giảm hiệu năng lớn để đổi lấy an toàn bộ nhớ
    • Bài viết nhắc tới khả năng đây có thể là biện pháp tạm thời trước khi viết lại bằng Java, Go hoặc Rust
  • Cũng có thể chạy Fil-C với mục đích phát hiện lỗi bộ nhớ như ASan
    • Có thể chạy mã C/C++ dưới Fil-C để kiểm tra lỗi bộ nhớ
  • Với các ngôn ngữ mà ngôn ngữ dùng lúc biên dịch và lúc chạy là một, và có độ an toàn mạnh ở thời điểm biên dịch, thì còn có thể dùng cho đánh giá an toàn ở compile time
    • Ví dụ được nhắc tới là Zig
    • Dù đánh giá runtime có thể không an toàn, đánh giá compile time vẫn có thể dùng cấu hình Fil-C
  • Điều này cũng có ý nghĩa như một ví dụ hệ thống cụ thể khi bàn về pointer provenance
    • Bài viết nêu câu hỏi liệu có thể tối ưu if (p1 == p2) { f(p1); } thành if (p1 == p2) { f(p2); } khi p1 và p2 cùng kiểu hay không
    • Trong Fil-C, do AllocationRecord* truyền vào f là khác nhau nên câu trả lời được nêu rõ là không thể
    • Ở điểm này, Fil-C đóng vai trò như một ví dụ hệ thống cụ thể có pointer provenance

Bài viết liên quan

1 bình luận

 
GN⁺ 4 ngày trước
Ý kiến trên Hacker News
  • Có vẻ sẽ là một thử nghiệm khá thú vị nếu gắn invisicaps vào những thứ như chibicc hay slimcc
    Cũng còn chỗ để thử nghiệm counting tham chiếu hoặc các biến thể của invisible capability system, và tôi nghĩ cũng có thể tiết kiệm bộ nhớ đổi lại một chút chi phí gián tiếp tham chiếu
  • Tôi đã tạo filc-bazel-template và đóng gói nó thành Bazel target
    Hy vọng điều này sẽ hữu ích cho những ai muốn dùng cả hai cùng nhau để tạo hermetic builds
  • Tôi không hiểu rõ câu này có nghĩa là gì
    Upon freeing an unreachable AllocationRecord, call filc_free on it.
    Theo tôi, ý định ở đây có vẻ là phải giải phóng trước phần bộ nhớ mà các trường visible_bytes và invisible_bytes đang trỏ tới rồi mới giải phóng AR không còn khả năng truy cập
  • Tôi cảm thấy Fil-C là một trong những dự án bị đánh giá thấp nhất mà tôi từng thấy
    So với câu “rewrite it in Rust” vì an toàn, việc có thể biên dịch các chương trình C hiện có để trở nên hoàn toàn an toàn bộ nhớ nghe còn thú vị hơn nhiều
    • Theo tôi thì cần nhìn cùng lúc vài điểm
      Thứ nhất, Fil-C chậm hơn và nặng hơn. Nếu điều đó chấp nhận được thì cũng có thể nói rằng trong 10 năm qua lẽ ra người ta đã nên chuyển sang Java hay C# trước Rust
      Thứ hai, rốt cuộc vẫn là đang dùng C. Điều đó ổn cho việc bảo trì mã nguồn cũ, nhưng nếu phải viết nhiều mã mới thì tôi thấy Rust dễ chịu hơn nhiều
      Thứ ba, Fil-C là an toàn lúc chạy, còn Rust có thể biểu đạt một phần ở thời điểm biên dịch. Xa hơn nữa, các ngôn ngữ như WUFFS còn cố chứng minh tính an toàn ở giai đoạn biên dịch mà không cần check lúc chạy, nên khác ở chỗ mã có thể sai về mặt logic nhưng vẫn ngăn được crash hay thực thi mã tùy ý
    • Tôi không nghĩ nó bị đánh giá thấp ở đây. Đã có khá nhiều thảo luận liên quan rồi
      Đã có các thread như 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
    • Theo tôi, giới hạn cốt lõi của Fil-C là nó là runtime memory safety
      Bạn vẫn có thể viết mã không an toàn bộ nhớ, chỉ là giờ kết quả của nó sẽ gần với một vụ crash chắc chắn hơn là một lỗ hổng
      Nếu bạn xây thứ như web API nhận đầu vào không đáng tin cậy, thì kiểu vấn đề này rốt cuộc vẫn có thể dẫn đến denial-of-service, nên tuy tốt hơn nhưng khó mà nói là đã đủ tốt
      Tôi không có ý hạ thấp bản thân công việc của Fil-C, chỉ là tôi thấy cách tiếp cận ở runtime có những giới hạn rất rõ
    • Cảm ơn vì đã quan tâm
      Nhưng nói công bằng thì Fil-C chậm hơn Rust khá nhiều, và cũng dùng nhiều bộ nhớ hơn
      Bù lại, Fil-C hỗ trợ safe dynamic linking và ở vài khía cạnh thậm chí có thể nói là an toàn nghiêm ngặt hơn Rust
      Rốt cuộc đây là trade-off, nên mỗi người cứ chọn theo tình huống của mình
    • Theo cảm giác của tôi, không mấy khi thấy lập trình viên C/C++ sáng mắt lên khi nghe rằng họ có thể gắn garbage collector vào chương trình của mình
      Vì thế nên dù ý tưởng này thú vị về mặt kỹ thuật, về mặt cảm xúc lại có vẻ không dễ được đón nhận
  • Theo tôi thì Fil-C không an toàn bộ nhớ trong tình huống data race
    Giá trị capability và pointer có thể bị xé trong lúc gán, nên nếu luồng xen kẽ theo cách xấu thì có thể truy cập đối tượng bằng con trỏ sai và gây ra hành vi sai lệch tùy ý
    Bản thân giới hạn này thì tôi chấp nhận được, nhưng điều đáng tiếc là bầu không khí mà ngay cả những người ủng hộ cũng mạnh tay công kích những ai chỉ ra vấn đề đó
    • Theo tôi biết thì phần đó đang được xử lý bằng atomic ops
      Tiếc là đó cũng là một trong những nguyên nhân lớn gây ra overhead
  • Theo tôi thì đây rốt cuộc chỉ là một biến thể khác của họ kỹ thuật fat pointers
    Những cách làm kiểu này đã nhiều lần được triển khai rồi bị loại bỏ vì hoặc không đảm bảo đủ về bảo mật, hoặc khó vượt qua các non-fat ABI boundaries, hoặc overhead quá lớn
    • Nhưng dạo gần đây lại đang có xu hướng phần cứng trực tiếp hỗ trợ fat pointers, nên có lẽ cũng chưa hẳn là bị bác bỏ quá sớm
      Hơn nữa, tôi nghĩ filc cũng không thể được giải thích chỉ bằng fat pointer đơn thuần
    • Tôi nghĩ cũng cần nhìn thêm thực tế là nhiều nền tảng hiện đã cung cấp hardware memory tagging