Computer Science ›› 2014, Vol. 41 ›› Issue (5): 208-214.doi: 10.11896/j.issn.1002-137X.2014.05.043

Previous Articles     Next Articles

Technology and Implementation of Extracting Control Flow Model of C Program

YANG Chang-kun and XU Qing-guo   

  • Online:2018-11-14 Published:2018-11-14

Abstract: CFG (Control Flow Graph) represents the execution paths that may be taken in program,and the majority of static analysis tools provide its outcome by extracting control flow graph from AST (Abstract Syntax Tree) and then analyzing the CFG.Extracting correct CFG is the key to build system model on the process of model checking.This paper presented the algorithms for extracting the CFG of functions based on semantic analysis and structure analysis of AST.According to the CFG,some properties of C program can be analyzed via model checking tool.

Key words: Control flow graph,Abstract syntax tree,Model checking

[1] Cavada R,Cimatti A,Keighren G,et al.NuSMV 2.2Tutorial[R].CMU and ITC-irst,nusmv@ irst.itc.it,2004
[2] Clarke E M,Emerson E A.Design and synthesis of synchronization skeletons using branching time temporal logic[C]∥25Years of Model Checking.Springer,2008:196-215
[3] Clarke E M,Emerson E A,Sistla A P.Automatic verification of finite-state concurrent systems using temporal logic specifications[J].ACM Transactions on Programming Languages and Systems (TOPLAS),1986,8:244-263
[4] 韩俊刚,杜慧敏.数字硬件的形式化验证[M].北京:北京大学出版社,2002
[5] Holzmann G J.Static source code checking for user-definedproperties[C]∥Proc.IDPT.2002
[6] Wagner C,Margaria T,Pagendarm H G.Analysis and CodeModel Extraction for C/C++Source Code[C]∥ 14th IEEE International Conference on Engineering of Complex Computer Systems.2009:110-119
[7] Fehnker A,Huuck R,Jayet P,et al.Model checking software at compile time[C]∥ First Joint IEEE/IFIP Symposium on Theoretical Aspects of Software Engineering 2007(TASE’07).2007:45-56
[8] 叶俊民,谢茜,金聪,等.一种基于模型检验程序分析技术的前端工具研究[J].计算机科学,2010,37:118-122
[9] 韩坤亮.基于模型检验的C程序内存安全分析[D].上海:上海大学,2012
[10] 封战胜.基于GCC抽象语法树文本的C源程序语义分析方法研究[D].哈尔滨:哈尔滨工业大学,2009
[11] 何恺铎,顾明,宋晓宇,等.面向源代码的软件模型检测及其实现[J]. 计算机科学,2009,36:267-272
[12] Clarke E,Kroening D,Lerda F.A tool for checking ANSI-C programs[C]∥Tools and Algorithms for the Construction and Analysis of Systems.Springer,2004:168-176
[13] Leven P,Mehler T,Edelkamp S.Directed error detection in C++with the assembly-level model checker StEAM[C]∥Model Checking Software.Springer,2004:39-56
[14] Henzinger T A,Jhala R,Majumdar R,et al.Software verifica-tion with BLAST[C]∥Model Checking Software.Springer,2003:235-239
[15] Clarke E,Kroening D,Sharygina N,et al.SATABS:SAT-based predicate abstraction for ANSI-C[C]∥Tools and Algorithms for the Construction and Analysis of Systems.Springer,2005:570-574
[16] 曹俊亮.C/C++程序安全检查工具前端的设计与实现[D].西安:西安电子科技大学,2007

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!