Nine Rules to Formally Validate Rust Algorithms with Dafny by Carl Kadie & Divyanshu Ranjan

The internal_add operate tries to effectively insert a brand new vary of integers into an current listing of sorted and disjoint integer ranges. For instance, if we began with [101..=102, 400..=402, 404..=405] and added 402..=404, we anticipate a results of [101..=102, 400..=405].

Ideally, I’d formally confirm this algorithm with Rust-specific instruments [1,2]. These instruments, nevertheless, appear arduous to make use of. As an alternative, I selected Dafny. Dafny is a language and verification system. It’s taught to undergraduates at universities world wide. It’s utilized in business. I discover it to be addictively interactive and programmer pleasant.

Apart: Dafny creator, Dr. Rustan Leino has a connection to Rust past the coincidence of his first identify. He helped create Spec#, the primary language to make use of a kind system to keep away from null pointers. Rust, after all, adopted this concept to nice success.

This text covers guidelines 1 to six. Half 2 will cowl guidelines 7 to 9.

Earlier than making an attempt to show the mathematical correctness of your algorithm, resolve if the trouble is well worth the profit.

Dafny shouldn’t be Rust. Utilizing Dafny requires porting algorithms of curiosity from Rust to Dafny. This port can miss particulars and introduce errors. Given this threat, ought to you use Dafny to confirm Rust algorithms? I boldly declare that “it relies upon”.

• How essential is your algorithm’s correctness? In case you are printing a report and it seems proper, it in all probability is correct. The internal_add algorithm relates to a knowledge construction that I’d like others to make use of with confidence, giving me further motivation to confirm it.
• Possibly all formal verification, with present instruments, is simply too arduous. I imagine, nevertheless, that Dafny makes formal verification as straightforward as presently potential. You will discover formally verifying code simpler in case you are already acquainted with varieties (for instance, from Rust) and recursion/induction (used sometimes in Rust). You’ll be able to learn this text and resolve for your self if/when formal verification is simple sufficient to be useful to you.
• Possibly fuzzing (reminiscent of cargo-fuzz) and property-based testing (reminiscent of QuickCheck) are ok. Though these strategies don’t present mathematical certainty, they’re intelligent, helpful, and straightforward to make use of. (The range-set-blaze crate already makes use of QuickCheck. See Rule 9.5 in a previous article for particulars).
• Possibly formal verification is and can at all times be doomed as a result of writing a specification is as arduous as writing code. I disagree. Take into consideration refactoring. I typically begin coding by writing one thing easy. I then refactor this easy code for effectivity. For internal_add, I discovered the specification to be less complicated than any code. (You’ll be able to choose this for your self in Rule 4.)

Apart: Verification then turns into a computer-checked refactoring from a easy specification to a ultimate, environment friendly algorithm.

• Possibly formal verification is and can at all times be doomed as a result of the halting problem tells us formally that formality isn’t typically potential. The halting drawback doesn’t doom us. Whereas we are able to’t at all times perceive arbitrary code, we don’t have to. We solely want to know our personal code, which we (hopefully) wrote to be comprehensible. Beginning in Rule 2, we’ll see how Dafny simply verifies that particular loops and recursions halt.
• Possibly porting to Dafny is simply too arduous. This has not been my expertise. Like Rust, Dafny mixes and matches crucial and practical programming. I discovered porting my algorithm to be simple.

Assuming you continue to need to confirm your algorithm with Dafny, the next step is to be taught Dafny.

Dafny is each a programming language and an interactive verification system. I like to recommend you install it as a VS Code extension.

To be taught it, begin at https://dafny.org/. Of particular curiosity is the Online Tutorial and the Reference Manual. I additionally discovered the Verification Corner videos on YouTube useful. (Of potential curiosity is the school textbook, Program Proofs, $49 for the Kindle Version). I discovered the programming language a part of Dafny simpler to be taught than Rust, maybe comparable in problem to C#.

Dafny, like Rust, is totally typed. Dafny, like Python, is rubbish collected. Right here is a “Hello World”:

// hiya.dfy
methodology Most important()
{
var s := "Hi there World";
print s, "n";
}

Dafny, additionally like Python, affords integers of arbitrary measurement. Right here is a program that provably provides two pure numbers by repeatedly incrementing.

Some factors of curiosity:

• Dafny coding tips observe C#, not Rust. So, we identify the operate SlowAdd not slow_add (though both will run).
• Dafny helps subtypes. For instance, any int that may be proven to be non-negative can also be a nat.
• Project is := and equality is == . (There is no such thing as a = .)
• Operate parameters, for instance, x and y above, are immutable.
• Dafny makes use of ensures and invariant statements to confirm the code at compile-type. It then removes these statements to complete compiling.
• The inexperienced verify mark exhibits that this code verifies. Dafny’s VS Code extension will, by default, repeatedly attempt to validate every methodology. This provides an virtually gambling-like pleasure to working with Dafny. Within the instance above, if I make y an int slightly than a nat, then validation ought to and can fail. (Can you determine why?) Dafny will mark my operate with a purple X and inform me “This postcondition won't maintain: r == x + y”.
• Dafny is aware of a number of the arithmetic of integers, arrays, units, maps, sequences, and so on. This typically permits it to complete the final particulars of validation by itself.

Now that you understand about Dafny, you must let it find out about your algorithm.

The range-set-blaze crate represents units of integers as sorted, disjoint ranges. For instance, this listing of three ranges:

100..=2_393,
20_303..=30_239_000,
501_000_013..=501_000_016

represents a set of 30,220,996 integers.

In Rust, the RangeSetBlaze struct represents this information construction internally with a typical BTreeMap. Recall {that a} BTreeMap represents an inventory of key/worth pairs, sorted by key. Right here, our keys are the ranges’ begins (for instance, 100, 20_303, 501_000_013) and the values are the ranges’ inclusive ends (for instance, 2_393, 30_239_000, 501_000_016. RangeSetBlaze shops the listing with a BTreeMap slightly than a vec to make key search for extra cache pleasant.

RangeSetBlaze will depend on BTreeMap, so should we implement BTreeMap in Dafny? Fortunately, no. We will, as an alternative, use Dafny’s vec-like seq information kind. This substitution works as a result of BTreeMap, vec, and seq can all characterize sorted lists — simply with totally different efficiencies. For the aim of formal verification, we solely care about correctness and may ignore effectivity.

RangeSetBlaze requires the listing of ranges be sorted and disjoint. How do we are saying “sorted and disjoint” in Dafny? We will say it through this ghost predicate (and related code):

ghost predicate ValidSeq(sequence: seq<NeIntRange>) sequence
kind IntRange = (int, int)
kind NeIntRange = x: IntRange | !IsEmpty(x) witness (0,0)
operate IsEmpty(r: IntRange): bool
{
r.0 > r.1
}

A predicate is one other identify for a way that returns bool. A ghost methodology (or predicate) is one that may solely be used for validation, not for operating the ultimate code.

At a excessive degree, the ValidSeq predicate takes as enter a sequence of non-empty integer ranges. It then assessments that the beginning values are sorted and that the ranges don’t contact. Particularly,

• An IntRange is a tuple of two int values.
• An IntRange IsEmpty precisely when its begin is larger than its finish. (This follows Rust’s convention.)
• A NeIntRange (non-empty integer vary) is an IntRange that’s not empty, for instance, (0,0). [All our ranges are end inclusive.]
• This expression assessments that the beginning values are sorted:

forall i:nat, j:nat | i < j < |sequence| :: sequence[i].0 < sequence[j].0

It may be learn as “for all pure numbers i and j — such that i is lower than j and j is lower than the size of the sequence — take a look at that the beginning worth at index i is lower than the beginning worth as index j”.

Apart: Notice {that a} Rust BTreeMap doesn’t help (random-access) indexing however right here we’re utilizing such indexing. That is OK as a result of ValidSeq is a ghost predicate and so will solely be used for validation.

• This expression assessments that the ranges are disjoint:

forall i:nat, j:nat | i < j < |sequence| :: !Contact(sequence[i], sequence[j])

It may be learn as “for all pure numbers i and j — such that i is lower than j and j is lower than the size of the sequence — take a look at that the vary at index i doesn’t contact the vary at index j. However what’s Contact?

We’ll outline Contact on two-levels. On a mathematical degree, a spread i is alleged to the touch a spread j if there exists an integer i0 in vary i and an integer j0 in vary j such that i0 and j0 are inside a distance of certainly one of one another. On an environment friendly programming degree, we need to keep away from definitions relying on “there exists”. Here is a Dafny predicate that’s each mathematical and environment friendly:

predicate Contact(i: NeIntRange, j: NeIntRange)
ensures Contact(i, j) == exists i0, j0 ::
Incorporates(i, i0) && Incorporates(j, j0) && -1 <= i0 - j0 <= 1
{
assert Incorporates(i, i.0) && Incorporates(i, i.1) && Incorporates(j, j.0) && Incorporates(j, j.1);
if i.1 < j.0 then
assert  (-1 <= i.1 - j.0 <= 1) == (i.1+1 == j.0);
i.1+1 == j.0
else if j.1 < i.0 then
assert (-1 <= j.1 - i.0 <= 1) == (j.1+1 == i.0);
j.1+1 == i.0
else
var k0 := Max(i.0, j.0);
assert Incorporates(i, k0) && Incorporates(j, k0);
true
}
operate Incorporates(r: IntRange, i: int): bool
{
r.0 <= i && i <= r.1
}
operate Max(a: int, b: int): int
{
if a < b then b else a
}

Some factors of curiosity:

• Contact shouldn’t be a ghost. In different phrases, we are able to use it in each common code and validation code.
• The assert statements assist Dafny show that the common code meets the mathematical ensures assertion.
• For effectivity, the Dafny prover validates the within of a methodology individually from its exterior. Solely the ensures (and the yet-to-be-seen, requires) statements cross this border. In distinction to a methodology, a Dafny operate is clear to the validator. (I consider it as inlining code with respect to validation.)

With ideas reminiscent of ValidSeq and Contact outlined, we subsequent transfer onto specifying what our algorithm is meant to do.

In the end, I need to show that my particular Rust algorithm for inserting a brand new vary right into a RangeSetBlaze is appropriate. Earlier than we do this, nevertheless, let’s outline what “correct” range insertion is.

methodology InternalAdd(xs: seq<NeIntRange>, a: IntRange) returns (rs: seq<NeIntRange>)
requires ValidSeq(xs)
ensures ValidSeq(rs)
ensures SeqToSet(rs) == SeqToSet(xs) + RangeToSet(a)
{
if IsEmpty(a)
{
rs := xs;
}
else
{
assume false; // cheat for now
}
}

This says that InternalAdd is a technique that takes xs, a sequence of non-empty integer ranges, and a, an integer vary (that may very well be empty). The tactic outputs rs, a brand new sequence of non-empty integer ranges.

We have to say that xs and rs have to be sorted and disjoint. That’s simply achieved with the ValidSeq’s within the requires and first ensures.

We additionally have to say that rs accommodates the correct stuff. Is this difficult? It’s not. We simply say that the set of integers in rs should equal the set of integers in xs unioned with the integers in a.

Apart: In Dafny, “+” when utilized to units is “union”.

The set of integers in a spread is:

ghost operate RangeToSet(pair: IntRange): set<int>
{
set i {:autotriggers false} | pair.0 <= i <= pair.1 :: i
}

And the set of integers in a sequence of non-empty ranges could be outline inductively (that’s, recursively):

ghost operate SeqToSet(sequence: seq<NeIntRange>): set<int>
decreases |sequence|
requires ValidSeq(sequence)
{
if |sequence| == 0 then {}
else if |sequence| == 1 then RangeToSet(sequence[0])
else RangeToSet(sequence[0]) + SeqToSet(sequence[1..])
}

Some factors of curiosity:

• The road: assume false; // cheat for now makes validation work even if it really shouldn’t. We use it as a short lived placeholder.
• We make RangeToSet and SeqToSet ghosts to cease us from utilizing them in common code. We make them features (as an alternative of strategies) to inline them with respect to validation.
• As a result of Dafny is aware of quite a bit about creating and manipulating units and sequences, we regularly revenue through the use of units and sequences in our specification.
• Even when our common code makes use of loops as an alternative of recursion, our validation code will typically use recursive-like induction.
• The {:autotriggers false} pertains to avoiding a warning message. For extra data see this Stack Overflow answer by Prof. James Wilcox.

We now have a proper specification of InternalAdd. I discover this specification brief and intuitive. However what in case you need assistance determining a specification or different Dafny code?

The primary discussion board for Dafny questions is Stack Overflow. To my shock, I really acquired a lot helpful assist there.

I like to recommend beginning your query’s title with “Dafny:”. Additionally, you’ll want to tag your query with dafny and, maybe, formal-verification.

Apart: On the positioning, you possibly can see my 11 questions and Divyanshu Ranjan’s 48 Dafny-related answers.

As an open-source venture on GitHub, Dafny additionally hosts GitHub Discussions and Points.

The Dafny neighborhood is small however appears obsessed with serving to customers and bettering the venture.

With assist at hand, we should subsequent discover an algorithm that meets the specification.

As a novice to formal verification, I made a decision to postpone work on the actual internal_add utilized in my Rust code. As an alternative, I began work on an InternalAdd algorithm that I hoped can be simpler to validate. I ended up with this:

methodology InternalAdd(xs: seq<NeIntRange>, a: IntRange) returns (rs: seq<NeIntRange>)
requires ValidSeq(xs)
ensures ValidSeq(rs)
ensures SeqToSet(rs) == SeqToSet(xs) + RangeToSet(a)
{
if IsEmpty(a)
{
rs := xs;
}
else
{
var notTouching, merged := PartitionAndMerge(xs, a);
var indexAfter := NoTouchIndexAfter(notTouching, merged);
rs := InsertAt(notTouching, [merged], indexAfter);
}
}

The thought is that if vary a is empty, we return the enter sequence unchanged. In any other case, we divide the work into three steps, which we are able to validate independently. Step one, PartitionAndMerge, returns:

• notTouching, a sequence of ranges that don’t contact vary a, and
• merged, a single vary created from a and all the things it touches.

Right here is an instance enter and output:

InternalAdd subsequent finds the place to insert merged and, lastly, inserts it.

Right here is the code for PartitionAndMerge:

methodology PartitionAndMerge(xs: seq<NeIntRange>, a: NeIntRange) returns (notTouching: seq<NeIntRange>, merged: NeIntRange)
requires ValidSeq(xs)
ensures ValidSeq(notTouching)
ensures RangeToSet(merged) >= RangeToSet(a)
ensures forall vary | vary in notTouching :: !Contact(vary, merged)
ensures SeqToSet(xs) + RangeToSet(a) == SeqToSet(notTouching) + RangeToSet(merged)
{
// Break up into touching and never touching seqs
var touching: seq<NeIntRange>;
touching, notTouching := Partition(a, xs);
// Merge the touching seq into one vary with our authentic vary
merged := UnionSeq(a, touching);
}

This says that PartitionAndMerge requires that xs be a legitimate sequence of non-empty integer ranges and that a be a non-empty integer vary. It ensures that nonTouching is one other legitimate sequence of non-empty integer ranges. It ensures that the integers in vary merged are a superset of these in vary a. It ensures that no vary in notTouching touches vary merged. And eventually, it ensures that the integers in xs and a are precisely the identical because the integers in notTouching and merged.

PartitionAndMerge additionally divides the work, this time into two steps (Partition and UnionSeq) that may be validated independently. These steps proceed to subdivide their work. The place does it finish? Let’s have a look at one instance.

The tactic UnionSeq calls UnionRange which merges two ranges:

operate UnionRange(x: IntRange, y: IntRange): IntRange
requires IsEmpty(x) || IsEmpty(y) || Contact(x, y)
ensures RangeToSet(x) + RangeToSet(y) == RangeToSet(UnionRange(x,y))
{
if IsEmpty(x) then y
else if IsEmpty(y) then x
else (Min(x.0, y.0), Max(x.1, y.1))
}

The UnionRange code handles the empty instances after which returns the minimal bounding vary. (The minimal bounding vary is the vary from the smaller of the 2 begins to the bigger of the 2 ends.) However how can this be appropriate? On the whole, a minimal bounding vary of two ranges would possibly embrace further integers. We’d get one thing larger than the union of the inputs, like so:

The code is appropriate as a result of it requires that the 2 enter ranges contact or are empty. This ensures that the union of the integers in vary x with the integers in vary y are precisely the integers within the output vary.

At compile time, Dafny proves this operate appropriate. Past that, it proves that all the things that calls this operate gives inputs which might be empty or touching.

I consider this as a generalization of Rust’s borrow checker. At compile-time Rust checks that we’re protected from many reminiscence errors. At compile time, verification techniques, reminiscent of Dafny, can show virtually arbitrary properties. In fact, as we’re seeing, this potential comes at the price of complexity.

The full code for this verified algorithm is about 200 strains, organized into a couple of dozen strategies and features.

This rule exhibits that we are able to confirm an algorithm for InternalAdd, however it isn’t the algorithm I utilized in Rust. We’ll flip to that subsequent.