Bachelor and Master Theses

Title: WCET Analysis and Certification of Automatically Generated Code for CC-Systems AB
Subject: Computer Science
Level: Advanced
Description: This M.Sc. thesis proposal is for two students, and consists of two different parts. It is preferred that both students work concurrently, so they can cooperate on some of the parts. The work is carried out in cooperation with CC-Systems AB and Tidorum Oy, an will most likely take place on CC-Systems' premises in Västerås.

Worst-Case Execution Time (WCET) analysis tries to find safe upper bounds to the running time of a program. The field has been subject to intense research for the last decade, and now a few commercial tools for WCET analysis exist as well as a number of research prototypes. State of the practice right now is that small to moderately sized embedded C programs, running on not too complex embedded processors, can be analyzed with reasonable precision given that the user provides some information to the analysis: how hard it is to provide this information depends to a large extent on the character and structude of the program. A WCET analysis showing that a real-time program always meets its deadlines should increase the confidence in the program and ought to be an argument when certifying safety-critical code with real-time demands.

Today, code for embedded systems is increasingly being generated automatically from models. Depending on the kind of model and the code generation tool, the character of the generated code can be very different. Little is known about how to perform WCET analysis on such code, that is: where the difficulties are, and conversely if there are any simplifications in the analysis that can be made compared with analysis of hand-written code. It is also quite unclear today to which extent a WCET analysis of automatically generated and safety-critical code actually is helpful when certifying the system.

The first part concerns a case study in WCET analysis. A commercial WCET tool is used to analyse embedded C++-code generated from Rhapsody. The following steps are to be performed:



  • Identify the parts of the generated code which are time-critical. How analyse these parts w.r.t. WCET? Can information from the Rhapsody model be used to find these parts, and then how?


  • Perform a WCET analysis of the generated code:


  • identify possible difficulties and investigate how to get around them. Examples may be function pointers due to object-oriented code, obscure control structure, difficulties to find upper bounds to the number of loop iterations, etc.


  • investigate if high-level information, in the model, can facilitate the WCET analysis. For instance, there may be information that can help finding upper bounds to the number of loop iterations, or to identify infeasible execution paths through the code.


  • (possibly) do some kind of estimation of the precision of the WCET analysis, for instance by comparing with measured or simulated execution times.




The second part concerns certification. Certification is typically done for safety-critical software and systems, and is done by some independent certification authority. Typically, certification requires that certain routines are used and that certain standards are met for the development process, as well as for testing. The first phase of this part is an investigation how to certify safety-critical software in general. The second phase applies the results to the code which is analysed w.r.t. WCET, and demands on the WCET analysis which make it more apt to aid certification are identified. This phase is made in close cooperation with the part of the project concerning actual WCET analysis, and should result in a WCET analysis of the code which does help the certification of the code.
Company: CC-systems AB, kontaktperson: Stefan Rnning
Prel. end date: 2007-06-25
Presentation date: 2007-10-23
Student: Elie Manouel Assaf eaf02001@student.mdh.se
Student: Syed Abbas Ali sai04001@student.mdh.se
IDT supervisor: Bjrn Lisper
bjorn.lisper@mdh.se, +46-21-151709
Misc: The thesis project is for two persons and has two distinct parts.

Rapport och bilagor

Size

Senaste uppdatering

TR0628.pdf

1912321

2007-11-06, 16:59

TR0628_1.pdf

3002848

2007-11-07, 14:12


  • Mälardalen University |
  • Box 883 |
  • 721 23 Västerås/Eskilstuna |
  • 021-101300, 016-153600 |
  • webmaster |
  • Latest update: 2017.03.25