Soundness violation with self-written futures

[eernstg]

Thanks to Sergejs for detecting this soundness violation!

Consider the following program:

void foo(int? x, Future<Never> guard) async {
  if (x == null) await guard;
  print('hello');
  print(x.isEven); // Unsound!
}

class F implements Future<Never> {
  @override
  dynamic noSuchMethod(i) async {
    i.positionalArguments[0](null);
  }
}

void main() async {
  foo(null, F());
}

This program prints 'hello' and then throws a NoSuchMethodError because it attempts to invoke isEven on the null object, using dart 2.17.0-266.5.beta, but this is a soundness violation because it implies that await guard evaluated to null in spite of the fact that the expression has static type Never. The execution does not use unsound null safety, so an expression of type Never should not yield an object.

Interestingly, the kernel transformation obtained by running the following command:

> dart2kernel n011.dart

where the example program is stored in n011.dart and dart2kernel is the following script:

#!/bin/bash --norc

SDK_PATH=$HOME/devel/dart/work/sdk
$SDK_PATH/pkg/front_end/tool/fasta compile \
  --platform=$SDK_PATH/out/ReleaseX64/vm_platform_strong.dill \
  -o ${1}{.dill,}
TMP_FILE=${1}.dill.txt
$SDK_PATH/pkg/kernel/bin/dump.dart ${1}.dill $TMP_FILE
echo "less $TMP_FILE"
less $TMP_FILE

shows that foo is translated into the following kernel code:

  static method foo(core::int? x, asy::Future<Never> guard) → void async /* fut>
    if(x == null)
      let final Never #t1 = await guard in throw new _in::ReachabilityError::•("`null` encountered as the result from expression with type `Never`.");
    core::print("hello");
    core::print(x{core::int}.{core::int::isEven}{core::bool});
  }

I do not understand how the evaluation of the let expression can complete normally. Also, it is surprising that await guard can complete normally in the first place, because that expression has static type Never.

Note that we do get the expected reachability error if the example is executed with --no-sound-null-safety.

[johnniwinther]

cc @chloestefantsova

[srawlins]

@eernstg in labeling this with area-analyzer, should analyzer's behavior change as well? Should analyzer report that the two lines after if (x == null) await guard; are dead code?

[eernstg]

dead code

That was what I was thinking, but it wouldn't be dead (x could be an int), so that label was a mistake. Gone now. Thanks!

[eernstg]

@mraleph just clarified a bunch of things. Here's a simpler example:

class F implements Future<int> {
  @override
  dynamic noSuchMethod(i) async {
    i.positionalArguments[0]('Hello, int!');
  }
}

void main() async {
  var x = await F();
  print('x: $x, of type: ${x.runtimeType}, isEven: ${x.isEven}');
  // Prints 'x: Hello, int!, of type: int, isEven: true'.
}

The underlying issue seems to be that _Future "manually" ensures the soundness of evaluating an await expression, but a self-written subtype of Future may not follow the same rules, and this gives rise to the need for a dynamic type check on the value obtained from await e in general. In order to avoid that (and in particular, to avoid the cost associated with having a dynamic type check on every await out there), it is probably necessary to give self-written futures a special treatment, e.g., in _awaitHelper, such that the thenCallback will enforce the typing properties.

[mraleph]

We have looked at this briefly with @eernstg and discovered that the underlying soundness issue is actually related to VM (or dart2js) implementation of the async rather than CFE - VM passes a very loosely typed closure to then which allows then to pass back any value to the callback. Internal Future implementation honors the contract that Future<T> would only pass subtypes of T to onValue, but this can be violated by custom subclasses:

import 'dart:async';

void foo(Future<String> f) async {
  final String result = await f;
  print(result.runtimeType);
}

class F<T> implements Future<T> {
  Future<R> then<R>(FutureOr<R> Function(T) onValue, {Function? onError}) {
    return Future.value((onValue as FutureOr<R> Function(dynamic))(10));
  }

  @override
  dynamic noSuchMethod(i) => throw 'Unimplimented';
}

void main() async {
  foo(F<String>());
}

Here we would pass int where String is expected because onValue is a actually an extremely generic callback that does no argument checking.

It seems that async implementation should use different then callbacks depending on whether we are dealing with internal Future implementations (which are known to be safe) or not and through that employ additional type checking when we are dealing with potentially unsafe futures.

/cc @alexmarkov

[eernstg]

[Edit: This is just a joke, please ignore. ;-]

So the canonical arbitrary number is 7 or 87, the canonical string is Hello, world! or at least Hello followed by something, the canonical list is [1, 2, 3], and the canonical soundness issue is "you think it's an int, but it's actually a String". Maybe we could simplify our test portfolio to ignore those other cases that nobody wants, anyway? 😀

[alexmarkov]

It seems like in order to close this loophole we should either

• cast the result of await to the expected type in async/async* functions

  Future<T> x = foo();
  T y = await x;

=>

  Future<T> x = foo();
  T y = await_impl(x) as T;

• or parameterize the implementation of await with the expected type and use that type to check the parameter of onValue callback passed to Future.then. In general case we don't know if x is a user-defined Future or not, so we probably need to always pass the expected type. Note that within the same async/async* function there can be multiple await expressions with different static types, so we will not be able to reuse the same callbacks for all of them.

  Future<T> x = foo();
  T y = await x;

=>

  Future<T> x = foo();
  T y = await_impl<T>(x);

where implementation of await can use T to provide a specialized onValue callback for Future.then. The async implementation in the VM already checks if the future is built-in at runtime, so we can create a new closure only in case of user-defined futures.

The first approach is simple and can be done in the front-end to share across implementations, but may incur significant performance and code size overheads.

The second approach probably has better performance and code size, but passing the expected static type to await still would have some negative effect on performance and code size.

I think this problem is a good example of unnecessary complexity and additional overheads caused by user-defined Future implementations, which are rarely used. We should consider deprecating user-defined futures to avoid that. /cc @lrhn

[mraleph]

@alexmarkov I think there is a third approach where we do something like this pseudo-code inside await machinery:

awaitImpl(Future x) {
  if (x is _Future) {
    // Old case: value produced by [_Future.then] is guaranteed to be a subtype of
    // static type of a variable which contained this future. No need to use 
    // tightly typed callback.
    x.then(_genericThenCallback);
  } else if (x is Future<var T>) {
    // Enforce types for custom future implementations.
    x.then((T value) => _genericThenCallback(value));
  }
}

The idea here is that we don't really need static type at the await side. Instead we could enforce a very strong constraint that an instance of Future<T> is expected to produce a subtype of T. We can derive T from the instance of the future itself instead of passing it down.

This has no code size implications at call-site, but unfortunately requires allocating closures.

I think there is a possibility to avoid that as well, by using continuation approach: we stash T and suspend PC in a separate place in the suspend state and then set suspend PC to point to a stub which type-checks the value and then redirects to actual suspend PC.

[lrhn]

A Future<T> should only provide a T. That can be seen from it's then function taking ... Function(T) callback, which cannot possibly accept anything but a T.

If we have a combination of a Future<T>.then which gets a more permissive callback, like a ... Function(Object?) and it internally tries to call it dynamically with a value which isn't actually a T, we bypass the inherent type-check. The async implementation code can only control the callback, not the future, so it should be strict and pass a ... Function(T). That will cause an extra generic type check on each call, but the alternative is to not check and be surprised when the caller gets it wrong too.

Alternatively, we can say that it's unspecified behavior what happens if a future does not follow the Future specification. (Like, calling callbacks more than once, and at odd times, etc. There should be limits to how defensively you need to code!) We still need to be sound, though, so we need to stop the error before it reaches typed code with an invalid value.

[alexmarkov]

@mraleph Deriving the expected type of value from future instance is a great idea! Note that user-defined future class might implement Future, not extend it, so we cannot query type from the type arguments vector. We would probably need to make a runtime call to search Future recursively among base classes and implemented interfaces in order to get the expected type.

On top of the runtime call allocating a new closure is not that heavy. Maybe we should prefer creating new closures instead of increasing size of SuspendState objects (memory usage) and adding more complexity to the stubs. This approach should not add any overhead to the common case of built-in futures, and only make awaiting user-defined futures slower. I'll create a CL for that.

@lrhn Yes, that's what we'll probably end up doing in the implementation. Note that providing a callback which type is specialized for every await means the implementation cannot reuse the same callback for all awaits.

[lrhn]

You could reuse the same callback and inline the type check at the point of the await instead, a place which should have access to the expected type. As long as it throws a some time before the await e completes, we shouldn't have unsound behavior.

[mraleph]

You could reuse the same callback and inline the type check at the point of the await instead, a place which should have access to the expected type.

This approach is mentioned in https://github.com/dart-lang/sdk/issues/49345#issuecomment-1169099697 but it has bad code size implications.

[eernstg]

check at the point of the await instead

What's the percentage of await e expressions where e is statically known to be an _Future? For instance, every async function is presumably guaranteed to return an _Future, not some other subtype of Future. If we can "almost always" know that await e will await an _Future then those expressions wouldn't need the cast.

The main stumbling block here would probably be that an overridden method could change this: A.foo has a body which is marked async, but the expression of type A is really a B which implements A, and B.foo returns a Future which is not a _Future.

So we probably just can't know this sufficiently frequently to make it useful.

[alexmarkov]

Fix for the VM: https://dart-review.googlesource.com/c/sdk/+/250222.

@sigmundch Both dart2js and DDC fail on the regression test (derived from https://github.com/dart-lang/sdk/issues/49345#issuecomment-1168608833) so they probably have this bug too. I'm going to approve the failures when landing the VM fix.

[alexmarkov]

Dart VM fix landed (abedfaf62a2a426d44142dc97aa342524feedf8f).

[sigmundch]

Thanks @alexmarkov!

FYI @rakudrama @nshahan

[TimWhiting]

A future related test is failing on flutter/dart master with the fpdart library, found while creating this pull request to fix mixin breaking changes to work on master. I believe I'm running with a new enough sdk to incorporate the soundness fix.

https://github.com/SandroMaglione/fpdart/pull/42

This is the test.

 test('run', () async {
      final task = Task.of(10);
      final future = task.run();
      expect(future, isA<Future<int>>());
      final r = await future;
      expect(r, 10);
 });

This is the relevant bit of Task

/// [Task] represents an asynchronous computation that yields a value of type `A` and **never fails**.
///
/// If you want to represent an asynchronous computation that may fail, see [TaskEither].
class Task<A>  {
  final Future<A> Function() _run;

  /// Build a [Task] from a function returning a [Future].
  const Task(this._run);

  /// Build a [Task] that returns `a`.
  factory Task.of(A a) => Task<A>(() async => a);

  /// Run the task and return a [Future].
  Future<A> run() => _run();
}

dart version:

dart --version
Dart SDK version: 2.18.0-263.0.dev (dev) (Thu Jul 7 10:24:22 2022 -0700) on "macos_x64"

output

00:05 +558 -1: test/src/task_test.dart: Task run [E]                                                                                                                                  
  Expected: <Instance of 'Future<int>'>
    Actual: <Instance of 'Future<dynamic>'>
     Which: is not an instance of 'Future<int>'

  package:test_api              expect
  test/src/task_test.dart 83:7  main.<fn>.<fn>

Standalone repo with just the above code, able to reproduce: https://github.com/TimWhiting/dart_fail_future

Analyzer shows the correct type when hovering over the future returned from Task.run()

[mraleph]

@TimWhiting it is a different issue, moved it into its own issue.