×

An array content static analysis based on non-contiguous partitions. (English) Zbl 1379.68096

Summary: 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.

MSC:

68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
68Q60 Specification and verification (program logics, model checking, etc.)

Software:

Apron; FunArray
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[26] Miné, Antoine, The octagon abstract domain, Higher-Order Symbol. Comput., 19, 31-100 (2006) · Zbl 1105.68069
[31] Tanenbaum, Andrew S.; Woodhull, Albert S.; Tanenbaum, Andrew S.; Tanenbaum, Andrew S., Operating systems: design and implementation, vol. 2 (1987), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0835.68017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.