一种面向安全检查的代码静态分析方法
一种面向安全检查的代码静态分析方法
【技术领域】
[0001]本发明涉及软件安全漏洞检测技术领域，尤其涉及一种面向安全检查的代码静态分析方法。
【背景技术】
[0002]静态分析是指在不运行待检测程序的情况下，通过分析程序源代码中的语法、过程和程序结构等来验证程序的正确性。它通过检查代码是否与设计相符、代码对安全编码标准的遵循程度、代码中逻辑正确性和结构的合理性，发现代码中存在的潜在安全问题，包括代码检查和代码结构分析等。静态检测技术的检测对象是软件的源代码。该类技术不需要动态执行程序的源代码，也不需要获得程序编译时的信息，而是在具体检测代码中存在的问题之前，扫描软件源代码，运用词法分析、语法分析以及语义分析等技术生成源代码的某种中间表示，然后再通过各种技术对中间表示进行扫描，生成相应的检测模型，最后根据各种检测规则分析模型来查找程序源代码中存在的安全缺陷。
[0003]抽象解释是静态分析的形式化框架。静态分析仅跟踪用户关心的程序属性，所以它对程序语义的解释是程序实际语义的近似。抽象解释需要用户根据被检测安全漏洞设计具体的抽象解释函数和抽象域。目前，主流的静态分析方法都是抽象解释的实例。在对程序进行语法分析时，在保持被测程序原有逻辑完整性的基础上，可以在程序的不同部位插入一些探针，通过探针的执行获取程序运行测试用例的特征数据，如调用分支的执行次数等。
[0004]数据流分析收集程序中每个点所计算的值的可能集合，这些集合指明变量的值在何处产生以及在什么地方使用，指明如何处理、存储、传递数据，以及将数据传递到何处等。对程序源码进行数据流分析，首先需要将被分析的代码划分为基本块(程序子序列由顺序执行的指令组成)，然后以这些基本块为结点给程序构造控制流图。数据流分析以基本块和控制流程图为基础，控制流图是函数体的形式化表示，可以表达程序结构，在安全分析阶段起着重要作用。控制流图通过遍历抽象语法树，依据程序的执行规则，分析程序的可能执行路径，最终生成程序调用图供后续检测工作使用。
[0005]程序调用图是静态分析安全检查中常用的描述函数之间调用关系的结构之一，相比于其他结构，程序调用图更为直观，易于理解和使用。函数递归调用可以分为直接递归调用和间接递归调用两种。一个可终止的程序在进入递归调用后，必定会在某条件满足后退出递归，否则程序会永不停息的递归下去。因此可以判定构成递归的所有函数调用中，至少有一个位于条件分支中。
[0006]在自底向上的静态安全检查中，生成拓扑序列的前提是控制流图中没有环，但是递归函数的存在使控制流图存在环，从而无法确定该环中各个函数的调用顺序，因此必须解除递归函数依赖。解除递归函数的依赖关系后，相应的函数依赖信息也随之丢失。
[0007]如图1和2所示，在图1中，函数f2存在直接递归函数调用f2 — f2,函数Π、f3、f6和f4，函数fl、f5、f6和f4均存在间接递归函数调用，函数递归调用环分别为Π — f3 — f6 — f4 — fl和fl — f5 — f6 — f4 — fl。现有解除递归函数依赖的技术是基于程序调用图通过比较控制流图中环的函数节点的入度和出度选择被解除的边，即找出递归调用环中具有最大入度的f(x)和与f(x)相连的出度最小的f(y)，删除二者的调用关系。在图1中的3个函数递归调用环中，直接递归函数调用f2 — f2直接解除；在间接递归函数调用fl — f3 — f6 — f4 — fl中，函数fl节点具有最大的入度2，在与函数fl节点相连的函数节点中，函数f3节点具有最小的出度1，因此，将fl — f3的函数依赖关系解除；同理，在间接递归函数调用fl — f5 — f6 — f4 — fl中，函数fl节点具有最大的入度2，在与函数fI节点相连的函数节点中，函数f5节点具有最小的出度1，因此，将fl — f5的函数依赖关系解除。解除递归函数依赖后的程序调用图如图2所示。该技术只分析了程序的控制流程图，具有易实现、速度快的优点，但其对程序的语义分析不足，容易解除重要的函数依赖，造成较大的损失，对检测结果的精确性影响较大。
【发明内容】
[0008]有鉴于此，本发明提供了一种面向安全检查的代码静态分析方法，将两函数之间的调用次数作为两者之间条件调用边的权值，并将权值作为两函数依赖重要性，可根据该依赖的重要性，解除递归环中权值较小的条件调用边，如此，在尽量减少解除边的数目的同时减少重要依赖的损失，提高程序漏洞的检测效率。
[0009]为了解决上述技术问题，本发明是这样实现的:
[0010]一种面向安全检查的代码静态分析方法，包括如下步骤:
[0011]步骤1、对待分析的程序代码进行词法分析，即将程序代码中的字符流分割为独立的单词；
[0012]步骤2、将步骤I分割得到的各个独立的单词进行语法分析，得到抽象语法树；
[0013]步骤3、基于步骤2的抽象语法树，得到控制流图；
[0014]步骤4、根据步骤3得到的所述控制流程图，得到函数调用图；
[0015]步骤5、对程序代码的函数依赖关系进行解除，具体为:
[0016]S51、计算所述函数调用图中两两函数之间的调用次数；
[0017]S52、在所述函数调用图的基础上，针对任意两个有调用关系的函数，将两者之间的调用次数作为权值并赋值给该两个函数之间的条件调用边，得到带权依赖关系的函数调用图；
[0018]S53、查找所述带权依赖关系的函数调用图中的递归环，针对任意一个递归环X，检测与该递归环X没有共用条件调用边的递归环，将检测到的递归环中权值最小的条件调用边解除，遍历函数调用图中所有的递归环，得到解除函数依赖关系的函数调用图；
[0019]步骤6、依照所述步骤5得到的解除了函数依赖关系的函数调用图，使用静态分析方法对程序代码进行安全缺陷的检测，并将检测结果以文本形式存储并输出，供程序员查看。
[0020]本发明具有如下有益效果:
[0021](I)本发明针对目前软件安全漏洞检测方法在代码静态分析安全检查中漏报率和误报率无法与检测软件的运行效率兼得的问题，本发明将消除函数递归技术引入到软件安全漏洞静态分析中:首先生成程序安全检查的中间表示如控制流图和程序调用图等，获得程序的函数依赖关系；若程序调用图中存在递归环，则意味着函数依赖中存在递归。其次得到程序调用图中各依赖的权值；最后根据依赖重要性即权值决定要解除的依赖关系，提高程序漏洞的检测效率的同时，尽量降低解除递归函数依赖造成的检测损失。
【附图说明】
[0022]图1为现有技术中存在递归的函数调用图。
[0023]图2为利用现有的方法解除递归的函数调用图。
[0024]图3为利用本发明的方法解除递归的函数调用图。
【具体实施方式】
[0025]下面结合附图并举实施例，对本发明进行详细描述。
[0026]步骤1、对待分析的程序代码进行词法分析，即将程序代码中的字符流分割为独立的单词:
[0027]以待分析的程序代码(源文件)作为输入，逐行扫描程序文件中的字符，根据编程语言约束生成的正则表达式，把源文件中的字符流分割为一个个的单词。该单词流将作为语法分析器的输入。此过程会自动过滤掉源程序中的空白符、制表符等对文件分析无帮助的字符，并将有关单词序列的信息写入符号表。
[0028]步骤2、将步骤I分割得到的各个独立的单词进行语法分析，得到 抽象语法树:每一种程序设计语言都具有描述自己程序语法结构的一组规则，使得该语言所写的程序能够正确运行，并被该语言的编译器所理解，进而生成执行文件。语法分析就是以词法分析的输出作为自己的输入，检验源代码的标号流是否符合语法规则。一般情况下，一组语法规则往往用一组文法表示。而抽象语法树就是根据文法进行推导而形成的一种树，它使得程序更具层次性，便于理解和操作，因此抽象语法树不仅仅是用于语法检查，而且还是后续编译工作或安全缺陷检测工作的基础。
[0029]步骤3、基于步骤2的抽象语法树，得到控制流图:控制流图是静态分析后续工作的基础，在检测代码中的安全缺陷等操作时需要遍历控制流图，模拟程序的执行路径，根据操作类型提取相关的变量信息，并依此检测代码中存在的安全缺陷。
[0030]步骤4、根据步骤3得到的所述控制流程图，得到函数调用图；通过对控制流图的分析，检查程序源码中的数组越界、使用未初始化变量和空指针解引用等错误，并且收集相关信息写入中间文件中，便于全局分析的进行。
[0031]步骤5、对函数依赖关系进行解除，具体为:
[0032]S51、计算所述函数调用图中两两函数之间的调用次数；
[0033]为了获得函数调用的信息，插装器在各程序结构中插入相应的探针。用一个二维整型数组counter来记录程序中每个函数调用经历的次数。程序执行完毕后，根据counter数组的值即可得知各函数的调用情况。
[0034]根据函数调用的触发条件可将函数依赖分为条件依赖和必然依赖。C/C++程序中位于if-then-else，for，switch_case，while语句块中的函数调用可能是有条件的也有可能是必然的，但是条件依赖必定出现在这些语句中。必然调用在程序执行中必定发生，而条件调用的发生需要满足一定的条件，因此必然依赖的优先级要高于条件依赖。程序总是在条件调用点上终止递归，因此，解除递归依赖应该优先解除条件依赖边，这样较接近程序本身的语义。
[0035]S52、在所述函数调用图的基础上，针对任意两个有调用关系的函数，将两者之间的调用次数作为权值并赋值给该两个函数之间的条件调用边，得到带权依赖关系的函数调用图；
[0036]通过对程序调用图的分析可以获得程序中所有函数的必然调用集合与条件调用集合，将必然调用所对应的二维数组的值设为最大值。
[0037]S53、查找所述带权依赖关系的函数调用图中的递归环，针对任意一个递归环X，检测与该递归环X没有共用条件调用边的递归环，将检测到的递归环中权值最小的条件调用边解除。
[0038]在带权程序调用图中查找环的关键是做到高效，尽量避免重复查找，而且要保证能够查出所有的环。此外，查找环的目的是解除环，因此要将查出的所有的环记录，包括构成环的所有的边信息。
[0039]解除递归环的关键是尽量减小由于解除依赖边造成的依赖损失。在带权程序调用图中，由于一个环中必然存在至少一条条件调用边，而且条件调用边的依赖的重要性次于必然调用。因此条件调用边是被解除边的首选。在同一个环中，如果存在多个条件调用边，选择使用频率较低的边，所谓使用频率是指共享一条条件调用边的环的数目。之所以这样，是因为解除一条使用频率低的边影响到的函数调用序列是最少的。此外由于带权程序调用图中可能同时存在多个环，为了提高解除环效率，避免反复执行查找环的操作，应该同时解除多个环。但是，解除某条边可能会同时解除了多个环，如果随意地同时解除一批环，有可能会解除一个环中的多条边，造成不必要的损失。因此，在每次解除环操作时，只解除互相不相邻的环。这样可以避免解除一个环中的多条边。对于直接递归环(只包含一条边)，直接将环解除。
[0040]基于程序语义的解除递归函数依赖的算法在构建程序的带权程序调用图的同时，记录了各函数调用的条件性信息，依据该信息将函数依赖划分为必然依赖程序安全检查中的函数依赖分析和条件依赖，以此作为解除递归函数依赖的依据，避免解除重要的依赖边，在解除带权程序调用图中的递归环时，优先解除使用频率低的条件依赖边，从而也尽量降低了解除环对函数依赖的影响。
[0041]步骤6、使用高级静态分析算法对采用步骤5的方法解除了函数依赖关系的程序代码进行安全缺陷的检测，并将检测结果以文本形式存储并输出，供程序员查看。在前段工作的基础上，逐步遍历程序的中间表示，利用区间运算等技术求解程序运行时可能的上下文执行环境，依据已有的约束条件检测程序中的安全缺陷。
[0042]从图1可以得知，在递归函数调用环fl — f3 — f6 — f4 — fl和Π — f5 — f6 — f4 — fl中，f6 — f4和f4 — fl是必然函数调用，即函数调用关系拥有最高的权重，不能被解除；若在程序实际执行中，fl — f3出现次数为7，即该调用关系权重为7，而f3 — f6出现次数为4，即该调用关系权重为4，因此，在在间接递归函数调用Π — f3 — f6 — f4 — fl中，须解除的调用关系为f3 — f6。同理，若fl — f5出现次数为10，而f5 — f6出现次数为8，须解除的调用关系为f5 — f6。直接递归函数调用f2 — f2直接解除即可。解除递归函数依赖后的程序调用图如图3所示。
[0043]综上所述，以上仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
【主权项】
1.一种面向安全检查的代码静态分析方法，其特征在于，包括如下步骤: 步骤1、对待分析的程序代码进行词法分析，即将程序代码中的字符流分割为独立的单词； 步骤2、将步骤I分割得到的各个独立的单词进行语法分析，得到抽象语法树； 步骤3、基于步骤2的抽象语法树，得到控制流图； 步骤4、根据步骤3得到的所述控制流程图，得到函数调用图； 步骤5、对程序代码的函数依赖关系进行解除，具体为: S51、计算所述函数调用图中两两函数之间的调用次数； S52、在所述函数调用图的基础上，针对任意两个有调用关系的函数，将两者之间的调用次数作为权值并赋值给该两个函数之间的条件调用边，得到带权依赖关系的函数调用图； S53、查找所述带权依赖关系的函数调用图中的递归环，针对任意一个递归环X，检测与该递归环X没有共用条件调用边的递归环，将检测到的递归环中权值最小的条件调用边解除，遍历函数调用图中所有的递归环，得到解除函数依赖关系的函数调用图； 步骤6、依照所述步骤5得到的解除了函数依赖关系的函数调用图，使用静态分析方法对程序代码进行安全缺陷的检测，并将检测结果以文本形式存储并输出，供程序员查看。
【专利摘要】本发明公开了一种面向安全检查的代码静态分析方法，该方法首先生成程序安全检查的中间表示如控制流图和程序调用图等，获得程序的函数依赖关系；若程序调用图中存在递归环，则意味着函数依赖中存在递归。其次得到程序调用图中各依赖的权值；最后根据依赖重要性即权值决定要解除的依赖关系，提高程序漏洞的检测效率的同时，尽量降低解除递归函数依赖造成的检测损失。
【IPC分类】G06F11/36, G06F21/56
【公开号】CN104899147
【申请号】CN201510347630
【发明人】胡昌振, 单纯, 吴露霞, 于泽群, 马锐
【申请人】北京理工大学
【公开日】2015年9月9日
【申请日】2015年6月19日
【技术领域】
[0001]本发明涉及软件安全漏洞检测技术领域，尤其涉及一种面向安全检查的代码静态分析方法。
【背景技术】
[0002]静态分析是指在不运行待检测程序的情况下，通过分析程序源代码中的语法、过程和程序结构等来验证程序的正确性。它通过检查代码是否与设计相符、代码对安全编码标准的遵循程度、代码中逻辑正确性和结构的合理性，发现代码中存在的潜在安全问题，包括代码检查和代码结构分析等。静态检测技术的检测对象是软件的源代码。该类技术不需要动态执行程序的源代码，也不需要获得程序编译时的信息，而是在具体检测代码中存在的问题之前，扫描软件源代码，运用词法分析、语法分析以及语义分析等技术生成源代码的某种中间表示，然后再通过各种技术对中间表示进行扫描，生成相应的检测模型，最后根据各种检测规则分析模型来查找程序源代码中存在的安全缺陷。
[0003]抽象解释是静态分析的形式化框架。静态分析仅跟踪用户关心的程序属性，所以它对程序语义的解释是程序实际语义的近似。抽象解释需要用户根据被检测安全漏洞设计具体的抽象解释函数和抽象域。目前，主流的静态分析方法都是抽象解释的实例。在对程序进行语法分析时，在保持被测程序原有逻辑完整性的基础上，可以在程序的不同部位插入一些探针，通过探针的执行获取程序运行测试用例的特征数据，如调用分支的执行次数等。
[0004]数据流分析收集程序中每个点所计算的值的可能集合，这些集合指明变量的值在何处产生以及在什么地方使用，指明如何处理、存储、传递数据，以及将数据传递到何处等。对程序源码进行数据流分析，首先需要将被分析的代码划分为基本块(程序子序列由顺序执行的指令组成)，然后以这些基本块为结点给程序构造控制流图。数据流分析以基本块和控制流程图为基础，控制流图是函数体的形式化表示，可以表达程序结构，在安全分析阶段起着重要作用。控制流图通过遍历抽象语法树，依据程序的执行规则，分析程序的可能执行路径，最终生成程序调用图供后续检测工作使用。
[0005]程序调用图是静态分析安全检查中常用的描述函数之间调用关系的结构之一，相比于其他结构，程序调用图更为直观，易于理解和使用。函数递归调用可以分为直接递归调用和间接递归调用两种。一个可终止的程序在进入递归调用后，必定会在某条件满足后退出递归，否则程序会永不停息的递归下去。因此可以判定构成递归的所有函数调用中，至少有一个位于条件分支中。
[0006]在自底向上的静态安全检查中，生成拓扑序列的前提是控制流图中没有环，但是递归函数的存在使控制流图存在环，从而无法确定该环中各个函数的调用顺序，因此必须解除递归函数依赖。解除递归函数的依赖关系后，相应的函数依赖信息也随之丢失。
[0007]如图1和2所示，在图1中，函数f2存在直接递归函数调用f2 — f2,函数Π、f3、f6和f4，函数fl、f5、f6和f4均存在间接递归函数调用，函数递归调用环分别为Π — f3 — f6 — f4 — fl和fl — f5 — f6 — f4 — fl。现有解除递归函数依赖的技术是基于程序调用图通过比较控制流图中环的函数节点的入度和出度选择被解除的边，即找出递归调用环中具有最大入度的f(x)和与f(x)相连的出度最小的f(y)，删除二者的调用关系。在图1中的3个函数递归调用环中，直接递归函数调用f2 — f2直接解除；在间接递归函数调用fl — f3 — f6 — f4 — fl中，函数fl节点具有最大的入度2，在与函数fl节点相连的函数节点中，函数f3节点具有最小的出度1，因此，将fl — f3的函数依赖关系解除；同理，在间接递归函数调用fl — f5 — f6 — f4 — fl中，函数fl节点具有最大的入度2，在与函数fI节点相连的函数节点中，函数f5节点具有最小的出度1，因此，将fl — f5的函数依赖关系解除。解除递归函数依赖后的程序调用图如图2所示。该技术只分析了程序的控制流程图，具有易实现、速度快的优点，但其对程序的语义分析不足，容易解除重要的函数依赖，造成较大的损失，对检测结果的精确性影响较大。
【发明内容】
[0008]有鉴于此，本发明提供了一种面向安全检查的代码静态分析方法，将两函数之间的调用次数作为两者之间条件调用边的权值，并将权值作为两函数依赖重要性，可根据该依赖的重要性，解除递归环中权值较小的条件调用边，如此，在尽量减少解除边的数目的同时减少重要依赖的损失，提高程序漏洞的检测效率。
[0009]为了解决上述技术问题，本发明是这样实现的:
[0010]一种面向安全检查的代码静态分析方法，包括如下步骤:
[0011]步骤1、对待分析的程序代码进行词法分析，即将程序代码中的字符流分割为独立的单词；
[0012]步骤2、将步骤I分割得到的各个独立的单词进行语法分析，得到抽象语法树；
[0013]步骤3、基于步骤2的抽象语法树，得到控制流图；
[0014]步骤4、根据步骤3得到的所述控制流程图，得到函数调用图；
[0015]步骤5、对程序代码的函数依赖关系进行解除，具体为:
[0016]S51、计算所述函数调用图中两两函数之间的调用次数；
[0017]S52、在所述函数调用图的基础上，针对任意两个有调用关系的函数，将两者之间的调用次数作为权值并赋值给该两个函数之间的条件调用边，得到带权依赖关系的函数调用图；
[0018]S53、查找所述带权依赖关系的函数调用图中的递归环，针对任意一个递归环X，检测与该递归环X没有共用条件调用边的递归环，将检测到的递归环中权值最小的条件调用边解除，遍历函数调用图中所有的递归环，得到解除函数依赖关系的函数调用图；
[0019]步骤6、依照所述步骤5得到的解除了函数依赖关系的函数调用图，使用静态分析方法对程序代码进行安全缺陷的检测，并将检测结果以文本形式存储并输出，供程序员查看。
[0020]本发明具有如下有益效果:
[0021](I)本发明针对目前软件安全漏洞检测方法在代码静态分析安全检查中漏报率和误报率无法与检测软件的运行效率兼得的问题，本发明将消除函数递归技术引入到软件安全漏洞静态分析中:首先生成程序安全检查的中间表示如控制流图和程序调用图等，获得程序的函数依赖关系；若程序调用图中存在递归环，则意味着函数依赖中存在递归。其次得到程序调用图中各依赖的权值；最后根据依赖重要性即权值决定要解除的依赖关系，提高程序漏洞的检测效率的同时，尽量降低解除递归函数依赖造成的检测损失。
【附图说明】
[0022]图1为现有技术中存在递归的函数调用图。
[0023]图2为利用现有的方法解除递归的函数调用图。
[0024]图3为利用本发明的方法解除递归的函数调用图。
【具体实施方式】
[0025]下面结合附图并举实施例，对本发明进行详细描述。
[0026]步骤1、对待分析的程序代码进行词法分析，即将程序代码中的字符流分割为独立的单词:
[0027]以待分析的程序代码(源文件)作为输入，逐行扫描程序文件中的字符，根据编程语言约束生成的正则表达式，把源文件中的字符流分割为一个个的单词。该单词流将作为语法分析器的输入。此过程会自动过滤掉源程序中的空白符、制表符等对文件分析无帮助的字符，并将有关单词序列的信息写入符号表。
[0028]步骤2、将步骤I分割得到的各个独立的单词进行语法分析，得到 抽象语法树:每一种程序设计语言都具有描述自己程序语法结构的一组规则，使得该语言所写的程序能够正确运行，并被该语言的编译器所理解，进而生成执行文件。语法分析就是以词法分析的输出作为自己的输入，检验源代码的标号流是否符合语法规则。一般情况下，一组语法规则往往用一组文法表示。而抽象语法树就是根据文法进行推导而形成的一种树，它使得程序更具层次性，便于理解和操作，因此抽象语法树不仅仅是用于语法检查，而且还是后续编译工作或安全缺陷检测工作的基础。
[0029]步骤3、基于步骤2的抽象语法树，得到控制流图:控制流图是静态分析后续工作的基础，在检测代码中的安全缺陷等操作时需要遍历控制流图，模拟程序的执行路径，根据操作类型提取相关的变量信息，并依此检测代码中存在的安全缺陷。
[0030]步骤4、根据步骤3得到的所述控制流程图，得到函数调用图；通过对控制流图的分析，检查程序源码中的数组越界、使用未初始化变量和空指针解引用等错误，并且收集相关信息写入中间文件中，便于全局分析的进行。
[0031]步骤5、对函数依赖关系进行解除，具体为:
[0032]S51、计算所述函数调用图中两两函数之间的调用次数；
[0033]为了获得函数调用的信息，插装器在各程序结构中插入相应的探针。用一个二维整型数组counter来记录程序中每个函数调用经历的次数。程序执行完毕后，根据counter数组的值即可得知各函数的调用情况。
[0034]根据函数调用的触发条件可将函数依赖分为条件依赖和必然依赖。C/C++程序中位于if-then-else，for，switch_case，while语句块中的函数调用可能是有条件的也有可能是必然的，但是条件依赖必定出现在这些语句中。必然调用在程序执行中必定发生，而条件调用的发生需要满足一定的条件，因此必然依赖的优先级要高于条件依赖。程序总是在条件调用点上终止递归，因此，解除递归依赖应该优先解除条件依赖边，这样较接近程序本身的语义。
[0035]S52、在所述函数调用图的基础上，针对任意两个有调用关系的函数，将两者之间的调用次数作为权值并赋值给该两个函数之间的条件调用边，得到带权依赖关系的函数调用图；
[0036]通过对程序调用图的分析可以获得程序中所有函数的必然调用集合与条件调用集合，将必然调用所对应的二维数组的值设为最大值。
[0037]S53、查找所述带权依赖关系的函数调用图中的递归环，针对任意一个递归环X，检测与该递归环X没有共用条件调用边的递归环，将检测到的递归环中权值最小的条件调用边解除。
[0038]在带权程序调用图中查找环的关键是做到高效，尽量避免重复查找，而且要保证能够查出所有的环。此外，查找环的目的是解除环，因此要将查出的所有的环记录，包括构成环的所有的边信息。
[0039]解除递归环的关键是尽量减小由于解除依赖边造成的依赖损失。在带权程序调用图中，由于一个环中必然存在至少一条条件调用边，而且条件调用边的依赖的重要性次于必然调用。因此条件调用边是被解除边的首选。在同一个环中，如果存在多个条件调用边，选择使用频率较低的边，所谓使用频率是指共享一条条件调用边的环的数目。之所以这样，是因为解除一条使用频率低的边影响到的函数调用序列是最少的。此外由于带权程序调用图中可能同时存在多个环，为了提高解除环效率，避免反复执行查找环的操作，应该同时解除多个环。但是，解除某条边可能会同时解除了多个环，如果随意地同时解除一批环，有可能会解除一个环中的多条边，造成不必要的损失。因此，在每次解除环操作时，只解除互相不相邻的环。这样可以避免解除一个环中的多条边。对于直接递归环(只包含一条边)，直接将环解除。
[0040]基于程序语义的解除递归函数依赖的算法在构建程序的带权程序调用图的同时，记录了各函数调用的条件性信息，依据该信息将函数依赖划分为必然依赖程序安全检查中的函数依赖分析和条件依赖，以此作为解除递归函数依赖的依据，避免解除重要的依赖边，在解除带权程序调用图中的递归环时，优先解除使用频率低的条件依赖边，从而也尽量降低了解除环对函数依赖的影响。
[0041]步骤6、使用高级静态分析算法对采用步骤5的方法解除了函数依赖关系的程序代码进行安全缺陷的检测，并将检测结果以文本形式存储并输出，供程序员查看。在前段工作的基础上，逐步遍历程序的中间表示，利用区间运算等技术求解程序运行时可能的上下文执行环境，依据已有的约束条件检测程序中的安全缺陷。
[0042]从图1可以得知，在递归函数调用环fl — f3 — f6 — f4 — fl和Π — f5 — f6 — f4 — fl中，f6 — f4和f4 — fl是必然函数调用，即函数调用关系拥有最高的权重，不能被解除；若在程序实际执行中，fl — f3出现次数为7，即该调用关系权重为7，而f3 — f6出现次数为4，即该调用关系权重为4，因此，在在间接递归函数调用Π — f3 — f6 — f4 — fl中，须解除的调用关系为f3 — f6。同理，若fl — f5出现次数为10，而f5 — f6出现次数为8，须解除的调用关系为f5 — f6。直接递归函数调用f2 — f2直接解除即可。解除递归函数依赖后的程序调用图如图3所示。
[0043]综上所述，以上仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
【主权项】
1.一种面向安全检查的代码静态分析方法，其特征在于，包括如下步骤: 步骤1、对待分析的程序代码进行词法分析，即将程序代码中的字符流分割为独立的单词； 步骤2、将步骤I分割得到的各个独立的单词进行语法分析，得到抽象语法树； 步骤3、基于步骤2的抽象语法树，得到控制流图； 步骤4、根据步骤3得到的所述控制流程图，得到函数调用图； 步骤5、对程序代码的函数依赖关系进行解除，具体为: S51、计算所述函数调用图中两两函数之间的调用次数； S52、在所述函数调用图的基础上，针对任意两个有调用关系的函数，将两者之间的调用次数作为权值并赋值给该两个函数之间的条件调用边，得到带权依赖关系的函数调用图； S53、查找所述带权依赖关系的函数调用图中的递归环，针对任意一个递归环X，检测与该递归环X没有共用条件调用边的递归环，将检测到的递归环中权值最小的条件调用边解除，遍历函数调用图中所有的递归环，得到解除函数依赖关系的函数调用图； 步骤6、依照所述步骤5得到的解除了函数依赖关系的函数调用图，使用静态分析方法对程序代码进行安全缺陷的检测，并将检测结果以文本形式存储并输出，供程序员查看。
【专利摘要】本发明公开了一种面向安全检查的代码静态分析方法，该方法首先生成程序安全检查的中间表示如控制流图和程序调用图等，获得程序的函数依赖关系；若程序调用图中存在递归环，则意味着函数依赖中存在递归。其次得到程序调用图中各依赖的权值；最后根据依赖重要性即权值决定要解除的依赖关系，提高程序漏洞的检测效率的同时，尽量降低解除递归函数依赖造成的检测损失。
【IPC分类】G06F11/36, G06F21/56
【公开号】CN104899147
【申请号】CN201510347630
【发明人】胡昌振, 单纯, 吴露霞, 于泽群, 马锐
【申请人】北京理工大学
【公开日】2015年9月9日
【申请日】2015年6月19日
最新回复(0)