Computer Systems II

Joshua Gregory

Introduction (please read)        9

Embedded Systems        9

Cross Compilation        9

Build Process        10

Cross-linker        10

Cross-assembler        10

Errors and Options        10

Intermediate Files        11

Sections        11

Translation Units        12

La Fortuna Hardware        12

Microcontroller        12

System on Chip (SoC)        13

Embedded Computer        13

La Ruota Della Fortuna (LaFortuna)        13

Programming in C        14

When to use C        15

C in Practice        16

Header files: *.h        16

Things to be aware from the start        16

Unspecified        16

Undefined        17

Memory-mapped I/O        17

How is software connected to Hardware?        18

Control Registers        18

Special Instructions vs. Memory Mapping        19

AT90USB1286: Address Spaces        20

AT90USB1286: Data Memory Map        20

Manipulating register bits        20

Interrupt Handling & Event Driven Programming        21

Basic I/O Methods        21

Programmed I/O (Polling)        21

Interrupt-driven I/O        21

Interrupts        21

Program Flow        21

Interrupt Service Routines (ISR)        22

Latency        22

Maximum Latency        23

Jitter        23

How to keep ISRs fast and simple?        23

ISRs in C        23

Event Driven Programming        24

State Machines        24

Internal and External Events        25

Events        25

Interrupt Vectors & Interrupt Service Routine        25

Volatile        26

ISR Implementation        26

avr-libc’s interrupt API        26

Memory Architecture        26

Harvard Architecture        26

Von Neumann vs. Harvard Architecture        27

Types of Memory on AVR Microcontrollers        27

Memory Technology        27

Flash        28

EEPROM        28

SRAM        28

Addressing        28

RAM Layout        28

Heap/Stack        29

Heap/Stack Collision        29

Handling Memory in C        30

Speed        30

Don’t be sloppy        30

How is malloc implemented        30

Device Drivers        31

Operating System (OS)        31

Uniform Interface        31

Management of Resources        31

Management of Interactions        31

OS Application Interface        32

Role of the Driver        32

Abstraction        33

Potential Drivers on LaFortuna        33

How to write a driver        33

Connecting Hardware to a Microcontroller        33

Connecting extra modules to LaFortuna        33

TFT LCD Display        33

ILI9341 TFT Display Driver        34

Microcontroller Interface Modes        34

Real-time Scheduling        34

Real-time Deadlines        34

CPU Utilization: U        34

Assumptions for Analysis        35

Load from Set of Periodic Tasks        35

Schedulability        35

Simple Case        35

Priority        35

Fixed Priority Scheduling        36

Rate Monotonic Scheduling (RMS)        36

Requirements for RMS        36

RMS Priority        37

RMS is optimal for fixed priorities        37

Harmonic Task Sets        37

RMS issues to consider        38

Dynamic Priority Scheduling        38

Earliest Deadline First        38

Earliest Deadline First (EDF)        38

Multitasking & RIOS        38

OS: Multiprogramming        38

Processes        39

Process States        39

State Transitions of Processes        39

Scheduling        39

Scheduling Algorithms        40

Round Robin        40

Lottery Scheduling        40

Scheduling Scenarios        40

Context Switching        41

Real-time Scheduling        41

Constraints On Computation        41

Real-Time Systems        41

RIOS        41

Key Concept of RIOS        41

Persistent Storage        42

On LaFortuna        42

EEPROM        42

CMOS Floating Gate Transistors        43

Speed vs. Endurance Trade-off        43

Amount of Data / Write Frequency        43

EEPROM on AT90USB1286 (LaFortuna Microcontroller)        43

Flash Memory        43

Flash Access        44

File System        44

Physical Layer        44

Mapping Logical Addresses to Physical Addresses        44

Interface Protocol        45

Serial Communication        45

SPI Protocol        45

Reading blocks from the card        47

Debugging Embedded Applications        47

Debugging        47

Typical Run-time Errors        48

When is debugging hard?        48

General Approach to Debugging        48

Strategies        48

Device Under Test        49

Gather Data        49

Access        49

Timing        49

Make Bug Reproducible        50

Debugging is a Science        50

Tools        50

Where can things go wrong?        50

Typical Scenarios        50

Memory Problems        51

Memory Leak        51

Memory Fragmentation        51

Available Stack Space        51

Memory Corruption        51

How to Debug Memory Problems?        52

Compiler Support        52

FAT File Systems        52

File System        53

Implementation        53

FAT File System(s)        53

FAT FS Metadata        53

CP/M        53

CP/M Disk Format        53

Directory entry (32 Bytes):        54

Present FAT FSs        54

FAT Layout        54

General “Disk” Layout        55

FAT-FS Partition        55

Volume ID Sector        55

Volume ID:        55

FAT-16 Directory Entry        55

Directory Entry        55

Short File Names        56

Attribute Byte        56

FAT Entries        56

Partition Table in MBR        57

Reading FAT        57

FAT start        57

Root Start        57

Data start        57

Simplest way to read data from SD card        58

FAT-FS Limitations        58

VFAT: Long File Names        58

Further additions to FAT-FS Family        59

Directory Entry: Fat16 vs. FAT32        59

Recognising the FAT FS Type        59

The FAT        60

FAT Example        60

FAT Structure        60

Reliability and Security        61

Reliability of Embedded Applications        61

Embedded Systems        61

Common Issues        61

Hardware        61

Software        61

What can happen?        62

What can be done?        62

The Situation:        62

Mitigation Measures        62

Application Specific Failure Modes        62

Example        62

How to respond?        62

Triple redundancy with voting        63

Protection Circuits        63

Defensive Programming        63

Reliability: Toyota Electronic Throttle Control        63

Michael Barr        63

Embedded Systems Defined        64

Embedded Systems        64

Embedded systems in cars        64

Review of Toyota’s Source Code        64

Electronic Throttle Source Code        64

~18 Months With Code        64

Electronic Throttle Control        64

Safety-Critical Systems        65

What Could Go Wrong?        65

Safety Has To Be Designed In        65

Electronic Throttle Control (ETCS)        65

Summary of Conclusions        65

Unintended Acceleration (UA)        65

NASA’s Code Review was bad        65

Software Malfunctions Happen        66

Toyota’s Operating System (OSEK)        66

Example of Unintended Acceleration        66

Software Causes of Memory Corruption        66

Spaghetti Code Defined        67

Dinosaur Says:        67

Toyota’s Spaghetti Code        67

Types of Spaghetti Code        67

Stack Anal.        68

Recursion        68

Toyota’s Stack Mistakes        68

Failed to Comply With…:        68

System Standards        68

Coding Standards        68

Violating Coding Rules Causes Bugs        69

Coding Standards (again)        69

NASA’s Software Areas of Concern        69

Toyota’s Defective “Safety Layers”        69

Layer 1: Mirroring of Critical Variables        69

Throttle Command Design        70

UA VIA Memory Corruption        70

Layer 2: DTCs and Fail-Safe Modes        70

Layer 3: Watchdog Supervisor        71

Defective Watchdog Design        71

Layer 4: ESP-B2 Monitor CPU        71

Toyota Failed to Review Monitor CPU        71

Monitor CPU is Last Line of UA Defence        72

Toyota’s Defective Software Process        72

Toyota’s Inadequate Software Process        72

Stuff        72

Toyota’s Defective Safety Culture        72

NASA sought what Barr Group found        72

Unreasonable Single Points of Failure        73

Individual Task Death Outcomes        73

The Test Space is Effectively Infinite        73

UA forever if brake on at task death        74

Case-Specific Opinions        74

Other Similar Incident Criteria        74

Toyota Experts        75

Reliability Continued        75

Context        75

Classic Problem        75

Interesting Problem        75

What can persist?        75

Reliability in Embedded Systems        76

What can be done?        76

Integrity Checks        76

Cyclic Redundancy Checksums        77

Which bit is wrong?        77

Redundant Codes        77

Watchdogs        77

Fault Recovery        77

Autonomous Fault Recovery        77

Watchdog        78

Software Faults        78

Watchdog in the AT90USB1286        78

Acting on the Watchdog        79

Usage Scenarios        79

Power Consumption        79

Protection        79

Avr-libc support        79

Initialization Period        80

Watchdog is Practice        80

Software Reset        80

Watchdogs differ from device to device        81

Stuck Tasks        81

Multi-tasking        81

Monitor Task        81

Time Scales        81

Event-driven Tasks        81

Robust Monitoring        81

What do we do when the dog bites?        82

?        82

Security in Embedded Applications        82

Risks        82

Internet of Things Research        82

IoT Security        83

Security in Microcontroller Applications        83

Threads?        83

Issues        83

What can be done?        83

Attacks On Hardware        84

Why is hardware attacked?        84

Attack Methods        84

Firmware as Attack Vector        84

Subverted Firmware on Drives        84

Subverted Firmware on USB Drives        85

Attack on physical infrastructure        85

IT- based attacks on physical systems        85

Infrastructure Security        85

Process Control Honey Pot        85

Serious damage to blast furnace in Germany        86

ThyssenKrupp, May 2013        86

Vulnerability in pacemakers        86

Cybersecurity of Infrastructure        86

Stuxnet        86

Outline of how Stuxnet worked        87

Ralph Langner: To Kill a Centrifuge        87

Iran’s approach to uranium enrichment        87

Cascade Protection System        87

Over Pressure Attacks        87

Rotor Speed Attack: Pushing the Envelope        87

Stuxnet Relations        88

Engineering        88

Exploited Vulnerabilities        88

Targeting        88

Impact        89

Stuff        89

Duqu        89

Stuxnet relation        90

Duqu Attack        90

Duqu: Installation        90

Duqu vs. Stuxnet        91

Duqu Logging        92

TL;DR        92

Actual useful stuff to know for the exam        95

RMS        95

FAT FS        96

RIOS and ISRs        98

Introduction (please read)

These notes are basically just copying from the lecture slides, with possible additional info added for further explanation. They are definitely not as good as Matt’s notes, but writing notes is a good way to study, and if others can read this and get value from it then that’s great :D

Edit: These were made when the module ran in 2018/2019. Contents may have changed and stuff, but hopefully this will be largely useful.

Embedded Systems

Cross Compilation

Source code needs to be compiled to an executable to be run. This is usually done on the same machine.

But cross complication is where the executable is meant to be run on a different machine. Source code is compiled on a host, then executed on a target.

This is done when compilation on the target is impossible / impracticable.

Examples:

The architecture of the host and target may be very different.

[Endianness is the sequential order in which bytes are arranged into larger numerical values when stored in memory or when transmitted over digital links.]

Build Process

This process includes the cross-compiler, cross-linker and cross-assembler.

Cross-linker

[A computer utility program that takes one or more object files generated by a compiler or an assembler and combines them into a single executable file, library file, or another 'object' file.]

Cross-assembler

[An assembler that generates machine language for a different type of computer than the one the assembler is running in.]

Errors and Options

When in the build process you may need to:

There are many options to steer the build process, important ones include:

Intermediate Files

Intermediate Files:

Other files

Sections

Memory segments are laid out with virtual addresses.

Section

Use

Location

.text

Instructions

Flash Memory

.rodata

Read-only data

Flash Memory

.data

Initialised global variables

Flash copied to RAM

.bss

Uninitialised global variables

RAM zeroed out

There are 24 section types defined in ELF, but you don’t need to know the rest (I hope)

Translation Units

C-Source code has three scopes

  1. Program wide scope
  2. File scope
  3. Block scope

Programs are organized in files

Files can be compiled independently (.c -> .o)

La Fortuna Hardware

Embedded Hardware comes in made different shapes and sizes:

Microcontroller

Some properties of microcontrollers are:

System on Chip (SoC)

Some properties of systems on a chip are:

Embedded Computer

Some properties of embedded computers are:

As you can see, choosing a piece of embedded hardware has trade-offs, and the right hardware will depend on the task you want to achieve.

La Ruota Della Fortuna (LaFortuna)

The LaFortuna is a Microcontroller (μC)

Dev Kit:

Microcontroller Board with AT90USB1286

AVR Microcontroller

See LaFortuna schematic for more in depth details: https://secure.ecs.soton.ac.uk/notes/comp2215/rscs/lafortuna-schem.pdf

See AVR Microcontroller datasheet for more in depth details:

https://secure.ecs.soton.ac.uk/notes/comp2215/rscs/at90usb1286_doc7593.pdf

Programming in C

Outcome:

… In many ways ideal for embedded systems.

C puts the programmer in full control and doesn’t get in their way. There are some subtle pitfalls. For efficiency reasons there are no safety nets at runtime. It has a terse syntax that is not very restrictive - but has little redundancy. It’s very likely the compiler will find an interpretation for your code.

C can be written in very obfuscated ways.

[Obfuscation is the deliberate act of creating source or machine code that is difficult for humans to understand.]

This means it’s ideal to smuggle malicious code past a review, to use backdoors, security stuff. If bugs make it past the review, why would it stop some carefully crafted code?

C is still a very popular and in demand language to this day.

When to use C

Where C is used, there is typically no alternative:

C is also great for short bit of code that benefit from optimisation:

  1. Write everything in Python
  2. Profile
  1. Replace the hotspots with C

The code will now be more efficient.

C in Embedded Systems

C in Practice

Portability:

Header files: *.h

Things to be aware from the start

Unspecified

Undefined

In some contexts Zero (0) is special:

(Testing for zero is generally fast on any hardware.)

Also be aware:

You don’t need to know by heart for the exam. But don’t sprinkle around parentheses because you are too lazy to look it up. Parenthesis should indicate that the programmer deliberately overwrites the precedence rules, rather than indicating ignorance of the rules.

Memory-mapped I/O

(Finally a real topic…)

A microcontroller is made up of: CPU, Memory, Hardware Modules.

How is software connected to Hardware?

Control Registers

Control registers are sets of flip flops which are not only connected for reading and writing: their inputs or outputs are wired into other circuits.

[A flip-flop is a circuit that has two stable states and can be used to store state information.]

How does the CPU interact with the control registers?

Two methods:

  1. I/O instructions
  1. Memory Mapped I/O

In some CPUs a mix of both methods is used.

Special Instructions vs. Memory Mapping


AT90USB1286: Address Spaces

0x00000 → 0x1FFFF

0x0000 → 0x0FFF

C assumes a single address space (von Neumann architecture).

Workaround: the intended address space is indicated to the linker by a specific big offset.

AT90USB1286: Data Memory Map

All hardware modules on the microcontroller are configured by writing to I/O registers.

All communication from these modules is facilitated by reading and writing I/O registers.

Note that even the general purpose registers are mapped into memory address space.

PORTF, DDRF and PINF registers are mapped to a unique memory address.

io.h will include a set of C-preprocessor #define statements that define constant labels (e.g., DDRF) for the correct address of that register in the target chip.

Manipulating register bits

Interrupt Handling & Event Driven Programming

(Okay, this is even a realer topic)

Basic I/O Methods

Programmed I/O (Polling)

Interrupt-driven I/O

Other I/O methods like Direct memory Access (DMA) or dedicated I/O computers (e.g. a graphics card) use interrupts to communicate with the CPU.

Interrupts

The solution to overcome the inefficiency of programmed I/O is a possibility to interrupt the CPU when I/O devices are ready to receive or deliver data.

Important: the CPU needs to be able to continue where it was interrupted after the interrupt has been dealt with.

State of the interrupted process needs to be preserved.

(Exception: if interrupt should abort execution because of an irrecoverable fault)

Program Flow

“Precise Interrupt”:

  1. State of program counter (PC) is preserved
  2. Everything before PC has been fully executed
  3. Nothing beyond the PC has been started
  4. Execution state of instruction at the PC is know

When interrupt arrives:

  1. Processor completes current instruction
  2. Processor acknowledges interrupt
  3. Hardware saves some state:
  1. Program Counter (PC)
  2. Process status word (PSW)
  1. PC register is loaded with value from interrupt vector table

Control now handed to software…

  1. Software disables interrupts
  2. Saves additional state
  1. Registers -> Stack
  1. May re-enable interrupts
  1. Easier if not enabled
  1. Services the interrupt -> ISR (Interrupt Service Routine)
  2. Resotres state (software)
  3. Enable interrupts
  4. Hardware: restores PSW and PC

Interrupt Service Routines (ISR)

Procedure that is executed when the interrupt occurs and that handles the interrupt.

Two important rules:

  1. Keep them fast
  1. Keep them simple

Why fast?

Latency

Deterministic latency may be important in real-time applications: e.g., human operators and also control algorithms can adapt to deterministic latency, but struggle with random delays in control lines.

Maximum Latency

We have latency due to hardware:

We also have latency due to software

Jitter

How to keep ISRs fast and simple?

Advantage

Disadvantage

No worries about stack depth

Latency

No overhead for re-entrant code

Lost interrupts

ISR needs to be short/fast (always bounded)

ISRs in C

Instructions are not interrupted, but…

Event Driven Programming

The main loop may be empty or in a sleep command.

State Machines

Example:

They are similar to automatons. Used in this module as more of a model to understand event driven programming.

Internal and External Events

Internal:

External:

Events

Things to consider:

Interrupt Vectors & Interrupt Service Routine

There needs to be an ISR for every interrupt source that is enabled. For the processor to know where to branch to, there is a table at the start of the program memory with the interrupt vector; the address of the ISR for each source.

ISR: Things to watch out for:

Variables:

Volatile

Volatile is slow.

ISR Implementation

  1. Register ISR
  2. Enable interrupt at device level
  3. Globally enable interrupts

avr-libc’s interrupt API

Memory Architecture

Harvard Architecture

Separate memory for instructions and data.

Program Bus:

Data Bus:

Von Neumann vs. Harvard Architecture

Von Neumann

Harvard

No separation between data and program: CPU decides what to execute

Less bus congestion

Types of Memory on AVR Microcontrollers

Bus

Technology

Size

Persistent

Writes

Program

Flash

128 KB

yes

slow

Data

EEPROM

4 KB

yes

slow

Data

SRAM

8 KB

no

fast

Slow writes not only impact performance, but need to be considered also from a reliability perspective (e.g., power failure).

Memory Technology

Flash

EEPROM

SRAM

Addressing

Flash, RAM and EEPROM memory, all have address spaces starting at $0000.

RAM Layout

Heap/Stack

RAM that is not taken up by the global variables and the local static variables is shared dynamically between the heap and the stack.

Heap:

Stack:

In the RAM layout:

Heap/Stack Collision

Handling Memory in C

  1. malloc(SIZE)

Request memory from the heap

  1. Check whether the memory has been granted
  1. free(POINTER)

Return memory to the heap

Speed

Don’t be sloppy

If you don’t follow these rules you might DIE!

Well… maybe not, but these things are more likely:

How is malloc implemented

Device Drivers

Operating System (OS)

Uniform Interface

Management of Resources

Management of Interactions

Uniform for device class or system:

PC:

Embedded:

A PC has a minimum guaranteed amount of I/O hardware. In contrast, embedded systems hardware configurations vary widely. Nevertheless if a type of I/O exist, a standardized form of access can be provided.

This is where device drivers come in the layers of the system.

Device driver - In computing, a device driver is a computer program that operates or controls a particular type of device that is attached to a computer. A driver provides a software interface to hardware devices, enabling operating systems and other computer programs to access hardware functions without needing to know precise details about the hardware being used.

OS Application Interface

Isolates software from

They may be stable over decades, and they are a bridge to user space

They also:

Role of the Driver

Aside from read/write requests the driver also may need to:

For access to I/O registers

Require detailed knowledge of device hardware

Abstraction

But:

Potential Drivers on LaFortuna

How to write a driver

Start with data sheet

Any sample code provided?

Pay detailed attention to reset conditions and the required timing for initialization

Connecting Hardware to a Microcontroller

… typically challenging:

Connecting extra modules to LaFortuna

Precautions:

TFT LCD Display

(You probably don’t need to remember any of this lol)

ILI9341 TFT Display Driver

Supports two color depth:

Microcontroller Interface Modes

The interface mode is selected by hardware with pins.

Other devices (e.g., SD card) may start a negotiating process on the simplest/slowest interface.

(look at the slides for some diagrams idk what they are showing really lol)

Real-time Scheduling

Real-time Deadlines

Deadline: The latest time by which a task has to be completed.

CPU Utilization: U

U = ctotal - cidle <= 1

C total = Total CPU time available (100%)

C idle = Fraction of CPU time spent in idle task or sleeping

Assumptions for Analysis

  1. Tasks are periodic
  1. The deadline for a task is its next invocation
  2. Context switches take no time

Load from Set of Periodic Tasks

Given a set of tasks T1..Tn with periodicity pi and fixed CPU time ci for Ti the utilization is:

Schedulability

Requirement: All tasks meet their deadlines all the time.

A real time system is schedulable if:

(Assuming periodic tasks, with the next invocation as deadline and no overhead for context switching)

How to schedule it?

We need predictable worst case performance.

Simple Case

All tasks can finish within the period of the most frequent task.

Static cyclic scheduling possible: use table to assign time slots to tasks.

Priority

  1. Fixed (static) priority
  1. Dynamic priority

Fixed Priority Scheduling

Optimal fixed priority scheme: Rate Monotonic Scheduling

Rate Monotonic Scheduling (RMS)

Requirements for RMS

  1. Tasks are independent
  1. Tasks have fixed CPU requirement
  2. Free context switching
  3. Deadline is task period

If the conditions for RMS are met, then it is optimal to assign fixed priorities according to the period:

Guaranteed scheduling for:

n = number of tasks

ci = duration of task

pi = period of task

RMS Priority

Task

Importance

Frequency

Priority

A

Very high (critical)

2 Hz

1

B

High

0.1 Hz

2

C

Medium

50 Hz

0 high

The priority in RMS is directly derived from the frequency of the task. It has nothing to do with the importance of the task!

RMS is optimal for fixed priorities

What if your task set does not satisfy U bound?

To guarantee scheduling for any task set that satisfies the conditions, the bound has to assume as worst-cast task set.

If you are wasting 30% of the CPU time

Harmonic Task Sets

Every task period is a multiple of the period of any higher priority task

Non-harmonic

Harmonic

P1 = 17 ms

P1 = 15 ms

P2 = 31 ms

P2 = 30 ms

P3 = 130 ms

P3 = 120 ms

RMS issues to consider

Dynamic Priority Scheduling

Earliest Deadline First

Is a high utilization possible with non-harmonic task sets?

Earliest Deadline First (EDF)

Multitasking & RIOS

OS: Multiprogramming

Processes

Process / Task / Thread - an abstraction of a program in execution

A process has an entry in the process table that typically contains:

Depending on the complexity of switching between, and the level of isolation among processes, you can also talk about tasks and threads.

Process States

There is one running process, but also a ready set and blocked set of processes.

State Transitions of Processes

Processes typically alternate bursts of computing with I/O requests. While waiting for I/O they are blocked from CPU access.

Scheduling

Scheduler - decides which process from the set of ready processes will get the CPU next.

The requirements for the scheduler differ according to the nature of the processes and the computer system:

Scheduling Algorithms

According to what criteria can/should the scheduler select?

Round Robin

Every process gets a time slices and is served in a fixed order

Lottery Scheduling

Scheduling Scenarios

Context Switching

Context switching requires CPU time - this time is wasted.

Context switch overhead:

Real-time Scheduling

Constraints On Computation

  1. Correct (normal system)
  2. Within deadline
  1. Within power budget (new research area)

Real-Time Systems

RIOS

RIOS - Riverside/Irvine Operating System

Key Concept of RIOS

(See the slides for some code examples lol)

Persistent Storage

Note: the details persistent storage section are not examinable.

On LaFortuna

EEPROM

Electrically Erasable Programmable Read-Only Memory

CMOS Floating Gate Transistors

Programming requires up to 20 V -> stressing transistors

Speed vs. Endurance Trade-off

In the design of an EEPROM, programming speed has to be traded against endurance.

Amount of Data / Write Frequency

Sample application: Telephone ☎

Small amounts of data, frequent writes: you can use a Ringbuffer!

EEPROM on AT90USB1286 (LaFortuna Microcontroller)

Flash Memory

Flash Memory is the most common non-volatile storage for embedded systems.

Flash Access

File System

Physical Layer

On SD cards about 1% of capacity is reserved for DRM (Digital Rights Management).

Wear levelling required to extend lifetime.

Mapping Logical Addresses to Physical Addresses

Interface Protocol

3 Interface Methods:

  1. 1-bit SD Bus
  2. 4-bit SD Bus
  3. SPI (Serial Peripheral Interface)

Serial Communication

Types of serial communication:

SPI Protocol

Reading in single block modus.

Reading blocks from the card

Debugging Embedded Applications

Debugging

Typical Run-time Errors

Big bugs in big products:

See slides for more detail

When is debugging hard?

General Approach to Debugging

Debugging is not an Art, it’s experimental Science!

Strategies

Device Under Test

Gather Data

Access

Timing

Make Bug Reproducible

Debugging is a Science

Tools

Where can things go wrong?

Always document the requirements in the source code. Automate and version the build process.

Typical Scenarios

Memory Problems

Memory Leak

Memory Fragmentation

Pay attention to the memory map produced by the linker and watch the available stack space.

Note that you might use malloc() indirectly, e.g., printf() may use it.

Available Stack Space

Determine memory available for dynamic allocation/stack:

Use command: avr-nm -n myprog.elf

Look for the symbol _end. It is the first address in RAM that is not allocated by a variable.

The addresses from _end to the end of the SRAM is what is available for stack and malloc().

Memory Corruption

There is no memory protection on microcontrollers: delays detection of memory corruption.

How to Debug Memory Problems?

On host computer or large embedded system;

On a microcontroller, there is not enough RAM for fancy tools… especially not if there is already a memory issue.

See Code to Observe Fragmentation for an example of looking into the malloc() data structures to track fragmentation.

Compiler Support

Carefully consider whether the debug code should stay in the product or not

This is often a trade-off between reliability and security.

FAT File Systems

File System

Implementation

FAT File System(s)

A simple file system:

FAT - File Allocation Table

FAT FS Metadata

  1. File Allocation Table
  2. Directory Entries

Widely used:

Adapted to massive (x1000) increase in disk capacity

CP/M

Control Program (for) Microcomputers (late 1970s)

CP/M Disk Format

Directory entry (32 Bytes):

Present FAT FSs

FAT Layout

General “Disk” Layout

FAT-FS Partition

Partition Diagram:

Volume ID Sector

The first sector of a FAT partition contains the volume ID, also called volume boot record, or partition boot record. (The yellow section in the picture above.)

Volume ID:

FAT-16 Directory Entry

Root Directory (purple section in partition diagram above):

Directory Entry

Short File Names

11 Bytes for short “8.3” - File Name:        nnnnnnnn.ttt

First Byte

Interpretation

0x00

Never used

0x05

First character of name is 0xe5

0x2e

Entry is a directory

0xe5

Deleted

Attribute Byte

FAT Entries

(The orange and light orange sections in the partition diagram up above)

FAT Entry

Interpretation

0x000

Unused

0xFF0 - 0xFF6

Reserved (e.g., FAT)

0xFF7

Bad (do not use)

0xFF8 - 0xFFF

End of CLuster Chain (EOC) = End of File

anything else

Index to next cluster

Partition Table in MBR

Reading FAT

When reading FAT you first can skip(?) the MBR. Reading the volume ID, and then the FAT and write to memory.

FAT start

The start of the FAT in memory is found by:

FATstart = LBAbegin + Reserved Sectors * Bytes/sector

Root Start

The start of Root is found by:

Rootstart = FATstart + Number of FATs * Sectors/FAT * Bytes/sector

Data start

Then the Data start can be found by:

Datastart = Rootstart + Max Roots * 32

Simplest way to read data from SD card

This can be useful, e.g., to update firmware or to read in a configuration file when memory is too tight to implement a full FAT file system.

FAT-FS Limitations

Originally developed in the late 1970s for floppy disks of less than 500k per volume.

Property

FAT12

FAT16A/B

FAT32

Bits per FAT-entry

12

16

32

Max cluster number

4078

65524

228

Max sector number

216

216 / 232

232

Max size of a cluster

4 KB

32 KB

32 KB

Max file size

8 MB

128 MB / 2 GB

4 GB

Max partition size

16 MB

32 MB / 8 GB

2-16 TB

Year of introduction

1980

1983 / 1987

1997

VFAT: Long File Names

Originally FAT12 and FAT16 were limited to file names of 8 characters and a 3 character suffix.

A backward-compatible fix was introduced as VFAT which hides longer names in directory entries with an unused flag:

MS holds patents (some under dispute, some soon to end) on VFAT.

Further additions to FAT-FS Family

Directory Entry: Fat16 vs. FAT32

Recognising the FAT FS Type

The file formats can be distinguished by the driver software based on the number of clusters c:

The FAT

FAT Example

This is a FAT32 FAT

FAT Structure

Reliability and Security

Reliability of Embedded Applications

Embedded Systems

Typical:

There is also a legal dimension: Embedded software is typically part of a product and liability can not be dodged by excluding it in the license.

Common Issues

Hardware

Software

What can happen?

Anything can happen……

What can be done?

The Situation:

> Reduce probability that something bad happens.

Do not underestimate the failure probabilities for a mass product that is on 24h.

Mitigation Measures

Application Specific Failure Modes

Example

Power glitches have different effects depending on their timing relative to the clock.

How to respond?

Failed system not identified? (requires redundancy):

Triple redundancy with voting

Summarised example: Plane sensors got frozen and then the system disregarded/turned off a sensor because it disagreed more than the permitted value with other 2 sensors.

Some stuff happens with planes nose pointing down………….

If the condition is not corrected, it could result in a loss of control of the aeroplane.

Protection Circuits

Defensive Programming

Reliability: Toyota Electronic Throttle Control

The following is not a shortened version of these lecture slides. Read at your own risk.

Michael Barr

Experienced embedded software dev, consultant, trainer, former adjunct professor person.

He’s written some books.

Embedded Systems Defined

Embedded Systems

Embedded systems in cars

Review of Toyota’s Source Code

Electronic Throttle Source Code

~18 Months With Code

Electronic Throttle Control

Safety-Critical Systems

Embedded systems that can injure or kill people are called Safety-Critical Systems.

What Could Go Wrong?

Safety Has To Be Designed In

Electronic Throttle Control (ETCS)

This Toyota System is an Example of a Safety-Critical hard real-time system

Summary of Conclusions

Toyota’s ETCS source code is of unreasonable quality

Toyota’s fail safes are defective and inadequate

Unintended Acceleration (UA)

NASA didn’t rule out the problem of UA being caused by the software.

NASA’s Code Review was bad

They didn’t spot

They spotted

But Barr Group found more bugs.

Toyota’s ETCS software can malfunction…!

Software Malfunctions Happen

All kinds of embedded systems experience partial software malfunction from time-to-time.

Toyota’s Operating System (OSEK)

The data structures can have bit flips that kill tasks.

Example of Unintended Acceleration

Software Causes of Memory Corruption

All these caused memory corruption

Spaghetti Code Defined

Dinosaur Says:

Toyota’s Spaghetti Code

Types of Spaghetti Code

Data-flow spaghetti

Control-flow Spaghetti

The throttle angle function scored over 100 (unmaintainable)

Stack Anal.

In the stack analysis, Toyota said 41% was used, but it actually got up to 94%!

Recursion violated a MISRA-C rule.

Recursion

NASA was concerned about possible stack overflow…

And NASA didn’t know there was so little safety margin!

Toyota’s Stack Mistakes

Toyota botched its worst-case stack depth analysis

Toyota used dangerous recursion

Toyota failed to perform run-time stack monitoring

Failed to Comply With…:

System Standards

“OSEK” is an international standard API

But Toyota’s Rx-OSEK850 version is non-standard!!!

Coding Standards

MISRA-C – motor industry software reliability coding rules for C

From 2002-2004, Toyota said in public they followed MISRA-C

Toyota’s coding standard only has 11 MISRA-C rules

Violating Coding Rules Causes Bugs

Wow.

Coding Standards (again)

Toyota maintains a set of company internal coding rules

Enforcement is the most important part of having a rule

NASA’s Software Areas of Concern

Toyota’s Defective “Safety Layers”

Layer:

  1. Mirroring of Critical Variable
  2. DTCs and Fail-Safe Modes
  3. Watchdog Supervisor
  4. ESP-B2 Monitor CPU

Layer 1: Mirroring of Critical Variables

Toyota’s engineers sought to protect numerous variables against software-caused and hardware-caused corruptions

But failed to mirror several key critical variables

Throttle Command Design

UA VIA Memory Corruption

Task X death causes loss of throttle control by driver

Motor Control Task continues to drive throttle motor; engine powered

One corruption event can cause task death and open throttle

Layer 2: DTCs and Fail-Safe Modes

NASA talks about 5 fail-safe modes

However, all 5 fail-safes are in same Task X

Most diagnostic trouble codes need Task X too!

Layer 3: Watchdog Supervisor

A “watchdog timer” is hardware to auto-reset software

With multiple tasks, health of all tasks must be checked

Defective Watchdog Design

Toyota’s watchdog supervisor design is unreasonable

Reasonable design alternatives were well known

Layer 4: ESP-B2 Monitor CPU

“System Guards”

“Brake Echo Check”

Toyota Failed to Review Monitor CPU

The critical “monitor CPU” that checks the main CPU has never been independently reviewed

Monitor CPU is Last Line of UA Defence

But ESP-B2 monitor CPU could have included a proper UA defense:

Per car cost to add this safety feature is $0.00 (it’s just bits)

Toyota’s Defective Software Process

FMEA was incomplete; single points of failure are present

Peer reviews not done on OS code and ESP-B2 code

Toyota’s own “power train” coding standard not enforced

Watchdog supervisor doesn’t detect most task’s deaths

No EDAC protection against hardware bit flips

Toyota’s Inadequate Software Process

Stuff

Toyota’s Defective Safety Culture

NASA sought what Barr Group found

“Single memory corruption results in UA”

“Fault escapes detection”

“Openings up to wide open throttle”

Unreasonable Single Points of Failure

Safety critical systems shouldn’t have single points of failure

Toyota tried to mitigate such risks, including in software

Individual Task Death Outcomes

(Watchdog should have detected them all!!!!!!!!!!!)

The Test Space is Effectively Infinite

There are >16 million combinations of task death

Each task can die in thousands of different states

Test “samples” so far confirm

UA forever if brake on at task death

Case-Specific Opinions

ETCS misbehavior is more likely than other causes

Cannot identify with 100% certainty the specific software defects

More likely than not undetected Task X death

Other Similar Incident Criteria

Vehicles with substantially similar ETCS software

Incidents with no apparent mechanical cause

Driver and witness statements describe UA

Toyota Experts

there are gaps thru those layers

counter-intuitive (in an emergency!) and likely to increase (!) risk of harm

“It depends on how much fuel” (Sep 2013)

So why does any of this matter? I don’t know, I just write the notes...

If you actually read through all of that... then well done :)

Reliability Continued

Context

Classic Problem

Reliability is one of the oldest problems studied in computer science:

It is still a problem: new technologies trade size and energy consumption against reliability. (nano-tansistors, organic transistors, etc.)

Interesting Problem


What can persist?

  • Simple system
  • Deteriorates slowly

  • Engineered complex system
  • Deteriorates fast
  • Self-repair
  • Deteriorates slowly

Reliability in Embedded Systems

What can be done?

Integrity Checks

Is anything wrong?

Cyclic Redundancy Checksums

Which bit is wrong?

If we know which bit is wrong we can flip it back.

Redundant Codes

Hamming distance between code words: how many bits differ?

Watchdogs

Fault Recovery

Autonomous Fault Recovery

Typical embedded systems need to operate continuously, but cannot rely on human supervision:

Watchdog

Software Faults

Watchdog in the AT90USB1286

Acting on the Watchdog

Usage Scenarios

Power Consumption

Note, that if the watchdog is enabled it will run in all sleep modes and always consume power. This may be the dominant power consumption in a deep sleep mode.

The watchdog’s oscillator is much slower than the typical main clock and requires therefore less power - it can be used to wake from sleep instead of a timer running off the main clock.

Protection

It is important that a run-away program will not accidentally disable the watchdog timer before it times out!

Configuration bits for reset mode and time-out are protected by a specific write sequence:

Watchdog Configuration

  1. In one operation write a 1 to:
  1. Within the next four clock cycles:

It is important that the watchdog timer is not accidentally disabling a system!

Avr-libc support

#include <avr/wdt.h>

Enable the watchdog with a given timeout period:

wdt_enable(WDT0_1S);

Restart the timer:

        wdt_reset();

Disable the watchdog:

        MCUSR = 0;

        wdt_disable();

Initialization Period

Watchdog is Practice

Software Reset

Applications for the watchdog timer:

Watchdogs differ from device to device

Watchdogs have different modes - know which mode is active.

Stuck Tasks

Multi-tasking

Monitor Task

Time Scales

Often tasks run at very different time scales

How can this be handled?

Event-driven Tasks

Tasks may arrive at unpredictable intervals

Robust Monitoring

Assume that random bit-flips can happen

What do we do when the dog bites?

  1. Reset is often a good option
  1. Try to make it known that there was a watchdog reset

?

Security in Embedded Applications

Risks

Internet of Things Research

IoT Security

Security in Microcontroller Applications

Threads?

Issues

What can be done?

Attacks On Hardware

Why is hardware attacked?

Attack Methods

Passive attack on hardware

Monitor normal operation of hardware (I/O, power consumption) to infer implementation details

Active attack on hardware

Manipulate hardware into abnormal states (including destruction) to gain insight design

Firmware as Attack Vector

Subverted Firmware on Drives

”HDDs/SSDs whose firmware has been reprogrammed can reload associated malware each time infected systems boot and the threat remains persistent even if the drives are reformatted or the operating system is reinstalled. Further, the reprogrammed firmware and associated malware is undetectable by security software once they have infected the drive.”

- McAfee Labs Threats Report, May 2015

Subverted Firmware on USB Drives

USB drives self-declare what they are…

It can pretend to be a hub with all of the above and with a USB drive plugged in.

Attack on physical infrastructure

IT- based attacks on physical systems

Infrastructure Security

Process Control Honey Pot

[A honeypot is a computer security mechanism set to detect, deflect, or counteract attempts at unauthorized use of information systems. Generally, a honeypot consists of data that appears to be a legitimate part of the site, but is actually isolated and monitored, and that seems to contain information or a resource of value to attackers, who are then blocked.]

Serious damage to blast furnace in Germany

Uh oh

ThyssenKrupp, May 2013

Vulnerability in pacemakers

Hedge fund and cybersecurity firm team up to short-sell device maker.

Convert to weapons that can disable therapeutic care and deliver shocks to patients at distances of 10 feet…. Big uh oh.

Cybersecurity of Infrastructure

Stuxnet

“The malware marks a clear turning point in the history of cyber security and in military history as well.”

Outline of how Stuxnet worked

  1. Infection
  2. Search
  3. Update
  4. Compromise
  5. Control
  6. Deceive and destroy

Ralph Langner: To Kill a Centrifuge

A Technical Analysis of What Stuxnet’s Creators Tried to Achieve “. . .between 2008 and 2009 the creators of Stuxnet realized that they were on to something much bigger than to delay the Iranian nuclear program: History’s first field experiment in cyber-physical weapon technology.” “. . .offensive cyber forces around the world will certainly learn from history’s first true cyber weapon. . .”

Iran’s approach to uranium enrichment

Centrifuges in use are not reliable and not efficient— Iran took Google’s approach: build a large infrastructure that can tolerate the break-downs: Cascade Protection System

Cascade Protection System

Over Pressure Attacks

Rotor Speed Attack: Pushing the Envelope

Stuxnet Relations

Engineering

Exploited Vulnerabilities

  1. LNK vulnerability (Zlob in 2008)
  2. Server service
  3. Print spooler (Hackin9 magazine 2009)
  4. Kbd privilege escalation
  5. Return-oriented exploits (ROP)
  6. Hardcoded password (WinCC DBMS)
  7. Stolen certificates (Realtek, JMicron)

Targeting

Impact

Stuxnet was a proof of concept for a new attack strategy.

Stuff

Centrifuge graph?

Recent sighted of code, Duqu payload 2011?

Duqu

“Duqu’s purpose is to gather intelligence data and assets from entities such as industrial control system manufacturers in order to more easily conduct a future attack against another third party. The attackers are looking for information such as design documents that could help them mount a future attack on an industrial control facility”.

Stuxnet relation

Duqu Attack

Three components

  1. Installer
  1. Configuration File
  2. Driver

Control:

Duqu: Installation

Duqu vs. Stuxnet

Feature

Duqu

Stuxnet

Composed of multiple modules

Yes

Yes

Rootkit to hide its activities

Yes

Yes

System driver is digitally signed

Yes (C-Media)

Yes (Realtek, JMicron)

System driver decrypts secondary modules in PNF files

Yes

Yes

Decrypted DLLs are directly injected into system processes instead of dropped to disk

Yes

Yes

Date sensitive: functionality is controlled via complex, encrypted configuration file

Yes (36 days)

Yes

Use XOR based encryption for strings

Yes (key: 0xAE1979DD)

Yes (key: 0xAE1979DD)

Referencing 05.09.1979 in configuration file

Yes (0xAE1979DD)

Yes (0xAE1979DD)

New update modules via C&C

Yes (keylogger)

Yes

Known module to control PLC/SCADA systems

No

Yes

Duqu Logging

Logging controlled by command line, and delivered after initial installation.

 

TL;DR

Microcontroller’s and stuff.

Know about memory and scheduling, RMS IS THE BEST!

Know about interru- HEY STOP INTERRUPTING!

Classic Von Neumann and Harvard architecture.

Know how to code in C, its cool and works with embedded systems.

Also debugging suuuuuucks on microcontrollers.

Device drivers drive devices.

Multitasking also.

Toyota’s code sucks.

Watchdogs?

Actual useful stuff to know for the exam

This is just a section for collection of information on frequent exam topics, from the past paper answers.

RMS

Rate-Monotonic Scheduling

Priorities for tasks using RMS should always be assigned according to their period.

The shortest period should have the highest priority, going up to the longest period having the lowest priority.

If multiple tasks have the same period, it is okay for them to have the same priority.
Priorities are usually ordered starting with 0 for highest priority.

Example:

0 <- high priority

0

2

2

3

4 <- low priority

Schedulability Condition U:

From the list of tasks to be scheduled, it is the sum of each task’s duration (ci) divided by that task’s period (pi).

Example:

 U = 0.2/1 + 0.2/1 + 4/20 + 4/20 + 10/100 + 6/300 = 0.92

For tasks to be scheduled with RMS, U needs to be <= 1.

In the example, it’s 0.92, so this is schedulable.

For all the deadlines to be guaranteed for the task set if RMS is used:

U needs to be <= n(2^(1/n) - 1)

Where n is the total number of tasks to be scheduled.

Using the example above with 6 tasks:

6*(2^(1/6) - 1) ~= 0.73477

U = 0.92 from above, which is > than 0.73…

So the deadlines cannot be guaranteed.

RMS can reach 100% utilization with harmonic task sets.

To make a task set harmonic, each period needs to be a multiple of the lowest period.

The alternative to RMS is using earliest deadline first (EDF).

Also note that the calculations do NOT take into account overhead: context switching or the external step detection interrupt.

Advantages of RMS in real-time systems:

Advantage of EDF over RMS:

EDF can handle changing importance of tasks, accommodate new tasks at runtime, and handle variable execution times of tasks.

FAT FS

FAT is a file system which is commonly used with microcontrollers.

It can be FAT16, FAT32….

It splits memory up into sectors.

The first sector is always the Master Boot Record (MBR).

FAT can have small or large block sizes.

Small block sizes means that there is more overhead in the FAT, as it has to reference every block used by each directory. Files are spread across more blocks, may slow down reading of file.

Large block sizes increase the chance for internal fragmentation, where blocks are much larger than the data space required leaving blank spaces in the blocks.

Internal fragmentation refers to the amount of space left over in a block at the end of a file. High amounts of this fragmentation is caused by large block sizes.

External fragmentation refers to when small block sizes are used, as blocks are more spread out.

General Structure:

The first sector in the Disk is the Master Boot Record (MBR).

Then the first sector of a FAT partition contains the volume ID, also called volume boot record.

Volume ID contains:

Name, Size of sectors and clusters, Sectors per file allocation table, Hidden sectors

The FAT partition then contains 2 FATs, the root directory, then files and directories.

FAT stands for File Allocation Table (what FAT file systems are named after).

It serves as a free-list of all blocks on the device and at the same time it holds the block chain of every file in the file system.

(This table contains entries of data clusters)

More than one copy of FAT due to if one becomes corrupted, second FAT can be used for redundancy.

It allows us to get each cluster of a file (which spans multiple clusters) by following the cluster chain in the FAT.

How to read FAT:

FATstart = LBAstart + ReservedSectors * Bytes/Sector

Rootstart = FATstart + NumberOfFats * Sectors/FAT * Bytes/Sector

Datastart = Rootstart + MaxRoots * 32

When deleting something in FAT:

Directory entries are only changed in the first byte to mark files as deleted.

Still have the start cluster and length of each file

The FAT entries are wiped (marked as free clusters)

RIOS and ISRs

RIOS scheduling uses reentrant interrupt service routines.

Reentrant means that an ISR can be safely interrupted (directly or indirectly) by itself.

Purpose is that it allows higher priority tasks to interrupt lower priority tasks.

This is achieved by keeping static information in a global array and advancing the index of the array with the nesting depth.

Reentrant is a property of a function so that it can be safely called again before it is completed (e.g., recursion or ISR).

Self-preemption is related to scheduling. A preemptive scheduler is one which can take the CPU away from a task in order to give a new or another instance of the same task access to the CPU.

Memory Architecture

Von Neumann

Harvard

Difference: Von Neumann, program memory and data memory are stored in the same place and share the same bus. Harvard, program memory and data memory are separated and use different buses.

Harvard good for microcontrollers: No shared bus so easier for instructions to be executed every clock cycle due to no contention. Data can’t be accidentally executed. Program memory can’t be accidentally overwritten. Cheaper and more efficient to use different storage types for program and data.

How C deals with harvard: C doesn’t support different memory spaces. So compiler deals with this by adding big offset to different memory spaces.

LaFortuna Stuff

After resetting, the clock needs time to stabilize.

When compiling, you need the correct clock frequency so periodic events are accurate to real time.

Ports: PINx, PORTx, DDRx

Where x is a port letter.

DDR (Data Direction Register)

DDR = 0, input

DDR = 1, output

PORT

Usually used with output pin in which it sets output to high or low.

PIN

Sets state of internal pull-up resistors. PIN register is used to get the data from the pins set to inputs.

sei(); - Enables interrupts.

cli(); - Disables all interrupts.

Setting a bit (=1)

Clearing a bit (=0)