Method callgraphs are integral components of many interprocedural static analyses which are widely used to aid in the development and maintenance of software. Unfortunately, the existences of certain dynamic features...
详细信息
ISBN:
(纸本)9780769543475
Method callgraphs are integral components of many interprocedural static analyses which are widely used to aid in the development and maintenance of software. Unfortunately, the existences of certain dynamic features in modern programming languages, such as Java or C++, can lead to either unsoundness or imprecision in statically constructed callgraphs. We investigate a hierarchy of assumptions that a Class Hierarchy Analysis (cha) callgraphconstructionalgorithm can make about dynamic features in Java. Each successive level of the assumption hierarchy introduces new relaxations of suppositions. These relaxations allow the callgraphalgorithm to treat some uses of dynamic features more precisely and still remain sound. The hierarchy includes a novel assumption that dynamic features will respect encapsulation. We present an empirical study in which a unique callgraphalgorithm is implemented for each level of the assumption hierarchy. This study shows that assuming that dynamic features will respect encapsulation can lead to a callgraph with 44% fewer edges than the fully conservative graph. By incorporating assumptions about casting operations and string values, it is possible to remain conservative and reduce the number of graph edges by 54% and graph nodes by 10% through the use of various resolution techniques. This work demonstrates that even a slight relaxation of assumptions can greatly improve the precision of a callgraph. It further articulates the exact assumptions that a cha call graph construction algorithm must make in order to use advanced resolution techniques.
暂无评论