Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

make Debug and ReleaseSafe modes fully safe #2301

Open
andrewrk opened this issue Apr 18, 2019 · 18 comments
Open

make Debug and ReleaseSafe modes fully safe #2301

andrewrk opened this issue Apr 18, 2019 · 18 comments

Comments

@andrewrk
Copy link
Member

@andrewrk andrewrk commented Apr 18, 2019

It's always going to be possible to do unsafe things in Zig, because we have inline assembly, @intToPtr, and ability to call extern functions with the wrong ABI.

But what if we could eliminate everything else? What if, after enumerating all kinds of undefined behavior (See #1966), we could make all of them safety-checked, with only some obvious exceptions such as inline assembly?

  • even @intToPtr could look at the type it was casting to and make sure it is correct, somehow?
  • runtime safety for pointer lifetimes? can we solve use-after-free? This is the big one.
  • try to solve everything on the list turned up by #1966.

This might turn out to be impossible or impractical, but it's worth investigating.

If we could reduce the unchecked undefined behavior surface to a minimum level, there could be auditing/linting tools to point out where unsafety lies in zig software. It would be possible to say something like, "Debug and ReleaseSafe builds of Zig code are safe (in that they crash rather than have undefined behavior), except for inline assembly and extern function ABI mismatch", or some short list of exceptions.

If the cost of these protections is high, that's what we have @setRuntimeSafety for (see #978).

It would be reasonable for these protections to depend on OS-specific behavior, and to be unavailable on some targets, such as freestanding.

@andrewrk andrewrk added this to the 0.6.0 milestone Apr 18, 2019
@andrewrk
Copy link
Member Author

@andrewrk andrewrk commented Apr 30, 2019

Interestingly, this may be related to #130. One current area of unsafety is when you use struct embedding and @fieldParentPtr with an enum telling which kind of type something is with a @ptrCast. If you mismatch ids and types, boom. Potentially the interface/vtable/oop feature, if any, that ends up coming out of #130 could solve this safety issue. Or maybe there could be a more general solution.

@ghost
Copy link

@ghost ghost commented Aug 27, 2019

any improvement?

@nmeum
Copy link
Contributor

@nmeum nmeum commented Apr 22, 2020

IMHO the important thing to get right in regards to safety is memory safety. Existing publications on this topic often make a distinction between spatial and temporal memory safety, e.g. [1]:

Memory safety has two aspects. Temporal safety is ensured when memory is never used after it is freed. Spatial safety is ensured when any pointer dereference is always within the memory allocated to that pointer.

As it stands currently, I think Zig offers neither spatial nor temporal memory safety. Haven't really used the language much yet but it seems to me that [*]T pointer types allow spatial errors as they do not have bounds information associated with them. Issues regarding temporal memory safety have already been mentioned in this issue (use-after-free). I also believe that temporal memory safety is harder to get right. The obvious solution is garbage collection though that would make Zig unusable on embedded devices. Alternatives include reference counting or Rust-like borrow checking. There is a nice write-up by the person behind the Lobster programming language which briefly discusses the different techniques and describes how the issue is addressed in Lobster.

@andrewrk andrewrk removed this from the 0.7.0 milestone Oct 9, 2020
@andrewrk andrewrk added this to the 0.8.0 milestone Oct 9, 2020
@ngrilly
Copy link

@ngrilly ngrilly commented Mar 16, 2021

Curious about what could be the strategy to make Zig safe against use-after-free of a local function stack variable? Do you think it's possible through static analysis or by crashing at runtime in Debug and ReleaseSafe modes?

@matu3ba
Copy link
Contributor

@matu3ba matu3ba commented Mar 23, 2021

Latest relevant blog post summary by scattered thoughts:

issue c zig (release-safe) rust (release)
out-of-bounds heap read/write none runtime runtime
null pointer dereference none runtime⁰ runtime⁰
type confusion none runtime, partial¹ runtime²
integer overflow none runtime runtime³
use after free none none⁴ compile time
double free none none⁴ compile time
invalid stack read/write none none compile time
uninitialized memory none none compile time
data race none none compile time
  1. optional types
  2. tagged unions, doesn't protect against holding a pointer to value while changing tag
  3. tagged unions
  4. not by default, but available via compiler setting or by linting against unchecked arithmetic
  5. mitigated by "the basic building block of heap allocation, page_allocator, uses a global, atomic, monotonically increasing address hint to mmap, ensuring that virtual address pages are not reused until the entire virtual address space has been exhausted. In practice, this is a very long time for 64-bit applications. The standard library GeneralPurposeAllocator in safe build modes follows a similar strategy for large allocations and for small allocations, does not re-use slots. Similarly, an ArenaAllocator backed by page_allocator does not re-use any virtual addresses." https://lobste.rs/s/v5y4jb/how_safe_is_zig#c_vddk9j

My thoughts
Borrow checking requires fixing the drop order aka RAII, because free cant be borrow-checked (unless one maps and proves the complete program logically): https://users.rust-lang.org/t/how-drop-clear-memory/26388/6
If the drop order is not fixed wrt to allocation order, the borrow checker cant rely on which pointers to memory are valid and which are not. It would need to check all possible combinations how memory can be allocated over the control-flow to check all paths that free (sic).

I realized this after I tried to understand free (called drop in Rust).
Here is how Polonius works: https://nikomatsakis.github.io/rust-belt-rust-2019/#98

Since we would need to require 1.lifetime annotations on functions and types as 2.parseable comments, 3.no union(type compression): Is it feasible to separate a program into memory checked and unchecked parts?

@matu3ba
Copy link
Contributor

@matu3ba matu3ba commented Mar 23, 2021

Sketch of borrow checking (BC). I dont know yet, if and where I did flawed assumptions. Will probably sleep a few nights overthinking it. Based on Nikos presentation on Polonius.

(I think) The decision for or against datafrog is motivated by

  1. finding and accessing time of each scope block (likely one or two hashsets) that defines (1.variables, 2.lifetime rules, 3. tree that describes relation to other variables).
  2. resolving loop relations on creating the relation tree of types => likely space vs execution time tradeoff.
  3. Keeping code simple to have a sound implementation.

On applying BC (we simplify allocation here):

  1. Global scope variables etc must be obtained and the according tree defining their relations filled. Loops in the relation tree must be detected/handled (how costly with inference rules?) to prevent getting too slow/error out.
  2. For each function:
    The Control Flow Automata(CFA) must be constructed, which requires forward traversing all functions (on demand).
    The CFA of each function (edges corresponding to statements) must be traversed 2 times:
  • backwards to annotate lifetimes to the variables
  • forwards to conduct BC analysis

The BC analysis then must abstract over loops to generate rules and figure out, if any function evaluation resolves to satisfying or unsatisfying lifetime constraints (1.order of how memory is allocated or deallocated, 2.pointer validity with lifetime rules).
Rust solves 1. by using RAII and zig could enforce defer deinit and defer free to the respecting init call. We can also easily generate those rules via lifetime annotations on the functions.

The difficult part is 2: Pointer allow arbitrary indirection complexity and looking up the address the pointer points to crushes cache-locality relatively fast, because we must track the possible indirections over the whole lifetime of the program with annotating and resolving the lifetime rules.
Hence it becomes very fast easier to use a database/key value store for it, which boils down to the Rust approach.

BC Fundamental rule
An memory slice(MS) is defined by base address + bytelength and maps to continuous memory.
We must have in every scope either

  1. exactly one non-const pointer to a MS (mutable borrow of variable) (that is used later)
  2. arbitrary many const pointer to a MS (shared borrow of variable) (that is used later)

BC principles

  1. Loans define the relation of pointers p to variable x (and vice versa)
    var x: u16 = 100; //MS assume base address 0x400, len 2 (byte)
    // ignore for now that p1 and p2 (and x) are not live (dead variable optimisation)

    var p1: *const u16 = &x; //Rust: let p1 = &x //Loan1(L1): p1 borrows x shared, so x can not be written unless p1 goes of out of scope

    var p2: *u16 = &x; //Rust: let p1 = mut &x //Loan2(L2): p2 borrows x mutable, so only p2 can write x. x can be used as usual.
  1. Violating loans
    var x: u16 = 22;
    var p1: *const u16 = &x; //L1: p1 borrows x shared
    x += 1; //error: x is modified, but was borrowed shared => lookup (what subparts) are shared in which mode
    print("y: {}", .{p1.*}); //make sure p1 lives  (see below)
  1. Live variables
    var x: u8 = 1;
    //x is dead here, because it is reassigned before usage
    x = 2;
    //x is live here, because there is no reassignment before usage
    //common static analysis method: Live Variable Analysis (traverse CFA backwarsd)
    print("x: {}", .{x});
  1. Live loan
    const Foo = struct { x: u8 = 1, bar: u8 = 2 };
    //TODO: make it properly
    var foo:Foo = Foo{};
    var x:  = &foo.bar; //L1: x borrows foo mutable
    var y = &foo; //L1: error, can not borrow foo[0,bar.end] => foo[bar.start,bar.end] mutable borrowed

    //y gets used => loans L1 and L2 live
    print("z: {}", .{y.*});

APPENDUM
What I think is worth investigating is in Polonius/Rust borrow checker a way to tell the solver what values to drop during analysis (once they become not needed anymore).

@Hadron67
Copy link
Contributor

@Hadron67 Hadron67 commented Apr 3, 2021

  1. Live loan
    const Foo = struct { x: u8 = 1, bar: u8 = 2 };
    //TODO: make it properly
    var foo:Foo = Foo{};
    var x:  = &foo.bar; //L1: x borrows foo mutable
    var y = &foo; //L1: error, can not borrow foo[0,bar.end] => foo[bar.start,bar.end] mutable borrowed

    //y gets used => loans L1 and L2 live
    print("z: {}", .{y.*});

Since Rust borrow checker does not work for self referential types, I doubt if BC of this type is feasible? For example, is the following code disallowed?

const Foo = struct { next: ?*Foo, };
var foo: Foo = .{ .next = null };
foo.next = &foo;// error, foo is already borrowed mutable?

@matu3ba
Copy link
Contributor

@matu3ba matu3ba commented Apr 3, 2021

@Hadron67

This is what Rust has Pin for.
So another referencing Pin types should have the same lifetimes + must not to be moved around in memory after getting placed (by the programmer): https://rust-lang.github.io/async-book/04_pinning/01_chapter.html

So in theory this should be possible, but in practice one would need to compute a compile-time derivable memory layout over the recursive structures. This works fine for lists, smaller/fixed-layout trees and simple stuff, but likely does not work anymore for more complex structures.

(The idea is that you can only set null-pointer to non-null and non-null pointer must not be modified until you clean up recursively the structure.)

By the way, your simplified example is currently broken on master:

const std = @import("std");
const print = std.debug.print;
pub fn main() void {
    const Foo = struct { t1: u8, next: ?*Foo }; //without type t1 zls or zig.vim immediately complains
    var foo: Foo = .{ .t1 = 1, .next = null };
    foo.next = &foo;
}

@matu3ba
Copy link
Contributor

@matu3ba matu3ba commented Apr 6, 2021

Another interesting approach is Wuffs, which can be significantly fast.
"However, unlike hand-written C, Wuffs the Language is safe with respect to buffer overflows, integer arithmetic overflows and null pointer dereferences."

They can only do this, because they require that heap memory owned by pointers does not get fragmented. So programmers must manage pointer offsets to each heap structure themself. Hence one never gets potential pointer soup (pointers pointing to subparts and pointing to other things), which Rust resolves with (the costly) pointer lifetime checking.

So memory handling is relative static and simple, because no subpointers or substructures to same memory region can be created.

Also loop invariants etc must all be annotated, so one does basically proof all invariants manually and gets only the compiler confirmation. So overall this should be fine for anything simpler in terms of memory layout.

@Hadron67
Copy link
Contributor

@Hadron67 Hadron67 commented Apr 7, 2021

@matu3ba
Actually the big problem with Rust-style borrow checker and lifetime analyse is they can only handle affine substructural type system, such as simple structs and trees. Wuffs also falls into this category of types that's why it's simple, fast, and easy to analyse. However, when come to non-linear types the analysis become much harder and is very likely impossible to be carried out in general. Example of such types including self referential types, doubly linked lists, graphs, etc. Unfortunately many OS level data structures belong to this type. Dealing with such types in Rust would require unsafe, such as using Pin for self referential types, and Rc<RefCell<T>> for shared mutable objects (Rc and RefCell implementation all contains unsafe block).

So instead, in zig, except some really simple cases such as returning pointer to a stack-allocated variable, I think we should keep the language simple (I don't want to fight with BC even in zig hahaha, and we don't have "unsafe zig") and just do the safety checks at runtime (Debug and ReleaseSafe modes only of course), raise error immediately when a memory access violation happens. This makes the problem much easier to spot than in c or c++.

For more information about the problem with Rust and ownership model, I recommend this article.

(maybe we should consider moving to discussions?)

@matu3ba
Copy link
Contributor

@matu3ba matu3ba commented Apr 8, 2021

@Hadron67 thanks for the great article and summary (though Pin does require unsafe due to move semantics in c++/Rust, which c and zig to my knowledge does not have).

https://zigforum.org/ would be a candidate.

@oconnor663
Copy link

@oconnor663 oconnor663 commented May 3, 2021

How might future safety checks handle lifetime issues involving allocating containers like ArrayList? Here are a couple of proof-of-concept examples, which run without errors in Debug mode currently, but where Valgrind detects invalid reads and writes. (Of course the fact that these examples trigger UB is unsurpsing and well documented, and the question is just how to catch them in Debug mode. Also apologies for unidiomatic code here. I'm totally new to Zig.)

Example 1: reallocation invalidating a pointer

const std = @import("std");

pub fn main() anyerror!void {
    // Make an ArrayList with one element.
    var list = std.ArrayList(i32).init(std.heap.c_allocator);
    defer list.deinit();
    try list.append(0);

    // Take a pointer to that element.
    const ptr = &list.items[0];

    // Add some more elements, to force a reallocation.
    var i: usize = 0;
    while (i < 100) {
        try list.append(0);
        i += 1;
    }

    // BUG: Reallocation has invalidated our pointer, and dereferencing it is
    // now a use-after-free.
    std.debug.print("ptr.* = {}\n", .{ptr.*});
}

Example 2: copying leading to a double free

const std = @import("std");

pub fn main() anyerror!void {
    // Make an ArrayList with one element.
    var list1 = std.ArrayList(i32).init(std.heap.c_allocator);
    defer list1.deinit();
    try list1.append(0);

    {
        // Make another ArrayList with a shorter lifetime.
        var list2 = std.ArrayList(i32).init(std.heap.c_allocator);
        defer list2.deinit();

        // Overwrite list2 with list1. This assignment is a shallow copy.
        list2 = list1;
    }

    // BUG: list2.deinit() has freed list1's heap storage, so reading list1 is
    // now a use-after-free, and list1.deinit() will be a double free.
    std.debug.print("list1 = [{}]\n", .{list1.items[0]});
}

@pfgithub
Copy link
Contributor

@pfgithub pfgithub commented May 4, 2021

@oconnor0 The GeneralPurposeAllocator catches these issues in most cases by avoiding reusing memory addresses for as long as possible.

const std = @import("std");

pub fn main() anyerror!void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer std.testing.expect(!gpa.deinit());
    const alloc = &gpa.allocator;
    // Make an ArrayList with one element.
    var list = std.ArrayList(i32).init(alloc);
    defer list.deinit();
    try list.append(0);

    // Take a pointer to that element.
    const ptr = &list.items[0];

    // Add some more elements, to force a reallocation.
    var i: usize = 0;
    while (i < 100) {
        try list.append(0);
        i += 1;
    }

    // BUG: Reallocation has invalidated our pointer, and dereferencing it is
    // now a use-after-free.
    std.debug.print("ptr.* = {}\n", .{ptr.*});
}
Segmentation fault at address 0x7ff11876b000
/home/pfg/Dev/Node/temp/generated/c2eadb992fd9e98a212b0aa4ca835207/tmp/test.zig:24:42: 0x229e09 in main (test)
    std.debug.print("ptr.* = {}\n", .{ptr.*});
                                         ^
/home/pfg/Apps/zig/zig-linux-x86_64-0.8.0-dev.2082+e9e91b4ed/lib/std/start.zig:420:37: 0x22256a in std.start.callMain (test)
            const result = root.main() catch |err| {
                                    ^
/home/pfg/Apps/zig/zig-linux-x86_64-0.8.0-dev.2082+e9e91b4ed/lib/std/start.zig:362:12: 0x20653e in std.start.callMainWithArgs (test)
    return @call(.{ .modifier = .always_inline }, callMain, .{});
           ^
/home/pfg/Apps/zig/zig-linux-x86_64-0.8.0-dev.2082+e9e91b4ed/lib/std/start.zig:316:17: 0x2057c9 in std.start.posixCallMainAndExit (test)
    std.os.exit(@call(.{ .modifier = .always_inline }, callMainWithArgs, .{ argc, argv, envp }));
                ^
/home/pfg/Apps/zig/zig-linux-x86_64-0.8.0-dev.2082+e9e91b4ed/lib/std/start.zig:238:5: 0x2056f2 in std.start._start (test)
    @call(.{ .modifier = .never_inline }, posixCallMainAndExit, .{});
    ^
fish: Job 1, 'zig run test.zig' terminated by signal SIGABRT (Abort)

,

const std = @import("std");

pub fn main() anyerror!void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer std.testing.expect(!gpa.deinit());
    const alloc = &gpa.allocator;

    // Make an ArrayList with one element.
    var list1 = std.ArrayList(i32).init(alloc);
    defer list1.deinit();
    try list1.append(0);

    {
        // Make another ArrayList with a shorter lifetime.
        var list2 = std.ArrayList(i32).init(alloc);
        defer list2.deinit();

        // Overwrite list2 with list1. This assignment is a shallow copy.
        list2 = list1;
    }

    // BUG: list2.deinit() has freed list1's heap storage, so reading list1 is
    // now a use-after-free, and list1.deinit() will be a double free.
    std.debug.print("list1 = [{}]\n", .{list1.items[0]});
}
Segmentation fault at address 0x7f28a6d18000
/home/pfg/Dev/Node/temp/generated/c2eadb992fd9e98a212b0aa4ca835207/tmp/test.zig:24:52: 0x229dcd in main (test)
    std.debug.print("list1 = [{}]\n", .{list1.items[0]});
                                                   ^
/home/pfg/Apps/zig/zig-linux-x86_64-0.8.0-dev.2082+e9e91b4ed/lib/std/start.zig:420:37: 0x22256a in std.start.callMain (test)
            const result = root.main() catch |err| {
                                    ^
/home/pfg/Apps/zig/zig-linux-x86_64-0.8.0-dev.2082+e9e91b4ed/lib/std/start.zig:362:12: 0x20653e in std.start.callMainWithArgs (test)
    return @call(.{ .modifier = .always_inline }, callMain, .{});
           ^
/home/pfg/Apps/zig/zig-linux-x86_64-0.8.0-dev.2082+e9e91b4ed/lib/std/start.zig:316:17: 0x2057c9 in std.start.posixCallMainAndExit (test)
    std.os.exit(@call(.{ .modifier = .always_inline }, callMainWithArgs, .{ argc, argv, envp }));
                ^
/home/pfg/Apps/zig/zig-linux-x86_64-0.8.0-dev.2082+e9e91b4ed/lib/std/start.zig:238:5: 0x2056f2 in std.start._start (test)
    @call(.{ .modifier = .never_inline }, posixCallMainAndExit, .{});
    ^
fish: Job 1, 'zig run test.zig' terminated by signal SIGABRT (Abort)

The c allocator will likely never be able to be fully safe, but there might be things that can be done.

@oconnor663
Copy link

@oconnor663 oconnor663 commented May 4, 2021

@pfgithub a couple questions about the GeneralPurposeAllocator if you have time: If some objects in a page are still alive, can it catch use-after-free bugs related to freed objects in the same page? Or is it only able to do that once all the objects in a page have been freed? Also, could it ever be possible to implicitly switch an application to the GeneralPurposeAllocator (or something that behaves like it) in Debug/ReleaseSafe mode, or will that sort of thing always require explicit debugging code in the application itself?

Edit: Trying your examples just now, it looks like if I add an extra ArrayList that keeps an allocation of the same size alive until the end of main, it affects the debugging output. The first example doesn't catch the use-after-free, and exits without an error. The second example doesn't catch the use-after-free, but does panic on the double-free.

@pfgithub
Copy link
Contributor

@pfgithub pfgithub commented May 4, 2021

@oconnor0

The best places for questions like these is in one of the community spaces. I know that people in the discord are very responsive, and the irc is good as well especially for more technical questions about zig.

Also, could it ever be possible to implicitly switch an application to the GeneralPurposeAllocator (or something that behaves like it) in Debug/ReleaseSafe mode, or will that sort of thing always require explicit debugging code in the application itself?

The general purpose allocator is configurable, and the default configuration .{} automatically changes stuff in release-fast to run faster: https://github.com/ziglang/zig/blob/master/lib/std/heap/general_purpose_allocator.zig

Switching to a c allocator in release-fast instead of using zig's release-fast allocator does require explicit application code.

@matu3ba
Copy link
Contributor

@matu3ba matu3ba commented May 11, 2021

"MemorySanitizer: fast detector of uninitialized memory use in C++" by Evgeniy Stepanov and Konstantin Serebryany https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/43308.pdf

With this approach for checking UUM => 2.5x compiletime cost, 2x memory. However, this approach still includes false negatives (there can be UUM even though the check says there is none).

@andrewrk andrewrk removed this from the 0.8.0 milestone May 19, 2021
@andrewrk andrewrk added this to the 0.9.0 milestone May 19, 2021
@FlyingWombat
Copy link

@FlyingWombat FlyingWombat commented Sep 19, 2021

Would Zig's safety features also be applied to C code, when using C via @cImport and zig translate-c? If so, that would be a killer feature for Zig: fully safe Zig would, by extension make C fully safe.

@hiljusti
Copy link

@hiljusti hiljusti commented Sep 20, 2021

@FlyingWombat That's an interesting idea and a great point. There's a lot of interest in C and making it safer. If you have some concrete ideas, they might be worth their own issue. I think this will go far outside the scope of Zig safety.

I don't think that a simple translation of arbitrary C source code to Zig could be guaranteed to generate safe code. C source code can be perfectly valid C and do something wildly unsafe. E.g. create a null pointer and immediately dereference it. Far more subtle unsafe code can exist (that's part of why languages like Zig are a breath of fresh air) so I think an idea of C -> Zig safety improvements might be worth their own discussion.

I do think translating from C to Zig would surface a number of unsafe conditions, so if you have C source with some classes of bugs, you could get Zig compiler warnings for them. You'd also get some subtle things more provably safe, for free. (E.g. integer overflow)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Safety
  
To do
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
9 participants