Skip to content
Back to the collection

Safe Pointers in SPARK 2014

Georges-Axel Jaloyan

2017 · arXiv

Read the paper
HN score
1
Mentions
5
Readers
3
Months
5
What’s in a score?

From the abstract

In the context of deductive software verification, programs with pointers present a major challenge due to pointer aliasing. In this paper, we introduce pointers to SPARK, a well-defined subset of the Ada language, intended for formal verification of mission-critical software. Our solution is based on static alias analysis inspired by Rust's borrow-checker and affine types, and enforces the Concurrent Read, Exclusive Write principle. This analysis has been implemented in the GNAT Ada compiler and tested against a number of challenging examples including parts of real-life applications. Our tests show that only minor changes in the source code are required to fit the idiomatic Ada code into SPARK extended with pointers, which is a significant improvement upon the previous state of the art. The proposed extension has been approved by the Language Design Committee for SPARK for inclusion in a future version of SPARK, and is being discussed by the Ada Rapporteur Group for inclusion in the next version of Ada. In the report, we give a formal presentation of the analysis rules for a miniature version of SPARK and prove their soundness. We discuss the implementation and the case studies, and compare our solution with Rust.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

5 selected excerpts · 5 total mentions

johnisgood
Recommendation · rule
I would recommend https://www.adacore.com/uploads/books/pdf/ePDF-Implementatio... for more information regarding contracts. There are of course a LOT more, just fire up your preferred search engine and enjoy your findings. :) > SPARK builds on the strengths of Ada to provide even more guarantees statically rather than dynamically. As summarized in the following table, Ada provides strict syntax and strong typing at compile time plus dynamic checking of run-time errors and program contracts. SPARK allows such checking to be performed statically. In addition, it enforces the use of a safer language subset and detects data flow errors statically. Contract programming: - Ada:…
Read the full comment
dynamic - SPARK: dynamic / static Run-time errors: - Ada: dynamic - SPARK: dynamic / static Data flow errors: - Ada: - - SPARK: static Strong typing: - Ada: static - SPARK: static Safer language subset: - Ada: - - SPARK: static Strict clear syntax: - Ada: static - SPARK: static --- Additionally, safe pointers in SPARK: https://blog.adacore.com/using-pointers-in-spark and https://arxiv.org/abs/1710.07047. --- Cryptographic library in SPARK 2014: https://github.com/Componolit/libsparkcrypto. > libsparkcrypto is a formally verified implementation of several widely used cryptographic algorithms using the SPARK 2014 programming language and toolset. For the complete library proofs of the absence of run-time errors like type range violations, division by zero and numerical overflows are available. Some of its subprograms include proofs of partial correctness. --- Ada/SPARK is excellent for real-time and safety-critical software: https://www.rcs.ei.tum.de/fileadmin/tueircs/www/becker/spark... to give you some ideas. It may be a bit outdated in some regards, though, for example: "Next version of SPARK 2014 under development (pointers!).". It is already done! :)
thesuperbigfrog
Neutral mention · rule
Probably SPARK (programming language derived from Ada with advanced proof capabilities). The next release of SPARK will support pointer ownership similar to the Rust borrow checker: https://blog.adacore.com/using-pointers-in-spark https://arxiv.org/pdf/1710.07047.pdf Concurrency in Ada is very easy. I haven't used SPARK enough to be familiar with its concurrency, but it looks very similar to Ada, but with added restrictions to allow for proofs: https://docs.adacore.com/spark2014-docs/html/ug/en/source/co...
nickpsecurity
Neutral mention · rule
“but after studying many other ICO, I am convinced now that this is not just a short-lived fad, but a real new model to fund projects, and especially open-source projects related to blockchains.” There’s been quite a few of us suggesting people jump into blockchain just to get funding for more important stuff (e.g. language-level tooling or libraries) they’ll produce as part of the coin offering they sell to investors. Plus, with the focus on correctness, it’s easier than ever to get the private sector to invest in high-assurance tooling. Problem is they keep trying to clean-slate everything when there's piles of work to build on with better benefits in the long term. And…
Read the full comment
this work is hard even when doing simple things if you want end result to be widely usable. So, you better have a good justification for trying to redo decades worth of hard work on your own with some VC funding. Anyone wanting a shortcut should build your language on top of capabilities of the SPARK Ada language [1] with this book [2]. Your smart contracts get all the benefits it currently offers plus whatever extra you build plus whatever they build with the influx of money for Pro edition. Recent projects already add some pointer [3] and floating-point [4] safety to what they already mostly automate with that tooling. This is also a mature tool whose development and commercial use goes back decades [5]. [1] https://en.wikipedia.org/wiki/SPARK_(programming_language) [2] https://www.amazon.com/Building-High-Integrity-Applications-... [3] https://arxiv.org/abs/1710.07047 [4] http://lists.forge.open-do.org/pipermail/spark2014-discuss/2... [5] http://www.spark-2014.org/uploads/itp_2014_r610.pdf
johnisgood
Neutral mention · rule
It can employ, but you do not have to (you can turn off all runtime checks and use formal verification only, something that Rust cannot do (statically verify correctness the same way you can with SPARK using GNATprove)), it can all be done at compile-time with Ada/SPARK. > These runtime checks[1] are costly, both in terms of program size and execution time. It may be appropriate to remove them if we can statically ensure they aren't needed at runtime, in other words if we can prove that the condition tested for can never occur. > This is where the analysis done by GNATprove comes in. It can be used to demonstrate statically that none of these errors can ever occur at…
Read the full comment
runtime. Specifically, GNATprove logically interprets the meaning of every instruction in the program. Using this interpretation, GNATprove generates a logical formula called a verification condition for each check that would otherwise be required by the Ada (and hence SPARK) language. Additionally, in Ada/SPARK, you can formally verify tasks (concurrency), too: https://docs.adacore.com/spark2014-docs/html/ug/en/source/co.... Moreover: > SPARK builds on the strengths of Ada to provide even more guarantees statically rather than dynamically. As summarized in the following table, Ada provides strict syntax and strong typing at compile time plus dynamic checking of run-time errors and program contracts. SPARK allows such checking to be performed statically. In addition, it enforces the use of a safer language subset and detects data flow errors statically. Contract programming: - Ada: dynamic - SPARK: dynamic / static Run-time errors: - Ada: dynamic - SPARK: dynamic / static Data flow errors: - Ada: - - SPARK: static Strong typing: - Ada: static - SPARK: static Safer language subset: - Ada: - - SPARK: static Strict clear syntax: - Ada: static - SPARK: static Additionally, safe pointers in SPARK: https://blog.adacore.com/using-pointers-in-spark and https://arxiv.org/abs/1710.07047. More information about Get_Line (i.e. even where you would think you cannot go static): https://blog.adacore.com/formal-verification-of-legacy-code. [1] overflow check, index check, range check, divide by zero

Keep following the thread.

More in Programming languages

More from the same topics.