What I’ve Discovered About Formal Strategies In Half a 12 months — Jakob’s Private Webpage
The category I am taking this semester, CSCI 1710: Logic for Systems, covers mannequin checking with Forge. Forge is virtually custom-made for 1710, although it is successfully an alternate implementation of Alloy, which is considerably better-known. Forge is developed by Tim Nelson alongside a handful of Brown college students.
“Light-weight” is a time period that is sometimes thrown round when discussing these sorts of mannequin checking instruments. I would summarize light-weight formal strategies as these constructed round the concept “it is higher to have an imperfect instrument that is helpful than a complete instrument that is unusable.” Alloy (and, by extension, Forge) might be the perfect instance of this. It is an try on the “smallest modelling notation that may specific a helpful vary of structural properties, is straightforward to learn and write, and will be analyzed robotically”. It is designed to make it straightforward to mannequin issues in an summary and high-level modality.
These instruments take, as enter, a specification of structural properties within the type of varieties and predicates, and validate that these expectations concerning the properties are true. For instance, let’s take a homework drawback from Working Methods – one other class I am taking this semester. The issue wasn’t notably troublesome, however I feel that checking my work with Alloy is a extra compelling use-case than any of the toy examples I might provide you with.
I’ll paraphrase the issue textual content in order to not make the search engine a extra great tool for any future college students of the cours. The issue pertains to ZFS, which is a copy-on-write file system. All allotted blocks of the file system are organized as one massive tree. When an operation is carried out that might modify a disk block, a replica of that block is made and that replicate is what will get modified. Mentioned modified copy is linked into the tree by copying the block’s dad or mum node and modifying that replicate in order that it factors to the modified block. This continues all the way in which as much as the basis, at which level you may have two copies of the basis: one which represents the filesystem earlier than the operation came about, and one which represents the filesystem after the operation came about. When you maintain the previous root round, it is a snapshot of the file system earlier than the operation.
The issue asks about when the kernel ought to free a block that was within the file system. Particularly:
- If a file is deleted, how do we all know if there is a ZFS snapshot that refers to it?
- If a snapshot is deleted, which recordsdata can we free?
One thing vital to contemplate when modeling a system with Alloy is whether or not particulars are vital sufficient to incorporate, or if they are often omitted for the sake of creating the mannequin simpler to cause about. For this drawback, we aren’t involved with concerning the tree-like construction of a file system – simply the time that recordsdata are created, whether or not or not they’re free, and whether or not or not they’re referred to by a snapshot (or the present file system).
(I’ll use “Alloy” and “Forge” interchangeably on this part, however I’m utilizing Forge right here.)
An Alloy spec begins with some definitions.
#lang forge
choice problem_type temporal
choice min_tracelength 2
choice max_tracelength 10
sig File {
ctime: one Int,
var free: one Int
}
sig Snapshot extends File {
kids: set File,
retired_list: set File
}
one sig CurrentRoot {
var live_children: set File,
var live_retired_list: set File
}
The issue we’re coping with entails a time area: a file would possibly exist at one time limit, however we would delete it in a while. We start by telling Forge that that is the type of drawback we’re coping with, and that we solely care about traces with a variety of distinctive states between 2 and 10.
We then mannequin the information varieties in query. You may consider sig like class in Java, or no matter your favourite object-oriented programming language is. In our mannequin, each File has a static ctime representing when the file was created, and whether or not or not it is free. var signifies that the sector can differ with time, so operations on the filesystem can have an effect on whether or not or not a file is free, however not the creation time.
This would possibly sound unsuitable, nevertheless it’s an intentional modeling selection. Relatively than mannequin the file system operations we’re involved with as altering the ctime, we as a substitute deal with it as one thing static, and think about whether or not or not it is legitimate solely when the file is allotted. In different phrases: we do not care what the ctime is for a free block, we simply care that the ctime is the same as the present time when a file is created.
If that did not make a lot sense, it is in all probability my fault and never yours. That time is a bit laborious to elucidate with out displaying the remainder of the code, so simply bear with me.
We’ll write some predicates subsequent, to mannequin the properties we’re thinking about.
pred referenced_by_snapshot[f: File] {
some s: Snapshot {
s.free = 0
f in s.kids
}
}
pred valid_state {
all f: File {
-- No referenced file ought to be free.
(f in CurrentRoot.live_children or (some s: Snapshot | f in s.kids and s.free = 0)) => f.free = 0
-- No file in a retired listing ought to referenced
f in CurrentRoot.live_retired_list => f not in CurrentRoot.live_children
all s: Snapshot {
f in s.retired_list and s.free = 0 => f not in s.kids
}
-- Deal with `free` as a boolean.
f.free = 0 or f.free = 1
}
-- Snapshots should be roots.
all s1 : Snapshot {
s1 not in CurrentRoot.live_children
s1 not in CurrentRoot.live_retired_list
all s2: Snapshot {
s1 not in s2.kids
s1 not in s2.retired_list
}
}
}
Predicates are sentences in first order logic (albeit with respect to a bounded area, as we’ll clarify later). The predicates above ought to be pretty readable with a light-weight clarification of the syntax. Braces ({}) symbolize a conjunction, so referenced_by_snapshot is equal to
pred referenced_by_snapshot[f: File] | (some s: Snapshot | (s.free = 0 and f in s.kids))
“A file f is referenced by a snapshot if there’s some snapshot s which is not free and refers to f by its kids relation.”
The valid_state is an encoding of the protection properties we care about. We would wish to cause about whether or not or not our ZFS releasing algorithm ever violates some properties that ought to be true of our mannequin. Particularly, that each one recordsdata which are “energetic” within the file system ought to be allotted, and that the retired listing ought to by no means seek advice from an allotted file.
There are another constraints within the predicate for issues which might usually be “apparent,” like free being both 0 or 1. A bonus to modeling issues like this in Forge is that it forces you to explicitly enumerate your entire assumptions – in the event you do not, it is going to reap the benefits of that and produce fashions which may appear nonsensical however are literally fully legitimate throughout the constraints you offered. For instance, if we did not have the constraint that f.free = 0 or f.free = 1 for all recordsdata, and we requested Forge to generate a mannequin of a legitimate state, it would construct a mannequin the place each file has free set to -7. Alloy is actually good for forcing you to grasp the issue at hand. I would examine it to having to show the issue to somebody unfamiliar, or explaining a tricky debugging problem to your favorite rubber duck.
Let’s outline the file system operations now. That is performed with predicates as properly, which encode whether or not the post-state precisely displays a specific operation upon the pre-state.
pred make_snapshot {
one s: Snapshot {
-- The snapshot captures the state of the filesystem at this time limit.
s.kids = CurrentRoot.live_children
s.retired_list = CurrentRoot.live_retired_list
-- The snapshot is now marked as allotted.
s.free = 1
s.free' = 0
all f: File {
f != s => {
-- The free flag is unchanged for each different file.
f.free' = f.free
-- All different creations occurred previously, relative to this one.
f.free = 0 => s.ctime > f.ctime
}
}
}
-- The retired listing is emptied for the present filesystem.
no live_retired_list'
-- Nothing else adjustments.
live_children' = live_children
}
pred delete_snapshot {
one s: Snapshot {
-- The snapshot is now marked as free
s.free = 0
s.free' = 1
-- TODO: Add reclaiming operation.
all f: File {
-- The free flag is unchanged for each different file.
f != s => f.free' = f.free
}
}
-- Nothing else adjustments.
live_retired_list' = live_retired_list
live_children' = live_children
}
pred make_file {
one f: File {
-- `f` is added to the set of dwell kids.
CurrentRoot.live_children' = CurrentRoot.live_children + f
-- `f` is marked as allotted.
f.free' = 0
-- n.b. it might already be allotted, if a earlier snapshot refers to it.
all f2: File {
f2 != f => {
-- Free flag for different recordsdata stays unchanged.
f2.free' = f2.free
-- All different creations occurred previously, relative to this one.
f2.free = 0 => f.ctime > f2.ctime
}
}
}
-- Nothing else adjustments.
live_retired_list' = live_retired_list
live_children' = live_children
}
pred delete_file {
one f: File {
-- It solely is smart to delete a file if it is within the filesystem
f in CurrentRoot.live_children
-- Take away it from the filesystem, and reclaim it if relevant.
-- In any other case, put it within the retired listing.
CurrentRoot.live_children' = CurrentRoot.live_children - f
referenced_by_snapshot[f] => {
-- If one other snapshot refers to this one, we do not free it
-- however add it to the retired listing.
f.free' = 0
CurrentRoot.live_retired_list' = CurrentRoot.live_retired_list + f
} else {
-- In any other case we are able to free it and the retired listing is unchanged.
f.free' = 1
live_retired_list' = live_retired_list
}
all f2: File {
-- Free flag for different recordsdata stays unchanged.
f2 != f => f2.free' = f2.free
}
}
}
Be aware that I’ve left a “TODO” in delete_snapshot. We’ll add that in later to see the way it adjustments the mannequin.
We also needs to encode what the file system appears like to start with.
-- We begin with an empty filesystem, the place every little thing is free.
pred init {
no CurrentRoot.live_children
no CurrentRoot.live_retired_list
all f: File {
f.free = 1 iff f != CurrentRoot
}
}
And with that, we are able to say what a “hint” appears like.
pred traces {
init
at all times (make_snapshot or delete_snapshot or make_file or delete_file)
}
We begin from nothing and at all times carry out one of many 4 operations we care about.
With that, we’ve sufficient that we are able to ask Forge some questions. We should always be sure that our predicates are satisfiable, and never so over-constrained that they will by no means be true, after which we should always be sure that valid_state is an invariant – that no operation will violate it.
check count on {
valid_state_vacuity1: { valid_state } for five File is sat
valid_state_vacuity2: { valid_state } for precisely 5 File is sat
init_vacuity1: { init } for five File is sat
init_vacuity2: { init } for precisely 5 File is sat
make_snapshot_vacuity1: { valid_state and make_snapshot } for five File is sat
make_snapshot_vacuity2: { valid_state and make_snapshot } for precisely 5 File is sat
make_snapshot_good: {
(valid_state and make_snapshot) => next_state valid_state
} for five File is theorem
delete_snapshot_vacuity1: { valid_state and delete_snapshot } for five File is sat
delete_snapshot_vacuity2: { valid_state and delete_snapshot } for precisely 5 File is sat
delete_snapshot_good: {
(valid_state and delete_snapshot) => next_state valid_state
} for five File is theorem
make_file_vacuity1: { valid_state and make_file } for five File is sat
make_file_vacuity2: { valid_state and make_file } for precisely 5 File is sat
make_file_good: {
(valid_state and make_file) => next_state valid_state
} for five File is theorem
delete_file_vacuity1: { valid_state and delete_file } for five File is sat
delete_file_vacuity2: { valid_state and delete_file } for precisely 5 File is sat
delete_file_good: {
(valid_state and delete_file) => next_state valid_state
} for five File is theorem
traces_vacuity: { traces } for five File is sat
traces_vacuity: { traces } for precisely 5 File is sat
}
for five File tells Forge to contemplate conditions the place there are between 0 and 5 recordsdata. for precisely 5 File tells Forge to contemplate conditions the place there are, properly, precisely 5 recordsdata. I normally embrace the latter as a result of some over-constrained predicates are satisfiable exactly when there precisely 0 of one thing, and I am normally within the case the place there’s not less than 1 of one thing. The “vacuity” checks are there to make sure that the implication is not “vacuously” true (i.e., the left-hand facet is at all times false and the implication tells us nothing.)
We are able to run these checks to seek out that all of them cross. That means that if we assume valid_state truly encodes what we imply, our mannequin upholds the invariant. Which is sweet, as a result of instinct tells us that the implementation the place we simply leak disk area ought to be secure.
With that, we are able to lastly reply the second a part of the query by updating delete_snapshot to reclaim the free area and see if our invariant is violated.
pred delete_snapshot {
one s: Snapshot {
-- The snapshot is now marked as free
s.free = 0
s.free' = 1
all f: File {
-- Added this
f in s.retired_list => f.free' = 1
-- The free flag is unchanged for each different file.
(f not in s.retired_list and f != s) => f.free' = f.free
}
}
-- Nothing else adjustments.
live_retired_list' = live_retired_list
live_children' = live_children
}
Let’s run it.
jakob@whitecloud ~ $ racket 1670-problem.frg
Forge model: 2.7.0
To report points with Forge, please go to https://report.forge-fm.org
#vars: (size-variables 1806); #major: (size-primary 322); #clauses: (size-clauses 3035)
Transl (ms): (time-translation 505); Fixing (ms): (time-solving 77)
#vars: (size-variables 1464); #major: (size-primary 317); #clauses: (size-clauses 2396)
Transl (ms): (time-translation 147); Fixing (ms): (time-solving 24)
#vars: (size-variables 1597); #major: (size-primary 322); #clauses: (size-clauses 2661)
Transl (ms): (time-translation 76); Fixing (ms): (time-solving 48)
#vars: (size-variables 1255); #major: (size-primary 317); #clauses: (size-clauses 2022)
Transl (ms): (time-translation 35); Fixing (ms): (time-solving 15)
#vars: (size-variables 3304); #major: (size-primary 322); #clauses: (size-clauses 8369)
Transl (ms): (time-translation 167); Fixing (ms): (time-solving 42)
#vars: (size-variables 2942); #major: (size-primary 317); #clauses: (size-clauses 7670)
Transl (ms): (time-translation 163); Fixing (ms): (time-solving 23)
#vars: (size-variables 38523); #major: (size-primary 6129); #clauses: (size-clauses 86238)
Transl (ms): (time-translation 1451); Fixing (ms): (time-solving 829) Core min (ms): (time-core 0)
#vars: (size-variables 2131); #major: (size-primary 322); #clauses: (size-clauses 4196)
Transl (ms): (time-translation 64); Fixing (ms): (time-solving 21)
#vars: (size-variables 1764); #major: (size-primary 317); #clauses: (size-clauses 3482)
Transl (ms): (time-translation 54); Fixing (ms): (time-solving 21)
#vars: (size-variables 1951); #major: (size-primary 317); #clauses: (size-clauses 3955)
Transl (ms): (time-translation 52); Fixing (ms): (time-solving 17)
Occasion discovered, with statistics and metadata:
(Sat
'(#hash((CurrentRoot . ((CurrentRoot0)))
(File . ((File0) (File1) (File2) (File3) (File4)))
(Snapshot . ((File4)))
(kids . ((File4 File2) (File4 File3)))
(ctime . ((File0 5) (File1 -7) (File2 6) (File3 5) (File4 7)))
(free . ((File0 0) (File1 0) (File2 0) (File3 0) (File4 0)))
(live_children . ((CurrentRoot0 File0)))
(live_retired_list . ())
(retired_list . ((File4 File0) (File4 File1))))
#hash((CurrentRoot . ((CurrentRoot0)))
(File . ((File0) (File1) (File2) (File3) (File4)))
(Snapshot . ((File4)))
(kids . ((File4 File2) (File4 File3)))
(ctime . ((File0 5) (File1 -7) (File2 6) (File3 5) (File4 7)))
(free . ((File0 1) (File1 1) (File2 0) (File3 0) (File4 1)))
(live_children . ((CurrentRoot0 File0)))
(live_retired_list . ())
(retired_list . ((File4 File0) (File4 File1)))))
'((size-variables 1951)
(size-clauses 3955)
(size-primary 317)
(time-translation 52)
(time-solving 17)
(time-building 1681047504957))
'((prefixLength 2) (loop 1)))
Sterling working. Hit enter to cease service.
Our check fails, and Forge reveals us a counterexample! That is the primary state:
Then we delete a snapshot (File4).
It is perhaps a bit laborious to visually parse, however File0 is being freed. It is in a snapshot’s retired listing, nevertheless it’s dwell within the present file system as properly. So if we free it, we find yourself violating the invariant that each dwell file ought to be allotted.
That is fairly fascinating from a counterexample perspective. Can we delete a file after which have it.. come again? Possibly, however I’ll say “in all probability not” within the case of this homework drawback. (Although it’s useful to have one other assumption I could make specific in my answer set!) So let’s deal with this as a modeling problem and repair it. The issue is that we’ve a file that comes again to life: it is in some snapshot’s retired_list, however then it additionally reveals again up within the root’s live_children. The identical problem also can manifest as a file being in a snapshot’s retired_list and likewise in a a later snapshot’s kids. Let’s add this to the protection property:
pred valid_state {
all f: File {
-- No referenced file ought to be free.
(f in CurrentRoot.live_children or (some s: Snapshot | f in s.kids and s.free = 0)) => f.free = 0
-- No file in a retired listing ought to referenced
f in CurrentRoot.live_retired_list => f not in CurrentRoot.live_children
all s: Snapshot {
f in s.retired_list and s.free = 0 => f not in s.kids
}
-- Deal with `free` as a boolean.
f.free = 0 or f.free = 1
}
-- Snapshots should be roots.
all s1 : Snapshot {
s1 not in CurrentRoot.live_children
s1 not in CurrentRoot.live_retired_list
all s2: Snapshot {
s1 not in s2.kids
s1 not in s2.retired_list
}
}
-- Added this!
all f: File | (all s1: Snapshot | f in s1.retired_list => {
f not in CurrentRoot.live_children
all s2: Snapshot {
s2.ctime > s1.ctime => f not in s2.kids
}
})
-- This was additionally needed -- clock is monotone.
all disj f1, f2: File | f1.ctime != f2.ctime
}
And now we get a extra smart counterexample.
Now we’ve a file being freed that is additionally referred to by a earlier snapshot. This is smart, and divulges an precise problem with the strategy of “let’s delete every little thing within the retired listing.” What we truly have to do is examine to see if any snapshots seek advice from an entry within the retired listing earlier than deleting it. How we do that is the topic of the primary a part of the issue, which we’ll get to. For now, let’s assume we’ve some environment friendly predicate to tells us if a file is referenced by an earlier snapshot.
pred referenced_by_no_other_snapshot[f: File] {
all s: Snapshot {
s.free = 0 => f not in s.kids
}
}
pred delete_snapshot {
one s: Snapshot {
-- The snapshot is now marked as free
s.free = 0
s.free' = 1
all f: File {
(f in s.retired_list and referenced_by_no_other_snapshot[f]) => {
f.free' = 1
} else {
-- The free flag is unchanged for each different file.
f != s => f.free' = f.free
}
}
}
-- Nothing else adjustments.
live_retired_list' = live_retired_list
live_children' = live_children
}
jakob@whitecloud ~ $ racket 1670-problem.frg Forge model: 2.7.0 To report points with Forge, please go to https://report.forge-fm.org #vars: (size-variables 3529); #major: (size-primary 322); #clauses: (size-clauses 7302) Transl (ms): (time-translation 794); Fixing (ms): (time-solving 127) #vars: (size-variables 3162); #major: (size-primary 317); #clauses: (size-clauses 6638) Transl (ms): (time-translation 296); Fixing (ms): (time-solving 93) #vars: (size-variables 1597); #major: (size-primary 322); #clauses: (size-clauses 2661) Transl (ms): (time-translation 52); Fixing (ms): (time-solving 41) #vars: (size-variables 1255); #major: (size-primary 317); #clauses: (size-clauses 2022) Transl (ms): (time-translation 62); Fixing (ms): (time-solving 14) #vars: (size-variables 3947); #major: (size-primary 322); #clauses: (size-clauses 9561) Transl (ms): (time-translation 239); Fixing (ms): (time-solving 65) #vars: (size-variables 3560); #major: (size-primary 317); #clauses: (size-clauses 8837) Transl (ms): (time-translation 233); Fixing (ms): (time-solving 55) #vars: (size-variables 44814); #major: (size-primary 6129); #clauses: (size-clauses 107343) Transl (ms): (time-translation 2139); Fixing (ms): (time-solving 777) Core min (ms): (time-core 0) #vars: (size-variables 3934); #major: (size-primary 322); #clauses: (size-clauses 8718) Transl (ms): (time-translation 126); Fixing (ms): (time-solving 48) #vars: (size-variables 3542); #major: (size-primary 317); #clauses: (size-clauses 7979) Transl (ms): (time-translation 121); Fixing (ms): (time-solving 31) #vars: (size-variables 44652); #major: (size-primary 6129); #clauses: (size-clauses 107046) Transl (ms): (time-translation 1545); Fixing (ms): (time-solving 1413) Core min (ms): (time-core 0) #vars: (size-variables 3844); #major: (size-primary 322); #clauses: (size-clauses 9198) Transl (ms): (time-translation 82); Fixing (ms): (time-solving 40) #vars: (size-variables 3452); #major: (size-primary 317); #clauses: (size-clauses 8459) Transl (ms): (time-translation 113); Fixing (ms): (time-solving 34) #vars: (size-variables 43842); #major: (size-primary 6129); #clauses: (size-clauses 103941) Transl (ms): (time-translation 1342); Fixing (ms): (time-solving 1027) Core min (ms): (time-core 0) #vars: (size-variables 3831); #major: (size-primary 322); #clauses: (size-clauses 8652) Transl (ms): (time-translation 94); Fixing (ms): (time-solving 49) #vars: (size-variables 3454); #major: (size-primary 317); #clauses: (size-clauses 7958) Transl (ms): (time-translation 98); Fixing (ms): (time-solving 34) #vars: (size-variables 43761); #major: (size-primary 6129); #clauses: (size-clauses 105993) Transl (ms): (time-translation 1218); Fixing (ms): (time-solving 1214) Core min (ms): (time-core 0) #vars: (size-variables 4586); #major: (size-primary 322); #clauses: (size-clauses 13204) Transl (ms): (time-translation 111); Fixing (ms): (time-solving 34) #vars: (size-variables 4124); #major: (size-primary 317); #clauses: (size-clauses 12205) Transl (ms): (time-translation 80); Fixing (ms): (time-solving 10) #vars: (size-variables 87834); #major: (size-primary 6273); #clauses: (size-clauses 264636) Transl (ms): (time-translation 3211); Fixing (ms): (time-solving 10304) Core min (ms): (time-core 0)
Candy. Now, let’s sort out the primary drawback. I posit that this may be decided by strolling the snapshots and seeing if any exist with a ctime after the block’s ctime and earlier than the time of the deletion.
check count on {
problem_2b: { traces => at all times referenced_by_snapshot[f] => s.free = 0 and s.ctime > f.ctime
} for precisely 5 File is theorem
}
jakob@whitecloud ~ $ racket 1670-problem.frg Forge model: 2.7.0 To report points with Forge, please go to https://report.forge-fm.org #vars: (size-variables 4660); #major: (size-primary 329); #clauses: (size-clauses 13496) Transl (ms): (time-translation 910); Fixing (ms): (time-solving 67) Core min (ms): (time-core 0)
Good! Now I’ve some confidence that my homework solutions are proper.