Abstract
Analyzing and verifying heap-manipulating programs automatically
is challenging. A key for fighting the complexity is to develop compositional
methods. For instance, many existing verifiers for heap-manipulating programs
require user-provided specification for each function in the program in order to
decompose the verification problem. The requirement, however, often hinders the users from applying such tools. To overcome the issue, we propose to automatically learn heap-related program invariants in a property-guided way for each function call. The invariants are learned based on the memory graphs observed during test execution and improved through memory graph mutation. We implemented a prototype of our approach and integrated it with two existing program verifiers. The experimental results show that our approach enhances existing verifiers effectively in automatically verifying complex heap-manipulating programs with multiple function calls.
is challenging. A key for fighting the complexity is to develop compositional
methods. For instance, many existing verifiers for heap-manipulating programs
require user-provided specification for each function in the program in order to
decompose the verification problem. The requirement, however, often hinders the users from applying such tools. To overcome the issue, we propose to automatically learn heap-related program invariants in a property-guided way for each function call. The invariants are learned based on the memory graphs observed during test execution and improved through memory graph mutation. We implemented a prototype of our approach and integrated it with two existing program verifiers. The experimental results show that our approach enhances existing verifiers effectively in automatically verifying complex heap-manipulating programs with multiple function calls.
| Original language | English |
|---|---|
| Pages (from-to) | 405-424 |
| Number of pages | 20 |
| Journal | Lecture Notes in Computer Science |
| Volume | 11893 |
| Early online date | 18 Nov 2019 |
| DOIs | |
| Publication status | E-pub ahead of print - 18 Nov 2019 |
| Event | The 17th Asian Symposium on Programming Languages and Systems - Bali, Indonesia Duration: 1 Dec 2019 → 4 Dec 2019 Conference number: 17 https://conf.researchr.org/home/aplas-2019 |