How to verify tag when type changes

[ya0guang]

Issue

I want to verify a typestate program but I'm hindered by some unexpected output. So I start with a minimal reproducible example.

When I have two structs (say A and B for example) and have a function converting from A to B. How should I maintain and propagate the tag? I checked annotations/lib.rs and found SubComponent and SuperComponent, but the output is not as what I expected. In the example below I verified the tag after executing a_to_b and has the same postcondition in a_to_b, however only the postcondition is not always satisfied.

Steps to Reproduce

// main.rs
#![cfg_attr(mirai, allow(incomplete_features), feature(generic_const_exprs))]

extern crate mirai_annotations;

use mirai_annotations::*;

#[cfg(mirai)]
use mirai_annotations::TagPropagationSet;

#[cfg(mirai)]
struct SecretTaintKind<const MASK: TagPropagationSet> {}

#[cfg(mirai)]
const SECRET_TAINT: TagPropagationSet = TAG_PROPAGATION_ALL;

#[cfg(mirai)]
type SecretTaint = SecretTaintKind<SECRET_TAINT>;

#[cfg(not(mirai))]
type SecretTaint = ();

struct A(u32);
struct B(u32);

fn a_to_b(a: A) -> B {
    precondition!(has_tag!(&a, SecretTaint));
    let b = B(a.0 + 1);
    postcondition!(has_tag!(&b, SecretTaint));
    b
}

fn main() {
    let a = A(1);
    add_tag!(&a, SecretTaint);
    let b = a_to_b(a);
    verify!(has_tag!(&b, SecretTaint));
}

run cargo mirai.

Expected Behavior

no warning.

Actual Results

 test-mirai git:(master) ✗ cargo mirai
    Checking test-mirai v0.1.0 (/Users/ya0guang/test-mirai)
[2022-02-02T02:16:39Z INFO  mirai] MIRAI options from environment: Options { single_func: None, test_only: false, diag_level: Default, constant_time_tag_name: None, max_analysis_time_for_body: 30, max_analysis_time_for_crate: 240, statistics: false, call_graph_config: None }
[2022-02-02T02:16:39Z INFO  mirai] MIRAI options modified by command line: Options { single_func: None, test_only: false, diag_level: Default, constant_time_tag_name: None, max_analysis_time_for_body: 30, max_analysis_time_for_crate: 240, statistics: false, call_graph_config: None }
[2022-02-02T02:16:39Z INFO  mirai::callbacks] Processing input file: src/main.rs
[2022-02-02T02:16:39Z INFO  mirai::callbacks] storing summaries for src/main.rs at /var/folders/cv/mtjnjfxs14lbt801r9vm8sd40000gp/T/.tmpAuiOal/.summary_store.sled
[2022-02-02T02:16:39Z INFO  mirai::summaries] creating a new summary store from the embedded tar file
[2022-02-02T02:16:39Z INFO  mirai::crate_visitor] analyzing function test_mirai.main
warning: possible unsatisfied postcondition
  --> src/main.rs:28:5
   |
28 |     postcondition!(has_tag!(&b, SecretTaint));
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: `test-mirai` (bin "test-mirai") generated 1 warning
    Finished dev [unoptimized + debuginfo] target(s) in 0.68s

Besides, from the comments in annotations/lib.rs, I think postcondition! is flow-sensitive, but verify! is not when using them in the same place in the function.

Environment

rustc 1.60.0-nightly (bfe156467 2022-01-22)

[hermanventer]

This seems like something that ought to work. I'll try and have a look this weekend.

[hermanventer]

This is quite a subtle problem and I don't have a fix for it as yet. What is going on here is that the post condition can't be proved while constructing the summary for a_to_b. It should be, given the precondition, but it is tricky and it goes wrong in this case.

The summary, however, is complete enough that the calling code can prove the verify in main even without the explicit post condition. So your work around for now is just to omit the post condition.

In general, post conditions are seldom needed, so omit them by default.

[ya0guang]

Thanks for your explanation!

I agree that postconditions could be avoided in most cases. I tried to reform my sample program without using postcondition but still got unexpected result:

#![cfg_attr(mirai, allow(incomplete_features), feature(generic_const_exprs))]

extern crate mirai_annotations;

use mirai_annotations::*;

#[cfg(mirai)]
use mirai_annotations::TagPropagationSet;

#[cfg(mirai)]
struct SecretTaintKind<const MASK: TagPropagationSet> {}

#[cfg(mirai)]
const SECRET_TAINT: TagPropagationSet = TAG_PROPAGATION_ALL;

#[cfg(mirai)]
type SecretTaint = SecretTaintKind<SECRET_TAINT>;

#[cfg(not(mirai))]
type SecretTaint = ();

struct A(u32);
struct B(u32);

fn a_to_b(a: A) -> B {
    precondition!(has_tag!(&a, SecretTaint));
    let b = B(a.0 + 1);
    b
}

fn b_to_a(b: B) -> A {
    precondition!(has_tag!(&b, SecretTaint));
    let a = A(b.0 + 1);
    a
}

fn main() {
    let a = A(1);
    add_tag!(&a, SecretTaint);
    let b = a_to_b(a);
    verify!(has_tag!(&b, SecretTaint));
    let a = b_to_a(b);
    verify!(has_tag!(&a, SecretTaint));
    // println!("reachable?");
}

Output of cargo mirai:

warning: unsatisfied precondition
  --> src/main.rs:42:13
   |
42 |     let a = b_to_a(b);
   |             ^^^^^^^^^
   |
note: related location
  --> src/main.rs:32:5
   |
32 |     precondition!(has_tag!(&b, SecretTaint));
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: this warning originates in the macro `precondition` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: this is unreachable, mark it as such by using the verify_unreachable! macro
  --> src/main.rs:43:5
   |
43 |     verify!(has_tag!(&a, SecretTaint));
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: `mirai_test` (bin "mirai_test") generated 2 warnings
    Finished dev [unoptimized + debuginfo] target(s) in 0.60s

In this program, I add another function b_to_a() and verify the same precondition at the beginning of b_to_a(). However, this is unsatisfied. The thing most confusing me is MIRAI doesn't complain on verify!(has_tag!(&b, SecretTaint));, which verifies the same thing as the precondition.

Besides, the last verify in main is unreachable (verify!(has_tag!(&a, SecretTaint));) and I don't know why. The commented println could be printed out when uncommented and I'm confused.

I would be more than grateful if you can provide some insights about the potential reasons lead to these. I'm not pretty sure if MIRAI should be used in this way and please point out my mistakes if possible!

[hermanventer]

Taint that propagates to other elements of a structure/collection is hard to deal with in the MIRAI heap model because the model is sparse. Also add_tag!(&a, SecretTaint); propagates from parent to child, whereas let b = a_to_b(a); propagates taint from child to parent, hence the success of the first verify and the failure of the second.

You are not doing anything wrong, just using a feature that is complicated and not yet well tested. I hope to fix these problems in the coming weeks.

[ya0guang]

Thank you for the quick rely! I'm looking forward to seeing the updated features!