An array content static analysis based on non-contiguous partitions. (January 2017)

• Record Type: Journal Article
• Authors: Liu, Jiangchao; Rival, Xavier
• Is Part Of: Computer languages, systems & structures. Volume 47:Part 1(2017)
• Page Start: 104
• Page End: 129
• Publication Date: 2017-01
• Subjects: Array analysis -- Abstract domain -- Program verification; Programming languages (Electronic computers) -- Periodicals; Computer networks -- Periodicals; Computer architecture -- Periodicals; Computer systems -- Periodicals; Langage de programmation; Réseau d'ordinateurs; Architecture d'ordinateur; Périodique électronique (Descripteur de forme); Ressource Internet (Descripteur de forme); 005.13
• DOI: 10.1016/j.cl.2016.01.005
• Languages: English
• ISSNs: 1477-8424

Abstract

Abstract: Conventional array partitioning analyses split arrays into contiguous partitions to infer properties of sets of cells. Such analyses cannot group together non-contiguous cells, even when they have similar properties. In this paper, we propose an abstract domain which utilizes semantic properties to split array cells into groups. Cells with similar properties will be packed into groups and abstracted together. Additionally, groups are not necessarily contiguous. This abstract domain allows us to infer complex array invariants in a fully automatic way. Experiments on examples from the Minix 1.1 memory management and a tiny industrial operating system demonstrate the effectiveness of the analysis. Abstract : Highlights: An abstract domain that partitions array elements according to semantic properties. The abstract domain can represent non-contiguous partitions. Allowing empty groups eliminates the need for global disjunction. We verify two non-trivial invariants in two distinct operating systems.