Optimizing Hash-Based Equivalence Checks for Fault Injection in Continuous Integration Testing

• Typ der Arbeit: Bachelor-/Masterarbeit
• Status der Arbeit: in Planung
• Projekte: CLASSY-FI
• Betreuer: Tim-Marek Thomas, Daniel Lohmann

Context

Testing fault tolerance mechanisms and by indirection safety-critical systems is commonly done by performing extensive fault injection (FI) experiments on a system that tries to mimic physical causes of soft errors/bit flips and then observing the system’s behaviour. There are many possibilities for such injections, for instance, every bit in every cycle. The size of the fault space also heavily depends on the layer in the system stack. In our case, we perform ISA-level fault injection, and FAIL*¹ is the fault injection framework of our choice.

Currently, fault injection campaigns are performed on a by-need basis. However, as advocated by the community² performing tests early and often leads to a more reliable system. In an ideal world, testing is done continuously, and since the project start, for instance, in a continuous integration (CI) setting.

As an FI campaign, which covers the whole fault space, takes a long time³, we need to shorten the campaign runtime to enable FI in a CI setting. A solution to this is injecting only a sample of the fault space⁴. However, as the samples are typically chosen at random and uniformly distributed, the sample might provide a misleading picture of the dependability of the program under test (PUT), especially if we want to use the results to guide developers. In addition, even sampling takes too long when executed on every single commit.

Problem

One technique for speeding up fault injection campaigns is introducing equivalence checks during the campaign execution. If the current state of an experiment after the fault injection was already encountered in the past and evaluated, we can then abort the execution and inherit the result. This has been implemented and proposed in different flavors in the past ⁵ and present ⁶.

However, we can take the principle even further by evaluating the following aspects:

• What is the most optimal point in time during the experiment execution for a) hashing and b) comparison?
  • In the past, single-entry single-exit regions were explored⁵, and the creation of snapshots at all simulated steps⁶. Is there an optimal strategy between the both extremes?
  • Could the checkpoint placement proposed by us ⁷ be a valid mechanism?
• We can expand the hash database to include hashes of different configurations/versions/input variations.
  • Do the inherited results stay valid?
  • What is the fitting "length" of the history? I.e. how many FI runs from past commits should be considered?

Goal

The goal of this thesis is an implementation and optimization of the equivalence check mechanism, which additionally considers a CI-pipeline context. In particular following steps are needed:

1. Literature research regarding equivalence check implementations in the domain of testing, with a focus on fault injection
2. Implementation of an equivalence check implementation into FAIL* with:
   • Modular points in time for hashing and comparison (seperately!)
   • An integration of the checkpoint placement⁷ into the FAIL* pipeline
3. Extensive evaluation regarding several aspects:
   • Is the speedup comparable to other approaches⁶⁷?
     • What influence does the point in time/amount of checks have? What are tradeoffs?
   • What is the speedup when considering hashes from old versions?
   • What is the speedup when considering hashes from different configurations?
   • What is the speedup when considering hashes from different inputs?
   • For all three above: does inheriting falsify the overall result?
   • Several Zephyr⁸ applications will be provided for the evaluation.
4. Last, but not least, writing the thesis ;)

As the focus lies heavily on the evaluation part, this thesis workload is freely scalable, depending on whether the aim is a bachelor or master's thesis.

Topics:

• Dependability analysis, continuous integration setup
• C++ (for FAIL*)
• Python (for data visualization, benchmark automation; I am open for other tooling)
• Docker/Podman (environment to run/build FAIL*)

References