Monday, February 14, 2005

Detecting infeasible paths statically

Refining Data Flow Information using Infeasible Paths : Published in the Fifth ACM SIGSOFT Symposium on Foundations of Software Engineering and Sixth European Software Engineering Conference in 1997. By Rastislav Bodik, Rajiv Gupta and Mary Lou Soffa.

Key points of the paper.

1. Some of the paths in a program are infeasible and will never be executed. In data flow testing, imprecision may lead to the selection of def-use pairs which are impossible to test because they lie on infeasible paths.

2. A conditional branch has a static co-relation along a path if its outcome can be determined along the path from prior statements or branch outcomes at compile time. Experiments show that from 9-40% of conditionals in large programs exhibit correlation that is detectable at compile time.

They present an alogrithm for the detection of branch co-rrelation and identification of infeasible program sub-paths and then they present the def-use pair analysis that excludes def-use pairs spanning the identified infeasible subpaths.

No comments: