[PDF] Live-Verification While Programming:

View - Download Live-Verification While Programming:

Previous PDF

Next PDF

Live-Verification While Programming:

Dafny

Image Source: https://www.microsoft.com/

Master Seminar -Summer term 2020

Presented by: Philippe Heiler

ƒDafny was developed by K. Rustan M. Leinoat Microsoftin 2008 ƒPart of Microsoft Research RiSE(Research in Software Engineering)

ƒLiveVerification Language

ƒCross Language Compiler to

ƒJavaScript, Go, .NET Languages

ƒSupports

ƒGeneric Classes

ƒDynamic Allocation

ƒSpecification Constructs

ƒPre-and Post-Conditions

ƒGhost State

ƒDynamic Frames

ƒProof of Termination

Introduction

2

Image Sources:

https://www.microsoft.com/ RiSE ƒPre-and Post-Conditions ( requiresand ensures) are checked beforecompilation ƒWorks similar to Typingconstraints in other programming languages like C# or Java ƒDafny analyzes possible code paths, to validate the solvabilityof the given specifications ƒThis assures that certain specificationsare complied beforeand aftermethod execution ƒPreconditionsneed to be ensured beforethe Methods Body ƒPostconditionsneed to be ensured afterthe Methods Body

Pre-and Post-Conditions

3 ensures requirescall()return()

Image Source: https://www.iconfinder.com/data/icons/online-marketing-hand-drawn-vol-2/52/development__code__script__web__tag__root__browser-512.png

ƒEverything that is specified as ghost is only considered by the Verifier, and will be completely ignoredby the Compiler ƒVariables can be initialized as Ghost Variables

ƒGhostMethods are called Functions

ƒGhost Variables and Functions are prohibitedto influence normal

Variables and Methods

ƒThis is also checked by the Verifier

Ghost State

4Image Source: https://cdn3.iconfinder.com/data/icons/sweet-halloween/512/Sweet_Halloween_Ghost-256.png

ƒDynamic Frames assure that only the selected objects can be accessedby the current Method be alteredby the current Method readby the current Method ƒThe selection is recursive complete, which means every object that is a parameter of the selected object (and so on) will also be accessible.

Dynamic Frames

5Image Source: https://www.flickr.com/photos/d_pham/8072408810/

ƒDafny can check if a Method with Loopsand / or Recursionwill terminate eventually ƒThe termination proof will only take seconds, even if the programs termination itself could need years

ƒE.g. recursive Ackermannor Fibonacci

6Image Source: https://pixabay.com/photos/pocket-watch-time-of-sand-time-3156771/

Proof of Termination

ƒDafny can check if a Method with Loopsand / or Recursionwill terminate eventually ƒThe termination proof will only take seconds, even if the programs termination itself could need years

ƒE.g. recursive Ackermannor Fibonacci

7Image Source: https://de.wikipedia.org/wiki/Alan_Turing#/media/Datei:Alan_Turing_Aged_16.jpg

Proof of Termination

WAIT A MINUTE !?

(Pun not intended)

Isn't that the Halting-Problem ?

Why can Dafny solve NP Complete ??

ƒDafny can check if a Method with Loopsand / or Recursionwill terminate eventually ƒThe termination proof will only take seconds, even if the programs termination itself could need years

ƒE.g. recursive Ackermannor Fibonacci

ƒDafny will analyze the termination with the help of the

ǀariable decreases towards it's halting anchor

ƒThis works for Loopsand Recursion, but there could still be algorithms that can notbe proven to terminate ƒThis will result in a verification timeout and a warning

8Image Source: https://rise4fun.com/Dafny/

Proof of Termination

ƒHow can Dafny verify all those things ?

ƒDafny uses an Intermediate Verification

Language calledBoogie (Microsoft)

ƒBoogie is able to translate specifications defined by Dafny into ƒThose Mathematical Formulas will then be solved by the

SMT-Solver Z3(Microsoft)

ƒThis will result in a feedbackif (e.g.) a Pre-or Post-Condition can be fulfilled or not

How ? Magic ?

9Image Source: https://ethz.ch/content/dam/ethz/special-interest/infk/chair-program-method/pm/documents/Education/Theses/Alexandru_Dima_RS_report.pdf

SMT Solver

10Image Sources: http://algos.inesc-id.pt/projectos/projects/projects/nanotime/ref12.pdf

Satisfiability

Modulo

Theories

ƒAbstract Classes are called Traits

ƒClasses may extendother classes or Traits

ƒConsist of Constructor, Variablesand Methods

ƒVariables can be initialized as Ghost Variables

Specification -Classes

11Image Source: https://www.dcc.fc.up.pt/~nam/web/resources/vfs20/DafnyQuickReference.pdf

ƒHas multipleInput and Output Parameters

ƒUses Pre-and Post-Conditions

ƒUses Dynamic Frames to manage Memory Access

ƒProofsTermination of Loops and Recursive Methods

ƒGhostMethods are called Functions

Specification -Methods

12Image Source: https://www.dcc.fc.up.pt/~nam/web/resources/vfs20/DafnyQuickReference.pdf

Example: Queue Datastructure

13Image Source: https://www.flickr.com/photos/hktang/4243300265

Not Empty

Swinging Pivot Restriction

Old Queue but WITHOUT

the first entry

Function Body

Dynamic Frame

Literature

14

Introduction and Theory:

ƒ'Dafny: An automatic program verifier for functional correctness' (K. Rustan M. Leino, 2010) ƒ'Specification and Verification of Object-Oriented Software' (K. Rustan M. Leino, 2010)

Programming Documentation:

ƒ'Dafny Reference Manual' (Richard L. Ford et al. 2017)

Try out Dafny:

( https://github.com/dafny-lang/dafny/releases ) ( https://rise4fun.com/Dafny/ ) Image Source: https://pixabay.com/de/photos/literatur-buch-weisheit-bibliothek-3324023/quotesdbs_dbs14.pdfusesText_20

[PDF] icpe

[PDF] icpe autorisation déclaration

[PDF] icsi institut pour une culture de sécurité industrielle

[PDF] ict technical business analyst

[PDF] ictaal pdf

[PDF] ictarn pdf

[PDF] idcc 2216

[PDF] iddri adresse

[PDF] iddri biodiversité

[PDF] iddri climat

[PDF] iddri institut

[PDF] iddri recrutement

[PDF] ide en ehpad definition

[PDF] idéa agricole

[PDF] idea agriculture durable