Please wait a minute...
浙江大学学报(工学版)
JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE)
Automation technology     
Data flow analysis for C program based on graph model
CHANG Chao, LIU Ke-sheng, TAN Long-dan, JIA Wen-chao
Electronics Engineering Institute of PLA, Hefei 230037, China
Download:   PDF(1312KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  A dataflow analysis method based on graph model for C program was proposed to solve the problem of high false positive rate. A multi-dimensional property graph that includes abstract syntax tree, control flow graph, program dependence graph and function call graph was constrcheted. From the security sensitive program point (sink), the related external controllable input point (source) could be traced. The tainted-style vulnerabilities could be detected through intra-procedural and inter-procedural define analysis. Results show that the false positive rate of data flow analysis was effectively reduced relying on the complete code property guidance and interval operation support,  The method can reduce the workload of manual code audit.

Published: 01 May 2017
CLC:  TP 311  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

CHANG Chao, LIU Ke-sheng, TAN Long-dan, JIA Wen-chao. Data flow analysis for C program based on graph model. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(5): 1007-1015.


基于图模型的C程序数据流分析

针对数据流分析常面临的高误报率等问题,提出基于图模型的C程序数据流分析方法,构建包含抽象语法树、控制流信息、程序依赖信息及函数调用信息的多维图模型,从安全敏感程序点（sink）溯源得到所有相关的外界可控输入源（source）,通过基于图模型的过程内和过程间定值分析,实现对污点型缺陷的检测.结果表明,依赖完备的代码属性指导和区间运算支撑,可以有效降低数据流分析的误报率,减少人工审计代码的工作量.

参考文献(References)：
［1］ WANG R, FENG D G, YANG Y, et al. Semantics-based malware behavior signature extraction and detection method ［J］. Journal of Software, 2012 (2):378-393.
［2］ 李舟军,张俊贤,廖湘科,等.软件安全漏洞检测技术［J］.计算机学报,2015, 38(4): 717-732.
LI Zhou-jun, ZHANG Jun-xian, LIAO Xiang-ke, et al. Survey of software vulnerability detection techniques ［J］. Chinese Journal of Computers, 2015, 38(4):717-732.
［3］ YAMAGUCHI F, MAIER A, GASCON H, et al. Automatic inference of search patterns for taint-style vulnerabilities ［C］∥ Ecurity and Privacy. San Jose, California: IEEE, 2015: 797-812.
［4］ DAHSE J, HOLZ T. Simulation of Built-in PHP features for precise static code analysis ［C］∥Network and Distributed System Security Symposium, San Diego, California : DNSS, 2014： 23-26.
［5］ 万志远,周波.基于静态信息流跟踪的输入验证漏洞检测方法［J］.浙江大学学报：工学版, 2015 (4): 683-691.
WAN Zhi-yuan, ZHOU Bo. Static information flow tracking based approach to detect input validation vulnerabilities［J］. Journal of Zhejiang University ：Engineering Science, 2015 (4): 683-691.
［6］ NECULA G C, MCPEAK S, RAHUL S P, et al. CIL: Intermediate language and tools for analysis and transformation of C programs［C］∥ Compiler Construction. Grenoble, France: IEEE, 2002: 213-228.
［7］ CORBETT J C, DWYER M B, HATCLIFF J, et al. Bandera: Extracting finite-state models from Java source code［C］∥ Software Engineering. Buenos Aires, Argentina: IEEE, 2000: 439-448.
［8］ YAMAGUCHI F, GOLDE N, ARP D, et al. Modeling and discovering vulnerabilities with code property graphs［C］∥Security and Privacy. San Diego, California: IEEE, 2014: 590-604.
［9］ GNU Bash shellshock remote code execution vulnerability report［EB/OL］. ［2014-09-09］. http:∥cve.mitre.org/cgi-bin/cvename.cgi？name=CVE2014-6271
［10］ AHO A V, 阿霍, SETHI R,等. 编译原理［M］.第2版,北京：机械工业出版社,2012： 382-393.
［11］ 王雅文, 宫云战, 肖庆,等. 基于抽象解释的变量值范围分析及应用［J］. 电子学报, 2011(2): 296-303.
WANG Ya-wen, GONG Yun-zhan, XIAO Qing, et al. A method of variable range analysis based on abstract interpretation and its applications ［J］. Acta Electronica Sinica, 2011(2): 296-303.
［12］ 万志远,周波.支持局部调用图生成的指针分析［J］.浙江大学学报:工学版,2015 (6): 1031-1040.
WAN Zhi-yuan, ZHOU Bo. Points-to analysis for partial call graph construction ［J］. Journal of Zhejiang University ：Engineering Science, 2015 (6): 1031-1040.
［13］ 董玉坤,宫云战,金大海.基于区域内存模型的空指针引用缺陷检测［J］.电子学报,2014, 42(9): 1744-1752.
DONF 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.
［14］ HORWITZ S, REPS T, BINKLEY D. Interprocedural slicing using dependence graphs ［J］. Transactions on Programming Languages and Systems, 1990, 12(1):26-60.
［15］ 张迎周,符炜.一种过程间单子切片方法［J］.电子学报,2013(8): 1457-1461.
ZHANG Ying-zhou, FU Wei. An approach of monadic slicing for interprocedural programs ［J］. Acta Electronica Sinica, 2013(8): 1457-1461.
［16］ GODEFROID P, LEVIN M Y, MOLNAR D. SAGE: whitebox fuzzing for security testing ［J］. Queue, 2012, 10(1): 20.
[1] You-wei WANG,Li-zhou FENG. Improved AdaBoost algorithm using group degree and membership degree based noise detection and dynamic feature selection[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2021, 55(2): 367-376.
[2] Jia-hao LIAO,Zhi-wen YU,Yi-meng LIU,Bin GUO. Design and implementation of mobile crowdsensing platform[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2020, 54(10): 1915-1922.
[3] Zi-long JI,Jun-zhong JI. Learning effective connectivity network structure based on parallel searching of double firefly populations[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2020, 54(4): 694-703.
[4] Wan-liang WANG,Xiao-han YANG,Yan-wei ZHAO,Nan GAO,Chuang LV,Zhao-juan ZHANG. Image enhancement algorithm with convolutional auto-encoder network[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2019, 53(9): 1728-1740.
[5] Zhi-yuan WAN,Jia-heng TAO,Jia-kun LIANG,Zhen-gong CAI,Cheng CHANG,Lin QIAO,Qiao-ni ZHOU. Large-scale empirical study on machine learning related questions on Stack Overflow[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2019, 53(5): 819-828.
[6] Kai-long ZHU,YU-liang LU,Hui HUANG,Zhao-kun DENG,Yi-jie DENG. Construction approach for control flow graph from binaries using hybrid analysis[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2019, 53(5): 829-836.
[7] YUAN You-wei-, YU Jia, ZHENG Hong-sheng, WANG Jiao-jiao. Cloud workflow scheduling algorithm based on novelty ranking and multi-quality of service[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(6): 1190-1196.
[8] WANG Haiyan, CHENG Yan . Dual service selection method based on coefficient of variation[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(6): 1197-1204.
[9] XU Rong-bin, SHI Jun, ZHANG Peng-fei, XIE Ying. Similarity measurement of transition mapping relation using Petri net[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(6): 1205-1213.
[10] WANG Ji kui . Bayesian conflicting Web data credibility algorithm[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(12): 2380-2385.
[11] TU Ding, CHEN Ling, CHEN Gen cai, WU Yong, WANG Jing chang. Hierarchical online NMF for detecting and tracking topics[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(8): 1618-1626.
[12] YANG Sha, YE Zhen yu, WANG Shu gang, TAO Hai, LI Shi jian. Perception enhanced intelligent robotic arm system[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(6): 1155-1159.
[13] LUO Lin, SU Hong ye, BAN Lan. Nonparametric bayesian based on  mixture of dirichlet process in application of fault detection[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(11): 2230-2236.
[14] WANG Hong-hao, WANG Hui-quan, JIN Zhong-he. Rollback-able on-board software upgrade method based on incremental link[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(4): 724-731.
[15] WANG Ji-kui, LI Shao-bo. Quality evaluation algorithm for conflicting data sources based on true value finding[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(2): 303-318.