Static Analysis of Embedded Software with Priority ... · Static Analysis of Embedded Software with Priority Scheduling and Interrupts ... 7.3 Obstacle Avoiding Car ... The autonomous

TECHNISCHE UNIVERSITAT MUNCHENLehrstuhl fur Informatik II

Static Analysis of Embedded Softwarewith Priority Scheduling and

Interrupts

Martin D. Schwarz

Vollstandiger Abdruck der von der Fakultat fur Informatik der Technis-chen Universitat Munchen zur Erlangung des akademischen Grades eines

Doktors der Naturwissenschaften (Dr. rer. nat.)

genehmigten Dissertation.

Vorsitzender:

Prufer der Dissertation: 1. Prof. Dr. Helmut Seidl2.

Die Dissertation wurde am 14.05.2014 bei der Technischen UniversitatMunchen eingereicht und durch die Fakultat fur Informatik am .......................angenommen.

VI

Abstract

The OSEK1 operating system is a widely used automotive standard relyingon priority scheduling and interrupts. The peculiarities of embedded sys-tems, especially the presence of interrupts, make static analysis of such sys-tems a challenging task. While a lot of good analyses exist for single andmulti-threaded programs, the results for concurrent embedded systems werenot satisfactory, mainly due to the different scheduling paradigms. The workpresented here provides methods to leverage the vast ecosystem of abstractinterpretation to programs with preemptive scheduling and interrupts.

One difficulty of interrupt-driven programs is that interrupts introduce aform of concurrency, thus resulting in unexpected program behavior. As onebenchmark problem, a notion of data-races for OSEK programs is consid-ered and it is shown how to exploit the intricate properties of the priorityscheduling, and especially the priority ceiling protocol to construct a pre-cise analysis. Surprisingly, real world OSEK programs often do not rely onthe protection mechanisms provided by the operating system but introducehand-crafted synchronization primitives. For a large class of such program-ming patterns based on flag variables, a dedicated analysis is provided thatallows the verification of race freedom as well as to expose subtle bugs inthese ad-hoc protocols.

1 Offene Systeme und deren Schnittstellen fur die Elektronik in Kraftfahrzeugen;English: ”Open Systems and their interfaces for the Electronics in Cars”

VII

Zusammenfassung

Dem OSEK2 Betriebssystem liegt eine weit verbreitete Spezifikation derAutomobil-Industrie zugrunde. Der Kern des Betriebssystems basiert auf In-terrupts und dem Scheduling anhand von Prioritaten. Die Eigenheiten voneingebetteten Systemen, insbesondere die haufigen Interrupts, machen diestatische Analyse solcher Systeme zu einer großen Herausforderung. Fur se-quentielle und parallele Programme gibt es bereits viele gute Analysetech-niken. Angewandt auf nebenlaufige eingebettete Systeme waren die Ergeb-nisse jedoch nicht zufriedenstellend. Die vorliegende Arbeit zeigt Methodenauf, die es erlauben, die vielfaltigen Analysen, die auf abstrakter Interpreta-tion basieren, auch erfolgreich auf Programme mit Interrupts und preemp-tivem Scheduling anzuwenden.

Eine Schwierigkeit bei Interrupt-basierten Programmen liegt darin, dassInterrupts zu einer Art von Nebenlaufigkeit fuhren, die unerwartetes Pro-grammverhalten auslosen kann. Als Beispiel hierfur dient eine Form vonData-Races fur OSEK Programme. Es wird gezeigt, wie die komplexenEigenschaften von Prioritats-basiertem Scheduling und insbesondere des Pri-ority Ceiling Protokolls ausgenutzt werden konnen, um prazise Analysenzu konstruieren. Uberraschenderweise vermeiden echte OSEK Programmehaufig die durch das Betriebssystem zur Verfugung gestellten Schutzmech-anismen. Stattdessen werden handgeschriebene Synchronisierungmethodeneingefuhrt. Fur eine große Gruppe solcher Synchronisierungmethoden, die aufMarkierungsvariablen basieren, wird eine spezialisierte Analyse angegeben.Diese Analyse erlaubt es, die Abwesenheit von Data-Races in Programmenmit handgeschriebener Synchronisierung zu verifizieren und subtile Sicher-heitslucken dieser Methoden offenzulegen.

2 Offene Systeme und deren Schnittstellen fur die Elektronik in Kraftfahrzeugen;

VIII

List of Original Publications

Some of the results of this work have been previously presented in the fol-lowing publications:

1) Martin Daniel Schwarz, Helmut Seidl, Vesal Vojdani, Peter Lammich,and Markus Muller-Olm. Static analysis of interrupt-driven programssynchronized via the priority ceiling protocol. In POPL, pages 93104,ACM Press, 2011.

2) Martin Daniel Schwarz, Helmut Seidl, Vesal Vojdani and Kalmer Apinis.Precise Analysis of Value-Dependent Synchronization in Priority Sched-uled Programs. In VMCAI, pages 21-38, LNCS 8318, Springer BerlinHeidelberg, 2014.

IX

Acknowledgements

First and foremost, I would like to thank Prof. Dr. Helmut Seidl. My academiccareer would not have gotten anywhere without his constant support andcriticism of my ideas and writing.

The content and quality of my work has greatly profited from my co-workers Dr. Vesal Vojdani, Kalmer Apinis, Dr. Peter Lammich and Prof.Dr. Markus Muller-Olm. I do not have room to name all the colleagues andfriends who have helped me over the last years but I thank them all. A specialthanks to those that proof read this thesis, especially in its earlier stages.

Next, I would also like to thank Gordon and Falk for identifying theproblem with user-defined synchronization. Their patient testing of the proto-type tool on industrial code was invaluable, and I appreciate them remaininganonymous in order to spare me from requiring company approval.

Finally, I thank Petra and my family for keeping me motivated.

The research leading to this thesis and the prior publications has receivedfunding from the ARTEMIS Joint Undertaking under grant agreement No.269335 (MBAT) and from the German Research Foundation (DFG).

Table of Contents

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2 The OSEK Operating System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1 Components of OSEK systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Scheduling in OSEK Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.3 Conformance Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.4 OSEK API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 A Stack-based OSEK Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.1 Semantics of OSEK Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.2 Stack-Based Semantics of OSEK . . . . . . . . . . . . . . . . . . . . . . . . . 223.3 Constraint System for the Stack-based Semantics . . . . . . . . . . . 263.4 Race Detection in the OSEK Model . . . . . . . . . . . . . . . . . . . . . . . 293.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4 Resource and Priority Analysis of OSEK Programs . . . . . . . 354.1 The Core Priority Ceiling Model and its Semantics . . . . . . . . . 374.2 Data Races and Nontransactional Behavior . . . . . . . . . . . . . . . . 424.3 Analyzing Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.4 Analyzing Data Races . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.5 Analyzing Transactionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.5.1 Tasks Without Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 494.5.2 Tasks With Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.6 Linear Equalities For Priority Ceiling Programs . . . . . . . . . . . . 554.7 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.8 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.9 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5 Value-dependent Synchronization . . . . . . . . . . . . . . . . . . . . . . . . . 655.1 OSEK Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.2 Inter-procedural Analysis of Flags . . . . . . . . . . . . . . . . . . . . . . . . 695.3 Intra-Interrupt Flag Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705.4 Simple Analysis of Flags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735.5 Precise Analysis of Flags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

XII Table of Contents

5.6 Data Race Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795.7 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815.8 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 835.9 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

6 Invariants and Privatization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 856.1 Call String Analysis of OSEK Programs . . . . . . . . . . . . . . . . . . . 866.2 Global Invariants with Privatization . . . . . . . . . . . . . . . . . . . . . . 90

6.2.1 Privatization with Flags . . . . . . . . . . . . . . . . . . . . . . . . . . . 936.2.2 General Privatization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

6.3 Layered Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 956.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

7 Benchmark Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1017.1 Robotic Arm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1017.2 Line Following Car . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1037.3 Obstacle Avoiding Car . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1047.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

8 Practical Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1078.1 OIL-file Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1078.2 Grouping of Warnings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1088.3 Flag Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1088.4 Convention Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1088.5 Variant Code Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

9 Future Prospects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1119.1 Extended Conformance Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . 1119.2 Hook Routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1129.3 Precise Task Activation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1129.4 Multi-core Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

List of Figures

2.1 OIL-file and source code structure of an OSEK program. . . . . . 82.2 Structure of an OSEK build process. . . . . . . . . . . . . . . . . . . . . . . . 92.3 OSEK Scheduler. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.4 Preemption. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.5 Scheduling with priority ceiling. . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.6 Scheduling with events. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.7 Conformance classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.1 Example program. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.2 Queue-based semantics (⇒). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.3 Scheduling of tasks in the queue . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.4 Stack-based semantics (→). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.1 Example program. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.2 Priority ranges. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.3 Example program with procedures. . . . . . . . . . . . . . . . . . . . . . . . . 554.4 Runtimes of the analyzer on chain n. . . . . . . . . . . . . . . . . . . . . . . 62

5.1 Example code of program with a flag f. . . . . . . . . . . . . . . . . . . . . . 655.2 Example program with a flag f. . . . . . . . . . . . . . . . . . . . . . . . . . . . 685.3 Extended example code of program with a flag f. . . . . . . . . . . . . 80

6.1 Example program. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 876.2 Example program with flag privatization. . . . . . . . . . . . . . . . . . . . 936.3 Example of information with layered invariants. . . . . . . . . . . . . . 95

7.1 Lego model of the robotic arm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1027.2 Lego model of the line follower. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1037.3 Lego model of the obstacle avoider. . . . . . . . . . . . . . . . . . . . . . . . . 104

1 Introduction

In August 1888, one of the first automobiles drove approximately 100 kilo-meters over empty cross-country roads between Mannheim and Pforzheim.At that time this was a great achievement. In August 2013, a research vehi-cle autonomously covered the same distance following the same route. Thistime, however, the roads were not empty. The autonomous car had to nav-igate through dense city traffic, roundabouts, and share the cross countryroads with other cars and agricultural vehicles. Once again this was a greatachievement. But in the 125 years between these events the challenges havechanged a lot. The configuration of the combustion cycle, fuel piping, and geartransmission might still hold optimization potential, but great achievementstoday arise from other components. Electronic sensor systems and embed-ded micro controllers make the difference in modern automotive technology.The applications range from entertainment and navigation systems, to theconfiguration and control of the engine, as well as steering and breaking as-sistance. As demonstrated by the autonomous car, these applications maybecome more than mere assistance. As the systems become more potent andmore complex, it becomes increasingly important to verify safety propertiesof embedded systems. Extensive testing and source code review are necessary,and are already part of the production process of the automotive industry.But a car already has too many and too complex systems to exhaustivelytest.

Probably the most prominent examples showcasing the need for verifica-tion of embedded systems and the challenges involved are the cases of invol-untary accelerating cars that occurred in the USA between the years 2007and 2010. Several incidents have been reported where cars leaving a highwaysuddenly accelerated and crashed, leading to injuries and even loss of life.These cars all have undergone the regular development and testing process.And for a long time driver errors or slipped floor mats jamming the pedalswere considered the cause of these accidents. A technical assessment reportby NASA [41] stated that it could not confirm software flaws as the reason forthe acceleration but did not exclude them either. Since there were still ongo-ing court actions regarding these incidents, an independent group of expertsthoroughly investigated the code again [6]. The results of this investigationwere astonishing. The controller program of these vehicles implemented an

2 1 Introduction

OSEK1 [22] operating system but it did not fully follow the standard and wasnot certified. It consisted of 24 tasks and over 11.000 global variables mak-ing it essentially impossible to fully test. Despite the tests and analysis doneby the manufacturer it turned out that a memory inconsistency could leadto silent failure of certain tasks. One crucial part controlled by these taskswas the position of the throttle valve. The failure could therefore lead to thethrottle valve getting stuck and in the worst case it could take the systemabout 30 seconds to detect the problem and reboot. This is enough time toaccelerate a car from 90km/h to over 150km/h while approaching the turn ofa highway exit. Given that it took the embedded experts over a year of fulltime work to discover this behavior and reproduce it with testing equipment,it is clear that such flaws are very hard to detect with current techniques.This is especially the case for memory corruption since the sources of mem-ory corruption are manifold. The investigated program exhibits several suchfaults, reaching from stack and buffer overflows over pointer arithmetic andvariable casts to data races. Testing can only verify that a given test case istreated correctly or exposes a program flaw. Testing can not guarantee that aprogram operates correctly in all possible situations. In contrast, static anal-ysis and abstract interpretation investigate all possible situations a programcan encounter. Due to the abstractions and (over-)approximations it is hardto construct a concrete test case for the results provided by static analysistechniques.

The static program analysis community has tackled these problems for along time and a wealth of analysis techniques and tools exist to deal withthem. However, most of this work focuses on sequential programs or thread-based parallelism. An OSEK system like the one investigated above existsin a different environment. The strict real-time constraints, highly variablehardware, short development times, long maintenance cycles, and safety crit-ical applications of the automotive industry require specialized programmingtechniques. A purely sequential program will rarely be able to meet the real-time demands, while a fully threaded program will struggle with the hardwareconstraints. The OSEK specification [22] provides a unified middle groundthat can run on small embedded micro controllers and by means of pre-emption, react to real-time input. This thesis presents novel techniques andadapted analyses targeting OSEK programs specifically and preemptive em-bedded systems in general. Since the most common programming languageused for embedded systems and especially OSEK programs is C source code,examples will be presented with a C-like syntax throughout this thesis. Thefocus of the work presented is on the discovery of data races. A data race is asituation where two or more tasks interfere while accessing shared memory.This can result in inconsistent data and even memory corruption, which, asillustrated above, can have severe consequences.


1 Introduction 3

Outline

Chapter 2 gives an overview of the structure and components of the OSEKoperating system. First the main components and their general propertiesare presented, followed by an explanation of the principles of the schedulerand the priority ceiling protocol. Then, the different conformance classesof OSEK programs will be introduced and the differences between themare discussed. Finally, there will be an overview of the most commonOSEK API functions.

Chapter 3 defines an operational semantics of OSEK programs, which is thantransformed into a stack based system that is further translated to a pushdown system. Finally, a constraint system based on the semantic rules isset up in order to compute the first data race results.

Chapter 4 reduces the previous model to its core components. The semanticsis adjusted and simplified accordingly. With this semantics the notions ofdata race and non-transactional behavior are defined. Next, an analysisof priorities and resources is introduced which enables the detection ofdata races based on priority differences. This approach is then extendedto reason about whole functions in order to discover non-transactionalbehavior. The final contribution of this chapter is an analysis of linearequalities adapted to OSEK programs. This is made possible by buildingon the constraint system used for the resource analysis.

Chapter 5 starts by introducing flags as another means of synchronization inOSEK programs. Next comes the first look at inter-procedural analysis offlag values, which continues into an analysis of programs with interrupts.Based on this analysis, two approaches to the analysis of flag based syn-chronization are discussed. Finally, this chapter demonstrates how flaginformation can be used to improve precision of data race analyses.

Chapter 6 presents a call string based analysis system for OSEK programsand an extension of a global invariant based approach is introduced. Theresults of an interval analysis with both approaches are compared. Nextfurther extension of the global invariant approach are given which illus-trate that not limited to OSEK programs or intervals. Finally, a newapproach based on several invariants is introduced, which for OSEK pro-grams is as precise as the call string 0 approach.

Chapter 7 discusses the experiences from various student projects whereOSEK was employed to solve medium scale programming tasks.

Chapter 8 presents the technical additions necessary for the prototype toanalyze industrial programs.

Chapter 9 discusses the aspects of the OSEK program that have not beenfully addressed in previous chapters.

Chapter 10 summarizes the presented work and gives a small overview offuture work.

2 The OSEK Operating System

OSEK1[22] is a set of specifications not only for an embedded operatingsystem, but for the whole communication stack of automotive embeddedsystems. OSEK was designed to provide a standard software architecture forall embedded systems throughout the car. Development started in 1993 byGerman automotive companies and the University of Karlsruhe. One yearlater, it was joined with the French VDX2, which lead to the official namebecoming OSEK/VDX. Throughout this thesis the shorter OSEK will beused.

The original OSEK operating system has been extended several times.The specification OSEKcom allows independent OSEK systems which can bedistributed through the car to communicate. OSEKtime extends the time-triggered features present in the OSEK operating system. A more recentdevelopment is AUTOSAR3 [9] which unifies and extends all three of thesespecifications. A main goal of AUTOSAR is to allow a better integration intothe processes of all parties involved in developing, building and maintaininga car. At the core, it is, however, still an OSEK compliant operating systemwhich is fully backward compatible. Conversely, the results presented in thisthesis can be applied to AUTOSAR programs as long as the programs canbe modeled by the abstracted systems presented in the following chapters.

2.1 Components of OSEK systems

An OSEK program consists of several components. The main program logicis contained in dedicated C-functions called interrupts and tasks. Interruptsare typically triggered by the hardware and can occur any time. Tasks onthe other hand are activated by the program itself. In addition to tasks andinterrupts, so called hooks are called at specific program points. For time-dependent programs alarms and counters are used. A counter, or timer, mea-sures the time and counts ticks. An alarm observes a counter and triggers


2 Vehicle Distributed eXecutive3 AUTomotive Open System ARchitecture

6 2 The OSEK Operating System

when a certain number of ticks has occurred. For synchronization betweeninterrupts and tasks, OSEK provides resources and events. An OSEK re-source is used like a lock but provides additional protection by increasing thepriority of the running task or interrupt when it is acquired. An event is theOSEK representation of wait/notify synchronization.

InterruptInterrupts are used to react to environmental conditions like physicalchanges in the hardware or sensor data. The handling of interrupt serviceroutines by the OSEK operating system is subdivided into two categories:ISR category 1: Such interrupts closely correspond to micro controller

interrupts. The use of operating system procedures is not allowed,andupon completion the execution resumes with the instruction wherethe interrupt occurred.

ISR category 2: Category 2 interrupt service routines are handled bythe regular scheduler and when a category 2 interrupt terminatesrescheduling takes place. Operating system procedures can be used,but are limited regarding events.

Both types of interrupts have to be statically declared with their priorityand in the case of a category 2 interrupt, the resources and events beingused must also be statically declared.

TaskTasks execute the main functions of the program. They are staticallydeclared with their priority, and the resources and events they use. Taskshave full access to the operating system services. There is a distinctionof tasks that depends on whether or not events are usedBasic tasks: Basic tasks do not use events and, once started, only stop

executing upon completion or when the operating system switches toa higher priority task or interrupt.

Extended tasks: An extended task uses events and can enter a waitingstate until a given event is set. Once the event is set, the task can bescheduled by the operating system and resumes executing with thenext instruction.

HooksAt several points during the execution of an OSEK program it is possibleto execute additional code. These hook routines are part of the operatingsystem. Their main use is to do error handling, tracing, and debugging.Hooks cannot access resources and only read the state of tasks and events.Their execution priority is considered to be between category 1 and 2Interrupts. Therefore, they are allowed to suspend and resume category1 interrupts in case full exclusive access is required. There are five differenthooks:ErrorHook: This hook is called whenever a API function returns an

error status unless it was already called from inside ErrorHook. Fur-thermore, it is called when an alarm expires and there is an error

2.1 Components of OSEK systems 7

during task activation or event setting. The hook allows user definederror handling and recovery.

PreTaskHook: This Hook is called by the operating system after a newtask has been scheduled to run but before it starts to execute. Thehook allows to trace the order in which tasks are executed.

PostTaskHook: This hook is called by the operating system after a taskhas executed it’s last statement but before a new task is scheduledto run. The hook allows unit testing of the task.

StartupHook: This hook is called at the end of the operating systeminitialization, and allows the initialization of device drivers.

ShutdownHook: This hook is called during the operating system shutdown after ShutdownOS has been called. The hook allows user definedshut down functionality.

CounterCounters are characterized by an initial value, a time interval, and a max-imal value. Whenever the given time interval has passed, the operatingsystem increases the counter value by one. This is called a tick. Severalalarms can be connected to the same counter.

AlarmAlarms trigger certain actions whenever their counter reaches a givenvalue. Alarms can activate tasks or set events. Alarms are used to providerecurring functionality and time dependent behavior to the program.

ResourceResources are used to synchronize concurrent accesses of tasks and in-terrupts to program sequences, memory or hardware areas. This is doneby increasing the priority of a task acquiring a resource. The increasedpriority is guaranteed to be high enough that no other task or interruptthat uses the same resource can preempt the task holding the resource.

EventEvents are an alternative method of synchronization between tasks andinterrupts. This method does not rely on priorities. Instead, a task canwait to resume execution until a given event is set. Events can be set byalarms or directly by tasks and interrupts.

The components and properties of an OSEK program are defined atcompile-time using the OSEK Implementation Language (OIL). The sepa-rate OIL-file defines the properties of all the components of the program andmakes them known to the operating system. The OIL-file connects the appli-cation source code to the OSEK operating system. An example of an OSEKprogram and the corresponding OIL-file can be seen in figure 2.1.

The operating system, OIL-file and the application source code are thencompiled to a single executable. A graphic representation of the structure ofthe OSEK build process is shown in figure 2.2 taken from the OIL specifica-tion [21].


OIL− f i l e :

COUNTER C1{

MINCYCLE = 1 ;MAXALLOWEDVALUE = 1000 ;TICKSPERBASE = 1 ;

} ;

RESOURCE resource1{

RESOURCEPROPERTY = STANDARD;} ;

TASK T3{

AUTOSTART = FALSE;PRIORITY = 5 ;ACTIVATION = 1 ;} ;

TASK T2{

AUTOSTART = FALSE;PRIORITY = 3 ;ACTIVATION = 1 ;} ;

TASK T1{

AUTOSTART = FALSE;PRIORITY = 1 ;ACTIVATION = 1 ;RESOURCE = resource1 ;} ;

ISR INT2{

PRIORITY = 2 ;} ;

ALARM A1{

COUNTER = C1 ;ACTION = ACTIVATETASK{

TASK = T1 ;} ;AUTOSTART = TRUE{

ALARMTIME = 1 ;CYCLETIME = 20 ;} ;

} ;

ALARM A2{

COUNTER = C1 ;ACTION = ACTIVATETASK{

TASK = T2 ;} ;AUTOSTART = TRUE{

ALARMTIME = 1 ;CYCLETIME = 10 ;} ;

} ;

Source code :

int x = 0 ;int y = 0 ;int z = 0 ;

TASK(T1){

[ . . . ]GetResource ( r e source1 ) ;[ . . . ]

x = y + z ;[ . . . ]Re leaseResource ( r e source2 ) ;[ . . . ]TerminateTask ( ) ;

}

TASK(T2){

[ . . . ]TerminateTask ( ) ;

}

TASK(T3){

[ . . . ]TerminateTask ( ) ;

}

ISR (INT1){

[ . . . ]GetResource ( r e source1 ) ;[ . . . ]

y = z − x ;[ . . . ]Re leaseResource ( r e source2 ) ;[ . . . ]

}

ISR (INT1){

[ . . . ]}

Fig. 2.1. OIL-file and source code structure of an OSEK program.

2.2 Scheduling in OSEK Programs 9

Fig. 2.2. Structure of an OSEK build process.

2.2 Scheduling in OSEK Programs

The scheduling principle employed is called the priority ceiling protocol. Thepriority ceiling protocol is a variant of the priority inheritance protocols whichare discussed in e.g. [42]. The general principle of all priority inheritanceprotocols is that tasks or interrupts with higher priority execute first, andusing shared resources leads to predefined priority changes. Similarly, there isa method to decide the execution order of same priority tasks or interrupts.The priority ceiling protocol used by the OSEK operating system schedulestasks or interrupts with the same priority on a first-in-first-out basis. Seefigure 2.3 taken from the OSEK specification [22].

In case a task or interrupt becomes ready that has a higher priority thanthe currently executing task or interrupt, the OSEK scheduler will stop theexecution and reschedule. The new highest priority task or interrupt thenstarts executing. This process is called preemption. See figure 2.4 taken fromthe OSEK specification [22].

OSEK resources are used to temporarily prevent some preemption in orderto exclusively accesses shared resources, e.g. shared memory. To every OSEKresource the priority ceiling protocol assigns a so called ceiling priority whichis the maximal static priority of all tasks and interrupts that may access thisresource. Which resources a task or interrupt may access has to be specifiedin the OIL-file. Therefore the ceiling priorities of resources can be computedby analyzing the OIL-file. The dynamic priority of a task or interrupt isthen given by the maximum of its static priority and the ceiling priorities of


Fig. 2.3. OSEK Scheduler.

Fig. 2.4. Preemption.

resources currently acquired. See figure 2.5 taken from the OSEK specification[22] which shows a possible execution of the program shown in figure 2.1.

The priority ceiling protocol with resources has two important propertiesfor real-time systems [42]. First, it is deadlock free. Since a task or interruptcannot be preempted by another task or interrupt which uses a resourceacquired by the currently running task, there can never be two tasks orinterrupts that mutually require a resource held by the other in order toproceed. Obviously, if the preempting task or interrupt does not access anyof the resources held by the preempted task then there will be no deadlock.On the other hand, if there is a resource accessed by both tasks or interrupts,then the dynamic priority of the running task will be at least the staticpriority of the task attempting to preempt and therefore the preemption willnot succeed until the resource is released. Again, no deadlock can occur.Secondly, the priority ceiling protocol minimizes priority inversion. Priority

2.2 Scheduling in OSEK Programs 11

Fig. 2.5. Scheduling with priority ceiling.

inversion describes the situation when a task or interrupt has to wait for atask or interrupt with lower static priority. The OSEK scheduling ensuresthat priority inversion is limited to one block of resource acquirement. Thisis true since tasks or interrupts which do not require the resource are alsoblocked if they have priority lower than the ceiling priority of the resource.Consequently there might be more tasks waiting, but the duration of the waitfor a lower priority task is strictly limited.

As was stated before, there is another synchronization mechanism presentin the OSEK operating system that is based on events. An event has twostates. It can either be set or clear. When a task waits for an event e which isclear the task will stop execution and enter a waiting state. The task rejoinsthe priority based scheduling process once the event e is set. See figure 2.6taken from the OSEK specification [22].

Events allow to synchronize without interfering with tasks and interruptsthat do not use the event. Both properties of pure priority ceiling schedulingregarding deadlocks and priority inversion are lost when event synchroniza-tion is used. This, however, only effects the theoretical guarantees. In practice,the system still exhibits a low chance for deadlocks and a low amount of pri-ority inversion. The events used by a task or interrupt have to be specifiedin the OIL-file.


Fig. 2.6. Scheduling with events.

BCC1 BCC2 ECC1 ECC2

Multiple task no yes Basic: no Basic: yesactivation Extended: no Extended: no

Number of task 8 16priorities

Multiple tasks no yes no yesper priority

Number of 1 8resources (res scheduler)

Number of — 8events per task

Fig. 2.7. Conformance classes.

2.3 Conformance Classes

Support for synchronization and general computational power varies betweenmicro controllers. Additionally, some features of the OSEK operating systemmay be unwanted. Therefore, OSEK programs are subdivided into confor-mance classes.

A conformance class limits the size of the programs and the usable syn-chronizations features. There are four conformance classes, i.e., BCC1, BCC2,ECC1, ECC2. The basic conformance classes BCC1 and BCC2 can only useresources for synchronization. Resources defined by the user in the OIL-filecan be used in all conformance classes except BCC1. The conformance classesBCC1 and ECC1 have unique priorities, i.e. no two tasks have the same staticpriority. See the table in figure 2.7 for more details on the differences betweenthe conformance classes.

2.4 OSEK API

In the source code of a program OSEK features are mostly invisible. TheOSEK operating system provides a rich interface which can be found in full

2.4 OSEK API 13

detail in the OSEK specification [22]. For the work presented here the mostimportant interface functions are GetResource and ReleaseResource whichboth take a resource parameter and acquire or release the given resource, re-spectively. Other functions involved in synchronization but not using eventsare DisableAllInterrupts and EnableAllInterrupts, which block all in-terrupts, SuspendAllInterrupts and ResumeAllInterrupts, which alsoblock all interrupts but allows nested calls, e.g. for use in libraries, and finallySuspendOSInterrupts and ResumeOSInterrupts, which only block operat-ing system induced interrupts, i.e. interrupts of category 2, while allowingnested calls. In all cases, further calls of other OSEK API calls are forbiddenuntil all pairs have been closed. Event handling functions are not introducedhere because the next chapters will focus on the basic conformance classesBCC1 and BCC2 which exclude events.

3 A Stack-based OSEK Model

The conformance classes discussed in chapter 2 allow for different kinds of for-malization of OSEK1[22] programs. This section will investigate how closelyOSEK programs belonging to the different conformance classes can be rep-resented as push-down systems. Despite the complex control-flow introducedby interrupts and preemption, programs written for an OSEK operating sys-tem are meant to exhibit an essentially sequential behavior. The first goal ofthis section is to make this sequential behavior explicit. Then, this behaviorwill be exploited in order to transfer techniques for the analysis of sequen-tial programs to OSEK programs. At the end of the section, related work isdiscussed which deals with the components of OSEK programs that do noteasily translate to a sequential semantics.

Based on this push-down semantics, a first notion of data races forinterrupt-driven programs is defined. For this notion, an algorithm is pre-sented that precisely detects all data races for OSEK programs that belongto basic conformance classes.

The OIL-file accompanying every OSEK program is an important sourceof structural information. An example of the kind of information that is pro-vided by the OIL-file can be seen in the excerpt in figure 3.1. For this section,the priority and set of accessible resources of tasks and interrupts are the mostimportant facts. The autostart tag determines whether a given task is readyfor execution at program start. Furthermore, the number of instances of atask that can exist simultaneously is defined. Interrupts have a more fixedbehavior, e.g., they cannot autostart and are limited to one instance, andtherefore, the interrupt service routines define fewer attributes. This infor-mation about tasks and interrupts is made accessible to the analysis throughfunctions generated during preprocessing. For a more detailed description ofOIL-files see chapter 2.

Recall that the OSEK operating system employs the priority ceiling pro-tocol. This means that activated tasks and interrupts are scheduled in orderof priority. Once started, a task or interrupt will run to termination unlessa task or interrupt of higher priority occurs and preempts it. These prop-erties allow the translation of OSEK programs to a sequential, stack-based


16 3 A Stack-based OSEK Model

Ie I1 I2 I3 Ir

Te T1 T2 Tr

T ′e T ′

1 T ′2

T ′3

T ′4 T ′

5 T ′r

get(A) a++ rel(A) act(T )

IRSoff print(a) IRSon

a=0 get(A)

a>0 a--

a<1 rel(A)

true

false

[...]

TASK T’ {

PRIORITY = 1;

AUTOSTART = TRUE;

ACTIVATION = 1;

RESOURCE = A;

[...]

};

TASK T {

PRIORITY = 3;

AUTOSTART = FALSE;

ACTIVATION = 2;

[...]

};

ISR I{

PRIORITY = 10;

RESOURCE = A;

[...]

};

Fig. 3.1. Example program.

execution model presented in section 3.2. The ceiling priorities introducedfor synchronization by the priority ceiling protocol fit well into this model.The treatment of events, however, is less clear. Therefore the presented tech-niques are limited to programs belonging to the basic conformance classes.Furthermore, hook routines will not be considered since typical uses of hookroutines should not interfere with the execution of the application code.

The program in figure 3.1 is an instance of a consumer-producer schemeand will serve as a running example throughout this section. OSEK li-brary function names have been shortened by replacing GetResource() andReleaseResource() with get() and rel(), respectively. Similarly, the functionsDisableAllInterrupts() and EnableAllInterrupts() have been replacedwith IRSoff and IRSon, respectively. Additionally, ActivateTask() has beenshortened to act() and calls to TerminateTask() have been omitted. In thesemantics in figure 3.2 TerminateTask() is abbreviated by kill.

The program variable a represents a counter of items available for con-sumption. The task T ′ consumes an item (not shown) and decreases thecounter if there is at least one item available; otherwise, it waits until the

3.1 Semantics of OSEK Programs 17

next item arrives. The interrupt I is triggered as soon as a new item is pro-duced. It increases the counter a and activates the printing task T . This smallprogram already exhibits some of the interesting consequences of the priorityceiling protocol. For example, as T has a higher priority than T ′ the printedoutput will always be at least 1 because T ′ will only be scheduled to resumeafter T has terminated.

Priorities place restrictions on the execution, ruling out many interleav-ings which otherwise would constitute a data race. Consider again the exam-ple above. While holding the resource A, the task T ′ has a ceiling priority of10 because the highest priority task or interrupt declared to use the resourceis I, which has a static priority of 10. Therefore, T ′ cannot be interrupted byI when holding this resource. Note that as long as the resource A is assignedto I in the OIL-file, there is no data race even when the resource acquisitionin the body of I is removed. This is because the interrupt cannot be pre-empted by lower-priority tasks and the ceiling priority of T ′ when it acquiresthe resource A is still 10. This ensures that T ′ cannot be preempted by Ieither. Only if the declaration that I may acquire A is removed from theOIL-file as well can the task T ′ be interrupted at the nodes T ′2,T ′3, and T ′4,since acquiring the resource would no longer raise the priority of T ′. As willbe seen in section 3.4, the presented analysis is sensitive to these distinctions.

The disabling of interrupts can be encoded as a resource that is assignedto all interrupts. This allows the model to remain clean by just definingsemantics for resource handling functions. To verify the absence of races inthe program, the following information will be computed for the nodes wheredata is accessed.

Node Task Resource Queue Offense DefenseI1 I {A} {∅} 10 10T1 T {IRS} {∅, {T}} 3 10T ′3 T ′ {A} {∅} 1 10

As there is no pair of accesses to the variable a where one access has astrictly higher offensive priority than the defensive priority of the other, theprogram is free from races.

3.1 Semantics of OSEK Programs

The first step towards the analysis of OSEK programs is to introduce asmall-step operational semantics which captures the principles of the OSEKoperating system and the priority ceiling protocol in particular. Here, thisis done for programs which conform to the BCC2 conformance class of theOSEK specification. This excludes event-based communication, the preciseanalysis of which is undecidable [46].

Formally, the set of all tasks and interrupts is denoted as Task and theset of all resources is denoted as Res. Each task and interrupt q ∈ Task is


represented as a control flow graph like those shown in figure 3.1. A controlflow graph Gq = (Nq, Eq, qe, qr) consists of a set Nq of program points, a setof edges Eq ⊆ Nq ×Stmt×Nq annotated with program statements, a specialentry point qe ∈ Nq, and a special return point qr ∈ Nq. Let N and E denotethe sets of all nodes and edges, respectively, of all tasks and interrupts.

Since there is no main-function in an OSEK program, an artificial main-task which consists of a single node T and an edge (T, sched, T ) is constructed.This task makes the scheduling and rescheduling of the operating system ex-plicit. The priority of the main task is set to 0 which ensures that it doesnot interfere with the actual program. Execution then starts at T with noresources held and all tasks ready which have the autostart attribute ac-cording to the OIL-file. If there are no auto-starting tasks, nothing happensuntil an interrupt occurs.

To handle priorities, the function P : 2Res → N is computed that mapssets of resources to the maximum (ceiling) priority of the resources in the set.In the example P(A) = 10.

On the hardware level an interrupt is merely a signal that causes the exe-cution of some interrupt handler. For OSEK programs, the OSEK operatingsystem would then look up the corresponding interrupt service routine and,if necessary, perform rescheduling. This would cause the currently executingtask or interrupt to be preempted. Similarly, there is a difference between atasks name and its function. However, since the focus here lies on the pro-gram behavior, task and interrupt will refer to the corresponding function orinterrupt service routine.

During the execution of an OSEK program, tasks have a state that iseither suspended, ready or running. At any given time at most one task isrunning and when a task terminates it becomes suspended. The semantics willalways operate on a node of a task that is running. Ready tasks are kept ina priority queue Q which is represented as a list. Since the priority dependson the set of resources held, the set of held resources is stored along withthe node. The function hd(Q) yields the first, i.e. highest priority, elementand tl(Q) yields the queue without the head. In case the queue is empty hdreturns 〈T, ∅〉.

The auxiliary functions add and push insert an element into the queueas the newest or oldest element of its priority, respectively. The number ofinstances of a task q that are allowed to exist simultaneously is denoted by |q|The function add(u,Q) may return Q unchanged if u = qe and |q| is reached.With πi denoting the projection to the i-th component of a tuple and Q|qthe restriction of the queue to only nodes in Nq, add and push are defined asfollows:


add(〈u,R〉,Q) =

Q u ∈ qe, |Q|q| ≥ |q|〈u,R〉 : Q P(R) > P(π2(hd(Q)))

hd(Q) : add(〈u,R〉, tl(Q)) otherwise

push(〈u,R〉,Q) =

{〈u,R〉 : Q P(R) ≥ P(π2(hd(Q)))

hd(Q) : push(〈u,R〉, tl(Q)) otherwise

In the example program from figure 3.1, |T | = 2, |T ′| = 1, and, since I isan interrupt, |I| = 1. Since there will always be at least one task or interruptrunning, there will be at most three tasks or interrupts in the queue.

According to the OSEK specification, the currently running task iscounted as one active instance. The current definition of add does not takecare of this. It can, however, be simulated by pushing a copy of the runningtask into the queue before calling add and removing it again afterwards. Sincethis would clutter the semantics without gaining precision, this special caseis neglected.

The semantics will only consider the set of held resources to determinethe priority of a task. According to the OSEK specification, though, furtherinformation must be taken into account. These are the static priorities de-fined in the OIL-file; various OSEK library functions disabling interrupts aswell as locking of the scheduler through get. This last case highlights twothings. First, the scheduler is internally already considered to be a resourceand secondly, scheduling modifying statements can be modeled by resourceacquisition. Therefore all these statements will be subsumed by get.

Consider e.g. the disabling of all interrupts. Encoding this function as aninstance of get is done by introducing a resource that is made available toall interrupts. The ceiling priority of this resource then equals the highestpriority present in the program, which will in turn prevent any preemptiononce it is acquired. Similarly, the resource corresponding to the scheduler isavailable to all tasks leaving only interrupts to preempt a task that acquiredit.

Accordingly, distinct artificial resources are created for all library func-tions. The resources are assigned to all affected tasks and interrupts and thelibrary function call is replaced by a call of get() with the correspondingartificial resource.

For the example program of figure 3.1, this means that the commandIRSoff is replaced by get(rISR) where the new artificial resource rISR is as-signed to I and T . The scheduler resource rsched would be assigned to all tasksexcept interrupts. Analogously, the static priority of a task q is representedby the artificial resource rq which is assigned solely to q. The correspondingcommands get() and rel(), will be included directly in the semantics insteadof the source code. Otherwise a task could theoretically be preempted beforestarting and after terminating. With this transformation, all priority infor-mation is bundled in the set of held resources and P can compute it. Thesemantic rules can be seen in figure 3.2.


(u, c, v) ∈ E c ∈ basic 〈R′,Q′〉 = JcK〈R,Q〉〈u,R,Q〉 =⇒ 〈v,R′,Q′〉

basic

(u, sched, v) ∈ E 〈u′, R′〉 = hd(Q) P(R) < P(R′)

〈u,R,Q〉 =⇒ 〈u′, R′, push(〈v,R〉, tl(Q))〉switch

(u, sched, v) ∈ E 〈u′, R′〉 = hd(Q) P(R) ≥ P(R′)

〈u,R,Q〉 =⇒ 〈v,R,Q〉stay

(u, kill, v) ∈ E 〈u′, R′〉 = hd(Q)

〈u,R,Q〉 =⇒ 〈u′, R′, tl(Q)〉kill

q ∈ Irpt R′ = {rq} P(rq) > P(R)

〈u,R,Q〉 ⇒ 〈qe, R′, add(〈u,R〉,Q)〉irpt

Fig. 3.2. Queue-based semantics (⇒).

A state of the semantics consists of the current node u ∈ N , the set of heldresources R ∈ 2Res of the running task, and the queue Q ∈ Queue(N×2Res) ofready tasks and interrupts. For cleanliness of notation components for otherglobal or intra-task information are omitted.

Interrupts are readied by hardware or operating system conditions in-stead of program statements. The irpt-rule models this by not requiring acorresponding edge in the control flow graph. Note that in addition to theOSEK specification, interrupts are also terminated with a call of kill. Thisdoes not change the semantics but allow the treatment of task and interrupttermination with a single kill-rule.

The basic-rule deals with all commands c which are not related toscheduling. For these basic statements the notation c ∈basic is used. Be-sides all C statements, basic contains the OSEK commands get(), rel() andact() which operate on the state as follows:

Jget(r)K〈R,Q〉 = 〈R ∪ {r},Q〉Jrel(r)K〈R,Q〉 = 〈R \ {r},Q〉Jact(q)K〈R,Q〉 = 〈R, add(〈qe, {rq}〉,Q)〉

The priority ceiling protocol is realized by the scheduler routine of theOSEK operating system. The scheduler is not constantly monitoring thequeue. Instead, it acts when certain conditions occur or library functionsare called. Scheduling is, e.g., invoked when a resource is released via thecommand rel(), when readying a task via act(), or terminating a task via kill.The scheduler can also explicitly be called via the command sched. In theexample from the previous section, scheduling may occur at the nodes Tr, T

′5

and T ′r. The completion of an interrupt calls the scheduler, hence a scheduling


may indirectly also occur, e.g., at node T ′1, allowing T to execute before T ′

resumes. On the other hand, the nodes T ′2 to T ′4 are visited continuously asthe priority at these nodes is so high that I is not allowed to run, and thenodes T1 and T2 are also visited contiguously since interrupts are disabled,which again translates to a high priority.

In order to make all calls of the scheduler explicit, all implicit triggersare ignored and instead the command sched is inserted after every triggeringcommand before the semantics is applied. This separates commands modify-ing the program state from commands modifying the control flow. The onlyexception is the command kill where the running task is replaced with thenext task which the scheduler would select. This is expressed by the kill-rulein figure 3.2. This may, due to the queue being empty, result in returning tothe artificial node T where the program would idle until an interrupt occurs.

When the scheduler is called, it selects the ready task with the highestpriority from the queue, changes its state to running, and starts executing it.Should several tasks have the same priority, the oldest one is selected first.See figure 3.3 for a graphical presentation. Note that when a tasks becomesrunning, it keeps its age. In case of preemption, it will still be the oldestamong the same priority tasks. This behavior is already captured by thefunctions push and add defined above. The next task to be selected from thequeue Q is thus retrieved by hd(Q).

. . .

priority(high) (low)

age

(old)

(new)

A B

C

scheduler

Fig. 3.3. Scheduling of tasks in the queue

In figure 3.3 tasks are added at the top of a bucket and removed at thebottom. The scheduler will empty the queue from left to right, currentlyselecting task A as the oldest task in the highest bucket. Once all higherpriority buckets are empty the task B will be selected to run and task B willmove to the bottom of the bucket. When task B is preempted it is pushedback into the bottom of its bucket, keeping the earlier relative order betweenB and C.


After selecting the next task, the scheduler checks whether it has a strictlyhigher priority than the running task. If not, the scheduler will do nothingwhich the stay-rule reflects. Otherwise, preemption occurs. This means thatthe current running task is stopped, its state is changed to ready and theselected task becomes running. See the switch-rule. Note that when a taskor interrupt is selected to run, it has the highest priority of all ready tasks,meaning that in the case of preemption, either a resource was released oranother task or interrupt has become ready during the execution.

In the semantic description, J K is used in the basic-rule to refer to thestandard semantics of C. A specific analysis can replace this with a suitableabstraction of the semantics without interfering with the scheduling.

The queue-based semantics is natural for OSEK programs and can beextended with, possibly recursive, functions. A configuration would then berepresented as a call-stack for the running task together with a task queuewhich now consists of the call-stacks of fresh or preempted tasks. In the nextsection an alternative semantics is presented, that still closely models thesemantics of OSEK programs, but can be extended with functions in a muchcleaner way.

3.2 Stack-Based Semantics of OSEK

In this section it is shown that the queue-based small-step semantics of thelast section is equivalent to a stack-based small-step semantics. There is al-most a one-to-one correspondence between the rules of the semantics of fig-ure 3.2 and the rules of the new stack-based semantics presented in figure 3.4.However, the kill-rule must be split into two cases, namely next and re-sume. The main difference are the data structures for storing ready tasks.Instead of maintaining a single queue, a stack of preempted tasks is main-tained together with a simpler and smaller queue of names of fresh tasks only.Therefore, a call of the scheduler behaves similarly to an indirect functioncall, where the switch-rule and resume-rule, act as call and return, respec-tively. The two cases of the new kill-rule refer to resuming a preemptedtask from the stack and to starting the next task from the queue. The func-tions add and push that handle the queue still apply P to the resource setof their first argument but this set now only consists of the artificial resourcecorresponding to the static priority of the added task. This resource can beretrieved directly from the name of the task and therefore need not be storedinside the queue.

A translation Φ from configurations of the queue-based semantics to con-figurations of the stack-based semantics can be defined as follows:

Φ : N × (2Res × Queue(N × 2Res))→ Stack(N × 2Res)× Queue(Task)

Φ〈u, 〈R,Q〉〉 = 〈φΓ (Q) ; 〈u,R〉, φQ(Q)〉

3.2 Stack-Based Semantics of OSEK 23

(u, c, v) ∈ E c ∈ basic 〈R′,Q′〉 = JcK〈R,Q〉〈Γ ; 〈u,R〉,Q〉 → 〈Γ ; 〈v,R′〉,Q′〉

basic

(u, sched, v) ∈ E R′ = {rhd(Q)} Q′ = tl(Q) P(R) < P(R′)

〈Γ ; 〈u,R〉,Q〉 → 〈Γ ; 〈v,R〉 ; 〈hd(Q)e, R′〉,Q′〉

switch

(u, sched, v) ∈ E R′ = {rhd(Q)} P(R) ≥ P(R′)

〈Γ ; 〈u,R〉,Q〉 → 〈Γ ; 〈v,R〉,Q〉stay

(u, kill, v) ∈ E R′ = {rhd(Q)} Q′ = tl(Q) P(R) < P(R′)

〈Γ ; 〈u, R〉 ; 〈u,R〉,Q〉 → 〈Γ ; 〈u, R〉 ; 〈hd(Q)e, R′〉,Q′〉

next

(u, kill, v) ∈ E R′ = {rhd(Q)} P(R) ≥ P(R′)

〈Γ ; 〈u, R〉 ; 〈u,R〉,Q〉 → 〈Γ ; 〈u, R〉,Q〉resume

q ∈ Irpt P({rq}) > P(R)

〈Γ ; 〈u,R〉,Q〉 → 〈Γ ; 〈u,R〉 ; 〈qe, {rq}〉,Q〉irpt

Fig. 3.4. Stack-based semantics (→).

Note that Task only contains names and no context information. Taskis therefore equivalent to the set of all entry nodes, which is a small finitesubset of N . This will later allow to encode the queue as part of the push-down stack. Suppose that the configuration of the queue-based semantics isgiven by 〈u, 〈R,Q〉〉, then the function φQ removes partially executed tasksfrom the queue Q returning a queue of fresh tasks only. It is given by:

φQ(Q) =

[ ] Q = [ ]

push(q, φQ(tl(Q))) hd(Q) = 〈qE , {rq}〉φQ(tl(Q)) otherwise

The function φΓ builds the stack of partially executed tasks from Q. Thedepth of this stack is at most the number of priorities below the static priorityof the currently running task. The function is defined as follows:

φΓ (Q) =

[ ] Q = [ ]

φΓ (tl(Q)) hd(Q) = 〈qe, {rq}〉φΓ (tl(Q)) ; 〈u,R〉 hd(Q) = 〈u,R〉

Note that the introduced artificial resources are the same in both seman-tics and the sets of held resources are not modified by the translation Φ.Therefore the priority function P commutes with Φ. The following theoremyields the formal correspondence between the two semantics.


Theorem 3.1. For any two reachable configurations 〈u, 〈R,Q〉〉, 〈v, 〈R′,Q′〉〉,the following equivalence holds:

〈u, 〈R,Q〉〉 ⇒ 〈v, 〈R′,Q′〉〉 ⇐⇒ Φ〈u, 〈R,Q〉〉 → Φ〈v, 〈R′,Q′〉〉

Proof. There is a one-to-one correspondence in the structure of the rules ofthe queue-based and the stack-based semantics with the exception of thekill-rule which is simulated by the two rules next and resume. The fol-lowing case distinction on the rules shows that a rule is applicable to a con-figuration of the queue-based semantics if and only if the corresponding ruleis applicable to the translated configuration where the results of the appli-cation are again in relation via the translation Φ. Note that all configura-tions have to be reachable, i.e., have proper priorities. Consider, e.g., the(⇒)-switch-rule at an edge (u, sched, v) and a configuration 〈u, 〈R,Q〉〉 ofthe queue-based semantics. Let 〈u′, R′〉 = hd(Q). Then the (⇒)-switch-rule is applicable if and only if P(R) < P(R′), with resulting configuration〈u′, 〈R′,Q′〉〉 where Q′ = push(〈v,R〉, tl(Q)). On the other hand, considerthe configuration Φ(〈u, 〈R,Q〉〉) = 〈φΓ (Q); 〈u,R〉, φQ(Q)〉 of the stack-basedsemantics. Let R′′ = {rhd(φQ(Q))}. Then the (←)-switch-rule is applica-ble if and only if P(R) < P(R′′). The first step is to prove that R′ = R′′.Let q be the task or interrupt within which u occurs. Then the conditionP(R) < P(R′) implies that also P(rq) < P(R′). Thus, due to the priorityceiling protocol, 〈u′, R′〉 = 〈qe, {rq}〉 for some task or interrupt q ∈ Task sincea partially executed task or interrupt of priority P(R′) could not have beenpreempted by q. Here the assumption that all configurations are reachable isrequired since a configuration could theoretically represent the preemptionof partially executed tasks and interrupts. Such a configuration, however,would be unreachable. Since φQ preserves the relative ordering of tasks andinterrupts, and 〈qe, {rq}〉 = hd(Q), it follows, that also q = hd(φQ(Q)).

It remains to prove that Φ〈u′, 〈R′,Q′〉〉 equals the result of applying the(←)-switch-rule of the stack-based semantics to 〈φΓ (Q); 〈u,R〉, φQ(Q)〉. Thelatter results in 〈φΓ (Q); 〈v,R〉; 〈qe, {rq}〉, tl(φQ(Q))〉. As a consequence thefollowing holds:

Φ(〈v, 〈R′,Q′〉〉) = 〈φΓ (Q′); 〈u′, R′〉, φQ(Q′)〉= 〈φΓ (push(〈v,R〉, tl(Q)); 〈u′, R′〉, φQ(push(〈v,R〉, tl(Q))〉= 〈φΓ (push(〈v,R〉, tl(Q)); 〈qe, {rq}〉, φQ(push(〈v,R〉, tl(Q))〉

Regarding the stack, it has to be shown that:

φΓ (push(〈v,R〉, tl(Q)) = φΓ (Q) ; 〈v,R〉

By the same argument that was used for the head of the queue, alltasks and interrupts in Q of higher priority than P(R) are of the form〈q′′e , {rq′′}〉. Regarding φΓ , this implies that not only φΓ (Q) = φΓ (tl(Q))

3.2 Stack-Based Semantics of OSEK 25

but also φΓ (push(〈v,R〉, tl(Q))) = φΓ (tl(Q)) ; 〈v,R〉 which together yieldthe desired equality.

Finally it has to be shown, that the queues match, i.e.,

φQ(push(〈v,R〉, tl(Q))) = tl(φQ(Q))

Since 〈v,R〉 is a partially executed task or interrupt the following twoequalities hold:

φQ(push(〈v,R〉, tl(Q))) = φQ(tl(Q))

φQ(Q) = push(q, φQ(tl(Q)))

By preservation of the relative orderings of tasks, it follows that q is thehead of the translated queue thus tl(φQ(Q) = φQ(tl(Q). This completes theproof for the switch-rule.

The proofs for the remaining rules are analogous. The presentation there-fore focuses on the simulation of the two disjoint cases of the kill-rule bymeans of the next- and resume-rule, respectively. If the node u′ at thehead of the queue is an entry node qe for some q ∈ Task, when the kill-ruleis applied its set of held resources will equal {rq}. The latter implies thatq = hd(φQ(Q)), and, therefore, that the priority of rq is higher than thepriority of the set of held resources of all partially executed tasks in Q. Thisensures that the priority condition of the next-rule is satisfied while at thesame time the priority condition of the resume-rule is falsified. If, however,the head of Q is a partially executed task or interrupt, it becomes the top ofφΓ (Q) and the priority of its set of held resources is higher than (or equal toand ready for a longer time) the static priority of all tasks and interrupts inQ, in particular all fresh tasks and interrupts. This ensures that the prioritycondition of the resume-rule is satisfied while at the same time the prioritycondition of the next-rule is false.

ut

The stack-based semantics can naturally be extended with potentiallyrecursive functions. The stack then has layers corresponding to preemptedtasks followed by called functions which have not yet returned at the momentof preemption. Analogously, functions can also be added to the queue-basedsemantics. As was hinted at before, this could be achieved by turning each sin-gle node into a stack of nodes corresponding to the task or interrupt togetherwith the called functions which have not yet returned. These stacks wouldthen also have to be stored in the queue in case of preemption. And since onewould then have several stacks, decidability of reachability is no longer given.Theorem 3.1 however also holds for queue-based and stack-based semanticswhen extended with function calls since they do not interfere with the pri-ority ceiling protocol. In this case, the type of the translation Φ is extendedto:


Φ : Stack(N×2Res)×Queue(Stack(N×2Res))→ Stack(N×2Res)×Queue(Task)

Since there are finitely many tasks and interrupts with finite number ofactivation, the set of queues possibly occurring in the stack-based semanticsis finite. Similarly, the occurring sets of resources held are finite. Hence, therules of the stack-based semantics can be interpreted as the transfer functionof a pushdown system where the sets of pushdown symbols and states aregiven by N × 2Res and Queue(Task), respectively.

This also remains true when finite abstractions of local and global dataare added. Therefore, techniques for analyzing pushdown systems [7] canbe applied. In particular, reachability is decidable. When dealing with moreexpressive abstractions for deriving program invariants such as, e.g., affineequalities of variables, alias analysis, etc., techniques from interproceduralanalysis [11] can be applied. For that, it is convenient to represent the small-step semantics as a system of constraints that expresses its collecting seman-tics.

3.3 Constraint System for the Stack-based Semantics

In addition to the program model presented so far, control flow edges cannow be labeled with procedure calls. A procedure f is given by a control flowgraph Gf = (Nf , Ef , fe, fr). The set of all functions is denoted by Proc andwithout loss of generality assume Proc ∩ Task = ∅.

In the following, the stack-based semantics from section 3.2 is transformedinto a constraint-based collecting semantics. The most important change isthat the constraint-based semantics uses a a big-step formulation insteadof the previous small-step formulation. To this end three operators are in-troduced which handle interruptions, preemptions, and termination. The re-sulting constraint system allows the application of standard techniques fromabstract interpretation and interprocedural analysis [10, 11, 32] in order toderive sound analyses of program properties. The analysis of the OSEK modelrelies on constraint based fix-point iteration, and since section 3.2 showed,that OSEK programs can be modeled by a single stack system, conventionaltechniques for interprocedural analysis as discussed in, e.g, [11, 32] can beapplied.

The key observation is that with respect to the stack, preemptions behavelike function calls. When preemption occurs, a new element is pushed ontothe stack and once it is popped again the current task resumes execution.An execution fragment starting with preempting a task (switch,irpt) up toresuming this task (resume) is called a preemption. Note that the next-ruledoes not encode a big-step as it does not return to the initially preemptedtask. Instead, it calls another task which indirectly preempts the initiallypreempted task again. In order to decide whether another task is executed

3.3 Constraint System for the Stack-based Semantics 27

before returning to the initially preempted task, the priority of the initiallypreempted task is added to the state of the system.

Let S = N×2Res×Queue(Task) denote the set of all triples of priorities, setsof held resources, and queues of task names. The complete lattice D of thecollecting semantics is then given by D = 2S, ordered by subset inclusion.For the moment, the remaining components of the concrete C semanticsare omitted but Res ∈ 2Res and Q ∈ Queue(Task), are exemplary for thetreatment of task-local and global information, respectively. Note that thequeue (and possibly other global information) is added to the local state. Inpractice this information would be kept in a global invariant. The constraint-based formulation consists of two layers. First, summaries for functions andpreemptions are specified as transformers from D → D by the constraintsystem [S], and then in a second step the reachable states for all nodes arecomputed as elements of D by the constraint system [R]. Function summariessummarize the executions of a function or preemption to the same-level returnpoint, i.e., after all local calls and preemptions have returned.

[S0] S[qe] ⊇ Id ∀q ∈ Task

[S1] S[v] ⊇ JcK ◦ S[u] (u, c, v) ∈ E, c ∈ basic

[S2] S[v] ⊇ apply(S[fr]) ◦ S[u] (u, call f, v) ∈ E[S3] S[v] ⊇ Tq(S[qr]) ◦ S[u] ∀q ∈ Task \ Irpt, (u, sched, v) ∈ E[S4] S[u] ⊇ Iq(S[qr]) ◦ S[u] ∀q ∈ Irpt, @ q′ s.t. u = q′r[S5] S[rq′ ] ⊇ Kq(S[qr]) ◦ S[u] ∀q ∈ Task \ Irpt, (u, kill, q′r) ∈ E

Based on these summaries, the states reaching a program point, from aset S of possible starting states, are characterized by the following constraintsystem:

[R0] R[Te] ⊇ S

[R1] R[v] ⊇ JcK(R[u]) (u, c, v) c ∈ basic

[R2] R[v] ⊇ apply(S[fr])(R[u]) (u, call f, v) ∈ E[R2′] R[fe] ⊇ R[u] (u, call f, v) ∈ E[R3] R[v] ⊇ Tq(S[qr])(R[u]) ∀q ∈ Task \ Irpt, (u, sched, v) ∈ E[R3′] R[qe] ⊇ Tq(Id)(R[u]) ∀q ∈ Task \ Irpt, (u, sched, v) ∈ E[R4] R[u] ⊇ Iq(S[qr])(R[u]) q ∈ Irpt and @ q′ s.t. u = q′r[R4′] R[qe] ⊇ Iq(Id)(R[u]) q ∈ Irpt and @ q′ s.t. u = q′r[R5] R[q′r] ⊇ Kq(S[qr])(R[u]) ∀q ∈ Task \ Irpt, (u, kill, q′r) ∈ E[R5′] R[q′e] ⊇ Kq(Id)(R[u]) ∀q ∈ Task \ Irpt, (u, kill, q′r) ∈ E

The auxiliary functions apply and apply ′ apply summaries in the returningor terminating context, respectively. They are defined as follows:


apply(f)(S) =

{〈p,R′,Q′〉|∃R,Q, p′ s.t. 〈p,R,Q〉 ∈ S, 〈p′, R′,Q′〉 ∈ f{〈p,R,Q〉}}apply ′(q)(S) =

{〈p,R,Q′〉|∃Q, p′, R′ s.t. 〈p,R,Q〉 ∈ S, 〈p′, R′,Q′〉 ∈ q{〈p′, R,Q〉}}

With these definitions, the operators T (task preemption), I (interrup-tion) and K (kill) are given by:

Tq(f)(S) =apply ′(f){〈P(R), {rq}, tl(Q)〉 | 〈p,R,Q〉 ∈ S, q = hd(Q), P(rq) > P(R)}

Iq(f)(S) =apply ′(f){〈P(R), {rq},Q〉 | 〈p,R,Q〉 ∈ S,P(rq) > P(R)}

Kq(f)(S) =apply(f){〈p, {rq}, tl(Q)〉 | 〈p,R,Q〉 ∈ S, q = hd(Q), P(rq) > p}

Note that the additional condition on u to not be a return node in theconstraints [S4], [R4] and [R4’] which deal with interrupts is consistent withthe stack-based semantics since return nodes can never be reached in the stackbased semantics. Even if return nodes could be reached in the semantics theconstraints on return nodes would be redundant since there is no observabledifference to the interrupt occurring at the following node. The constructionthat interrupts cannot occur at return nodes allows the result of completepreemptions to be gathered at these nodes.

The typical starting state for the shown components would be 〈0, ∅,Q〉where Q consists of all auto-starting tasks. The soundness of the least solutionof this constraint system follows from general abstract interpretation theory[11, 32]. Moreover since the three operators T , I and K mimic the OSEKscheduling policies, the following theorem is obtained.

Theorem 3.2. A state 〈p,R,Q〉 is in R[u] if and only if the stack-basedsemantic can derive the state Γ ; 〈u′, R′〉; 〈u,R〉,Q where P(R) = p

Proof. The full proof is very technical and does not provide additional in-sights. Therefore only the key arguments are presented. The operator T takescare of internal scheduling points by checking the priority and queue condi-tions defined by the semantics. The operator I takes care of interrupts bychecking the priority conditions defined by the semantics. The operator Ktakes care of task termination by applying the summary of the next task inthe queue, whenever it has a priority high enough to preempt the initiallypreempted task. This includes applications of the next-rule. Function callsare treated by the functions apply and apply ′.

ut

The constraint system [R] tracks the possible states of an OSEK programand the resources held at a program point precisely, yet it can still be solvedby the usual means of fixpoint iteration, since all information is finite.

3.4 Race Detection in the OSEK Model 29

3.4 Race Detection in the OSEK Model

In this section, the collecting semantics from the previous section is usedin order to detect data races in OSEK programs. Despite their essentiallysequential structure, non-deterministic behavior occurs in OSEK programsdue to interrupts. These interrupts may violate the assumptions of the useron the exclusiveness of his access to a shared variable. These assumptionsare based on the priorities at which accesses occur. If an access to a globalvariable x occurs at a given priority p, the assumption is, that the currenttask q has the exclusive right to access x until the task terminates or decreasesits priority to guarantee safety for all accesses. Consequently, a race occursif the task q, while still running in priority at least p after the access to x, isinterrupted, and this interrupt leads to another access to x so that the taskq may execute on a different value when it resumes.

Formally, a data race is defined as follows. Let c be a condition on prioritiesand −→c denote a program step where the priority at the source node satisfiesthe condition and −→∗c its transitive closure. Then there is a data race overthe shared variable x if a path of the following pattern exists:

π : Te −→∗ uaccess(x)−→=p v −→∗≥p Ie −→∗>p u′

access(x)−→>p v′ (3.1)

for some interrupt I where u, v are nodes of the same task q which doesnot terminate before the interrupt occurs. For a given shared variable x andpriority p, this property of an execution path can be verified by a small finiteautomaton. Viewing an OSEK program as a pushdown system, yields thefollowing theorem:

Theorem 3.3. Absence of data races for OSEK programs is decidable.ut

It turns out that number of pushdown symbols and states of the push-down system for an OSEK program p is exponential in the maximal numberof simultaneously acquired resources and exponential in the number of tasks,respectively. While the number of simultaneously acquired resources is small(namely 8 OSEK resources plus the artificial resources introduced by thetransformation) the number of occurring tasks can be arbitrarily high. There-fore, an algorithm for detecting data races which is just based on reachabilityof pushdown systems is not very practical.

In the following, an alternative algorithm is presented which determinesfor a given shared variable x, whether a data race over x occurs. For this,non-deterministic branching is assumed. Under this assumption, changes tothe global state cannot influence the control-flow of the program. This allowsthe decomposition of the analysis of data races into separate analyses ofeach task. There exist, however, pathological cases where a task or a part ofa task will never begin/resume execution. This is called starvation and forexample occurs when a task of a higher priority activates itself or contains


a deterministic infinite loop. Starvation is in itself an interesting problempresent in many real-time systems that would warrant further investigation.The presented algorithm is only precise for starvation-free programs.

An intra-task execution path is an execution path without preemptionor interrupts that starts at an entry node qe of a task q. By this definition,reachability of a node via an intra-task execution path is independent of thetask queue. In particular, this holds for start nodes of edges where resourcesare acquired or released as well as start nodes of edges where tasks are ac-tivated. According to the semantics of figure 3.4, the set of held resources isnot modified by a preemption. Together this implies the following lemma:

Lemma 3.4. The following equivalences hold.

1. There exists an intra-task path reaching a node u for an activation edge(u, act q, v) if and only if there exists an inter-task (i.e. not preempted)path reaching u.

2. There exists an intra-task path reaching a node u with set of held resourcesR if and only if there exists an inter-task path reaching node u with thesame set R.

ut

For the algorithm, two different kinds of priorities are important. Thedefensive priority Pd(x) of a shared variable x is given by the least priorityat which an access to x may be executed and therefore depends only on thesets of held resources at the accesses point to x. In contrast, the offensivepriority Po(q) of a task q, on the other hand, is the maximum of the lowestpriority obtained on a path from an interrupt to the entry node of the taskq. Let Π(q) denote the set of all such paths. For every path π ∈ Π(q), letPmin(π) denote the lowest priority obtained along the path π. The offensivepriority of q then is given by:

max{Pmin(π) | π ∈ Π(q)}

If the task is not reachable from any interrupt, its offensive priority is 0.This yields the following theorem:

Theorem 3.5. A data race over the shared variable x occurs if and only ifthere is a task q with Po(q) > Pd(x) which contains an access to x.

Proof. Let Pd(x) = p and assume there is a task q with Po(q) > p. A datarace path (3.1) can be constructed as follows. Pd(x) = p implies that thereexists an access to x which can be reached with a set of resources R suchthat P(R) = p. On the other hand, the task q has priority P(rq) at its entrynode, hence P(rq) ≥ Po(q) > p. Together this yields the following two paths:

Te −→∗ uaccess(x)−→=p v qe −→∗>p u′

access(x)−→>p v′

3.4 Race Detection in the OSEK Model 31

If q is an interrupt, the above paths may be connected through aninterrupt-edge from the node v. Otherwise, Po(q) > Pd(x) > 0 implies thatthere exists a sequence of tasks starting from an interrupt I = q0, q1, . . . , qn =q where each qi−1 contains an edge ( , act(qi), ) and Po(qi) ≥ Po(q). In partic-ular, this implies Po(I) ≥ Po(q) > p which means that I and the subsequentexecute before returning to the node v. As all activated tasks will be executedwith a priority above p, this yields the path:

v −→ Ie −→∗>p q1e −→∗>p · · · −→∗>p qn−1e −→∗>p qne = qe

This connects the two accesses above, completing the race path definedas (3.1).

For the other direction, the existence of a race path with an access atpriority p implies that a set of held resources R with P(R) = p can reachan access to x and thus that Pd(x) ≤ p. Let the second access of the racepath occur in task q. The existence of a path with priority strictly above pfrom interrupt I to the access in q implies Po(q) > p. Together, this yieldsPo(q) > p ≥ Pd(x) concluding the proof.

ut

With these results in place, an algorithm is now constructed that com-putes the defensive and offensive priorities. The key data structure of thealgorithm is the activation graph G. The nodes of the activation graph aregiven by the set Task of all tasks of the program (including interrupts) whilethe set of edges consists of all pairs (q, q′) if an edge (u, act(q′), v) is intra-taskreachable from qe. Due to lemma 3.4.1 there exists an edge (q, q′) in G if andonly if the task q may activate the task q′. This graph can be constructed intime polynomial in the size of the OSEK program.

The activation graph for the example program in figure 3.1 is as follows:

T T ′ I T

Here, in-edges without a source mark the starting points of activationchains.

For a given shared variable x, the algorithm then determines the setAcc(x) that denotes the sets of resources held when accessing the variablex in a task which is reachable with respect to G from the main task or aninterrupt. This set is determined again by intra-task reachability in timepolynomial in the size of the program and exponential in the number of ac-quirable resources. Due to lemma 3.4.2, the defensive priority of x is given asthe minimal priority of a resource set R ∈ Acc(x).

In order to compute the offensive priorities, let GI be the subgraph ofG consisting of all tasks that are reachable (in G) from an interrupt I. Bythe coincidence theorem [31] for distributive data flow frameworks, the leastupper bound of the minimal priorities of tasks traversed on paths starting at


interrupts and reaching q in the subgraph GI , coincides with the least solutionfor q of the following system of equations:

Po[q] = min (P(rq), max{Po[q′] | (q′, q) edge in GI}) . (3.2)

The least solution of a system over the integers with only the minimumand maximum operators can be determined in linear time. For a detaileddiscussion see, e.g., [51].

Since each activated task waiting in the queue can eventually be executed,the paths in GI correspond to the inter-task execution paths. This implies thatthe least solution of the system of equations is indeed equal to the offensivepriorities for all tasks. Due to the characterization given in theorem 3.5, thisyields the following result:

Theorem 3.6. Assume that the OSEK program p only uses non-deterministicbranching. Then the set of all variables over which there is a data race canbe computed in time polynomial in the size of p and time exponential in thenumber of simultaneously held resources only.

ut

Since the number of simultaneously held resources is small (namely 8OSEK resources plus the artificial resource encoding the static priority) thecomputation of data races in OSEK programs is essentially polynomial.

3.5 Related Work

Ramalingam showed in [46] that the context- and synchronization-sensitiveanalysis of concurrent programs is generally undecidable even for simpleanalyses. Therefore, one either over-approximates the interaction betweenthreads, as in thread-modular model-checking [18] and nested fix-point ab-stract interpretation [52]; or one places restrictions on concurrency, analyzingprecisely up to a fixed number of context switches [4, 45] or analyzing struc-tured parallelism only [15]. Here a precise analysis was obtained by exploitingproperties of a specific framework for interrupt-driven concurrency.

The result that concurrent programs with priority preemptive schedulingcan be reduced to sequential programs has also been reached, simultaneouslyand independently, by Kidd et al. [29]. In addition to programs scheduledwith the priority ceiling protocol discussed here they also consider programsscheduled using the priority inheritance protocol. The difference between pri-ority ceiling and priority inheritance is that, while priority ceiling raises thepriority as soon as a resource is acquired, priority inheritance only raisesit when a higher priority task requests an occupied resource. This resultsin more priority changes, but also more fine grained concurrency. Thereforetasks not using a resource are generally less affected by waiting for taskswith increased priority. On the contrary, high priority tasks in need of a

3.5 Related Work 33

resource are more likely to find it occupied and consequently have to waitmore often. It turns out that priority inheritance is harder to reduce to asequential model. While for a priority ceiling system, as was also shown here,configuration reachability is decidable, it is generally undecidable for priorityinheritance systems. They show that well nested resource acquisition is nec-essary to decide configuration reachability for priority inheritance systems.Their technique does not rely on semantic rules to encode the scheduling.Instead they add an explicit scheduler to the concurrent program, that ap-proximates the concurrent behavior by non-deterministic function calls. Todo this they compute a hyperperiod which denotes the least common multipleof the periods of all tasks. Then they create as many copies of each task asthis task is scheduled during one hyperperiod. The scheduler then takes careto execute each task once. This is done according to the scheduling protocoland in arbitrary order. In order to model the full system such a hyperperiodexecution is put into an infinite loop. This technique relies heavily on thefact that all their tasks are periodic. Interrupts do not exist in their model.However, as long as efficiency is not the main focus, interrupts can be addedsimply by introducing non-deterministic transition rules into the correspond-ing push-down system. The abstraction presented here is complementary inthe sense that periodic tasks are considered as interrupts which can occurarbitrarily often.

Closest to the presented model is the model used by Atig et al. [3].They show that the control point reachability problem is decidable forasynchronous programs with preemption consisting of tasks with priorities.Thanks to the OSEK scheduling policy and the priority ceiling protocol, it ispossible to keep the task pool structured as a queue and reduce the systemto pushdown system, while in the general setting a multi-set is required andthe reduction is to petri-nets with inhibitor arcs. While not mentioned by theauthors, it appears that interrupts can be added to their model without theneed to adjust the reduction.

In a number of papers, Kahlon et al. [26–28] discuss model checking ofpushdown systems communicating via locks and asynchronous rendezvous(wait/notify). Using acquisition histories, they show that in the case of onlynested locks the problem is decidable. While their model does not use prior-ities, this approach might help to improve the analysis of OSEK programssince nested use of locks is a desired, but not enforced, property of OSEKprograms. Lammich and Muller-Olm [34] use a restricted semantics to gen-erate monitor-consistent inter-leavings in order to find conflicting states ina system with dynamic thread creation and re-entrant monitors. Buildingon this idea, priority conditions encoding the OSEK scheduling have beenincluded in the semantics presented in this chapter.

Regehr and Cooprider, [47], present a source-to-source-transformationtechnique to turn interrupt driven embedded code into thread-based code.Applying normal race detection tools to the transformed code yields good


results. They also introduce artificial interrupt locks to make interruptdisabling/enabling visible to the analysis. With minor modifications theyadapted this idea to also work with priority ceiling protocol scheduling.

3.6 Conclusions

By incorporating the scheduling strategies of the OSEK specification into aconstraint-based formalization, a framework has been obtained that allowsthe precise analysis of OSEK programs. Additionally a notion of data racesin the OSEK context has been formalized and an analysis to find them hasbeen proposed.

As the OSEK specification does not restrict the programmer to a safesubset of C, it is effectively necessary to analyze real C programs. This re-quires dealing with arrays, pointer manipulation, indirect function calls, etc.Furthermore, many interesting programs properties may depend on numericinvariants. A practical analyzer of OSEK programs, therefore, must rely onvarious auxiliary analyses which compute may- and must-aliasing informa-tion and track relationships between integer variables. These analyses cannaturally be incorporated into the constraint system of section 3.3. The re-quired analysis results then can be determined by local fix-point solving [17]as applied, e.g., in the static analyzer Goblint [58].

The assumption of starvation freedom for the data race analysis in sec-tion 3.4 is not completely satisfactory. However, finding definite and/or po-tential starvation in OSEK programs is in itself a challenging problem andsolving it requires more information than the activation graph provides.

4 Resource and Priority Analysis of OSEKPrograms

There is an inherent tension in concurrent real-time software like, e.g., OSEK1

[22] programs, between synchronization, needed to preserve data consistency,and prioritized execution, needed to meet hard deadlines. Keeping executiontime of high-priority tasks within a predictable time frame, yet allowing lower-priority tasks to safely complete critical sections requires sophisticated syn-chronization primitives. A key requirement for these synchronization primi-tives is to minimize the worst-case waiting time of high-priority tasks. Usingcommon binary semaphores (mutexes) can result in a higher-priority taskwaiting an indefinite amount of time for a lower-priority task to complete.This situation is known as unbounded priority inversion.

As an example of unbounded priority inversion, consider a low-prioritytask q1 which acquires a lock needed by a high-priority task q3. When q3 isready to execute, it will preempt q1, but as soon as q3 attempts to acquirethe lock, it must wait for q1 to complete its critical section. It is perfectlyacceptable, and necessary for the sake of data consistency, that a high-prioritytask waits for a low-priority task to complete execution of a critical section.The problem is that an intermediate-priority task q2 may preempt the low-priority task before it releases the lock. Then, q2 is indirectly also blocking thehigh-priority task q3. If q2 occurs multiple times during the critical section ofq1 the highest priority task has to wait for an arbitrary amount of time.

Unbounded priority inversion makes it impossible to guarantee hard tim-ing deadlines. Operating systems for embedded systems provide more sophis-ticated synchronization primitives than common mutexes. It is, therefore, im-portant to provide static analysis techniques which uncover potential flawsin programs which rely on such sophisticated synchronization protocols. Onesuch primitive is the priority ceiling protocol implemented in the OSEK [22]operating system. In Safety Critical Java [25], a proposed subset of Real-TimeJava, it is called the immediate ceiling priority protocol. It is also present inthe Pthreads library, where it is called the Priority Protect Protocol.

This chapter provides methods for uncovering subtle flaws due to theconcurrency induced by interrupts. Specifically, the focus will be on concur-rent data races and transactional behavior of procedures. Moreover, a general


36 4 Resource and Priority Analysis of OSEK Programs

I ′e33 I ′1 I ′2 I ′r

Ie22 I1 I2 I3 Ir

Te11 T1 T2 T3 T4 T5 T6 T7 · · ·

· · · T7 T8 T9 T10 T11 Tr

get(r′) z=20 rel(r′)

get(r) y++ x-- rel(r)

get(r′) x=10 y=0 rel(r′) get(r) t=x+y x=t-x

rel(r) z=t*2 get(r) y=t-y rel(r)


method is given how inter-procedural value analyses can be enhanced to takepriorities and interrupts into account. This method is applied here to analgorithm for inferring affine equalities.

The program in figure 4.1 is used as a running example throughout thischapter. It consists of one (main) task T and two interrupts I and I ′ withpriorities 1, 2 and 3, respectively (higher numbers denote higher priorities).The program uses two resources, r and r′. Since r is used by T and I, itsceiling priority is 2, while r′ is used by T and I ′, so its ceiling priority is 3.The interrupt I ′ has the highest priority and resets the variable z to thefixed value 20. The interrupt I increments the counter y and decrements thecounter x. The main task T initializes the counters x and y; then, it attemptsto swap their values by means of an auxiliary variable t, which receives thesum of x and y. Before completing the swap, the result 2 ∗ t is stored inthe variable z. This example is designed to exhibit both a data race andnon-transactional behavior.

The resource r′ is held during the initialization of the main task. Conse-quently, the dynamic priority of this part is 3 (the maximal priority) duringthe initialization part. This ensures that no interrupts can interfere with theinitialization. The acquisition of r′ in I ′ does not increase the dynamic priorityof I ′ since the static priority of I ′ is already maximal. After the initializa-tion part, T acquires the resource r which has ceiling priority 2. This willonly protect against the interrupt I, while I ′ may still occur. Except for theinitialization phase, I ′ can occur at any node while I can only occur at thenodes T4, T8, T9 and Tr. Note that the interrupt I is unaware of the resourcer′, and yet acquiring resource r′, protects a task from being interrupted byI because the static priority of I is less than the ceiling priority of r′. Thiseffect is typical for priority based synchronization. An analysis which treatsresources as locks, though, could not exclude the possibility of I interruptingthe initialization code, resulting in false alarms.

The assignment z = t ∗ 2 in T may overwrite the assignment in I ′ if I ′

occurs at T8 (or earlier). Or it might itself be overwritten if I ′ occurs at T9 (or

4.1 The Core Priority Ceiling Model and its Semantics 37

later). This constitutes a data race. While this might be intentional behaviorin a real program, it is a very error prone technique. Therefore knowing whichvariables can be overwritten in such a fashion is important even if it is notan error. Moreover, at T10, variable y is overwritten with a value that mighthave become outdated due to an occurrence of I. In the example, this willresult in failing to correctly swap the variables x and y. Note that this mightoccur although all accesses to x and y are protected by the resource r. Thisbehavior is called nontransactional. This occurs due to overly eager releasingresources and the mis-perception of having a private copy of global values.

4.1 The Core Priority Ceiling Model and its Semantics

The model used in this chapter consists of one task T , with which programexecution starts; a finite collection of interrupt routines Irpt and auxiliaryprocedures Proc, which may be called anywhere in the program. The maintask T as well as the interrupt routines are distinguished procedures whichmay not be directly called. Since the main task and interrupts are oftentreated equally in this chapter the term task may also refer to interrupts andthe notation Task = Irpt∪{T} is used. For the sake of the analysis, proceduresand tasks are specified by means of control-flow graphs as in figure 4.1.

Every procedure f has a designated entry node fe and return node fr.The collection of all control flow graphs of procedures in Proc is denoted by(N,E) where N is the set of nodes and E the set of edges. Let Ne and Nrdenote the set of all entry and return nodes, respectively.

Conditional branching is approximated by nondeterministic branchingand it is assumed that all executions may eventually terminate, i.e. returnnodes are formally reachable from every node. This is done to enable lateranalyses to accumulate all information at return nodes.

Each edge is labeled either with a basic statement s, or with a callf(), f ∈ Proc. For simplicity, only procedures without parameters are con-sidered. Each basic statement s is either a basic command cmd, such as anassignment to a global variable, or a priority ceiling protocol statement, suchas resource acquisition. Let Res denote the finite set of resources used by theprogram. For r ∈ Res, the priority ceiling protocol statement get(r) acquiresthe resource r and rel(r) releases r. It is assumed that at the exit node ofeach task, all resources have been released. This can be enforced, e.g., bysuccessively releasing all resources potentially used by the task. In the exam-ple of figure 4.1, this is not required, since the program properly releases allacquired resources.

Additionally, functions P : Task → N and U : Task → 2Res are givenwhich map tasks to their static priorities from N and (super-)sets of the setsof resources possibly acquired during their execution. The priority of T isminimal and assumed to be 1. This means that P(T ) = 1 < P(q) for eachq ∈ Irpt. The same notation is used to assign to each resource r ∈ Res,


its ceiling priority P(r). P(r) which equals the maximal priority of a taskacquiring r, i.e.,

P(r) = max{P(q) | r ∈ U(q)}

For a subset of resources R ⊆ Res, the notation P(R) is used as a short-hand for max{P(r) | r ∈ R} where P(∅) = −∞. Both P and U can beconstructed by parsing the OIL-file of the OSEK program analyzed.

Execution Paths An execution path π of a priority ceiling based programis a sequence of control-flow edges labeled by statements s into which subse-quences corresponding to procedure calls or interrupts are nested. The nestingof a call to the procedure f is indicated by means of the start and end tags〈f〉 and 〈/f〉, respectively. Interrupts are indicated analogously.

Same-level execution paths reaching a program point v (on the same level)are defined as follows:

– ε is a same-level execution path reaching the entry nodes qe of procedures;– π(u, s, v) is a same-level execution path reaching v if π is a same-level

execution path reaching u;– π1〈f〉π2〈/f〉 is a same-level execution path reaching v if π1 is a same-level

execution path reaching u, (u, f(), v) is a call edge, and π2 is a same-levelexecution path reaching the return node fr of f ;

– π1〈q〉π2〈/q〉 is a same-level execution path reaching v if π1 is a same-levelexecution path reaching v, and π2 is a same-level execution path reachingthe return node qr of an interrupt q.

Likewise, a (reaching) execution path reaching a program point v (notnecessarily at the same level) is defined as follows:

– ε is an execution path reaching the entry point Te of the main task;– π(u, s, v) is an execution path reaching v if π is an execution path reachingu;

– π1〈f〉π2〈/f〉 is an execution path reaching v if π1 is an execution pathreaching u, (u, f(), v) is a call edge and π2 is an execution path reachingthe return node fr of f ;

– π1〈q〉π2〈/q〉 is an execution path reaching v if π1 is an execution pathreaching v, and π2 is a same-level execution path reaching the return nodeqr of an interrupt q;

– π〈q〉 is an execution path reaching the entry node qe of q if π is an executionpath reaching u and either there is a call edge (u, q(), v) or q is an interrupt.

Let ΠS and ΠR denote the set of same-level execution paths and reachingexecution paths, respectively.

For same-level execution paths, the resource set after the path is definedin terms of the resource set R before the path:


R(ε, R) = RR(π(u, cmd, v), R) = R(π,R)R(π(u, get(r), v), R) = R(π,R) ∪ {r}R(π(u, rel(r), v), R) = R(π,R) \ {r}R(π1〈q〉π2〈/q〉, R) = R(π1, R) if q ∈ TaskR(π1〈f〉π2〈/f〉, R) = R(π2,R(π1, R)) if f 6∈ Task

This definition is extended to (reaching) execution paths:

R(π〈f〉π,R) = R(π,R(π, R)) if f 6∈ TaskR(π〈q〉π,R) = R(π, ∅) if q ∈ Task

Here π is a same-level execution path and π is a reaching execution path.

The Path Semantics The concrete semantics collects, for each programpoint v, the set of execution paths reaching v taking static priorities andresource sets into account. Each task starts with an empty set of resources.It is assumed that procedures cannot be interrupted at their entry points. Ifa task is interrupted (while executing some procedure), its resource set beforeand after the interrupt is identical, while procedure calls may change the setof currently held resources.

Let p denote the maximal static priority of all tasks, and [p] the interval{0, . . . , p}. For a procedure f , let JfK : [p]→ (2Res → 2ΠS ) denote the functionwhich assigns to each static priority i at which f can be called, a functionwhich takes a resource set R before a call to f and returns the set of same-level execution paths of the procedure f including all execution paths ofinterrupts which possibly may have occurred. Likewise for j > 0, let JjK ⊆ ΠS

denote the set of execution paths of all interrupts with static priority j. Foran edge e labeled with a statement s, the concrete semantics is a functionJeK : 2Res → 2ΠS which for each resource set R returns the single pathJeK(R) = {e}.

In order to put up a constraint system to characterize the sets of same-level execution paths of procedures, composition operators are required whichtake resource sets and static priorities into account. The composition of map-pings M1,M2 : 2Res → 2ΠS must ensure that the sets of execution paths areconcatenated according the attained sets of resources:

(M2 ◦M1) R = {π1π2 | π1 ∈M1(R), π2 ∈M2(R(π1, R))}

For interrupts, execution paths which cannot be interrupted, due to highdynamic priorities, need to be filtered out. Let Sj denote the set of executionpaths of interrupts of priority j. Then the application of Sj is defined by amapping M : 2Res → 2ΠS :

(Sj •j M) R = {π1π2 | π1 ∈M(R), π2 ∈ Sj , j > P(R(π1, R))}


Here the priority condition checks that the acquired resources allow theinterrupt to occur. Note that here there are no checks for the static prioritysince these are done directly in the constraint system.

The functions JfK : [p]→ 2Res → 2ΠS , f ∈ Proc, and the sets JjK then canbe characterized as the least solution of the following constraint system:

[S0] S[fe, i] ⊇ I

[S1] S[v, i] ⊇ J(u, s, v)K ◦ S[u, i] (u, s, v) ∈ E[S2] S[v, i] ⊇ (JfK i) ◦ S[u, i] (u, f(), v) ∈ E

JfK i ⊇ Hf (S[fr, i])

[S3] JjK ⊇ (JqK j ∅) q ∈ Irpt,P(q) = j

S[u, i] ⊇ JjK •j S[u, i] u /∈ Ne, j > i

Here, the initial function I is given by I(R) = {ε}. The auxiliary variableS[v, i] for a node v of some procedure f , and a static priority i describes thefunction which, for a given resource set R at procedure start, returns the setof all same-level execution paths reaching v in f when executed within a taskof static priority i. The auxiliary operator Hf takes a description M of thesame-level execution paths of the procedure f and wraps it into the openingand closing tags corresponding to f , i.e,

Hf (M)(R) = {〈f〉π〈/f〉 | π ∈M(R)}

For real-time systems, it is reasonable to assume that every procedure hasat least one same-level execution path, i.e., that JfK i R is non-empty for everyi and R. If this is the case, the set of all program points which are definitelyunreachable can be computed by standard means and then be removed fromthe control-flow graphs, which implies that property (S) is satisfied:

(S) Each program point v of a procedure f is same-level reachable, i.e.,S[v, i](R) 6= ∅ for every i and R.

This property, therefore, will henceforth be generally assumed.In order to put up a constraint system to characterize the sets of reaching

execution paths, an operator is required that applies the effects M : 2Res →2ΠS of edges or procedures to sets of reaching execution paths S, which takesattained sets of resources into account. This operator is defined as follows:

M@S = {π1π2 | π1 ∈ S, π2 ∈M(R(π1, ∅))}

Likewise, the application of a set of same-level execution paths S2 ofinterrupts of priority j to a set S1 of reaching execution paths is defined by:

S2 @j S1 = {π1π2 | π1 ∈ S1, π2 ∈ S2,P(R(π1, ∅)) < j}

The collecting semantics of sets of reaching execution paths then is givenby the least solution of the following constraint system:


[R0] R[Te, 0] ⊇ {ε}[R1] R[v, i] ⊇ J(u, s, v)K@R[u, i] (u, s, v) ∈ E[R2] R[v, i] ⊇ (JfK i)@R[u, i] (u, f(), v) ∈ E

R[fe, i] ⊇ enterf (R[u, i]) (u, f(), v) ∈ E[R3] R[u, i] ⊇ JjK@jR[u, i] u /∈ Ne, j > i

R[j] ⊇ projj(R[u, i]) u /∈ Ne, j > i

R[qe,P(q)] ⊇ enterq(R[j]) q ∈ Irpt, P(q) = j

For a procedure f 6∈ Task the operator enterf applied to a set S of reachingexecution paths appends the opening tag 〈f〉 to each reaching execution pathin S, i.e.,

enterf (S) = {π〈f〉 | π ∈ S}

The operator projj when applied to a set S, extracts the set of all reachingexecution paths π from S where the priority of the resource set R(π, ∅) isless than j, i.e,

projj(S) = {π | π ∈ S,P(R(π, ∅)) < j}

The constraints S0, R0 provide values for entry points of all proceduresin Proc, and the entry node of procedure T , respectively. S1 and R1 takecare of all non-call edges, by applying the semantics of the edge, i.e., ap-pending the edge to the collected sets of paths. Procedure calls are handledby the constraints S2 and R2. In S2 as well as the first part of R2, thesame-level executions of the called procedure are composed with the execu-tions before the call. Additionally, the second part of R2 describes executionpaths entering procedures. The constraints S3 and R3 deal with interrupts.They correspond to implicitly introducing extra loop edges with interruptcalls at every node where an interrupt may occur, given that the dynamicpriority of the executing task is sufficiently low. Interrupts are summarizedby static priority levels. Similarly, the entry sets of the reaching executionpaths are summarized into one set for each static priority level. According tothe assumption, entry nodes are excluded from constraints S3 and R3. Notethat the least solution is required to obtain a solution which is true to thescheduling paradigm.

The collecting path semantics describes all formally possible executionpaths of the program. Any concrete execution of the program which maydepend on input data realizes one of the formal execution paths, while someformal execution paths may not be realizable by any concrete execution sinceconditions are not taken into account.

If every program point is same-level reachable from its correspondingentry node the sets S[v, i](R) will all be non-empty. This excludes procedureswhich may never terminate. For the rest of this chapter this property isassumed to hold.


4.2 Data Races and Nontransactional Behavior

Let Acc(cmd) and Acc(f) denote the set of all variables accessed by the basiccommand cmd and same-level executions of procedure f , respectively. Forclarity of presentation, read and write accesses are treated as one.

Then a data race at some global variable x occurs if program executionreaches an access to x at a dynamic priority j while x also might be accessedby some interrupt q of static priority exceeding j.

Definition 4.1. A priority ceiling based program contains a data race at vari-able x if there exists a reaching execution path

π (u, cmd, v) 〈q〉 π〈/q〉 ∈ R[v, i]

for a basic command cmd with x ∈ Acc(cmd) and a same-level execution pathπ of the interrupt q with x ∈ Acc(q).

In the example program of figure 4.1, a data race occurs at the variablez. The interrupt I ′ has static priority 3 and accesses z while the main task Taccesses z at a dynamic priority of 1 and can therefore be preempted by I ′

at T8 or T9. A possible run of the example program reaching the data racewould be:

(Te, get(r′), T1) . . .(T3, rel(r′), T4) . . . (T8, z = t ∗ 2, T9)

〈I ′〉(I ′e, get(r′), I ′1) (I ′1, z = 20, I ′2) (I ′2, rel(r′), I ′r)〈/I ′〉

There are no further data races in the example program since the variablesx and y are only used by the interrupt I which has a static priority of 2 andall accesses to these variables occur at a dynamic priority of at least 2.

A procedure f is transactional (or atomic) if during every execution of f ,no interrupt may occur between the first and last access to a global variablealso accessed by f .

Definition 4.2. Formally, f is nontransactional at static priority j for aresource set R, if there exists a same-level execution path

〈f〉 π1 〈q〉 π 〈/q〉 π2〈/f〉 ∈ JfK(j)(R)

where the following holds:

– π1π2 ∈ S[fr, j](R) is a same-level execution path which contains no inter-rupts;

– π is a same-level execution path of the interrupt q without further inter-rupts;

– π1 and π2 contain edges (u1, cmd1, v1),(u2, cmd2, v2) with Acc(cmd1) 6= ∅ 6=Acc(cmd2); and

– π contains an edge (u, cmd, v) with Acc(cmd) ∩Acc(f) 6= ∅.

4.3 Analyzing Resources 43

To exemplify this situation consider again the program of figure 4.1. Thefirst access of the main task T to a global occurs before program point T2 whilethe last access is after T10. In between, e.g., at program point T8, the dynamicpriority is 1. At this node, T can be preempted by the interrupt I whichchanges the variables x and y also used by T . Therefore T is not transactional.A possible run of the example program exhibiting this behavior would be:〈T 〉 (Te, get(r′), T1) . . . (T7, rel(r), T8) 〈I〉 (Ie, get(r), I1) . . . (I3, rel(r), Ir) 〈/I〉(T8, z = t ∗ 2, T9) . . . (T11, rel(r), Tr) 〈/T 〉.

4.3 Analyzing Resources

In this section, an analysis of sets of resources possibly held at a given programpoint is presented. The results of this analysis are fundamental for determin-ing the minimal dynamic priority guaranteed to hold at this program point,as well as all subsequent analyses of the program.

The analysis determines for each program point a set of possible resourcesets. The complete lattice thus is given by D. Sets of sets are ordered bysubset inclusion. Therefore at join points the union of reaching sets is taken.

For analyzing same-level executions, each procedure f is associated withan abstract semantics JfK] : 2Res → D. Unlike the collecting semantics, JfK]

does not depend on the static priority in which a call to f is made. The staticpriority determines the interrupts which may occur during the call of f , butinterrupts do not modify the sets of currently held resources. In order to setup the corresponding abstract constraint system, an abstract semantics from2Res → D is defined for edges (u, s, v) labeled with basic statements:

J(u, cmd, v)K](R) = {R}J(u, get(r), v)K](R) = {R ∪ {r}}J(u, rel(r), v)K](R) = {R \ {r}}

Additionally, an abstract composition operator ◦] is required which, forabstract mappings M1,M2 : 2Res → D, returns the function defined by thefollowing equation:

(M2 ◦]M1)(R) =⋃{M2(R′) | R′ ∈M1(R)}

As with the concrete semantics the effect of procedures is computed de-pending on resource sets with which they are called. The functions JfK] :2Res → D, f ∈ Proc, then are given by the least solution of the followingconstraint system:

[S]0] S[fe]] w I] f ∈ Proc

[S]1] S[v]] w J(u, s, v)K] ◦] S[u]] (u, s, v) ∈ E[S]2] S[v]] w JfK] ◦] S[u]] (u, f(), v) ∈ E[S]3] JfK] w S[fr]

]


Here the function I] is given by I](R) = {R}. No constraints have beenincluded to deal with interrupts since interrupts do not change the resourcesheld.

For determining the sets of reaching resource sets, an abstract applicationoperator @] is required, which applies a mapping M : 2Res → D to a set ofresource sets S ∈ D as follows:

M@]S =⋃{M(R) | R ∈ S}

For approximating the sets of resource sets reaching a node v at staticpriority level i, consider the following constraint system:

[R]0] R[qe, j]] ⊇ {∅} q∈Task, j=P(q)

[R]1] R[v, j]] ⊇ J(u, s, v)K]@]R[u, j]] (u, s, v) ∈ E[R]2] R[v, j]] ⊇ JfK]@]R[u, j]] (u, f(), v) ∈ E

R[fe, i]] ⊇ R[u, i]] (u, f(), v) ∈ E

Note that the constraint R]0 not only provides an abstract start value forthe entry node of T , but also for the entry nodes of all interrupts q ∈ Irpt.This is because every interrupt may occur, for example at the exit node ofT , and will always start with the empty resource set. Note further that forreachability, the information i about the static priority at which a node isreached is preserved since it is required to determine the possible dynamicpriorities at the node.

In order to relate the concrete and abstract semantics of programs, ab-straction functions are defined as follows: α : (2Res → 2ΠS ) → (2Res → D)and α : 2ΠR → D. These are given by:

α(M)(R) = {R(π,R) | π ∈M(R)}α(X) = {R(π, ∅) | π ∈ X}

The following theorem not only shows that the least solution of the con-straint systems are safe over-approximation of the sets of resource sets at-tained by reaching executions, but also a precise one, with respect to thepresented model.

Theorem 4.3. 1. Let JfK j,S[v, j] and JfK],S[v]] denote the least solutionsof the constraint systems S and S], respectively. Then for every proceduref , static priority i, and program point v,

α(JfK j) = JfK] and α(S[v, j]) = S[v]]

2. Let R[v, j] and R[v, j]] denote the least solutions of the constraint systemsR and R], respectively. Then for every program point v and possible staticpriority j,

α(R[v, j]) = R[v, j]]

4.3 Analyzing Resources 45

Proof. For the proof, note that for every edge e = (u, s, v), the followingholds:

α(JeK) = JeK]

Also for composition of functions M1,M2 : 2Res → 2ΠS , the followingholds:

α(M2 ◦M1) = α(M2) ◦] α(M1)

Since, furthermore, the abstract functions JeK], as well as the operation ◦]are completely distributive, i.e., commute with arbitrary least upper bounds,the first assertion of the theorem follows by fixpoint induction. An analogousargument applies to the second statement of the theorem.

ut

Let n denote the sum of the number of program points and control flowedges, and o the number of resources used by the program. Recall that p isthe number of static priority levels. Then the number of constraints in thesystems S] and R] are bounded by O(p · n). Since the height of the lattice2Res → D is exponential in the number of resources, the least solution ofthese systems can be computed by a standard work-list algorithm in timeO(p · n · 2co) for some constant c.

Typically, the number of resources used by embedded controllers are quitesmall. A practical implementation still may tabulate functions JfK] only forthose (i, R) of static task priorities i and resource sets R for which the pro-cedure f may be called at runtime. Also, elements in D can be naturallymodeled by Boolean functions, which in turn can be efficiently operated on,if these are represented through ordered binary decision diagrams.

The example program in figure 4.1 does not use any procedures, whichmeans only the constraint R]0 and R]1 are important. Furthermore, eachnode is only reached with the static priority of its task. Therefore the followingresults are obtained directly:

Node [I ′e, 3] [I ′1, 3] [I ′2, 3] [I ′r, 3]Result {∅} {{r′}} {{r′}} {∅}

Node [Ie, 2] [I1, 2] [I2, 2] [I3, 2] [Ir, 2]Result {∅} {{r}} {{r}} {{r}} {∅}

Node [Te, 1] [T1, 1] [T2, 1] [T3, 1] [T4, 1] [T5, 1] [T6, 1]Result {∅} {{r′}} {{r′}} {{r′}} {∅} {{r}} {{r}}Node [T7, 1] [T8, 1] [T9, 1] [T10, 1] [T11, 1] [Tr, 1]Result {{r}} {∅} {∅} {{r}} {{r}} {∅}

Flow-independent Must-resource Analysis One interesting class of pri-ority ceiling based programs consists of all programs where the set of heldresources at a program point v only depends on the set of resources heldat the entry point of a procedure f but not on the concrete execution path


reaching v. More precisely, for every procedure f and set of resources R it isrequired, that the set S[v, j]](R) is a singleton set {R′}. These programs aresaid to have flow-independent resource sets. Such programs can be analyzedmore efficiently, while still being precise with respect to the presented model.

The analysis presented above can be further abstracted to compute notall possible resource sets, but the set of definitely held resource. The domainis then simplified to 2Res ordered by superset inclusion (⊇) and intersectionas the least upper bound. Since every program point is reachable by somesame-level execution path, no dedicated bottom element is required to de-note unreachability. Consider the abstraction functions αm : (2Res → D) →(2Res → 2Res) and αm : D→ 2Res given by:

αm(M)(R) =⋂M(R) and αm(S) =

⋂S

Here⋂∅ is defined as Res. The resulting analysis is called must resource

analysis. The abstract functions JeK]m : 2Res → 2Res for edges e = (u, s, v)corresponding to this analysis are given by:

J(u, cmd, v)K]m(R) = R

J(u, get(r), v)K]m(R) = R ∪ {r}J(u, rel(r), v)K]m(R) = R \ {r}

Note that these transformers now are functions of the general formatg(R) = R \ K ∪ G for suitable constant sets K and G. Let F denote theset of all these functions. This lattice is well known for gen-kill bit-vectoranalyses as discussed in, e.g., [24]. Also, since the abstract composition offunctions as used by the constraint system S], becomes ordinary compositionof functions for must resource analysis, must resource analysis for priorityceiling based programs can be performed by means of an interprocedural gen-kill approach. Similarly the abstract function application, becomes ordinaryfunction application. Let S]m denote the constraint system over the completelattice F corresponding to S].

Theorem 4.4. Assume that JfK],S[v]] and JfK]m,S[v]]m are the least solu-tions of the constraint systems S] and S]m, respectively, where S[v]](R) 6= ∅for all program points v, and resource sets R. Then for every procedure f ,and program point v,

αm(JfK]) = JfK]m and αm(S[v]]) = S[v]]mut

The proof is analogous to the proof of theorem 4.3. The non-emptinessassumptions are required as the functions from F only commute with non-empty least upper bounds since

⋂∅ = Res.

In the analysis results of the example program of figure 4.1, every setof resource sets has only one element. This is the case because the example

4.4 Analyzing Data Races 47

program is flow-independent. Applying αm in this case just removes the extrapair of set brackets. For, e.g., the interrupt I ′ the following result is obtained:

Node [I ′e, 3] [I ′1, 3] [I ′2, 3] [I ′r, 3]Result ∅ {r′} {r′} ∅

For programs with flow-independent resource sets satisfying assumption(S), the following corollary holds:

Corollary 4.5. Assume that all resource sets are flow-independent. Assumethat JfK,S[v, i] and JfK]m,S[v]]m are the least solutions of the constraint sys-tems S and S]m, respectively. Then for every program point v, possible staticpriority i and resource set R,

α(JfK i)(R) = {JfK]m(R)} α(S[v, i])(R) = {S[v]]m(R)}ut

The least solution to the system S]m can be computed in O(n ·o) if opera-tions on resource sets, which can be represented as bit vectors, are counted forO(1). In case a program with flow-independent resource sets consists solelyof tasks, each program node needs to be analyzed for only a single context,namely the static priority of its task and the empty resource set. However, anode inside a procedure can be reached not only with different static prioritiesbut also with several distinct resource sets. In order to deal with this situ-ation, the summary functions JfK]m (which can be computed in polynomialtime) are combined with the constraint system R]. This is possible since, by

Corollary 4.5, the functions JfK] can be recovered from the functions JfK]mby:

JfK](R) = {JfK]m(R)}

4.4 Analyzing Data Races

In this section, the results from the last section are applied to the detection ofdata races in programs using priority ceiling synchronization. One can thinkof a task using its dynamic priority to defend against interfering interrupts.Interrupts use their static priority to attack other tasks. Note that it is thestatic priority of an interrupt q which decides whether q may interfere withthe computation of another task executing at a given dynamic priority level.The dynamic priority level protecting an access is referred to as defensivepriority and the static priority level of an access as its offensive priority.

Definition 4.6. Assume that R[v, i]] denotes the least solution to the con-straint system R]. The following functions are defined:

Po(x) =∨{P(q) | x ∈ Acc(q), q ∈ Irpt}

Pd(x) =∧{P(R) ∨ i | (u, cmd, v) ∈ E, x ∈ Acc(cmd), R ∈ R[v, i]] 6= ∅}

Where ∧ and ∨ denote minimum and maximum, respectively.


These functions map global variables to their offensive and defensive pri-orities, respectively. This yields:

Theorem 4.7. If the program satisfies assumption (S), a data race occurs atx if and only if Po(x) > Pd(x).

Proof. First assume that an execution path π(u, s, v)〈q〉π〈/q〉 ∈ R[v, i] isgiven for some static priority i where π is an execution path reaching programpoint u, π is a same-level execution path of the interrupt q, (u, s, v) accessesthe global x and π also contains an access to x. Let R = R(π, ∅) denotethe resource set held when reaching v along π(u, s, v), and j = i ∨ P(R)denote the corresponding dynamic priority. Since the interrupt q may occurafter the execution of π, it follows that j < P(q). By theorem 4.3, R ∈R[v, i]]. Therefore, Pd(x) ≤ j < P(q) ≤ Po(x). Conversely assume thatPo(x) > Pd(x). This means that there is an interrupt q of priority Po(x)which has a same-level execution path π containing an access to the global x.Furthermore, there is an edge (u, cmd, v) accessing x together with a staticpriority i and resource set R ∈ R[v, i]] such that P(R) ∨ i = Pd(x) < P(q).Since R[u, i]] gathers all resource sets possibly reaching u and cmd may notchange resource sets, R is also contained in R[u, i]]. Therefore by theorem 4.3,there exists an execution path π reaching u at static priority i with R(π, ∅) =R. It follows that π(u, cmd, v)〈q〉π〈/q〉 is a reaching execution path fromR[v, i], resulting in a data race at x.

ut

If the program has flow-independent resource sets, and all accesses arereachable, an equivalent result can be achieved using the cheaper must-resource analysis R]m. In a general setting this would still yield a safe over-approximation of data races. For the example program in figure 4.1, Po(x)and Pd(x) are as follows:

Po(x) = 2 Po(y) = 2 Po(z) = 3

Pd(x) = 2 Pd(y) = 2 Pd(z) = 1

This means that x and y are safe, but there is a data race at z. Which isdue to I ′ being possible at T9. More generally it can be said that an access tox or y is safe at a defensive priority of 2 and higher, while z requires priority3 or more.

4.5 Analyzing Transactionality

Nontransactional behavior occurs when a fragment of a program which ismeant to be executed atomically is interrupted by a task which accesses datamanipulated by this fragment. A write access of the interrupting task mayresult in inconsistent data for the program fragment, while a read access may

4.5 Analyzing Transactionality 49

supply the interrupt with inconsistent data. In the example in figure 4.1 themain task switches the value of x and y and whenever accessing either one,it holds the resource r guaranteeing exclusive access. However, it releases theresource between the two operations, which allows the interrupt I to modifyx and y. However the old value of x is still stored in the local variable twhich is used later to overwrite y. This is an instance of the nontransactionalbehavior described by Definition 4.2.

These problems are avoided if the defensive priority is sufficiently largenot only for a single access, but for the whole program fragment in question.There are several subtle points to be taken into account. One point is that aprocedure may have leading and trailing parts which do not access globals.These parts should not influence the defensive priority of the procedure.Another point is that there can be calls to other procedures which mightrelease a held resource and then, perhaps, acquire it again. This influences thedefensive priority of the caller, no matter where in the callee the temporarydecrease in priority occurs.

4.5.1 Tasks Without Procedures

First consider programs with tasks, but no procedure calls. Thus, transac-tional behavior may refer to tasks only. Assume that q is such a task withstatic priority j. Assume further that for every program point v of q, a setS[v]]m(∅) ⊆ Res of (definitely) held resources when reaching program point vis given. In particular, S[qe]

]m(∅) = ∅. These sets allow to compute a (lower

bound to) the dynamic priority of q when reaching program point v. Thisvalue is given by:

P[v] = P(q) ∨ P(S[v]]m(∅))

Let the lattice [p]∗ denote the set {0, . . . , p} ∪ {∞} together with thereverse natural ordering ≥ and minimum as least upper bound. For conve-nience, the componentwise ordering on pairs from [p]2∗ is denoted by ≥ aswell.

For each program point v, values S[v]]t ∈ [p]2∗ are determined where the

first component of S[v]]t is the minimal dynamic priority attained on executionpaths reaching v between the first and the last access to a global. It equals∞ if and only if no global has been accessed so far. The second component isthe minimal dynamic priority attained after the first access. The pairs S[v]]tare characterized as the least solution (least with respect to the ordering ≥)of the following constraint system:


S[qe]]t ≤ (∞,∞)

S[v]]t ≤ let (a1, a2) = S[u]]tin let a = P[v] ∧ a2in (a2, a)

for a control-flow edge (u, s, v) with Acc(s) 6= ∅S[v]]t ≤ let (a1, a2) = S[u]]t

in let a = if a2 <∞ then P[v] ∧ a2else∞

in (a1, a)for a control-flow edge (u, s, v) with Acc(s) = ∅

Let Pd(q) be the first component of S[qr]]t. Then the task q is transac-

tional, if and only if Pd(q) ≥ Po(x) holds for all globals x accessed by q. WherePo(x) is the offensive priority of the global x as defined in Definition 4.6. Incase the program has flow-independent resource sets, also the reverse impli-cation holds. The proofs for these statements follow from the correspondingproperties of the more general inter-procedural setting presented in the nextsubsection. For illustration consider the introductory example.

Applying the analysis to the example program from figure 4.1, yields thefollowing results:

Node T2 T5 T8 Tr Ir I ′rPriorities (3, 3) (1, 1) (1, 1) (1, 1) (2, 2) (3, 3)

In each task, the return point is reachable from every program point ofthe task. Therefore, the defensive priorities are given by:

Pd(T ) = 1 Pd(I) = 2 Pd(I ′) = 3

It follows that I ′ and I are transactional, since the sets of variables ac-cessed by I and I ′ are disjoint, but T is not, since the offensive priority, e.g.,of z exceeds 1. Note that if z is removed from the program, the analysis stilldetects that the task T does not swap x and y transactionally.

4.5.2 Tasks With Procedures

In presence of procedure calls, the dynamic priority when reaching a programpoint v of some procedure f , may depend on the static priority j of the taskwhich executes f as well as the set R of resources held when f has beencalled. Let S[v]]m(R) denote the set of resources which are (definitely) heldwhen reaching program point v. Then (a lower bound to) the dynamic priorityof v is given by j ∨ P(S[v]]m(R)).

Moreover, two values per program point no longer suffice for analyzingtransactionality, since procedure parts before the first or after the last accessto a global can not be excluded when a procedure is called. Therefore, four


f() x y

a4

a3

a2

a1

Fig. 4.2. Priority ranges.

values a1, a2, a3, a4 are computed. The first two components correspond tothe two components which have been used in absence of procedures. Thus,the priority a1 is the lowest priority attained between the first and the lastaccess to some global variable, and a2 is the lowest priority attained after thefirst access to a global. As before, a1 receives the value of a2 at every accessto a global. At the return node of a procedure, the value of a1 denotes theprocedure’s defensive priority.

Additionally, the lowest priority obtained before the last access to a globalvariable is computed in component a3. For that, the component a4 tracksthe lowest priority encountered altogether. The component a3 then receivesthe value of component a4 at every access to a global. This is illustrated infigure 4.2.

Let D denote the set of all quadruples (a1, a2, a3, a4) ∈ [p]4∗ wherea1 ≥ a2 ∨ a3 and a4 ≤ a2 ∧ a3. Let the ordering on D again be the com-ponentwise extension of the reverse natural ordering ≥ on quadruples. Theminimal element with respect to this ordering thus is given by (∞,∞,∞,∞)which signifies the empty set of same-level execution paths. The abstracteffect J(u, s, v)K]t : [p]× 2R → D of a control-flow edge (u, s, v) is defined by:

J(u, s, v)K]t(j, R) =

(∞, j ∨ P(R), j ∨ P(R), j ∨ P(R)) Acc(s) 6= ∅(∞,∞,∞, j ∨ P(R\{r})) s ≡ rel(r))

(∞,∞,∞, j ∨ P(R)) otherwise

The tuple J(u, s, v)K]t(j, R) collects the defensive priorities of the executionof s with resource set R at static priority j.

The following constraint system characterizes the defensive priorities fortriples (u, j, R) of nodes u, static priority level j and resource sets R. Theresource set R denotes the set of resources held, when the current proce-dure has been called. Similarly for non-task procedures, j denotes the staticpriority of the calling task.


[S]t0] S[qe, j, ∅]]t ≤ (∞,∞,∞, j) q ∈ Task, j = P(q)

S[fe, j, R]]t ≤ (∞,∞,∞, j ∨ P(R)) f /∈ Task, j ∈ [p]

[S]t1] S[v, j, R]]t ≤ (J(u, s, v)K]t (j,S[u]]m(R))) ◦]t S[u, j, R]]t (u, s, v) ∈ E[S]t2] S[v, j, R]]t ≤ (JfK]t(j,S[u]]m(R))) ◦]t S[u, j, R]]t (u, f(), v) ∈ E[S]t3] JfK]t j R ≤ S[fr, j, R]]t

where the abstract composition ◦]t : D × D → D of two quadruples isdefined by:

(b1, b2, b3, b4) ◦]t (a1, a2, a3, a4) =

(∞,∞,∞,∞) a4 ∨ b4 =∞(a1, a2, a3, a4 ∧ b4) a2 =∞ = b2

(b1, b2, a4 ∧ b3, a4 ∧ b4) a2 =∞ 6= b2

(a1, a2 ∧ b4, a3, a4 ∧ b4) a2 6=∞ = b2

(a2 ∧ b3, a2 ∧ b4, a4 ∧ b3, a4 ∧ b4) a2 6=∞ 6= b2

Note that a quadruple represents an execution path containing an accessto some global if and only if the second component is less than ∞. Let(c1, c2, c3, c4) = (b1, b2, b3, b4) ◦]t (a1, a2, a3, a4). The abstract composition isthen defined by case distinction on whether the represented execution pathscontain accesses to globals or not. Assume for example the fourth case, i.e.,that a2 6=∞ and b2 =∞. Thus, the right quadruple represents an executionpath π containing an access, while the left quadruple represents executionpaths π′ which do not access globals. In this case, c1 = a1 because first andlast accesses in π π′ both are contained in π. Furthermore, c2 = a2 ∧ b4 asthe dynamic priorities encountered during the entire path π′ occur after thefirst access to a global. The third component is c3 = a3, since the last accessto a global occurs in π. Finally, the fourth component is c4 = a4 ∧ b4 sincethis component provides the minimal dynamic priority encountered duringthe whole path π π′. The other cases are analogous with the exception of thefirst case, which takes care of bottom values. This yields:

Proposition 1. The abstract composition ◦]t : D × D → D is distributive ineach argument, i.e., for all a, b, c ∈ D,

c ◦]t (a ∧ b) = (c ◦]t a) ∧ (c ◦]t b)(a ∧ b) ◦]t c = (a ◦]t c) ∧ (b ◦]t c)

Proof. Let a = (a1, a2, a3, a4), b = (b1, b2, b3, b4) and c = (c1, c2, c3, c4). Con-sider the first assertion of the proposition. If a2 = b2, then the same caseof the composition applies to c ◦]t (a ∧ b) as well as to c ◦]t a and c ◦]t b,and the assertion follows by idempotency, commutativity and associativityof the minimum ∧. Accordingly, assume that w.l.o.g. a2 =∞ and b2 6=∞. Ifc2 =∞, it follows:


c ◦]t (a ∧ b) = (a1 ∧ b1, a2 ∧ b2 ∧ c2, a3 ∧ b3, a4 ∧ b4 ∧ c4)

c ◦]t a = ( a1 , a2 , a3 , a4 ∧ c4 )

c ◦]t b = ( b1 , b2 ∧ c2 , b3 , b4 ∧ c4 )

By inspection of each component, the assertion can be verified. If, on theother hand, c2 6=∞, it yields:

c ◦]t (a∧b) = (a2∧b2∧c3, a2∧b2∧c4, a4∧b4∧c3, a4∧b4∧c4)

c ◦]t a = ( c1 , c2 , a4 ∧ c3 , a4 ∧ c4 )

c ◦]t b = ( b2 ∧ c3 , b2 ∧ c4 , b4 ∧ c3 , b4 ∧ c4 )

In order to prove the assertion, it only must be proven for the first twocolumns that a2 ∧ b2 ∧ c3 = c1 ∧ b2 ∧ c3 and a2 ∧ b2 ∧ c4 = c2 ∧ b2 ∧ c4.Recall that a2 =∞ and by assumption on the quadruples in D, c1 ≥ c3 andc2 ≥ c4. The necessary the nfollow directly. This completes the proof of thefirst assertion. The proof of the second assertion is analogous.

ut

Assume that S[v, j, R]]t and JfK]t j R is the least solution of the constraint

system S]t . Assume further that Po(x) is the offensive priority of the globalx as defined in Definition 4.6. Then the following holds:

Theorem 4.8. Assume that assumption (S) is satisfied, i.e., all programpoints are reachable by some same-level execution path. For a procedure fof a program with control-flow independent resource sets, a static priority jand a resource set R, let (a1, a2, a3, a4) = JfK]t(j, R). Then the procedure fcalled with resource set R at static priority level j is nontransactional, if andonly if there exists a global variable x ∈ Acc(f) with Po(x) > a1.

Proof. For a given static priority level j and an initial resource set R, assignto each same-level execution path π not containing interrupts, a priority tuple(b1, b2, b3, b4) = αt(π, j, R) ∈ D. The entry b1 denotes the minimal dynamicpriority between the first and the last access to a global in π. The entry b2denotes the minimal dynamic priority after the first access to the end of π.The entry b3 denotes the minimal dynamic priority from the beginning of πto the last access to a global and the entry b4 denotes the minimal dynamicpriority through π. By the definition of J(u, s, v)K]t and ◦]t, the tuple αt(π, j, R)is inductively defined by:

αt(ε, j, R) = (∞,∞,∞, j ∨ P(R))

αt(π1(u, s, v), j, R) = J(u, s, v)K]t(j,R(π1, R)) ◦]t αt(π1, j, R)

αt(π1〈f〉π2〈/f〉, j, R) = αt(π2, j,R(π1, R)) ◦]t αt(π1, j, R)

Extend the mapping αt to sets S ⊆ ΠS of same-level execution paths by:

αt(S, j, R) =∧{αt(π, j, R) | π ∈ S}


Note that according to this definition, αt(S, j, R) = (∞,∞,∞,∞) if andonly if S = ∅. Let S[v, j]′(R) denote the set of same-level execution paths atstatic priority j and initial resource set R reaching v which do not containinterrupts. These sets can be characterized by a constraint system S′ whichis obtained from constraint system S characterizing all same-level executionpaths by removing the constraints S3. By definition, the operator ◦]t preserves

the least element. Since by Proposition 1, ◦]t is also distributive in each argu-

ment, it follows that αt(S[v, j]′(R), j, R) = S[v, j, R]]t for all program pointsv.

Now assume that the procedure f is nontransactional at static prioritylevel j and initial resource set R, i.e., there is an execution path of the fol-lowing form:

〈f〉 π1 〈q〉 π 〈/q〉 π2〈/f〉 ∈ JfK(j)(R)

Where π1π2 ∈ S[fr, j](R) is a same-level execution path containing nointerrupts; π is a same-level execution path of the interrupt q; both π1 andπ2 contain an edge accessing a global; and π contains an edge which ac-cesses a global variable x ∈ Acc(f). Thus in particular, Po(x) ≥ P(q). Letαt(π1π2, j, R) = (b1, b2, b3, b4). Since the interrupt q may occur between thetwo global accesses in π1 and π2, it follows that P(q) > b1. From the definitionof αt it is obtained that:

(b1, b2, b3, b4) ≥ (a1, a2, a3, a4) = JfK]t(j, R)

Therefore,Po(x) ≥ P(q) > b1 ≥ a1

Conversely, assume that JfK]t(j, R) = (a1, a2, a3, a4) and there is a globalx ∈ Acc(f) such that Po(x) > a1. This means that a1 < ∞, and that thereis an interrupt q with P(q) = Po(x) > 0 = P(T ) which has a same-levelexecution path π which accesses x. Since a4 ≤ a1 <∞ the following holds:

S[fr, j, R]]t = αt(S[fr, j]′(R), j, R) =

∧{αt(π′, j, R) | π′ ∈ S[fr, j]

′(R)}

Therefore, an interrupt-free same-level execution path π′ ∈ S[fr, j]′(R)

exists such that a1 equals the first component of αt(π′, j, R). Since a1 <∞,

there exist at least two accesses to globals in π′. Moreover, π′ can be factoredinto π′ = π1π2 where π1 and π2 both contain at least one access to a globaland the dynamic priority after π1 equals a1. Since P(q) > a1 interrupt q mayoccur between π1 and π2. Thus by Definition 4.2, f is not transactional whencalled at static priority j with resource set R.

ut

For programs with flow-dependent resource acquisition, this analysis stillyields a safe over-approximation, i.e., transactional procedures may be con-sidered as possibly nontransactional, but not the other way round. Alter-natively, the flow-precise resource analysis S] could be used to obtain moreprecise results.

4.6 Linear Equalities For Priority Ceiling Programs 55

I ′e33 I ′1 I ′2 I ′r

Ie22 I1 I2 I3 Ir

Te11 T1 T2 T3 T4 Tr

fe f1 f2 f3 f4 f5 fr

ge g1 g2 gr


get(r) y++ x-- rel(r)

get(r′) x=10 y=0 rel(r′) f()

get(r) t=x+y x=t-x g() y=t-y rel(r)

rel(r) z=t*2 get(r)

Fig. 4.3. Example program with procedures.

Consider the example program of figure 4.3 where the part of T after theinitialization has been wrapped into the procedure f and the nodes T9 to T10of the original example program have been wrapped into the procedure g.The procedure g is transactional since it only contains one access to a globalvariable. The procedure f holds the resource r at all nodes between its firstand last access to a global variable. However the call to g compromises thetransactionality of f since it temporarily releases r. The analysis presentedabove captures this behavior. For the procedure g called at static priority1 with resource set {r} the following summary is obtained: JgK]t(j, {r}) =

(∞, 1, 1, 1). When applied to the tuple reaching f3 this yields: (∞, 1, 1, 1) ◦]t(2, 2, 1, 1) = (1, 1, 1, 1). Since tuple entries may not increase, this tuple is thencarried over to fr and with Pd(x) = 2 implying that f is not transactional.

4.6 Linear Equalities For Priority Ceiling Programs

The resource analysis presented in section 4.3 did not explicitly deal withinterrupts. The reason for this is that interrupts neither change sets of heldresources nor affect the current priorities of tasks. Values of globals on theother hand, can be affected by interrupts. Fortunately, summary-based inter-procedural analyses as presented by Sharir and Pnueli [55] can be adaptedto resource aware value analyses of priority ceiling protocol based programsrather easily. As a prototypic example the approach presented by Muller-Olm and Seidl [38] for the analysis of linear equalities is extended to takeresources and interrupts into account. The goal of this analysis is to computethe linear closure of extended states of the collecting semantics. For simplicity,only programs with flow-independent resource sets are considered.

Let X = {x1, . . . , xk} denote the set of global variables, where k = |X|is the number of global variables. Consider affine assignments of the form


xj := t0 + Σki=1ti · xi with ti ∈ Q. Let V denote the complete lattice of

linear subspaces of (k + 1) × (k + 1) matrices over the rationals Q. Eachmatrix A describes the effect of an execution onto the global state. Thereby,each global state is represented by a vector v = [v0, . . . , vk]T ∈ Qk+1 wherev0 = 1 and for i > 0, vi records the value of the variable xi. We write V ′ forthe complete lattice of linear subspaces of (k + 1) vectors over the rationalsQ. The extra component v0 allows to linearize affine transformations. A setS ⊆ Q(k+1)×(k+1) of transformation matrices is abstracted by the linear spaceSpanS∈V of all linear combinations of matrices in S.

The concrete resource sensitive semantics J(u, s, v)Kl : 2Res → Q(k+1)×(k+1)

of an edge is then given by:

J(u, s, v)Kl(R) =

[1 | 0 | 00 | Ij−1 | 0t0 | t1 ... tk0 | 0 | Ik−j

]s = xj := t0 +Σk

i=1ti · xi

J(u, s, v)Kl(R) = Ik+1 otherwise

Where Im denotes the m-dimensional identity matrix. Note that the re-source parameter is not used here, but might be in another instance of theframework and is therefore given for completeness.

The resource sensitive semantics of an execution path π ∈ Π is definedas follows:

JεKl = Ik+1

Jeπ′Kl = Jπ′Kl · JeKlJ〈f〉π1〈/f〉π2Kl = Jπ2K · Jπ1Kl

J〈f1〉π1 . . . 〈fs〉πsKl = JπsKl · . . . · Jπ1KLThe concrete resource sensitive collecting semantics R[u, i]l : 2Res → Qk+1

of a program point u and static priority level i is then given by:

R[u, i]l(R) = {JπK(x) | R = R(π, ∅), x ∈ Qk+1, π ∈ R[u, i]}

As in the paper by Muller-Olm and Seidl [38] this is approximated by itsspan, i.e.:

R[u, i]]l (R) = Span(R[u, i]l(R))

The abstract semantics of an edge JeK]l : 2Res → V is defined by JeK]l (R) =Span{JeKl(R)}. Since in the end equalities holding at a program point areof interest, non-affine assignments, xj =?, can be modeled by assignments ofall constant values. For the abstract semantics this yields:

Jxj :=?K]l (R) = Span

{[1 | 0 | 00 | Ij−1 | 00 | 0 | 00 | 0 | Ik−j

],

[1 | 0 | 00 | Ij−1 | 01 | 0 | 00 | 0 | Ik−j

]}

To each procedure f , assign an abstract function JfK]l : [p] → 2Res → Vwhich summarizes the abstract effect of f . These effects are characterized bythe least solution of the constraint system:


[S]l0] S[fe, i, R]]l ⊇ I

[S]l1] S[v, i, R]]l ⊇ (J(u, s, v)K]lR) ◦]l S]l [u, i, R]]l (u, s, v) ∈ E[S]l2] S[v, i, R]]l ⊇ (JfK]l i (S[u]]m (R))) ◦]l S[u, i, R]]l (u, f(), v) ∈ E[S]l3] S[u, i, R]]l ⊇ JjK]l ◦

]l S[u, i, R]]l

u /∈ Ne, j > i ∨ P(S]m[u] (R))

[S]l4] JfK]l i R ⊇ H]f (S[fr, i, R]]l )

JjK]l ⊇ JqK]l j ∅ q ∈ Irpt, P(q = j)

For two sets of matrices M1,M2 ∈ V , the operator ◦]l : V × V → V isdefined as follows:

M1 ◦]l M2 = Span{A1A2 | A1 ∈M1, A2 ∈M2}

By using the precomputed transformers for resource sets, the priority con-dition including the resource set information can be checked statically andtherefore, for this instance, no dedicated •]l operator performing this check

is needed. Instead, ◦]l can be used for interrupts as well. Since only global

variables are considered, the operator H]f which transforms the abstract se-mantics of a procedure into the abstract semantics of its call, is simply theidentity. For tasks, the resource set parameter R is always the empty set andthe static priority i is the static priority of that task. Thus, if the programdoes not contain procedures, the summaries can be simplified to vector spacesof matrices.

In the second phase, compute for every program point v and static priorityi a mapping R]

l [v, i] : 2Res → V ′. For any given resource set R, this mappingis meant to return the linear hull of all concrete states x ∈ Qk+1 possiblyreaching program point v within a task with static priority i given the currentresource set equals R. The set of all functions 2Res → V ′ forms a completelattice with respect to the partial ordering on functions induced by the partialordering on V ′. From a basis B of R]l [u, i](R) for a program point u withstatic priority i and resource set R, which yields the set of valid equalitiest0 +

∑ki=1 ti · xi = 0 as the set of solutions of the system

t0 · b0 + . . .+ tk · bk = 0 , (b0, . . . , bk) ∈ B

In order to describe the effect of a procedure f for this second phase, werely on two components:

– the summary JfK]m computed by same-level must resource analysis, whichrecords how the execution of f may change the sets of held resources, and

– the summary JfK]l computed by the same-level analysis of linear transfor-mations in the first phase, which for each static priority i and resource setbefore the call returns the vector space of possible linear transformations.

This yields the following constraint system:


[R]l0] R[Te, 0]]l w M0

[R]l1] R[v, i]]l w (JeK]l , JeK

]m)@]

lR[u, i]]l e = (u, s, v) ∈ E[R]

l2] R[v, i]]l w ((JfK]l i), JfK]m)@]lR[u, i]]l (u, f(), v) ∈ E

R[fe, i]]l w enter ]f,l(R[u, i]]l ) (u, f(), v) ∈ E

[R]l3] R[u, i]]l w JjK]l@

]j,lR[u, i]]l u /∈ Ne, j > i

R[j]]l w proj]j,l(Rl[u, i]) u /∈ Ne, j > i

R[qe, j]]l w enter ]q,l(R[j]]l ) q ∈ Irpt, P(q) = j

Here, M0 is the mapping which assigns the full vector space Qk+1 to theempty resource set R = ∅ and the zero space {0} to all resource sets R 6= ∅.The operator @]

l : ((2Res → V ′)× (2Res → 2Res))× (2Res → V ′)→ (2Res → V ′)is defined by:

((M,h)@]lφ)(R′) = Span{Ax | R′ = h(R), A ∈M(R), x ∈ φ(R)}

Recall, that since only global variables are considered, the functionenter ]f,l is the identity function:

enter ]f,l φ = φ

In the constraint R]l3, a modified version of the application and the enteroperator are required, which take into account that an interrupt q can onlybe enabled if the static priority of q exceeds the dynamic priority at a givenprogram point. Therefore, define:

(M@]j,lφ)R = Span{Av | A ∈M(∅), v ∈ φ(R), j > P(R)}

(proj]j,lφ)R =

{Span{v ∈ φ(R′) | j > P(R′)} if R = ∅{0} otherwise

In any case the following theorem holds:

Theorem 4.9. Assume that the program has flow-independent resource setsand satisfies (S). Let furthermore S[v, i], JfK and S[v, i, R]]l , JfK]l , S[v]]m, JfK]mas well as R[v, i]]l denote the least solutions of the constraint systems S, S]l ,

S]m, and R]l , respectively. Then the following holds:

1. For a program point v, static priority i, resource set R and procedure f ,

Span{JπKl | π ∈ S[v, i](R)} = S[v, i, R]]l

Span{JπKl | π ∈ JfK i R} = JfK]l i R

2. For a program point v, static priority i and resource set R

Span{JπKl(x) | π ∈ R[v, i], x ∈ Qk+1,R(π, ∅) = R} = R[v, i]]l (R)


ut

For the constraint system S]l this results in at most n · p2 · 2o constraints.Using the techniques from Muller-Olm and Seidl [38], this implies that theleast solution can be computed in time O(n ·p2 ·2o ·k8). This is a smooth gen-eralization of the results obtained by Muller-Olm and Seidl [38] to the caseof programs with interrupts and resources. Note that a practical implemen-tation may explore the given constraint systems in a demand-driven fashionsuch that only those resource sets are considered which actually are necessaryfor computing the reachability information as provided by the least solutionof R]l . For the special case of tasks only without auxiliary procedures, thismeans that the factor 2o can be dropped completely.

Consider the example program in figure 4.1. Due to the non-deterministicnature of interrupts, it is possible that an interrupt occurs arbitrarily often.This creates an infinite number of program executions for a given programpoint, each corresponding to linear transformations of the state vectors. Sinceonly the linear hull of these transformations is of interest, it suffices to main-tain a basis of the generated sub-space of matrices. Accordingly, this yieldsthe following summaries for the interrupts I and I ′:

JI ′K]l (3, ∅) = Span

{[1 0 0 0 00 1 0 0 00 0 1 0 020 0 0 0 00 0 0 0 1

]}

JIK]l (2, ∅) = Span

{[1 0 0 0 0−1 1 0 0 01 0 1 0 00 0 0 1 00 0 0 0 1

],

[1 0 0 0 0−1 1 0 0 01 0 1 0 020 0 0 0 00 0 0 0 1

]}

These transformations can be applied to compute the subspace of possiblevalues for each program point of the main task. For T4, this yields:

R[T4, 1]]l∅ = Span

{[110000

],

[01−100

],

[00010

],

[00001

]}

The second vector is due to the potential occurrence of the interrupt I.The interrupt I ′ has no impact, since I ′ is not enabled and there are norestrictions on the value of z, at T4. From the basis the following system ofequalities is obtained:

1 · t0 + 10 · t1 = 01 · t1 + (−1) · t2 = 0

1 · t3 = 01 · t4 = 0

Solving this yields the equality x+y = 10. Overall the following equalitiesare obtained:


Node Example EqualitiesT3 x = 10, y = 0, x+ y = 10T4, T5 x+ y = 10T6 t = x+ y = 10T7 x− y + t = 0T8 z = 10T9, . . . , Tr z = 20, t = 10I ′2, I

′r z = 20

This means that at the end of the main task T and the interrupt I ′, theequality z = 20 holds. Moreover, the equality 10 = x + y holds, although,interrupts may freely occur at nodes T4 and T5. Finally, the local variable tequals 10, once it has been written. The equalities for z and t, however, cannotbe guaranteed in I, since I may occur at node T3 where both variables maystill be uninitialized.

Note that while this analysis directly fits into the framework, it is also pos-sible to use analyses, which for example use infinite lattices, evaluate branch-ing conditions, or are even unable to provide closed function summaries. Forinfinite lattices one would use a demand-driven local solver [17] and possiblywidenings [12]. The branching conditions could be added to the flow-graphand the framework semantics extended to treat them as nops while allow-ing the concrete analysis instance to fully evaluate them. Finally, summaryfunctions can be handled by tabulating them. This technique is used in theGoblint analyzer and proved to be very useful.

4.7 Implementation

The data race and transactionality analyses from sections 4.4 and 4.5, respec-tively, have been implemented in the analyzer Goblint for multi-threaded C[58]. This analyzer framework is based on a local fixpoint engine and pro-vides basic analyses such as constant propagation and alias analysis, whichthen can be enhanced with additional specific domains and transfer func-tions. The analyzer differentiates between read and write accesses in orderto avoid read-read warnings. Beyond the path-based approach presented insections 4.4 and 4.5, Goblint takes conditions into account whenever possi-ble. By that, the analysis may exclude some unrealizable execution paths andtherefore may raise less false alarms.

The test suite consists of sample programs from the nxtOSEK implemen-tation [16] together with some handwritten examples. Program biped robot

is part of the control software of a self-balancing two wheeled robot, whichuses resources to synchronize the balancing with remote control commands.The programs xxx test are examples for preemptive scheduling (pe), re-source synchronization (res), time-triggered tasks (tt), and USB communi-cation (usb). Each of these tests uses two tasks and one resource. Programs

4.7 Implementation 61

example and example fun are from figure 4.1 and figure 4.3, respectively.Program pingpong consists of two tasks which alternately set a variable to”ping” and ”pong” synchronizing via a single resource. Program counter

consists of an interrupt which increases two fields of a struct if an integer flagis set and does nothing otherwise. It also utilizes a task which unsets the flag,then prints the struct and re-sets the flag. The integer flag itself is protectedby the resource.

Program Size Time Race Transactionality

biped robot 151 lines 0,02 s 1 0pe test 97 lines 0,06 s 1 1res test 74 lines 0,03 s 0 1tt test 101 lines 0,07 s 1 1usb test 140 lines 0,04 s 0 0example 38 lines 0,01 s 1 1example fun 51 lines 0,01 s 1 2pingpong 53 lines 0,03 s 0 0counter 58 lines 0,02 s 2 1

Table 4.1. Result of analyzing example programs

The results of running the analyzer on these examples are summarized intable 4.1. These experiments were run on a Intel(R) Core(TM)2 Quad CPUmachine with 3.00GHz under Ubuntu 10.04. The analyzer verifies that thetwo programs pingpong and usb test are free of data races. The data racesin both versions of the example program are discovered, as well as the unsafeaccess to counters in pe test and tt test. The race warning in biped robot

occurs since re-running the initialization task is not ruled out. For counter,race warnings are produced for the fields of the struct since they are accessedboth by the task and the interrupt without protection with a resource. Whileit is verified that the integer flag accesses are safe, the analysis presented hereapproximates conditional branching with non-deterministic branching and,therefore, does not relate the flag value with the accesses to the struct. Otheranalyses provided by the Goblint analyzer, however, may split the executionpath based on the value of the flag and thus may separately analyze the casesfor a set and an un-set flag.

Regarding transactionality, the analyzer verifies that the tasks of usb test

and pingpong are transactional. It discovers the violation of transactionalityof the running example and also produces warnings for pe test and tt test

where the race occurs between accesses to the counter. In res test, a variablewhose accesses are otherwise protected by a resource, is read after the releaseof the resource and, therefore, violates the definition of transactionality. Inbiped robot, on the other hand, the accesses to globals may be involved indata races, but are the only accesses to globals in their respective procedures.Accordingly, transactionality is not violated. For counter, a transactionality


200 400 600 800 1,000

1

2

3

4

5

6

7

Number of interrupts

Runti

me

inse

conds

Fig. 4.4. Runtimes of the analyzer on chain n.

warning is produced, since the resource is released between un-setting andre-setting the flag.

All examples are small and therefore analyzed in negligible time. In orderto get an intuition how the analyses scales, the analyzer was also evaluated onthe synthetic benchmarks chain n. While the estimates for the asymptoticcomplexity of the analyses grow exponentially with the number of resources,they depend only linearly on the program size. Therefore, the program sizeis not expected to be the major bottleneck for scalability but the number ofresources and interrupt levels. Thus, these latter parameters are varied in thebenchmarks. For n ≥ 1, program chain n has globals x0, . . . , xn, n interruptlevels and n resources which are used to successively copy the value of thevariable xi into the variable xi−1. The running times of the analyzer for theinstances n = 100, 200, . . . , 1000 are shown in figure 4.4. For each of them,the analyzer verified absence of data races and transactionality of all tasks.

The increase in run time for these instances is slightly worse than lin-ear. Even for 1000 interrupt levels and resources, the runtime is still quiteacceptable. The structure of the program is, however, very regular.

4.8 Related Work

While the ceiling and inheritance protocols [5, 54] have been formally studied[14, 42], these papers focus on schedulability rather than data consistency;that is, one assumes the program is correctly synchronized and character-izes the impact of synchronization primitives on meeting hard deadlines as a

4.8 Related Work 63

function of resource usage. In contrast, here the focus is on the detection oferroneous uses of these synchronization primitives.

Already simple analysis problems for concurrent programs with recursionand synchronization are undecidable [46]. Practical approaches therefore ei-ther over-approximate the interaction between threads, as in thread-modularmodel checking [18], or ignore synchronization altogether [8, 15]. Some papersalso place restrictions on concurrency. In a number of papers, Kahlon et al.[26–28] discuss model checking of pushdown systems synchronized via lockswhere the usage of locks must be well nested. This approach has been gener-alized to pushdown systems with dynamic thread creation by Muller-Olm etal. [34, 35]. With, potentially, the exception of dynamically changing prior-ities, programs with priority-preemptive scheduling extended with dynamictask creation can also be cast within the more general model of multi-setpushdown systems. For these, Atig et al. [3] show that control point reach-ability is decidable. Their approach is based on Petri net reachability anddoes not support the inference of more complicated invariants such as linearequalities.

Kidd et al. [30] observe that every priority preemptive system can betransformed into a pushdown system. Beyond that, they additionally repre-sent the schedulers corresponding to synchronization protocols such as prior-ity ceiling or priority inheritance, as exponentially large pushdown systems.In case of priority ceiling as well as for priority inheritance with well-nestedresource usage, these two systems can be combined into one pushdown sys-tem. From that, they conclude that reachability is decidable for priority ceil-ing as well as for priority inheritance with well-nested resource usage. Theapproach presented here cannot be applied to priority inheritance directly,while for priority ceiling, the analysis is exponential only in the number ofresources (not in the number of interrupts).

Another model-checking result for asynchronous programs by Ganty etal. [20] considers programs with priorities where tasks can be added to amulti-set buffer which is then handled by a scheduler and prove that livenessproperties such as termination and starvation are decidable. To do so, theprogram is first transformed into an asynchronous automaton and then intoa Petri net.

Summarizing abstract effects of interrupts has also been considered byRegehr and Cooprider [48] in order to analyze stack overflow in assemblycode. Their summaries describe the stack consumption of an interrupt to-gether with the set of interrupts which become enabled/disabled by the exe-cution. Their model does not deal with specific protocols such as PCP. Ad-ditionally, they present in [47] a transformation technique to turn interrupt-driven embedded code into thread-based code and apply off-the-shelf racedetection tools to the transformed code. They introduce artificial interruptlocks to make interrupt disabling/(re-)enabling visible to the analysis. Theyassume fixed static priorities and suffer from the imprecision possibly incurred


by the thread analyzer. In contrast, the approach presented here directlyexploits the properties of the priority ceiling protocol for interrupt-drivenconcurrency and explicitly deals with dynamically changing priorities. Thisallows the precise handling of set of possible interleavings.

Flanagan et al. [19] present a type system for atomicity in concurrent Javaprograms. A transactional procedure as defined in this chapter is atomic intheir sense since every execution of a transactional procedure that is possiblyinterrupted has an equivalent serial execution, i.e., no interrupts occur duringits execution. This atomicity condition is relaxed by Vaziri et al. [56], whoprovide a set of problematic access patterns and show that they are complete,i.e., the absence of all these patterns guarantee that the execution is serial-izable with respect to the critical variables and demarcated critical sections.The presented notion of transactionality for a procedure f considers all, po-tentially accessed, global variables as critical for f where the critical sectionof f is the section between the first and last access to global variables. Kiddet al. [29] provide a static analysis for Java programs to verify the absenceof such patterns in a given program. Artho et al. [2] give a static analysisto detect stale-value atomicity violations, i.e., accesses to outdated values ofglobals stored in a local variable that has escaped the critical section.

4.9 Conclusions

This chapter provides practical methods to analyze data races and transac-tionality in priority ceiling based programs. Moreover, the analysis of linearequalities can be considered as one instance of an analysis framework whichgeneralizes the functional approach of Sharir and Pnueli [55] from programswith, just, procedures to programs that use the priority ceiling protocol andcontain of procedures, interrupts, priorities and resources. Other instances ofthis framework can be obtained by providing specific domains V and V ′ forsummary functions and abstract states, respectively, together with transferfunctions for the basic statements and specific versions of the operators ◦, •j ,Hf , @, enterf , @j and projj .

The analyses of potential data races and transactionality have been imple-mented within the static analyzer Goblint [58]. Preliminary experiments withtypical examples as well as a scalable synthetic benchmark are encouraging.Still, experiments with larger and more complicated real-world examples aredesirable.

5 Value-dependent Synchronization

Embedded computing pervades the automotive industry. Dedicated operatingsystems and standards, such as Autosar/OSEK1[9, 22], have been createdand are used by many car manufacturers. These operating systems providesophisticated synchronization primitives, such as priority-driven schedulingand resource acquisition. Still, developers sometimes rely on hand-craftedmechanisms for ensuring safe concurrent execution. One such mechanism isto use global program variables as flags whose values control the access tocritical sections. Accordingly, any analysis of OSEK programs, such as thosepresented in chapter 4, which only take resources and priorities into account,will produce a large number of false alarms on real-world automotive code.

An example of a typical flag-based synchronization pattern used by de-velopers is shown in figure 5.1. This program consists of two interrupt serviceroutines that are executed by a priority driven scheduler.

int f = 0;int x = 0;/∗ Priority 3 ∗/isr Q() {

if (f == 0)x−−; /∗ Qx ∗/

}

/∗ Priority 1 ∗/isr I () {

f = 1;x++; /∗ Ix ∗/f = 0;}

Fig. 5.1. Example code of program with a flag f.

The low-priority interrupt I sets a flag f to 1 before entering its criticalsection and resets it to 0 afterwards, whereas the higher-priority interrupt Qfirst checks whether the flag f has been set and only enters its critical sectionif f equals 0. This ensures, in a priority-driven single-core concurrency setting,that the accesses to x will always be exclusive. Note that priorities are crucialfor such non-symmetric idioms: The higher-priority interrupt Q may safelyassume that it cannot itself be preempted by the lower-priority interrupt Ibetween checking the flag and accessing the data. Conversely, having checked


66 5 Value-dependent Synchronization

the flag, it would be redundant for the high priority interrupt to set and resetthe flag. Idioms like this, when properly used and implemented, can indeedprotect critical sections. Still, being hand-crafted, they are error-prone andmay be rendered insufficient if further priority levels are introduced. If, forexample, another interrupt R is introduced, whose priority exceeds that of Q,but uses the same pattern to access the variable x, a potential race conditionarises between interrupts Q and R.

The goal in this chapter, therefore, is to provide practical methods foridentifying and analyzing a wide range of synchronization patterns based onglobal variables, in order to provide a more accurate data-race analysis.

In principle, interrupt-driven programs with priority-based scheduling ona single-core can be analyzed by interpreting interrupts as function calls pos-sibly occurring at every program point [30, 50]. Practically, though, context-and flow-sensitive handling of the global program state is prohibitively expen-sive. The approach outlined in chapter 4 is to arrive at a practical analysis ofmutual exclusion for interrupt-driven programs by analyzing local data suchas dynamic priorities and resources context-sensitively, while summarizingthe global state into a single flow- and context-insensitive invariant. How-ever, when global variables are used as flags, that approach is insufficient inprecision.

The key contributions of this chapter are, first, to identify general proper-ties of global variables used as flags in a wide range of hand-crafted synchro-nization patterns, and second, using these properties to construct efficientdedicated analysis methods based on off-the-shelf inter-procedural analysis.In particular, the resulting analysis turns out to be interrupt-modular, mean-ing that each interrupt can be analyzed independently. In a second stage, theresulting summaries can be combined to precisely and efficiently compute theset of values that a flag variable may take at any given program point. Thisinformation, finally, is exploited to ensure that two program points are notpart of a data-race.

At first, this chapter will consider a class of primitive flag-based synchro-nization patterns, which allow a low-priority interrupt to protect its criticalsections against cooperating interrupts from higher priority levels. For exam-ple, the synchronization pattern used in figure 5.1 falls into this class. Forthis restricted class of flags, it suffices to only consider the intra-interruptvalue-sets of the flag variable. For that, it is verified that program points canonly be part of a data race if the protecting flag variable has overlappingvalue sets.

In a second step the conditions on flag variables are generalized in orderto handle a richer class of synchronization patterns, while keeping interrupt-modularity. An example of such a pattern is provided in figure 5.3 in sec-tion 5.6. A critical feature of both techniques is that they are sound on allprograms; that is, they do not merely assume that the flags are well-behaved.Instead, they also verify the assumptions on the flag variables themselves.

5.1 OSEK Model 67

Thus, the techniques can be applied one after the other on-demand to ensurerace freedom when purely resource-based analyses fail. The analysis dealswith recursive procedures in polynomial time, while still computing flag val-ues precisely and remains feasible and sound on real world programs. Thecore technique has been implemented in the Goblint analyzer [58]. This notonly allowed to decrease the number of warnings on a suite of toy examples,but also resulted in a drastic reduction of alarms in the presented industrialbenchmarks.

5.1 OSEK Model

An OSEK program consists of tasks and interrupts. Tasks are activated bydirect calls or timers. Interrupts can occur at any time. The priority ceilingprotocol [54] is used for scheduling. Tasks and interrupts have a static initialpriority which my be dynamically increased during execution by acquiringresources and possibly decreased again by releasing resources, where the dy-namic priority never drops below the static initial priority. An interrupt willpreempt the running execution, if its static priority exceeds both the staticand dynamic priority of the running task or interrupt.

Since execution time and timer information is not used, and generally hardto obtain time triggered tasks are treated as interrupts. For the purpose ofthis chapter, a programming model can be used which consists of a finite setof procedures Proc; a finite collection of interrupt routines Irpt together witha starting node T , which serves as an initial task for interrupts to preempt.A procedure or interrupt g is given by a control flow graph (Ng, Eg). For twodifferent procedures or interrupts these graphs are disjoint. Let N denotethe union of all sets Ng of program points, extended with T . Likewise, let Edenote the union of all sets Eg of control flow edges. Entry and return nodesof g are unique and denoted as sg and rg, respectively. Additionally, the setof priorities is given by P = {0, . . . , pmax}. In this chapter, it is assumed thateach node u ∈ N is always reached with the same priority P(u) ∈ P, wherethe static initial priority of an interrupt q ∈ Irpt is attained at program pointsq and T is the only node with minimal priority, i.e., P(T ) = 0. Edges inE are triples (u, cmd, v) leading from program point u to program point vby means of the command cmd. The command cmd can be either a basicstatement s like an assignment x = 42; or a guard (x != y)?, or a procedurecall h() otherwise. For the purpose of this chapter, the restrict case of globalvariables only is considered. Therefore, procedures neither need parametersnor return values. The execution of basic statements is assumed to be atomic.How to deal with local variables and parameters is an orthogonal matter anddiscussed in [32].

In general, the assumption that the dynamic priority is a function ofthe program point only need not be met by arbitrary OSEK programs. Theissue of computing and tracking dynamic priorities, however, is orthogonal


3 3 3

1 1 1 1

eQ Q1 rQ

eI I1 I2 rI

f==0? x--

(f !=0)?

f=1 x++ f=0

Fig. 5.2. Example program with a flag f.

to the problem of dealing with flag variables. Therefore, this simple settingis used, in particular, since it always can be achieved by introducing distinctcopies of program points for distinct priorities. For a detailed discussion oncomputing context and resource aware priorities, see chapter 4. Another wayof viewing this priority is as the minimum priority with which a node can bereached. All results remain sound in case a node can be reached with differentpriorities. Precision statements are to be taken as proving that no additionalprecision is lost after approximating priorities. Since interrupts may neverdrop below their initial priority, this assumption implicitly creates distinctcopies for functions that are called at different priorities. The functions arenot restricted in any other way. In particular they might be recursive orchange priorities.

In order to define data races in a single-core concurrency setting, it is notenough to know that two accesses are both reachable. Whether two accessesare safe or not is decided by the path the program takes from one accessto the other. Therefore, a path-based concrete semantics is chosen for themodel. A similar formalization can be found, e.g., in [38]. Here, a path is asequence of control flow edges where the empty path is denoted by ε. For twosets of paths, M1, M2, the concatenation operator @ appends every path inM2 to every path in M1:

M1@M2 = {π1π2|π1 ∈M1, π2 ∈M2}

In a first step, the sets of same-level paths, i.e., paths leading from theentry node to the return node of the same procedure or interrupt, are char-acterized as the least solution to the following constraint system:

[S0] S[sg] ⊇ {ε} g ∈ Irpt ∪ Proc

[S1] S[v] ⊇ S[u]@{(u, s, v)} (u, s, v) ∈ E[S2] S[v] ⊇ S[u]@S[rh] (u, h(), v) ∈ E[S3] S[u] ⊇ S[u]@S[rq] q ∈ Irpt, P(u) < P(sq)

Given these sets of same-level paths, the sets of paths reaching programpoints from the initial node T are characterized by the following constraintsystem:

5.2 Inter-procedural Analysis of Flags 69

[R0] R[T ] ⊇ {ε}[R1] R[v] ⊇ R[u]@{(u, s, v)} (u, s, v) ∈ E[R2] R[v] ⊇ R[u]@S[rh] (u, h(), v) ∈ E

R[sh] ⊇ R[u] (u, h(), v) ∈ E[R3] R[sq] ⊇ R[u] q ∈ Irpt, P(u) < P(sq)

R[u] ⊇ R[u]@S[rq] q ∈ Irpt, P(u) < P(sq)

In the next step, a value semantics is introduced can check whether a pathis executable for a given initial state or not. Let D denote the set of programstates. The concrete value semantics defines for every basic statement s apartial transformer JsKV : D 99K D. This semantics is lifted to a semanticsJ·K : E → D 99K D, of control flow edges (u, s, v) by J(u, s, v)K = JsKV . Thepartial state transformer JπK for a path π = e1 . . . en then is obtained as thecomposition of the state transformers JeiK of the edges contained in π, i.e.,

JπK = JenK ◦ · · · ◦ Je1K

A path π is executable for an initial state σ if JπK σ is defined. Let Mdenote any set of paths. Then the set of paths in M which are executablefor σ is given by Π(M,σ) = {π ∈ M | π is executable for σ}. Intuitively,a data race occurs at variable x if a low-priority interrupt, q1, accesses xin an edge reaching a program point v1, at which point it is immediatelyinterrupted by a higher-priority interrupt q2, which accesses x at a programpoint v2. However, as long as q1 is not allowed to continue, there may beother interrupts, before q2 occurs. This notion is formalized by the followingdefinition.

Definition 5.1. There is a data race at variable x in a program (N,E) withinitial state σ, if there exists an executable path π ∈ Π(R[v2], σ) reachingsome program point v2 where

π = π1( , s1, v1)(sq, , )π2( , s2, v2)

such that the following holds:

(a) s1 and s2 are accesses to x;(b) P(v1) < P(sq), P(v1) < P(v2) and also P(v1) < P(v) for every program

point v occurring in π2.

5.2 Inter-procedural Analysis of Flags

Consider the program in figure 5.1. Race freedom of this program can onlybe verified by taking the values of the global variable f into account. Thisvariable is set to 1 to flag the critical section of the lower-priority interrupt,


and reset to 0 again to signal that the critical section has been left. Theinformation provided by f is respected by the higher-priority interrupt Q inthat its value is tested against 0 before Q enters its own critical section. Afirst practical property of a variable f used in such a pattern therefore is:

Property 1. f is assigned constants only, and f is checked against constantsonly.

Also, such synchronization patterns assume an application wide consentabout the role of such a variable f and its values. This means that higher-priority interrupts will respect the value of f . This leads to the second prop-erty:

Property 2. Let pf denote the least static priority of an interrupt where f isaccessed. Then all interrupts of priority exceeding pf leave f intact.

Property 2 means that the value of f before any interrupt q at priorityP(sq) > pf equals the value of f after termination of q. Note that it is notruled out that the interrupt q may change the value of f , e.g., in order toprotect its own critical section against even higher-priority interrupts as infigure 5.3 following in section 5.6. In this case, however, q must restore theold value before termination. Subsequently, variables f satisfying properties 1and 2 are called flags.

5.3 Intra-Interrupt Flag Analysis

Let F denote the set of candidate flag variables, i.e., all variables which satisfyproperty 1. For each f ∈ F let Vf denote the set of possible values of f atrun-time. Note that F together with all sets Vf can be easily constructed fromthe program text. For simplicity, assume that for all f ∈ F , Vf ⊆ Z. The goalis to compute for each program point u the set of all possible values of all flagvariables f when reaching this program point. For each flag f a summary iscomputed for each interrupt or procedure g, which maps the value of f beforeentering g to the set of possible values of f at a program point u in g. Thisanalysis is not new. It is the enhancement of simple constants with simpleguards as discussed in, e.g., [31, 60]. First summaries of basic edges are given.

The abstract semantics J·K] : E → Vf → 2Vf for flag f is given by:

5.3 Intra-Interrupt Flag Analysis 71

J(u, f = c; , v)K] c′ = {c}

J(u, f == c?, v)K] c′ =

{{c′} if c′ = c

∅ otherwise

J(u, f != c?, v)K] c′ =

{{c′} if c′ 6= c

∅ otherwise

J(u, f < c?, v)K] c′ =

{{c′} if c′ < c

∅ otherwise

J(u, f > c?, v)K] c′ =

{{c′} if c′ > c

∅ otherwise

J(u, , v)K] c′ = {c′} otherwise

Due to property 1, no other assignments or guards involving variable fmay occur in the program. It is also assumed that the address of f is nevertaken. First, the effect of a procedure is given by the following constraintsystem where composition is lifted appropriately by:

(g ◦ h) c =⋃{g c′ | c′ ∈ h c}

Then the following constraint system is defined:

[F′0] S][sh] w (c 7→ {c}) h ∈ Proc

[F′1] S][v] w J(u, s, v)K] ◦ S][u] (u, s, v) ∈ E[F′2] S][v] w S][rh] ◦ S][u] (u, h(), v) ∈ E

Note that this is the characterization of the flag summary defined accord-ing to inter-procedural analysis only, i.e., as if no interrupts may occur. This ismade possible due to property 2 which implies that interrupts, at least whenflag variables are concerned, have no impact. Using the inter-procedural sum-maries, the transformation of flag values from the beginning of the executionof an interrupt to any given program point is characterized by:

[F0] R][sq] w (c 7→ {c}) q ∈ Irpt

[F1] R][v] w J(u, s, v)K] ◦R][u] (u, s, v) ∈ E[F2] R][v] w S][rh] ◦R][u] (u, h(), v) ∈ E[F3] R][sh] w R][u] (u, h(), v) ∈ E

In practice all flags would be analyzed simultaneously. This analysis islinear in the size of the program and the number of flags. For each flag f itis quadratic in the number of possible values of f . Formally, it is shown thatthe analysis is sound given that property 2 holds.

Lemma 5.2. For a program point u, flag f and initial state σ the followingholds: ∀π ∈ Π(R[u], σ):

(JπK σ) f ∈ R][u] (σ f)


Proof. The proof is by induction on the lengths of paths obtained as solutionsof the system [R]. For the initialization constraints [S0], [R0], and [F′0], [F0]use that JεK σ = σ and obtain:

R][sq] (σ f) = {σ f} 3 σ f = (JεK σ) f ⊆ R[T ] ⊆ R[sq]

Assuming the condition holds for a given path π, consider how adding anedge (or summary path) and applying the corresponding constraint in the[F/F’] system may change the result. Due to property 2 interrupts do notcontribute to the values of f . Therefore, the constraints [S3] and [R3] mustnot be considered. For the extension of π with a basic edge the result followsas a direct consequence of J·K] soundly abstracting J·K. This works for bothprocedure summaries constructed by [S1] and [F′1] or reaching informationconstructed by [R1] and [F1]. For same-level paths constructed by [S2] and[F′2] the result then follows by induction. Consequently, the result is alsoobtained for [R2] and [F2]. By induction, it is known that every programpoint u that influences a procedure entry node sh is a sound approximation.The result for sh then follows by monotonicity.

ut

In order to show which programs the analysis can handle precisely, anabstraction of J·K is introduced which only evaluates guards on flag f anddenote it by J·Kf . E.g., J(u, x == y, v)Kf σ = σ for any σ, as the expressionx == y does not use the flag f , however, J(u, f == 5, v)Kf σ = σ only inthe case where σ f = 5. If this is not the case it is undefined. A path π isf -executable for an initial state σ if JπKf σ is defined. Let M denote any setof paths. Then the set of paths in M which are f -executable for σ is givenby Πf (M,σ) = {π ∈M | π is f -executable for σ}.

Lemma 5.3. For a program point u, priority i, flag f and initial state σ thefollowing holds:

Πf (R[u], σ) 6= ∅ =⇒ R][u] (σ f) ⊆⋃

π∈Πf (R[u],σ)

{(JπK σ) f}

Proof. In case R][u](σ f) = ∅ the subset relation holds trivially. Otherwise,do induction on Kleene-iteration steps solving the constraint system [F/F′].First consider the initialization constraints [F0] and [F′0]. For entry nodes sg,it holds that ε ∈ Πf (R[sg], σ). Since JεK is the identity function this yields:

R][sg] (σ f) = {σ f} ⊆ (JεK σ) f ⊆⋃

π∈Πf (R[sg ],σ)

{(JπK σ) f}

For the application of constraints [F1] and [F′1] the result follows since for

a flag J·K] is complete with respect to J·K. For constraint [F′2] the result thenfollows by induction, and consequently for [F2]. Regarding [F3] it is known by

5.4 Simple Analysis of Flags 73

induction that the condition holds for all program points on the right handside of the constraint. This yields:

R][sh] (σ f) =⋃

(u,h(),v)∈E

(R][u] (σ f)) ⊆

⋃(u,h(),v)∈E

⋃π∈Πf (R[u],σ)

{(JπK σ) f} ⊆⋃

π∈Πf (R[sh],σ)

{(JπK σ) f}

ut

Together lemmas 5.2 and 5.3 show that if property 2 holds precision is lostwith respect to the concrete semantics only when guards on other variablesinfluence the value of f . Making use of the general properties of OSEK pro-grams, a check of property 2 can be bootstrapped from the results of system[F/F’].

Theorem 5.4. For a flag f property 2 holds if for all interrupts q and initialstates σ the following holds:

R][rq] (σ f) = {σ f}

Proof. Consider an interrupt q of maximal priority, i.e. P(sq) = pmax. Fora program point u occurring in a path π ∈ Π(R[rq], σ), the condition ofconstraint [S3] is never satisfied since P(u) ≥ P(sq). Thus constraint [S3]does not contribute to R[rq]. Consequently lemma 5.2 holds for rq evenwhen property 2 is not generally satisfied. Therefore for π ∈ Π(S[rq], σ)and S][rq] (σ f) = {σ f} this yields:

{(JπK σ) f} = S][rq] (σ f) = {σ f}

I.e. property 2 holds for q. If property 2 holds for all interrupts of maximalpriority his argument can be repeated for the next lower priority and so on.

ut

5.4 Simple Analysis of Flags

In this section, a first analysis of flag based synchronization patterns is pro-vided where no value of f is excluded before an interrupt occurs. Accordingly,the analysis of each interrupt starts with Vf . Then by lemma 5.2, the set ofpossible values of f at any program point u is given by:

R[[u] =⋃{R][u] c | c ∈ Vf}

Now consider a global variable x. Simple protection mechanisms for x bymeans of the flag f assume that the value of f after the protected access tox is reliable. Here, f is called reliable at a program point u, if its value may


not be intermediately changed by any higher priority interrupts occurringat u. Then f is reliable at u if for all interrupts q that may occur at u, i.e.P(sq) > P(u), and every program point v reachable from sq without enteringanother interrupt this yields:

R][v] c ⊆ {c} for all c ∈ R[[u]

This test can be done in time linear in the size of the program and thenumber of values of f . The following theorem shows how reliable values of aflag f can be used to verify the absence of data races.

Theorem 5.5. Assume that u and v are end points of accesses to x where vis reached without entering another interrupt by an interrupt q with P(u) >P(sq) and flag f is reliable at program point u. Then no data race between uand v occurs, if R[[u] ∩R[[v] = ∅.

Proof. Assume there is a race path going through u and v. Since the flagf is reliable at u, the sub-path π from u to v may not contain assignmentschanging f . Let σ be a state reaching u where π is executable for σ andσ f = c ∈ R[[u]. Let π = π1(sq, , )π2 where π2 contains no interrupt entryedges. Then the program state σ1 = Jπ1K σ after execution of π1 as well asJπ2K σ1 will map f to c. Therefore by lemma 5.2, c also must be included inR[[v]. Accordingly, R[[u] ∩R[[v] 6= ∅ in contradiction to the assumption.

ut

In the program in figure 5.1, the flag f is reliable at Ix where R[[Ix] = {1}and R[[Qx] = {0}. Accordingly, due to theorem 5.5, the program does notcontain a data race. However, for the pattern in figure 5.3, the flag is notreliable in the sense of the definition presented here. Therefore, theorem 5.5cannot exclude a data race for variable x.

5.5 Precise Analysis of Flags

The flag analysis from the last section is imprecise regarding two main points.First, all flag values are assumed to possibly occur at all entry points ofinterrupts. Second, only reliable flag values could be exploited for discardingpotential races. In this section the approach is therefore refined by preciselytracking how flag values may change along inter -interrupt paths. Due toproperty 2, the value analysis from section 5.2 provides valid intra-interruptresults for a given set of flag values at the beginning of the correspondinginterrupt. In order to use these results to determine whether a value is possibleat the start of an interrupt, they are refined by additionally recording theminimal priorities at which a flag value is attained. The minimal priority atwhich a flag f obtains a certain value is crucial since this is when the valueis propagated to the largest number of further interrupt entry nodes.

5.5 Precise Analysis of Flags 75

Accordingly, now abstract values of the form Vf → P∞ are considered,where P∞ = P ∪ {∞} and ∞ denotes that a value is not obtained at all.The ordering is point-wise and reversed, i.e., ⊥ maps all values to ∞ (novalues are obtained) whereas > maps all values to 0 (all values can occur atall interrupt entry nodes). The constraint system [C] following on the nextpage accumulates for every interrupt and procedure the occurring values offlag f and the corresponding minimal priorities. In that constraint system,priorities are added to value summaries R[u]] of type Vf → 2Vf by means ofthe functions pryi which returns a function of type Vf → Vf → P∞ and isdefined by:

pryi φ c c′ :=

{i if c′ ∈ φ c∞ otherwise

First the functions S∗[rh] (h a procedure) is characterized where S∗[rh] c c′

denotes the minimal dynamic priority at which the flag f could take the valuec′ along any f -executable path in h when the initial value of f is c. For this,the values computed by S][·] are accumulated and priorities are added by thefunctions pryi.

[C0] S∗[sh] w pryP(sh) S][sh] h ∈ Proc

[C1] S∗[v] w (pryP(v) S][v]) t S∗[u] (u, , v) ∈ E[C2] S∗[v] w S∗[rh] t S∗[u] (u, h(), v) ∈ E

By means of these procedure summaries, the mappings R∗[u] are char-acterized, where R∗[u] c c′ indicates the minimal priority at which flag fmay have value c′ along paths reaching u when the value of f equals c at theprogram point where the last interrupt before reaching u occurs. These aregiven by the least solution to the following constraint system:

[C3] R∗[sq] w pryP(sq) R][sq] q ∈ Irpt

[C4] R∗[v] w (pryP(v) R][v]) tR∗[u] e = (u, s, v) ∈ E[C5] R∗[v] w S∗[rh] tR∗[u] (u, h(), v) ∈ E

Since the constraint system [C] is a pure join system (the only operatorin right-hand sides is t), the least solution can be computed in time linearin the size of the program and polynomial in the number of flag values. Theformal correctness of this construction is given by the following lemma.

Lemma 5.6. For a program point u, flag f and initial state σ with σ f = cthe following holds:

(1) For all paths π ∈ Πf (R[u], σ) that do not contain any interrupt edges(sq, , ) and program points v such that π = π1( , , v)π2 and the semantics(Jπ1( , , v)K σ) f = c′ it follows that R∗[u] c c′ ≤ P(v).


(2)If R∗[u] c c′ = p then there exists a path π ∈ Πf (R[u], σ) that does notcontain any interrupt edges (sq, , ) and there exists a program point v suchthat π = π1( , , v)π2 and (Jπ1( , , v)K σ) f = c′ and P(v) = p.

Proof. The proof is done by induction on the Kleene iteration steps usedto compute the fix-point. Since the same priority information is used in thesystems [C] and [R] lemmas 5.2 and 5.3 imply the result for the initializationconstraints [C0] and [C3]. Again by lemmas 5.2 and 5.3 and induction itfollows that the result holds for both operands of a join. Soundness thenfollows directly. For the completeness statement (2) note that P∞ is totallyordered. Therefore the join operator element-wise selects the result of one ofits operands.

utNote that paths with interrupts are implicitly covered as well, since prop-

erty 2 ensures that higher priority interrupts do not affect the attained flagvalues and priorities. Therefore, R∗[u] can be applied to the state just beforethe final interrupt of a path occurs.

Consider, e.g., the program in figure 5.1. For the return nodes of rI andrQ this yields R∗[rI ] 0 = {0 7→ 1, 1 7→ 1} and R∗[rQ] 0 = {0 7→ 3, 1 7→ ∞},respectively.

The results of the intra-interrupt accumulation of flag values and prioritiesare now combined to summarize the effects of all interrupts of a given priority.For each priority i, let Ii denote the least upper bound of R∗[rq] for allinterrupts q of priority i. Thus, Ii c c

′ returns the least priority for which theflag f may obtain value c′ inside an interrupt of priority i if the value of f isc before execution is interrupted (by an interrupt of priority i).

In particular, since there are no interrupts of priority 0, the function I0 c′ c

returns 0 for c′ = c and ∞ otherwise. This reflects the fact that initial valuesare visible to all interrupts.

Formally, this yields:

Lemma 5.7. For a program point u, flag f , initial state σ with σ f = c anda path π ∈ Πf (R[u], σ) with π = (sq, , )π′ where π′ contains no interruptedges (sq′ , , ) and (JπK σ) f = c′, the following holds:

IP(sq) c c′ ≤ P(u)

Proof. By definition of Ii, it holds that Ii c c′ ≤ R∗[rq] c c′ and fromlemma 5.6 it is obtained that R∗[rq] c c

′ ≤ P(u).ut

Conversely it can be shown that the functions Ii are complete with respectto f -executable paths.

Lemma 5.8. For a flag f and initial state σ with σ f = c if Ii c c′ = j

then there exists an interrupt q with P(sq) = i and a path π ∈ Πf (R[rq], σ)such that π = (sq, , )π1( , , v)π2, π1 contains no interrupt edges (sq′ , , ),(J(sq, , )π1( , , v)K σ) f = c′ and P(v) = j.

5.5 Precise Analysis of Flags 77

Proof. Since P∞ is totally ordered, the join on Vf → Vf → P∞ can alwaysselect one of the joined values. Therefore, no finite priorities are introducedfor values, which are not actually obtained during some interrupt. Let qdenote the interrupt, such that R∗[rq] c c

′ = j. Lemma 5.6 then yields a pathrealizing the value c.

ut

For the example of figure 5.1, this yields I1 = R∗[rI ] and I3 = R∗[rQ]. Theempty union for I2 yields the constant∞ function which can be ignored sinceit does not add any values. Taking the initial function δ mapping the initialflag value 0 to priority 0 and all other flag values to∞ I ′1δ additionally mapsflag value 1 to priority 1. This means flag value 0 can occur at the entry ofall interrupts while 1 can only reach entry nodes of interrupts with prioritiesgreater 1.

In order to account for inter -interrupt effects, the mappings Ii : Vf →Vf → P∞ are lifted to mappings (Vf → P∞)→ (Vf → P∞) by:

(lift Ii) δ = δ t⊔{Ii c | c ∈ Vf , δ c < i}

Thus, the transformation (lift Ii) takes a mapping of flag values to pri-orities and returns the mapping, which maps each value c to the minimalpriority at which flag f can attain value c if additionally interrupts at prior-ity i are taken into account. Note that the application of (lift Ii) to a mappingδ can be represented as matrix operations and therefore computed in timepolynomial in the number of possible values.

In the final step, the inter-interrupt summaries I(i,j), comprising the ef-fects of interrupt at priority levels between i and j, are obtained from thelifted intra-interrupt summaries by composition:

I(i,j) = (lift Ij) ◦ . . . ◦ (lift Ii)

For i > j, it is assumed that I(i,j) equals the identity transformation. Thelevel summaries do not need to be composed in every possible order, since ahigher priority must terminate before another interrupt of lower priority canexecute. But on termination the higher priority interrupt must have restoredthe values of flags, i.e. for the lower priority interrupt it might as well nothave occurred. Therefore, only chains of consecutive interruptions add newentries to the set of possible values of a flag f . Such chains, however, musthave strictly increasing priorities. Let initi : 2Vf → (Vf → P∞) denote thefunctions that given a set of values C returns the mapping which maps eachvalue in C to i, i.e initi C c = i for c ∈ C and ∞ otherwise. Applying init0 tothe set of initial values of flag f reflects the fact that initial values can occurat all interrupt entry nodes. Moreover, let filterj denote the function whichtakes a mapping of flag values to priorities and returns the set of values ofpriorities less than j, i.e., filterj δ = {c | δ c < j}. Applying filterj returns theset of flag values possible at entry nodes of interrupts of priority j according


to the given mapping. With these definitions, the set of all possible values offlag f at entry nodes of interrupts with priority j is obtained by:

Cj = filterj ◦ I(1,j−1) ◦ (init0 C0)

Here C0 is the set of possible values of f at program start. Accordingly,the set of all values of f possibly occurring at program point u when reachedby an interrupt with priority j, is given by:

R[[u, j] =⋃{R][u] c | c ∈ Cj}

The complexity of applying I(i,j) to some initial mapping of values topriorities requires (j − i) applications of a lifted transformation (lift Ii′).Therefore, this can be done in time polynomial in the number of possible flagvalues where the exponent linearly depends on j − i.

Theorem 5.9. For a program point u reached by an interrupt with priorityj, flag f and initial state σ with σ f ∈ C0, the following holds:

R[[u, j] ⊇⋃

π∈Πf (R[u],σ)

{(JπK σ) f}

Proof. For a path π ∈ Πf (R[u], σ) with (JπK σ) f = c′′ show that c′′ ∈R[[u, j]. In case that j = 1, the following holds:

R[[u, j] =⋃{R][u] c | c ∈ C1} =

⋃{R][u] c | c ∈ (filter1 ◦ (init0 C0))} =⋃{R][u] c | c ∈ C0} ⊃= R][u] (σ f)

With lemma 5.2 the result follows. For higher context priorities decompose πinto the two parts. The part inside the final interrupt q and the part beforeq. Let π = π′( , , v)(sq, , )π′′ where P(sq) = j and π′′ does not contain anyinterrupt edges (sq′ , , ). Since lemma 5.2 applies (sq′ , , )π′′ again what’sleft to show is that the values observable by sq′ are contained in Cj . Let(Jπ′( , , v)K σ) f = c′. Then lemma 5.7 yields that there exists a priorityi ≤ P(v) such that Ii (σ f) c′ = i. Since j = P(sq) > P(v) this yields c′ ∈ Cjconcluding the proof.

ut

Note that property 2 ensures that the interrupt-free tails exist. Otherwise,higher priority interrupts changing f might be necessary to reach u with c′′.For f -executable paths the sets of reaching values are also complete.

Theorem 5.10. For a program point u reached by an interrupt with priorityj, flag f and initial set C0 the following holds:

R[[u, j] ⊆⋃

σ f∈C0

⋃π∈Πf (R[u],σ)

{(JπK σ) f}

5.6 Data Race Analysis 79

Proof. In case R[[u, j] = ∅ the result follows directly. Otherwise lemma 5.3yields that for every c′ ∈ R[[u, j] there exists a c′′ ∈ Cj such that for a stateσ2 with σ2 f = c′′ there exists a path π2 ∈ Πf (R[u], σ2) with (Jπ2K σ2) f = c′

and π2 = (sq, , )π′2 with P(sq) = j. If there exists a program point vwith P(v) < j such that there exists state σ with σ f ∈ C0 and a pathπ1inΠf (R[v], σ) with (Jπ1K σ) f = c′′ then π1π2 ∈ Πf (R[u], σ) conclud-ing the proof. If, however, there is no such state or program point then bylemma 5.8 it follows that ((lift Ii−1)◦· · ·◦(lift I1)◦(init0 C0)) c′′ ≥ j. Thereforefilterj would remove c′′ in contradiction to lemma 5.3.

ut

Consider the program in figure 5.1. For program points in the critical sec-tion Ix and Qx the analysis yields R[[Ix, 1] {0} = {1} and R[[Qx, 3] {0} ={0}.

5.6 Data Race Analysis

In the previous section it was shown that the values of a flag f can be trackedprecisely along all f -executable paths reaching a given program point. A datarace, however, consists of two program points u and v at which shared data isaccessed, and a path from one access to the other. Therefore, the results forreaching values are extended to start from any given priority level (insteadof 1). The set of possible values of flag f at entry nodes of interrupts withpriority j from a set of values C at priority i, is given by:

Ci,j = filterj ◦ I(i+1,j−1) ◦ (initi C)

Accordingly, the set of all values of f possibly occurring at program pointu when reached by an interrupt with priority j, is given by:

R[[u, i, j] =⋃{R][u] c | c ∈ C(i,j)}

Consider a flag f with initial value set C0 and program points u andv which are reached by interrupts with priorities j and k, respectively. Todecide if there is a race at accesses to a variable x occurring at u and v firstthe values of f reaching u are computed by R[[u, j] = C. Then, starting withC and the priority P(u) of u, the set of values of f reaching v if execution isinterrupted immediately after the access at u is computed by R[[v,P(u), k].If this set is non-empty, there exists a path satisfying the conditions for adata race. Formally this yields:

Theorem 5.11. For accesses to a variable x at program points u and v wherev is reached by an interrupt with priority j > P(u) and the set of values offlag f reaching u given by C 6= ∅ the following holds:

(1) There is no race between the two accesses, if R[[v,P(u), j] = ∅.


(2) If R[[v,P(u), j] 6= ∅ there is a race path connecting u and v which isf -executable for some σ0 with σ0 f ∈ C0.

Before the proof of theorem 5.11, consider the following corollary to the-orems 5.9 and 5.10:

Corollary 5.12. For a program point u, a priority j and a flag f with initialvalue set C0 = {σ0 f} the following holds:

R[[u, j] = ∅ ⇐⇒ Π{f}(R[u], σ0) = ∅

I.e. if R[[u, j] = ∅ then there is no path which is f -executable for σ0 andreaches u by an interrupt with priority j.

Proof (Theorem 4.7). If R[[v,P(u), j] = ∅ then R][v] c = ∅ for all c ∈C(P(u),j). This corresponds to R[[v, j] = ∅ in the (sub-)program consistingonly of interrupts with priority greater than P(u). Therefore, corollary 5.12yields no f -executable path reaching v from u with the given value sets.Consequently, there can be no race path.

If, however, R[[v,P(u), j] 6= ∅ there exists a path π from u to v which con-tains only interrupts of priority greater than P(u) and which is f -executablefor initial state σ1 with σ1 f ∈ C. Therefore, every program point v1 occur-ring in π1 has a higher priority than u, i.e. P(v) > P(u). Since C 6= ∅ therealso exists an initial state σ2 and a path π2 reaching u that is f -executablefor σ2. With corollary 5.12 it can be assumed that (Jπ2K σ2 f = σ1 f . Thenπ2π1 is a f -executable race path since the lowest priority obtained in π1 isgreater than P(u) and the states match.

ut

For the running example from figure 5.1 the initial value set is {0} andthe analysis yields R[[Ix, 1] = {1} as well as R[[Qx, 1, 3] = ∅ since the onlyvalue that can pass through the guard edge to Qx is 0. The analysis presentedin this section is able to handle more complex patterns as well. For exampleconsider the extension in figure 5.3.

int f = 0;int x = 0;/∗ Priority 3 ∗/isr Q() {

if (f==0)x−−; /∗ Qx ∗/

}

/∗ Priority 2 ∗/isr R() {if (f==1){

f = 2;f = 1;}}

/∗ Priority 1 ∗/isr I () {

f = 1;x++; /∗ Ix ∗/f = 0;}

Fig. 5.3. Extended example code of program with a flag f.

The assignment f=2; in the new interrupt R adds 2 to the set of valuesQ can observe at Ix. This yields R[[I1, 1] = {1, 2}. But still R[[Qx, 1, 3] = ∅

5.7 Experimental Results 81

program loc time (s) warnings w/o flags warnings w flags

bad flag 21 0,008 1 1bad flag2 21 0,012 1 1example flag 18 0,012 1 0tested flag 27 0,024 1 0resource flag 26 0,020 1 0inverse flag 21 0,012 1 1weak flag 21 0,016 1 1arbiter flag 26 0,016 1 0

linecar 2586 0,072 5 0bipedrobot 2684 0,028 1 1ballsort 2786 0,424 7 0

controller ∼400k 3171 929 265

Table 5.1. Benchmark results.

certifying that there is no race between Ix and Qx. If, however, Q checked forf!=1; instead, which yields the same result for the program without R, theanalysis would yield R[[Qx, 1, 3] = {2}. The corresponding race path is givenby first interrupting Ix with R and then after f has been set to 2 interruptingR with Q.

5.7 Experimental Results

The analysis from section 5.4 has been implemented in the Goblint tool [58].For that, the analysis was extended with tracking of priorities and acquiredresources as described in chapter 4 as well as an inter-procedural treatmentof local variables and parameters and global invariants to deal approximatelywith global data different from flag variables. The implementation was testedon a number of valid and invalid uses of flags. The results are summarizedin table 5.1. Execution time (in seconds) on an Intel(R) Core(TM) i5 650running Ubuntu is listed in column 3. The last two columns indicate thenumbers of warnings by the analyzer without and with taking flag informationinto account. The race and warn columns exclude the considered flag.

Benchmark example flag and tested flag are the programs of figure 5.1and 5.3, respectively. The accesses to x are proven safe in both programs.Benchmark bad flag has an additional interrupt of intermediate prioritywhich (re)sets the flag to 0. Benchmark bad flag2 has an additional interruptof higher priority which (re)sets the flag to 0. In both cases, the analysiscorrectly recognizes the violation of property 2 and warn on the data race atx.

Benchmark inverse flag is benchmark example flag with flipped pri-orities. While syntactically the flag pattern is intact, the associated prioritiesrender it moot. The analysis captures this and issues a data race warning forx. Benchmark resource flag has an additional task of intermediate priority


which temporarily (re)sets the flag to 0, but employs resources to increasethe priority of I to the intermediate priority before using the flag. Due tothe raised priority, the value of f is reliable and the analysis verifies theaccesses to x as safe. Despite the access to f happening at different staticpriorities, the additional priority information allows the analysis to treat thispattern correctly. Benchmark weak flags employs the flag pattern correctly,but not thoroughly. There is an additional high priority interrupt, which alsoaccesses x. The analysis recognizes the flag pattern where it is used, but issuea data race warning due to the unprotected access. Benchmark arbiter flag

uses an extended synchronization scheme where the lowest priority interruptuses the value of the flag variable to signal which higher-priority interrupt isallowed to enter its critical section.

Additionally, the analysis has been evaluated on four larger programs.Benchmarks linecar, bipedrobot, and ballsort consist of about 300 to500 lines of application code plus about 2300 lines of headers taken fromthe NxtOSEK framework [16]. While benchmark bipedrobot is taken fromthe NxtOSEK samples [16], benchmarks linecar and ballsort have beenproduced in students’ projects. Interestingly, the students made use of flagvariables, without having been told to do so. Benchmark linecar is the con-trol program for a line following car which picks up items placed on the track.Two variables are used to synchronize between scanning for the line and for-ward movement. Benchmark bipedrobot is a two-wheel self balancing robotwhich uses a resource, i.e. dynamic priorities, to synchronize between balanc-ing and movement. The warning is due to an initialization task, which omitsacquiring the resource. It assumes that the timers have not yet triggered theremaining parts of the program. The code of benchmark ballsort resemblesa state machine controlling a manipulator arm, which first locates coloredballs in reach and then sorts them by placing red balls to the left and blueballs to the right. Additionally, it has a pause button, which stops all move-ment until it is pressed again. A race-analysis based on priorities alone wouldwarn on all shared variables. On the contrary, treating the state variable as aflag, allows to verify all accesses as safe. Finally, controller is an industrialbenchmark. It consists of about 400,000 lines of code including headers. Dur-ing the analysis 7232 global variables are found. The flag analysis reduces thenumber of race warnings from 929 to 265. This corresponds to a reductionby over 60%. The analysis on this real-world example takes about 3171s.

Overall, the analysis times, in particular for the larger programs, are ac-ceptable. Also the number of spurious data race warnings is dramaticallyreduced in the industrial benchmark controller. The remaining data racewarnings could possibly be reduced further, if additional information such as,e.g., worst-case execution time and cycle duration of time-triggered tasks istaken into account.

In addition to the analysis, an heuristic for the detection of potential flagshas been implemented. The heuristic works by searching for global variables

5.8 Related Work 83

that satisfy property 1 i.e. only have constants assigned. Furthermore, theyhave to occur in a guard since a variable that is never checked, can not act asa flag. While this heuristic found all flags used in the benchmarks presentedabove it also produced a lot of other candidates, in particular in the industrialbenchmark controller. In the small benchmarks these were temporary stor-age variables that were used to decide the further course of a computation.Unfortunately, it has so far not been possible to test the promising candi-dates, e.g. those variables ending in flag, from the controller benchmark.Many other have been discarded by the industrial partners as not typicallybeing constant. There is hope that future precision improvements to thegeneral analysis of this benchmark will also improve the quality of the flagcandidates.

5.8 Related Work

In general terms, the goal of this chapter was to exclude invalid paths fromdiluting the analysis result. Taking into account the control flow of proce-dure call and return, makes the analysis context-sensitive. Static analysisof concurrency errors requires context-sensitive alias analysis, and there arevarious solutions to obtain context-sensitive alias analysis for race detection,including approaches based on procedure summaries of relative locksets [59],bootstrapping of alias analyses [28], type based label-flow [44], and condi-tional must-not aliasing [39].

Distinguishing valid paths with respect to the sequential semantics of pro-gram execution is known as path-sensitivity. Path-sensitivity is required todeal, e.g., with conditional locking schemes. Voung et al. Voung et al. [59]identify this as one important source of false alarms in their analyzer. Ageneric approach to path-sensitivity is property simulation [13]. This tech-nique has previously been applied to achieve path-sensitive data race anal-ysis by Vojdani and Vene [58]. What is required here, however, is path-sensitivity with respect to the interleaving semantics of the program. It isnecessary to exclude semantically invalid interleavings, not merely invalidpaths in the flow-graphs. None of the static race detection tools presented in[28, 40, 43, 59] attempt to exclude semantically invalid interleavings basedon boolean guards. Also, tests with state-of-the-art dynamic race detectiontool, Intel Inspector XE 2013 (formerly Intel Thread Checker [49]), revealedthat boolean flags confuse the analysis such that no warnings are generatedat all even when negating the flag to make it invalid.

The seriousness of this issue becomes clear when attempting to adaptconventional race detection techniques to priority-driven single-processor con-currency systems. In this setting, locking can be avoided by higher prioritythreads because lower-priority threads cannot preempt them. Here, it wasexplored how boolean program variables can be used instead of explicit lock-ing. Another way to avoid acquiring resources in higher priority threads is to


merely check if the lock is free. If no other thread holds the lock, the highestpriority thread can simply execute the critical section. Mine [36] presents ascheduled interference semantics of ARINC 653 systems that takes this intoaccount by tracking a separate set of resources known to be free. A mutexis only known to be free when it has been explicitly probed by the highestpriority thread that uses it and there has been no blocking operations (e.g.,attempting to lock another mutex) since the mutex was last probed.

5.9 Conclusions

Application developers tend to rely not only on the synchronization mecha-nisms provided by embedded operating systems such as Autosar/OSEK tosecure their programs. Therefore, analysis methods for programs executedby Autosar/OSEK were provided which can deal with hand-crafted synchro-nization mechanisms based on flag variables. The analysis is based on anoff-the-shelf constant propagation analysis, together with post-processing totake care of the intricate inter-interrupt dependencies arising from the thepriority based scheduling of Autosar/OSEK programs. The presented charac-terization of flags allowed to precisely determine whether two accesses com-prise a data race or not. The construction still could be enhanced by usingmore sophisticated value analyses of flag variables, e.g., by allowing to storeand restore flag values or by tracking dependences between different flags. Itis possible to do the same construction for stronger value analyses in order torelax property 1. The preliminary experiments showed that already the sim-ple version of the analysis presented in section 5.4 significantly reduces thenumber of false alarms in real-world programs. It remains for future workto evaluate in how far stronger analyses will further impact the practicalprecision of the analysis.

6 Invariants and Privatization

The chapters 4 and 5 both provide information about possible or impossibleexecution paths, especially regarding whether a variable can be accessed con-currently or not. The goal of this chapter is to provide techniques that exploitthis information to produce more precise value information while conservingthe efficiency of the global invariant approach [52]. This is important since thepresence of interrupts in OSEK1[22] systems introduces such a huge amountof interleavings that even a call string 0 approach [55] quickly becomes pro-hibitively expensive. As a reference model, a constraint system for call string0 interval analyses of OSEK programs is given. Next two improvements of theglobal invariant approach are introduced and compared to the call string 0approach. The first technique used to improve the global invariants is calledprivatization. Privatization allows variable changes to be hidden from theglobal invariant under certain conditions. This technique does not rely onOSEK specific properties and has already been used by Kreiker et al. [33, 57]in the context of shape analysis. In general it can provide improved precisionto all global invariant based analyses. In the context of OSEK programs,however, the priority scheduling and the previously introduced analyses gen-erally allow the privatization of much more information than can be expectedin multi-threaded programs. Interval analysis is again used to illustrate thetechnique and to compare the results to the call string 0 approach.

For multi-threaded programs, Mine [36, 37] developed a similar approach.In principle every thread is analyzed separately and flow sensitively. Duringthis analysis so called influences are gathered which are then propagated toother threads and used to, e.g., relax the value ranges of global variables. Inessence the set of influences for a variable is equal to the privatized globalinvariant. But since the basic analysis approach is flow sensitive, self influenceproblems do not occur. The latest extension to the influences approach alsoallows to propagate some relational information.

The second technique presented here goes one step further by introduc-ing invariants for every priority level of the OSEK program. The idea hereis to make the layers of privacy explicit, i.e., only let values flow to tasksand interrupts that can observe them. In this sense it can be considered an


86 6 Invariants and Privatization

extension of privatization. The notion of observable values already occurredduring the flag analysis in chapter 5. For the layered invariants approach,it is crafted directly into the constraint system. This results in an analysisthat for the presented interval analysis on OSEK programs is as precise as acall string 0 analysis. The computational complexity of the layered system,however, is still in the order of the global invariant system.

6.1 Call String Analysis of OSEK Programs

The model used in this chapter consists of a single task T , with which pro-gram execution starts and a finite collection of interrupt routines Irpt. In thefollowing, task may also refer to interrupts; i.e., the set of all tasks Task isgiven by Task = Irpt ∪ {T}. Additionally, the program can contain auxiliaryprocedures Proc, which may be called by all tasks. The main task as well asthe interrupt routines are distinguished procedures which can occur at anytime but may not be called otherwise. Therefore, the set of all proceduresProc contains all tasks. For the sake of the analysis, procedures are specifiedby means of control-flow graphs as in figure 6.1.

Every procedure f has a designated entry node fe and return node fr.The collection of all control flow graphs of procedures in Proc is denoted by(N,E) where N is the set of nodes and E the set of edges. Let Ne and Nrdenote the set of all entry and return nodes, respectively.

Each edge is labeled either with a basic statement s or with a callf(), f ∈ Proc \ Task. For simplicity, only procedures without parameters areconsidered. Each basic statement s is either a basic command cmd, such as anassignment to a global variable, or the acquiring (get(r)) or releasing (rel(r))of a resource.

The program in figure 6.1 consists of the initialization task T and theinterrupts I and I ′, which implement a small producer-consumer pattern.Note that the counting variable x is incremented and decremented withoutchecking its value. Afterwards it is set to 0 if it left the desired range. While itmight seem contrived, this form of error checking was discovered in industrialexamples. The additional interrupt I ′′ and the last statement of T have beenadded to highlight the challenges the different analysis techniques have todeal with. This program will serve as the running example throughout thischapter.

In order to incorporate the priority information present in OSEK pro-grams into the model, it is assumed that the functions Ps,Pd : N → N mapnodes to their static and dynamic priority, respectively. In figure 6.1 the staticpriority is shown by the number left of the starting arrows, while the dynamicpriority is written below each node. How to compute such functions has beendescribed in chapter 4. While an interrupt can occur at any time, it will onlypreempt the running task if its static priority is higher than the dynamic pri-ority of the running task. Otherwise, it will wait until the dynamic priority of

6.1 Call String Analysis of OSEK Programs 87

4 4 4 4

3 3 3 3 3 3

2 3 3 3 3 2

1 4 4 4 1 1

I ′′e44 I ′′1 I ′′2 I ′′r

I ′e33 I ′1 I ′2 I ′3 I ′4 Ir

Ie22 I1 I2 I3 I4 Ir

Te11 T1 T2 T3 T4 Tr


get(r) x-- x<0? x=0

x=>0?

rel(r)

get(r) x++ x>8? x=0

x<=8?

rel(r)

get(r′) x=0 z=0 rel(r′) z=1


the running task drops low enough before executing. On the other hand, anypoint that allows a waiting interrupt to execute would also allow this inter-rupt to preempt if it just occurred. For the program, it is indistinguishablewhether the interrupt was waiting or just occurred. Therefore, interrupts areonly allowed to occur in the model if they can directly preempt the runningtask. This yields the following condition:

An interrupt q ∈ Irpt may occur at a node u ∈ N⇐⇒

Ps(qe) > Pd(u)

Entry nodes, however, may never be interrupted. Except for the very firstoccurence of the entry node of T it is again indistinguishable if an interruptoccurs at an entry node or at the return node of the previously preemptedtask. Similarly, for procedures there is no difference if an interrupt occurs atthe call site or at the entry node. Therefore, excluding interrupts at entrynodes is a sensible restriction. In addition to avoiding unnecessary interleav-ings, this allows for an uninterrupted initialization part in the main-task.

Procedures may be called in contexts with different priorities. For eachpriority at which a procedure is called, a separate copy of the correspondingcontrol flow graph is introduced where each node is additionally indexedwith the static and dynamic priority of the call site. This allows more precisepriority information at the nodes inside the procedure and some context-sensitivity.

Taking the classical approach to abstract interval analysis: the domain isgiven by (Z×Z) ·∪{>,⊥}, the least upper bound operator t is defined by theminimum and maximum on the lower bound and upper bound, respectively.


Transfer functions rely on the usual interval arithmetics:

(a1, a2) •] (b1, b2) = (min(a1 • b1, a1 • b2, a2 • b1, a2 • b2),

max(a1 • b1, a1 • b2, a2 • b1, a2 • b2))

Here • can represent addition, subtraction and multiplication. For > and⊥ values, the usual extensions apply:

(a1, a2) t ⊥ = ⊥(a1, a2) t > = >

> t ⊥ = >(a1, a2) •] > = >(a1, a2) •] ⊥ = ⊥

A state σ : X → (Z × Z) ·∪{>,⊥} is a mapping from the finite set ofvariables X to abstract intervals. The auxiliary functions σ1, σ2 yield thelower and upper bound of an interval, respectively. The semantics for edgeswith basic statements is then given by:

J(u, x = y, v)K(σ) = σ[x 7→ σ(y)]

J(u, x = y • z, v)K(σ) = σ[x 7→ σ(y) •] σ(z)]

J(u, x <= y ?, v)K(σ) =

{σ if σ(x) = > or σ(y) = > or σ2(x) ≤ σ1(y)

⊥ if σ(x) = ⊥ or σ(y) = ⊥ or σ2(x) > σ1(y)

J(u, get(r), v)K(σ) = σ

J(u, rel(r), v)K(σ) = σ

The interval semantics presented here suffices to precisely deal with theexample program in figure 6.1 and to illustrate the differences between thecall string 0 approach and the later global invariant approach. For a practicalanalysis of intervals, a more precise treatment of guards is necessary. Thevalues flowing into a branch should be intersected with the interval definedby the branch condition. A detailed discussion of this technique can be foundin, e.g., [53].

Values of variables not used inside a procedure may flow through it andmassively reduce precision at the return points. This is especially severe withthe presence of interrupts since they can occur virtually everywhere. To avoidthis situation, a function Acc : N → X is required, that, for a program point,determines the set of variables the corresponding procedure can access. Thisis a slight extension to conventional enter andcombine operators which takeprocedure names as their first argument. The later invariant based systemsrequire this extension since the invariant values are applied to different pro-gram points. The following call string 0 constraint system only uses enterand return nodes and would work equally well with just the procedure name.To avoid several versions of enter and combine the extension is introduced

6.1 Call String Analysis of OSEK Programs 89

here already. Consider for example the following results for the program infigure 6.1: Acc(T2) = {x, z}; Acc(Ie) = {x}; Acc(I ′′r ) = {z}. For simplicity,read and write accesses are not distinguished. In practice, only variables thatare read need to enter a procedure or interrupt, and only variables that havebeen written are combined back into the caller state or preempted state.

Here the enter and combine operators are used to filter out variableswhich are neither read nor written:

enter(u, σ) = σ[x 7→ ⊥|∀x /∈ Acc(u)]

combine(u, σ, σ′) = σ′[x 7→ σ(x)|∀x /∈ Acc(u)]

Let σ0 denote the mapping which maps all variables to ⊥. The flow-sensitive callstring-insensitive semantics of an OSEK program is then givenas the least solution of the following constraint system:

[CS0] C[Te] w σ0

[CS1] C[v] w Ju, s, vKC[u] (u, s, v) ∈ E[CS2] C[fei,j ] w enter(fe,C[u]) (u, f(), v) ∈ E,

i = Ps(u), j = Pd(u)

[CS3] C[v] w combine(fe,C[u],C[fri,j ]) (u, f(), v) ∈ E,i = Ps(u), j = Pd(u)

[CS4] C[qe] w enter(qe,C[u]) q ∈ Irpt, u /∈ Ne,Ps(qe) > Pd(u)

[CS5] C[u] w combine(qr,C[u],C[qr]) q ∈ Irpt, u /∈ Ne,Ps(qr) > Pd(u)

The constraints [CS0] to [CS3] are derived from the edges of the control-flow graph. The constraints [CS4] and [CS5], however, do not have a corre-sponding edge in the control-flow graph. They are based solely on the priorityof nodes. [CS4] gathers information from all nodes where the dynamic prior-ity is low enough for the interrupt to occur while [CS5] constrains every nodeby the return values of all interrupts that could have preempted the programat that point.

Solving the constraint system [CS] yields the following results for theexample program in figure 6.1:

Node Te T3 T4 Tr Ie I2 Ir I ′e I ′2 I ′r I ′′e I ′′rx ⊥ (0, 0) (0, 8) (0, 8) (0, 8) (1, 9) (0, 8) (0, 8) (−1, 7) (0, 7) ⊥ ⊥z ⊥ (0, 0) (0, 0) (0, 1) ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ (0, 1) (0, 0)

First note that since interrupts can not occur at entry nodes, T can safelyset both variables to 0, but as soon as the priority drops at T4, the valueof x takes the full interval (0, 8). The variable z retains its value at T4 sinceI ′′ (re)sets it to its initial value. Although interrupt I ′′ may occur both at


T4 and Tr, the less precise information read from Tr is overwritten beforereturning to T4. The other interrupts have no effect on z. Also, note that thetemporary bound violations of x at I2 and I ′2 are contained in a section ofhigh priority and therefore not visible to the rest of the program. While I ′′

may occur inside this section, the values of x are hidden from I ′′ becausex /∈ Acc(I ′′e ). At the return points the damage is already repaired and noprecision is lost.

It is also interesting to see to what extent priority sensitivity and thefiltering of unaccessed variables influence the precision of the analysis. If thepriority conditions are removed from [CS4] and [CS5], I and I ′ can interrupteach other at any given program point, which makes both the value 9 at I2and the value −1 at I ′2 visible at the entry nodes. This leads to a completeloss of information about x throughout the whole program.

Similarly, if I ′′ is allowed to see all variables, all program points at whichI ′′ can occur would be joined. Since these are all but the nodes in I ′′ itself andthe initialization part, again all information about x is lost. This behavior isclose to what a naive global invariant approach would achieve. In the nextsection, it is shown that global invariants can do much better.

6.2 Global Invariants with Privatization

In the previous section it was shown that a flow sensitive approach whichexplicitly computes all interleavings yields precise results for the values ofvariables. In practice it is important to quickly reach a fixpoint. The Goblintanalyzer uses global invariants to summarize concurrent effects. This allowsvery efficient computation of fixpoints. However, the precision of the globalinvariant is not satisfactory since all flow information is lost and every poten-tial interleaving is considered possible. This is especially disappointing sincethe priority and flag information computed in chapters 4 and 5 provides in-formation about mutually exclusive program sections. It is now shown howa global invariant approach can utilize this information to compute valueranges, that are competitive compared to the precision of the call string 0approach.

In the following, the same domains and semantics as in the previous sec-tion will be used. The intra-task constraints remain the same, however, in-stead of allowing interrupts to possibly occur at each program point, theconstraint system contains a global invariant Ψ . The value of Ψ is a statethat summarizes the values of global variables over the whole program exe-cution. Thus, instead of the constraints for interrupts in [CS], the followingconstraint system [GI] computes Ψ and then constrains every program pointby Ψ . This alone would be very imprecise, so the constraint system uses atechnique called privatization to limit the flow of information from and tothe global invariant. A privatized variable will act as a local variable and not

6.2 Global Invariants with Privatization 91

make its changes visible to the global invariant, as long as it remains priva-tized. Generally, a variable is privatized if it cannot be accessed concurrently.

Here precomputed priority information will be used to decide which vari-ables are privatized. Recall from chapter 4 the notion of the priority of avariable. With acc(x) denoting any basic statement reading or writing thevariable x, the function P : X → N is defined as follows:

P(x) = max{Ps(u)|(u, acc(x), v) ∈ E}

This means that P(x) is the greatest static priority of any task or interruptthat accesses x. One could consider it the ceiling priority of the variable x.If the dynamic priority of a program point at the start of an edge accessinga variable x is at least P(x), then the execution can not be preempted byother tasks that also access x. The synchronization function sync then takesas input a priority and a state σ and returns the state where all variablesthat cannot be accessed concurrently are set to ⊥. In the following definitioni denotes the priority of the considered program point.

sync(i, σ) = σ[x 7→ ⊥ | P(x) ≤ i]

The constraint system for global invariants with privatization is then givenby:

[GI0] G[Te] w σ0

[GI1] G[v] w Ju, s, vKG[u] (u, s, v) ∈ E[GI2] G[fei,j ] w enter(fe,G[u]) (u, f(), v) ∈ E,


[GI3] G[v] w combine(fe,G[u],G[fri,j ]) (u, f(), v) ∈ E,i = Ps(u), j = Pd(u)

[GI4] G[qe] w enter(qe, Ψ) q ∈ Irpt

[GI5] G[u] w enter(u, sync(Pd(u), Ψ)) u /∈ Ne[GI6] Ψ w combine(qr, Ψ,G[qr]) q ∈ Irpt

[GI7] Ψ w combine(u, Ψ, sync(Pd(u),G[u])) u /∈ Ne

What sync introduces are validity conditions for considered paths. Forexample, the priority condition in sync corresponds to the condition of [CS4]when an interrupt can occur. Note that interrupt entry nodes and return donot use sync. To see the need for this, consider a variable that is only ac-cessed by two different interrupts with the same static priority. These taskshave exclusive access to the variable and the sync constraint will not prop-agate updates to this variable to the global invariant. Nevertheless, theseinterrupts may occur one after another, in any order, and this is taken careof by the special constraints for entry and return nodes. The functions enter


and combine are again used to filter out unused variables. As an alternativeto the invariant constraints [GI6] and [GI7], a side-effecting constraint system[1] could be used. This approach is used in the implementation of the Goblintanalyzer.

Solving the constraint system [GI] yields the following results for theexample program in figure 6.1:

Node Ψ Te T3 T4 Ie I2 Ir I ′e I ′2 I ′r I ′′e I ′′rx (0, 8) ⊥ (0, 0) (0, 8) (0, 8) (1, 9) (0, 8) (0, 8) (−1, 7) (0, 7) ⊥ ⊥z (0, 1) ⊥ (0, 0) (0, 1) ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ (0, 1) (0, 0)

Compared to the results of the call string 0 system the only difference isin node T4 where the call string 0 system computes the exact value (0, 0).The global invariant system, however, has to use the full invariant since zis not accessed exclusively at T4. This is a typical situation. With the flowinsensitive global invariant approach the information from the end of a taskflows back to all program points of the task not just to its entry node. On theother hand the call string 0 approach has to evaluate every interrupt at everypossible program point. The global invariant system instead summarizes allnodes into the global invariant and then just applies the single invariant toall nodes.

Both systems safely over approximate the concrete program executions.As was seen from the example program, the call string 0 solution is stillgenerally more precise than the global invariant with privatization.

Theorem 6.1. For every program point the least solution of [CS] is smallerthan the least solution of [GI].

Proof. Let G[u]∗ and C[u]∗ denote the least solution of the [GI] and [LI]constraint system, respectively. By induction on the evaluation of constraintsit is shown that G[u]∗ A C[u]∗. As the constraints [CS0] to [CS3] are identicalto the constraints [GI0] to [GI3], it is only shown that the evaluation of theremaining constraints do retain the inequality.

Case [CS4]: The comparison is done variable by variable. Since the enterfunctions in [CS4] and [GI4] are the same, there is nothing to prove forvariables x /∈ Acc(qe). Furthermore, if x /∈ Acc(u), then C[u]∗(x) = ⊥,since the entry node leading to u would not access x either and thereforethe function enter would filter it out. Since x is not accessed, the ⊥ valueremains unchanged until reaching u and is trivially over-approximated byΨ . If x ∈ Acc(qe) ∩ Acc(u) the enter and combine functions do nothingand it remains to prove, that sync does not filter C[u]∗ if q can occur atu, i.e., Ps(qe) > Pd(u). Since x ∈ Acc(qe), it follows that P(x) ≥ Ps(qe)and consequently that P(x) > Pd(u). Therefore, the condition in sync isnot satisfied for x and it is not set to ⊥, concluding the proof.

6.2 Global Invariants with Privatization 93

Case [CS5]: This is analogous to the previous case, except the key inequalityto establish is Ψ w C[qr]

∗. But with G[qr]∗ w C[qr]

∗, this is ensured by[GI6] since the same combine as in [CS5] is used.

ut

6.2.1 Privatization with Flags

So far only priority information has been considered by sync. In order to alsouse flag information, the flag information would have to be processed to yielda set of (un)safe variables. Consider for example the program in figure 6.2.

3 3 3

2 2 2 2 2

Qe Q1 Qr

Ie I1 I2 I3 Ir

f==0? x=-x

f!=0?

f=1 x++ x-- f=0

Fig. 6.2. Example program with flag privatization.

Here priority information cannot guarantee that x is accessed exclusivelyat I2. The flag analysis from chapter 5 however can exclude a data race at x.Let F : N → 2X denote the function that for every program point returnsthe set of variables that can be accessed exclusively according to the flaginformation. Then a synchronization function using both priority and flaginformation could be defined as follows:

sync′((s, i), σ) = σ[x 7→ ⊥ | x ∈ s ∨ P(x) ≤ i]

In the constraint system, sync′ would be called with F(u) and Pd(u) asinput, i.e., sync′(F(u),Pd(u), Ψ).

For the example program in figure 6.2 F(u) is {x} for u ∈ {Q1, I1, I2.I3}and empty otherwise. Replacing sync in [GI] by sync′ and assuming thatx = 0 at the beginning would then yield the following result:

Node Ψ Ie I1 I2 I3 Ir Qe Q1 Qrx (0, 0) (0, 0) (0, 0) (1, 1) (0, 0) (0, 0) (0, 0) (0, 0) (0, 0)

Without privatization the statements x++ and x-- would result in x beingmapped to > everywhere.


The concept of privatization for global invariants is not limited to OSEKprograms or precomputed information. In the following subsection it will beshown how a general privatization framework could work, using informationcomputed during the analysis.

6.2.2 General Privatization

For privatization to work the sync function only requires some form of infor-mation that guarantees exclusive access to a variable. Flags and priorities inOSEK programs have been discussed above. Common lock-sets in a threadmodel would be another example. The effect is then that as long as a variableis privatized, it may locally violate the global invariant. If this violation isrepaired before the variable leaves the private section, the global invariantdoes not lose precision.

A general synchronization function is a projection, which sets all vari-ables which satisfy a condition based on the first parameter to bottom. Ifthis parameter is taken from the analysis domain, this component of the do-main is called privatization information. In case synchronization informationis computed simultaneously with the values, the synchronization function isnot necessarily monotonic. This could cause the fixpoint computation to fail.Therefore, synchronization functions are required which privatize less vari-ables, the more privatization information is present. E.g. all variables areprivatized until the analysis finds concurrent accesses which can not be mu-tually excluded. In this case, monotonicity can be assured.

Theorem 6.2. Let Dp denote the privatization component and Dv the valuecomponent of the domain D = Dp ×Dv. Then a privatization function sync :Dp × D → D is monotone if sync is monotone in its first parameter. Thismeans for p1, p2 ∈ Dp and d ∈ D the following holds:

p1 vp p2 =⇒ sync(p1, d) v sync(p2, d)

Proof. If d1, d2 ∈ D with d1 v d2 it follows that for each variable x thesame relation holds for the values, i.e., d1(x) vv d2(x). Since for a fixed firstparameter sync projects out the same variables of the second parameter themonotonicity for a fixed first parameter follows directly from the ordering ofthe second parameter. I.e. for a fixed p ∈ Dp and d1, d2 ∈ D the followingholds d1 v d2 =⇒ sync(p, d1) v sync(p, d2).

Now for variable privatization information, p1 vp p2 ∈ Dp it remains toshow, that sync(p1, d1) v sync(p2, d2). By monotonicity in the first parame-ter, p1 can be replaced by p2. Then the result follows from monotonicity fora fixed first parameter.

sync(p1, d1) v sync(p2, d1) v sync(p2, d2)ut

6.3 Layered Invariants 95

Therefore if a global invariant constraint system terminates without pri-vatization, and the condition in theorem 6.2 holds, it will also terminate whenusing privatization. This makes privatization a useful technique for all analy-ses that deal with potentially concurrent accesses and the corresponding lossof precision. In the Goblint analyzer, instances of privatization have alreadybeen used with great success for a wide range of analyses [1, 33, 57].

6.3 Layered Invariants

Global invariants with privatization are a very potent technique for analyzingOSEK programs. They provide good precision and fast computation time.But, as demonstrated by the application to the example program in figure 6.1,the call string 0 approach is still more precise. This section will present aninvariant based approach that, when only priority information is considered,achieves the same precision as the call string 0 approach while still utilizingsummarization to keep the amount constraints influencing a program pointlow. The main source of imprecision for the global invariants approach isthat tasks are allowed to interfere with themselves. In the example programin figure 6.1, the assignment z = 1 at the end of T influences the invariant,which is used at T3. But if the computation had started at the entry of Tit would reach T3 with z = 0. An idea to solve this is to split the globalinvariant into several priority dependent invariants (Ψj). This, however, doesnot suffice. It is also necessary to separately track the invariants which flowto entry nodes (Φi). Otherwise imprecise information is propagated to higherpriority layer invariants which then again influence the internal nodes. Thelayout of the information flow between the program points and the layerinvariants is sketched in figure 6.3.

33

22

11

Φ1

Φ2

Ψ2

Ψ3

Fig. 6.3. Example of information with layered invariants.

The key insights behind this approach are similar to the ideas used inchapter 5 to track observable values for the precise analysis of flags. First,


what is observable by an interrupt of (static) priority i is also observable byall higher priority interrupts. Conversely, interrupts that influence a node of(dynamic) priority j also influence all nodes of lower priority. On the otherhand, some values a variable can take can not be observed by interrupts ofthe same priority. The value can, to some extend, be kept private. It will laterbe shown that the layered invariants subsume the priority based privatizationapproach.

Formally the same domain and semantics as before are used. The layeredinvariants approach is then given by the following constraint system:

[LI0] L[te] w ⊥[LI1] L[v] w Ju, s, vKL[u] (u, s, v) ∈ E[LI2] L[fei,j ] w enter(fe,L[u]) (u, f(), v) ∈ E,


[LI3] L[v] w combine(fe,L[u],L[fri,j ]) (u, f(), v) ∈ E,i = Ps(u), j = Pd(u)

[LI4] L[qe] w enter(qe, Φi) q ∈ Irpt,Ps(qe)− 1 = i

[LI5] L[u] w enter(u, Ψi) u /∈ Ne,Pd(u) + 1 = i

[LI6] Ψi w combine(qr, Ψi,L[qr]) q ∈ Irpt,Ps(qe) = i

[LI7] Φi w combine(u, Φi,L[u]) u /∈ Ne,Pd(u) = i

[LI8] Ψi w Ψj i < j

[LI9] Φi w Φj i > j

The same filtering of unaccessed variables is used as in [CS] and [GI].Compared to [GI] the effect of sync and the computation of the priority ofvariables now implicitly takes place in the constraint conditions.

Solving the constraint system [LI] for the example program in figure 6.1yields the following invariants:

Φ1 Φ2 Φ3 Ψ1 Ψ2 Ψ3

x (0, 8) (0, 8) (−1, 9) (0, 8) (0, 8) (0, 7)z (0, 1) (0, 1) (0, 1) (0, 0) (0, 0) (0, 0)

The results for program points are identical to the results obtained bysolving [CS].

The following theorems will prove that [LI] is indeed as precise as thecall string 0 approach. The first compares the layered invariants to the singleglobal invariant system.

Theorem 6.3. For every program point the least solution of [LI], is smallerthan or equal to the least solution of [GI].

Proof. Let G[u]∗ and L[u]∗ denote the least solution of the [GI] and [LI]constraint system, respectively. By induction on the evaluation of constraints

6.3 Layered Invariants 97

it is shown that G[u]∗ A L[u]∗. As the constraints [LI0] to [LI3] are identicalto the constraints [GI0] to [GI3], it is only shown that the evaluation of theconstraints [LI4] and [GI4], as well as [LI5] and [GI5], does retain the ordering.

Case [LI4]: Comparing the constraints [LI4] and [GI4] yields that it has tobe shown that Ψ w ΦPs(qe)−1, since the enter and combine functions areidentical.Combining [LI7] and [LI9] with the inductive assumption, Φi can berewritten as follows:

Φi =⊔

u/∈Ne,Pd(u)≤i

L[u]∗ =⊔

u/∈Ne,Pd(u)≤i

G[u]∗

Together with [LI4] and i = Ps(qe)− 1 this yields:

ΦPs(qe)−1 =⊔

u/∈Ne,Pd(u)≤Ps(qe)−1

G[u]∗

=⊔u/∈Ne

G[u]∗[x→ ⊥|¬(Pd(u) ≤ Ps(qe)− 1)]

(6.1)

Conversely looking at the global invariant yields with [GI7]:

Ψ v⊔u/∈Ne

sync(Pd(u),G[u]∗)

=⊔u/∈Ne

G[u]∗[x→ ⊥|P(x) ≤ Pd(u)]

=⊔u/∈Ne

G[u]∗[x→ ⊥|¬(P(x) > Pd(u))] (6.2)

Comparing these two formulae variable by variable implies that if a vari-able x is mapped to ⊥ in (6.1) the desired inequality holds trivially.Otherwise, it remains to prove that x is not set to ⊥ in (6.2) either. From(6.1) it follows that Pd(u) ≤ Ps(qe) − 1 and from [LI4] it can also beassumed that x ∈ Acc(qe) which, with the definition of P(x), yields:

P(x) ≥ Ps(qe) > Ps(qe)− 1 ≥ Pd(u)

Therefore, the condition in (6.2) is not satisfied and x is not set to ⊥.Case [LI5]: It has to be shown that sync(Pd(u), Ψ) w ΨPd(u)+1 for all u /∈ Ne.

First note that if a variable is not accessed by an interrupt q, this variablewill not contribute to ΨPs(qe) via qr due to the combine function.Together with [LI6] and [GI6], it then follows that for all i the followingequation holds:


Ψ =⊔j

Ψj w Ψi

Again comparing variable by variable, it has to be shown that sync has noeffect on this inequality. If sync maps a variable x to ⊥ because P(x) ≤Pd(u), the definition of P(x) implies that @q ∈ Irpt with Ps(qe) > Pd(u)s.t. x ∈ Acc(qe). However, for an interrupt q to contribute to ΨPd(u)+1

it is necessary that Ps(qe) = Pd(u) + 1 > Pd(u). Therefore, it followsthat ΨPd(u)+1(x) = ⊥. In the other case, it would have to hold thatx /∈ Acc(qe) for all interrupts. Otherwise the interrupt accessing x would,by induction, contribute equally to Ψ and ΨPd(u)+1. If, however, x is neveraccessed by an interrupt then x = ⊥ anyway.

ut

Theorem 6.3 compares the layered invariants to the global invariant andshows that the layered invariants are more precise. When comparing thecomputational complexity, the layered invariants approach has to computelinearly (in the number of priorities) many more summaries. Otherwise, theconstraints systems are equivalent in terms of necessary computations. Thisimplies that while more expensive than the global invariants approach, thelayered invariants approach is cheaper than the call string 0 approach. Thefollowing theorem will now show that the layered invariants approach stillobtains the same results.

Theorem 6.4. For all program points the least solution of [CS] is equivalentto the least solution of [LI].

Proof. Let L[u]∗ and C[u]∗ denote the least solution of the [LI] and [CS]constraint system, respectively. First it will be shown by induction on theevaluation of constraints that G[u]∗ A L[u]∗. Since the constraints [LI0] to[LI3] are identical to the constraints [CS0] to [CS3], it remains to be shownthat the evaluation of [CS4] and [CS5] and the corresponding constraints in[LI] retain the equation.

Case [LI4]: Since the enter function is identical in both constraints it remainsto be shown that the following holds:⊔

Ps(qe)>Pd(u)

C[u]∗ w ΦPs(qe)−1

Since [LI7] and [LI8] imply that only program points u with Ps(qe)−1 ≥Pd(u) contribute to ΦPs(qe)−1, this is guaranteed.

Case [LI5]: As in theorem 6.3, the enter and combine functions would onlyinfluence the result if a variable is not accessed by any interrupt. There-fore it remains to show that the following holds:⊔

Ps(qr)>Pd(u)

C[qr]∗ w ΨPd(u)+1

6.4 Conclusions 99

Here [LI6] and [LI9] imply that Ps(qr) ≥ Pd(u) + 1, which is equivalentto the condition in [CS5] Ps(qr) > Pd(u).

The other direction is completely analogous since the arguments used aboveare symmetrical.

ut

This shows that for OSEK programs it is possible to decide preciselywhich information can be summarized without loss of precision.

6.4 Conclusions

It was shown that the information provided by priority, resource, and flaganalysis can be used to fine tune the global invariant approach to obtainmore precise results with only a minor overhead. In fact, a general methodwas provided that allows the usage of information that can exclude certainexecution paths or variable accesses in such a way. This recovers some ofthe precision of the call string 0 approach that global invariants based anal-yses sacrificed for summarization and fast fixpoint computation. The workof Mine [37], on the other hand, starts with a call string 0 approach andgathers influences which are then propagated to all other procedures, addingsome summarization to call string 0 based analysis. It appears likely thatboth approaches can be adjusted to cover the whole spectrum between fastcomputation and precise results. For OSEK programs the layered invariantsapproach presented in section 6.3 represents a perfect compromise betweenthe two approaches.

7 Benchmark Generation

Finding decent benchmarks for the presented techniques has been a surpris-ingly challenging task. Virtually no freeware project exist that utilize anOSEK operating system. The cooperating industrial partners have been verysupportive, but due to confidentiality reasons have been unable to providefull access to their source code. Having benchmarks run by a third party isnot satisfactory since adjustments take a lot of time and in case of errorsit is difficult to extract the cause. As was hinted at before, there exists animplementation of OSEK for the Lego R© Mindstorms R© platform [16]. Thisimplementation comes with several small feature test programs and an im-plementation of a self balancing two wheel robot. These programs were thestart of the benchmark suit. The Lego platform also attracted students whichallowed to introduce several new people to OSEK. Below, three successfulstudent projects are presented. It turns out that many of the more obscuretechniques encountered in industrial code also come naturally to people start-ing to write OSEK programs.

7.1 Robotic Arm

The first student project was centered around a robotic arm. The roboticarm was constructed to be able to rotate on a fixed mount and move up anddown. It ended in a claw that was able to grasp balls. The balls were laidout on the reachable circle of the robotic arm. The starting orientation of thearm defined the left and right halves of the circle. The goal was then to havethe robot collect all blue balls on its right side and all red balls on its leftside. A picture of the finished robotic arm is shown in figure 7.1.

The student was limited to the conformance classes BCC1 and BCC2and was told not to rely on timing for synchronization. Otherwise he wasfree to design and implement the program as he saw fit. The resulting pro-gram resembled a state machine which first searched for positions of balls onthe circle, then scanned their color and finally moved them to their respec-tive halves of the circle. A fairly large amount of error correction had to beincluded since both the used motors and sensors delivered varying results.For example, the color scanning of a ball was done 10 times while count-ing whether the resulting sensor data indicated a blue, red or unknown ball.

102 7 Benchmark Generation

Fig. 7.1. Lego model of the robotic arm.

Finally the result with the most votes was considered correct. Similarly thesteering to previously discovered ball positions had to monitor when the ballwas actually found and adjust the movement accordingly.

Since the task was very well structured it was not surprising that thestudent did not opt for resources to coordinate his program tasks. Insteadhe relied on the static priorities and global variables denoting the state ofthe program. These variables closely resembled the flag patterns employedin the industrial benchmarks. However, since every state was represented bya separate variable the flags depended on each other and this pattern wasnot supported by the framework described in chapter 5 and implementedin the Goblint analyzer. Manually condensing these several variables into asingle one with several values the analyzer was able to verify that the shareddata structures containing the ball positions and colors were indeed safelysynchronized between the program tasks.

In order to create more complex interactions and potential data conflicts,the program was extended by an emergency shutdown and resume button anda reaction to a sound sensor. The reaction to the sound sensor was designedto take precedence over the sorting but would cause gripped balls to bedropped. Therefore the sorting would have to protect itself against the soundreaction while a ball was moved. On the other hand, the shutdown wouldstop all movement immediately regardless of whether a ball was picked upor not. This extension lead to the introduction of resources into the program

7.2 Line Following Car 103

that secure the state variables. The resources however just secure the statevariables. Considering just priorities and resources it could not be guaranteedthat the arm never drops a ball when reacting to the sound sensor. Similarly,removing the resources would leave the state variable vulnerable. Combiningboth analysis enabled the tool to verify that the implemented sound sensorreaction is safe.

7.2 Line Following Car

The second student project was centered around a line following car. The carwas constructed with two big wheels that could be controlled separately, anda small support wheel in the back. This allowed for a very agile car, that couldturn around in a very small space. Additionally, the car had a forklift-likeappendage. With this appendage it was able to pick up a parcel in front ofthe car. The goal was to have the car autonomously drive along a grid of linessearching for the parcel and pick it up. The car had to follow the grid lineseven across intersections, unless it received external input through a soundsensor, in which case it would turn on the next intersection. A picture of thefinished car is shown in figure 7.2.

Fig. 7.2. Lego model of the line follower.

As before, the student was limited to the conformance classes BCC1 andBCC2 and was told to not rely on timing for synchronization. In addition tothe imprecision of the sensors and motors discussed previously, the slip in-troduced by the wheels turned the construction and programming of this carinto a task a lot less simple than expected. A program task was introduced


with the sole purpose of correcting the motor speeds of the wheel motors tokeep the car going in a roughly straight line. Another surprising difficultywas that if sensor data was read very frequently, it often produced spuriousresults. Furthermore, it also caused the feature related tasks of the programto progress very slowly since they were constantly preempted by sensor up-dating. On the other hand, a low rate of sensor updates would cause theprogram to miss an intersection or the parcel. The most challenging case waswhen the car encountered an intersection while it attempted to pick up theparcel.

This student did not choose flags as his means of synchronization. Insteadhe relied heavily on resources and often the first statement of a task wasthe acquisition of a resource that was held almost till termination. This, inessence, lifted the whole task to a higher priority, but without allowing itto preempt more tasks. While he also recorded the state of the robot inglobal variables that agreed with the flag patterns analyzed by Goblint, theywere not necessary to ensure safe memory accesses. For the benchmarks inchapter 5, an earlier version was used that still relied on the flags.

7.3 Obstacle Avoiding Car

The third student project was a continuation of the second project in thesense that it also used a autonomous car as the basis. But since the amountof sensors and motors available on the platform is limited, the line followingfeature was dropped in favor of obstacle avoidance. The model consequentlyresembles the previous one but had the fork lift replaced by a telescope pole.A picture of the modified car is shown in figure 7.3.

Fig. 7.3. Lego model of the obstacle avoider.

7.4 Conclusion 105

The goal was to have the car move around an enclosed area withoutcolliding with the boundary. Additionally, the area contained tunnels throughwhich the robot could only pass with the telescope pole retracted. Uponreceiving an acoustic signal the car would rotate. The conflict between thesetasks arises from the fact that the car would collide with the walls whenturning in a tunnel or in the opposite direction of the general avoidance.Furthermore, the retracted pole interfered with the general obstacle avoidancealgorithm.

The previous limitation to conformance classes BCC1 and BCC2 applieshere, as well as the precision issues with sensor measurements and wheel slip.Additionally a delay was introduced to the processing of the sound sensorinput. Otherwise, a prolonged acoustic signal would cause the car to restartthe rotation multiple times.

The student chose a very fine grained implementation approach whereevery movement task and the processing of every sensor was assigned to aseparate OSEK task. Consequently, there was a lot of shared memory com-munication between the tasks. While this seems error prone at first, it alsoallowed to pinpoint the priority at which each task should operate. Similarly,each remaining critical section is protected by a separate resource. Addition-ally, the program state was encoded in many different state variable whichwere used to control the flow of the program. Combining these approachesallowed for a very precise handling of synchronization and yielded a fairlycomplex OSEK program with nine tasks and eight resources. The state vari-ables strongly interact and in one instance are even wrapped into a functionputting them beyond the reach of the implemented flag analysis. Goblint is,however, able to verify that his use of resources is sound and protects all butone global variable from data races. This variable is indeed accessible fromcompeting tasks without resource protection. Only with intimate knowledgeof the control structure, which is distributed over several global variables andpartially wrapped in functions, is it possible to conclude that these tasks cannot access this variable concurrently. As a side note, the student reportedthat during development there was occasional strange behavior in the tasksaccessing this variable. A version of the code exhibiting this behavior couldunfortunately not be retrieved for analysis.

7.4 Conclusion

It is surprising how diverse the programs resulting from these projects han-dle the challenges introduced by the embedded environment, the physicalcomponents, and the OSEK system. This showcases that even in the confor-mance classes BCC1 and BCC2, OSEK programs can exhibit a wide varietyof synchronization structures. With the help of the techniques presented inthe chapters 4 and 5 Goblint was able to analyze all three approaches, veri-


fying correct synchronization patterns as well as uncovering potential errorswhere corner cases have been missed.

On the other hand, these projects confirm that developers are likely toimplement their own synchronization methods or make unexpected use ofthe resource mechanism. Accordingly, equally creative analyses will have tobe constructed. It is likely that continued work with OSEK programs willuncover further implementation patterns that need to be addressed by newdedicated analyses.

8 Practical Implementation

The practical implementation of the results presented in chapters 4 and 5required an extended infrastructure compared to the thread-based analysespresent in the Goblint analyzer. It was, however, possible to fully reuse thefront-end for C-files as well as the base analysis dealing with, e.g., pointertargets and guards. This allowed the focus of the implementation effort toremain on OSEK related features. The main addition was a front-end for OIL-files. Furthermore, during the cooperation with industrial partners, severalusability features have been implemented as well as some convention checkingcapabilities.

8.1 OIL-file Parsing

Since the OSEK operating system with the scheduler and the rules of the pri-ority ceiling protocol are identical for all OSEK programs, they can and havebeen hard coded into the analyzer. The properties of Tasks and Interrupts,however, vary from program to program and are generally not visible in thesource code. Instead, they are given in the OIL-file, which is an additional con-figuration file written in the OSEK implementation language. Accordingly,these OIL-files have to be processed in order to exploit the strong propertiesof the OSEK operating system. Fortunately, the format of OIL-files is givenby a context free grammar and readily parsed using common parser genera-tors. The information extracted during the parsing is stored in separate hashtables for interrupts, tasks, resources, and events. For interrupts, the priority,category, and list of accessible resources is stored. Tasks additionally storethe list of accessible events, how often they can be activated, whether theycan be preempted, if they are ready at startup, and if they can be activatedby a timer. The activation of a task through a timer is not given as a propertyof a task, it is computed by inspecting all alarms and timers. For resources,a unique identifier and a lock object is generated that allows the analyses toreuse the lock domains of the must-lock analysis of Goblint. Additionally, theceiling priority of a resource is computed by investigating the list of accessi-ble resources of all tasks and interrupts. Events only store an id and whetherthey can be set by an alarm.

108 8 Practical Implementation

8.2 Grouping of Warnings

The size of the industrial benchmarks did not only prove challenging for theanalyzer, who handled it very well, but also for the user, since the amountof information produced was overwhelming. The first step was to separatepositive information from warnings by writing them to separate files. Beyondthe usual distinction into read and write data races, the asymmetric situationin OSEK programs allows four more groups that represent different racesituations. While all these situations constitute possible error sources, theyalso can occur when certain design patterns are used. For example, there is theconcept of a blackboard where high priority tasks write and low priority tasksread. This is a common method of communicating sensor values, especiallyfor tasks with short cycle times, despite the fact that due to the lack ofsynchronization, the data in use might be outdated. Therefore, it is nowpossible to separate warnings into high read races, high write races, low readraces and low write races corresponding to e.g. only read accesses by highpriority tasks.

8.3 Flag Discovery

During the research of flag based synchronization in industrial source code,it was noticed that some variables acted as flags even though they did notindicate to do so, i.e., their names did not end in “ flag”. The implementedanalysis can only discover synchronization with variable a priori specifiedas flags. Since the person using the analyzer might not be the programmer,or some flag synchronization might not even have been implemented inten-tionally, it is hard to provide that input. The observed properties of flagsas defined in chapter 5, however, can also be used to search variables thatmight act as flags. Based on this, a heuristic has been implemented that out-puts variables which take only constant values and are used in guards butnot in computations. In the student projects, this heuristic produced listsof variables that consisted of all flags and at most two unsuitable variables.These lists of variables were also small enough to be directly used as input forthe flag analysis. For the industrial benchmark, however, it produced severalhundred hits. And while it contained a large amount of variables ending in“ flag”, it also contained several variables that have been immediately ruledout by the industrial partners. Manual post processing or a better heuristic istherefore required before this technique can replace the manual input, sincethe number of flags is crucial factor for the speed of the analysis.

8.4 Convention Checking

In addition to the strict properties, the OSEK specification also describesseveral conventions that should hold but are not essential to an OSEK system.

8.5 Variant Code Issues 109

For example, the priorities of category 1 interrupts should be higher than thepriorities of category 2 interrupts, which again should have higher prioritiesthan tasks. Since this information is readily available during the parsing of theOIL-file, Goblint has been enhanced with an option to report on whether thisconvention is satisfied for the input program or not. Similarly, the mandatoryproperty that all events and resources that are used by tasks and interruptsare declared in the OIL-file is checked during parsing.

The source code analysis knows whether a task or an interrupt is analyzedand which category an interrupt belongs to. Therefore, it is able to check ifan API function is called outside its allowed context. For example, if aninterrupt calls WaitEvent. Similarly, WaitEvent should not be called whileholding a resource or having disabled interrupts. Another convention is thattasks do not terminate while holding resources. Since priority informationis conservatively computed only from resources definitely held at a givenprogram point, this test only issues a warning if a task will always hold acertain resource upon termination. There is also a domain available to trackpossibly held resources which would allow this test to verify that no resource isheld upon termination of a task. While the programming overhead is minimal,this was not implemented since the OSEK operating system employed by theindustrial partners is implemented to release any held resources upon tasktermination. Therefore, the memory needed to track the set of potentiallyheld resources was saved.

8.5 Variant Code Issues

The structure of the industrial source code provided a major challenge. Notbecause of intricate uses of the OSEK system, but because of variants. Vari-ants occur naturally in the automotive industry due the the large amount offeatures and options, the heterogeneous hardware environment, as well as na-tional traffic legislation. The colloquial statement by the industrial partnersis that of the 30.000 trucks produced in the local factory each year no twoare identical. Consequently, the software project contains specialized codefragments for each piece of hardware which are typically selected by compilerflags during compilation. For the analysis of the source code, these selectionsare not available. Partially because they are unknown but even more so be-cause a dedicated proprietary compiler is needed to process them. Therefore,data races found might occur only between code fragments that belong tomutual exclusive hardware components. The current state of the implemen-tation is that Goblint is locked into the default selection, which leads to largeparts of the source code to be considered unreachable.

9 Future Prospects

There remain some interesting points regarding the analysis of OSEK pro-grams which have not been touched in this thesis. This chapter will elaborateon these points and give some ideas how to tackle them.

9.1 Extended Conformance Classes

The reason for the focus on basic conformance classes is the absence of events.All other properties of extended conformance classes are well within the scopeof the techniques presented here. Events, however, introduce a wait and notifytype of synchronization which is typical for thread based parallelism like, e.g.,Java. In the presence of recursive procedures, however, unrestricted synchro-nization through wait and notify can be used to encode the intersection ofcontext-free languages implying that reachability becomes undecidable [46],or, alternatively, further abstractions are required. A possible approach forthe non-recursive case might be to split a task into two separate pieces, wherethere is a wait command and treat the wait as termination of the first pieceand a corresponding notify as a activation of the second piece. Regarding themodeling as a push-down system described in chapter 3, it would create theneed for more summaries and complicate the scheduling rules. Therefore, itwould be more sensible to instead rely on acquisition histories as presentedby Kahlon and Gupta [28] for the push-down view. For the analysis of dataraces, the splitting of tasks creates new entry points. Holding a resource atthe wait produces a task fragment that starts with a higher priority thanstatically defined. This is likely to cause false alarms, especially when theflag based synchronization from chapter 5 is considered. The wait could oc-cur inside a branch resulting in loss of flag information for the second taskfragment. However, it is convention that wait is not called while holding aresource. While this solves the issue of higher priority task entries, the split-ting of branches and loss of flag information would persist. Another approachwould be to simply forfeit all priority based protection for accesses surround-ing a wait call. This is a sound approximation but also a very coarse solution.More research is required to obtain a satisfactory solution for the treatmentof events in OSEK programs or priority preemptive systems in general.

112 9 Future Prospects

9.2 Hook Routines

Another feature of OSEK system not considered in this thesis are so-calledhook routines. These routines are program fragments which are executed bythe OSEK operating system when certain situations occur during execution.For example, there is a hook routine that is called whenever a task terminatesand is then executed before any other task or interrupt is scheduled. Hookroutines are not allowed to access resources or events. Additionally, thesefunctions occur at precisely defined moments and run outside the prioritybased scheduling. Therefore, they do not contribute to the complexity ofthe theoretical model presented here. It is an implementation detail to makesure that this source code is added to the appropriate nodes of the controlflow graph. If the hook routine is triggered when an alarm expires it can beadded as a new interrupt of highest priority. This type of control flow graphextension can not be cleanly integrated into the current Goblint tool. Sinceno relevant hook routines have been encountered during industrial testing,hook routine support was not implemented.

9.3 Precise Task Activation

The current implementation treats all tasks as if they could occur at any time,which is a sound approximation. The vast majority of tasks present in thetest programs are indeed activated by alarms. Therefore, it is a sensible con-jecture that this is the typical use of tasks, which makes this approximationnot only very practical but also fairly precise. For tasks that are activateddirectly by another task, this approximation clearly introduces spurious con-trol flow. However, in order to handle time triggered tasks any more precisely,an intimate knowledge of the run times of tasks and timers is required. Thetick interval and expiration times of timers and alarms are available throughthe OIL-file. It is therefore possible to determine the exact times when atime triggered task is activated. The difficulty is to determine the state ofthe program at these times. The control point of the running task, for ex-ample, is very hard to obtain. It is an interesting future topic to investigatehow information about worst case execution time can be used to obtain abetter approximation. For example, one could rule out a data race betweentwo tasks that are activated at the same tick and have definitely terminatedbefore they are activated again. The presence of interrupts, however, makesthis very challenging and definitely requires information about the underly-ing hardware and the rates at which interrupts can be triggered by the realworld environment.

9.4 Multi-core Architectures 113

9.4 Multi-core Architectures

With the surge of multi-core processor architectures it might seem anachro-nistic that this work is limited to single cores. It is, however, unclear how pri-ority based synchronization principles can be retained in case several tasks areexecuted at once. The communication specification for OSEK systems [23]defines the cooperation of several separate OSEK systems. This obviouslydoes not require physically distant processors. If every core of a multi-coreprocessor is in essence running a separate OSEK system, the same commu-nication methods can be used. The AUTOSAR specification[9] allows theassignment of every task to a component. Which component a task belongsto is statically defined in the OIL-file. Every component is then executed invirtual isolation with, e.g., separate memory space. This allows the distribu-tion of tasks from different components to different cores, without interferingwith the priority based synchronization. This strict separation, however, alsoallows each component to be treated as a separate program and analyze itin isolation. The current implementation does not take this information intoaccount.

10 Conclusions

The knowledge and security of embedded programs are important, especiallyin the automotive domain where errors can easily cause large damages. Thisthesis provides models and techniques to further both. Starting from theOSEK specification several models of programs, running under an OSEKoperating system, have been developed. Based on these models, dedicatedanalysis of data races and value ranges have been created that yield moreprecise results than general techniques for thread-based parallel programs.

The first step to understand OSEK programs and priority preemptiveprograms in general, was that they can be modeled as push-down systems.The modeling as a push-down system clarifies the complex scheduling andcontrol flow of the concurrent program. This translation was achieved bydeveloping new semantic rules that deal with, e.g., interrupts and the waitingqueue. The resulting model already allowed a first analysis of data races bymeans of push-down system reachability.

The next step was to precisely analyze the dynamic changes of prioritiesduring program execution. This was achieved by tracking the static prioritiesfrom which functions can be called, as well as for every program point thesets of held resources. The knowledge about priorities and resources wasthen integrated into a program analysis constraint system. Based on thisconstraint system, a sound analysis of data races was constructed. In casethe set of resources held at a program point was unique, this analysis is alsocomplete. It was also shown that the constraint system can act as a frameworkto leverage any abstract interpretation analysis to OSEK programs. As anexample, the analysis of linear equations was presented, which even in thepresence of interrupts, was able to determine interesting correlations of globalprogram variables like, for example, that the sum of two variables is constant.Furthermore, the priority information has been aggregated over functions.With this aggregated information it was possible to make statements aboutthe security of shared data over the whole execution of a function instead ofa single access.

A key abstraction in all the results so far was that branch conditions wereevaluated nondeterministically. Under this abstraction, value based synchro-nization could not be analyzed. Full evaluation of all guards, however, wasunfeasible. Some typical but syntactically plain guard statements were found

116 10 Conclusions

to be sufficient to strongly limit the potential values of variables. The anal-ysis of flags uses the information gained from guards to verify that certainexecution paths are spurious. This allowed a very precise analysis of dataraces, reducing the number of warnings in the industrial application by ap-proximately 60%.

Finally, two approaches were described that exploit the previously de-scribed techniques to compute flow information to obtain precise value ofvariables. Privatization is a general technique that can be utilized in anyglobal invariant based constraint system. The layered invariants approachis dedicated topriority preemptive programs. It was shown that the layeredinvariants approach for these programs is as precise as classical control flowanalysis without invariants, while being significantly cheaper.

Furthermore knowledge beyond the scope of data race analysis has beengenerated during the development and testing of these analyses. The resultsproduced by the prototypical implementation often help to discover seeminglyunrelated code properties. Even false data race warnings often hint at con-voluted synchronization structures which could become faulty during furtherdevelopment of the program. Another example was the list of flag candidateswhich contained variables that the industrial partner immediately excludedas near constant. This exposed that important parts of code were missed inthe industrial benchmark because an incorrect compiler argument was passedto the analyzer.

In addition to the future prospects already discussed, the identificationand analysis of further hand written synchronization schemes is an interestingopen topic. Also, the discovery of situations where a task will remain in thequeue indefinitely could be investigated. In general, temporal properties arevery important and very challenging in all real time applications.

References

[1] K. Apinis, H. Seidl, and V. Vojdani. Side-effecting constraint systems:A swiss army knife for program analysis. In Programming Languagesand Systems, volume 7705 of Lecture Notes in Computer Science, pages157–172. Springer, 2012.

[2] C. Artho, K. Havelund, and A. Biere. Using block-local atomicity to de-tect stale-value concurrency errors. In ATVA’04, volume 3299 of LNCS,pages 150–164. Springer, 2004.

[3] M. F. Atig, A. Bouajjani, and T. Touili. Analyzing asynchronous pro-grams with preemption. In FSTTCS’08, volume 2 of LIPIcs, pages 37–48. Schloss Dagstuhl, 2008.

[4] M. F. Atig, A. Bouajjani, and S. Qadeer. Context-Bounded analysis forconcurrent programs with dynamic creation of threads. In TACAS’09,volume 5505 of LNCS, pages 107–123. Springer, 2009.

[5] T. P. Baker. Stack-based scheduling of realtime processes. Real-TimeSystems, 3(1):67–99, 1991.

[6] M. Barr. Bookout v. toyota, 2013. URL www.safetyresearch.net/

Library/BarrSlides_FINAL_SCRUBBED.pdf.[7] A. Bouajjani, J. Esparza, and O. Maler. Reachability analysis of push-

down automata: Application to model-checking. In CONCUR’97, vol-ume 1243 of LNCS, pages 135–150. Springer, 1997.

[8] A. Bouajjani, M. Muller-Olm, and T. Touili. Regular symbolic analysisof dynamic networks of pushdown systems. In CONCUR’05, volume3653 of LNCS, pages 473–487. Springer, 2005.

[9] A. Consortium. AUTOSAR Architecture Specification, Release 4.0, 2009.URL http://www.autosar.org/.

[10] P. Cousot and R. Cousot. Abstract interpretation: a unified lattice modelfor static analysis of programs by construction or approximation of fix-points. In POPL’77, pages 238–252. ACM Press, 1977.

[11] P. Cousot and R. Cousot. Static determination of dynamic propertiesof recursive programs. In E. Neuhold, editor, Formal Descriptions ofProgramming Concepts, pages 237–277. North-Holland Publishing Com-pany, 1977.

118 References

[12] P. Cousot and R. Cousot. Comparing the Galois connection and widen-ing/narrowing approaches to abstract interpretation, invited paper. InPLILP’92, pages 269–295. Springer, 1992.

[13] M. Das, S. Lerner, and M. Seigle. ESP: Path-sensitive program verifica-tion in polynomial time. In PLDI’02, pages 57–68. ACM Press, 2002.

[14] B. Dutertre. Formal analysis of the priority ceiling protocol. In RTSS’00,pages 151–160. IEEE Press, 2000.

[15] J. Esparza and A. Podelski. Efficient algorithms for pre* and post* oninterprocedural parallel flow graphs. In POPL’00, pages 1–11. ACMPress, 2000.

[16] T. C. et al. OSEK platform for legoR© mindstorms R©, 2010. URLhttp://lejos-osek.sourceforge.net/.

[17] C. Fecht and H. Seidl. A faster solver for general systems of equations.Sci. Comput. Programming, 35(2):137–161, 1999.

[18] C. Flanagan, S. N. Freund, S. Qadeer, and S. A. Seshia. Modular veri-fication of multithreaded programs. Theoretical Comput. Sci., 338(1-3):153–183, 2005.

[19] C. Flanagan, S. N. Freund, M. Lifshin, and S. Qadeer. Types for atom-icity: Static checking and inference for java. ACM Trans. Prog. Lang.Syst., 30(4):1–53, 2008.

[20] P. Ganty, R. Majumdar, and A. Rybalchenko. Verifying liveness forasynchronous programs. POPL’09, pages 102–113, 2009.

[21] O. Group. OSEK/VDX OIL: OSEK Implementation Language, Version2.5, 2004. URL http://www.osek-vdx.org.

[22] O. Group. OSEK/VDX Operating System Specification, Version 2.2.3,2005. URL http://www.osek-vdx.org.

[23] O. Group. OSEK/VDX Communication Specification, Version 3.0.3,2005. URL http://www.osek-vdx.org.

[24] M. S. Hecht. Flow Analysis of Computer Programs. Elsevier, 1977. ISBN0444002162.

[25] T. Henties, J. J. Hunt, D. Locke, K. Nilsen, M. Schoeberl, and J. Vitek.Java for safety-critical applications. In SafeCert’09, ENTCS. Elsevier,2010.

[26] V. Kahlon and A. Gupta. On the analysis of interacting pushdownsystems. In POPL’07, pages 303–314. ACM Press, 2007.

[27] V. Kahlon, F. Ivancic, and A. Gupta. Reasoning about threads commu-nicating via locks. In CAV’05, volume 3576 of LNCS, pages 505–518.Springer, 2005.

[28] V. Kahlon, Y. Yang, S. Sankaranarayanan, and A. Gupta. Fast andaccurate static data-race detection for concurrent programs. In CAV’07,volume 4590 of LNCS, pages 226–239. Springer, 2007.

[29] N. Kidd, P. Lammich, T. Touili, and T. Reps. A decision procedure fordetecting atomicity violations for communicating processes with locks.In SPIN’09, volume 5578 of LNCS, pages 125–142. Springer, 2009.

References 119

[30] N. Kidd, S. Jagannathan, and J. Vitek. One stack to run them all— reducing concurrent analysis to sequential analysis under priorityscheduling. In SPIN’10, volume 6349 of LNCS, pages 245–261. Springer,2010.

[31] G. A. Kildall. A unified approach to global program optimization. InPOPL’73, pages 194–206. ACM Press, 1973.

[32] J. Knoop and B. Steffen. The interprocedural coincidence theorem. InCC’92, volume 641 of LNCS, pages 125–140. Springer, 1992.

[33] J. Kreiker, H. Seidl, and V. Vojdani. Shape analysis of low-level c withoverlapping structures. In VMCAI’10, pages 214–230. Springer, 2010.

[34] P. Lammich and M. Muller-Olm. Conflict analysis of programs withprocedures, dynamic thread creation, and monitors. In SAS’08, volume5079 of LNCS, pages 205–220. Springer, 2008.

[35] P. Lammich, M. Muller-Olm, and A. Wenner. Predecessor sets of dy-namic pushdown networks with Tree-Regular constraints. In CAV’09,volume 5643 of LNCS, pages 525–539. Springer, 2009.

[36] A. Mine. Static analysis of run-time errors in embedded critical parallelC programs. In ESOP’11, pages 398–418. Springer, 2011.

[37] A. Mine. Relational thread-modular static value analysis by abstractinterpretation. In VMCAi’14, volume 8318 of LNCS, pages 39–58.Springer, 2014.

[38] M. Muller-Olm and H. Seidl. Precise interprocedural analysis throughlinear algebra. In POPL’04, pages 330–341. ACM Press, 2004.

[39] M. Naik and A. Aiken. Conditional must not aliasing for static racedetection. In POPL’07, pages 327–338. ACM Press, 2007.

[40] M. Naik, A. Aiken, and J. Whaley. Effective static race detection forJava. In PLDI’06, pages 308–319. ACM Press, 2006.

[41] NASA. Toyota unintended acceleration investigation, 2011. URL www.

nhtsa.gov/staticfiles/nvs/pdf/NASA_report_execsum.pdf.[42] M. Pilling, A. Burns, and K. Raymond. Formal specifications and proofs

of inheritance protocols for real-time scheduling. Softw. Eng. J., 5(5):263–279, 1990.

[43] P. Pratikakis, J. S. Foster, and M. Hicks. Locksmith: Context-sensitivecorrelation analysis for detecting races. In PLDI’06, pages 320–331.ACM Press, 2006.

[44] P. Pratikakis, J. S. Foster, and M. Hicks. Existential label flow inferencevia CFL reachability. In SAS’06, volume 4134 of LNCS, pages 88–106.Springer, 2006.

[45] S. Qadeer and J. Rehof. Context-Bounded model checking of concurrentsoftware. In TACAS’05, volume 3440 of LNCS, pages 93–107. Springer,2005.

[46] G. Ramalingam. Context-sensitive synchronization-sensitive analysis isundecidable. ACM Trans. Prog. Lang. Syst., 22(2):416–430, 2000.

120 References

[47] J. Regehr and N. Cooprider. Interrupt verification via thread verifica-tion. ENTCS, 174(9):139–150, 2007.

[48] J. Regehr, A. Reid, and K. Webb. Eliminating stack overflow by ab-stract interpretation. ACM Trans. Embedded Comput. Syst., 4(4):751–778, 2005.

[49] P. Sack, B. E. Bliss, Z. Ma, P. Petersen, and J. Torrellas. Accurate andefficient filtering for the intel thread checker race detector. In ASID’06,pages 34–41. ACM Press, 2006.

[50] M. D. Schwarz, H. Seidl, V. Vojdani, P. Lammich, and M. Muller-Olm.Static analysis of interrupt-driven programs synchronized via the priorityceiling protocol. In POPL’11. ACM Press, 2011.

[51] H. Seidl. Least solutions of equations over N. In ICALP’94, volume 820of LNCS, pages 400–411. Springer, 1994.

[52] H. Seidl, V. Vene, and M. Muller-Olm. Global invariants for analyzingmultithreaded applications. Proc. of the Estonian Academy of Sciences:Phys., Math., 52(4):413–436, 2003.

[53] H. Seidl, R. Wilhelm, and S. Hack. Compiler Design - Analysis andTransformation. Springer, 2012. ISBN 978-3-642-17547-3.

[54] L. Sha, R. Rajkumar, and J. P. Lehoczky. Priority inheritance protocols:an approach to real-time synchronization. IEEE Trans. Comput., 39(9):1175–1185, 1990.

[55] M. Sharir and A. Pnueli. Two approaches to interprocedural data flowanalysis. Program Flow Analysis: Theory and Applications, pages 189–234, 1981.

[56] M. Vaziri, F. Tip, and J. Dolby. Associating synchronization constraintswith data in an object-oriented language. In POPL’06, pages 334–345.ACM Press, 2006.

[57] V. Vojdani. Static Data Race Analysis of Heap-Manipulating C Pro-grams. PhD thesis, University of Tartu, 2010.

[58] V. Vojdani and V. Vene. Goblint: Path-sensitive data race analysis.Annales Univ. Sci. Budapest., Sect. Comp., 30:141–155, 2009.

[59] J. W. Voung, R. Jhala, and S. Lerner. RELAY: static race detection onmillions of lines of code. In ESEC/FSE’07, pages 205–214. ACM Press,2007.

[60] M. N. Wegman and F. K. Zadeck. Constant propagation with conditionalbranches. ACM Trans. Program. Lang. Syst., 13:181–210, 1991.

Documents

Static Analysis of Embedded Software with Priority ... · Static Analysis of Embedded Software with Priority Scheduling and Interrupts ... 7.3 Obstacle Avoiding Car ... The autonomous