Productivity Improvement of Data Consistency in Transportation Models

From Evidence on Formal Methods Uses and Impact on Industry
Jump to: navigation, search
Success Story
Domain Transportation
Keywords B-Methods, assumption validation, model-checking, ProB tool
Source Siemens, University of Düsseldorf (DEPLOY)

Main -> DEPLOY Success Stories -> Transport-2

Short description

The correct and safe behaviour of Metro models developed by Siemens rely on assumptions made on the topology of each specific site. Those assumptions have to be validated against a number of properties required on the model. Until now this task was achieved through custom rules in AtelierB which was not very efficient at proving them automatically: it required a lot of manual work, about one person-month for a typical metro project.

As alternative to a proof-based approach, model checking with the ProB model-checker was successfully applied to this task. A dramatic productivity improvement was experienced on a real project (San Juan metro line): the same faults could be discovered totally automatically and within a few minutes of execution time whereas the previous approach required about one man-month of effort.

Related FAQ

of Interest to Project and QA Managers

  • QI-PQAM-2 How is the productivity of the various stages of the system development cycle affected when formal engineering methods are used ?
  • ExFac-HM-1 What is the position of standards regarding formal methods in my Industry segment? (e.g. are they enforcing, highly recommending, etc.)

of Interest to Engineers and Analysts

  • TOOL-EA-2 Are tools functionality automating all tedious tasks?

Benefits

  • Dramatic productivity improvement for the problem of data validation
  • Better diagnostics of failed property using output

Limitations

  • Specific problem to transportation domain, extensibility to other sector to be studied
  • ProB-Tool must undergo qualification/certification (on-going)

Elaboration

The success story is fully described in the paper [1] and its qualification report is an internal deliverable of the DEPLOY Project. We highlight here the main arguments and lessons learned:

  • Full automation and quick response time: checking the properties takes 4.15 seconds, and checking the assertions takes 1017.7 seconds (i.e., roughly 17 minutes) using ProB 1.3.0- final.4 on a MacBook Pro with 2.33 GHz Core2 Duo. Manually it takes a month for one person to solve the same problem (San Juan line).
  • Easier diagnostics: another advantage of model checking over proof is that it provides a counter example that will be of greater help in understanding the cause than the information found in a failed proof. Furthermore, a specific visualisation tool was developed to even further enhance and quicken the process of understanding a counter example.
  • Confidence in the results. An important issue is the qualification of the tool in order to fully have confidence in the results produced. With respect to this, the model-checking approach implemented has some form of redundancy: a property is expressed in positive and in negative form. The produced result should be consistent otherwise it is indicative of a problem. This problem could be located at lower levels (actually 2 bugs in the Prolog interpreter where discovered). The absence of problem is however not a guarantee of correctness and does not remove the need of tool validation (identified as further work).
  • Qualification process: In order to be used as a correctness argument in the development process of a qualified product, the tool must be qualified itself. Without such qualification, the tool might be used like a debugger is used by developers, to speed up development time, and to perform a manual verification only when one has high assurance that the verification will succeed. Nevertheless, the tool has undergone a qualification process. The qualification argument is based mainly on testing of various parts of the tool, and on the implementation of internal sanity checking mechanisms to check that the tool it consistent with itself. Two testing approaches were deployed in parallel: global end-to-end testing on industrial cases and unit testing of specific internal modules. Part of the unit testing involved automatically generated test cases. Furthermore, a second independent tool was used to double-check the results of some unit tests.

An additional lesson learned for academics is the need to cover the full language used in industry while prototyping. As the industry will generally not adapt their models to suit an academic tool, the industrialisation phase will need to consider the extension of the tool. The amount of work for evolving towards the industry should be evaluated early enough in the R&D process. The evidence is already a success as Siemens plans to replace Atelier B by ProB for the task of data validation regarding formal properties. It requires the validation of ProB for SIL4 use which is being investigated.

Related Work

Model-checking was tried in the past in the railways domain to validate some interlocking properties. Specific properties (robustness and locality) allowed optimization to the general CTL algorithm. The case was only validated on a small railway interlocking involving two stations [2]. A CSP approach was also investigated together with the FDR model-checker [3]. Useful counter examples related to safety requirements could be produced on some examples. However, a conclusion was that the languages based on process algebra like CSP is not adequate for modelling this domain (especially for control table). It led to model that were difficult to understand and validate by practitioners.

Specific Deploy Contributions

  • Some optimisations were specifically developed to improve the efficiency of ProB: the handling of large sets and improved constraint propagation.
  • Development of an industrial strength parser for B and improved type inference
  • Graphical visualisation of failed properties

Further work

  • Tool qualification (on-going)

References

  1. Michael Leuschel, Jérôme Falampin, Fabian Fritz and Daniel Plagge, Automated Property Verification for Large Scale B Models, in Proc. Formal Methods Second World Congress FM 2009, Eindhoven, The Nederlands, November 2009.
  2. Eisner, C. Using Symbolic Model Checking to Verify the Railway Stations of Hoorn-Kersenboogerd and Heerhugowaard. In Proceedings of the 10th IFIP WG 10.5 Advanced Research Working Conference on Correct Hardware Design and Verification Methods, September 27 - 29, 1999.
  3. Winter, K. Model checking railway interlocking systems. In Proceedings of the Twenty-Fifth Australasian Conference on Computer Science - Volume 4 (Melbourne, Victoria, Australia, 2002.


Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox