微信服务号

微信订阅号

2025-5-15- 21
Home > Archive>Volume 21, Issue 2, 2010 >209-217
PDF HTML XML Export Cite reminder
Path Sensitive Static Defect Detecting Method
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [13]
    • |
  • Related [20]
    • |
  • Cited by [10]
    • | |
  • Comments
    Abstract:

    This paper presents a new path sensitive algorithm for static defect detecting running in polynomial time. In this method, property state conditions are represented by abstract domain of variables, and infeasible paths can be identified when some variables’ abstract value range is empty. This method avoids the combination explosion of full path analysis by merging the conditions of identical property state at join points in the CFG (control flow graph). This algorithm has been implemented as part of a defect testing tool called DTS (defect testing system). Practical test results show that this method can reduce false positive.

    Reference
    [1] Rice HG. Classes of recursively enumerable sets and their decision problems. Trans. of the American Mathematical Society, 1953, 74(2):358-366.
    [2] Ball T, Rajamani SK. Automatically validating temporal safety properties of interfaces. In: Dwyer M, ed. Proc. of the 8th Int’l SPIN Workshop on Model Checking of Software. Berlin, Heidelberg: Springer-Verlag, 2001. 103-122.
    [3] Aho AV, Lam MS, Sethi R, Ullman JD. Compilers Principles, Techniques, and Tools. 2nd ed., New York: Addison-Wesley, 2006. 626-632.
    [4] Yang ZH, Gong YZ, Xiao Q, Wang YW. The application of interval computation in software testing based on defect pattern. Journal of Computer-aided Design & Computer Graphic, 2008,20(12):1630-1635 (in Chinese with English abstract).
    [5] Das M, Lerner S, Seigle M. ESP: Path-Sensitive program verification in polynomial time. In: Knoop J, Hendren LJ, eds. Proc. of the ACM SIGPLAN Conf. on Programming Language Design and Implementation. New York: ACM Press, 2002. 57-68.
    [6] Bodik R, Anik S. Path-Sensitive value-flow analysis. In: MacQueen DB, Cardelli L, eds. Proc. of the 25th ACM SIGPLAN- SIGACT Symp. on Principles of Programming Languages. San Diego: ACM Press, 1998. 237-251.
    [7] Ammons G, Larus JR. Improving data-flow analysis with path profiles. In: Berman AM, ed. Proc. of the ACM SIGPLAN ’98 Conf. on Programming Language Design and Implementation. New York: ACM Press, 1998. 72-84.
    [8] Thakur A, Govindarajan R. Comprehensive path-sensitive data-flow analysis. In: Soffa ML, Duesterwald E, eds. Proc. of the 6th Annual IEEE/ACM Int’l Symp. on Code Generation and Optimization. New York: ACM Press, 2008. 55-63.
    [9] Holley LH, Rosen BK. Qualified data flow problems. In: Abrahams P, Lipton R, Bourne S, eds. Proc. of the 7th ACM SIGPLAN- SIGACT Symp. on Principles of Programming Languages. New York: ACM Press, 1980. 68-82.
    [10] Bodik R, Gupta R, Soffa PL. Refining data flow information using infeasible paths. In: Jazayeri P, Schauer H, eds. Proc. of the Software Engineering Notes ESEC/FSE’97. New York: ACM Press, 1997. 361-377.
    [11] Tu P, Padua D. Gated SSA-based demand-driven symbolic analysis for parallelizing compilers. In: Valero M, ed. Proc. of the 1995 ACM Int’l Conf. on Supercomputing. New York: ACM Press, 1995. 414-423.
    [12] Fischer J, Jhala R, Mujumdar R. Joining data flow with predicates. In: Wermelinger M, Gall HC, eds. Proc. of the 13th ACM SIGSOFT Int’l Symp. on Foundations of Software Engineering. Lisbon: ACM Press, 2005. 227-236.
    附中文参考文献: [4] 杨朝红,宫云战,肖庆,王雅文.基于缺陷模式的软件测试中的区间运算应用.计算机辅助设计与图形学学报,2008,20(12): 1630-1635.
    Comments
    Comments
    分享到微博
    Submit
Get Citation

肖庆,宫云战,杨朝红,金大海,王雅文.一种路径敏感的静态缺陷检测方法.软件学报,2010,21(2):209-217

Copy
Share
Article Metrics
  • Abstract:9985
  • PDF: 10750
  • HTML: 0
  • Cited by: 0
History
  • Received:June 11,2009
  • Revised:December 07,2009
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2044735Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063