Fun with Spec#
You can copy-paste this code directly into the Spec# web-interface. If Spec# gives the message: “Verified, no errors found”, then you're done (of course provided the postcondition is correct).
Find the invariant
class Mult {
int fi(int x, int y)
requires x >= 0 && y >= 0;
ensures result == x * y;
{
int r = 0;
int i = 0;
while (i < y)
invariant ... ;
{
i = i + 1;
r = r + x;
}
return r;
}
}
Find the invariant 2
class Mult {
int fi2(int x, int y)
requires x >= 0 && y >= 0;
ensures result == x * y;
{
int r = 0;
int i = y;
while (i > 0)
invariant ...;
{
i = i - 1;
r = r + x;
}
return r;
}
}
What's missing?
class Account {
private int checkingBalance;
private int savingsBalance;
private void checkingDeposit(int amount)
ensures checkingBalance == old(checkingBalance) + amount;
{
checkingBalance = checkingBalance + amount;
}
private void checkingWithdraw(int amount)
ensures checkingBalance == old(checkingBalance) - amount;
{
checkingBalance = checkingBalance - amount;
}
private void savingsDeposit(int amount)
ensures savingsBalance == old(savingsBalance) + amount;
{
savingsBalance = savingsBalance + amount;
}
…
}
Why does this fail to verify?
Now add the following two methods to the class above:
private void transferSavingsToChecking(int amount)
requires amount > 0 && savingsBalance >= amount;
ensures savingsBalance == old(savingsBalance) - amount;
ensures checkingBalance == old(checkingBalance) + amount;
ensures old(checkingBalance) + old(savingsBalance) == checkingBalance + savingsBalance;
{
savingsBalance = savingsBalance - amount;
checkingBalance = checkingBalance + amount;
}
private void transferCheckingToSavings(int amount)
requires amount > 0 && checkingBalance >= amount;
ensures old(checkingBalance) + old(savingsBalance) == checkingBalance + savingsBalance;
{
checkingWithdraw(amount);
savingsDeposit(amount);
}
Find the invariant 3
class Sqrt {
public int sqrt(int x)
requires 0 <= x;
ensures result*result <= x && x < (result+1)*(result+1);
{
int r = 0;
while ((r+1)*(r+1) <= x)
invariant ... ;
{
r++;
}
return r;
}
}
Find the invariant 4
class LinearSearch {
bool search(int[] a, int key)
ensures result == exists{int i in (0: a.Length); a[i] == key};
{
int n = a.Length;
do
invariant ...;
{
n--;
if (n < 0) {
break;
}
} while (a[n] != key);
return 0 <= n;
}
}
Find the error
class SomeFunction1 {
public int f(int x, int y)
requires 0 <= x && 0 <= y;
ensures result == 2*x + y;
{
int r = x;
for (int n = 0; n < y; n++)
invariant r == x+n && n <= y;
{
r++;
}
return r;
}
}
Find the invariant - last one
class GCD {
int gcd(int a, int b)
requires a > 0 && b > 0;
ensures ...;
ensures ...;
{
int i = 1; int res = 1;
while (i < a+b)
invariant ...;
{
i++;
if (a % i == 0 && b % i == 0) {
res = i;
}
}
return res;
}
}