Detecting large number of infeasible paths through recognizing their patterns

Abstract

A great majority of program paths are found to be infeasible, which in turn make static analysis overly conservative. As static analysis plays a central part in many software engineering activities, knowledge about infeasible program paths can be used to greatly improve the performance of these activities especially structural testing and coverage analysis. In this paper, we present an empirical approach to the problem of infeasible path detection. We have discovered that many infeasible paths exhibit some common properties which are caused by four code patterns including identical/complement-decision, mutually-exclusive-decision, check-then-do and looping-by-flag pattern. Through realizing these properties from source code, many infeasible paths can be precisely detected. Binomial tests have been conducted which give strong statistical evidences to support the validity of the empirical properties. Our experimental results show that even with some limitations in the current prototype tool, the proposed approach accurately detects 82.3% of all the infeasible paths.