Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

A Reachability Predicate for Analyzing Low-Level Software

Shaunak Chatterjee1, Shuvendu K. Lahiri2, Shaz Qadeer2 and Zvonimir Rakamarić3

(1)  Indian Institute of Technology, Kharagpur,  
(2)  Microsoft Research,  
(3)  University of British Columbia,  
Abstract
Reasoning about heap-allocated data structures such as linked lists and arrays is challenging. The reachability predicate has proved to be useful for reasoning about the heap in type-safe languages where memory is manipulated by dereferencing object fields. Sound and precise analysis for such data structures becomes significantly more challenging in the presence of low-level pointer manipulation that is prevalent in systems software.
In this paper, we give a novel formalization of the reachability predicate in the presence of internal pointers and pointer arithmetic. We have designed an annotation language for C programs that makes use of the new predicate. This language enables us to specify properties of many interesting data structures present in the Windows kernel. We present preliminary experience with a prototype verifier on a set of illustrative C benchmarks.

Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Referenced by
1 newer article

  1. Wang, Zhifang (2008) Automated verification of pointer programs in pointer logic. Frontiers of Computer Science in China
    [CrossRef]
Remote Address: 38.107.191.110 • Server: mpweb22
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)