Iceccs 2010
Iceccs 2010
Abstract: Designing safety critical systems is a complex II. R ELATED M ETHODOLOGIES AND T OOL S UPPORT
task due to the need of guaranteeing that the resulting Designing new generations of embedded real-time systems
model can cope with all the functional and non-functional is so complex that became mandatory to work with higher
requirements of the system. Obtaining such guarantees is abstractions (namely computational models) previous to imple-
only possible with the use of model verification techniques. mentation. The Model Driven Engineering (MDE) [10] is, for
This paper presents an approach aimed to fulfill the needs instance, an initiative to help developers to manage software
of critical system design. The proposed approach is based development complexity using models at the very beginning,
on the Architecture Analysis and Design Language (AADL), and with different abstraction levels. The key aspect from
which is suitable to describe the system’s architecture. A this technology is the design of models that are decoupled
sequence of model transformations facilitates the verification from their target platform. Among the main benefits of the
of the designed AADL model and so assures its correctness. emerging MDE approach it should be highlighted its enhanced
It must be highlighted that this is not performed in a single possibilities for early model verification.
step, as it is possible to verify AADL models with different In fact, many recent tools have been proposed to support
abstraction levels, which allows successive refinements in a different kinds of verification. With respect to our concerns,
top-down approach. timing verification tools have been an active area of research
over these last years. It is interesting to remark that although
most of these tools are based on existing theoretical models,
I. I NTRODUCTION
e.g., timed automata, Petri nets, the limitations (especially
with respect to combinatorial explosion and scalability) of
The Architecture Analysis & Design Language (AADL) [6]
which are well known, the effort has been undertaken to
is a textual and graphical language used to design and analyze
achieve them. In fact, it is hoped that first, the abstraction
the software and hardware architecture of safety critical real-
and the structure brought by the model driven approach and
time systems. AADL is used to describe the structure of
second, the adoption of a specific execution model will help
systems as an assembly of software components mapped
to struggle against these limitations. Along these lines, we
onto an execution platform. It is used to describe functional
can cite the Cheddar [4] scheduling tool which proposes
interfaces to components (such as data inputs and outputs) and
dedicated analysis for the AADL execution model. Currently,
performance-critical aspects of components (such as timing).
it considers mainly analytical models. Future versions should
In order to support model analysis, AADL relies on a precise
take into account more detailed behavior descriptions [7]. The
execution model. AADL is by now a standard [9]; The version
tools Uppaal Port [8] and Pola[2] are based on the traditional
2 has been recently voted.
model checking approach. Uppaal Port is based on timed
The goal of this paper is to present an approach that supports automata and supports component based development. In order
model checking over AADL models. This is possible by means to reduce the combinatorial explosion Uppaal Port adopts a
of a sequence of model transformations, which finishes when synchronous like execution model which restricts interleaving
the model is suitable for verification, as further discussed along of the asynchronous approach. Moreover, it proposes partial
the paper. Using the proposed approach we expect to enhance order techniques for reducing space explorations. The tool Pola
considerably the reliability of AADL models designed for is based on timed Petri nets, and it proposes specific support
safety-critical applications. for the AADL execution model.
The remainder parts of the paper are structured as follows:
Section II discusses some related methodologies and tool III. T HE P ROPOSED A PPROACH
support. Sections III and IV detail the proposed verification Our proposed design-process for critical embedded systems
approach and its application in a case study. Section V presents supports the safe design of the system’s architecture using
our conclusions and directs our future work. MDE’s principles. By safe design we mean that the resulting
332
Tools like Scade/Lustre and Matlab/Simulink are often used times due to the lack of information in the model), a new
for this propose. refinement in each component should take action, starting new
iterations.
C. Environment Description
Following this approach, each component of the AADL
The third level of the proposed process consists of using model can derive into several subcomponents. By definition,
AADL to describe the environment that interacts with the the successive refinements will only finish as the model
system under development. In other words, it is necessary to contains enough details to be proof correct or incorrect by the
define the set of interactions of the system with the external model verification. Each detailed model (i.e. iteration) should,
devices, such as sensors, actuators, user interface, etc. however, cope with the abstract behavior defined for the
For this reason it is suggested here the use of a high- higher level component. Follows a more detailed discussion
level AADL diagram. Figure 2 presents the diagram designed about the main steps of this phase, namely Architecture
for the AP system, where it is possible to observe the main Refinement and Model Verification.
system in the center (named ParkingCtrl) surrounded by 1) Architecture Refinement: The architecture refinement
the devices. An advantage of using AADL is that it allows process consists of successive model refinements and verifi-
detailing each message exchanged between the system and the cation, as suggested in the design flow from Figure 3. It starts
devices, including information like data type, arrival pattern, with identifying the operation modes (1) and threads (2) of
and time constraints. the system, being followed by the mapping of functions to
threads (3). Afterwards the designer can make the connections
among the threads (4) and associate an execution mode to each
thread (5). The reminder of this section details these steps and
presents its application on the AP system.
1. Identify modes
yes
2. Identify threads
new
refinement?
4. Add connections
333
SystemManagement is used to start or halt the AP system be obtained using, for example, model simulation on top
by means of the graphical interface (FR1), SlotSelection of the target architecture. Thereby it is possible to obtain
is responsible to search for a parking slot (FR2), and finally the worst case execution time (WCET) for each function of
ParkingManeuver is responsible to perform the parking the system prior to its implementation. The last step of the
(FR3). proposed process is in charge of making the verification of the
timing properties. Schedulability and response-time analysis
are exemples of possible properties to be verified.
IV. V ERIFICATION P ROCESS
It is possible to argue that our proposed verification process
supports the safe design of the system’s architecture using
MDE’s principles. By safe design we mean that the resulting
system architecture goes through several verification steps
in order to assure its correctness. To reach this goal it is
performed a sequence of model transformations, which starts
with an AADL-like model and finishes with an equivalent
automaton model that is suitable for verification.
The verification process we have been working on uses
AADL models as input and performs the model checking of
LTL properties. Moreover, schedulability and buffer overflow
can also be analyzed, as well as user defined properties. This
process is split in the following phases (Figure 5):
Fig. 4. AADL model of parking control system (in the first decomposition)
334
nets, like absence of deadlocks, linear time temporal prop- handled by the translator to generate a specific deadlock
erties, or bisimilarity. For untimed systems, abstract state if the capacity of the input buffer is exceeded.
spaces help to prevent combinatorial explosion. For timed 2) Real-time observers: Some properties such as bounded
systems, TINA provides various abstractions based on state response time can be expressed using AADL threads acting as
classes, preserving reachability properties, linear properties or real-time observers. The component to be checked is linked
branching properties. to an observer which plays the role of its environment and
State space abstractions are provided in various formats checks its responses.
suitable for existing model checkers. The TINA toolbox also For example, properties of the maneuver component of the
provides a native model checker, selt. Selt allows one to check parking can be verified by specifying an environment as the
more specific properties than the general ones (boundedness, following. It checks that the highSpeed signal is emitted one
deadlocks, liveness) already checked by the state space genera- period (fixed here at 10ms) after the speed becomes non zero.
tion tool. Selt implements an extension of linear time temporal Otherwise, the err state would be reached. It also checks
logic known as State/Event LTL [5], a logic supporting both that the abort signal is sent if the wheels are moved. The
state and transition properties. The modeling framework con- selt model checker is used to show that the err state is
sists of Kripke transition systems (labeled Kripke structures, unreachable.
the state class graph in our case), which are directed graphs
in which states are labeled with atomic propositions and t h r e a d i m p l e m e n t a t i o n E n v i r o n m e n t T h r e a d . imp
annex b e h a v i o r s p e c i f i c a t i o n {∗∗
transitions are labeled with actions. states
State/Event-LTL formulas are interpreted over the compu- s0 : i n i t i a l complete s t a t e ;
tation paths of the model. They may express a wide range of s1 , s2 , e r r : c o m p l e t e s t a t e ;
state and/or transition properties. Some typical formulas are transitions
the following (a formula evaluates to true if it does so on all s 0 −]→[ s0 { speed ! ( 0 ) ; r a n g l e ! ( 0 ) ; } ;
s 0 −[f i n i s h e d ?]→ s 0 ;
computation paths, X, F, G and U are LTL modalities, p, q s 0 −]→[ s1 { speed ! ( 1 0 ) ; } ;
are formulas): s 0 −]→[ s 2 { wheelMoved ! ; } ;
p p holds at the start s 1 −[h i g h S p e e d ?]→ s 0 ;
X p p holds at the next step (next) −− d e t e c t e d i n l e s s t h a n t h e p e r i o d
s 1 −[on h i g h S p e e d ’ c o u n t = 0]→ e r r ;
G p p holds all along the path (globally) s 2 −[a b o r t ?]→ s 0 ;
F p p holds in a future step (eventually) s 2 −[on a b o r t ’ c o u n t =0]→ e r r ;
p U q p holds until q holds (until) and q holds eventually. ∗∗};
end E n v i r o n m e n t T h r e a d . imp ;
We also use the weak until operator W. p W q holds until q
holds. It is not mandatory that q eventually happens. Remark Response time information could be added to the
Real-time properties, like those expressed in so called AADL model as properties of flow specifications and thus
“timed temporal logics”, are checked using the standard tech- be implicitly checked. However, this is not easy if response
nique of observers, encoding such properties into reachability time is greater than the minimum period of the input signal.
properties. The technique is applicable to a large class of Here, our observer supposes that speed does not change while
real-time properties and can be used to analyze most of the waiting for the highSpeed signal.
“timeliness” requirements found in practice. 3) Linear time Temporal Logic: Temporal properties can be
checked on the closed system. They can be expressed in linear
B. Properties Verification
temporal logic (LTL) and passed to the selt tool. Atomic
Currently, we support the verification of three kinds of properties are either event properties or state properties. For
properties: (i) implicit properties taken into account by the example:
translator and leading to deadlock when not satisfied; (ii) user • If the speed is too high, the interface cannot get the
properties specified through AADL real-time observers; and found message while the search has not been restarted.
(iii) properties specified directly in linear temporal logic.
1) Implicit properties: For the moment, two implicit prop- (highSpeed ⇒ (¬found W startSearch))
erties are taken into account by the translator:
• Schedulability: threads are scheduled using a fixed prior- This property is in fact not satisfied because taking into
ity protocol with user-specified preemption points. Dead- account the speed information and aborting the process
line events are generated by the translator. If a deadline needs one cycle. We use the hyperperiod event H to
occurs while a thread is still active, a specific deadlock reformulate the property as follows: if the speed is too
is generated. high, starting from the next hyperperiod signal, we cannot
• Buffer overflows: AADL defines the property Over- get the found message unless startSearch has been
flow Handling Protocol which specifies what to do in pushed.
case of overflow. Either the oldest or the newest data is
lost, or the component is erroneous. The latest case is highSpeed ⇒ (¬H U H∧(¬found W startSearch))
335
• It is possible to park the car, i.e. there exists an execution we have suggested the use of mu-calculus. We intend to study
path leading to a state where the car is parked. It is in future work suitable patterns to enhance the use of such
expressed as a negated property: it is not true that in a logic. Another further direction of this research would be
any execution, finished is never sent. providing a risk analysis to assist the design.
336