Category Archives: Events

ERTS 2014: Integrated and Simpler Systems

I attended last week the 7th edition of the congress on Embedded Real Time Software and Systems that takes place in Toulouse (France) every two years. It started with Joseph Sifakis inviting all of us to work on the integration of embedded systems with Internet, and the Engineering Executive Vice-President of Airbus, Charles Champion, describing the many future challenges of avionics and asking, maybe surprisingly, for simpler software and systems to meet these challenges.

At the software level, I see two important trends contributing to these goals: model-based development and formal methods. The former because it facilitates communication between systems and software engineers, at the right level of abstraction, the latter because it makes the verification of these ever larger and integrated systems tractable thanks to abstraction and automation. No surprise then that both were very much present in presentations at the conference. A difference with previous years was that many of these presentations were backed by large industrial case studies. For example, for model-based development, the use of MBD in the context of DO-178C at Airbus Military, and for formal methods, the use of Event-B for requirements verification at BAE Submarine. The most interesting trend for me was the combination of model-based development and formal methods to manage greater integration between systems. We described such a workflow in our paper on System to Software Integrity. I expect more of these in the next edition.

Another highlight of this conference for me was certification, with two sessions dedicated to New Trends in Certification, among which a majority of papers on formal methods (5 papers). It will be interesting in the years to come to follow progress on the convergence of certification domains on the issues of tool qualification and formal methods.

Also posted in Certification | 1 Comment

Future Version of SPARK Will Be Based on Ada 2012

At the SPARK User Day yesterday in Bath, Altran-Praxis and AdaCore announced that the SPARK language will undergo a major transformation, to both extend the subset of Ada included in SPARK, and to use the new specification features of Ada 2012 instead of special comments like in today’s SPARK language. This is only fair that, SPARK annotations being the source of inspiration for many of the new specification features in Ada (pre- and postconditions, quantified expressions, etc.), their executable Ada version is now included in SPARK. This future version is expected to be released Q1 2014.

This is something we have been working on for almost 3 years now, between Altran-Praxis and AdaCore, inside the Hi-Lite project. We have been able to show that, not only we can extend the range of programs which can be proved automatically correct with respect to their specification, but we can combine much more easily testing and formal verification than what was considered possible until now.

Given the results achieved already, some (like the Microsoft researcher Rustan Leino who asked me this question at the SPARK User Day) could wonder why we don’t plan to release a product sooner. This was answered by a current SPARK customer, Robert Dorn from Secunet, who said that they want “first, that the future SPARK language and toolset allows them to express and prove as much as the existing one, and only then, that it extends the language and provides improved and new tools”. The work done in Hi-Lite is mostly concerned with automatic proof of functional properties. We are now working also on the expression and verification of data and information flow properties that are so important for many SPARK users.

We will continue to provide GPL releases of prototypes of these future tools to the community in 2013.

Also posted in Open Source | Tagged , , | Leave a comment

Use of formal methods in critical systems conference

This conference will take place in Toulouse on November the 12th. It is in French as is the announcement providing more details below:

Les animateurs du DAS Systèmes Embarqués, avec le soutien du thème IFSE du RTRA AE/SE, ont le plaisir de vous annoncer la programmation d’un cycle de conférences techniques sur les méthodes formelles de développement. Non, ne partez pas tout de suite : les méthodes formelles sont faites pour vous !

Ces méthodes ne sont pas assez connues mais ont un potentiel énorme pour faire progresser la productivité ET la qualité intrinsèque des développements de logiciels embarqués et de leurs outils de développement et de vérification. Et elles ne sont pas si difficiles à mettre en œuvre : certains l’ont déjà fait, avec succès, pourquoi pas vous ?

Nous vous proposons donc un cycle de conférence/forum pour vous présenter bien sûr les fondements théoriques de ces méthodes, mais surtout faire un état de l’art et de la pratique, démystifier, échanger, et pourquoi pas monter ensemble des projets pour “passer à l’acte” ? Les intervenants seront à la fois des scientifiques et universitaires les plus compétents dans ces domaines et des utilisateurs “de terrain” qui ont déjà pratiqué ces méthodes et vous livreront leurs retours d’expérience.

La première conférence de ce cycle aura lieu le mardi 13 Novembre 2012 à l’IAS, 23 Avenue Edouard Belin, Toulouse, sur le thème de “l’Utilisation des méthodes formelles dans les systèmes critiques”.

Read More »
Also posted in Certification | Tagged , , | Leave a comment

GNATprove Distinguished at VerifyThis Competition

I participated last week in the VerifyThis Verification Competition, which took place on Thursday afternoon during the Formal Methods 2012 conference in Paris. The goal was to apply verification tools to three small challenge programs, to compare approaches and learn from each other’s tools.

I used Ada 2012 as a programming and specification language (using preconditions and postconditions to specify contracts for subprograms) and our prototype GNATprove, a proof tool developed in project Hi-Lite, to formal verify that the code implements its contract and does not raise run-time errors (integer overflows, array index out of bounds, etc.) I completed challenge 1 and I did a part of challenge 2, but I had not enough time to complete it or start on challenge 3.

The competition was followed on Friday by a very interesting explanation session where each team showed how it addressed the problems with its tools. It was particularly interesting to see different solutions from teams using the same language (for example, the two teams using Why3 had quite different solutions for challenge 2), as well as the interaction between the user and the proof tool in KIV, KeY, Why3, etc. I think the problems and their solutions will be added soon to the VerifyThis repository, but if you cannot wait, you can also ask the organizers for a tarball of the submissions.

To come to the title of this post, the organizers awarded a distinction to GNATprove for its integration of proving and run-time assertion checking, of which I’m very proud. As I explained them, this integration was essential in helping me during the competition:

  • For the first problem, I was stuck with a postcondition that I could not prove, and I did not manage to figure out why. So I decided to write a small test to make sure at least that the code and the contract were not contradictory. I executed it, and it raised an exception saying the postcondition was wrong! (because Ada 2012 contracts are executable, the compiler can transform them into run-time assertions, including quantifiers that are transformed in loops) It was then easy to pinpoint the root cause of the problem, the use of “<" instead of "<=" in the test of the main loop.
  • For the second problem, I decided to implement the iterative version of the algorithm, which is more complex to specifiy and verify than the recursive one, but also more representative of critical embedded software. The algorithm is divided in two passes, each one performing two nested loops on the input array, with loop invariants to write for the proof to go through. Being able to execute these loop invariants as regular assertions made me quite confident that I had not written wrong assertions, before I even start proving something.

Hope to see even more participants at the next software verification competition, either VSTTE’s one or VerifyThis!

Posted in Events | Tagged , , , , | 1 Comment

Safe and reliable embedded linux programming

Dr José Ruiz gave this talk at yesterday’s Embed with Linux conference in Lorient, France. The talk provides an overview of techniques to design and implement reliable embedded applications. The goal is to achieve safe and analyzable behavior by construction, including handling parallel multiprocessor systems in an efficient and predictable way. The means to attain this objective is to statically configure the application to run on embedded linux platforms, and then to use run-time support to enforce constraints imposed to the system.

Also posted in Certification, Papers and Slides | Leave a comment

Hi-Lite team paper at FM 2012

The 18th edition of the International Symposium on Formal Methods organized by Formal Methods Europe will take place at the CNAM in Paris this August. A paper on the work being undertaken by the Hi-Lite team on “Maximal and Compositional Pattern-Based Loop Invariants” will be presented there.

Below is the abstract:

“We present a novel approach for the automatic generation of inductive loop invariants over loops manipulating arrays. Unlike most existing approaches, it generates invariants containing disjunctions and quantifiers, which are rich enough for proving functional properties over programs which manipulate arrays. Our approach does not require the user to provide initial assertions or postconditions. It proceeds by recognizing through static analysis simple code patterns that respect stability properties on accessed locations, on an intermediate representation of parallel assignments. We associate with each pattern a formula that we prove to be a so-called local invariant, and we give conditions for local invariants to compose an inductive invariant of the complete loop. We also give conditions over invariants to be locally maximal, and we show that some of our pattern invariants are indeed maximal.”

Also posted in Related Initiatives | Tagged , , | Leave a comment

Integrating Formal Program Verification with Testing

This is the paper that Yannick Moy presented at the recent ERTS 2012 conference:
Verification activities mandated for critical software are essential to achieve the required level of confidence expected in life-critical or business-critical software. They are becoming increasingly costly as, over time, they require the development and maintenance of a large body of functional and robustness tests on larger and more complex applications. Formal program verification offers a way to reduce these costs while providing stronger guarantees than testing. Addressing verification activities with formal verification is supported by upcoming standards such as do-178c for software development in avionics. In the Hi-Lite project, we pursue the integration of formal verification with testing for projects developed in C or Ada. In this paper, we discuss the conditions under which this integration is at least as strong as testing alone. We describe associated costs and benefits, using a simple banking database application as a case study. The full paper can de downloaded here.

Also posted in Certification, Open Source, Open-DO News, Papers and Slides | Tagged , , , , | Leave a comment

Compilation of Heterogeneous Models: Motivations and Challenges

This is the paper that Matteo Bordin presented at the recent ERTS 2012 conference:
The widespread use of model driven engineering in the development of software-intensive systems, including high- integrity embedded systems, gave rise to a “Tower of Babel” of modeling languages. System architects may use languages such as OMG SysML and MARTE, SAE AADL or EAST-ADL; control and command engineers tend to use graphical tools such as MathWorks Simulink/Stateflow or Esterel Technologies SCADE, or textual languages such as MathWorks Embedded Matlab; software engineers usually rely on OMG UML; and, of course, many in- house domain specific languages are equally used at any step of the development process. This heterogeneity of modeling formalisms raises several questions on the verification and code generation for systems described using heterogeneous models: How can we ensure consistency across multiple modeling views? How can we generate code, which is optimized with respect to multiple modeling views? How can we ensure model-level verification is consistent with the run-time behavior of the generated executable application?

Read More »
Also posted in Papers and Slides | Leave a comment

Certification, Safety and Security at ERTS 2012

We are now leaving the Embedded Real Time Systems and Software conference which was held in Toulouse for the last 3 days. The conference has been expanding since the last occurrence in 2010, with more international presence, many German companies in particular, and a large number of companies from the automotive industry (maybe this is related? :) ).

I was particularly interested in the increasing concern over techniques to address safety and security. Safety is not new in avionics/aerospace, but security is, and both safety and security are quite new for automotive. The key to understanding these concerns is the recent release of new safety certification in both avionics (DO-178C) and automotive (ISO-26262). Both put some emphasis (not at the same level, as one could expect) on static analysis and formal techniques.

Like two years ago, there were many presentations of work on formal methods and modelling, with many formal methods applying to modelling. Next episode in two years!

Posted in Events | Tagged | Leave a comment

Prove & Fly!

On December 5-6, I participated in the 2nd workshop on Theorem Proving in Certification, in Cambridge (UK). This turned out to be even more interesting than last year’s program promised.

The goal of the workshop is to clarify under which conditions theorem proving can be applied in the context of DO-178C Formal Methods Supplement (hence Prove & Fly!):

  • extent of verifications performed
  • cost/benefit compared to testing
  • characteristics of a technique/tool to be called theorem proving
  • tool qualification needs

The workshop was organized around a common challenge (gear nose challenge) which all participants were invited to address from different angles. The challenge was to compute the velocity of the nose gear of a plane while on the ground. This was made even more interesting by the need to comply with a small certification standard (Tamarack standard). Both the challenge and the certification standard were created by Jeff Joyce from CSL.

Besides sharing the strategy we follow in project Hi-Lite, and showing how it applied to the common challenge, I was very interested in the discussions we had over tool qualification and the alternate objectives to coverage in DO-178C, when using formal verification instead of testing. An interesting shared opinion was that the automatic prover does not need to be qualified if it generates a trace that can be double-checked independently by a theorem prover (based on a small set of induction rules). For example, that’s the case for CVC3. In the discussion on alternate objectives to coverage, Jeff Joyce clearly stated that the underlying goal is to detect incompleteness of specifications, or equivalently (from the opposite point of view) unintended functionalities. During the discussion, it appeared that we may be able to use either model checking to perform a symbolic coverage analysis, or information given by automatic provers stating which hypotheses (and thus source code constructs) were used in proofs, but for example not concolic testing which is based on source code.

Many of these subjects will need to be further explored as DO-178C is adopted in new projects and tools based on formal methods are applied in this context. In particular, I look forward to the evolutions of the Tamarack standard and new solutions to the gear nose challenge. Hot news: Open-DO will host the workshop forge and wiki to support these evolutions. :)

Also posted in Certification | Tagged , , | Leave a comment
  • Categories

  • Open-DO Projects

  • Want to get involved?

  • Contact

    info @ open-do.org