Categorization and analyzing linked structures

In this thesis, we categorize linked structures and linked substructures each into four groups based on two attributes, sharing and cycles. We show that these two attributes can be determined at compile-time by augmenting any store-based analysis with heap reference counts and the missing link property. An analysis, which has the form of an abstract interpretation, is defined and implemented with the program generator Z1. The language analyzed is a low-level intermediate form in which there is no user-level type information. This fact makes the analysis applicable to languages like C and C++, for which type casting and type violations are frequent.A set of programs that create and manipulate linked structures is analyzed. The results show that the analysis is able to correctly recognize a variety of linked data structures, such as radix trees and binary search trees, and substructures, such as those defined by down and next pointer fields in meshes.U of I OnlyETDs are only available to UIUC Users without author permissio