MIRROR Reflection-Oriented Slicing(Static Analysis) Reflection Resolution (Dynamic Analysis) Java Program Reflective Call Graph Reduct based Slicing matic Test Ca匹 nted Execution Targets Fig.2:The MIRROR framework for resolving reflective calls by combining static and dynamic analysis. className (line 7).Therefore,a dynamic analysis tool may such that these data dependences form the du-chains for R fail to find the four tostring (target methods provided in In reflection-oriented slicing,we obtain first a subgraph of the the four aforementioned subclasses of pmd.cpd.Renderer. program's call graph that contains DR(by considering data In general,dynamic analysis cannot resolve reflective calls that dependences)and then a small number of path-based slices for are not encountered during program execution.In MIRROR, R on this subgraph (by considering also control dependences). however,we can still handle such reflective calls by combining a)Stage 1.Call Graph Reduction:Instead of operating automatic test case generation and program execution. on the entire call graph of the program as in traditional slicing [23],[24],MIRROR restricts itself to a small subgraph. B.The MIRROR Approach For the reflective call in line 42,we have: Figure 2 gives an overview.Given a Java program,MIRROR D42={4÷7,7→12,5÷12,12→17,17→35,35→37 analyzes its reflective calls individually.Below we describe 35→39,35→41,37→42,39→42,41→42} (1) our approach by focusing on getM.invoke (o,null)in line 42 of Figure 1.We will highlight the functionalities of where each statement is identified by its line number.In its four stages,with the first two forming the static analysis Figure 1,all these statements,which affect the execution phase ("Reflection-Oriented Slicing")and the last two forming of line 42 in a data-dependent manner,are underlined.The the dynamic analysis phase ("Reflection Resolution").We definition of getM null in line 34 is disregarded since it will also explain some challenges faced,our solutions,the cannot trigger any target at the reflective call in line 42. motivations behind,and the tradeoffs made. Given D.a subgraph,denoted GR,is built so that,for 1)Reflection-Oriented Slicing(Static Analysis):As dis- every du-chain in DR,GR contains a sequence of method cussed earlier,pure static reflection analysis may introduce calls along which the du-chain holds.In our example,its call many false reflective targets,making it unscalable for some graph is given in Figure 3(a)and the subgraph G42 is given programs.Given a reflective call to resolve,one straightfor- in Figure 3(b). ward remedy is to restrict the analysis to its backward slice el comprising the statements on which the reflective call data-or main() changeInfo() ain0☐eL-changeInfo) 色2 control-depends.Unfortunately,such traditional slicing [23]. e4↓ [24]does not scale to large object-oriented programs [28]. initserver() readconfig() readconfig() e5. e3 e3, [31]-[33].as it operates on the entire call graph of the created()loadcommand() program.For the reflective call in line 42,its backward slice Loadcommand() consists of all the methods in Figure 1,comprising all the (a)Entire call graph (b)Subgraph G42 statements except the three in lines 9,10 and 23. Ideally.we would like to find the smallest backward slice for Fig.3:Call graph reduction for Figure 1. a reflective call so that its different paths trigger its different reflective targets.Achieving such soundness and precision There can be many such subgraphs to choose from.For efficiently is too challenging to be practical.In this paper,we the subgraph in Figure 3(b),replacing its call-graph edges e2 introduce reflection-oriented slicing that strikes a good balance and e3 by e4,e5 and e6 in Figure 3(a)yields another larger among efficiency,soundness and precision by leveraging the subgraph.We do not aim to find the smallest GR.Instead,we following key observation about reflection usage. will build GR by performing BFS in the program's call graph in order to keep GR as small as possible,thereby improving Observation 1.Given a reflective call R in the program, the scalability of the subsequent path-based slicing stage.This the variables that appear in all the conditionals affecting the tradeoff may still make call-graph reduction unscalable for execution of R are usually defined in the same set of methods some reflective calls,affecting the soundness of MIRROR (due that contain the du-chains (i.e.,def-use chains)for R. to the inherent complexity of slicing,in general). Let D be the set of du-pairs (i.e.,def-use pairs)of the b)Stage 2.Path-based Slicing:For a reflective call R, form ss',where a variable defined at s is used at s', its different targets may be defined along different paths.We 14Java Program Reflection-Oriented Slicing (Static Analysis) Call Graph Reduction Path-based Slicing Automatic Test Case Generation Path-besed Slices Reflection Resolution (Dynamic Analysis) Instrumented Execution Test Cases MIRROR Sub Call Graph Reflective Targets Fig. 2: The MIRROR framework for resolving reflective calls by combining static and dynamic analysis. className (line 7). Therefore, a dynamic analysis tool may fail to find the four toString() target methods provided in the four aforementioned subclasses of pmd.cpd.Renderer. In general, dynamic analysis cannot resolve reflective calls that are not encountered during program execution. In MIRROR, however, we can still handle such reflective calls by combining automatic test case generation and program execution. B. The MIRROR Approach Figure 2 gives an overview. Given a Java program, MIRROR analyzes its reflective calls individually. Below we describe our approach by focusing on getM.invoke(o, null) in line 42 of Figure 1. We will highlight the functionalities of its four stages, with the first two forming the static analysis phase (“Reflection-Oriented Slicing”) and the last two forming the dynamic analysis phase (“Reflection Resolution”). We will also explain some challenges faced, our solutions, the motivations behind, and the tradeoffs made. 1) Reflection-Oriented Slicing (Static Analysis): As dis￾cussed earlier, pure static reflection analysis may introduce many false reflective targets, making it unscalable for some programs. Given a reflective call to resolve, one straightfor￾ward remedy is to restrict the analysis to its backward slice comprising the statements on which the reflective call data- or control-depends. Unfortunately, such traditional slicing [23], [24] does not scale to large object-oriented programs [28], [31]–[33], as it operates on the entire call graph of the program. For the reflective call in line 42, its backward slice consists of all the methods in Figure 1, comprising all the statements except the three in lines 9, 10 and 23. Ideally, we would like to find the smallest backward slice for a reflective call so that its different paths trigger its different reflective targets. Achieving such soundness and precision efficiently is too challenging to be practical. In this paper, we introduce reflection-oriented slicing that strikes a good balance among efficiency, soundness and precision by leveraging the following key observation about reflection usage. Observation 1. Given a reflective call R in the program, the variables that appear in all the conditionals affecting the execution of R are usually defined in the same set of methods that contain the du-chains (i.e., def-use chains) for R. Let DR be the set of du-pairs (i.e., def-use pairs) of the form s ⇒ s , where a variable defined at s is used at s , such that these data dependences form the du-chains for R. In reflection-oriented slicing, we obtain first a subgraph of the program’s call graph that contains DR (by considering data dependences) and then a small number of path-based slices for R on this subgraph (by considering also control dependences). a) Stage 1. Call Graph Reduction: Instead of operating on the entire call graph of the program as in traditional slicing [23], [24], MIRROR restricts itself to a small subgraph. For the reflective call in line 42, we have: D42 = {4 ⇒ 7, 7 ⇒ 12, 5 ⇒ 12, 12 ⇒ 17, 17 ⇒ 35, 35 ⇒ 37, 35 ⇒ 39, 35 ⇒ 41, 37 ⇒ 42, 39 ⇒ 42, 41 ⇒ 42} (1) where each statement is identified by its line number. In Figure 1, all these statements, which affect the execution of line 42 in a data-dependent manner, are underlined. The definition of getM = null in line 34 is disregarded since it cannot trigger any target at the reflective call in line 42. Given DR, a subgraph, denoted GR, is built so that, for every du-chain in DR, GR contains a sequence of method calls along which the du-chain holds. In our example, its call graph is given in Figure 3(a) and the subgraph G42 is given in Figure 3(b). loadCommand() changeInfo() initServer() readConfig() created() main() e1 e4 e5 e6 e3 e2 loadCommand() changeInfo() readConfig() main() e1 e3 e2 (a) Entire call graph (b) Subgraph G42 Fig. 3: Call graph reduction for Figure 1. There can be many such subgraphs to choose from. For the subgraph in Figure 3(b), replacing its call-graph edges e2 and e3 by e4, e5 and e6 in Figure 3(a) yields another larger subgraph. We do not aim to find the smallest GR. Instead, we will build GR by performing BFS in the program’s call graph in order to keep GR as small as possible, thereby improving the scalability of the subsequent path-based slicing stage. This tradeoff may still make call-graph reduction unscalable for some reflective calls, affecting the soundness of MIRROR (due to the inherent complexity of slicing, in general). b) Stage 2. Path-based Slicing: For a reflective call R, its different targets may be defined along different paths. We 14