Compositional Verification of Heap-Manipulating Programs through Property-Guided Learning

Long H. Pham, Jun Sun, Quang Loc Le

    Research output: Contribution to journalConference article

    13 Downloads (Pure)

    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.
    Original languageEnglish
    Pages (from-to)405-424
    Number of pages20
    JournalLecture Notes in Computer Science
    Volume11893
    Early online date18 Nov 2019
    DOIs
    Publication statusE-pub ahead of print - 18 Nov 2019
    EventThe 17th Asian Symposium on Programming Languages and Systems - Bali, Indonesia
    Duration: 1 Dec 20194 Dec 2019
    Conference number: 17
    https://conf.researchr.org/home/aplas-2019

    Fingerprint Dive into the research topics of 'Compositional Verification of Heap-Manipulating Programs through Property-Guided Learning'. Together they form a unique fingerprint.

  • Cite this