基于区域内存模型的空指针引用缺陷检测

doi:10.3969/j.issn.0372-2112.2014.09.013

电子学报 ›› 2014, Vol. 42 ›› Issue (9): 1744-1752.DOI: 10.3969/j.issn.0372-2112.2014.09.013

基于区域内存模型的空指针引用缺陷检测

董玉坤^1,2, 宫云战¹, 金大海¹

1. 北京邮电大学网络与交换技术国家重点实验室, 北京 100876;
2. 中国石油大学(华东)计算机与通信工程学院, 山东青岛 266580

收稿日期:2014-01-23 修回日期:2014-04-24 出版日期:2014-09-25
- 作者简介:
- 董玉坤 男，1981年出生于山东省梁山县.中国石油大学（华东）计算机与通信工程学院讲师，主要研究领域为软件测试，程序静态分析. E-mail：dongyk@upc.edu.cn；宫云战 男，1962年生于山东省乳山市，北京邮电大学网络与交换技术国家重点实验室教授，博士生导师.研究方向为软件测试、可信计算等.；金大海 男，1974年出生于辽宁省沈阳市，北京邮电大学网络与交换技术国家重点实验室副教授.研究方向为软件测试、软件安全等.
- 基金资助:
- 国家自然科学基金 (No.91318301，No.61202080）; 国家863高技术研究发展计划 (No.2012AA011201）

Null Pointer Dereference Defect Detected Based on Region-Based Memory Model

DONG Yu-kun^1,2, GONG Yun-zhan¹, JIN Da-hai¹

1. State Key Lab of Networking and Switching Tech, Beijing University of Posts and Telecommunications, Beijing 100876, China;
2. College of Computer and Communication Engineering, China University of Petroleum, Qingdao, Shandong 266580, China

Received:2014-01-23 Revised:2014-04-24 Online:2014-09-25 Published:2014-09-25
- Supported by:
- National Natural Science Foundation of China (No.91318301, No.61202080); National High Technology Research and Development Program of China (863 Program) (No.2012AA011201)

摘要/Abstract

摘要：

为了实现对C程序中空指针引用的充分检测，本文提出了一种基于区域内存模型的空指针引用缺陷检测方法.首先，提出了基于区域的符号化三值逻辑（Region-based Symbolic Three-Valued Logic，RSTVL），RSTVL能够描述C程序运行时内存中数据结构的形态信息与变量的存储状态，以及可寻址表达式间的各种关系；其次，给出了基于抽象语法树与函数摘要识别被引用指针方法；最后，结合基于RSTVL的数据流分析结果，将对被引用指针的检测转换为对相应区域的检测，给出了空指针引用缺陷检测的方法，通过函数摘要实现过程间的空指针引用缺陷检测.对比实验结果表明，本文方法在保证一定检测准确率的前提下，能够极大的减少空指针引用缺陷的漏报.

关键词: 空指针引用, 内存模型, 静态分析, 函数摘要, 缺陷检测

Abstract:

In order to fully detect null pointer dereference for C procedures,this paper introduces a method based on region-based memory model.Firstly,region-based symbolic three-valued logic(RSTVL)is proposed,which can describe shape of data structures,all kinds of memory states and relations of addressable expressions.Then,an approach to fully recognizing pointer dereferences based on abstract syntax tree and procedure summary is introduced.Furthermore,this paper introduces a null pointer dereference detection method,which translates pointer dereference detection into region detection applying the result of data flow analysis based on RSTVL,and detects interprocedural null pointer dereference based on procedure summary.Experiment results show that compared with DTSC_STVL and Klocwork9,the proposed method could dramatically reduce null pointer dereference false negative on the precondition of guarantee the detection precision.

Key words: null pointer dereference, memory model, static analysis, function summary, defect detection

中图分类号:

TP311.5

董玉坤, 宫云战, 金大海. 基于区域内存模型的空指针引用缺陷检测[J]. 电子学报, 2014, 42(9): 1744-1752.

DONG Yu-kun, GONG Yun-zhan, JIN Da-hai . Null Pointer Dereference Defect Detected Based on Region-Based Memory Model[J]. Acta Electronica Sinica, 2014, 42(9): 1744-1752.

参考文献

[1] Michael D, Graham Z, Samuel Z.Breadcrumbs:efficient context sensitivity for dynamic bug detection analyses[A].Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation[C].New York:ACM, 2010.13-24.
[2] Javelund K, Rosu G.Monitoring Java Programs with Java PathExplore[EB/OL].http://ti.arc.nasa.gov/m/pub-archive/264h/0264%20(Havelund).pdf, 2001-06-15.
[3] Manevich R, Sridharan M, Adams S.PSE:Explainint program failure via psotmortem static analysis[A].Proceedings of the 12th ACM SIGSOFT Twelfth International Symposium on Foundations of Software Engineering[C].New York:ACM, 2004.63-72.
[4] Ma XD, Wang J, Dong W.Computing must and may alias to detect null pointer dereference[A].Leveraging Applications of Formal Methods, Verification and Validation[C].Berlin Heidelberg:Springer, 2008, Vol_17.252-261.
[5] M Buss.Summary-Based Pointer Analysis Framework for Modular Bug Finding[D].Columbia:Columbia University, 2008.
[6] Y Xie, A Aiken.Saturn:A scalable framework for error detection using Boolean satisfiability[J].ACM Transactions on Programming Languages and Systems, 2007, 29(3):1-43.
[7] Madhavan Ravichandhran, Komondoor Raghavan.Null dereference verification via over-approximated weakest pre-conditions analysis[A].Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications[C].New York:ACM, 2011.1033-1052.
[8] Dong Yukun, Xing Ying, Jin Dahai, Gong Yunzhan.An approach to fully recognizing addressable expression[A].The 13th International Conference on Quality Software[C].Piscataway, NJ:IEEE, 2013.149-152.
[9] Hackett B, Rugina R.Region-based shape analysis with tracked locations[A].Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages[C].USA:ACM, 2005.310-323.
[10] Zhao Yunshan, Wang Yawen, Gong Yunzhan, et al.STVL:Improve the precision of static defect detection with symbolic three-valued logic[A].Proceedings of the 8th Asia-Pacific Software Engineering Conference[C].NJ:IEEE, 2011.179-186.
[11] 王雅文, 宫云战, 肖庆, 杨朝红.基于抽象解释的变量值范围分析及应用[J].电子学报, 2011, 39(2):296-303. Wang Yawen, Gong Yunzhan, Xiao Qing, Yang Zhaohong.A method of variable range analysis based on abstract interpretation and its applications[J].Acta Electronica Sinica, 2011, 39(2):296-303.(in Chinese)
[12] 董玉坤, 金大海, 宫云战, 邢颖.基于区域内存模型的C程序静态分析[J].软件学报, 2014, 25(2):357-372. Dong Yukun, Jin Dahai, Gong Yunzhan, Xing Ying.Static analysis of C programs via region-based memory model[J].Journal of Software, 2014, 25(2):357-372.(in Chinese)
[13] Zhao Yunshan, Gong Yunzhan, et al.Context-sensitive interprocedural defect detection based on a unified symbolic procedure summary model[A].Proceedings of the 11th International Conference on Quality Software[C].NJ:IEEE, 2011.51-56.

基于区域内存模型的空指针引用缺陷检测

Null Pointer Dereference Defect Detected Based on Region-Based Memory Model

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

[1]	范书平, 万里, 姚念民, 张岩, 马宝英. 基于关键用例获取的测试用例排序方法[J]. 电子学报, 2022, 50(1): 149-156.
[2]	李鹏伟, 姜宇谦, 薛飞扬, 黄佳佳, 徐超. 一种基于深度学习的强对抗性Android恶意代码检测方法[J]. 电子学报, 2020, 48(8): 1502-1508.
[3]	师奕兵, 罗清旺, 王志刚, 张伟, 马东. 基于多元接收线圈的管道局部缺陷检测方法研究[J]. 电子学报, 2018, 46(1): 197-202.
[4]	马森, 赵文, 习翔宇, 王栋伟. 基于值依赖分析的空指针解引用检测[J]. 电子学报, 2015, 43(4): 647-651.
[5]	郭曦, 王盼. 基于动态协同双向映射的相似执行路径生成方法[J]. 电子学报, 2014, 42(11): 2168-2173.
[6]	任武. 通过用况聚类促进软件结构恢复的方法[J]. 电子学报, 2013, 41(7): 1412-1418.
[7]	禹振, 苏小红, 王甜甜, 马培军. C程序隐式规则自动提取与反例检测[J]. 电子学报, 2013, 41(2): 248-254.
[8]	王雅文;宫云战;肖庆;杨朝红. 基于抽象解释的变量值范围分析及应用[J]. 电子学报, 2011, 39(2): 296-303.
[9]	王雷;李吉;李博洋. 缓冲区溢出漏洞精确检测方法研究[J]. 电子学报, 2008, 36(11): 2200-2204.