静态程序分析并行化研究进展-陆申明，左志强，王林章.pdf
免费下载
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2020,31(5):1243−1254 [doi: 10.13328/j.cnki.jos.005950] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563
静态程序分析并行化研究进展
∗
陆申明
,
左志强
,
王林章
(计算机软件新技术国家重点实验室(南京大学),江苏 南京 210023)
通讯作者: 左志强, E-mail: zqzuo@nju.edu.cn; 王林章, E-mail: lzwang@nju.edu.cn
摘 要: 静态程序分析发展至今,已在多个方面取得了长足的进步,应用于软件开发的众多方面.但对现代大规模
复杂软件系统(如千万行代码规模的 Linux 操作系统、分布式大数据处理系统 Hadoop 等)进行高精度的静态分析,
因其极大规模数据量的计算,仍有一定难度.精度、效率和可扩展性相互制约,是静态分析技术在工业界应用的主要
障碍.对此,近年来,随着多核、众核架构的兴起,研究人员提出了静态分析的各种并行化解决方案.首先梳理了静态分
析的发展历程,然后针对当前静态分析面临的挑战,在分析了传统算法优化研究的不足后,对利用硬件资源进行并行
优化的方法进行了充分讨论,包括单机的 CPU 并行、分布式和 GPU 实现这 3 个方面;在此基础上,对一些使用较为
广泛的支持并行的静态分析工具进行了评估;最后,对未来如何从算法和算力角度对静态分析进行并行优化作了讨
论和展望.
关键词: 静态程序分析;软件质量保障;并行计算;分布式处理;GPU 加速
中图法分类号: TP311
中文引用格式: 陆申明,左志强,王林章.静态程序分析并行化研究进展.软件学报,2020,31(5):1243−1254. http://www.jos.org.
cn/1000-9825/5950.htm
英文引用格式: Lu SM, Zuo ZQ, Wang LZ. Progress in parallelization of static program analysis. Ruan Jian Xue Bao/Journal of
Software, 2020,31(5):1243−1254 (in Chinese). http://www.jos.org.cn/1000-9825/5950.htm
Progress in Parallelization of Static Program Analysis
LU Shen-Ming, ZUO Zhi-Qiang, WANG Lin-Zhang
(State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210023, China)
Abstra ct : After years of research, static program analysis has made great progress in many aspects. However, performing sophisticated
program analysis over large-scale software systems (such as Linux kernel, Hadoop, etc.) is still challenging due to its high complexity. To
address the poor scalability of static analysis, with the rise of multi-core computation architectures, researchers have proposed various
parallel static analysis techniques. This paper first introduces the basic concepts of static analysis, the key techniques, and the challenges.
Then the traditional optimization approaches are discussed followed by the studies in parallelizing static analysis in three
categories—CPU parallelism, distributed and GPU implementation, and the representative parallel static analysis tools. Finally, the
potential research trend in parallelizing static analysis is described.
Key words: static program analysis; software quality assurance; parallel computing; distributed processing; GPU acceleration
随着现代软件规模日趋庞大、功能日益复杂,其中的缺陷和漏洞数量也急剧增加.如何精确而又快速地发
现这些缺陷和漏洞,提高软件质量,是学术界和工业界共同关注的重要问题.
∗ 基金项目: 国家自然科学基金(61802168); 江苏省自然科学基金(BK20191247)
Foundation item: National Natural Science Foundation of China (61802168); Natural Science Foundation of Jiangsu Province
(BK20191247)
本文由“系统软件构造与验证技术”专题特约编辑赵永望副教授、刘杨教授、王戟教授推荐.
收稿时间: 2019-09-01; 修改时间: 2019-10-24; 采用时间: 2019-12-24; jos 在线出版时间: 2020-04-07
1244
Journal of Software 软件学报 Vol.31, No.5, May 2020
目前,软件缺陷(和漏洞)的检测方法主要分为两大类:静态分析和动态测试.不同于动态测试需要实际运行
被测程序,静态分析是指在不运行代码的情况下对程序代码进行系统的分析.不同于动态测试受限于测试用例
的完备性,静态分析可以比较全面地考虑可能的执行路径,能发现更多的缺陷,是当前被学术界和工业界普遍采
用的技术.
在实际应用中,静态分析的结果往往包含大量的误报,导致大量的人工确认工作,耗时且容易出错.为提高
分析的精度,往往需要执行高复杂度的静态分析,例如上下文敏感的过程间分析、流敏感/路径敏感的分析等.然
而,高复杂度的分析必然导致极大的计算量和内存消耗,例如在过程调用上下文敏感的分析中,上下文数量会随
目标程序的大小成指数级增长,一个中等规模的软件就可能包含上百万个不同的调用上下文
[1]
.其次,在开源软
件生态下,软件系统的规模急剧增长,百万行、千万行甚至更大的代码规模越来越常见
[2]
.
对此,多年来,人们在静态分析优化方面做了大量的研究工作,取得了不少的进步.传统的优化研究主要关
注对顺序算法的优化,但随着摩尔定律的失效,单核计算效率的提升不足,顺序算法分析效率相对低下.而随着
多核、众核架构的兴起,并行化计算成为有效解决计算效率瓶颈的关键,各种并行化的分析算法被提出,更进一
步地提高了分析的效率.
本文主要通过调研静态程序分析并行化方面的最新研究进展以及具有代表性的静态分析工具,简要综述
静态分析并行化方面的研究动态,同时根据调研内容,讨论在静态分析并行化方面的未来可能的研究方向.本文
第 1 节介绍静态分析的基本概念和关键技术.第 2 节简要讨论当前静态分析面临的挑战.传统算法优化研究及
其不足将在第 3 节详细讨论.第 4 节和第 5 节重点介绍并行/分布式静态分析研究以及并行静态分析工具.第 6
节讨论未来可以开展的研究.第 7 节对本文进行总结.
1 静态程序分析简介
程序分析指的是对计算机程序进行人工或自动化的分析,以确认或发现其特性,比如性能、正确性、安全
性等,是否符合预期
[3]
.程序分析的历史几乎与程序的历史一样长,自从有了程序就有了程序分析.最初的分析主
要是人工进行的,但人工分析往往需要消耗大量的时间和精力,因此,后来人们越来越多地关注自动分析.其中,
编译技术的发展大大带动了程序的自动分析技术,目前的许多分析技术都可以在编译技术中找到基本雏形
[4]
.
以分析过程“是否需要运行被测程序”为准,可将程序分析划分为两大类:静态分析和动态测试.静态分析是
指在不运行代码的方式下进行的分析,动态测试则通过运行具体程序并获取程序的输出或内部状态等信息来
验证或发现程序性质.一般来说,动态测试由于获取了具体的运行信息,因此报出的缺陷更为准确,但只能对有
限的测试用例进行检查;而静态分析可以比较全面地考虑可能的执行路径,能够发现更多的缺陷.本文主要关注
于静态分析.除了缺陷检测以外,静态分析还可用于程序理解、修复以及测试用例生成等方面,是程序语言和软
件工程领域的一个重要研究方向
[5]
.
静态分析涉及的基础理论包括抽象解释(abstract interpretation)、约束求解等,而关键技术包括数据流分析、
指针分析、符号执行(symbolic execution)等.下面将进行简要介绍.此外,人们在发展出众多静态分析技术的同
时,也开发了许多高效的静态分析工具,例如被广泛使用的商业静态分析工具 Coverity
[6]
、Fortify
[7]
、Klocwork
[8]
等,而且这些工具往往综合运用多种分析技术,这也是当前程序分析发展的一个趋势——各种分析技术的集成
与融合.图 1 是一些关键的静态分析技术和工具的时间线.
1) 抽象解释
程序的抽象解释
[12,17]
就是使用抽象对象域上的计算逼近程序指称的对象域(具体对象域)上的计算,使得程
序抽象执行的结果能够反映出其真实运行的部分信息.抽象解释本质上是一种为在计算效率和计算精度之间
取得均衡,以损失计算精度求得计算可行性,再通过迭代计算增强计算精度的抽象逼近方法.基于抽象解释的代
表性程序分析工具包括 Frama-C Value Analysis
[18]
、Astrée
[19]
等.
2) 数据流分析
数据流分析试图获取不同程序点上相关数据的流动信息
[20]
,它对程序控制流图(control flow graph,简称
of 12
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论