研讨数组基于区间集Cppcheck数组边界缺陷检测站
最后更新时间：2024-03-12
作者：用户投稿
本站原创
点赞:22371
浏览:97831
本站原创
点赞:22371
浏览:97831
论文导读：12下一页
摘要：
针对开源软件Cppcheck误报率和漏报率过高，且不能检测出运行时程序缺陷等问题，基于Cppcheck程序，提出了抽象区间集算法，并将其应用于数组边界缺陷检测。在Cppcheck框架内，通过引入区间集概念，建立每个程序点变量和表达式的整型区间集和数组区间集，并由此定位出程序中的矛盾点，最终检测出程序缺陷。与Cppcheck相比较，所提算法的查准率提高18.5%，漏报率降低22.5%，误报率提高3.5%。实验结果表明，该方法能有效地检测出运行程序缺陷，并提高Cppcheck缺陷检测性能。
关键词：
Cppcheck；抽象区间集；数组越界；变量；表达式
0引言
软件缺陷是存在于软件中、不期望或不可接受的偏差，以静态形式存在于软件的内部，是软件开发过程中人为错误的结果。当软件运行于某一特定条件时将出现软件故障（即软件缺陷被激活），所以软件缺陷检测一直是软件测试技术发展的瓶颈。
无论是商业软件领域还是开源社区，都有C/C++代码缺陷自动检测工具的开发。在商源于：论文格式字体www.7ctime.com
业领域，具有代表性的工具有PCLint和Parasoft C/C++Test工具包，其采用技术相对成熟，属于非开源软件，技术内幕没有公开，且配置规则和规则扩展方面需要用户编写脚本程序，造成软件的使用相对繁琐。在开源领域，具有代表的工具有ITS4、Splint和Cppcheck等。ITS4仅基于词法分析，无法分析代码的语义，即无法分析一个标识符代表何种意义，相比之下，Splint基于模糊静态分析，加上用户添加的扩展标记，检测准确率比ITS4要好，但目前只针对于C语言，无法检测出C++中缺陷，并且依赖用户添加的扩展标记，给用户带来了严重负担。Cppcheck是针对C/C++语言且基于缺陷模式的静态软件缺陷检测工具，因其开源和使用简单等特点在软件测试中得到广泛应用。然而大部分程序中存在分支和循环语句，有些值只有在程序运行时候才能确定，但Cppcheck不能对运行程序时的缺陷进行检测，所以提出利用计算机系统语义模型的近似理论来有效分析程序量的取值区间，从而有效地排除零缺陷，数组越界，整数溢出等多种运行时缺陷。
静态缺陷方法不需要运行程序，通过对程序代码进行静态分析，来查找程序中缺陷，类型推导、符号执行[3]、抽象解释[4-6]等是常用的静态缺陷检测方法。类型推导是由机器自动推导出程序量和函数类型，但它不能解决与程序控制流相关的问题。符号执行是用抽象符号表示程序量的值，来模拟程序执行，但在处理大量程序时，程序的执行路径呈指数级增长，运用符号执行进行检查时，需要选取一定数量的路径进行分析[3]。抽象解释用于构造和逼近程序不动点理论，是一种逼近程序语义的静态分析技术，它能处理计算机科学中不可判定问题和复杂问题的有效方法[4-6]。传统的方法利用经典区间抽象域[7]也即抽象区间来表示程序量取值范围，来检测程序中的矛盾点，但在很多情况下单个数值型变量区间表示的精度不够，例如：整型变量i区间是[2，4]或[9，10]用区间运算表示区间为[2，10]，但包含了冗余区间，所以本文对经典区间抽象进行了扩展，引入了数值型区间集代数[8-10]，提高区间表示的精度，用于数组越界检测，能够高效计算程序量的值取值区间，从而排除大部分的运行时缺陷。
本文首先对开源软件Cppcheck进行了分析和研究；然后借鉴抽象解释的思想，对经典抽象区间域进行了扩展，提出抽象区间集概念，用于数组越界检测，并在循环语句中利用区间的拓展算子[11]和收窄算子[12]对区间进行快速收敛并提高区间检测精度；最后通过实验验证提出的区间集算法，能有效解决程序运行时数组越界等缺陷，并提高了Cppcheck查准率和漏报率。
1区间运算
摘要：
针对开源软件Cppcheck误报率和漏报率过高，且不能检测出运行时程序缺陷等问题，基于Cppcheck程序，提出了抽象区间集算法，并将其应用于数组边界缺陷检测。在Cppcheck框架内，通过引入区间集概念，建立每个程序点变量和表达式的整型区间集和数组区间集，并由此定位出程序中的矛盾点，最终检测出程序缺陷。与Cppcheck相比较，所提算法的查准率提高18.5%，漏报率降低22.5%，误报率提高3.5%。实验结果表明，该方法能有效地检测出运行程序缺陷，并提高Cppcheck缺陷检测性能。
关键词：
Cppcheck；抽象区间集；数组越界；变量；表达式
0引言
软件缺陷是存在于软件中、不期望或不可接受的偏差，以静态形式存在于软件的内部，是软件开发过程中人为错误的结果。当软件运行于某一特定条件时将出现软件故障（即软件缺陷被激活），所以软件缺陷检测一直是软件测试技术发展的瓶颈。
无论是商业软件领域还是开源社区，都有C/C++代码缺陷自动检测工具的开发。在商源于：论文格式字体www.7ctime.com
业领域，具有代表性的工具有PCLint和Parasoft C/C++Test工具包，其采用技术相对成熟，属于非开源软件，技术内幕没有公开，且配置规则和规则扩展方面需要用户编写脚本程序，造成软件的使用相对繁琐。在开源领域，具有代表的工具有ITS4、Splint和Cppcheck等。ITS4仅基于词法分析，无法分析代码的语义，即无法分析一个标识符代表何种意义，相比之下，Splint基于模糊静态分析，加上用户添加的扩展标记，检测准确率比ITS4要好，但目前只针对于C语言，无法检测出C++中缺陷，并且依赖用户添加的扩展标记，给用户带来了严重负担。Cppcheck是针对C/C++语言且基于缺陷模式的静态软件缺陷检测工具，因其开源和使用简单等特点在软件测试中得到广泛应用。然而大部分程序中存在分支和循环语句，有些值只有在程序运行时候才能确定，但Cppcheck不能对运行程序时的缺陷进行检测，所以提出利用计算机系统语义模型的近似理论来有效分析程序量的取值区间，从而有效地排除零缺陷，数组越界，整数溢出等多种运行时缺陷。
静态缺陷方法不需要运行程序，通过对程序代码进行静态分析，来查找程序中缺陷，类型推导、符号执行[3]、抽象解释[4-6]等是常用的静态缺陷检测方法。类型推导是由机器自动推导出程序量和函数类型，但它不能解决与程序控制流相关的问题。符号执行是用抽象符号表示程序量的值，来模拟程序执行，但在处理大量程序时，程序的执行路径呈指数级增长，运用符号执行进行检查时，需要选取一定数量的路径进行分析[3]。抽象解释用于构造和逼近程序不动点理论，是一种逼近程序语义的静态分析技术，它能处理计算机科学中不可判定问题和复杂问题的有效方法[4-6]。传统的方法利用经典区间抽象域[7]也即抽象区间来表示程序量取值范围，来检测程序中的矛盾点，但在很多情况下单个数值型变量区间表示的精度不够，例如：整型变量i区间是[2，4]或[9，10]用区间运算表示区间为[2，10]，但包含了冗余区间，所以本文对经典区间抽象进行了扩展，引入了数值型区间集代数[8-10]，提高区间表示的精度，用于数组越界检测，能够高效计算程序量的值取值区间，从而排除大部分的运行时缺陷。
本文首先对开源软件Cppcheck进行了分析和研究；然后借鉴抽象解释的思想，对经典抽象区间域进行了扩展，提出抽象区间集概念，用于数组越界检测，并在循环语句中利用区间的拓展算子[11]和收窄算子[12]对区间进行快速收敛并提高区间检测精度；最后通过实验验证提出的区间集算法，能有效解决程序运行时数组越界等缺陷，并提高了Cppcheck查准率和漏报率。
1区间运算