Repository logo
 

A Unified Model for Context-Sensitive Program Analyses: The Blind Men and the Elephant

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Jaiswal, Swati 
Khedker, Uday P 

Abstract

Context-sensitive methods of program analysis increase the precision of interprocedural analysis by achieving the effect of call inlining. These methods have been defined using different formalisms and hence appear as algorithms that are very different from each other. Some methods traverse a call graph top-down whereas some others traverse it bottom-up first and then top-down. Some define contexts explicitly whereas some do not. Some of them directly compute data flow values while some first compute summary functions and then use them to compute data flow values. Further, different methods place different kinds of restrictions on the data flow frameworks supported by them. As a consequence, it is difficult to compare the ideas behind these methods in spite of the fact that they solve essentially the same problem. We argue that these incomparable views are similar to those of blind men describing an elephant called context sensitivity, and make it difficult for a non-expert reader to form a coherent picture of context-sensitive data flow analysis.

We bring out this whole-elephant view of context sensitivity in program analysis by proposing a unified model of context sensitivity which provides a clean separation between computation of contexts and computation of data flow values. Our model captures the essence of context sensitivity and defines simple soundness and precision criteria for context-sensitive methods. It facilitates declarative specifications of context-sensitive methods, insightful comparisons between them, and reasoning about their soundness and precision. We demonstrate this by instantiating our model to many known context-sensitive methods.

Description

Keywords

Interprocedural data flow analysis, interprocedurally valid paths, context sensitivity, flow sensitivity

Journal Title

ACM COMPUTING SURVEYS

Conference Name

Journal ISSN

0360-0300
1557-7341

Volume Title

54

Publisher

Association for Computing Machinery (ACM)

Rights

All rights reserved