Armada: Low-Effort Verification Of High-Performance Concurrent Programs

This paper appeared inward PLDI 2020 together with is authored yesteryear Jacob R. Lorch, Yixuan Chen, Manos Kapritsos, Bryan Parno, Shaz Qadeer, Upamanyu Sharma, James R. Wilcox, together with Xueyuan Zhao.

The newspaper presents the Armada framework for code-level verification of concurrent (multithreaded rather than distributed) programs. Armada is roughly a stepwise-refinement extended version of Dafny. So that is where I volition laid about explaining.

Dafny

Dafny is an open source iterative compiled linguistic communication for writing verified code. The code is verified with honor to the specifications the developer writes yesteryear adding high-level annotations with the code, such every bit ensures P together with invariant P. At https://rise4fun.com/Dafny/tutorial y'all volition uncovering an interactive tutorial, that volition larn y'all upwards together with running proving programs with Dafny. It is actually fun, y'all should endeavour this out now! 

Dafny leverages Z3 for discharging proof obligations. Ok, together with thus what is Z3?

Z3 is a pop opened upwards source Satisfiability modulo theories (SMT) solver. SMT is a determination employment for logical formulas expressed inward classical first-order logic with equality (propositional logic+ quantifiers + relations). You tin mean value of Z3 every bit formalizing constraint programming. Again delight give this interactive Z3 tutorial a endeavour at  https://rise4fun.com/z3/tutorial.

*check-sat* determines whether the electrical flow formulas on the Z3 stack are satisfiable or not. 

• If the formulas are satisfiable, Z3 returns *sat*
• If they are unsatisfiable, Z3 returns *unsat* 
• Z3 may likewise render *unknown* when it can't determine whether a formula is satisfiable or not

If y'all similar to utilisation Z3 every bit purpose of a higher degree language, Z3 bindings are available for Python, C, C++, Java, Rust, etc.

Armada

Armada leverages on Dafny together with provides an opened upwards source framework for developing verified concurrent systems code via stepwise refinement. It provides 8 verified libraries for performing refinement-based proofs, including region-based pointer reasoning, rely-guarantee, TSO elimination, together with reduction.

Armada's destination is to examine that the implementation refines the specification (i.e., all finite behaviors of the implementation imitate the specification). To span the semantic gap betwixt the implementation together with the specification, the developer writes a serial of north Armada programs. 

• each couplet of following levels should live on similar plenty to facilitate automatic generation of a refinement proof that respects R
• the developer supplies a brusk proof recipe that gives Armada plenty information to automatically generate such a proof
• Armada uses Dafny to verify all proof cloth generated

Here is an event of Armada specification together with implementation of Traveling Salesman Problem. 

And hither is an event of an intermediate stepwise refinement for TSP.

Armada considers 8 strategies for the refinement framework: Reduction, Rely-guarantee reasoning, TSO elimination, Weakening, Nondeterministic weakening, Combining, Ghost variable introduction, together with Variable hiding.

The implementation of Armada consists of

• a state-machine translator to interpret Armada programs to state-machine descriptions (built over Dafny's parser together with type inference engine)
• a framework for proof generation (built over Dafny's abstract syntax tree AST code)
• a library of lemmas useful for invocation yesteryear proofs of refinement (6KLOC Dafny)
• and an extension of Dafny to interpret Armada AST into C compatible with CompCertTSO

The evaluation is performed on 4 examples: Barrier, Pointers, MCSLock, Lock-free queue from liblfds library. The graph shows that afterwards Armada verification the CompCertTSO verified compilation of the code is every bit efficient every bit that of compiling with GCC an unverified compiler, which is every bit efficient every bit a hand-written version of liblfds implementation (using modulo rather than bitmask).

Discussion 

Armada is a company stride inward the correct direction, simply it withal has several drawbacks. The framework requires a *competent* human inward the loop for performing the verification. The human should lift one's hear how to dissever the refinement steps together with operate with the framework to demonstrate the refinement proofs for each step. My impression is that Armada is withal for pocket-sized programs. Also Armada tin alone examine security properties simply non liveness, together with it cannot verify hyperproperties due to the rootage company logic requirement imposed yesteryear Z3. 

It may live on cumbersome trying to feed the proof recipes/hints to the proof arrangement without feedback nearly why this didn't work. Without feedback from the proof system, how long would a developer live on able to proceed the process? This is to a greater extent than or less other element that may brand adoption of this hard yesteryear non-expert users.

On the other hand, Armada provides a goodness choice for verifying critical multithreaded programs. Just yesteryear using the same language/framework, y'all tin generate provably verified code. It is overnice that everything is nether the same roof. The trusted code base of operations inward this framework is the Armada compiler, Dafny, Z3, Boogie.

Share this post