自动分析递归数据结构的归纳性质  

Automatically Analyzing Inductive Properties for Recursive Data Structures

作　　者：汤震浩[1,2] 李彬[1,2] 翟娟 赵建华[1,2] TANG Zhen-Hao;LI Bin;ZHAI Juan;ZHAO Jian-Hua(Department of Computer Science and Technology, Nanjing University, Nanjing 210023, China;State Key Laboratory for Novel Software Technology （Nanjing University）, Nanjing 210023, China)

机构地区：[1]南京大学计算机科学与技术系,江苏南京210023 [2]计算机软件新技术国家重点实验室(南京大学),江苏南京210023

出　　处：《软件学报》2018年第6期1527-1543,共17页Journal of Software

基　　金：国家重点研发计划(2016YFB1000802);国家自然科学基金(61632015;61561146394)~~

摘　　要：提出了一种对递归数据结构的归纳性质进行自动化分析的框架.工作分为3个主要部分.首先,它将递归数据结构的归纳性质分为两个主要类别,并提出对应的处理模式,从而帮助简化对于程序中的递归数据结构上的相关性质的分析.其次,提出了一种称为分割与拼接的技术来发现和描述递归数据结构是如何被程序修改的:递归数据结构首先被分割为若干个互不相交的片段,然后,这些片段以新的方式重新拼接在一起,形成一个新的数据结构.这个技术的重点在于如何将程序原有的性质保留下来,从而为后面的分析过程所使用.最后,提出了一种调用上下文敏感的程序摘要过程间分析方法.案例分析和实验结果表明:分析框架可以有效地分析递归数据结构的归纳性质,并生成对程序证明过程有用的断言.This paper proposes a framework facilitating the automatic analysis on inductive properties for recursive data structures. This work has three main parts. First, the analysis of heap-manipulating programs is simplified by classifying inductive properties of recursive data structures into two classifications, each of them is handled with observed patterns. Second, a slicing and splicing technique, in which data structures are first sliced into several parts and these parts are further spliced into new data structures, is proposed to track and specify how data structures are manipulated by programs. The key idea of this technique is to preserve the properties of original data structures, which can be used by further analysis. Third, a calling context sensitive interprocedural analysis is presented for computing program summaries. A case study and experimental results show that the proposed analysis framework can effectively analyze inductive properties for recursive data structures, resulting in assertions that are helpful in program verification.

关 键 词：霍尔式程序证明 程序分析 递归数据结构 归纳性质 过程间分析 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]