Y.Li,T.Tan,Y.Zhang,and J.Xue XX:3 than traditional slicing,as TAILOR avoids handling of the heap by reasoning about essentially the (un)reachability of a statement towards the statement sequences in a SCp. Soundiness TAILOR is designed to be a practical tool to facilitate programming debugging and understanding as well as program analysis (among others)for large object-oriented programs.In this setting,any sound static analysis would be either unscalable or imprecise due to the presence of many hard language features,such as native code,dynamic class loading,reflection and multi-threading [30].Therefore,TAILOR is designed to be sound whenever a sound graph representation is available for capturing all the control flows in a (single-or multi-threaded)program.In other words,TAILOR is always sound with respect to part of the program behavior modeled.According to [30],"a soundy analysis aims to be as sound as possible without excessively compromising precision and/or scalability." Therefore,TAILOR represents one such soundy analysis. 1.2 Challenges and Solutions We examine some challenges faced in achieving our three goals and describe our solutions: Precision/Scalability Tradeoffs How do we compute T(SC)efficiently and precisely for large object-oriented programs?Due to exponential blowup of program paths,both DFS and BFS are out of question.We formulate the problem of computing T(SC)by solving an IFDS(Interprocedural Finite Distributive Subset)data-flow analysis problem [38], efficiently on its interprocedural control-flow graph(ICFG)representation of the program. To avoid unrealizable paths with mismatched calls and returns,our analysis must be (fully)context-sensitive in order to achieve useful precision for Java programs.Otherwise, many unrealizable paths,which go through the constructor of java.lang.Object,cannot be filtered out,causing T(SC)to be severely over-approximated.However,distinguishing calling contexts fully with call strings,object-sensitivity [33],and method cloning 54]are known to be unscalable for large programs [12,44].We achieve (full)context sensitivity by solving a CFL-reachability problem over a balanced-parentheses language by matching call and return edges also in the IFDS framework as described in 38. How do we ensure that TAILOR works effectively for a SC of any given length,which is defined to be the number of statements in its longest statement sequence?In general, the longer a SC is,the more SC-irrelevant statements will be removed.We propose to lengthen any given SCby leveraging the concept of object-sensitivity [33,44]developed by the pointer analysis community for Java.As a result,some infeasible paths that would otherwise be introduced are avoided.We will also try to avoid making SC extensions that make our analysis run longer but contribute nothing to precision improvement. Soundiness How do we make TAILOR as soundly as possible?We decompose the problem of tailoring a program for a given SC into two sub-problems:(1)building an ICFG,GICFG, for the program and(2)computing T(SC)from GICFG.TAILOR is sound if GICFG is sound(representation of all control flows in the program).In fact,TAILOR is designed to be practically useful for analyzing the program behavior modeled by GICFG even if GICFG is unsound.This paper solves(2)while resorting to the state-of-the-art for(1). 1.3 Contributions We introduce program tailoring,a new technique for trimming a program based on SCs, which are widely available from other analyses but never exploited by program slicing. We describe how to extend a given SC for object-oriented programs in order to improve the precision of program tailoring (by making tailored programs smaller). EC00P2016Y. Li, T. Tan, Y. Zhang, and J. Xue XX:3 than traditional slicing, as Tailor avoids handling of the heap by reasoning about essentially the (un)reachability of a statement towards the statement sequences in a SC P . Soundiness Tailor is designed to be a practical tool to facilitate programming debugging and understanding as well as program analysis (among others) for large object-oriented programs. In this setting, any sound static analysis would be either unscalable or imprecise due to the presence of many hard language features, such as native code, dynamic class loading, reflection and multi-threading [30]. Therefore, Tailor is designed to be sound whenever a sound graph representation is available for capturing all the control flows in a (single- or multi-threaded) program. In other words, Tailor is always sound with respect to part of the program behavior modeled. According to [30], “a soundy analysis aims to be as sound as possible without excessively compromising precision and/or scalability.” Therefore, Tailor represents one such soundy analysis. 1.2 Challenges and Solutions We examine some challenges faced in achieving our three goals and describe our solutions: Precision/Scalability Tradeoffs How do we compute T (SC) efficiently and precisely for large object-oriented programs? Due to exponential blowup of program paths, both DFS and BFS are out of question. We formulate the problem of computing T (SC) by solving an IFDS (Interprocedural Finite Distributive Subset) data-flow analysis problem [38], efficiently on its interprocedural control-flow graph (ICFG) representation of the program. To avoid unrealizable paths with mismatched calls and returns, our analysis must be (fully) context-sensitive in order to achieve useful precision for Java programs. Otherwise, many unrealizable paths, which go through the constructor of java.lang.Object, cannot be filtered out, causing T (SC) to be severely over-approximated. However, distinguishing calling contexts fully with call strings, object-sensitivity [33], and method cloning [54] are known to be unscalable for large programs [12, 44]. We achieve (full) context sensitivity by solving a CFL-reachability problem over a balanced-parentheses language by matching call and return edges also in the IFDS framework as described in [38]. How do we ensure that Tailor works effectively for a SC of any given length, which is defined to be the number of statements in its longest statement sequence? In general, the longer a SC is, the more SC-irrelevant statements will be removed. We propose to lengthen any given SC by leveraging the concept of object-sensitivity [33, 44] developed by the pointer analysis community for Java. As a result, some infeasible paths that would otherwise be introduced are avoided. We will also try to avoid making SC extensions that make our analysis run longer but contribute nothing to precision improvement. Soundiness How do we make Tailor as soundly as possible? We decompose the problem of tailoring a program for a given SC into two sub-problems: (1) building an ICFG, GICFG, for the program and (2) computing T (SC) from GICFG. Tailor is sound if GICFG is sound (representation of all control flows in the program). In fact, Tailor is designed to be practically useful for analyzing the program behavior modeled by GICFG even if GICFG is unsound. This paper solves (2) while resorting to the state-of-the-art for (1). 1.3 Contributions We introduce program tailoring, a new technique for trimming a program based on SCs, which are widely available from other analyses but never exploited by program slicing. We describe how to extend a given SC for object-oriented programs in order to improve the precision of program tailoring (by making tailored programs smaller). E COO P 2 0 1 6