张健等:程序分析研究进展 ( School of Computer Science, Wuhan University, Wuhan 430072, China) (Key Laboratory of High Confidence Software Technologies of Ministry of Education(Peking University), Beijing 100871, China) Huawei Technologies Co. Ltd, Beijing 100095, China) '(School of Information, Renmin University of China, Beijing 100872, China) s(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China) (School of Computer, National University of Defense Technology, Changsha 410073, China) Abstract: In the information age, people are increasingly demanding high quality of software systems. Program analysis is one of the important approaches to guarantee the quality of software, and has been receiving attentions from academia and industry. This artic mainly focuses on the research progress in program analysis in the last decade. First, the article introduces the basic program analysis chniques, including abstract interpretation, data flow analysis, summary-based analysis, symbolic execution, dynamic analysis, machin learning-based program analysis, etc. Then, it summarizes program analysis approaches for different types of software systems, including mobile applications, concurrent software, distributed systems, binary code, etc. Finally, the article discusses potential research directions and challenges of program analysis in the future. Key words: program analysis, software quality assurance, static analysis; dynamic analy 随着信息化的不断发展,软件对人们生活的影响越来越大,在国民经济和国防建设中具有越来越重要的地 位如何提高软件质量,保证其行为的可信性,是学术界和工业界共同关注的重要问题要解决该问题应加强软 件开发过程管理,在全生命周期采取各种方法和技术提升软件质量由于软件系统的复杂性在编码实现完成之 后,甚至在软件产品发布、被广泛使用之后,往往还有各种各样的缺陷和漏洞各种软件测试和分析技术是发现 这些缺陷、漏洞的有效手段. 不同于很多黑盒测试方法,软件分析技术可深入软件系统内部细致地考察其结构及各个组成部分,进而发 现其各种特性,如性能、正确性、安全性等软件分析已逐渐发展成为程序语言和软件工程领域的一个重要研 究方向,并已影响到信息安全等相关领域进入21世纪以来,该方向进展显著,研究成果不断涌现软件分析不仅 可用来发现软件中的缺陷、漏洞,还可用于软件理解、修复以及测试用例生成等方面 软件包含程序和文档由于篇幅所限,本文主要介绍程序分析方面的研究特别是最近10余年该方向的 些重要工作本文将介绍程序分析的基本概念(分析对象、难度、评价等)、主要的基础性分析技术、针对不 类型分析对象的分析方法等最后简要提及一些挑战性问题以及新兴的研究方向 1程序分析简介 本节介绍程序分析的基本概念、程序及其性质多样性等进而解释程序分析的难度及其评价 基本概念 程序分析指的是:对计算机程序进行自动化的处理,以确认或发现其特性,比如性能、正确性、安全性等凹 程序分析的结果可用于编译优化、提供警告信息等,比如被分析程序在某处可能出现指针为空、数组下标越界 的情形等 传统上程序分析包括各种静态分析技术(类型检查、数据流分析、指向分析等)与动态分析技术所谓的静 态分析,是指对程序代码进行自动化的扫描、分析,而不必运行程序;与静态分析相对应的是动态分析技术其利 用程序运行过程中的动态信息分析其行为和特性 与程序分析密切相关的两类方法是形式验证及测试:前者试图通过形式化方法,严格证明程序具有某种性 质,目前,其自动化程度尚有不足,难于实用;测试方法多种多样在实际工程中广泛使用,这些方法也是以发现程 序中的缺陷为目的,它们一般都需要人们提供输入数据,以便运行程序观察其输出结果 12程序及其性质的多样性 程序分析内涵比较丰富,具有多样性 1)被分析对象的多样性张健 等:程序分析研究进展 81 4 (School of Computer Science, Wuhan University, Wuhan 430072, China) 5 (Key Laboratory of High Confidence Software Technologies of Ministry of Education (Peking University), Beijing 100871, China) 6 (Huawei Technologies Co. Ltd., Beijing 100095, China) 7 (School of Information, Renmin University of China, Beijing 100872, China) 8 (Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China) 9 (School of Computer, National University of Defense Technology, Changsha 410073, China) Abstract: In the information age, people are increasingly demanding high quality of software systems. Program analysis is one of the important approaches to guarantee the quality of software, and has been receiving attentions from academia and industry. This article mainly focuses on the research progress in program analysis in the last decade. First, the article introduces the basic program analysis techniques, including abstract interpretation, data flow analysis, summary-based analysis, symbolic execution, dynamic analysis, machine learning-based program analysis, etc. Then, it summarizes program analysis approaches for different types of software systems, including mobile applications, concurrent software, distributed systems, binary code, etc. Finally, the article discusses potential research directions and challenges of program analysis in the future. Key words: program analysis; software quality assurance; static analysis; dynamic analysis 随着信息化的不断发展,软件对人们生活的影响越来越大,在国民经济和国防建设中具有越来越重要的地 位.如何提高软件质量,保证其行为的可信性,是学术界和工业界共同关注的重要问题.要解决该问题,应加强软 件开发过程管理,在全生命周期采取各种方法和技术提升软件质量.由于软件系统的复杂性,在编码实现完成之 后,甚至在软件产品发布、被广泛使用之后,往往还有各种各样的缺陷和漏洞.各种软件测试和分析技术,是发现 这些缺陷、漏洞的有效手段. 不同于很多黑盒测试方法,软件分析技术可深入软件系统内部,细致地考察其结构及各个组成部分,进而发 现其各种特性,如性能、正确性、安全性等.软件分析已逐渐发展成为程序语言和软件工程领域的一个重要研 究方向,并已影响到信息安全等相关领域.进入 21 世纪以来,该方向进展显著,研究成果不断涌现.软件分析不仅 可用来发现软件中的缺陷、漏洞,还可用于软件理解、修复以及测试用例生成等方面[1]. 软件包含程序和文档.由于篇幅所限,本文主要介绍程序分析方面的研究,特别是最近 10 余年该方向的一 些重要工作.本文将介绍程序分析的基本概念(分析对象、难度、评价等)、主要的基础性分析技术、针对不同 类型分析对象的分析方法等.最后,简要提及一些挑战性问题以及新兴的研究方向. 1 程序分析简介 本节介绍程序分析的基本概念、程序及其性质多样性等,进而解释程序分析的难度及其评价. 1.1 基本概念 程序分析指的是:对计算机程序进行自动化的处理,以确认或发现其特性,比如性能、正确性、安全性等[2]. 程序分析的结果可用于编译优化、提供警告信息等,比如被分析程序在某处可能出现指针为空、数组下标越界 的情形等. 传统上,程序分析包括各种静态分析技术(类型检查、数据流分析、指向分析等)与动态分析技术:所谓的静 态分析,是指对程序代码进行自动化的扫描、分析,而不必运行程序;与静态分析相对应的是动态分析技术,其利 用程序运行过程中的动态信息,分析其行为和特性. 与程序分析密切相关的两类方法是形式验证及测试:前者试图通过形式化方法,严格证明程序具有某种性 质,目前,其自动化程度尚有不足,难于实用;测试方法多种多样,在实际工程中广泛使用,这些方法也是以发现程 序中的缺陷为目的,它们一般都需要人们提供输入数据,以便运行程序,观察其输出结果. 1.2 程序及其性质的多样性 程序分析内涵比较丰富,具有多样性. 1) 被分析对象的多样性