Roadmap for closures, fn pointers, and traits

[cdstanford]

This is a work-in-progress, discussion welcome!

A possible short-term roadmap is:

• implement UnknownCall: an additional type of unsafety that must be audited. This is used for calls to closures and calls to function pointers.
• additionally, implement UnknownTraitCall: this applies to calls to dynamic trait objects, and calls to traits in a generic context. In other words, if we call t.foo() where we don't know the exact type of t.
• for traits in a non-generic context (t.foo() where we do know the type of t), fix resolution: currently we are resolving them to the trait path, we need to resolve them to the path where the trait is implemented instead.

Longer term:

• for closures and function pointers: add closure locations to the call graph. (i) define anonymous path names for closures (ii) use type resolution to try to resolve where closures are defined. If type resolution fails, fall back on UnknownCall
• for traits: track the set of possible implementations and be smarter about delegating responsibility. David had some ideas here and said it requires changes to the policy stuff

[cdstanford]

David's proposal

The function creating a closure or function pointer is responsible to ensure not just that that function pointer is used safely within the function, but also that it is safely called in any other context outside of that function. If not, it must be marked completely unsafe during an audit.

Example:

fn return_file_reader_v1(f: &std::path::Path) -> impl Fn() -> String {
    || { std::fs::read_to_string(f).unwrap() }
}

fn return_file_reader_v2() -> impl Fn() -> String {
    |f: &std::path::Path| { std::fs::read_to_string(f).unwrap() }
}

fn return_file_reader_v3() -> fn(&Path) -> Option<String> {
    std::fs::read_to_string
}

return_file_reader_v1 is caller-checked because caller can ensure the file is safe to read from.

Unfortunately return_file_reader_v2 and return_file_reader_v3 are both unsafe (and must be audited as so!) because the caller has to be responsible that all uses of the return value are safe, and it does not have enough information to determine this. This makes our tool a conservative overapproximation and it cannot express safety even in some cases where a crate or function may be used safely.

[cdstanford]

Alternative proposal

The advantage of David's proposal is it's very simple, and easy to audit things; the disadvantage of it is that any crates which use functions like return_file_reader_v2 and return_file_reader_v3 above can't be audited as safe, so we will simply mark crates using those as inherently unsafe to use.

An alternative approach is to consider all uses of function pointers and closures to be unsafe, rather than their creation. Under this proposal, all of return_file_reader_v1, return_file_reader_v2, and return_file_reader_v3 are entirely safe! However, this means that we have to audit all locations where a fn pointer or closure is called individually, which increases the auditing burden. For example, if we have:

main() {
    let f = fn return_file_reader_v1("foo.txt");
    /* ... */
    f();
}

Under David's proposal, we don't need to audit the call to f() at all -- it's return_file_reader_v1's responsibility to make sure all calls to its returned value are safe. Under this alternate proposal, instead, return_file_reader_v1 has no local responsibility, but we have to show the call to f() as an audit location (call to a function pointer or closure - possible effects could occur). David points out this can be a fair amount of additional work -- the auditor has to go into the definition of where f is declared, find the call to return_file_reader_v1, and then check the definition of return_file_reader_v1 in turn to see if this call to this closure can be considered safe.

[cdstanford]

RFC on the above! Both of these just handle the case of fn pointers and closures, and not the case of traits.

[ranjitjhala]

I'd go with @DavidThien 's proposal -- which seems simpler. We can always do fancier things if we turn out they are needed in practice?

[cdstanford]

Actually IMO both proposals are almost equally simple to implement -- but the alternative proposal might lead to more noise during an audit. In terms of implementation, the second just means adding "unknown call to a callable type" as a first-class category of unsafe effect.

[cdstanford]

Decision for function pointers and closures

DECISION: for v0 of the tool, we're going with David's proposal.

This is because the alternate proposal seems to have serious problems! Even for very simple uses of closures, like the typical case of maps and filters over iterators. See the following example:

use std::collections::HashSet;

fn foo() -> HashSet<usize> {
    (0..100).into_iter().map(|x| { println!("{}", x); /* log to file */; x } ).collect()
}

/*
    Proposal 1 (David): function creating the closure is responsible for safety
    - we add an audit location at the creation of the closure above: |x| { ... }
    - we add an unsafe effect to the effect model called ClosureCreation
    - auditor of foo() sees ClosureCreation and decides if it's safe.

    Proposal 2 (alternate): function *calling* the closure is responsible for safety
    - foo() doesn't get audited at all
    - implementor of std::iter::Map is responsible
        - specifically in impl<B, I: Iterator, F> Iterator for Map<I, F>
          somewhere nested inside the code
          ends up being in Option::map !!!
    - we add an unsafe effect to the effect model called UnknownCall
    - auditor of std::iter::Map sees Unk
    - This is terrible!!!!!!!!!!!
*/

fn main() {
    let y = foo();
    println!("{:?}", y);
}

Updated Roadmap

Therefore, an updated roadmap for function pointers and closures is:

• add a ClosureCreation and FnPointerCreation type of unsafe effect to our effect model
• In scanner.rs, whenever a closure or function pointer is created, add this to the list of effects associated with that function that need to be audited.

Discussion for traits

We are still deciding what to do about traits, hopefully discussing tomorrow.

[cdstanford]

Closing in favor of #34 and #35