https://www.mdu.se/

mdu.sePublications
Change search
Refine search result
1 - 13 of 13
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Bygde, Stefan
    Mälardalen University, Department of Computer Science and Electronics.
    Analysis of Arithmetical Congruences on Low-Level Code2007Conference paper (Refereed)
    Abstract [en]

    Abstract Interpretation is a well known formal framework for abstracting programming language semantics. It provides a systematic way of building static analyses which can be used for optimisation and debugging purposes. Different semantic properties can be captured by so-called abstract domains which then easily can be combined in various ways to yield more precise analyses. The most known abstract domain is probably the one of intervals. An analysis using the interval domain yields bindings of each integer-valued program variable to an interval at each program point. The interval is the smallest interval that contains the set of integers possible for that particular variable to assume at that program point during execution. Abstract interpretation can be used in many contexts, such as in debugging, program transformation, correctness proving, Worst Case Execution Time analysis etc.

    In 1989 Philippe Granger introduced a static analysis of arithmetical congruences. The analysis is formulated as an abstract interpretation computing the smallest (wrt. inclusion) congruence (residue) class that includes the set of possible values that that variable may assume during execution. The result of the analysis is a binding of each integer-valued variable at each program point to a congruence class. Applications for this analysis include automatic vectorisation, pointer analysis (for determining pointer strides) and loop-bound analysis (for detecting loops with non-unit strides). However, in the original presentation, the analysis is not well suited to use on realistic low-level code. By low-level code we mean either compiled and linked object code where high-level constructions has been replaced with target-specific assembly code, or code in a higher-level language written in a fashion close to the hardware. A good example of low-level code is code written for embedded systems which often is using advantages of the target hardware and/or using a lot of bit-level operations. Code for embedded systems is an increasingly important target for analysis, since it is often safety-critical. The reason that the congruence domain in its original presentation is not suitable for low-level code is mainly due to the three following properties of low-level code: A) Bit-level operations are commonly used in low-level code. Programs that contain bit-operations are not supported in the original presentation. For any computation of an expression which contain operations that has not been defined in the analysis, it has to assume that nothing is known about the result and assign the result to the largest congruence class (equal to Z). This can potentially lead to very imprecise analysis results.

    B) The interpretation of the values of integer-valued variables is not obvious (e.g. they can be signed or unsigned), the original presentation assumes that values has unambiguous representations. C) The value-domain is limited by its representation (integers are often represented by a fixed number of bits). In Grangers presentation integer-valued variables are assumed to take values in the infinite set of integers. Our contribution is to extend the theory of the analysis of arithmetical congruences to be able to handle low-level or assembly code, still in the framework of abstract interpretation.

    This paper provides accurate definitions to the abstract bit-operations AND,NOT,XOR, left- and right shifting and truncation for the congruence domain in order to make the domain support these operations. We provide definitions for the operations together with proofs of their correctness. In these definitions care has been taken to the finite, fixed representation of integers as well as their sometimes ambiguous interpretations as signed or unsigned. With these definitions, congruence analysis can efficiently be performed on low-level code. The paper illustrates the usefulness of the new analysis by an example which shows that variables keep important parity information after executing a XOR-swap.

  • 2.
    Bygde, Stefan
    Mälardalen University, School of Innovation, Design and Engineering.
    Parametric WCET Analysis2013Doctoral thesis, monograph (Other academic)
    Abstract [en]

    In a real-time system, it is crucial to ensure that all tasks of the system hold their deadlines. A missed deadline in a real-time system means that the system has not been able to function correctly. If the system is safety critical, this could potentially lead to disaster. To ensure that all tasks keep their deadlines, the Worst-Case Execution Time (WCET) of these tasks has to be known.

    Static analysis analyses a safe model of the hardware together with the source or object code of a program to derive an estimate of the WCET. This estimate is guaranteed to be equal to or greater than the real WCET. This is done by making calculations which in all steps make sure that the time is exactly or conservatively estimated. In many cases, however, the execution time of a task or a program is highly dependent on the given input. Thus, the estimated worst case may correspond to some input or configuration which is rarely (or never) used in practice. For such systems, where execution time is highly input dependent, a more accurate timing analysis which take input into consideration is desired.

    In this thesis we present a method based on abstract interpretation and counting of semantic states of a program that gives a WCET in terms of some input to the program. This means that the WCET is expressed as a formula of the input rather than a constant. This means that once the input is known, the actual WCET may be more accurate than the absolute and global WCET. Our research also investigate how this analysis can be safe when arithmetic operations causes integers to wrap-around, where the common assumption in static analysis is that variables can take the value of any integer. Our method has been implemented as a prototype and as a part of a static WCET analysis tool in order to get experience with the method and to evaluate the different aspects. Our method shows that it is possible to obtain very complex and detailed information about the timing of a program, given its input.

    Download full text (pdf)
    fulltext
  • 3.
    Bygde, Stefan
    Mälardalen University, School of Innovation, Design and Engineering.
    Static Analysis on Executable Code: A Survey2011Report (Other academic)
    Abstract [en]

    This is a survey paper investigating approaches to static program analysis on executable code. Analysis on executable code is important because in some cases the source code does not describe what happens during execution well enough. In other cases, only the executable may be available. Several difficulties are involved in analysing executables though, including incomplete information about the program flow, missing information about program variables, bit manipulation etc. This article surveys different suggested approaches to overcome some of these problems.

  • 4.
    Bygde, Stefan
    Mälardalen University, School of Innovation, Design and Engineering.
    Static WCET Analysis Based on Abstract Interpretation and Counting of Elements2010Licentiate thesis, monograph (Other academic)
    Abstract [en]

    In a real-time system, it is crucial to ensure that all tasks of the system holdtheir deadlines. A missed deadline in a real-time system means that the systemhas not been able to function correctly. If the system is safety critical, this canlead to disaster. To ensure that all tasks keep their deadlines, the Worst-CaseExecution Time (WCET) of these tasks has to be known. This can be done bymeasuring the execution times of a task, however, this is inflexible, time consumingand in general not safe (i.e., the worst-casemight not be found). Unlessthe task is measured with all possible input combinations and configurations,which is in most cases out of the question, there is no way to guarantee that thelongest measured time actually corresponds to the real worst case.Static analysis analyses a safe model of the hardware together with thesource or object code of a program to derive an estimate of theWCET. This estimateis guaranteed to be equal to or greater than the real WCET. This is doneby making calculations which in all steps make sure that the time is exactlyor conservatively estimated. In many cases, however, the execution time of atask or a program is highly dependent on the given input. Thus, the estimatedworst case may correspond to some input or configuration which is rarely (ornever) used in practice. For such systems, where execution time is highly inputdependent, a more accurate timing analysis which take input into considerationis desired.In this thesis we present a framework based on abstract interpretation andcounting of possible semantic states of a program. This is a general methodof WCET analysis, which is language independent and platform independent.The two main applications of this framework are a loop bound analysis and aparametric analysis. The loop bound analysis can be used to quickly find upperbounds for loops in a program while the parametric framework provides aninput-dependent estimation of theWCET. The input-dependent estimation cangive much more accurate estimates if the input is known at run-time.

    Download full text (pdf)
    FULLTEXT01
  • 5.
    Bygde, Stefan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    An Efficient Algorithm for Parametric WCET Calculation2009In: 2009 15TH IEEE INTERNATIONAL CONFERENCE ON EMBEDDED AND REAL-TIME COMPUTING SYSTEMS AND APPLICATIONS, PROCEEDINGS, LOS ALAMITOS: IEEE COMPUTER SOC , 2009, p. 13-21Conference paper (Refereed)
    Abstract [en]

    Static WCET analysis is a process dedicated to derive a safe upper bound of the worst-case execution time of a program. In many real-time systems, however, a constant global WCET estimate is not always so useful since a program may behave very differently depending on its configuration or mode. A parametric WCET analysis derives the upper bound as formula rather than a constant. This paper presents a new efficient algorithm that can obtain a safe parametric estimate of the WCET of a program. This algorithm is evaluated on a large set of benchmarks and compared to a previous approach to parametric WCET calculation. The evaluation shows that the new algorithm, to the cost of some imprecision, scales much better and can handle more realistic programs than the previous approach.

  • 6.
    Bygde, Stefan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    An efficient algorithm for parametric WCET calculation2011In: Journal of systems architecture, ISSN 1383-7621, E-ISSN 1873-6165, Vol. 57, no 6, p. 614-624Article in journal (Refereed)
    Abstract [en]

    Static WCET analysis is a process dedicated to derive a safe upper bound of the worst-case execution time of a program. In many real-time systems, however, a constant global WCET estimate is not always so useful since a program may behave very differently depending on its configuration or mode. A parametric WCET analysis derives the upper bound as a formula rather than a constant. This paper presents a new algorithm that can obtain a safe parametric estimate of the WCET of a program. This algorithm is evaluated on a large set of benchmarks and compared to a previous approach to parametric WCET calculation. The evaluation shows that the new algorithm, to the cost of some imprecision, scales much better and can handle more realistic programs than the previous approach.

  • 7.
    Bygde, Stefan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Towards an automatic parametric WCET analysis2008In: OpenAccess Ser. Informatics, 2008, p. 9-17Conference paper (Refereed)
    Abstract [en]

    Static WCET analysis obtains a safe estimation of the WCET of a program. The timing behaviour of a program depends in many cases on input, and an analysis could take advantage of this information to produce a formula in input variables as estimation of the WCET, rather than a constant. A method to do this was suggested in [12]. We have implemented a working prototype of the method to evaluate its feasibility in practice. We show how to reduce complexity of the method and how to simplify parts of it to make it practical for implementation. The prototype implementation indicates that the method presented in [12] successfully can be implemented for a simple imperative language, mostly by using existing libraries.

  • 8.
    Bygde, Stefan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Holsti, Niklas
    Tidorum Ltd, Helsinki, Finland.
    Fully Bounded Polyhedral Analysis of Integers with Wrapping2011In: Electronic Notes in Theoretical Computer Science, E-ISSN 1571-0661, Vol. 288, p. 3-13Article in journal (Refereed)
    Abstract [en]

    analysis technique to discover linear relationships among variables in a program. However, the classical way of performing polyhedral analysis does not model the fact that values typically are stored as fixed-size binary strings and usually have a wrap-around semantics in the case of overflows. In embedded systems where 16-bit or even 8-bit processors are used, wrapping behaviour may even be used intentionally. Thus, to accurately and correctly analyse such systems, the wrapping has to be modelled. We present an approach to polyhedral analysis which derives polyhedra that are bounded in all dimensions and thus provides polyhedra that contain a finite number of integer points. Our approach uses a previously suggested wrapping technique for polyhedra but combines it in a novel way with limited widening, a suitable placement of widening points and restrictions on unbounded variables. We show how our method has the potential to significantly increase the precision compared to the previously suggested wrapping method.

  • 9.
    Bygde, Stefan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Holsti, Niklas
    Tidorum Ltd, Helsinki, Finland.
    Improved Precision in Polyhedral Analysis with Wrapping2017In: Science of Computer Programming, ISSN 0167-6423, E-ISSN 1872-7964, Vol. 133, p. 74-87Article in journal (Refereed)
    Abstract [en]

    Abstract interpretation using convex polyhedra is a common and powerful program analysis technique to discover linear relationships among variables in a program. However, the classical way of performing polyhedral analysis does not model the fact that values typically are stored as xed-size binary strings and usually have wrap-around semantics in the case of over ows. In resource-constrained embedded systems, where 8- or 16-bit processors are used, wrapping behaviour may even be used intentionally to save instructions and execution time. Thus, to analyse such systems accurately and correctly, the wrapping has to be modelled. We present an approach to polyhedral analysis which derives polyhedra that are bounded in all dimensions. Our approach is based on a previously suggested wrapping technique by Simon and King, combined with limited widening, a suitable placement of widening points and size-induced restrictions on unbounded variables. With this method, we can derive fully bounded polyhedra in every step of the analysis. We have implemented our method and Simon and King's method compared them. Our experiments show that for a suite of benchmark programs it gives at least as precise result as Simon and King's method. In some cases we obtain a significantly improved result.

  • 10.
    Bygde, Stefan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Holsti, Niklas
    Mälardalen University, School of Innovation, Design and Engineering.
    Static Analysis of Bounded Polyhedra2011Conference paper (Refereed)
    Abstract [en]

    We present a method for polyhedral abstract interpretation which derives fully bounded polyhedra for every step in the analysis. Contrary to classical polyhedral analysis, this method is sound for integer-valued variables stored as fixed-size binary strings; wrap-arounds are correctly modelled. Our work is based on earlier work by Axel Simon and Andy King but aims to significantly reduce the precision loss introduced in their method.

  • 11.
    Ermedahl, Andreas
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Sandberg, Christer
    Mälardalen University, Department of Computer Science and Electronics.
    Gustafsson, Jan
    Mälardalen University, Department of Computer Science and Electronics.
    Bygde, Stefan
    Mälardalen University, Department of Computer Science and Electronics.
    Lisper, Björn
    Mälardalen University, Department of Computer Science and Electronics.
    Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis2007In: OpenAccess Series in Informatics, Volume 6, 2007, 2007Conference paper (Refereed)
    Abstract [en]

    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.

  • 12.
    Lu, Yue
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Cicchetti, Antonio
    Mälardalen University, School of Innovation, Design and Engineering.
    Bygde, Stefan
    Mälardalen University, School of Innovation, Design and Engineering.
    Kraft, Johan
    Mälardalen University, School of Innovation, Design and Engineering.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    Norström, Christer
    Mälardalen University, School of Innovation, Design and Engineering.
    Transformational Specification of Complex Legacy Real-Time Systems via Semantic Anchoring2009In: 2nd IEEE International Workshop on Component-Based Design of Resource-Constrained Systems (CORCS 2009) @ COMPSAC, 2009, p. 1183-1188Conference paper (Refereed)
    Abstract [en]

    RTSSim is a framework for simulating models extracted from complex legacy real-time systems which are task-oriented, run on a single processor and are developed in C. Such RTSSim models describe functional and temporal behavior as well as the resource usage of the system. However, the semantics specification of RTSSim models remains a challenging problem indeed, especially with tractable complexity to obtain a formal model which can be analyzed for instance by a model checking tool. In this paper, we present an approach towards using semantic anchoring for the transformational specification of RTSSim models, by relying on units with well-defined operational semantics and tool support. Specifically, Timed Automata with Tasks (TAT) in TIMES is chosen as the semantic unit with the purpose of anchoring different behavioral concerns of RTSSim models in all aspects. In this respect, model transformations are conducted at the meta-model level allowing the original operational semantics of RTSSim models to be preserved, while at the same time it can be presented in TIMES models in terms of a network of TAT.

  • 13.
    Lu, Yue
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Cicchetti, Antonio
    Mälardalen University, School of Innovation, Design and Engineering.
    Sjödin, Mikael
    Mälardalen University, School of Innovation, Design and Engineering.
    Mäki-Turja, Jukka
    Mälardalen University, School of Innovation, Design and Engineering.
    Bygde, Stefan
    Mälardalen University, School of Innovation, Design and Engineering.
    Norström, Christer
    Mälardalen University, School of Innovation, Design and Engineering.
    Towards Response-Time Analysis of Complex Real-Time Systems by using ParametricWorst-Case Execution-Time Estimate on Tasks – A Case Study for Robotic Control System2009In: 21st Euromicro Conference on Real-Time Systems (ECRTS 09) Work-In-Progress (WIP) session, Dublin, Ireland, 2009Conference paper (Refereed)
1 - 13 of 13
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf