Mbeddr C: Spracherweiterung und formale MethodenMbeddr C: Spracherweiterung und formale Methoden...

Mbeddr C: Spracherweiterung

und formale Methoden

Markus Voelter independent/itemis

voelter@acm.org

www.voelter.de voelterblog.blogspot.de

@markusvoelter +Markus Voelter

Daniel Ratiu ForTISS GmbH

ratiu@fortiss.org

www.fortiss.org

Bernd Kolb itemis AG

kolb@itemis.de

www.itemis.de

@berndkolb +Bernd Kolb

Intro

0

Main Points

More and more software is used in embedded

systems

Main Points

Added-value is driven by software

Main Points

Shorter time to market drives the need for reuse and product

lines

Main Points

As the software – lifespan gets longer,

maintainability becomes more important

Main Points

C does not provide the necessary abstractions

for large scale software engineering

Main Points

At the same time runtime efficiency remains important

So?

What makes developers efficient?

What makes software

maintainable?

And how can a tool and/or language help?

What makes developers efficient?

What makes software maintainable?

Improve Readability if ( tp->alt <= 2000 ) { if ( tp->speed < 150 ) { return 0; } if ( tp->speed >= 150 ) { return 5; } } if ( tp->alt >= 2000 ) { if ( tp->speed < 150 ) { return 10; } if ( tp->speed >= 150 ) { return 20; } }

Improve Readability

Advanced Type Checks

Error:  type  int32  is  not  a  subtype  of  int16  

Advanced Type Checks

Error:  type  int16/[m  /  s]  is  not  a  subtype  of  int16/m  

Meaningful Modularity

More Domain Semantics

Better Testability

Higher Level Concepts

Verification

Verification

SUCCESS:  Table  complete.    FAIL:  cells  (1,  1)  and  (2,  1)  are  inconsistent.  

 tp.alt  :  2000  FAIL:  cells  (1,  2)  and  (2,  2)  are  inconsistent.  

 tp.alt  :  2000  

Verification

Metadata/Tracing

The Preprocessor

The Preprocessor

All of that without runtime overhead?

mbeddr

1

An extensible version of the C programming language for Embedded Programming

C the Difference – C the Future

gefördert durch das BMBF Förderkennzeichen 01|S11014

An extensible C with support for formal methods, requirements

and PLE.

IDE for Everything

A debugger for all of that

The mbeddr stack

The mbeddr stack

The mbeddr stack

DEMO

Status and

Availability

http://mbeddr.com

LWES Language Workbenches

for  Embedded Systems

Developed within

gefördert durch das BMBF Förderkennzeichen 01|S11014

Open Source (Eclipse Public

License)

integration in early / mid

2013

support for graphical mid

2013

First Commercial

Project

2 Developers, 4 months existing source code

30.000 – 50.000 LOC Product Line

Certification Required

Com

m H

AL

App

licat

ion M

etrology U

til

hw-s

peci

fic

DLT645 DLMS/ COSEM

HTTP & TCP/IP

Energy data

Non-Volatile data

Mains frequency measurement

Instantaneous voltage & current sampling

RMS voltage & current calculation

Power & power factor calculation

Energy pulse generation

Energy and consumption calculation

Watch- dog

Clock system

Bin/Bcd converter

LCD formatter

Low-pass filter Ticker

USCI LCD line

Temperature provider RTC Flash

memory Timer ADC10 SD24 E²PROM

PLC modem

Energy data display

Multi-tariff & billing periods

support

Magnetic interference protection

DLT645 calibration commands

Load profile support

Time of use Reset function, historical data

recording

COSEM objects/OBIS

codes

Anti-tampering/ anti-fraud

Last/average/maximum demand

Output relay control

hard

war

e-in

depe

nden

t

Software Layers & Components

Systematic Study with

BMW

The “Pacemaker” Challenge

Formal Verification

2

Challenge: adoption of formal verification in

practice

Who uses Formal Verification?

Big companies and organizations IBM, NASA, Intel, Airbus, Boeing, Microsoft, ...

Safety critical systems Development of flight controllers, processors,

control units of nuclear power plants, automatic trains, ...

Projects with big budgets, long life-cycle Development spans over years, teams of experts are available

What about small and medium enterprises?

What about small and medium enterprises?

Often FV is seen as expert tools,

too heavy weighted, too expensive,

not practicable …

Our goal: formal verification

for everyone

Easy to understand Easy to learn Easy to use

. . . by non computer-

scientists

Short round-trip for defining checks, performing analysis,

and interpreting results.

Integrate formal verification

in more agile processes

Continuously define run and interpret formal analyses

1)  Writing the formal model

2) Specify the property to be verified 3) Interpret the analysis results

Challenges with using formal analyses

Addressing the 1)  Wrap the language of the

analysis tool into higher level languages

2)  Define out-of-the-box analyses goals that can be automated

3)  Lift the analysis results at the abstraction level of the domain

Challenges

Analyses are simpler to define

Automation degree grows / analyses are (computationally)

more feasible

The results of analyses can be presented in more adequate form

Adequate Languages Make Life Simpler

Today’s state of practice: Write some program (e.g. C) and then try (very hardly) to analyze it.

Adequate Languages Make Life Simpler

Today’s state of practice: Write some program (e.g. C) and then try (very hardly) to analyze it.

Today’s state of the art: Write programs that can be analyzed

Adequate Languages Make Life Simpler

Today’s state of practice: Write some program (e.g. C) and then try (very hardly) to analyze it.

The mbeddr approach: … by using adequate language (fragments)

Today’s state of the art: Write programs that can be analyzed

Adequate Languages Make Life Simpler

Code-based, Model-based and DSLs-based Analyses

Formal analysis tools – e.g. model checkers, SMT solvers

GPL Code

GPL Code

Abstract models

Abstraction

Program abstraction

Generation

C  code  

DSL1   DSL2   ...  DSL3  

Clean, easy to analyze DSLs

73  

Allow Software Developers Make Informed Decisions

Either write a sub-system in a restricted (but verifiable)

language

74  

Allow Software Developers Make Informed Decisions

Either write a sub-system in a restricted (but verifiable)

language or

use the full power of a GPL

75  

Allow Software Developers Make Informed Decisions

Either write a sub-system in a restricted (but verifiable)

language or

use the full power of a GPL

and: get immediate feedback if you are

(not) in the verifiable sub-set

Characteristics of Analyzable Languages

High modularisation and encapsulation Small and well-defined interfaces

Clean-up or restrict „problematic“ features Access to global state, side-effects, etc.

Raise the level of abstraction Be able to leave out unnecessary details

Eliminate the „accidental complexity“ Be able to directly express what we want

without any „encoding“ 76  

… for analyses users:

Paradigm Change

decide which parts of programs will be analyzed and use

adequate language fragments that allow analysis

Verifying Decision Tables

Referencing

Decision Tables

Completeness: did we cover all cases? Consistency: are there overlapping cases?

Decision Tables

Predicates Delimit Regions in the Variables Space

P1  

P2  

P3  

Completeness = do we cover the whole space?

P1  P2  

X  <  0   X  >=  0  Complete

Incomplete

Formulating as SAT problem: if „not (P1 or P2)“ is SAT then the

decision table is incomplete

Consistency = are the regions overlapping?

P1  P2  

Consistent

Incosistent

P1  P2  

Formulating as SAT problem: is „P1 and P2“ satisfiable? If yes, then table cells are active at the same time

Easy to answer automatically using an SMT solver J

SMT = Satisfiability Modulo Theories

- extension of boolean satisfiability with additional theories like linear arithmetic

Decision Tables

Language restriction: non-linear expressions

are not allowed

Decision Tables

Verifying Feature Models

Referencing

Feature Models

Can this feature model be instantiated?

Feature Models

Does this configuration comply to the feature model?

Feature Models

Feature Models

“SAT-based analyses of feature models are easy!”

[Mendoca et. al., SPLC’09 ]

Behind the Scene (set-evidence! true) (set-verbosity! 2) ;; each feature is declared as a boolean variable (define root::bool) (define Diagnosis::bool) (define Logging::bool) ... ; the root feature is always present (assert root) ;; for each (sub-feature, feature) we have "sub-feature -> feature" (assert (or (not Diagnosis) root) ) (assert (or (not Logging) Diagnosis) ) (assert (or (not HeartBeat) Diagnosis) ) ... ;; for each mandatory sub-feature we have "feature -> sub-feature" (assert+ (or (not root) Diagnosis) ) (assert+ (or (not root) DataAquisition) ) (assert+ (or (not root) CommProtocol) )

Raw Results

Raw result unsat unsat core ids: 1 3 5 7 9 10

Lifted Results

Verifying State

Machines

Referencing

Model Checking

Model Checking

Model Checking

Model Checking

Model Checking

Unreachable States Dead End States

Live States

Out of the box verification conditions

Transitions Nondeterminism

Dead Transitions

Variables out-of-bounds

Check the sanity of the code

Have a (temporal) scope: Global

Before R

After Q

Between Q and R

After Q Until R

User Defined Properties

Define Business-Domain Specific Verification Conditions

… that restrict a certain basic property:

P not P S responds to P

R   R  

Q   Q  

Q   Q  R   R  Q   Q  

Q   Q  R  Q  

Checking contracts of components

Referencing

Contracts

Define what an interface expects and promisses from/to its environment

Preconditions (assumptions)

Postconditions (guarantees)

Contracts

Does this client comply with the interface?

Checking Contracts

Problem: the variable „time“ can be zero.

How is this done? Reduce the analysis to reacheability.

- For each pre/postcondition we generate a label - Use the CBMC model checker to check the code. - Lift the counterexample at the DSL level

Checking interface

protocols of components

Referencing

Interface Protocols

Define an order upon the execution of operations

... E.g. before ‚drive‘ can be called the system must be in the state ‚Running‘ ... to change the direction we first must stop

Interface Protocols

Which sequence of operations is allowed?

Interface Protocols

Before reversing the direction we must stop

Extending Mbeddr

3

Extensibility Prevent users from using forbidden constructs

•  MISRA •  Void-Pointers •  Pointer Arithmatics •  …

all depending on your context

Extensibility Prevent users from using forbidden constructs

•  MISRA •  Void-Pointers •  Pointer Arithmatics •  …

all depending on your context

Add custom types •  (arbitrary precision) fixed point •  OS-Types such as TASK or EVENT •  Vectors, Matrices •  …

with support for custom validations and special operators

Extensibility Prevent users from using forbidden constructs

•  MISRA •  Void-Pointers •  Pointer Arithmatics •  …

all depending on your context

Add custom types •  (arbitrary precision) fixed point •  OS-Types such as TASK or EVENT •  Vectors, Matrices •  …

with support for custom validations and special operators

Custom language extensions •  acquire memory, do reference counting and garbage collection

•  state machines •  …

Extensibility Prevent users from using forbidden constructs

•  MISRA •  Void-Pointers •  Pointer Arithmatics •  …

all depending on your context

Add custom types •  (arbitrary precision) fixed point •  OS-Types such as TASK or EVENT •  Vectors, Matrices •  …

with support for custom validations and special operators

Custom language extensions •  acquire memory, do reference counting and garbage collection

•  statemachines •  …

Tool Integration •  Requirements •  Verification Tools •  Build Tools •  …

as first class citizen

more specialized domains more specialized languages

Extension Extension

more specialized domains more specialized languages

Extension Extension

more specialized domains more specialized languages

Extension Extension

more specialized domains more specialized languages

Extension Extension

C

LEGO Robot Control

Components

State Machines

Sensor Access

General Purpose

Domain Specific

my L

α  

β  

a b c

d e f

g h i

j k l

Modular Language

composable modules with many optional,

Incremental Trafo

Incremental Trafo

Incremental Trafo

Incremental Trafo

A Language Extension

Concept Tooling Semantics

Editor Validations Refactoring

Typesystem

Generator

Assign fixed types

What does a type system do?

Assign fixed types

Derive Types

What does a type system do?

Assign fixed types

Derive Types

Calculate Common Types

What does a type system do?

Assign fixed types

Derive Types

Calculate Common Types

Check Type Consistency

What does a type system do?

Recap

4

Main Points

Meaningful abstractions help to build maintainable

software.

Main Points

Abstractions without good tool support don’t

work with most developers. Tool

integration is key.

Main Points Once programs contain

(domain-specific) abstractions,

meaningful formal analyses can be

performed much more easily.

Main Points

When integrated directly into the IDE

every project can benefit without big additional effort.

Main Points Mbeddr is an open,

extensible language workbench which can help you to overcome

your software engineering problems