平码五不中公式规律
  • / 10
  • 下载费用:30 金币  

基于程序切片的代码缺陷静态检测的并行化方法及装置.pdf

关 键 词:
基于 程序 切片 代码 缺陷 静态 检测 并行 方法 装置
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
摘要
申请专利号:

CN201210593048.9

申请日:

2012.12.31

公开号:

CN103914372A

公开日:

2014.07.09

当前法律状态:

授权

?#34892;?#24615;:

有权

法?#19978;?#24773;: 授权|||实质审查的生效IPC(主分类):G06F 11/36申请日:20121231|||公开
IPC分类号: G06F11/36 主分类号: G06F11/36
申请人: 北京启明星辰信息技术股份有限公司; 北京启明星辰信息安全技术有限公司
发明人: 孙薇; 梁彬; 边攀
地址: 100193 北京市海淀区东北旺西路8号中关村软件园21号楼启明星辰大厦
优?#28909;ǎ?/td>
专利代理机构: 北京安信方达知识产权代理有限公司 11262 代理人: 栗若木;曲鹏
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

CN201210593048.9

授权公告号:

||||||

法律状态公告日:

2017.11.10|||2014.08.06|||2014.07.09

法律状态类型:

授权|||实质审查的生效|||公开

摘要

本发明提供了一种基于程序切片的代码缺陷静态检测的并行化方法及装置,其中,该基于程序切片的代码缺陷静态检测的并行化方法包括:利用程序切片技术,将检测对象切分成多个相互独立的子对象;以及,并行执行对各子对象的代码缺陷静态检测。本发明利用程序切片技术将待检测对象划分成多个相互独立的子对象;这些子对象的检测过程互不干扰,可以并行执行对各子对象的代码缺陷静态检测,从而提高静态检测的效率和精度。

权利要求书

权利要求书
1.  一种基于程序切片的代码缺陷静态检测的并行化方法,其特征在于,该方法包括:
利用程序切片技术,将检测对象切分成多个相互独立的子对象;以及
并行执行对各子对象的代码缺陷静态检测。

2.  根据权利要求1所述的方法,其特征在于:
所述利用程序切片技术,将检测对象切分成多个相互独立的子对象,包括:
解析检测对象源程序代码,生成源程序的中间表述形式;
获取切片准则;以及
对于每个切片准则,通过程序切片技术获取与所述切片准则相关的程序代码子集,从而将所述检测对象切分成多个相互独立的子对象。

3.  根据权利要求2所述的方法,其特征在于:
所述解析检测对象源程序代码,生成源程序的中间表述形式,包括:读取检测对象源程序代码,进行词法分析及语法分析,生成抽象语法树和控制流程图,在所述控制流程图的基础上,进行语义分析,生成程序依赖图;和/或
所述获取切片准则包括:从检测规则或已知类型缺陷中提取所述切片准则,或者接收用户自定义的所述切片准则;其中,所述切片准则包含起始点和/或兴趣点。

4.  根据权利要求3所述的方法,其特征在于:
所述对于每个切片准则,通过程序切片技术获取与所述切片准则相关的程序代码子集,包括:
对于只包含起始点的切片准则,采用前向切片的方法遍历所述程序依赖图获取与对应切片准则相关的程序代码子集;
对于只包含兴趣点的切片准则,采用后向切片的方法遍历所述程序依赖图获取与对应切片准则相关的程序代码子集;或者
对于包含起始点和兴趣点的切片准则,采用砍片的方法遍历所述程序依赖图获取与对应切片准则相关的程序代码子集。

5.  根据权利要求1-4?#25105;?#26435;利要求所述的方法,其特征在于:
所述并行执行对各子对象的代码缺陷静态检测,包括:
并行运行多个代码缺陷检测引擎,对各个子对象进行缺陷检测。

6.  一种基于程序切片的代码缺陷静态检测的并行化装置,其特征在于,该装置包括:
切分模块,用于利用程序切片技术,将检测对象切分成多个相互独立的子对象;以及
检测模块,用于并行执行对各子对象的代码缺陷静态检测。

7.  根据权利要求6所述的装置,其特征在于:
所述切分模块包括:
解析单元,用于解析检测对象源程序代码,生成源程序的中间表述形式;
获取单元,用于获取切片准则;以及
切分单元,用于对于每个切片准则,通过程序切片技术将所述检测对象切分成多个相互独立的子对象。

8.  根据权利要求7所述的装置,其特征在于:
所述解析单元,具体用于:读取检测对象源程序代码,进行词法分析及语法分析,生成抽象语法树和控制流程图,在所述控制流程图的基础上,进行语义分析,生成程序依赖图;和/或
所述获取单元,具体用于:从检测规则或已知类型缺陷中提取所述切片准则,或者接收用户自定义的所述切片准则;其中,所述切片准则包含起始点和/或兴趣点。

9.  根据权利要求8所述的装置,其特征在于:
所述切片单元,具体用于:
对于只包含起始点的切片准则,采用前向切片的方式遍历所述程序依赖图获取与对应切片准则相关的程序代码子集;
对于只包含兴趣点的切片准则,采用后向切片的方式遍历所述程序依赖图获取与对应切片准则相关的程序代码子集;或者
对于包含起始点和兴趣点的切片准则,采用砍片的方式遍历所述程序依赖图获取与对应切片准则相关的程序代码子集。

10.  根据权利要求6-9?#25105;?#26435;利要求所述的装置,其特征在于:
所述检测模块,具体用于:并行运行多个代码缺陷检测引擎,对各个子对象进行缺陷检测。

说明书

说明书基于程序切片的代码缺陷静态检测的并行化方法及装置
技术领域
本发明涉及一种代码缺陷静态检测技术,尤其涉及一种基于程序切片的代码缺陷静态检测的并行化方法及装置。
背景技术
目前,代码缺陷静态检测系?#31216;?#36941;存在效率低下的问题,即海量的待分析执行路径需要消耗大量的时间和资源,尤其是在路径爆炸的情况下,静态分析往往是计算不可行的。随着软件规模及复杂度的加大,该问题将越来越严重。目前主流的缺陷检测系?#36784;?#20381;靠引入一些启发式规则和设定分析上界将分析工作限定在一个可接受的范围内。然而这种限定必然会使得部分路径未被分析,从而对检测精度造成影响,导致某些代码缺陷被漏报。
当前,计算机的计算能力得到了空前的提高,主要性能提升手?#38382;?#24341;入并行化计算,但在代码缺陷静态检测领域,很少引入并行化来提高检测效率。其中一个主要原因是代码缺陷静态检测的过程耦合度非常高,难以将单个检测过程拆分成多个可以并行的子过程,导致传统的拆分计算过程的并行化方法不能直接应用于代码缺陷静态检测的并行化。
发明内容
本发明提供了一种基于程序切片的代码缺陷静态检测的并行化方法及装置,以克服因代码缺陷静态检测的过程耦合度非常高而无法将传统的拆分计算过程的并行化方法直接应用于代码缺陷静态检测的问题。
本发明提供了一种基于程序切片的代码缺陷静态检测的并行化方法,该方法包括:
利用程序切片技术,将检测对象切分成多个相互独立的子对象;以及
并行执行对各子对象的代码缺陷静态检测。
优选地,所述利用程序切片技术,将检测对象切分成多个相互独立的子对象,包括:
解析检测对象源程序代码,生成源程序的中间表述形式;
获取切片准则;以及
对于每个切片准则,通过程序切片技术获取与所述切片准则相关的程序代码子集,从而将所述检测对象切分成多个相互独立的子对象。
优选地,所述解析检测对象源程序代码,生成源程序的中间表述形式,包括:读取检测对象源程序代码,进行词法分析及语法分析,生成抽象语法树和控制流程图,在所述控制流程图的基础上,进行语义分析,生成程序依赖图;和/或
所述获取切片准则包括:从检测规则或已知类型缺陷中提取所述切片准则,或者接收用户自定义的所述切片准则;其中,所述切片准则包含起始点和/或兴趣点。
优选地,所述对于每个切片准则,通过程序切片技术获取与所述切片准则相关的程序代码子集,包括:
对于只包含起始点的切片准则,采用前向切片的方法遍历所述程序依赖图获取与对应切片准则相关的程序代码子集;
对于只包含兴趣点的切片准则,采用后向切片的方法遍历所述程序依赖图获取与对应切片准则相关的程序代码子集;或者
对于包含起始点和兴趣点的切片准则,采用砍片的方法遍历所述程序依赖图获取与对应切片准则相关的程序代码子集。
优选地,所述并行执行对各子对象的代码缺陷静态检测,包括:
并行运行多个代码缺陷检测引擎,对各个子对象进行缺陷检测。
本发明?#22266;?#20379;了一种基于程序切片的代码缺陷静态检测的并行化装置, 该装置包括:
切分模块,用于利用程序切片技术,将检测对象切分成多个相互独立的子对象;以及
检测模块,用于并行执行对各子对象的代码缺陷静态检测。
优选地,所述切分模块包括:
解析单元,用于解析检测对象源程序代码,生成源程序的中间表述形式;
获取单元,用于获取切片准则;以及
切分单元,用于对于每个切片准则,通过程序切片技术将所述检测对象切分成多个相互独立的子对象。
优选地,所述解析单元,具体用于:读取检测对象源程序代码,进行词法分析及语法分析,生成抽象语法树和控制流程图,在所述控制流程图的基础上,进行语义分析,生成程序依赖图;和/或
所述获取单元,具体用于:从检测规则或已知类型缺陷中提取所述切片准则,或者接收用户自定义的所述切片准则;其中,所述切片准则包含起始点和/或兴趣点。
优选地,所述切片单元,具体用于:
对于只包含起始点的切片准则,采用前向切片的方式遍历所述程序依赖图获取与对应切片准则相关的程序代码子集;
对于只包含兴趣点的切片准则,采用后向切片的方式遍历所述程序依赖图获取与对应切片准则相关的程序代码子集;或者
对于包含起始点和兴趣点的切片准则,采用砍片的方式遍历所述程序依赖图获取与对应切片准则相关的程序代码子集。
优选地,所述检测模块,具体用于:并行运行多个代码缺陷检测引擎,对各个子对象进行缺陷检测。
本发明利用程序切片技术将待检测对象划分成多个相互独立的子对象;这些子对象的检测过程互不干扰,可以并行执行对各子对象的代码缺陷静态 检测,从而提高静态检测的效率和精度。
附图说明
图1为本发明基于程序切片的代码缺陷静态检测的并行化方法实施例的流程图;
图2为本发明利用程序切片技术对检测对象进行划分的流程图;
图3为本发明基于程序切片的代码缺陷静态检测的并行化装置实施例的结构示意图。
具体实施方式
为使本发明的目的、技术方案和优点更加清楚明白,下文中将结合附图对本发明的实施例进行详细说明。需要说明的是,在不冲突的情况下,本申请中的实施例及实施例中的特征可以相互?#25105;?#32452;合。
如图1所示,为本发明基于程序切片的代码缺陷静态检测的并行化方法实施例的流程图,该方法包括如下步骤:
步骤101、利用程序切片技术,将检测对象切分成多个相互独立的子对象;
步骤102、并行执行对各子对象的代码缺陷静态检测。
并行运行多个代码缺陷检测引擎,对各个子对象进行缺陷检测。
其中,步骤101的具体实现过程如图2所示,具体包括如下步骤:
步骤1011、解析检测对象源程序代码,生成源程序的中间表述形式;
读取源程序代码,进行词法分析及语法分析,生成抽象语法树和控制流程图,并在控制流程图的基础上,生成程序依赖图。抽象语法树描述了源程序代码的语法结构;控制流程图描述了程序的潜在执行路径,在控制流程图,每个节点代表一条程序语句,而边表示执行流的可能跳转路径;程序依赖图描述了程序语句之间的控制依赖及数据依赖关系,由控制依赖子图和数据依 赖子图组成。下面简单介绍从控制流程?#25216;?#31639;控制依赖子图及数据依赖子图的方法:
控制依赖子图描述了程序语句间的控制依赖关系。在控制流程图中,如果节点n2是否执行取决于节点n1的执行结果,则称节点n2控制依赖于节点n1(每个节点代表一条程序语句)。节点n2控制依赖于节点n1当且仅当满足:(1)存在从n1到n2的路径P,对于P上的任何节点n3(除n1和n2之外),n2为n3的后支配节点;(2)n2不是n1的后支配节点。如果n2控制依赖于n1,则在控制依赖子图中,从n1到n2存在一条控制依赖边,当n1为条件语句时,边的标签为T或F,当n2在n1的True分支执行时为T,当n2在n1的False分支执行时为F。在控制流程图中,节点n1为n2的支配节点,当且仅当从控制流程图的入口到n2的所有路径都经过n1;节点n1为n2的后支配节点,当且仅当从n2到控制流程图的出口节点都经过n1;
数据依赖子图描述了程序语句间的数据依赖关系。在控制流图中,如果存在某一变量v在节点n1处被定义,在节点n2处被使用,且存在从n1到n2的一条可执行路径,在该路径上,除n1、n2之外,不存在对变量v的定义节点,则称n2数据依赖于n1;此时在数据依赖子图上存在一条从n1到n2的数据依赖边,边的标签为v,表示n2通过变量v数据依赖于n1。变量v在语句n被定义指语句n写变量v的值,而变量v在语句n被引用指语句n读变量v的值;
控制依赖子图和数据依赖子图合并在一起,形成程序依赖图;
步骤1012、获取切片准则;
程序切片是一种代码分解技术,从源程序中寻找与兴趣点相关的代码子集。兴趣点被称为切片准则,用于确定哪些代码应该被保留,哪些代码应该被消除。一个切片准则包含切片的起始(source)点、兴趣(sink)点。一个切片准则至少包含一个source点或sink点,但可以同时拥有多个source点或sink点。获取切片准则的关键在于确定source点和sink点。在本实施方式中,切片准则有多种来源,可?#28304;?#26816;测规则或已知类型缺陷中提取,也可以由用户自定义。
从检测规则或已知类型缺陷中提取切片准则:在代码缺陷静态检测中,检测规则用于指定程序中哪些代码正常,哪些代码存在安全隐患。每个检测规则都指定了从代码的什么地方开?#35745;?#37197;,并指定在代码的什么地方终止,因?#31169;?#24320;?#35745;?#37197;的位置作为切片准则的source点,而匹配终止的地方作为切片准则的sink点。?#34892;?#26816;测规则既明确定义了开?#35745;?#37197;的位置,?#32622;?#30830;定义?#31169;?#26463;匹配的位置,此时的切片准则即包含source点,又包含终止点;当检测规则只明确定义了开?#35745;?#37197;位置时,此时切片准则只包含source点;当检测规则只明确定义了终止匹配位置时,此时切片准则只包含sink点。采用同样的方法可?#28304;?#24050;知类型缺陷中获取切片准则;
用户自定义切片准则:切片准则也可以由用户定义,用户指定?#34892;?#36259;的source点或sink点;
步骤1013、对于每个切片准则,通过程序切片技术获取与切片准则相关的程序代码子集,从而将检测对象切分成多个相互独立的子对象。
根据切片准则的不同,采用不同的切片方法。对于只定义了source点的切片准则,采用前向切片的方法;对于只定义了sink点的切片准则,采用后向切片的方法;而对于source点和sink点都定义了的切片准则,则采用砍片的切片方法。
前向切片用于发现受兴趣点(source点)影响的程序代码的集合,当切片准则未明确定义sink点时,适合采用该切片方法;
后向切片用于发现影响兴趣点(sink点)的程序代码的集合,当切片准则未明确定义source点时,适合采用该切片方法;
砍片用于发现受source点影响,而又影响sink点的程序代码的集合,当切片准则既明确定义了source点,?#32622;?#30830;定义了sink点时,适合采用该切片方法。
其中,步骤102并行执行对步骤101产生的各子对象的代码缺陷静态检测。
步骤101产生的子对象之间也是相互独立的,对各个子对象的代码缺陷静态检测过程互不干扰,因此可以并行检测,即每个子对象对应一个检测任 务。并行检测可以有多种方式,可以在一台机器上运行多个检测进程分别执行检测任务,也可以将检测任务分配到不同的机器上执行。
由此可见,本发明应用程序切片技术来切分代码缺陷静态检测的检测对象,从而实现并行化。检测对象被拆分成多个独立的子对象,这些子对象之间互不干扰,因此可以并行检测。一方面,由于代码缺陷静态检测的时间开销(随程序中的分支数的增加?#25163;?#25968;增长)?#23545;?#22823;于程序切片的时间开销(在多项式时间内可以完成),本发明能?#24739;?#22823;的提高静态检测的效率;另一方面,由于程序切片消除了与检测目标不相关的程序代码,?#26723;?#20102;检测对象的复杂度,本发明还能够在一定程度上提高静态检测的检测精度。
如图3所示,为本发明基于程序切片的代码缺陷静态检测的并行化装置实施例的结构示意图,该装置包括:
切分模块31,用于利用程序切片技术,将检测对象切分成多个相互独立的子对象;以及
检测模块32,用于并行执行对各子对象的代码缺陷静态检测。
其中,所述切分模块包括:解析单元,用于解析检测对象源程序代码,生成源程序的中间表述形式;获取单元,用于获取切片准则;以及,切分单元,用于对于每个切片准则,通过程序切片技术将所述检测对象切分成多个相互独立的子对象。
所述检测模块,具体用于:并行运行多个代码缺陷检测引擎,对各个子对象进行缺陷检测。
另外,所述解析单元,具体用于:读取检测对象源程序代码,进行词法分析及语法分析,生成抽象语法树和控制流程图,在所述控制流程图的基础上,进行语义分析,生成程序依赖图。和/或,所述获取单元,具体用于:从检测规则或已知类型缺陷中提取所述切片准则,或者接收用户自定义的所述切片准则;其中,所述切片准则包含起始点和/或兴趣点。
进一步地,所述切片单元,具体用于:对于只包含起始点的切片准则, 采用前向切片的方式遍历所述程序依赖图获取与对应切片准则相关的程序代码子集;对于只包含兴趣点的切片准则,采用后向切片的方式遍历所述程序依赖图获取与对应切片准则相关的程序代码子集;或者,对于包含起始点和兴趣点的切片准则,采用砍片的方式遍历所述程序依赖图获取与对应切片准则相关的程序代码子集。
上述基于程序切片的代码缺陷静态检测的并行化装置,利用程序切片技术将待检测对象划分成多个相互独立的子对象;这些子对象的检测过程互不干扰,可以并行执行对各子对象的代码缺陷静态检测,从而提高静态检测的效率和精度。
本领域普通技术人员可以理解上述方法中的全部或部分步骤可通过程序来指令相关?#24067;?#23436;成,上述程序可?#28304;?#20648;于计算机可读存储介质中,如只读存储器、磁盘或光盘?#21462;?#21487;选地,上述实施例的全部或部分步骤也可以使用一个或多个集成电路?#35789;?#29616;。相应地,上述实施例中的各模块/单元可以采用?#24067;?#30340;形式实现,也可以采用软件功能模块的形式实现。本发明不限制于任何特定形式的?#24067;?#21644;软件的结合。
以上实施例仅用?#36816;?#26126;本发明的技术方案而非限制,仅仅参照较佳实施例对本发明进行了详细说明。本领域的普通技术人员应当理解,可以对本发明的技术方?#38468;?#34892;修改或者等同替换,而不脱离本发明技术方案的精神和范围,均应涵盖在本发明的权利要求范围当中。

关于本文
本文标题:基于程序切片的代码缺陷静态检测的并行化方法及装置.pdf
链接地址:http://www.pqiex.tw/p-6115886.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
平码五不中公式规律 澳洲幸运8官网 黑龙江十一选五遗漏期数 双色球单式投和复式投注 体彩四川金7乐怎么玩 辽宁十一选五任五遗漏 北京十一选五中奖号码 怎样控制棋牌游戏 印度股票指数 这期福彩开奖什么号 四川金7乐投注技巧