Automatic fault location for data structures

Vineet Singh, Rajiv Gupta, Iulian Neamtiu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


Specification-based data structure verification is a powerful debugging technique. In this work we combine specification-based data structure verification with automatic detection of faulty program statements that corrupt data structures. The user specifies the consistency constraints for dynamic data structures as relationships among the nodes of a memory graph. Our system detects constraint violations to identify corrupted data structures during program execution and then automatically locates faulty code responsible for data structure corruption. Our approach offers two main advantages: (1) a highly precise automatic fault location method, and (2) a simple specification language. We employ incremental constraint checking for time efficient constraint matching and fault location. On average, while Tarantula statistical debugging technique narrows the fault to 10 statements, our technique narrows it to ≈ 4 statements.

Original languageEnglish (US)
Title of host publicationProceedings of CC 2016
Subtitle of host publicationThe 25th International Conference on Compiler Construction
PublisherAssociation for Computing Machinery, Inc
Number of pages11
ISBN (Electronic)9781450342414
StatePublished - Mar 17 2016
Event25th International Conference on Compiler Construction, CC 2016 - Barcelona, Spain
Duration: Mar 17 2016Mar 18 2016

Publication series

NameProceedings of CC 2016: The 25th International Conference on Compiler Construction


Other25th International Conference on Compiler Construction, CC 2016

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Signal Processing
  • Software


  • Constraint checks
  • Data structure error
  • Fault location
  • Memory graph


Dive into the research topics of 'Automatic fault location for data structures'. Together they form a unique fingerprint.

Cite this