search

microsoft / qsharp-runtime

Runtime components for Q#
https://docs.microsoft.com/quantum
MIT License
285 stars 93 forks source link

QIR: Result reference counting incorrectly allows for use after free, multiple release #933

Open swernli opened 2 years ago

swernli commented 2 years ago

Describe the bug

The reference counting logic for the opaque %Result* type in the QIR Runtime allows for a given result to be released any number of times or used after release. This can cause failures in code that implements the Runtime C++ API that expects the reference count semantics to be obeyed.

To Reproduce

(Note: a bug in the Q# QIR Generation allowed use after free, tracked by https://github.com/microsoft/qsharp-compiler/issues/1350, but this repro will not rely on that bug.) Author QIR (or C/C++ that calls the QIR Runtime API) that performs this sequence:

%r = call %Result* @Microsoft__Quantum__Intrinsic__M__body(%Qubit* %q)
call void @__quantum__rt__result_update_reference_count(%Result* %r, %i32 -1)
call void @__quantum__rt__result_update_reference_count(%Result* %r, %i32 -1)
call void @__quantum__rt__result_update_reference_count(%Result* %r, %i32 -1)

By convention in the specification, %Result* returned from measurement have an initial reference count of 1, so the repeated decrement should result in a negative reference count and some kind of failure.

Expected behavior

Failure due to attempt to reach a negative reference count, or at the very least only one call to release the underlying result.

Actual behavior

The runtime does not fail, and will actually end up calling the C++ API ReleaseResult three times.

Additional context Our simulator runtime doesn't care about this incorrect behavior because each %Result* is just a Boolean value (either integer zero or integer 1), and ReleaseResult is a no-op. But for callers who use a pointer to an object then ReleaseResult getting called multiple times will cause the underlying object to get cleaned-up or freed multiple times, causing a failure at runtime.

The issue comes from this code in the QIR Runtime: https://github.com/microsoft/qsharp-runtime/blob/a22c80c962ce27be2336db93a39d243019c376f6/src/Qir/Runtime/lib/QIR/delegated.cpp#L83-#L129 Note the logic assumes that any RESULT* that hasn't been seen before must be a newly created result. This has the undesirable effect of treating every unknown result as if it had a reference count of 1 instead of a reference count of 0, and allows for multiple release. Likewise a result that was already released and should not be allowed to have it's count incremented will be treated as if it had a count of 1, leading to a total of count of 2. So code like this:

%r = call %Result* @Microsoft__Quantum__Intrinsic__M__body(%Qubit* %q)
call void @__quantum__rt__result_update_reference_count(%Result* %r, %i32 -1) ; Decrement count to zero
call void @__quantum__rt__result_update_reference_count(%Result* %r, %i32 1) ; Invalid resurrection?

will not only incorrectly execute when it should fail, it results in a reference count of 2 on the result in the allocatedResults global structure.

swernli commented 2 years ago

One thought on how this could be resolved: delegate reference counting of results to the implementers of IRuntimeDriver. While this further relies on the C++ API that restricts the options for implementers, this particular issue is already specific to them due to the use of the ReleaseResult function defined in that API. If we add an UpdateResultReferenceCount function or something similar, then we can allow the runtime driver to track those reference counts in whatever manner makes the most sense for the result implementation it uses, including ignoring it if results don't need to be reference counted.