Logotype Mälardalenn University
This web site has been moved.
Please visit our new and improved web site at: http://www.es.mdh.se/
Startpage www.mdh.se

Selected Results


Selected Results

The ProCom component model

A component model defines the nature of components, e.g., how they interact with each other, how they are specified and implemented, and how they can be composed into complex systems. The ProCom component model is developed for i) scalable design of embedded systems, ii) integration of different models for prediction and analysis of components and system properties, and iii) allowing resource-efficient realizations at run-time. The desired characteristics have been obtained by designing a two-layered component model where the lower layer strictly defines the execution semantic and enables efficient timing and resource analysis, while the top level enables a variety of component designs and styles of communication. ProCom [30], including its predecessor SaveCCM [6], has been well received, and there is currently a growing international research community involved in development of tools and using the component model in research . Furthermore, the commercial potential has already been demonstrated by the improved version of the RUBUS component model , which to a large extent is based on our research.

Partial order verification

Scalability is a main challenge for automated formal verification. By taking advantage of information about the structure of component-based systems, we have been able to improve the time to perform model checking with up-to several orders of magnitude [44]. More specifically, we have developed an efficient formal verification technique for real-time component models, which is based on partial order reduction. The technique has been implemented in the tool UPPAAL Port (www.uppaal.org/port/) and a graphical user interface for modeling, simulation, and verification is provided in the PROGRESS IDE. We have also validated the techniques and the tool in a case-study, in which functional and timing requirements of an industrial production system are verified.

Advanced flow analysis

High quality execution time estimates for code fragments are needed for accurate prediction of safety-critical real-time systems. To obtain such estimates, the possible execution paths (program flows) must be determined. Most existing execution time analysis tools perform only a rudimentary flow analysis, which gives poor precision and necessitates manual provision of program flow information. We have developed advanced methods for flow analysis, including infeasible path detection [19] and fast methods for loop bounds detection [28] [50] (Best Paper Award). The methods have been verified against industrial real-time production code generated from the RUBUS component model [26], and they are implemented in our Worst-Case Execution Time (WCET) analysis tool SWEET.

Context aware execution-time estimation

One of the major challenges in providing component-based software engineering for embedded real-time systems is to achieve performance efficiency and predictability while maintaining reusability of software components. We have developed a contract-based approach for dealing with the WCET of a component [35] (Best Paper Award). This approach calculates the actual WCET of a component taking its actual usage into consideration, thereby greatly reducing the risk of over-provisioning CPU resources while still guaranteeing accurate WCET estimates for the components. The applicability of the approach has been shown in an industrial case-study.

Reliability assurance and error models

Embedded systems are typically characterized by high dependability requirements, where fault tolerance in both value and time domains plays an important role, though researchers have traditionally treated them independently. We have developed novel fault-tolerance techniques, which extend the state-of the art in both time and space dimensions, as well as techniques that consider both dimensions in combination to ensure better predictability of developed systems [48]. Another salient contribution is a technique that maximizes the fault-tolerance capabilities of fixed priority systems, which we show to be superior to other well-known techniques [34].

Stack-sharing in component-based systems

Random Access Memory (RAM) is a scarce and expensive resource in many embedded systems. RAM is needed for storing the dynamic state of a system, and is particularly needed for storing the stack. We have developed a technique for stack-sharing that reduces the amount of required stack-memory. The core of the approach is an analysis technique to calculate bounds on the stack usage [20]. The technique has been integrated in an existing component-model to allow stack-sharing between components [25]. Furthermore, the result has been incorporated in the tool-suite Rubus-ICE and is already commercially available.

Software development process

Research and practice in CBD have achieved significant results in different technologies, but in general there is a lack of identification of CBD development processes. We have developed component-based software development process that distinguishes component development, component selection, and system development, and analyzed its application in different development models (Waterfall, V model, and Agile methods). Through several case studies at Ericsson, ABB and Philips we have provided clear evidence that CBD is a sound approach in distributed development of high-volume and many-variant products. We have also identified that it is necessary to change the emphasis in the development process from intensive development activities to intensive specification and verification activities [40]. Based on the case studies we have proposed improvements in particular development phases important in CBD [9, 12, 23].

The IDE

The purpose of the PROGRESS Integrated Development Environment (IDE) is to support design, analysis, and realization of components and component-based systems using different tools integrated in a common environment. The novel CBD process is enabling a seamless integration of, and interaction between, different phases in the process, which traditionally are performed as a sequence of isolated activities. For example, our approach enables incremental and concurrent modeling and deployment, a combination of reuse of existing components and development of new ones, or a combined deployment on virtual and physical nodes. A first version of the IDE was released in December 2007 [22]. The development of the IDE is, together with related component-model research, performed at universities and research centers world-wide, as described in Highlight 1 above.

Faithful execution of legacy code

Predictable reuse of legacy software is substantially facilitated if the legacy code is executed in the same (or very similar) way as in the original system. To support such faithful execution of legacy components and subsystems, we have developed operating system mechanisms using a hierarchical scheduling approach. We have improved these mechanisms in several steps, including adaptation to new (multicore) architectures [24] (Best Paper Award nomination), development of a resource efficient synchronization protocol [27, 46], and development of efficient algorithms for constructing resource efficient systems [18] (Best Paper Award nomination). Several mechanisms have been implemented under the commercial operating system VxWorks.

Extraction of models from legacy code

Many industrial software systems are too large and complex for a single person to comprehend, since they contain millions of lines of code and are the result of hundreds of people working for many years. For such systems, it is too time-consuming and error-prone to manually reverse-engineer the type of detailed model that are required for accurate timing analysis. We have developed a modeling process that makes model extraction practical for very large systems [39] (Best Paper Award). The process is supported by two complementary methods for automated and semi-automated model extraction. A case-study at ABB Robotics shows the applicability of the approach to large and complex software systems.

References:

1. The Worst-Case Execution-Time Problem - Overview of Methods and Survey of Tools. Reinhard Wilhelm (Saarland University, Germany), Jakob Engblom (Virtutech AB), Andreas Ermedahl, Niklas Holsti (Tidorum Ltd., Finland), Stephan Thesing (Saarland University, Germany), David Whalley (Florida State University, USA), Guillem Bernat (Rapita Systems, Ltd.), Christian Ferdinand (AbsInt Angewandte Informatik), Reinhold Heckmann (AbsInt Angewandte Informatik), Tulika Mitra (National University of Singapore), Frank Mueller (North Carolina State University, USA), Isabelle Puaut (IRISA, France), Peter Puschner (TU Vienna, Austria), Jan Staschulat (TU Braunschweig, Germany), Per Stenström (Chalmers University of Technology), ACM Transactions on Embedded Computing Systems, vol. 7, nr 3, pp. 1-53, ACM, April, 2008.

2. Efficient Implementation of Tight Response-times for Tasks With Offsets. Jukka Mäki-Turja, Mikael Nolin, Real-Time Systems, vol. 40, nr 1, pp. 77-116, Springer Netherlands, February, 2008.

3. Data cache locking for tight timing calculations. Xavier Vera, Björn Lisper, Jingling Xue (University of New South Wales, Australia), ACM Transactions on Embedded Computing Systems, vol. 7, nr 1, pp. 4:1-4:38, ACM, December, 2007.

4. Task Automata: Schedulability, Decidability and Undecidability. Elena Fersman (Ericsson Research), Pavel Krcal (Uppsala University), Paul Pettersson, Wang Yi (Uppsala University), International Journal of Information and Computation, vol. 205, nr 8, pp. 1149-1172, Elsevier, August, 2007.

5. Key Factors for Achieving Project Success in Integration of Automotive Mechatronics. Joakim Fröberg, Mikael Åkerholm, Kristian Sandström, Christer Norström, Journal of Innovations in Systems and Software Engineering, vol. 3, nr 2, pp. 141-155, Springer, June, 2007.

6. The SAVE Approach to Component-based Development of Vehicular Systems. Mikael Åkerholm, Jan Carlson, Johan Fredriksson, Hans Hansson, John Håkansson (Uppsala University), Anders Möller, Paul Pettersson, Massimo Tivoli (University of L’Aquila, Italy), Journal of Systems and Software, vol. 80, nr 5, pp. 655-667, Elsevier, May, 2007.

7. Software Configuration Management. René Krikhaar (Vrije Universiteit, The Netherlands), Ivica Crnkovic, Science of Computer Programming, vol. 65, nr 3, pp. 215-221, Elsevier, April, 2007.

8. Component-Based Software Engineering of Trustworthy Embedded Systems. Ivica Crnkovic, Heinz Schmidt, Judith Stafford (Tufts University, USA), George Heineman (Worcester Polytechnic Institute, USA), Kurt Wallnau (SEI, Carnegie Mellon University, USA), Journal of Systems and Software, vol. 80, nr 5, pp. 641-642, Elsevier, January, 2007.

9. Software Systems In-House Integration: Architecture, Process Practices and Strategy Selection. Rikard Land, Ivica Crnkovic, Journal of Information and Software Technology, vol. 49, nr 5, pp. 419-444, Elsevier, September, 2006.

10. Code Analysis for Temporal Predictability. Jan Gustafsson, Björn Lisper, Raimund Kirner (Technische Universität Wien, Austria), Peter Puschner (Technische Universität Wien, Austria), Journal of Real-Time Systems, vol. 32, nr 3, pp. 253-277, Springer-Verlag, March, 2006.

11. Managing Redundancy in CAN-based Networks Supporting N-Version Programming. Julian Proenza (Universitat de les Illes Balears, Spain), José Miro-Julia (Universitat de les Illes Balears, Spain), Hans Hansson, to appear in Journal of Computer Standards and Interfaces, Elsevier. Available online December 3, 2007.

12. Software Product Integration: A Case Study-Based Synthesis of Reference Models. Stig Larsson, Petri Myllyperkiö (ABB Distribution Automation, Finland), Fredrik Ekdahl (ABB Robotics), Ivica Crnkovic, to appear in Information and Software Technology, Elsevier. Invited tutorials

13. Testing Real-time Systems Using UPPAAL. Anders Hessel (Uppsala University), Kim Guldstrand Larsen (Aalborg University, Denmark), Marius Mikuèionis (Aalborg University, Denmark), Brian Nielsen (Aalborg University, Denmark), Paul Pettersson, Formal Methods and Testing, Springer-Verlag, December, 2007.

14. Execution Time Analysis for Embedded Real-Time Systems. Andreas Ermedahl, Jakob Engblom (Virtutech), Handbook of Real-Time Embedded Systems, pp. 35.1-35.17, Chapman & Hall/CRC - Taylor and Francis Group, August, 2007.

15. Evaluating Dependability Attributes of Component-Based Specifications. Ivica Crnkovic, Lars Grunske (University of Queensland, Australia), International Conference on Software Engineering (ICSE), pp. 157-158, IEEE, May, 2007.

16. Trends in Timing Analysis. Björn Lisper, From Model-Driven Design to Resource Management for Distributed Embedded Systems, pp. 85-94, Springer Boston, 2006.

17. Component-based Software Engineering for Embedded Systems. Ivica Crnkovic, From MDD Concepts to Experiments and Illustrations, pp. 71-90, ISTE Ltd, 2006. Peer-reviewed conference articles

18. Synthesis of Optimal Interfaces for Hierarchical Scheduling with Resources. Insik Shin, Moris Behnam, Thomas Nolte, Mikael Nolin, to appear in Proceedings of the 29th IEEE International Real-Time Systems Symposium (RTSS’08), December, 2008, IEEE. (Acceptance ratio: 23%; BEST PAPER AWARD NOMINATION, decision pending)

19. Automatic Derivation of Loop Bounds and Infeasible Paths for WCET Analysis using Abstract Execution. Jan Gustafsson, Andreas Ermedahl, Christer Sandberg, Björn Lisper, In Proceedings of the 27th IEEE International Real-Time Systems Symposium (RTSS’06), pp. 57-66, December, 2006, IEEE. (Acceptance ratio: 24%)

20. Determining Maximum Stack Usage in Preemptive Shared Stack Systems. Kaj Hänninen, Jukka Mäki-Turja, Markus Bohlin, Jan Carlson, Mikael Nolin, In Proceedings of the 27th IEEE Real-Time Systems Symposium (RTSS’06), pp. 445-453, December, 2006, IEEE. (Acceptance ratio: 24%)

21. The TASM Toolset: Specification, Simulation, and Verification of Real-Time Systems. Martin Ouimet (MIT, USA), Kristina Lundqvist, In Proceedings of the 19th International Conference on Computer-Aided Verification (CAV’07), pp. 126-130, July, 2007, Springer LNCS vol. 4590. (Acceptance ratio: 24%)

22. Save-IDE – An Integrated development environment for building predictable component-based embedded systems. Séverine Sentilles, John Håkansson (Uppsala University), Paul Pettersson, Ivica Crnkovic, In Proceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering (ASE’08), September, 2008, ACM. (Acceptance ratio: 12%)

23. Driving the Selection of COTS Components on the Basis of System Requirements. Vittorio Cortaliessa (University of L'Aquila, Italy), Ivica Crnkovic, Pasqualina Potena (University of L'Aquila, Italy), Fabrizio Marinelli (Laboratoire d’Informatique de l’Ecole Polytechnique, France), In Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE’07), pp. 413-416, November, 2007, ACM. (Acceptance ratio: 12%)

24. Hierarchical Scheduling Framework for Virtual Clustering of Multiprocessors. Insik Shin, Arvind Easwaran (University of Pennsylvania, USA), Insup Lee (University of Pennsylvania, USA), In Proceedings of the 20th Euromicro Conference on Real-Time Systems (ECRTS’08), pp. 181-190, July, 2008, IEEE. (Acceptance ratio: 29%, BEST PAPER RUNNER UP)

25. Bounding Shared-Stack Usage in Systems with Offsets and Precedences. Markus Bohlin, Kaj Hänninen, Jukka Mäki-Turja, Jan Carlson, Mikael Nolin. In Proceedings of the 20th Euromicro Conference on Real-Time Systems (ECRTS’08), pp. 276-285, July 2008, IEEE. (Acceptance ratio: 29%)

26. Evaluation of Automatic Flow Analysis for WCET Calculation on Industrial Real-Time System Code. Dani Barkah (Volvo CE), Andreas Ermedahl, Jan Gustafsson, Björn Lisper, Christer Sandberg, In Proceedings of the 20th Euromicro Conference of Real-Time Systems (ECRTS’08), pp. 331-340, July, 2008, IEEE. (Acceptance ratio: 29%)

27. SIRAP: A Synchronization Protocol for Hierarchical Resource Sharing in Real-Time Open Systems. Moris Behnam, Insik Shin, Thomas Nolte, Mikael Nolin, In Proceedings of the 7th ACM and IEEE International Conference on Embedded Software (EMSOFT’07), pp. 279-288, October, 2007, ACM. (Acceptance ratio: 22%)

28. Faster WCET Flow Analysis by Program Slicing. Christer Sandberg, Andreas Ermedahl, Jan Gustafsson, Björn Lisper, In Proceedings of the 2006 ACM SIGPLAN Conference on Languages, Compilers and Tools for Embedded Systems (LCTES’06), pp. 103-112, June, 2006, ACM. (Acceptance ratio: 25%)

29. Scheduling Timed Modules for Correct Resource Sharing. Cristina Seceleanu, Paul Pettersson, Hans Hansson, In Proceedings of the 1st IEEE International Conference on Software Testing, Verification and Validation (ICST’08), pp. 102-111, April, 2008, IEEE. (Acceptance ratio: 20%)

30. A Component Model for Control-Intensive Distributed Embedded Systems. Séverine Sentilles, Aneta Vulgarakis, Tomas Bures, Jan Carlson, Ivica Crnkovic, to appear in Proceedings of the 11th International Symposium on Component-Based Software Engineering (CBSE’08), October, 2008, Springer LNCS. (Acceptance ratio: 29%)

31. Structural Testing of Component-Based Systems. Daniel Sundmark, Jan Carlson, Sasikumar Punnekkat, Andreas Ermedahl, to appear in Proceedings of the 11th International Symposium of Component Based Software Engineering (CBSE’08), October, 2008, Springer LNCS. (Acceptance ratio: 29%)

32. A Prototype Tool for Software Component Services in Embedded Real-Time Systems. Frank Lüders, Daniel Flemström, Anders Wall, Ivica Crnkovic, In Proceedings of the 9th International Symposium on Component-Based Software Engineering (CBSE’06), pp. 222-237, June, 2006, Springer LNCS vol. 4063. (Acceptance ratio: 29%)

33. A Metaheuristic Approach for Best Effort Timing Analysis targeting Complex Legacy Real-Time Systems. Johan Kraft, Yue Lu, Christer Norström, Anders Wall, In Proceedings of the 14th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’08), pp. 258-269, April, 2008, IEEE. (Acceptance ratio: 25%)

34. Maximizing the Fault Tolerance Capability of Fixed Priority Schedules. Radu Dobrin, Sasikumar Punnekkat, and Hüseyin Aysan, In Proceedings of the 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’08), pp. 337-346, August, 2008, IEEE. (Acceptance ratio: 26%)

35. Contract-Based Reusable Worst-Case Execution Time Estimate. Johan Fredriksson, Thomas Nolte, Mikael Nolin, Heinz Schmidt, In Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’07), pp. 39-46, August, 2007, IEEE. (Acceptance ratio: 29%; BEST PAPER AWARD)

36. COTS Selection Best Practices in Literature and in Industry. Rikard Land, Laurens Blankers (Logica, the Netherlands), Michel Chaudron (Technical University Eindhoven, the Netherlands), Ivica Crnkovic, In Proceedings of the 10th International Conference on Software Reuse (ICSR’08), pp. 100-111, May, 2008, Springer LNCS vol. 5030. (Acceptance ratio: 35%)

37. A Case Study of Issues Related to Automotive E/E System Architecture Development. Peter Wallin, Jakob Axelsson, In Proceedings of the 15th Annual IEEE International Conference and Workshop on the Engineering of Computer Based Systems (ECBS’08), pp. 87-95, March, 2008, IEEE. (BEST PAPER AWARD)

38. Evaluating the Quality of Models Extracted from Embedded Real-Time Software. Joel Huselius, Johan Kraft, Hans Hansson, Sasikumar Punnekkat, In Proceedings of the 14th Annual IEEE International Conference and Workshop on the Engineering of Computer Based Systems (ECBS’07), presented at the 5th Workshop and Session on Model-Based Development of Computer Based Systems, pp. 577-585, March, 2007, IEEE.

39. Extracting Simulation Models from Complex Embedded Real-Time Systems. Johan Andersson, Joel Huselius, Christer Norström, Anders Wall, In Proceedings of the 2006 International Conference on Software Engineering Advances (ICSEA’06), October, 2006, IEEE. (Acceptance ratio: 37%; BEST PAPER AWARD)

40. Component-based Development Process and Component Lifecycle. Ivica Crnkovic, Michel Chaudron (Eindhoven University of Technology, the Netherlands), Stig Larsson, In Proceedings of the 2006 International Conference on Software Engineering Advances (ICSEA’06), October, 2006, IEEE. (Acceptance ratio: 37%)

41. Analyzing Software Evolvability. Hongyu Pei-Breivold, Ivica Crnkovic, Peter Eriksson (ABB Robotics), In Proceedings of the 32nd Annual IEEE International Computer Software and Applications Conference (COMPSAC’08), pp. 327-330, July, 2008, IEEE. (Acceptance ratio: 31%)

42. Towards a Capability Model for the Software Release Planning Process - Based on a Multiple Industrial Case Study. Markus Lindgren, Rikard Land, Christer Norström, Anders Wall, In Proceedings of the 9th International Conference on Product-Focused Software Process Improvement (PROFES’08), pp. 117-132, June, 2008, Springer LNCS vol. 5089. (Among best papers – invited for submission to a special issue of the journal Software Process: Improvement and Practice)

43. Component Testing is Not Enough - A Study of Software Faults in Telecom Middleware. Sigrid Eldh, Sasikumar Punnekkat, Hans Hansson, Peter Jönsson (Combitech Systems), In Proceedings of the 19th IFIP International Conference on Testing of Communicating Systems/7th International Workshop on Formal Approaches to Testing of Software (TestCom/FATES’07), pp. 74-89, June, 2007, Springer LNCS vol. 4581.

44. Partial Order Reduction for Verification of Real-Time Components. John Håkansson (Uppsala University), Paul Pettersson, In Proceedings of the 5th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS’07), pp. 211-226, October, 2007, Springer LNCS vol. 4763.

45. Evaluating Flexibility in Embedded Automotive Product Lines Using Real Options. Håkan Gustavsson, Jakob Axelsson, In Proceedings of the 12th International Software Product Line Conference (SPLC’08), pp. 235-242, September, 2008, IEEE. (Acceptance ratio: 30%)

46. Scheduling of Semi-Independent Real-Time Components: Overrun Methods and Resource Holding Times. Moris Behnam, Insik Shin, Thomas Nolte, Mikael Nolin, In Proceedings of the 13th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA’08), September, 2008, IEEE. (Among best papers – invited to submit to a special section of the IEEE Transactions on Industrial Informatics)

47. Design-Time Management of Run-Time Data in Industrial Embedded Real-Time Systems Development. Andreas Hjertström, Dag Nyström, Mikael Nolin, and Rikard Land. In Proceedings of the 13th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA’08), September, 2008, IEEE.

48. VTV – A Voting Strategy for Real-Time Systems. Hüseyin Aysan, Sasikumar Punnekkat, and Radu Dobrin, to appear in Proceedings of the 14th Pacific Rim International Symposium on Dependable Computing (PRDC’08), December, 2008, IEEE.

49. The Rubus Component Model for Resource Constrained Real-Time Systems. Kaj Hänninen, Jukka Mäki-Turja, Mikael Nolin, Mats Lindberg (Arcticus Systems), John Lundbäck (Arcticus Systems), Kurt-Lennart Lundbäck (Arcticus Systems), In Proceedings of the 3rd IEEE International Symposium on Industrial Embedded Systems (SIES’08), pp. 177-183, June, 2008, IEEE.

50. Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis. Andreas Ermedahl, Christer Sandberg, Jan Gustafsson, Stefan Bygde, Björn Lisper, In Proceedings of the 7th International Workshop on Worst-Case Execution Time Analysis (WCET’07), pp. 63-68, July, 2007. (one of two BEST PAPERS)

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