https://www.mdu.se/

mdu.sePublications
Change search
Link to record
Permanent link

Direct link
Publications (10 of 13) Show all publications
Bygde, S., Lisper, B. & Holsti, N. (2017). Improved Precision in Polyhedral Analysis with Wrapping. Science of Computer Programming, 133, 74-87
Open this publication in new window or tab >>Improved Precision in Polyhedral Analysis with Wrapping
2017 (English)In: Science of Computer Programming, ISSN 0167-6423, E-ISSN 1872-7964, Vol. 133, p. 74-87Article in journal (Refereed) Published
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.

National Category
Engineering and Technology Computer Systems
Identifiers
urn:nbn:se:mdh:diva-17370 (URN)10.1016/j.scico.2016.07.006 (DOI)000389391000004 ()2-s2.0-84994454811 (Scopus ID)
Available from: 2012-12-20 Created: 2012-12-20 Last updated: 2023-06-08Bibliographically approved
Bygde, S. (2013). Parametric WCET Analysis. (Doctoral dissertation). Västerås: Mälardalen University
Open this publication in new window or tab >>Parametric WCET Analysis
2013 (English)Doctoral 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.

Place, publisher, year, edition, pages
Västerås: Mälardalen University, 2013. p. 167
Series
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 138
Keywords
WCET Analysis, parametric WCET Analysis, WCET, Timing
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-18770 (URN)978-91-7485-109-0 (ISBN)
Public defence
2013-06-04, Delta, Mälardalens högskola, Västerås, 13:00 (English)
Opponent
Supervisors
Available from: 2013-04-29 Created: 2013-04-26 Last updated: 2018-01-11Bibliographically approved
Bygde, S., Ermedahl, A. & Lisper, B. (2011). An efficient algorithm for parametric WCET calculation. Journal of systems architecture, 57(6), 614-624
Open this publication in new window or tab >>An efficient algorithm for parametric WCET calculation
2011 (English)In: Journal of systems architecture, ISSN 1383-7621, E-ISSN 1873-6165, Vol. 57, no 6, p. 614-624Article in journal (Refereed) Published
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.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-10790 (URN)10.1016/j.sysarc.2010.06.009 (DOI)000291840700005 ()2-s2.0-79957754134 (Scopus ID)
Available from: 2010-11-10 Created: 2010-11-10 Last updated: 2017-12-12Bibliographically approved
Bygde, S., Lisper, B. & Holsti, N. (2011). Fully Bounded Polyhedral Analysis of Integers with Wrapping. Electronic Notes in Theoretical Computer Science, 288, 3-13
Open this publication in new window or tab >>Fully Bounded Polyhedral Analysis of Integers with Wrapping
2011 (English)In: Electronic Notes in Theoretical Computer Science, E-ISSN 1571-0661, Vol. 288, p. 3-13Article in journal (Refereed) Published
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.

National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-13595 (URN)10.1016/j.entcs.2012.10.003 (DOI)2-s2.0-84870403479 (Scopus ID)
Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2024-07-04Bibliographically approved
Bygde, S., Lisper, B. & Holsti, N. (2011). Static Analysis of Bounded Polyhedra. In: : . Paper presented at Nordic Workshop of Programming Theory (NWPT), Västerås, Sweden.
Open this publication in new window or tab >>Static Analysis of Bounded Polyhedra
2011 (English)Conference paper, Published 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.

National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-13551 (URN)
Conference
Nordic Workshop of Programming Theory (NWPT), Västerås, Sweden
Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2017-04-07Bibliographically approved
Bygde, S. (2011). Static Analysis on Executable Code: A Survey.
Open this publication in new window or tab >>Static Analysis on Executable Code: A Survey
2011 (English)Report (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.

Publisher
p. 18
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-13683 (URN)
Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2014-01-30Bibliographically approved
Bygde, S. (2010). Static WCET Analysis Based on Abstract Interpretation and Counting of Elements. (Licentiate dissertation). Västerås: Mälardalen University
Open this publication in new window or tab >>Static WCET Analysis Based on Abstract Interpretation and Counting of Elements
2010 (English)Licentiate 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.

Place, publisher, year, edition, pages
Västerås: Mälardalen University, 2010
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 115
Keywords
parametric WCET analysis, program analysis, abstract interpretation
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-7854 (URN)978-91-86135-55-3 (ISBN)
Presentation
2010-03-16, Gamma, Mälardalens Högskola, Vasagatan, VÄSTERÅS, 10:00 (English)
Opponent
Supervisors
Projects
PROGRESS
Available from: 2010-02-04 Created: 2010-02-03 Last updated: 2018-01-12Bibliographically approved
Bygde, S., Ermedahl, A. & Lisper, B. (2009). An Efficient Algorithm for Parametric WCET Calculation. In: 2009 15TH IEEE INTERNATIONAL CONFERENCE ON EMBEDDED AND REAL-TIME COMPUTING SYSTEMS AND APPLICATIONS, PROCEEDINGS. Paper presented at 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (pp. 13-21). LOS ALAMITOS: IEEE COMPUTER SOC
Open this publication in new window or tab >>An Efficient Algorithm for Parametric WCET Calculation
2009 (English)In: 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, Published 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.

Place, publisher, year, edition, pages
LOS ALAMITOS: IEEE COMPUTER SOC, 2009
Identifiers
urn:nbn:se:mdh:diva-8955 (URN)10.1109/RTCSA.2009.9 (DOI)000276774500002 ()2-s2.0-72349096284 (Scopus ID)978-0-7695-3787-0 (ISBN)
Conference
15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications
Available from: 2010-03-03 Created: 2010-03-03 Last updated: 2013-12-03Bibliographically approved
Lu, Y., Cicchetti, A., Sjödin, M., Mäki-Turja, J., Bygde, S. & Norström, C. (2009). Towards Response-Time Analysis of Complex Real-Time Systems by using ParametricWorst-Case Execution-Time Estimate on Tasks – A Case Study for Robotic Control System. In: 21st Euromicro Conference on Real-Time Systems (ECRTS 09) Work-In-Progress (WIP) session: . Paper presented at Euromicro Conference on Real-Time Systems (ECRTS 09) Work-In-Progress (WIP) session, July 1-3, 2009, Dublin, Ireland. Dublin, Ireland
Open this publication in new window or tab >>Towards Response-Time Analysis of Complex Real-Time Systems by using ParametricWorst-Case Execution-Time Estimate on Tasks – A Case Study for Robotic Control System
Show others...
2009 (English)In: 21st Euromicro Conference on Real-Time Systems (ECRTS 09) Work-In-Progress (WIP) session, Dublin, Ireland, 2009Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Dublin, Ireland: , 2009
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-8954 (URN)
Conference
Euromicro Conference on Real-Time Systems (ECRTS 09) Work-In-Progress (WIP) session, July 1-3, 2009, Dublin, Ireland
Available from: 2010-03-03 Created: 2010-03-03 Last updated: 2015-07-31Bibliographically approved
Lu, Y., Cicchetti, A., Bygde, S., Kraft, J., Nolte, T. & Norström, C. (2009). Transformational Specification of Complex Legacy Real-Time Systems via Semantic Anchoring. In: 2nd IEEE International Workshop on Component-Based Design of Resource-Constrained Systems (CORCS 2009) @ COMPSAC: . Paper presented at IEEE 33rd International Computer Software and Applications Conference Location: Seattle, WA Date: JUL 20-24, 2009 (pp. 1183-1188).
Open this publication in new window or tab >>Transformational Specification of Complex Legacy Real-Time Systems via Semantic Anchoring
Show others...
2009 (English)In: 2nd IEEE International Workshop on Component-Based Design of Resource-Constrained Systems (CORCS 2009) @ COMPSAC, 2009, p. 1183-1188Conference paper, Published 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.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-8940 (URN)10.1109/COMPSAC.2009.184 (DOI)000274261400189 ()2-s2.0-70449643717 (Scopus ID)978-1-4244-4525-7 (ISBN)
Conference
IEEE 33rd International Computer Software and Applications Conference Location: Seattle, WA Date: JUL 20-24, 2009
Available from: 2010-03-03 Created: 2010-03-03 Last updated: 2013-12-03Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0001-9341-4031

Search in DiVA

Show all publications