Error Propagation Analyses for Shared-Memory Systems

Stefan Winter
stefan.winter@uni-ulm.de

University of Ulm

LMU Munich

Slide Deck Availability

https://www.stefan-winter.net/presentations/shared-memory_EPA.html

Speaker Background

  • Dr.-Ing: TU Darmstadt, 2015
  • Postdoc: TU Darmstadt, UIUC, LMU Munich
  • Lecturer/Interim prof.: HAW Landshut, LMU Munich, Ulm University

Research focus: Dependable software, mostly “low-level” code

[ICSE’11] [DSN’13] [ASE‘17] [TSE’20] [ISSTA’14] [ICSE’15] [ISSTA’19] [ISSRE’19] [PRDC’18] [ICST’17] [DSN’20] [ISSRE’20] [OOPSLA’20]

Motivation

// Your Program

void printSum(int a, int b) {
  printf(“%d”, a – b);
}

Motivation

// Your Program

void printSum(int a, int b) {
-  printf(“%d”, a – b);
+  printf(“%d”, a + b);
}

libc

Operating System

Problem Magnitude

  1. How many defects in external dependencies?

    • NASA: 0.1 defects/KLOC after deployment (Dvorak 2009)
    • For commodity software: ~1 defect/KLOC good
  1. How many KLOC?
    • Support libraries (glib, etc.): Several MLOC
    • System libraries (libc, etc.): 1-2 MLOC
    • Operating System: 20-60 MLOC

Fault Containment

// Your Program

void printSum(int a, int b) {
-  printf(“%d”, a – b);
+  printf(“%d”, a + b);
}

libc

Operating System

Error Propagation Analyses (EPA)

How do defects in one component affect other components?

Three Steps:

    1. Inject defect into external component

    2. Execute program

    1. Detect behavioral deviations
Assumption: Federated systems
    • Isolated components
    • Explicit interfaces

Interface Injections

Interface Error Injections: Mutating interface parameters

Interface Injections

Federated Systems Assumption

void user() {
  int a = 40;
  int b = 2;
  int result = library_function(a, b);
  ...
}
int library_function(int a, int b) {
  return a + b;
}

Interface injection:

  • Return value of library_function is external input
  • Replace by
    • Fixed value: 42 → 0
    • Random value: 42 → 2275
    • Mutated value: 42 → 43

Interface Injections

Federated Systems Assumption

void user() {
  struct test *t;
  library_function(1, t);
  ...
}
void library_function(int a, struct test *b) {
  bool init = (a - 1 ==  0);
  if (init)
    b->val = 0;
}

Stack (user) Stack (component) Heap struct test t b points to input-output parameter other data

  • No return value as external input
  • Shared-memory via heap pointer t
  • Injection into the pointer
    • Maybe other valid heap
    • Mostly unallocated/protected memory
      → segfault
  • Just inject in pointed-to heap

Interface Injections

void user() {
  struct test *t;
  library_function(1, t);
  ...
}
void library_function(int a, struct test *b) {
  bool init = (a - 1 ==  0);
  if (init)
-   b->val = 0;
+   char *str = "test"; 
+   b->string = str;
}

Stack (user) Stack (component) Heap struct test t b points to input-output parameter char* str

  • Heap contains pointers
    → Injection likely to invalidate
  • Only parts of shared data touched by external code
  • Strategy 1: Ignore it (and miss relevant tests)
  • Strategy 2: Inject into heap memory
    • Many wasted tests
  • Strategy 3: Track all memory “stores”
    • Filter irrelevant cases
    • Requires tracking allocations, frees
    • Orientation: sysbench cpu run
      • 4.8M reads & 1.2M stores

Analyzing Error Propagation in Shared Memory (Lanzaro et al. 2014)

  1. Execute with dynamic binary instrumentation
  2. Construct reachability graphs from function parameters & return values
  3. Compare clean/faulty store traces for reachable memory

Trace Comparison Example

Alignment of longest common sub-sequences (Hunt and Szymanski 1977)

Experimental Evaluation

Name Size (loc) Faults
Libxml2 155k 1471
Libbzip2 6k 463
SQLite 78k<