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.
[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.
[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.