Search Results

Documents authored by Sandberg, Christer

Document
DOI: 10.4230/OASIcs.WCET.2009.2279
ALF - A Language for WCET Flow Analysis

Authors: Jan Gustafsson, Andreas Ermedahl, Björn Lisper, Christer Sandberg, and Linus Källberg

Published in: OASIcs, Volume 10, 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09) (2009)

Abstract
Static Worst-Case Execution Time (WCET) analysis derives upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component in static WCET analysis is the flow analysis, which derives bounds on the number of times different code entities can be executed. Examples of flow information derived by a flow analysis are loop bounds and infeasible paths. Flow analysis can be performed on source code, intermediate code, or binary code: for the latter, there is a proliferation of instruction sets. Thus, flow analysis must deal with many code formats. However, the basic flow analysis techniques are more or less the same regardless of the code format. Thus, an interesting option is to define a common code format for flow analysis, which also allows for easy translation from the other formats. Flow analyses for this common format will then be portable, in principle supporting all types of code formats which can be translated to this format. Further, a common format simplifies the development of flow analyses, since only one specific code format needs to be targeted. This paper presents such a common code format, the ALF language (ARTIST2 Language for WCET Flow Analysis).
Cite as

Jan Gustafsson, Andreas Ermedahl, Björn Lisper, Christer Sandberg, and Linus Källberg. ALF - A Language for WCET Flow Analysis. In 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{gustafsson_et_al:OASIcs.WCET.2009.2279,
  author =	{Gustafsson, Jan and Ermedahl, Andreas and Lisper, Bj\"{o}rn and Sandberg, Christer and K\"{a}llberg, Linus},
  title =	{{ALF - A Language for WCET Flow Analysis}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  pages =	{1--11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-14-9},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{10},
  editor =	{Holsti, Niklas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2279},
  URN =		{urn:nbn:de:0030-drops-22791},
  doi =		{10.4230/OASIcs.WCET.2009.2279},
  annote =	{Keywords: WCET analysis, flow analysis, ALF WCET analysis, flow analysis, ALF}
}
Document
DOI: 10.4230/OASIcs.WCET.2007.1191
Finding DU-Paths for Testing of Multi-Tasking Real-Time Systems using WCET Analysis

Authors: Daniel Sundmark, Anders Petterson, Christer Sandberg, Andreas Ermedahl, and Henrik Thane

Published in: OASIcs, Volume 6, 7th International Workshop on Worst-Case Execution Time Analysis (WCET'07) (2007)

Abstract
Memory corruption is one of the most common software failures. For sequential software and multi- tasking software with synchronized data accesses, it has been shown that program faults causing memory cor- ruption can be detected by analyzing the relations be- tween defines and uses of variables (DU-based testing). However, such methods are insufficient in preemptive systems, since they lack the ability to detect inter-task shared variable dependencies. In this paper, we propose the use of a system level shared variable DU analy- sis of preemptive multi-tasking real-time software. By deriving temporal attributes of each access to shared data using WCET analysis, and combining this infor- mation with the real-time schedule information, our method also detects inter-task shared variable depen- dencies. The paper also describes how we extended the SWEET tool to derive these temporal attributes.
Cite as

Daniel Sundmark, Anders Petterson, Christer Sandberg, Andreas Ermedahl, and Henrik Thane. Finding DU-Paths for Testing of Multi-Tasking Real-Time Systems using WCET Analysis. In 7th International Workshop on Worst-Case Execution Time Analysis (WCET'07). Open Access Series in Informatics (OASIcs), Volume 6, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{sundmark_et_al:OASIcs.WCET.2007.1191,
  author =	{Sundmark, Daniel and Petterson, Anders and Sandberg, Christer and Ermedahl, Andreas and Thane, Henrik},
  title =	{{Finding DU-Paths for Testing of Multi-Tasking Real-Time Systems using WCET Analysis}},
  booktitle =	{7th International Workshop on Worst-Case Execution Time Analysis (WCET'07)},
  pages =	{1--6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-05-7},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{6},
  editor =	{Rochange, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2007.1191},
  URN =		{urn:nbn:de:0030-drops-11914},
  doi =		{10.4230/OASIcs.WCET.2007.1191},
  annote =	{Keywords: Testing, Real-time systems, WCET analysis, data flow}
}
Document
DOI: 10.4230/OASIcs.WCET.2007.1194
Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis

Authors: Andreas Ermedahl, Christer Sandberg, Jan Gustafsson, Stefan Bygde, and Björn Lisper

Published in: OASIcs, Volume 6, 7th International Workshop on Worst-Case Execution Time Analysis (WCET'07) (2007)

Abstract
Static Worst-Case Execution Time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component for static derivation of precise WCET estimates is upper bounds on the number of times different loops can be iterated. In this paper we present an approach for deriving upper loop bounds based on a combination of standard program analysis techniques. The idea is to bound the number of different states in the loop which can influence the exit conditions. Given that the loop terminates, this number provides an upper loop bound. An algorithm based on the approach has been implemented in our WCET analysis tool SWEET. We evaluate the algorithm on a number of standard WCET benchmarks, giving evidence that it is capable to derive valid bounds for many types of loops.
Cite as

Andreas Ermedahl, Christer Sandberg, Jan Gustafsson, Stefan Bygde, and Björn Lisper. Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis. In 7th International Workshop on Worst-Case Execution Time Analysis (WCET'07). Open Access Series in Informatics (OASIcs), Volume 6, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{ermedahl_et_al:OASIcs.WCET.2007.1194,
  author =	{Ermedahl, Andreas and Sandberg, Christer and Gustafsson, Jan and Bygde, Stefan and Lisper, Bj\"{o}rn},
  title =	{{Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis}},
  booktitle =	{7th International Workshop on Worst-Case Execution Time Analysis (WCET'07)},
  pages =	{1--6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-05-7},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{6},
  editor =	{Rochange, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2007.1194},
  URN =		{urn:nbn:de:0030-drops-11946},
  doi =		{10.4230/OASIcs.WCET.2007.1194},
  annote =	{Keywords: WCET analysis, loop-bound analysis, program slicing, abstract interpretation, invariant analysis}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact