Automated Verification of Monotonic Data Structure Traversals in C
a year ago
- #programming
- #C
- #verification
- Bespoke data structure operations are common in real-world C code.
- Monotonic data structure traversals (MDSTs) iterate monotonically through structures, e.g., strlen or binary search tree insert.
- Shrinker is a new automated verification tool for MDSTs in C, using scapegoating size descent analysis.
- Scapegoating size descent leverages similar execution traces between original and 'shrunk' inputs.
- A new benchmark set includes over 100 instances proving correctness, equivalence, and memory safety of MDSTs in major C codebases.
- Shrinker outperforms state-of-the-art tools in verifying monotonic string and list traversals.