Alastair Reid

Here's a 2020 overview of Rust verification tools https://alastairreid.github.io/rust-verification-tools/ - it says

> Auto-active verification tools

> While automatic tools focus on things not going wrong, auto-active verification tools help you verify some key properties of your code: data structure invariants, the results of functions, etc. The price that you pay for this extra power is that you may have to assist the tool by adding function contracts (pre/post-conditions for functions), loop invariants, type invariants, etc. to your code.

> The only auto-active verification tool that I am aware of is Prusti. Prusti is a really interesting tool because it exploits Rust’s unusual type system to help it verify code. Also Prusti has the slickest user interface: a VSCode extension that checks your code as you type it!

> https://marketplace.visualstudio.com/items?itemName=viper-admin.prusti-assistant

Now, on that list, there is also https://github.com/facebookexperimental/MIRAI that, alongside the crate https://crates.io/crates/contracts (with the mirai_assertion feature enabled) enables writing code like this

#[ensures(person_name.is_some() -> ret.contains(person_name.unwrap()))]
fn geeting(person_name: Option<&str>) -> String
{
let mut s = String::from("Hello");
if let Some(name) = person_name
{
s.push(' ');
s.push_str(name);
}
s.push('!');
s
}

And have it checked at compile time that the…

> What worries me is that when it comes to safety, surely the chain is as strong as the weakest link? You declare one thing unsafe, and then suddenly, all bets are off. And maybe you don't even know that what you're doing is unsafe.

Yes, you are correct. If some code or module contains a memory safety or data race bug, then the code which uses it could realize that bug in the form of a crash or race. This paper is not analyzing code that contains a memory safety or data race bug, but instead, code that the Rust compiler cannot prove doesn't have such a bug. That is a big difference.

Let's take your example. The questions you bring up are good ones. Fiddling with registers may indeed require atomic in the presence of multiple threads using that register. Or, if you can guarantee only one thread touches those registers, it may not. In both use cases, I'd like the compiler to help me verify that those conditions are met. A Rust approach to this problem (verified empirically by the paper) would be to create a module, function, or trait that enforces the invariants we need. Such an abstraction might contain a bug that causes the codebase to be unsafe. But when debugging that, we shouldn't have to look over the whole codebase for register writes but rather in just one place.

> Suppose you have an ISR (interrupt service routine) that wants to toggle a GPIO pin. From whence does it borrow the privilege to set the pin?

Assuming we are protecting the pin with atomics, the ISR…

Sail is not at the register-transfer level (RTL) [1].

Why? Because
Sail does not offer abstractions for clocked digital circuits, which is what characterises the RTL. The most widely used DSL for the RTL is (System)Verilog [3].
Instead, Sail is a stand-alone DSL for the ISA (= instruction set architecture). The purpose of the ISA level is to talk about that a processor looks from the outside, to the programmer (most specifically to the compiler writer). Sail is a minimal programming language with a single purpose: writing ISA specifications, which means writing an interpreter for assembly language.
Technically, Sail is a simple imperative language with first-order functions. What makes Sail suitable for specifying ISAs is its typing system. Sail supports
types that are frequently used in ISA interpreters, such as dependent typing for numeric types and bitvector lengths. Sail is closely related to Arm's ASL (= architecture specification language) [2].

Since Sail is Turing-complete, any ISA can be modelled, including Mill. For the same reason any RTL can be modelled, for example by coding up an interpreter for an RTL language like Verilog, but that would be mighty inconvenient.

[1] https://en.wikipedia.org/wiki/Register-transfer_level

[2] https://alastairreid.github.io/ARM-v8a-xml-release/

[3] https://en.wikipedia.org/wiki/Verilog

> I've never known any of XML's features to help with actually solving a business problem.

Arm are publishing their full ISA processor specifications in XML, so it is 100% machine readable, see [1] for the actual specification and [2, 3] for why you want a machine readable ISA spec in the first place. Arm has been really ahead with this, and all the other processor manufacturer are playing catchup.

I'm not saying that XML is the idea format for this purpose, but it clearly works for them. Which other format would you think is better for this purpose? Miminal requirements:
works for gigabytes of data including graphics, automatic format checking, conversion to/from other formats, widely supported, easy to hire for, standard IDEs (e.g. VSCode plugins), long-term stability (processors need support for decades).

[1] https://developer.arm.com/architectures/cpu-architecture/a-profile/exploration-tools

[2] https://alastairreid.github.io/papers/fmcad2016-trustworthy.pdf

[3] https://alastairreid.github.io/uses-for-isa-specs/

Came here to say the same thing, and add that GNU Octave is pretty good too. Its libraries didn't seem as diverse as MATLAB's when I tried it, but since it's open source, maybe that's changed.

Also when I tried SSE and AltiVec about 20 years ago for SIMD, they were really fast, but I was flabbergasted that the instructions were fixed-length. I wanted something more like the x86 string instructions so that I could fused-multiply-add arrays of floats without having to manually unroll loops to process 4 elements at a time:

https://docs.oracle.com/cd/E19120-01/open.solaris/817-5477/eoizn/index.html

Looks like Arm is trying to do variable-length vectors with Scalable Vector Extension (SVE) but it's limited to 2048 bits, which is unfortunate IMHO:

https://developer.arm.com/documentation/101726/0400/Learn-about-the-Scalable-Vector-Extension--SVE-/What-is-the-Scalable-Vector-Extension-

https://alastairreid.github.io/papers/sve-ieee-micro-2017.pdf

https://www.youtube.com/watch?v=eGCcPo4UAHs

There has been a steady industry of people retyping the manuals of all the major architectures for use in formal verification. At PLDI last year, there was even a paper where a team used synthesis techniques to automatically generate an instruction spec for x86 by generating tests for processors and using the answers to refine their current guess.

And within ARM, there were lots of people transcribing bits of the ARM manual into various forms: C/C++, LLVM .td files, Verilog, spreadsheets, etc. Apart from all the wasted effort, this also created a verification problem: each transcription had its own set of bugs that now had to be fixed. And it missed a verification opportunity: if everyone used the same master copy then each time one group spots a bug and reports it, the spec gets better for everybody.
I talked about this virtuous cycle at S-REPLS last year: https://alastairreid.github.io/papers/srepls4-trustworthy.pdf (S-REPLS is a programming language seminar in SE England.)