formal verification - Dafny: What does no terms found to trigger on mean?

Question

I am getting a warning in Dafny which says that my quantifiers have

No terms found to trigger on.

What I am trying to do for my code is to find the largest number that has a square value that is less than or equal to the given natural number 'n'. Here is the code I came up with so far:

method sqrt(n : nat) returns (r: int)
  // square less than or equal to n
  ensures (r * r) <= n 
  // largest number
  ensures forall i :: 0 <= i < r ==> (i * i) < (r * r)
{
    var i := 0; // increasing number
    r := 0;
    while ((i*i) <= n)
      invariant (r*r) <= n
      invariant forall k :: 0 <= k < r ==> (k*k) < (r*r)
      decreases n - i
    {
      r := i;
      i := i + 1;
    }

    return r;
}

In this snippet, I am verifying that I am returning a value that has a square value which is less than or equal to 'n' by using the post-condition ensures (r * r) <= n.

I am also trying to verify that the returned value is indeed the largest value that has a square value that is less than or equal to 'n' by using the quantifier forall i :: 0 <= i < r ==> (i*i) < (r*r)

This quantifier means that all elements which came before 'r' has a square value that is smaller than the square value of r.

How does one fix the No terms found to trigger on.? What does it actually mean?

Dafny tells me that it is a warning. Does this mean that my quantifiers are wrong? or Does it mean that Dafny cannot verify it at all but it is correct?

Answer 1

The warning has to do with how Dafny (and the underlying solver Z3) handle quantifiers.

First of all, it truly is a warning. If the program has no errors (which is the case for your example), then it has passed the verifier and satisfies its specification. You don't need to fix the warning.

However, in more complex programs you will often find that the warning comes along with failed or unpredictable verification outcomes. In those cases, it's worth knowing how to fix it. Often, the warning can be eliminated by introducing a otherwise-useless helper function to serve as the trigger.

For example, here is a version of your example where Dafny does not warn about triggers

function square(n: int): int
{
    n * n
}

method sqrt(n : nat) returns (r: int)
  // square less than or equal to n
  ensures r * r <= n
  // largest number
  ensures forall i :: 0 <= i < r ==> square(i) < r * r
{
    var i := 0; // increasing number
    r := 0;
    while i * i <= n
      invariant r * r <= n
      invariant forall k :: 0 <= k < r ==> square(k) < r * r 
      decreases n - i
    {
      r := i;
      i := i + 1;
    }

    return r;
}

All I did was introduce a new function square(n) defined to be n * n, and then used it in a few key places under quantifiers in the rest of the program.

If all you care about is getting this one example to verify, you can stop reading here. The rest of the answer tries to explain why this fix works.

---

In short, it works because Dafny is now able to use square(i) and square(k) as triggers for the two quantifiers.

But, what is a trigger anyway, and why is square(i) a valid trigger but i * i isn't?

What is a trigger?

A trigger is a syntactic pattern involving quantified variables that serves as heuristic for the solver to do something with the quantifier. With a forall quantifier, the trigger tells Dafny when to instantiate the quantified formula with other expressions. Otherwise, Dafny will never use the quantified formula.

For example, consider the formula

forall x {:trigger P(x)} :: P(x) && Q(x)

Here, the annotation {:trigger P(x)} turns off Dafny's automatic trigger inference and manually specifies the trigger to be P(x). Otherwise, Dafny would have inferred both P(x) and Q(x) as triggers, which is typically better in general, but worse for explaining triggers :).

This trigger means that whenever we mention an expression of the form P(...), the quantifier will get instantiated, meaning that we get a copy of the body of the quantifier with ... plugged in for x.

Now consider this program

method test()
    requires forall x {:trigger P(x)} :: P(x) && Q(x)
    ensures Q(0)
{
}

Dafny complains that it cannot verify the postcondition. But this is logically obvious! Just plug in 0 for x in the precondition to get P(0) && Q(0), which implies the postcondition Q(0).

Dafny cannot verify this method because of our choice of triggers. Since the postcondition mentions only Q(0), and nothing about P, but the quantifier is triggered only by P, Dafny will never instantiate the precondition.

We can fix this method by adding the seemingly-useless assertion

assert P(0);

to the body of the method. The whole method now verifies, including the postcondition. Why? Because we mentioned P(0), which triggered the quantifier from the precondition, causing the solver to learn P(0) && Q(0), which allows it to prove the postcondition.

Take a minute and realize what just happened. We had a logically-correct-but-failing-to-verify method and added a logically-irrelevant-but-true assertion to it, causing the verifier to suddenly succeed. In other words, Dafny's verifier can sometimes depend on logically-irrelevant influences in order to succeed, especially when there are quantifiers involved.

It is an essential part of becoming a competent Dafny user to understand when a failure can be fixed by a logically-irrelevant influence, and how to find the right trick to convince Dafny to succeed.

(As an aside, note that this example goes through without the irrelevant assertion if we let Dafny infer triggers instead of manually hobbling it.)

What makes a good trigger?

Good triggers are usually small expressions containing the quantified variables that do not involve so-called "interpreted symbols", which, for our purposes, can be considered "arithmetic operations". Arithmetic is not allowed in triggers for the good reason that the solver cannot easily tell when a trigger has been mentioned. For example, if x + y was an allowed trigger and the programmer mentioned (y + 0) * 1 + x, the solver would have trouble immediately recognizing that this was equal to a triggering expression. Since this can cause inconsistent instantiation of quantifiers, arithmetic is disallowed in triggers.

Many other expressions are allowed as triggers, such as indexing into Dafny data structures, dereferencing fields, set membership, and function application.

Sometimes, the most natural way of writing down a formula will contain no valid triggers, as your original example did. In that case, Dafny will warn you. Sometimes, verification will succeed anyways, but in large programs you will often need to fix these warnings. A good general strategy is to introduce a new function the abstract some part of the quantified formula that can serve as a trigger.