Timing Analysis of Embedded Software Updates

Kim G. Larsen, Ahmed El Yaacoub, Luca Mottola, Thiemo Voigt, Philipp RümmerRtcsa 2023 · DOI

TL;DR

This paper introduces RETA (Relative Timing Analysis), a novel technique for efficiently verifying the impact of software updates on the worst-case execution time (WCET) of embedded systems. By focusing only on modified and affected code segments, RETA significantly reduces analysis time and effort compared to re-analyzing the entire codebase, while still providing accurate and safe timing estimates.

What Problem Does This Paper Address?

Embedded systems, crucial for applications ranging from automotive to aerospace, rely heavily on precise timing guarantees to ensure correctness and safety. Worst-Case Execution Time (WCET) analysis is a standard technique for verifying these timing properties. However, embedded software frequently undergoes updates for bug fixes, security patches, or feature enhancements. Re-running full WCET analysis on every update is computationally expensive and time-consuming, especially given that updates often modify only a small fraction of the code. This creates a significant bottleneck in the development and maintenance of embedded systems, as developers must invest substantial effort to ensure that updates don't negatively impact critical timing behavior. The paper addresses this by proposing a "differential" approach that leverages the limited scope of changes in software updates.

Methods

The core of the paper is the Relative Timing Analysis (RETA) technique. RETA operates in several key stages:

  • Code Differencing: Identifies the exact lines of code that have changed between the original and updated versions.
  • Slicing Procedure: Uses both forward and backward program slicing to pinpoint all code segments that are potentially affected by the identified changes. This significantly narrows down the analysis scope.
  • Statement Categorization: Classifies the instructions within the sliced program into categories (CatA, CatB, CatBa, CatBb) based on how they affect program flow (sequential, branching, loops). This categorization is crucial for accurately determining their contribution to the timing difference.
  • Differential Timing Calculation: Computes the timing impact of each categorized instruction. Instructions present only in the original version contribute negatively to the difference (speed-up), while those in the updated version contribute positively (slow-down). The final differential timing is the sum of these contributions.

The authors developed two implementations:

  • DELTA: A proof-of-concept semi-automatic implementation of RETA for ARM Cortex M4F microcontrollers, using disassembly and instruction timing data.
  • AIT-RETA: A partial integration of RETA into aiT, an industry-strength WCET analysis tool, to leverage its capabilities for differential analysis under specific conditions.

Datasets

The paper evaluates RETA using:

  • Staple embedded benchmarks: A set of standard benchmarks commonly used in embedded systems.
  • Realistic code updates from official repositories: Actual code changes from projects like Hackflight, a drone autopilot, and a sorting algorithm.
  • Specific benchmark programs: Including matrix multiplication, sorting algorithms, proximity detection, and Fast Fourier Transform (FFT) implementations.

No new datasets were introduced; instead, existing codebases and common embedded software tasks were used to demonstrate the effectiveness of RETA.

Key Insights and Ideas

  • The "small change, big impact" problem: A seemingly minor code modification (e.g., changing an add to a mul instruction) can have a significant, multiplicative effect on execution time if that instruction is part of a critical loop or influences loop bounds. RETA's slicing and categorization are designed to capture these indirect effects.
  • Differential analysis is sufficient: For many updates, especially bug fixes and security patches, knowing the change in execution time is more important and practical than re-calculating the absolute WCET from scratch.
  • Slicing is key to efficiency: The ability to isolate only the relevant code segments is the primary driver of RETA's performance gains. Without it, the analysis would still be prohibitively expensive.
  • Instruction categorization is critical for accuracy: Different types of instructions (sequential, branching, loop-related) contribute to timing differences in distinct ways, requiring tailored analysis to avoid over- or under-estimation.
  • Trade-offs in implementation: DELTA, a full RETA implementation, offers broader applicability but has some limitations (e.g., not accounting for caches). AIT-RETA, integrated into a commercial tool, is more restrictive but demonstrates the potential for industry adoption.

Key Results

  • Accuracy: DELTA's differential timing estimates were found to be "safe" (within the bounds of real hardware execution) for most benchmarks. The estimates ranged from exactly the WCET of real hardware to 148% of the new version's measured WCET.
  • Comparison with aiT: In the same benchmarks, the unmodified aiT tool estimated WCETs that were 112% and 149% higher than actual executions, indicating DELTA is either more accurate or similarly pessimistic.
  • Performance Improvement:
    • AIT-RETA reduced aiT's analysis time by 45% and memory consumption by 8.9%.
  • Removing RETA from DELTA (making it a regular timing analysis tool) increased its analysis time by 27%.
  • DELTA itself showed significant reductions in computational complexity compared to full analysis.
  • Specific Benchmark Wins: For sorting benchmarks, DELTA provided insights into performance improvements for reverse-sorted arrays and degradation for sorted arrays, offering definitive bounds.

Limitations and Future Work

  • Limitations:
    • Cache and Pipeline Effects: DELTA does not explicitly account for caches, pipelines, wait states, or branch prediction. This can lead to inaccuracies, especially for systems with large caches or complex pipeline behavior.
  • Interrupts: Static timing analysis, in general, struggles with interrupts. While DELTA can identify changes in interrupt service routines, their impact on overall timing is complex.
  • Variable Instruction Timings: While DELTA handles variable instruction times by providing pessimistic and optimistic estimates, the accuracy can be affected by factors like spatial/temporal locality impacting cache behavior.
  • Peripheral Interactions: Reasoning about the timing of interactions with external peripherals is inherently difficult and may require combining DELTA with hardware profiling.
  • Future Work: The authors suggest integrating more advanced analysis techniques for caches and pipelines into DELTA. They also note that the slicing procedure could be optimized further for minimal program size. The potential for applying RETA to multicore systems is also an area for future exploration.

Summary updated

BibTeX
@inproceedings{larsen2023timing,
  author = {Kim G. Larsen and Ahmed El Yaacoub and Luca Mottola and Thiemo Voigt and Philipp Rümmer},
  title = {{Timing Analysis of Embedded Software Updates}},
  booktitle = {Rtcsa},
  year = {2023},
  doi = {10.1109/rtcsa58653.2023.00010},
}

Loading related content...

Figure