State exploration in directed software model checking is guided using a heuristic function to move states near errors to the front of the search queue. Distance heuristic functions rank states based on the number of transitions needed to move the current program state into an error location. Lack of calling context information causes the heuristic function to underestimate the true distance to the error; however, inlining functions at call sites in the control flow graph to capture calling context leads to an exponential growth in the computation. This paper presents a new algorithm that implicitly inlines functions at call sites to compute distance data with unbounded calling context that is polynomial in the number of nodes in the control flow graph. The new algorithm propagates distance data through call sites during a depth-first traversal of the program. We show in a series of benchmark examples that the new heuristic function with unbounded distance data is more efficient than the same heuristic function that inlines functions at their call sites up to a certain depth.

Full Paper and Presentation


N. Rungta and E. G. Mercer. “An improved distance heuristic function for directed software model checking,” Formal Methods in Computer Aided Design (FMCAD '06), San Jose, USA, November 2006.


author =   {N. Rungta and E. G. Mercer},
title =   {An Improved Distance Heuristic Function for Directed Software Model Checking},
booktitle = {FMCAD '06: Proceedings of the Formal Methods in Computer Aided Design},
year = {2006},
isbn = {0-7695-2707-8},
pages = {60--67}, 
doi = {http://dx.doi.org/10.1109/FMCAD.2006.5},
publisher = {IEEE Computer Society},
address = {Washington, DC, USA},}

vv-lab/an-improved-distance-heuristic-function-for-directed-software-model-checking.txt · Last modified: 2015/02/18 12:55 by egm
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0