# Patent

## Title
Timing analysis using formal methods

## Abstract

A method and tools for providing precise timing analysis scalable to industrial case studies with large numbers of tasks and messages are provided, including the capability to model and analyze task and message response times; ECU usage; bus usage; end-to-end latency of task/message chains; and timing synchronization problems in task/message graphs. System tasks and messages are modeled in a formalism known as calendar automaton. Models are written in a modeling language such as Promela and instrumented with code specific to the analysis specification. Models and instrumentation are automatically generated from the system description and analysis specification. The system model is subjected to exhaustive state space exploration by a compatible model checker, such as SPIN. During exploration, the instrumented code produces results for different timing analyses. Optimization techniques are provided to generate models which require less memory and time for analysis and make the method scalable to large, industrial case studies.

## Background
TECHNICAL FIELD
The invention relates generally to timing analysis of embedded systems using formal methods, and in particular to a computer executable method for formal modeling and timing analysis of a system described using calendar automata.
BACKGROUND
Existing methods used for the timing analysis of embedded systems include analytical, simulation-based and stochastic methods. These methods provide imprecise analysis. Analytical methods using schedulability analysis and Real Time Calculus give safe approximations. However since they cannot handle some operational details of the system under consideration and do not compute the reachable states in a model of the system, the results can be very pessimistic. Stochastic methods are good for average case analysis, but are not suitable for worst-case analysis. Further, these methods do not allow deterministic modeling of arbitrary scheduling algorithms and controller buffer policies, which influence actual results. Additionally, existing analytical and stochastic analysis tools do, not provide good solutions for timing synchronization problems, because these problems involve simultaneous analysis of multiple event chains which are beyond the capabilities of these methods. Simulation based methods can handle operational details. However, they do not guarantee coverage of corner cases during system simulation and timing measurements, thus possibly giving optimistic results.
Formal methods-based tools and methods for timing analysis exist but have not been scalable to large industrial examples. For example, formal methods based on timed automata cannot address the large amount of data associated with a complex system and typically fail due to the large memory and time required to complete the analysis. With the increasing complexity of electrical systems, such as automotive electrical systems comprising multiple electronic control units (ECUs) communicating via multiple controller area network (CAN) buses, scalable timing analysis methods and tools capable of analyzing these complex systems with precision and accuracy are needed.
SUMMARY
A method and system are provided herein for performing timing analysis of an embedded system including at least one electronic control unit (ECU) and/or at least one bus. The method includes providing a system description, providing an analysis specification for the system, automatically generating a formal model of the system using a model generator, analyzing the formal model of the system using a model checker, and providing results of the analysis. The system description may include task parameters describing tasks, message parameters describing messages, dependency relationships among the tasks and the messages, and other details of the system. The formal model may include a calendar automaton model and instrumentation.
Analyzing the formal model of the system may include analyzing response times of the tasks and the messages, analyzing end-to-end latency of task/message chains, and/or analyzing timing synchronization in task/message graphs. The method and system may further include providing scheduling policies for ECUs or buses included in the system; and providing rules for event activation which may include at least one rule pertaining to a timed transition or a discrete transition.
The model may be optimized using one or more optimization techniques, to reduce or optimize the state-space of the model to enable efficient state-space exploration. For example, the model may be optimized by dynamically computing response time of a task or of a message; by using the analysis specification to filter a portion or part of the system description that is independent of or not critical to the analysis specification; or by applying a combination of these techniques.
The above features and advantages and other features and advantages of the present invention are readily apparent from the following detailed description of the best modes for carrying out the invention when taken in connection with the accompanying drawings.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a flow chart describing a method for timing analysis using formal methods;
FIG. 2 is schematic graphical representation of an illustrative example of an embedded system;
FIG. 3 is a table of task/message allocations and parameters of the system of FIG. 2;
FIG. 4 is a table of task/message chains in the system of FIG. 2;
FIGS. 5A and 5B are graphical models of rules for state changes on event activation for tasks and messages, respectively;
FIG. 6 is a formal model of a discrete transition rule for event ready expressed in calendar automaton;
FIGS. 7A, 7B and 7C are graphical models for rules for end-to-end latency analysis of tasks, where FIGS. 7A, 7B and 7C represent first, intermediate, and last tasks in a chain, respectively;
FIG. 8 is a graphical model illustrating on-the-fly computation of task response time;
FIG. 9 is an algorithm for computing spill according to the method of FIG. 1; and
FIGS. 10A, 10B and 10C are illustrative examples of representative results of a timing analysis of the system of FIGS. 2, 3 and 4 performed according to the method of FIG. 1.



DETAILED DESCRIPTION
A method and tools are provided for performing precise timing analyses which are scalable to industrial case studies having a large number of tasks and messages without trading off accuracy. The method and tools provided herein include the capability to model and analyze task response times, including best case and worst case task response times and schedulability analysis; electronic control unit (ECU) usage including percentage usage of ECU computation time; message response times, including best case and worst case message response times and schedulability analysis; bus usage including percentage usage of bus and idle time availability; end-to-end latency for task/message chains, including first in-first out (FIFO), first in-last out (FILO), last in-first out (LIFO), last in-last out (LILO) end-to-end latencies; timing synchronization problems among task graphs; maximum time separation between multiple destinations starting from a single source; and maximum time separation between multiple sources leading to the same destination.
In the method described herein, system tasks and messages are modeled in a formal notation or formalism, such as calendar automaton. The models are written in a modeling language such as Process Meta Language (Promela). Further, the models are instrumented with code using formal notation and specifically designed to address the analysis under scope. The models along with the instrumentation are automatically generated from, at least, task/message descriptions and scheduling policies. Other operational details such as controller buffer policies can also be included in or supplied as models. Optimization techniques may be used to further optimize the state space for model checking. The modeled system is subjected to exhaustive state space exploration by a compatible model checker, such as Simple Promela Interpreter (SPIN). During exploration, the instrumented code produces results for different timing analyses which are recorded and outputted by a report generator as analysis results which may include witnesses.
Benefits of the method, model and tools provided herein include high precision achieved by the analysis due to the detailed operational models of the system described using mathematical formalisms and exhaustive state space exploration. Scalability is achieved due to the use of discrete event model, in particular the use of calendar automaton formalism, and careful design of the models, which in an exemplary embodiment are Promela models, which exploit many regular features of task-based architectures. The formal models are optimized to achieve scalability without trading off accuracy.
Advantages of the method and tools provided herein include automatic model generation and analysis; the capability to handle and incorporate operational details such as controller buffer policies and specific scheduling algorithms in system design; and the capability to perform simultaneous analysis of multiple task/message chains to detect timing synchronization problems. Further, the method and tools provide improved precision due to exhaustive state-space exploration capability, scalability to large systems with accuracy, and the ability to produce scenarios and simulation traces, also referred to as witnesses, witness paths or witness traces, that can be used to identify the causes of timing requirement violations.
Fundamental to the present invention is the use of calendar automaton model and its instrumentation for different timing analyses, and optimizing the encoding of calendar automaton model to reduce the state-space which must be explored, which allows modeling and analysis to be run within a reasonable amount of time and within reasonable memory requirements.
The method and tools for timing analysis using formal methods as described herein can also be used for the analysis of any system, including embedded systems which may be automotive or non-automotive systems. The method and tools described herein may be used to satisfy current and anticipated Automotive Open System Architecture (AUTOSAR) requirements and specifications for automotive software architecture, some of Which, e.g., timing synchronization problems, cannot be addressed precisely or accurately with existing analytical, simulation-based or stochastic tools.
Referring to FIG. 1, generally indicated at 100 is a method for timing analysis using formal models. A system description 10 is provided which describes the architectural details of the embedded system to be analyzed. In an exemplary embodiment, the embedded system is an electrical control system of an automobile, which is comprised of a plurality of electronic control units (ECUs) connected by one or more controller area network (CAN) buses.
Referring to FIG. 2, shown as an illustrative example is a graphical representation of an embedded system including a set of ECUs designated as E1 through E4 and a bus B. A set of tasks is deployed on each ECU, and different sets of tasks are deployed on different ECUs. For example, tasks τ1 and τ2 are deployed on ECU E1, as shown in FIG. 2. A set of messages associated with tasks are propagated on a bus. For example, messages m1 through m5 are assigned to bus B shown in FIG. 2. Each task is described by a tuple, where a tuple is an ordered list of parameters describing the task. For example, each task may be described by a tuple such as <priority, initial offset, period, execution time>. Each message is described by a similar tuple. The table shown in FIG. 3 shows task/message allocations to ECUs/buses and task/message descriptions in tuple form, including a task/message name (oi) for each task τi or message mi, a priority (πi), an initial offset (Oi), period (Pi) and execution time (Ei). The execution time of a task includes the time to read, process and output data. The execution time for a message is the transmission time of the message on a bus and can be computed from bus speed and the size of the message inclusive of bit-stuffing. Other task parameters may be described for each task, such as a deadline by which the task must complete its execution. If all these parameters are included, the task may be described by a tuple such as <ECU, priority, initial offset, period, execution time, deadline>. The message tuple may include parameters such as <bus, ID, initial offset, period, length, deadline>, where each message is described by the bus it is assigned to, for example a high-speed controller area network (CAN) with a typical baud rate of 500 kilobits per second (kbps) or a low-speed CAN with a typical baud rate of 33.3 kbps, the ID as an expression of priority, the initial offset and period, the message length expressed in bytes, and the deadline expressed as a set amount of time in which the message must reach its destination. A periodic or event-triggered tasks/messages can also be represented using similar tuples.
System description 10 may further specify certain properties or parameters to be input into the model generator, for the purpose of optimizing the encoding of the calendar automaton model such that the state-space of the model to be analyzed is reduced. The data dependency relationships among a set of tasks and messages may be specified, which may include a description of how the data is passed from one task/message to another task/message. The data dependency relationships among a set of tasks and messages of the embedded system are illustrated in FIG. 2 by the directed edges shown in the graph. A directed edge from τi to τj specifies that the output of task τi is an input to task τj. As an example, as shown in FIG. 2, in ECU E2, the directed edge from τ7 to τ11 shows the data-dependency between τ7 and τ11. A directed edge from τi to mj specifies that the message mj contains an output of task τi. Similarly, a directed edge from mj to τk specifies that message mj contains an input of task τk. As an example, in ECU E2, task τ11 outputs message m5, which in turn is an input to task τ2 in ECU El. A sample of task/message chains showing the data dependency relationships in the example system of FIG. 2 are summarized in the table shown in FIG. 4.
Optimizing the model may include filtering a part of the system description that is independent of the analysis specification, for example, optimizing the encoding may include modeling and/or analyzing only those tasks/messages which are critical to the timing analysis specified, thereby reducing the type and number of events to be included into the discrete event model. Optimizing system model 40 reduces the state-space in comparison to a generic system model by limiting the events in the discrete event model and by instrumenting the model based on analysis specification 20. For example, three events such as ready, start, finish may be modeled for each task or message. Shown in FIG. 5A is an example model of a task τi with three events, and shown in FIG. 5B is an example model of a message mi with three events.
Events may be encoded to occur at known time points determined from the task/message parameters. For example, the ready, start, finish events of a task τi may be modeled with their activation times for a given analysis specification as:
(readyi, t): task τi will be triggered after t time units from current time
(starti, t): task τi will start execution after t time units from current time
(finishi, t): task τi will finish execution after t time units from current time
Rules may be modeled for activation of selected events. For example, a rule may be provided for time advancement, also known as timed transition, which may be independent of the system description 10 and analysis specification 20. The rule for timed transition may specify that if no event can be activated at current time, advance time to the nearest activation time of any event. A formal model of the timed transition rule may be expressed in calendar automaton as:

1. min(C)>0

2. Δ←min(C)

3. C←C−Δ  (1)

where C is a set of all events along with their activation times, min(C) computes the nearest activation time of any event in C, and if min(C)>0, its value is subtracted from activation times of all entries in C.

The rules for event activations, also known as discrete transitions, may be dependent on one or both the system description 10 and analysis specification 20, for example, by depending on message/task tuples, scheduling policies of ECUs/buses, etc. A formal model of the discrete transition rule for event ready may be expressed in calendar automaton as shown in FIG. 6, where C is a set of all events with their activation times, line 1 represents the event activation condition, and lines 2-21 represent implementation of rules for task-ready condition.
Rules or policies may also be modeled for task and message schedulability. Again referring to FIGS. 5A and 5B, for example, the model of the task shown in FIG. 5A or the model of the message shown in FIG. 5B can move from an initial state of idle, once a ready event is activated, to a wait state, and on activation of a start event, go to an exec state. Tasks may be preemptively scheduled, where a task τi can be preempted by a higher priority task τj . For example, the task τi illustrated by the graph of FIG. 5A, moves from exec state to wait state when a higher priority task τj is ready to start execution. As illustrated by FIG. 5B, CAN messages typically are non-preemptively scheduled, therefore there is no transition from exec state to wait state for these messages.
Optimizing the encoding may further include specifying properties such as end-to-end latency or timing synchronization, which are obtained from analysis specification 20. For example, FIGS. 7A, 7B and 7C are graphical models of the rules for end-to-end latency analysis of a chain, where FIGS. 7A, 7B and 7C represent first, intermediate, and last tasks in a chain, respectively. Messages in a chain can be modeled similarly.
Optimizing system model 40 reduces the state-space in comparison to a generic system model by limiting the events in the discrete event model and by instrumenting the model based on analysis specification 20, thus enabling analysis using formal modeling and exhaustive state-space exploration using a model checker.
As shown in FIG. 1, system description 10 is provided to model generator 30 in conjunction with analysis specification 20. Analysis specification 20 describes the specific timing analysis to be completed for the embedded system being modeled and analyzed. The descriptions are formalized using calendar automaton or another formal notation. Analysis specification 20 may address various system parameters and characteristics, including providing for analysis of:
(1) Task response times: Best case and worst case task response times and schedulability analysis;
(2) ECU usage: Percentage usage of ECU computation time;
(3) Message response times: Best case and worst case message response times and schedulability analysis;
(4) Bus usage: Percentage usage of Bus, how much idle time is left;
(5) End-to-end latency for task/message chains: Given a chain of tasks and messages, different end-to-end latencies (e.g., FIFO, FILO, LIFO, LILO);
(6) Timing synchronization problems in task/message graphs;
(7) Maximum time separation between multiple destinations starting from a single source; and/or
(8) Maximum time separation between multiple sources leading to the same destination.
Analysis specification 20 may further specify problem specifications and problem parameters to model generator 30, in order to optimize the model by reducing the state-space to be analyzed, e.g., where the scope of events modeled and tested is limited. Analysis specification 20 may typically include specifications to measure the time for event chains, including the following:
Worst case response time of task/message:

<ready(t),finish(t)>  (2)

End-to-end latency of a task/message chain:

<ready(t1),finish(t1),ready(t2),finish(t2), . . . , ready(tn),finish(tn)>  (3)

Timing Synchronization:

<ready(t1), . . . , finish(tm)>

<ready(t1), . . . , finish(tn)>  (4)

Analysis specification 20 may also define deadlines and other details related to the system analysis requirements.
At step 30 shown on FIG. 1, the model generator automatically generates a formal model 40, based on calendar automaton, using the information provided by system description 10 and analysis specification 20 of the system. Formal model 40 may be expressed in Promela or any other suitable modeling language. Formal model 40 has two parts, a system model derived from system description 10 and a property instrumentation or analysis instrumentation derived from analysis specification 20. The formal model may be described by specifying the data dependency relationships among the tasks and the messages for a set of tasks and messages, providing scheduling policies for ECUs or buses included in the system, and providing rules for event activation, wherein the rules for event activation includes at least one rule pertaining to one of a timed transition or a discrete transition. The analysis specification may be used during the formal modeling process to further optimize the system model, to reduce the state space to be analyzed.
Formal model 40 may be further optimized by a variety of optimization techniques. One optimization technique is to filter parts of the system description that are independent of the analysis specification under consideration from the model, to reduce the model's state-space. For example, when the analysis specification is restricted to schedulability analysis for a specific ECU, for example, ECU E1 shown in FIG. 2, then formal model 40 of FIG. 1 may be filtered to include details pertaining to tasks on ECU E1 only.
Another optimization technique provided herein, which may be used for fixed priority preemptive scheduling, and typically for preemptively scheduled tasks, is to compute the task response time dynamically, e.g., on-the-fly. By combining model checking with on-the-fly computation of response times for analysis specifications involving end-to-end latency and/or timing synchronization problems, significant scalability for handling industry sized systems and problems can be enabled. Shown in FIG. 8 is a graphical model illustrating on-the-fly computation of task response time, where it is understood that whenever a task in a chain is activated, for example, at the end of a period, the task reads an input buffer and at the end of a computation, the task updates its output buffer. The updating of the output buffer takes varying time due to delays from higher priority tasks, therefore, the updating time actually equals the response time of a task. The response time of the task can be computed dynamically, e.g. on-the-fly, using the equation:




  
    
      
        w
        =
        
          spill
          +
          
            E
            j
          
          +
          
            
              ∑
              
                l
                ∈
                
                  hp
                  ⁡
                  
                    (
                    j
                    )
                  
                
              
            
            ⁢
            
              
                ⌈
                
                  
                    w
                    -
                    
                      O
                      l
                      ′
                    
                  
                  
                    T
                    l
                  
                
                ⌉
              
              *
              
                E
                l
              
            
          
        
      
    
    
      
        (
        5
        )
      
    
  




where w represents the computed response time of τj, spill is as defined herein, Ej is the worst case execution time of τj, hp(j) is the set of all tasks with higher priority than τj, O′l represents the next activation offset of τl from current time, Tl represents the period of τl and El represents the worst case execution time of τl. Spill, in the above equation and for a given task activation instance, is defined as the remaining execution time of an immediate higher priority task that is in the state of execution, and can be computed using the algorithm shown in FIG. 9. Because spill value is dependent on the different instances of higher priority tasks which were activated when the task under consideration is activated, its computation represents the remaining obligation of higher priority tasks in terms of execution and the computation is therefore non-trivial.

Yet another optimization technique or policy which may be applied to fixed priority non-preemptive scheduling used in a bus, such as a CAN bus similar to the bus B shown in the system of FIG. 2, is to optimize the calendar automaton models by using only two events, a Boolean array tracking the list of ready messages, and a timer variable. The first event is used to track the remaining propagation time of the message that most recently won the arbitration. The second event is a single cyclic timeout event that is sufficient to track periodic activation of all messages on the bus. By using this optimization technique instead of tracking activation time separately for all messages when analyzing worst case response time of messages, the state space required for analyzing the CAN network can be significantly reduced, helping in increasing the scalability.
Referring again to FIG. 1, at step 50 formal model 40 is subjected to exhaustive state space exploration by a model checker to determine if the system model complies with the analysis specification. Model checker 50 is configured to be compatible with model generator 30. For example, for a model generated at steps 30 and 40 in Promela modeling language, model checker 50 may be configured as the Simple Promela Interpreter (SPIN) model checker. Optimization of the model, as discussed previously, permits the model to be explored in a reasonable time and within reasonable memory requirements. During exploration, the instrumented code produces results for the different timing analyses discussed previously, which are summarized as an output in the form of a report at step 60.
The report produced by the report generator at step 60 is in human understandable form, including analysis results 70, and may be used to determine compliance of the design assumptions of system description 10 with the specifications and requirements included in analysis specification 20. Analysis results 70 may include, for example, results as shown in FIGS. 10A, 10B and 10C. Shown in FIG. 10A are analysis results for Best Case Response Times (BCRT) and Worst Case Response Times (WCRT) for each task and message, for example, for each task/message shown in FIG. 3. The table of FIG. 10B provides analysis results for last in-first out (LIFO) delay computations, also referred to as first-through (FT) for each task/message chain specified as an input to model generator 30, for example, for each task/message chain shown in FIG. 4. FIG. 10C shows analysis results for last in-last out (LILO) delay computations, also referred to as max-age (MA) for each task/message chain specified as an input to model generator 30, for example, for each task/message chain shown in FIG. 4.
Analysis results 70 may further include simulation traces, which may also be referred to as witnesses, whenever there is a violation of timing constraints or specifications during the state space exploration. These simulation traces can be used to assist in debugging by localizing the cause of analysis failures and identifying parameter changes to resolve the anomaly. The system architecture can be redesigned to ensure timing constraints are addressed and the redesigned architecture can be modeled and analyzed to confirm the anomaly recorded by the witness has been eliminated.
The ability to model and perform an exhaustive state space exploration of a system provides the advantage of early analysis such that issues found during modeling can be used to correct or improve the architectural design of the system, including changes to the bus/ECU design and task/message allocation, optimizing ECU/bus usage, performing schedulability analysis, optimizing message and task response times and resolving timing synchronization problems in task/message graphs, to ensure timing requirements are met and to optimize the system architecture. These system changes can be easily reassessed in a timely manner by incorporating the changes into system description 10 and analysis specification 20 and repeating steps 30 through 60 to determine the impact of the changes.
While the best modes for carrying out the invention have been described in detail, those familiar with the art to which this invention relates will recognize various alternative designs and embodiments for practicing the invention within the scope of the appended claims.

## Claims

1. A method for performing timing analysis of an embedded system comprising:
providing a system description;
providing an analysis specification for the system;
automatically generating a formal model of the system from the system description and the analysis specification using a model generator;
wherein the formal model includes a calendar automaton model and instrumentation;
analyzing the formal model of the system using a model checker;
optimizing the calendar automaton model by at least one of:
computing a spill time associated with a task; and
dynamically computing response time of the task using the spill time;
wherein





  w
  =
  
    spill
    +
    
      E
      j
    
    +
    
      
        ∑
        
          l
          ∈
          
            hp
            ⁡
            
              (
              j
              )
            
          
        
      
      ⁢
      
        
          ⌈
          
            
              w
              -
              
                O
                l
                ′
              
            
            
              T
              l
            
          
          ⌉
        
        *
        
          E
          l
        
      
    
  




where w represents the computed response time of τj, Ej is the worst case execution time of τj, hp(j) is the set of all tasks with higher priority than τj, O′l represents the next activation offset of τl from current time, Tl represents the period of τl and El, represents the worst case execution time of τl, Spill, for a given task activation instance, is defined as the remaining execution time of an immediate higher priority task that is in the state of execution; and
providing results of the analysis.

2. The method of claim 1, wherein providing the system description includes:
providing task parameters for a task;
providing message parameters for a message; and
providing data dependencies among a set of tasks and messages.

3. The method of claim 1, wherein analyzing the formal model of the system using a model checker includes at least one of:
specifying the analysis to be performed using the analysis specification;
analyzing response time of a task;
analyzing response time of a message;
analyzing end-to-end latency of a task/message chain; and
analyzing timing synchronization in a task/message graph.

4. The method of claim 1, wherein analyzing the formal model of the system using a model checker includes at least one of:
dynamically computing a response time of the task; and
dynamically computing a response time of the message.

5. The method of claim 1,
wherein the embedded system includes an electronic control unit (ECU) and a bus, the method further comprising at least one of:
providing a scheduling policy for the ECU; and
providing a scheduling policy for the bus.

6. The method of claim 1, further comprising:
providing a rule for event activation;
wherein the rule for event activation pertains to one of a timed transition and a discrete transition.

7. The method of claim 1, wherein the results of the analysis includes one of a witness path and simulation trace.

8. The method of claim 1, further comprising:
filtering the formal model using the analysis specification to exclude portions of the system description that are independent of the analysis specification from the model.

9. A method for performing timing analysis of an automotive system comprising:
providing a system description;
providing an analysis specification for the system;
automatically generating a formal model of the system including a calendar automaton model and instrumentation;
analyzing the formal model of the system using a model checker;
wherein the system includes a plurality of electronic control units (ECUs) connected by one or more buses, the method further comprising:
providing scheduling policies for the plurality of ECUs and for the one or more buses; and
analyzing percentage usage of ECU computation time; and
providing results of the analysis.

10. The method of claim 9, further comprising:
optimizing the calendar automaton model by at least one of:
dynamically computing response time of a task;
dynamically computing response time of a message; and
filtering the system description using the analysis specification.

11. The method of claim 9, wherein providing the system description includes:
describing a task by a tuple;
describing a message by a tuple; and
specifying data dependency relations among a set of tasks and messages.

12. The method of claim 9, wherein analyzing the formal model of the system using a model checker includes at least one of:
specifying the analysis to be performed using the analysis specification;
analyzing response time of a task;
analyzing response time of a message;
analyzing end-to-end latency of a task/message chain; and
analyzing timing synchronization in task/message graphs.

13. The method of claim 9, further comprising:
providing one or more rules for event activation, wherein the one or more rules includes a rule pertaining to one of a timed transition and a discrete transition.

14. A system for performing timing analysis of an embedded system, the system comprising:
a computer;
an embedded system description including a task and a message;
an analysis specification for the embedded system;
a formal model generator, wherein the formal model generator is configured to generate a formal model of the embedded system and the analysis specification;
wherein the formal model includes a calendar automaton model and instrumentation;
wherein the embedded system includes a plurality of electronic control units (ECUs) connected by one or more buses, further comprising:
an optimized calendar automaton model, wherein:
the optimized calendar automaton model includes no more than two events;
one of the two events is a Boolean array tracking a list of ready messages; and
the other of the two events is a single cyclic timeout event configured to track periodic activation of messages on the one or more buses; and

a model checker configured to analyze the formal model and provide results of the analysis.

15. The system of claim 14, further comprising:
an optimized calendar automaton model, wherein the optimized calendar automaton model includes one of:
a dynamic computation of response time of a task;
a dynamic computation of response time of a message; and
wherein the optimized calendar automaton model is defined by filtering the embedded system description using the analysis specification.

16. The system of claim 14,
wherein the model generator is a Promela model generator; and
wherein the model checker is SPIN model checker.

17. The system of claim 14, wherein the embedded system includes a plurality of electronic control units (ECUs) connected by one or more buses, further comprising:
a set of scheduling policies for the plurality of ECUs and for the one or more buses; and
a set of rules for event activation, wherein the set of rules for event activation includes a rule pertaining to one of a timed transition and a discrete transition.