Reflection Analysis for Java：Uncovering More Reflective Targets Precisely

2017 IEEE 28th International Symposium on Software Reliability Engineering Reflection Analysis for Java:Uncovering More Reflective Targets Precisely Jie Liu,Yue Li',Tian Tan',and Jingling Xuel.2 ISchool of Computer Science and Engineering,UNSW,Australia 2State Key Laboratory of Software Engineering,Computer School,Wuhan University,China Abstract-Reflection,which is widely used in practice and and records reflective targets accessed at reflective calls during abused by many security exploits,poses a significant obstacle program execution,can be both precise and efficient.As a to program analysis.Reflective calls can be analyzed statically result,bug detectors on finding,for example,data races [18], or dynamically.Static analysis is more sound but also more imprecise (by introducing many false reflective targets and thus deadlocks [19]and property violations [201),and security anal- affecting its scalability).Dynamic analysis can be precise but ysers on finding,for example,privacy leaks [21]and malicious often miss many true reflective targets due to low code coverage. functionalities [22],often resort to dynamic reflection analysis. We introduce MIRROR,the first automatic reflection analysis However,analyzing reflection dynamically often misses many for Java that increases significantly the code coverage of dynamic analysis while keeping false reflective targets low.In its static true reflective targets (due to low code coverage).This is analysis,a novel reflection-oriented slicing technique is applied to especially the case when GUI applications are analyzed.For identify a small number of small path-based slices for a reflective example,we observe that TAMIFLEX [17],the state-of-the-art call so that different reflective targets are likely exercised along dynamic reflection analysis,fails to find any new reflective these different paths.This preserves the soundness of pure static target after a long sequence of GUI operations has been reflection analysis as much as possible,improves its scalability, performed (on,for example,findbugs-1.2.1). and reduces substantially its false positive rate.In its dynamic analysis,these slices are executed with automatically generated In this paper,we introduce MIRROR,the first automatic test cases to report the reflective targets accessed.This signifi- reflection analysis for Java that combines program slicing cantly improves the code coverage of pure dynamic analysis.We (static analysis)and test case generation (dynamic analysis)to evaluate MIRROR against a state-of-the-art dynamic reflection uncover more reflective targets precisely.MIRROR is designed analysis tool,TAMIFLEX,by using 10 large real-world Java applications.MIRROR detects 12.5%-933.3%more reflective to assist dynamic reflection analysis (e.g.,TAMIFLEX)to targets efficiently (in 362.8 seconds on average)without producing resolve more reflective targets with low false positives.Thus, any false positives.These new targets enable 5-174949 call- MIRROR can discover effectively reflective targets that would graph edges to be reachable in the application code. otherwise be missed by TAMIFLEX in real-world applications and improve the code coverage of dynamic reflection analysis. I.INTRODUCTION In MIRROR,its static analysis applies a novel reflection- As one of the most widely adopted programming lan- oriented slicing technique to focus on the parts of the program guages [1].Java has been a popular attack target.Java suffers relevant to a reflective call.Unlike traditional slicing [23],[24]. still from serious security issues,with 87%of attack vectors which hardly scales to large object-oriented programs [25]. for web exploits in 2013 [2]and 91%in 2014 [3].A large [26],MIRROR identifies a small subgraph of the program's variety of exploited vulnerabilities are related to reflection,a call graph that likely affects the execution of a reflective call dynamic feature widely used in Java applications to enable and then computes a small number of small path-based slices their runtime behaviors to be examined or modified at run- in the subgraph so that potentially true yet different reflective time,which is abused by 45%of all exploits in the wild [4]. targets are likely exercised at the reflective call along these In practice,program analysis tools are invaluable for ensur- different paths.This preserves the soundness of pure static ing software quality and reliability.However,"you can't check reflection analysis as much as possible,improves its scalability, code you don't see"[5].Without analyzing reflection,bug and reduces substantially its false positive rate. detectors and security analysers may miss important program In MIRROR,its dynamic analysis executes each path-based behaviors.because these tools do not have a complete view slice with automatically generated test cases to exercise the of the code (as many reflectively induced call-graph edges are path and record the reflective targets accessed.This increases missing).Therefore,reflection poses a major obstacle to bug the code coverage of pure dynamic reflection analysis. detection and security analysis [6]-[9]. We have evaluated MIRROR against TAMIFLEX [17]by Reflective calls can be analyzed either statically or dy- using a set of 10 large real-world Java programs.MIRROR namically.Static analysis [6],[7].[10]-[15].which discovers detects 12.5%-933.3%more reflective targets efficiently reflective targets accessed at reflective calls via type inference, (in 362.8 seconds on average)with no false targets.These is often imprecise by reporting many false targets (and con- new reflective targets result in 5-174949 call-graph edges sequently,impairing scalability for some large applications). reachable in the application code of these programs. In contrast,dynamic analysis [16].[17].which instruments With MIRROR,more reflective targets can be found pre- IEEE 2332-6549/17$31.0002017IEEE 12 ④computer D0I10.1109/M1SSRE.2017.36 society

Reflection Analysis for Java: Uncovering More Reflective Targets Precisely Jie Liu1, Yue Li1, Tian Tan1, and Jingling Xue1,2 1School of Computer Science and Engineering, UNSW, Australia 2State Key Laboratory of Software Engineering, Computer School, Wuhan University, China Abstract—Reflection, which is widely used in practice and abused by many security exploits, poses a significant obstacle to program analysis. Reflective calls can be analyzed statically or dynamically. Static analysis is more sound but also more imprecise (by introducing many false reflective targets and thus affecting its scalability). Dynamic analysis can be precise but often miss many true reflective targets due to low code coverage. We introduce MIRROR, the first automatic reflection analysis for Java that increases significantly the code coverage of dynamic analysis while keeping false reflective targets low. In its static analysis, a novel reflection-oriented slicing technique is applied to identify a small number of small path-based slices for a reflective call so that different reflective targets are likely exercised along these different paths. This preserves the soundness of pure static reflection analysis as much as possible, improves its scalability, and reduces substantially its false positive rate. In its dynamic analysis, these slices are executed with automatically generated test cases to report the reflective targets accessed. This signifi- cantly improves the code coverage of pure dynamic analysis. We evaluate MIRROR against a state-of-the-art dynamic reflection analysis tool, TAMIFLEX, by using 10 large real-world Java applications. MIRROR detects 12.5% – 933.3% more reflective targets efficiently (in 362.8 seconds on average) without producing any false positives. These new targets enable 5 – 174949 call￾graph edges to be reachable in the application code. I. INTRODUCTION As one of the most widely adopted programming lan￾guages [1], Java has been a popular attack target. Java suffers still from serious security issues, with 87% of attack vectors for web exploits in 2013 [2] and 91% in 2014 [3]. A large variety of exploited vulnerabilities are related to reflection, a dynamic feature widely used in Java applications to enable their runtime behaviors to be examined or modified at run￾time, which is abused by 45% of all exploits in the wild [4]. In practice, program analysis tools are invaluable for ensur￾ing software quality and reliability. However, “you can’t check code you don’t see” [5]. Without analyzing reflection, bug detectors and security analysers may miss important program behaviors, because these tools do not have a complete view of the code (as many reflectively induced call-graph edges are missing). Therefore, reflection poses a major obstacle to bug detection and security analysis [6]–[9]. Reflective calls can be analyzed either statically or dy￾namically. Static analysis [6], [7], [10]–[15], which discovers reflective targets accessed at reflective calls via type inference, is often imprecise by reporting many false targets (and con￾sequently, impairing scalability for some large applications). In contrast, dynamic analysis [16], [17], which instruments and records reflective targets accessed at reflective calls during program execution, can be both precise and efficient. As a result, bug detectors on finding, for example, data races [18], deadlocks [19] and property violations [20]), and security anal￾ysers on finding, for example, privacy leaks [21] and malicious functionalities [22], often resort to dynamic reflection analysis. However, analyzing reflection dynamically often misses many true reflective targets (due to low code coverage). This is especially the case when GUI applications are analyzed. For example, we observe that TAMIFLEX [17], the state-of-the-art dynamic reflection analysis, fails to find any new reflective target after a long sequence of GUI operations has been performed (on, for example, findbugs-1.2.1). In this paper, we introduce MIRROR, the first automatic reflection analysis for Java that combines program slicing (static analysis) and test case generation (dynamic analysis) to uncover more reflective targets precisely. MIRROR is designed to assist dynamic reflection analysis (e.g., TAMIFLEX) to resolve more reflective targets with low false positives. Thus, MIRROR can discover effectively reflective targets that would otherwise be missed by TAMIFLEX in real-world applications and improve the code coverage of dynamic reflection analysis. In MIRROR, its static analysis applies a novel reflection￾oriented slicing technique to focus on the parts of the program relevant to a reflective call. Unlike traditional slicing [23], [24], which hardly scales to large object-oriented programs [25], [26], MIRROR identifies a small subgraph of the program’s call graph that likely affects the execution of a reflective call and then computes a small number of small path-based slices in the subgraph so that potentially true yet different reflective targets are likely exercised at the reflective call along these different paths. This preserves the soundness of pure static reflection analysis as much as possible, improves its scalability, and reduces substantially its false positive rate. In MIRROR, its dynamic analysis executes each path-based slice with automatically generated test cases to exercise the path and record the reflective targets accessed. This increases the code coverage of pure dynamic reflection analysis. We have evaluated MIRROR against TAMIFLEX [17] by using a set of 10 large real-world Java programs. MIRROR detects 12.5% – 933.3% more reflective targets efficiently (in 362.8 seconds on average) with no false targets. These new reflective targets result in 5 – 174949 call-graph edges reachable in the application code of these programs. With MIRROR, more reflective targets can be found pre- 2017 IEEE 28th International Symposium on Software Reliability Engineering 2332-6549/17 $31.00 © 2017 IEEE DOI 10.1109/ISSRE.2017.36 12

cisely and quickly,making many previously missing call-graph 1 public class Server edges visible to a variety of analysis tools.This enables bug 2 Class clzObj; 3 boolean infoChanged; detectors and security analyzers,for example,to identify more 4 public static void main(String args[]){ bugs and vulnerabilities effectively. 5 String className "content.HTTPRequest"; In summary,this paper makes the following contributions: 6 if (args.length 0){ className args [0] We introduce MIRROR,the first automatic Java reflection 8 analysis framework that combines static and dynamic 9 if (args.length >5) analysis to resolve reflective calls in large codebases. 0 System.out.println("No config info"); We describe a reflection-oriented slicing technique that Server srv new Server(); 12 srv.changeInfo(className); improves the scalability of traditional slicing for object- 中 arv.readConfig(); oriented programs (w.r.t.a reflective call).This technique 14 8rW.1 nitServer《: is also potentially useful for supporting bug detection, 15 16 public void changeInfo(String cName){ program understanding,and verification. 17 this.clzObj Class.forName(cName); We describe a dynamic analysis technique for resolving 18 this.infoChanged false; reflective calls by combining automatic test case genera- 19 d 20 public void readConfig(){ tion and program execution on path-based slices 21 loadCommand(); We evaluate MIRROR (implemented in 10 KLOC of Java) 2 this.infoChanged true; by using 10 large real-world Java programs.MIRROR is 23 FileMonitor.getFileMonitor().addReloadable(this); 24 critical in enabling their reflective calls to be analyzed 25 public void initServer(){ efficiently and precisely with good soundness 26 created(); 27 II.A MOTIVATING EXAMPLE 28 public void created(){ 29 loadCommand(): Our motivating example is a Java program given in 30 Figure 1,which is abstracted from real-world applications 31 public void loadCommand(){ freecs-1.3 and pmd-4.2.5 (used in our evaluation in 32 String cmdStr null; 33 if (this.infoChanged ==false){ Section IV).We focus on resolving the reflective target meth- Method getM null; ods that may be called at getM.invoke(o,null)in line 35 Class clz this.clzObj; 42.While MIRROR works on the Jimple IR (Intermediate 36 if (pmd.cpd.Renderer.class.isAssignableFrom(clz)) 37 getM clz.getMethod("toString"); Representation)in SooT [27],we illustrate it by using the 38 else if (content.HTTPRequest.class.isAssignableFrom(clz)) high-level statements in Java in order to ease understanding. 39 getM clz.getMethod("getUrl"); In line 17,a class metaobject pointed to by this.clzobj 40 else throw new ErrorClassTypeException(...); 41 is created by calling class.forName (cName)to rep- Object o clz.nevInstance(); 42 cmdStr =(String)getM.invoke(o,null); resent the class named by cName.Here,cName is either 43 "content.HTTPRequest"(line 5)or a non-constant string read from the command line (line 7).In line 41,an object 45] o is created reflectively as an instance of this.clzobj. Fig.1:A Java program. Then a method object,pointed to by getM,is created by calling getMethod()in line 37 or 39 to repre- sent a method from this.clzobj with its name being “toString”or“getUr1”.In line42,this method is two potential targets in line 42.Finally,as o may also be called reflectively on the receiver object o with the ac- an instance of any unknown class (line 7),getUrl()or tual argument null.There are five potential reflective tar- tostring()in any class is also a possible target.Thus, gets:getUrl()in class content.HTTPRequest and a dilemma emerges.Including all these targets improves the the four tostring ()methods in the four subclasses, soundness of the analysis but introduces many false targets, SimpleRenderer.XMLRenderer.CSVRenderer and making the analysis imprecise or unscalable.Conversely.ig- VSRenderer,of interface pmd.cpd.Renderer. noring all these targets may cause some true targets to be missed.In MIRROR,we avoid this dilemma by reporting only A.Existing Approaches the reflective targets observed dynamically on the path-based Static analysis [6],[7],[11],[28][30]attempts to re- slices that are statically computed for a given reflective call. solve reflective targets of getM.invoke (o,null)in Dynamic analysis [16],[17]instruments and records the line 42 by conducting type inference.By keeping track reflective targets invoked by getM.invoke (o,null)in of string constants,we know that getM represents a line 42 during program execution.Unless all test inputs are method named tostring ((line 37)or geturl() exhausted,which is impractical for many applications,espe- (line 39).In addition,as o may be an instance of cially GUI applications,some reflective targets will be missed. class content.HTTPRequest (line 5),tostring (and For example,pmd-4.2.5,from which our example is partly getUrl()from class content.HTTPRequest are the abstracted,does not come with any test case for exercising 13

cisely and quickly, making many previously missing call-graph edges visible to a variety of analysis tools. This enables bug detectors and security analyzers, for example, to identify more bugs and vulnerabilities effectively. In summary, this paper makes the following contributions: • We introduce MIRROR, the first automatic Java reflection analysis framework that combines static and dynamic analysis to resolve reflective calls in large codebases. • We describe a reflection-oriented slicing technique that improves the scalability of traditional slicing for object￾oriented programs (w.r.t. a reflective call). This technique is also potentially useful for supporting bug detection, program understanding, and verification. • We describe a dynamic analysis technique for resolving reflective calls by combining automatic test case genera￾tion and program execution on path-based slices. • We evaluate MIRROR (implemented in 10 KLOC of Java) by using 10 large real-world Java programs. MIRROR is critical in enabling their reflective calls to be analyzed efficiently and precisely with good soundness. II. A MOTIVATING EXAMPLE Our motivating example is a Java program given in Figure 1, which is abstracted from real-world applications freecs-1.3 and pmd-4.2.5 (used in our evaluation in Section IV). We focus on resolving the reflective target meth￾ods that may be called at getM.invoke(o, null) in line 42. While MIRROR works on the Jimple IR (Intermediate Representation) in SOOT [27], we illustrate it by using the high-level statements in Java in order to ease understanding. In line 17, a class metaobject pointed to by this.clzObj is created by calling Class.forName(cName) to rep￾resent the class named by cName. Here, cName is either “content.HTTPRequest” (line 5) or a non-constant string read from the command line (line 7). In line 41, an object o is created reflectively as an instance of this.clzObj. Then a method object, pointed to by getM, is created by calling getMethod() in line 37 or 39 to repre￾sent a method from this.clzObj with its name being “toString” or “getUrl”. In line 42, this method is called reflectively on the receiver object o with the ac￾tual argument null. There are five potential reflective tar￾gets: getUrl() in class content.HTTPRequest and the four toString() methods in the four subclasses, SimpleRenderer, XMLRenderer, CSVRenderer and VSRenderer, of interface pmd.cpd.Renderer. A. Existing Approaches Static analysis [6], [7], [11], [28]–[30] attempts to re￾solve reflective targets of getM.invoke(o, null) in line 42 by conducting type inference. By keeping track of string constants, we know that getM represents a method named toString() (line 37) or getUrl() (line 39). In addition, as o may be an instance of class content.HTTPRequest (line 5), toString() and getUrl() from class content.HTTPRequest are the 1 public class Server { 2 Class clzObj; 3 boolean infoChanged; 4 public static void main(String args[]) { 5 String className = "content.HTTPRequest"; 6 if (args.length > 0) { 7 className = args[0]; 8 } 9 if (args.length > 5) 10 System.out.println("No config info"); 11 Server srv = new Server(); 12 srv.changeInfo(className); 13 srv.readConfig(); 14 srv.initServer(); 15 } 16 public void changeInfo(String cName) { 17 this.clzObj = Class.forName(cName); 18 this.infoChanged = false; 19 } 20 public void readConfig() { 21 loadCommand(); 22 this.infoChanged = true; 23 FileMonitor.getFileMonitor().addReloadable(this); 24 } 25 public void initServer() { 26 created(); 27 } 28 public void created() { 29 loadCommand(); 30 } 31 public void loadCommand() { 32 String cmdStr = null; 33 if (this.infoChanged == false) { 34 Method getM = null; 35 Class clz = this.clzObj; 36 if (pmd.cpd.Renderer.class.isAssignableFrom(clz)) 37 getM = clz.getMethod("toString"); 38 else if (content.HTTPRequest.class.isAssignableFrom(clz)) 39 getM = clz.getMethod("getUrl"); 40 else throw new ErrorClassTypeException(...); 41 Object o = clz.newInstance(); 42 cmdStr = (String) getM.invoke(o, null); 43 } 44 } 45 } Fig. 1: A Java program. two potential targets in line 42. Finally, as o may also be an instance of any unknown class (line 7), getUrl() or toString() in any class is also a possible target. Thus, a dilemma emerges. Including all these targets improves the soundness of the analysis but introduces many false targets, making the analysis imprecise or unscalable. Conversely, ig￾noring all these targets may cause some true targets to be missed. In MIRROR, we avoid this dilemma by reporting only the reflective targets observed dynamically on the path-based slices that are statically computed for a given reflective call. Dynamic analysis [16], [17] instruments and records the reflective targets invoked by getM.invoke(o, null) in line 42 during program execution. Unless all test inputs are exhausted, which is impractical for many applications, espe￾cially GUI applications, some reflective targets will be missed. For example, pmd-4.2.5, from which our example is partly abstracted, does not come with any test case for exercising 13

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 14

Java 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

are therefore motivated to partition D into different du-chain Finally,for each representative path selected for a du-chain groups so that one group contains exactly one definition for group X partitioned from DR,we obtain a path-based slice every variable used at R.Clearly,all the paths that contain the by applying traditional slicing [23].[24]to R.However, same du-chains for R must trigger the same set of reflective we only consider the data and control dependences for the targets at R.Therefore,only one representative path needs to statements on the path and restrict the slice to GR. be selected for each du-chain group.As the partition obtained statically this way is not guaranteed to be the coarsest at run time,different du-chain groups may still trigger the same set A4,6-8,9,11,12,13,17,18,21,22,32,33,34,35-37,41,42 of reflective targets at R. B4,6-8,9,11,12,1317,18,21,22,32,33,34,35,36,38,39,41,42 ⊙4,5,6,9,11,12,13,17,18,21,22,32,33,34,35,36,38,39,41,42 7一12一173537 D4,5,6,9,11,12,13,17,18,21,22,32,33,34,35-37,41,42 净42 41 Fig.6:Path-based slices for the paths in Figure 5. 7→1217→3539入 净42 441 Figure 6 gives the slices found for the four representative 39 →12→1735< 净42 paths in Figure 5.For each path,the statements on the path that 41 are irrelevant to line 42 with respect to this path are crossed 12→1735< 37 out.In addition,line 22 is the only (new)statement added. 净42 41 2)Reflection Resolution (Dynamic Analysis):For each path-based slice obtained for R,we generate its test cases and Fig.4:Partitioning of D42 into du-chain groups. discover its reflective targets at R by instrumented execution. a)Stage 3.Automatic Test Case Generation:Each Figure 4 gives a partition of D42 in Equation (1)into four path-based slice has only one execution path.As in sym- du-chain groups,A,B.C and D.Note that 512 and bolic execution [34]-1381.a path condition is collected that 7=12 cannot appear in the same group since className is comprises all the constraints affecting the execution of the defined in lines 5 and 7 but used in line 12.Similarly,37=42 path.However,unlike the prior work,MIRROR models a and 3942 cannot appear in the same group since getM is variety of object-oriented features such as instanceof, defined in lines 37 and 39 but used in line 42. isAssignableFrom and type casts in order to generate Given a du-chain group Xm of DR,we will find a represen- test cases more comprehensively.In general,we will generate tative path that contains all the du-pairs in X such that for a set of different test inputs that satisfy the path condition so every s1→s2∈Xr,ifs→s2∈DR\XR,thens1 will not that different reflective targeted can be captured. appear on the path.This ensures that s is the only definition for s2 on this path.We will achieve this by performing BFS Args[]E"pmd.cpd SimpleRendererer",("pmd.cpd.XMLRendererer", on the ICFG (inter-procedural Control Flow Graph)of the "pmd.cpd.CSVRendererer","pmd.cpd.VSRendererer" program restricted to GR.If such a path does not exist,X B Args[]={"content.HTTPRequcst" is ignored.This can happen when X contains two du-pairs No input needed that appear in two mutually exclusive branches and thus cannot D hold simultaneously during program execution. Fig.7:Test inputs generated for the slices in Figure 6. A4,6-9,11,12,17,18,13,21,32-37,41,42 B4,6-9,11,12,17,18,13,21,32-36,38,39,41,42 Figure 7 give the test inputs generated.For slice A,four test C4-6,9,11,12,17,1813,21,32-36,38,39,41,42 cases for Args [0]at line 4 are generated due to pmd.cpd. D4-6,9,11,12,17,18,13.21,32-37,41,42 Renderer.class.isAssignableFrom(clz)in its path condition.Here,SimpleRenderer,XMLRenderer,C Fig.5:Representative paths for the du-chain groups in Fig- SVRenderer and VSRenderer are the four subclasses of ure 4. interface pmd.cpd.Renderer.For slice B,one test case is generated for Args[0]at line 4 due to content.HTTPRe Figure 5 gives the representative paths found for the four quest.class.isAssignableFrom(clz).For slice C. du-chain groups in Figure 4.In each case,there are two paths no input is needed as all variables are well initialized.For slice due to line 9.The shorter one that contains no statements in D,its path is infeasible due to two inconsistent constraints the if branch in lines 9-10 is selected.Note that for the className="content.HTTPRequest"and pmd.cpd du-chain groups C and D in Figure 4.with each containing Renderer.class.isAssignableFrom(clz). the definition of className in line 5,the other definition Let us now examine the implications of Observation I of className in line 7 is skipped.Thus,the else branch of on the precision of MIRROR.If a conditional,say,x = the if statement in lines 9-10 will be followed. 0 that affects the execution of R involves a definition of 15

are therefore motivated to partition DR into different du-chain groups so that one group contains exactly one definition for every variable used at R. Clearly, all the paths that contain the same du-chains for R must trigger the same set of reflective targets at R. Therefore, only one representative path needs to be selected for each du-chain group. As the partition obtained statically this way is not guaranteed to be the coarsest at run time, different du-chain groups may still trigger the same set of reflective targets at R. A 4 7 12 17 35 37 41 42 B 4 7 12 17 35 39 41 42 C 5 12 35 39 41 17 42 5 12 35 37 41 D 5 17 42 Fig. 4: Partitioning of D42 into du-chain groups. Figure 4 gives a partition of D42 in Equation (1) into four du-chain groups, A, B, C and D. Note that 5 ⇒ 12 and 7 ⇒ 12 cannot appear in the same group since className is defined in lines 5 and 7 but used in line 12. Similarly, 37 ⇒ 42 and 39 ⇒ 42 cannot appear in the same group since getM is defined in lines 37 and 39 but used in line 42. Given a du-chain group XR of DR, we will find a represen￾tative path that contains all the du-pairs in XR such that for every s1 ⇒ s2 ∈ XR, if s 1 ⇒ s2 ∈ DR \XR, then s 1 will not appear on the path. This ensures that s1 is the only definition for s2 on this path. We will achieve this by performing BFS on the ICFG (inter-procedural Control Flow Graph) of the program restricted to GR. If such a path does not exist, XR is ignored. This can happen when XR contains two du-pairs that appear in two mutually exclusive branches and thus cannot hold simultaneously during program execution. 4, 6-9, 11, 12, 17, 18, 13, 21, 32-37, 41, 42 4, 6-9, 11, 12, 17, 18, 13, 21, 32-36, 38, 39, 41, 42 4-6, 9, 11, 12, 17, 18, 13, 21, 32-36, 38, 39, 41, 42 4-6, 9, 11, 12, 17, 18, 13, 21, 32-37, 41, 42 A B C D Fig. 5: Representative paths for the du-chain groups in Fig￾ure 4. Figure 5 gives the representative paths found for the four du-chain groups in Figure 4. In each case, there are two paths due to line 9. The shorter one that contains no statements in the if branch in lines 9 – 10 is selected. Note that for the du-chain groups C and D in Figure 4, with each containing the definition of className in line 5, the other definition of className in line 7 is skipped. Thus, the else branch of the if statement in lines 9 – 10 will be followed. Finally, for each representative path selected for a du-chain group XR partitioned from DR, we obtain a path-based slice by applying traditional slicing [23], [24] to R. However, we only consider the data and control dependences for the statements on the path and restrict the slice to GR. B A C D 4, 6-8, 9, 11, 12, 13, 17, 18, 21,
22, 32, 33, 34, 35-37, 41, 42

4, 6-8, 9, 11, 12, 13, 17, 18, 21,
22, 32, 33, 34, 35, 36, 38, 39, 41, 42

4, 5, 6, 9, 11, 12, 13, 17, 18, 21,

22, 32, 33, 34, 35, 36, 38, 39, 41, 42

4, 5, 6, 9, 11, 12, 13, 17, 18, 21,

22, 32, 33, 34, 35-37, 41, 42

Fig. 6: Path-based slices for the paths in Figure 5. Figure 6 gives the slices found for the four representative paths in Figure 5. For each path, the statements on the path that are irrelevant to line 42 with respect to this path are crossed out. In addition, line 22 is the only (new) statement added. 2) Reflection Resolution (Dynamic Analysis): For each path-based slice obtained for R, we generate its test cases and discover its reflective targets at R by instrumented execution. a) Stage 3. Automatic Test Case Generation: Each path-based slice has only one execution path. As in sym￾bolic execution [34]–[38], a path condition is collected that comprises all the constraints affecting the execution of the path. However, unlike the prior work, MIRROR models a variety of object-oriented features such as instanceof, isAssignableFrom and type casts in order to generate test cases more comprehensively. In general, we will generate a set of different test inputs that satisfy the path condition so that different reflective targeted can be captured. B A D Args[] ∈ {{“pmd.cpd.SimpleRendererer”}, {“pmd.cpd.XMLRendererer”}, Args[] = {“content.HTTPRequest”} D Infeasible path C No input needed {“pmd.cpd.CSVRendererer”}, {“pmd.cpd.VSRendererer”}} Fig. 7: Test inputs generated for the slices in Figure 6. Figure 7 give the test inputs generated. For slice A, four test cases for Args[0] at line 4 are generated due to pmd.cpd. Renderer.class.isAssignableFrom(clz) in its path condition. Here, SimpleRenderer, XMLRenderer, C SVRenderer and VSRenderer are the four subclasses of interface pmd.cpd.Renderer. For slice B, one test case is generated for Args[0] at line 4 due to content.HTTPRe quest.class.isAssignableFrom(clz). For slice C, no input is needed as all variables are well initialized. For slice D, its path is infeasible due to two inconsistent constraints, className="content.HTTPRequest" and pmd.cpd .Renderer.class.isAssignableFrom(clz). Let us now examine the implications of Observation 1 on the precision of MIRROR. If a conditional, say, x == 0 that affects the execution of R involves a definition of 15

x outside GR,then MIRROR will generate a value of x so du-pair s s2 is central to our algorithm.To this end,we that x =0 holds.If this conditional never evaluates to true make use of the following two functions: during program execution,then MIRROR may report some ·Connect(s1,s2）returns a sub-call graph so that s1→s2. false reflective targets along this path.This has never happened Common(s1,s2)returns a statement reaching s1 and s2. to a set of 10 large Java programs evaluated,indicating that Observation 1 usually holds in real-world applications There are three types of interprocedural du-pairs.We discuss how to build the two functions,as illustrated in Figure 8. b)Stage 4.Instrumented Execution:For each path- based slice obtained for R,we generate an executable program by adding some missing variable declarations.For example, a(){ b(){ every slice in Figure 6 misses the declaration for getM.We s1:b(y)i s2:x=a()i then execute each slice with its test cases generated earlier to resolve the reflective targets at R along its associated path. el. Let us consider the reflective call in line 42.For slice A. the four tostring()target methods in the four subclasses, b(z){ a(){ SimpleRenderer,XMLRenderer,CSVRenderer and s2:x=Z; sl:returny VSRenderer,of interface pmd.cpd.Renderer are found. } For slice B,content.HTTPRequest.getUrl()is dis- covered.For the slice C.this same target is found. (a)Parameter passing (b)Value returning III.THE MIRROR ALGORITHMS c() a(){ We describe the algorithms for realizing the four compo- S3: a(); el S4: b); sl:p.f=.... nents in MIRROR (Figure 2).MIRROR operates on the ICFG of the program expressed in a three-address IR,by making use of the program's call graph G and def-use chains available. e2 Given a program,MIRROR analyzes the reflective calls b(){ reachable from its main (individually.For a given reflective s2:..q.f; call R.D represents the set of du-chains for R.Our call- graph reduction algorithm will reduce G to a substantially smaller subgraph GR that contains a sequence of method calls (c)Field access to establish every du-chain in DR.Our path-based slicing algorithm will build a small number of small path-based slices Fig.8:Building Connect(s1,s2)and Common(s1,s2)for three on GR with its paths leading potentially to all the possible types of interprocedural du-pairs ss2. targets accessed at R.Our automatic test case generator generates the test cases for exercising a (feasible)path-based (1)Parameter Passing (Figure 8(a)).s=s2 denotes a slice.Finally,our instrumentator instruments and executes a parameter-passing dependence,where s1 is a call state- given slice to report the reflective targets accessed at R. ment in method a()that passes an argument used at s2 in method b().As a result,Connect(s1,s2)=fa()b()} A.Call Graph Reduction and Common(s1,s2)=s1. Given a reflective call R,we will reduce the program's call (2)Return value (Figure 8(b))s1=s2 denotes a value- graph G to a subgraph GR,which is substantially smaller returning dependence,where s2 is a call statement in but still allows every du-chain in D to hold.Thus,GR method 60)that receives a value returned from s in suffices to trigger all the possible reflective targets at R while method a().Thus,Connecr(s1,s2)=fa()b()}and keeping the number of false targets reported to a minimum Common(s1,s2）=s2. due to Observation 1.This also enables MIRROR to perform (3)Field Access (Figure 8(c))s1=s2 denotes a field- its subsequent reflection-oriented slicing on a small sub- related dependence,where s is a store p.f =..in call graph,thereby improving the scalability of traditional method a()and s2 is a load...=q.f in method b(). slicing (especially for large object-oriented programs),which Here,p.f and g.f are aliases as p and q may point to is performed on the entire call graph of the program instead. a common object.This also includes the special cases We will build GR so that for every du-chain in DR.GR when s1 appears directly in c()(as if the call to a()at contains a sequence of method calls for the du-chain to hold. s3 is inlined)and/or when s2 appears directly in c()(as It suffices to consider only the interprocedural du-pairs (i.e.. if the call to 6()at s4 is inlined). the du-pairs spanning two different methods)in DR,since the We compute Connect(s1,s2)by performing BFS on the resulting G will naturally include all the intraprocedural du- program's call graph G backwards,starting from the use pairs in DR.To construct GR.we grow it incrementally by s2.We will stop at the first method m such that processing all the interprocedural du-pairs in turn.Therefore, 1)m is a direct or indirect caller of b()or contains s2 (as how to find a sub-call graph to establish one interprocedural is the case when s4 is replaced by s2),and 16

x outside GR, then MIRROR will generate a value of x so that x == 0 holds. If this conditional never evaluates to true during program execution, then MIRROR may report some false reflective targets along this path. This has never happened to a set of 10 large Java programs evaluated, indicating that Observation 1 usually holds in real-world applications. b) Stage 4. Instrumented Execution: For each path￾based slice obtained for R, we generate an executable program by adding some missing variable declarations. For example, every slice in Figure 6 misses the declaration for getM. We then execute each slice with its test cases generated earlier to resolve the reflective targets at R along its associated path. Let us consider the reflective call in line 42. For slice A, the four toString() target methods in the four subclasses, SimpleRenderer, XMLRenderer, CSVRenderer and VSRenderer, of interface pmd.cpd.Renderer are found. For slice B, content.HTTPRequest.getUrl() is dis￾covered. For the slice C, this same target is found. III. THE MIRROR ALGORITHMS We describe the algorithms for realizing the four compo￾nents in MIRROR (Figure 2). MIRROR operates on the ICFG of the program expressed in a three-address IR, by making use of the program’s call graph G and def-use chains available. Given a program, MIRROR analyzes the reflective calls reachable from its main() individually. For a given reflective call R, DR represents the set of du-chains for R. Our call￾graph reduction algorithm will reduce G to a substantially smaller subgraph GR that contains a sequence of method calls to establish every du-chain in DR. Our path-based slicing algorithm will build a small number of small path-based slices on GR with its paths leading potentially to all the possible targets accessed at R. Our automatic test case generator generates the test cases for exercising a (feasible) path-based slice. Finally, our instrumentator instruments and executes a given slice to report the reflective targets accessed at R. A. Call Graph Reduction Given a reflective call R, we will reduce the program’s call graph G to a subgraph GR, which is substantially smaller but still allows every du-chain in DR to hold. Thus, GR suffices to trigger all the possible reflective targets at R while keeping the number of false targets reported to a minimum due to Observation 1. This also enables MIRROR to perform its subsequent reflection-oriented slicing on a small sub￾call graph, thereby improving the scalability of traditional slicing (especially for large object-oriented programs), which is performed on the entire call graph of the program instead. We will build GR so that for every du-chain in DR, GR contains a sequence of method calls for the du-chain to hold. It suffices to consider only the interprocedural du-pairs (i.e., the du-pairs spanning two different methods) in DR, since the resulting GR will naturally include all the intraprocedural du￾pairs in DR. To construct GR, we grow it incrementally by processing all the interprocedural du-pairs in turn. Therefore, how to find a sub-call graph to establish one interprocedural du-pair s1 ⇒ s2 is central to our algorithm. To this end, we make use of the following two functions: • Connect(s1, s2) returns a sub-call graph so that s1 ⇒ s2. • Common(s1, s2) returns a statement reaching s1 and s2. There are three types of interprocedural du-pairs. We discuss how to build the two functions, as illustrated in Figure 8. a(){ s1: } b(y); e1 b(z){ s2: } x = z; b(){ s2: } x = a(); a(){ s1: } e1 return y; (a) Parameter passing (b) Value returning c(){ s3: s4: a(); b(); } b(){ s2: } … = e2 q.f; a(){ s1: } p.f=…; e1 (c) Field access Fig. 8: Building Connect(s1, s2) and Common(s1, s2) for three types of interprocedural du-pairs s1 ⇒ s2. (1) Parameter Passing (Figure 8(a)). s1 ⇒ s2 denotes a parameter-passing dependence, where s1 is a call state￾ment in method a() that passes an argument used at s2 in method b(). As a result, Connect(s1, s2) = {a() → b()} and Common(s1, s2) = s1. (2) Return value (Figure 8(b)) s1 ⇒ s2 denotes a value￾returning dependence, where s2 is a call statement in method b() that receives a value returned from s1 in method a(). Thus, Connect(s1, s2) = {a() → b()} and Common(s1, s2) = s2. (3) Field Access (Figure 8(c)) s1 ⇒ s2 denotes a field￾related dependence, where s1 is a store p.f = ··· in method a() and s2 is a load ··· = q.f in method b(). Here, p.f and q.f are aliases as p and q may point to a common object. This also includes the special cases when s1 appears directly in c() (as if the call to a() at s3 is inlined) and/or when s2 appears directly in c() (as if the call to b() at s4 is inlined). We compute Connect(s1, s2) by performing BFS on the program’s call graph G backwards, starting from the use s2. We will stop at the first method m such that 1) m is a direct or indirect caller of b() or contains s2 (as is the case when s4 is replaced by s2), and 16

2)m is a direct or indirect caller of a()or contains s e6 main() s9:d(): e7 (as is the case when sa is replaced by s). s10:e(j9 Then Connect(s1,s2)comprises the two call-chains,one from m to b()and one from m to a(),both computed d(){ e(){ :889 el e2 by BFS.In Figure 8(c),m is found to be cO).So 9 Connect(s1,s2)={c0→a0,c0→b0} Common(s1,s2)is s1 if m contains s1 or is the call a(){ statement in m that calls (directly or indirectly)a method e3 s1:p.f=; e5 that contains s1.In Figure 8(c),Common(s1,s2)=s3. c(){ b(){ (If we modify the example by replacing s3 by s1,then e4 s4:x=b(); g2·y=白.1： Common(s1,s2）=s1.) s3:return y } In theory,Connect(s1,s2)is not the smallest.In practice. however,Connecr(s1,s2)is nearly so due to BFS used,as all (a)Call graph the reflection-related statements are typically used together. e2 Algorithm 1:Call Graph Reduction. d( Input A reflective call site R Output:GR 1 Function BuildSubgraph() a() e5 e3 2 G ={the method containing R): foreach s1→s2∈DRdo visited(s1 s2):=false; foreach s→R∈DRdo b() RECBUILD(⊥，s→R): return GR 8 Procedure RECBUILD(u,s1 s2) (b)Incorrect G宽 (C)GR 9 visited(s1=s2):=true; 10 if s1=s2 spans two distinct methods then Fig.9:Construction of incorrect and correct GR 11 ifu==⊥then u=s2; 2 Gs1→u=Connect(s1,g G.G does not contain a sequence of method calls that 13 GR=GRUG1→u: allows the du-chain s1→s2→s3→s4 to be established.. 14 Ca1→u=Common(s1,u: Figure 9(c)gives the subgraph GR constructed by our 15 foreach s3→s1∈DRdo if !visited(s3=s1)then algorithm.We first compute Gss=-Connect(s3,s4)= 16 17 |RECBUILD(Cg1→u,s3→s1月 fe4}and ca354 Common(s3,s4)=s4.We then com- pute Gs1→s4=Connecr(s1,sa）={e1,e3}and ca1→84= 18 return; Common(s1,s4)=s5.By construction,the following two facts are true.(1)In Gs4 reaches the method b()that Let us now describe BuildSubGraph(),in Algorithm 1,that contains s3.(2)In G,51 can reach s4.As s2s3 is builds GR for a reflective call R.We tag a du-pair as visited intraprocedural,s2 and s3 reside in the same method.Thus, in the standard manner to deal with dependence cycles.One in GR,s can reach b()that contains also s2.By computing simple-minded but incorrect approach would compute: Connect(s1,s4)instead of Connect(s1,s2),s1 s2 is also G咒-= U respected.As shown,d()can trigger a sequence of method Connect(s1,s2） (2) calls,s5 a(),s6:c()and s:=b0,so that the du-chain Dx is interprocedural s1→s2÷s3→s4 holds. While G contains the statements in D.some du-chains Example 1.Da2 is given in Equation (1),which contains two may no longer be preserved,as some caller-callee relations interprocedural du-pairs.12=17 and 17=35.By apply- are missing.Consider Figure 9.The program's call graph is given in Figure 9(a).where s4 symbolizes R.Suppose ing Algorithm 1,we obtain Connect(17,35)=e1,e2,e3} and Common(17,35)=(12}.Finally,Connect(17,35)= Dr={s1→s2,s2→s3,s3→s4}.For the du-chain s1→ te1,e2,e3}is the subgraph Gr obtained in Figure 3. s2→s3→s4,s1→s2ands3→s4 are interprocedural and s2=s3 is intraprocedural.Due to the recursive nature of our B.Path-based Slicing algorithm,it suffices to use this du-chain to explain how our Given D that contains the du-chains for a reflective call algorithm works and argue for its correctness. R,we generate its path-based slices in three steps. G=Connect(s1:s2)UConnect(s3;sA)={e2,es}ufes} 1)Partitioning DR:We partition DR into du-chain groups given in Figure 9(b)is incorrect.As e()cannot reach c()in so that in one group,every variable has exactly one definition, 17

2) m is a direct or indirect caller of a() or contains s1 (as is the case when s3 is replaced by s1). Then Connect(s1, s2) comprises the two call-chains, one from m to b() and one from m to a(), both computed by BFS. In Figure 8(c), m is found to be c(). So Connect(s1, s2) = {c() → a(), c() → b()}. Common(s1, s2) is s1 if m contains s1 or is the call statement in m that calls (directly or indirectly) a method that contains s1. In Figure 8(c), Common(s1, s2) = s3. (If we modify the example by replacing s3 by s1, then Common(s1, s2) = s1.) In theory, Connect(s1, s2) is not the smallest. In practice, however, Connect(s1, s2) is nearly so due to BFS used, as all the reflection-related statements are typically used together. Algorithm 1: Call Graph Reduction. Input : A reflective call site R Output: GR 1 Function BuildSubgraph() 2 GR := {the method containing R}; 3 foreach s1 ⇒ s2 ∈ DR do 4 visited(s1 ⇒ s2) := false; 5 foreach s ⇒R∈ DR do 6 RECBUILD(⊥, s ⇒ R); 7 return GR 8 Procedure RECBUILD(u, s1 ⇒ s2) 9 visited(s1 ⇒ s2) := true; 10 if s1 ⇒ s2 spans two distinct methods then 11 if u == ⊥ then u := s2; 12 Gs1⇒u = Connect(s1, u); 13 GR = GR ∪ Gs1⇒u; 14 cs1⇒u = Common(s1, u); 15 foreach s3 ⇒ s1 ∈ DR do 16 if !visited(s3 ⇒ s1) then 17 RECBUILD(cs1⇒u, s3 ⇒ s1); 18 return; Let us now describe BuildSubGraph(), in Algorithm 1, that builds GR for a reflective call R. We tag a du-pair as visited in the standard manner to deal with dependence cycles. One simple-minded but incorrect approach would compute: Gerr R = s1⇒s2∈DR is interprocedural Connect(s1, s2) (2) While Gerr R contains the statements in DR, some du-chains may no longer be preserved, as some caller-callee relations are missing. Consider Figure 9. The program’s call graph is given in Figure 9(a), where s4 symbolizes R. Suppose DR = {s1 ⇒ s2, s2 ⇒ s3, s3 ⇒ s4}. For the du-chain s1 ⇒ s2 ⇒ s3 ⇒ s4, s1 ⇒ s2 and s3 ⇒ s4 are interprocedural and s2 ⇒ s3 is intraprocedural. Due to the recursive nature of our algorithm, it suffices to use this du-chain to explain how our algorithm works and argue for its correctness. Gerr R = Connect(s1, s2)∪Connect(s3, s4) = {e2, e5}∪{e4} given in Figure 9(b) is incorrect. As e() cannot reach c() in d(){ s5: s6: a(); c(); } a(){ s1: p.f } = …; c(){ s4: b(); } b(){ s2: s3: y return } = q.f; x = y; e1 e2 e3 e5 e4 e(){ s7: s8: a(); b(); } main(){ s9: s10: d(); e(); } e6 e7 (a) Call graph c() e2 e5 e4 b() a() e() c() e4 b() a() d() e3 e1 (b) Incorrect Gerr R (c) GR Fig. 9: Construction of incorrect and correct GR. Gerr R , Gerr R does not contain a sequence of method calls that allows the du-chain s1 ⇒ s2 ⇒ s3 ⇒ s4 to be established. Figure 9(c) gives the subgraph GR constructed by our algorithm. We first compute Gs3⇒s4 = Connect(s3, s4) = {e4} and cs3⇒s4 = Common(s3, s4) = s4. We then com￾pute Gs1⇒s4 = Connect(s1, s4) = {e1, e3} and cs1⇒s4 = Common(s1, s4) = s5. By construction, the following two facts are true. (1) In Gs3⇒s4 , s4 reaches the method b() that contains s3. (2) In Gs1⇒s4 , s1 can reach s4. As s2 ⇒ s3 is intraprocedural, s2 and s3 reside in the same method. Thus, in GR, s1 can reach b() that contains also s2. By computing Connect(s1, s4) instead of Connect(s1, s2), s1 ⇒ s2 is also respected. As shown, d() can trigger a sequence of method calls, s5 : a(), s6 : c() and s4 : x = b(), so that the du-chain s1 ⇒ s2 ⇒ s3 ⇒ s4 holds. Example 1. D42 is given in Equation (1), which contains two interprocedural du-pairs, 12 ⇒ 17 and 17 ⇒ 35. By apply￾ing Algorithm 1, we obtain Connect(17, 35) = {e1, e2, e3} and Common(17, 35) = {12}. Finally, Connect(17, 35) = {e1, e2, e3} is the subgraph GR obtained in Figure 3. B. Path-based Slicing Given DR that contains the du-chains for a reflective call R, we generate its path-based slices in three steps. 1) Partitioning DR: We partition DR into du-chain groups so that in one group, every variable has exactly one definition, 17

starting from the variables used at R.This can be done easily Algorithm 2:Representative Path Selection. by traversing the du-chains backwards from R by separating Input A du-chain group XR for R multiple definitions of a variable in different groups. Output:A representative path Px for XR Example 2.For the reflective call at line 42 in Figure 1.Da2 1 Function SelectPath() in Equation (1)is partitioned into the four du-chain groups Px=0; given in Figure 4,where each variable has one definition. Enqueue(Q,R); 4 RECSELECT(); 2)Finding Representative Paths:For a given du-chain Remove all non-downwards-exposed definitions in group Xx partitioned from Dr.all the paths sharing XR PXR: will cause the same set of reflective targets to be accessed return Pxx: at R.Thus,it suffices to consider just one of these paths.In 7 Procedure RECSELECT() MIRROR,we will find one representative path Px for X in 8 while O≠0do the program's ICFG restricted G.which is a small subgraph s Dequeue(Q) of the program's call graph found in call graph reduction,by 10 Let pa be the (BFS)path maintained for s; performing BFS.starting from R.Px is a path-specific to 11 if ps contains all statements in XR then XR.For every statement in XR,the path includes only its 12 PX元=Ps definition in X but excludes its other definitions that appear 13 Q=: in the other du-chain groups. 14 return: We can find Px by applying SelectPath()in Algorithm 2. 15 Let T be the set of statements in XR but not in The basic idea is simple.During BFS,the shortest path pa Ps: from R to any statement s visited in the program's ICFG 16 if 3tET:t does not reach s then restricted to GR (line 21)is maintained (line 10).If Px is 少 return; found (lines 11-14).then we are done.If the statements in 18 if3u∈pa:s→u∈Dr\XR then XR that are not yet encountered cannot reach s,we give up 19 |if书s'∈ps:s'→u∈XR then this path (lines 15-17).If s=uE DR XR is downward- 20 return: exposed for a statement u in pa,then we are traversing along a 21 foreach s'E pred(s)in the ICFG restricted to wrong direction(lines 18-20),since Px must include only GR do the single definition of u in XR rather than DR\XR.In lines 22 if s'was not previously engueued then 21-23,we perform our traversal in BFS,by avoiding visiting 23 Enqueue(Q.s') control-flow cycles repeatedly.In line 21,pred represents the 24 RECSELECTO); standard predecessor function for a directed graph.Finally,in 25 return; line 5,we remove non-downward-exposed definitions,which are in DX,as they are redundant (as illustrated below) Example 3.For the four du-chain groups in Figure 4,we can Example 4.For the four representative paths in Figure 5,their apply SelectPath to find their representative paths in Figure 5. corresponding path-based slices are given in Figure 6. Let us consider the du-chain group A.Consider the code in Figure 1.For getM used in line 42,its definition is given in C.Automatic Test Case Generation line 37.For className used in line 12,its definition is given in line 7.When constructing its representative path starting Each path-based slice exhibits one single path.A path from line 42,we will not include line 39,since this will make condition that consists of all the constraints governing the the definition of getM in line 39 downward-exposed (to line execution of the path is collected and solved to find all the 42).Towards the end of the BFS traversal,line 5 in Figure I test inputs for exercising the path.There are some SMT will be visited.The representative path built so far is "6-9. solvers around [39]-[41].However,we have written one 11,12,17,18,13,2l,32-37,41,42”.As the definition of ourselves in order to handle a variety of object-oriented className in line 7 is already included,the other definition constraints more comprehensively,including instanceof, className in line 5 is initially included by RECSELECT but isAssignableFrom,and type casts removed in SelectPath since its not downward-exposed,i.e., redundant.Thus,the final path found is "4,6-9,11,12,17. Example 5.For the four path-based slices generated in 18,13,21,32-37,41,42” ▣ Figure 6.their corresponding test cases are given in Figure 7. For the path-based slice named A,some path constraints are 3)Generating Path-based Slices:For each representative args.length 0,className args[0](an assig path found for a reflective call R,we apply traditional slicing nment),this.infoChanged false (an assignment), [23].[24]to compute a backward slice from R.However, this.infoChanged =false,and pmd.cpd.Rende only the data and control dependences for the statements in rer.class.isAssignableFrom(clz).Solving this this path are considered,with the slice restricted to G only. path condition yields the four test inputs given in Figure 7. 18

starting from the variables used at R. This can be done easily by traversing the du-chains backwards from R by separating multiple definitions of a variable in different groups. Example 2. For the reflective call at line 42 in Figure 1, D42 in Equation (1) is partitioned into the four du-chain groups given in Figure 4, where each variable has one definition. 2) Finding Representative Paths: For a given du-chain group XR partitioned from DR, all the paths sharing XR will cause the same set of reflective targets to be accessed at R. Thus, it suffices to consider just one of these paths. In MIRROR, we will find one representative path PXR for XR in the program’s ICFG restricted GR, which is a small subgraph of the program’s call graph found in call graph reduction, by performing BFS, starting from R. PXR is a path-specific to XR. For every statement in XR, the path includes only its definition in XR but excludes its other definitions that appear in the other du-chain groups. We can find PXR by applying SelectPath() in Algorithm 2. The basic idea is simple. During BFS, the shortest path ps from R to any statement s visited in the program’s ICFG restricted to GR (line 21) is maintained (line 10). If PXR is found (lines 11 – 14), then we are done. If the statements in XR that are not yet encountered cannot reach s, we give up this path (lines 15 – 17). If s ⇒ u ∈ DR \ XR is downward￾exposed for a statement u in ps, then we are traversing along a wrong direction (lines 18 – 20), since PXR must include only the single definition of u in XR rather than DR \XR. In lines 21 – 23, we perform our traversal in BFS, by avoiding visiting control-flow cycles repeatedly. In line 21, pred represents the standard predecessor function for a directed graph. Finally, in line 5, we remove non-downward-exposed definitions, which are in DR \ XR, as they are redundant (as illustrated below). Example 3. For the four du-chain groups in Figure 4, we can apply SelectPath to find their representative paths in Figure 5. Let us consider the du-chain group A. Consider the code in Figure 1. For getM used in line 42, its definition is given in line 37. For className used in line 12, its definition is given in line 7. When constructing its representative path starting from line 42, we will not include line 39, since this will make the definition of getM in line 39 downward-exposed (to line 42). Towards the end of the BFS traversal, line 5 in Figure 1 will be visited. The representative path built so far is “6 – 9, 11, 12, 17, 18, 13, 21, 32 – 37, 41, 42”. As the definition of className in line 7 is already included, the other definition className in line 5 is initially included by RECSELECT but removed in SelectPath since its not downward-exposed, i.e., redundant. Thus, the final path found is “4, 6 – 9, 11, 12, 17, 18, 13, 21, 32 – 37, 41, 42”. 3) Generating Path-based Slices: For each representative path found for a reflective call R, we apply traditional slicing [23], [24] to compute a backward slice from R. However, only the data and control dependences for the statements in this path are considered, with the slice restricted to GR only. Algorithm 2: Representative Path Selection. Input : A du-chain group XR for R Output: A representative path PXR for XR 1 Function SelectPath() 2 PXR = ∅; 3 Enqueue(Q, R); 4 RECSELECT(); 5 Remove all non-downwards-exposed definitions in PXR ; 6 return PXR ; 7 Procedure RECSELECT() 8 while Q = ∅ do 9 s = Dequeue(Q) 10 Let ps be the (BFS) path maintained for s; 11 if ps contains all statements in XR then 12 PXR = ps; 13 Q = ∅; 14 return; 15 Let T be the set of statements in XR but not in ps; 16 if ∃ t ∈ T : t does not reach s then 17 return; 18 if ∃ u ∈ ps : s ⇒ u ∈ DR \ XR then 19 if s ∈ ps : s ⇒ u ∈ XR then 20 return; 21 foreach s ∈ pred(s) in the ICFG restricted to GR do 22 if s was not previously enqueued then 23 Enqueue(Q, s ) 24 RECSELECT(); 25 return; Example 4. For the four representative paths in Figure 5, their corresponding path-based slices are given in Figure 6. C. Automatic Test Case Generation Each path-based slice exhibits one single path. A path condition that consists of all the constraints governing the execution of the path is collected and solved to find all the test inputs for exercising the path. There are some SMT solvers around [39]–[41]. However, we have written one ourselves in order to handle a variety of object-oriented constraints more comprehensively, including instanceof, isAssignableFrom, and type casts. Example 5. For the four path-based slices generated in Figure 6, their corresponding test cases are given in Figure 7. For the path-based slice named A, some path constraints are args.length > 0, className = args[0] (an assig nment) , this.infoChanged = false (an assignment), this.infoChanged == false, and pmd.cpd.Rende rer.class.isAssignableFrom(clz). Solving this path condition yields the four test inputs given in Figure 7. 18

D.Instrumented Execution ing class.newInstance ()Method.invoke()and For each path-based slice generated for a du-chain group Constructor.newInstance ()the three widely used XR,we will create an executable program by adding some Java reflection API in the application code of a program. missing declaration statements to the slice.In addition,we will synthesize a pseudo main (method to call all the source TABLE I:Program characteristics methods (with no predecessors)in GR.By construction,for Program #Classes #Methods #Statements every du-chain in XR,its path-based slice always contains a batikl.7 5148 32347 581106 findbugs-1.2.1 4692 28857 472647 source method that can make a sequence of method calls so freecs1.3 3714 24000 418731 that the du-chain holds (Section III-A). gruntspud-0.4.6-beta 4945 31684 527433 In Figure 9,the pseudo main()synthesized will call d(), h2-1.3.172 4139 30208 518189 since d()reaches the other three methods a().c()and b().so Edit-5.1.0 5135 34402 586647 ifreechart-1.0.19 451I 30596 534615 that the du-chain s1→s2→s3→s4 will be established. ip-1.6 5208 35739 659927 Example 6.For the four path-based slices in Figure 6.the pmd-4.2.3 3936 25068 422054 xalan-2.4.1 3483 21755 37300R pseudo main (is simply set as the original main ()which Total 4491I 294656 5094357 happens to be the only source node in GA2 (Figure 3).The declaration statements such as the ones for className and c)Computing Platform:Our plaform is an Intel i5- getM will be added in the final executables generated. O 4570 3.20 GHz machine(running Windows 7)with 16GB of IV.EVALUATION RAM.The analysis time of a program is the average of 5 runs. Our evaluation addresses three research questions: A.RO1:Refection Analysis RQ1.Can MIRROR assist TAMIFLEX [17],a state-of-the- Table II contains our main results.MIRROR can assist art dynamic reflection analysis tool,to resolve more (true) a state-of-the-art dynamic reflection analysis tool,TAMI- reflective targets in real-world applications efficiently and precisely while maintaining a good degree of soundness? FLEX [17],to find significantly more reflective calls and (true) RQ2.Is MIRROR's reflection-oriented slicing capable of reflective targets in real-world applications efficiently.For the 10 programs evaluated,MIRROR reports no false reflective avoiding many irrelevant methods (statements)introduced targets,demonstrating also the validity of Observation 1. by traditional slicing and including only the relevant reflection-related methods (statements)? TABLE II:Comparing MIRROR and TAMIFLEX in terms of RO3.Can MIRROR's reflection resolution solve path con- reflective calls and (true)refective targets found. ditions effectively during automatic test case generation? TAMIFLEX MIRROR TAMIFLEX n MIRROR a)Implementation:We have implemented MIRROR in #Ref Calls #Targets#Ref Calls #Targets #Ref Calls #Targets SOoT [27],a static analysis framework for Java,in 10 KLOC bauik 4 6 of Java code.Our analysis operates on the ICFG of the ndbugs program expressed in the Jimple IR constructed by SooT with freecs 6 59 gruntspud its demand-driven context-sensitive pointer analysis.We make 19 10 12 use of the program's call graph and def-use chains built this Edit 40 way.For each sliced program,we transform it into a jar file ifreechart 4 6 13 and report the reflective targets detected under the test inputs ftp 4 10 16 28 pmd 10 2 automatically generated by MIRROR xalan 56 b)Benchmarks:We consider a set of 10 large,widely- Total 48 154 67 165 7 30 used open-source Java applications evaluated under a large Java library.JDK 1.6.0_45,and test each with 8GB heap space. When running TAMIFLEX on a program,some test cases are As shown in Table I,our 10 open-source programs are needed.For the six GUI programs,findbugs,gruntspud, selected from a wide range of application areas:batik1.7 h2,jEdit,jfreechart and jftp,we exercise their GUI (a SVG toolkit).findbugs-1.2.1 (a bug detector), to invoke their main functionalities just like a user does,in 5 freecs1.3 (a chat server),gruntspud-0.4.6-beta minutes each.Take jfreechart as an example.We exercise (a graphical CVS client),h2-1.3.172 (a database man- its GUI by designing different charts and exporting them to agement system),jEdit-5.1.0 (a software text editor), files.There are four non-GUI programs.For batik,pmd and jfreechart-1.0.19 (a chart library),jftp-1.6 (a net- xalan,we have designed 10 test cases each guided by their work browser),pmd-4.2.5 (a source code analyzer),and user tutorials in order to exercise their main functionalities xalan-2.4.1 (a XSLT processor). When applying MIRROR to a program,we focus on the For each program,we list the number of classes, reflective calls that are identified by Soor and analyzed methods and Jimple statements reported by Soor that scalably under a budget (discussed below).For freecs,a are reachable from its main()in both the appli- chat server,we start it up for it to read several configuration cation and library code.We will focus on analyz- files (without providing any explicit input from us). 19

D. Instrumented Execution For each path-based slice generated for a du-chain group XR, we will create an executable program by adding some missing declaration statements to the slice. In addition, we will synthesize a pseudo main() method to call all the source methods (with no predecessors) in GR. By construction, for every du-chain in XR, its path-based slice always contains a source method that can make a sequence of method calls so that the du-chain holds (Section III-A). In Figure 9, the pseudo main() synthesized will call d(), since d() reaches the other three methods a(), c() and b(), so that the du-chain s1 ⇒ s2 ⇒ s3 ⇒ s4 will be established. Example 6. For the four path-based slices in Figure 6, the pseudo main() is simply set as the original main(), which happens to be the only source node in G42 (Figure 3). The declaration statements such as the ones for className and getM will be added in the final executables generated. IV. EVALUATION Our evaluation addresses three research questions: • RQ1. Can MIRROR assist TAMIFLEX [17], a state-of-the￾art dynamic reflection analysis tool, to resolve more (true) reflective targets in real-world applications efficiently and precisely while maintaining a good degree of soundness? • RQ2. Is MIRROR’s reflection-oriented slicing capable of avoiding many irrelevant methods (statements) introduced by traditional slicing and including only the relevant reflection-related methods (statements)? • RQ3. Can MIRROR’s reflection resolution solve path con￾ditions effectively during automatic test case generation? a) Implementation: We have implemented MIRROR in SOOT [27], a static analysis framework for Java, in 10 KLOC of Java code. Our analysis operates on the ICFG of the program expressed in the Jimple IR constructed by SOOT with its demand-driven context-sensitive pointer analysis. We make use of the program’s call graph and def-use chains built this way. For each sliced program, we transform it into a jar file and report the reflective targets detected under the test inputs automatically generated by MIRROR. b) Benchmarks: We consider a set of 10 large, widely￾used open-source Java applications evaluated under a large Java library, JDK 1.6.0 45, and test each with 8GB heap space. As shown in Table I, our 10 open-source programs are selected from a wide range of application areas: batik1.7 (a SVG toolkit), findbugs-1.2.1 (a bug detector), freecs1.3 (a chat server), gruntspud-0.4.6-beta (a graphical CVS client), h2-1.3.172 (a database man￾agement system), jEdit-5.1.0 (a software text editor), jfreechart-1.0.19 (a chart library), jftp-1.6 (a net￾work browser), pmd-4.2.5 (a source code analyzer), and xalan-2.4.1 (a XSLT processor). For each program, we list the number of classes, methods and Jimple statements reported by SOOT that are reachable from its main() in both the appli￾cation and library code. We will focus on analyz￾ing Class.newInstance(), Method.invoke() and Constructor.newInstance(), the three widely used Java reflection API in the application code of a program. TABLE I: Program characteristics Program #Classes #Methods #Statements batik1.7 5148 32347 581106 findbugs-1.2.1 4692 28857 472647 freecs1.3 3714 24000 418731 gruntspud-0.4.6-beta 4945 31684 527433 h2-1.3.172 4139 30208 518189 jEdit-5.1.0 5135 34402 586647 jfreechart-1.0.19 4511 30596 534615 jftp-1.6 5208 35739 659927 pmd-4.2.5 3936 25068 422054 xalan-2.4.1 3483 21755 373008 Total 44911 294656 5094357 c) Computing Platform: Our plaform is an Intel i5- 4570 3.20 GHz machine (running Windows 7) with 16GB of RAM. The analysis time of a program is the average of 5 runs. A. RQ1: Reflection Analysis Table II contains our main results. MIRROR can assist a state-of-the-art dynamic reflection analysis tool, TAMI￾FLEX [17], to find significantly more reflective calls and (true) reflective targets in real-world applications efficiently. For the 10 programs evaluated, MIRROR reports no false reflective targets, demonstrating also the validity of Observation 1. TABLE II: Comparing MIRROR and TAMIFLEX in terms of reflective calls and (true) reflective targets found. Program TAMIFLEX MIRROR TAMIFLEX ∩ MIRROR #Ref Calls #Targets #Ref Calls #Targets #Ref Calls #Targets batik 3 4 1 6 1 1 findbugs 3 3 3 4 2 2 freecs 6 6 6 59 3 3 gruntspud 5 8 7 7 2 2 h2 7 19 10 18 4 12 jEdit 4 40 6 12 1 1 jfreechart 4 6 13 13 1 1 jftp 4 10 16 28 1 5 pmd 1 2 2 10 1 2 xalan 11 56 3 8 1 1 Total 48 154 67 165 17 30 When running TAMIFLEX on a program, some test cases are needed. For the six GUI programs, findbugs, gruntspud, h2, jEdit, jfreechart and jftp, we exercise their GUI to invoke their main functionalities just like a user does, in 5 minutes each. Take jfreechart as an example. We exercise its GUI by designing different charts and exporting them to files. There are four non-GUI programs. For batik, pmd and xalan, we have designed 10 test cases each guided by their user tutorials in order to exercise their main functionalities. When applying MIRROR to a program, we focus on the reflective calls that are identified by SOOT and analyzed scalably under a budget (discussed below). For freecs, a chat server, we start it up for it to read several configuration files (without providing any explicit input from us). 19

TABLE III:Efficiency and effectiveness of MIRROR.For efficiency,the last column gives the analysis time spent by MIRROR (in all its four stages).The second last column gives the analysis time spent by SooT on performing its pointer analysis and building the call graph,ICFG and def-use chains.For effectiveness,the results in Table II are further analyzed.For each type of Java reflection API considered,the number of new reflective calls and reflective targets found by MIRROR relative to TAMIFLEX are given.The number of additional call-graph edges reachable from these new reflective targets are also given. TAMIFLEX MIRROR Reflection API Increased Call-Graph Edges Analysis Times (secs) Program #Calls #Targets #Calls #Targets App App Lib SOOT MIRROR Class.newInstance (+)0 (+)5 batik Method.invoke NA NA (+)0 (+0 Constructor.newInstance N/A (+0 (+)74 179.6 310.2 (+0 (+)637 Total (+0 (+5 Class.newInstance (+)0 (+)0 findbugs Method.invoke N/A N/A (+)1 (+)2 (+)22328 117.2 237.9 Constructor.newInstance +)0 (+0 (+)134769 Total +1 (+2 Class.newInstance (+)1 (+)1 Method.invoke freecs (+)2 (+)55 (+)728 Constructor.newInstance (+)0 (+)0 (+)60965 70.5 282.1 Total (+)3 (+)56 Class.newInstance (+)0 (+0 Method invoke +5 (+5 gruntspud Constructor.newInstance N/A N/A (+)0 (+0 (+)5 (+)120887 117.4 395.8 Total (+)5 (+)5 Class.newInstance 10 (+)2 (+2 h2 Method.invoke (+4 (+4 Constructor.newInstance +0 (+0 (+)22 (+)360300 103.9 451.7 Total 9 +)6 +6 Class.newInstance (+)3 (+)3 jEdit Method.invoke 10 (+2 (+)8 Constructor.newInstance 29 (+0 (+)0 (+)174949 (+)498536 133.9 375.4 Total 40 (+5 (+)T Class.newInstance N/A N/A (+)2 (+)2 jfreechart Method.invoke (+)9 (+)9 (+)97590 (+)1042689 Constructor.newInstance (+)I 122.7 244.2 +)I Total (+)12 +)12 Class.newInstance (+)13 (+)2I Method.invoke 3 (+)2 (+2 jftp N/A (+)94 (+)121745 157.2 950.6 Constructor.newInstance (+0 (+0 Total 4 10 (+)15 (+)23 Class.newInstance (+)1 (+)8 Method.invoke A A +0 (+0 pmd Constructor.newInstance N/A +0 (+0 (+)176 (+)150519 70.8 77.2 Total 2 +)I (+)8 Class.newInstance 28 (+)2 (+)7 xalan Method.invoke 28 (+)0 (+)0 (+)264 (+)121568 65.7 303.1 Constructor.newInstance N/A (+)0 (+)0 Total 11 56 (+)2 (+)7 Average 15 (+)5 (+)14 (+)29623 (+)261261 113.9 362.8 Looking at Table II,we find that MIRROR is complementary reflection analysis in practice.Second,for the remaining to TAMIFLEX.Indeed,MIRROR is actually designed to play reflective calls totaling 18 in TAMIFLEX-TAMIFLEX MIR- this important role by filling a gap left by pure static and ROR (visible to MIRROR),MIRROR's call-graph reduction is dynamic reflection analysis.For these two tools,neither is unscalable(due to the inherent complexity of program slicing), strictly more sound than the other.There are reflective calls despite its significant better scalability than traditional slicing. that can be resolved by TAMIFLEX but not by MIRROR as discussed later.This happens when their du-chains usually (TAMIFLEX-TAMIFLEX n MIRROR).There are two reasons span across many methods,highlighting an important avenue behind.First,there are 13 reflective calls that are invisible for future research on reflection-oriented slicing. to MIRROR,with 2 in batik,I in findbugs and 10 in Conversely.there are reflective calls that can be resolved by xalan.This happens since Soor (and other static tools,in MIRROR but missed by TAMIFLEX (MIRROR-TAMIFLEX n general)cannot soundly build the call graph for a program due MIRROR)since these calls are not reached during program to its inadequate modeling of dynamic class loading,reflection execution.MIRROR resolves more reflective calls in every and native libraries,highlighting again the significance of application except batik.In particular,MIRROR finds 56 20

TABLE III: Efficiency and effectiveness of MIRROR. For efficiency, the last column gives the analysis time spent by MIRROR (in all its four stages). The second last column gives the analysis time spent by SOOT on performing its pointer analysis and building the call graph, ICFG and def-use chains. For effectiveness, the results in Table II are further analyzed. For each type of Java reflection API considered, the number of new reflective calls and reflective targets found by MIRROR relative to TAMIFLEX are given. The number of additional call-graph edges reachable from these new reflective targets are also given. Program Reflection API TAMIFLEX MIRROR Increased Call-Graph Edges Analysis Times (secs) #Calls #Targets #Calls #Targets App App + Lib SOOT MIRROR batik Class.newInstance 3 4 (+)0 (+)5 (+)74 (+)637 179.6 310.2 Method.invoke N/A N/A (+)0 (+)0 Constructor.newInstance N/A N/A (+)0 (+)0 Total 3 4 (+)0 (+)5 findbugs Class.newInstance 2 2 (+)0 (+)0 (+)22328 (+)134769 117.2 237.9 Method.invoke N/A N/A (+)1 (+)2 Constructor.newInstance 1 1 (+)0 (+)0 Total 3 3 (+)1 (+)2 freecs Class.newInstance 3 3 (+)1 (+)1 (+)728 (+)60965 70.5 282.1 Method.invoke 1 1 (+)2 (+)55 Constructor.newInstance 2 2 (+)0 (+)0 Total 6 6 (+)3 (+)56 gruntspud Class.newInstance 2 5 (+)0 (+)0 (+)5 (+)120887 117.4 395.8 Method.invoke 3 3 (+)5 (+)5 Constructor.newInstance N/A N/A (+)0 (+)0 Total 5 8 (+)5 (+)5 h2 Class.newInstance 2 10 (+)2 (+)2 (+)22 (+)360300 103.9 451.7 Method.invoke 4 8 (+)4 (+)4 Constructor.newInstance 1 1 (+)0 (+)0 Total 7 19 (+)6 (+)6 jEdit Class.newInstance 1 1 (+)3 (+)3 (+)174949 (+)498536 133.9 375.4 Method.invoke 2 10 (+)2 (+)8 Constructor.newInstance 1 29 (+)0 (+)0 Total 4 40 (+)5 (+)11 jfreechart Class.newInstance N/A N/A (+)2 (+)2 (+)97590 (+)1042689 122.7 244.2 Method.invoke 3 5 (+)9 (+)9 Constructor.newInstance 1 1 (+)1 (+)1 Total 4 6 (+)12 (+)12 jftp Class.newInstance 1 7 (+)13 (+)21 (+)94 (+)121745 157.2 950.6 Method.invoke 3 3 (+)2 (+)2 Constructor.newInstance N/A N/A (+)0 (+)0 Total 4 10 (+)15 (+)23 pmd Class.newInstance 1 2 (+)1 (+)8 (+)176 (+)150519 70.8 77.2 Method.invoke N/A N/A (+)0 (+)0 Constructor.newInstance N/A N/A (+)0 (+)0 Total 1 2 (+)1 (+)8 xalan Class.newInstance 7 28 (+)2 (+)7 (+)264 (+)121568 65.7 303.1 Method.invoke 4 28 (+)0 (+)0 Constructor.newInstance N/A N/A (+)0 (+)0 Total 11 56 (+)2 (+)7 Average 5 15 (+)5 (+)14 (+)29623 (+)261261 113.9 362.8 Looking at Table II, we find that MIRROR is complementary to TAMIFLEX. Indeed, MIRROR is actually designed to play this important role by filling a gap left by pure static and dynamic reflection analysis. For these two tools, neither is strictly more sound than the other. There are reflective calls that can be resolved by TAMIFLEX but not by MIRROR (TAMIFLEX- TAMIFLEX ∩ MIRROR). There are two reasons behind. First, there are 13 reflective calls that are invisible to MIRROR, with 2 in batik, 1 in findbugs and 10 in xalan. This happens since SOOT (and other static tools, in general) cannot soundly build the call graph for a program due to its inadequate modeling of dynamic class loading, reflection and native libraries, highlighting again the significance of reflection analysis in practice. Second, for the remaining reflective calls totaling 18 in TAMIFLEX- TAMIFLEX ∩ MIR￾ROR (visible to MIRROR), MIRROR’s call-graph reduction is unscalable (due to the inherent complexity of program slicing), despite its significant better scalability than traditional slicing, as discussed later. This happens when their du-chains usually span across many methods, highlighting an important avenue for future research on reflection-oriented slicing. Conversely, there are reflective calls that can be resolved by MIRROR but missed by TAMIFLEX (MIRROR- TAMIFLEX ∩ MIRROR) since these calls are not reached during program execution. MIRROR resolves more reflective calls in every application except batik. In particular, MIRROR finds 56 20

TABLE IV:Comparing reflection-oriented and traditional slicing in terms of slice sizes and slicing times.For a program,a slice is measured by the number of methods/statements sliced for all its reflective calls considered(Column 4 of Table II).For the traditional slicer,"TO(x/y)"indicates that out of y reflective calls analyzed,x Times Out under the budget allocated. Program Budget Reflection-Oriented Slicing Traditional Slicing (mins) #Mtds #Stmts Time(secs)】 #Mtds #Stmts Time (secs) batik 40 12 1I7 4.3 2080 16244 TO (1/1) findbugs 55 12 91 3.4 3081 18893 TO(2/3) freecs 90 71 746 78.9 2403 22032 T0(5/6) gruntspud 50 11 129 33.6 9382 53304 T0(67) h2 150 19 138 63.7 23757 162117 T0(7/10の iEdit 130 12 124 7.1 7691 49452 T03/6) ifreechart 65 21 211T 3.6 40883 346618 TO1313) iftp 150 63 1676 40.5 22956 189145 T0I2I16) pmd 75 10 104 3.5 10 109 0.1(0/2) xalan 30 6 572 120.4 125 2295 T0(1/3) Average 84 24 391T 35.9 1I237 86021 TO(57) new targets in freecs,because it has activated a path with human efforts to manually launch GUI operations (in order to many reflective targets read from a file generate user inputs for these applications). For all the 10 programs,TAMIFLEX finds 154 targets at 48 reflective calls and MIRROR finds 165 targets at 67 reflective B.RO2:Reflection-Oriented Slicing calls.In total,MIRROR resolves 104.2%more reflective calls and 87.7%more reflective targets,measured by (((MIRROR Table IV compares MIRROR's reflection-oriented slicer with -TAMIFLEX n MIRROR)/TAMIFLEX)X 100)%.MIRROR a backward slicer that we have implemented in SooT based discovers reflective targets that are not found by TAMIFLEX in on traditional slicing [23].[24]to reconfirm its known un- all programs.For reflective calls,the percentage improvements scalability for object-oriented programs [25],[26].For each range from 0.0%(batik)to 375.0%(jftp)with an average program,Table II(Column 4)gives the number of reflective of 118.7%.For reflective targets,the percentage improvements calls analyzed by MIRROR.For both slicers,the same time range from 12.5%(xalan)to 933.3%(freecs)with an budget is allocated to a program (Column 2 in Table IV). average of 208.9%. which is calculated as follows.For each program,MIRROR Finally,Table IlI provides a breakdown of the results computes path-based slices separately for its representative in Table II on the effectiveness of MIRROR,together with paths constructed at its reflective calls analyzed.Looking the analysis times of MIRROR for the 10 programs to ahead in Figure 10,the number of representative paths per demonstrate its efficiency.Due to the new reflective targets program ranges from 6(xalan)to 30(h2 and iftp)with discovered,MIRROR enables between 5 (gruntspud) an average of 17.The average number of paths per reflective and 174949 (jedit)call-graph edges to be reached from call ranges from 1 (jfreechart)to 8 (batik)with an these new targets in the application code.These numbers average of 4.For MIRROR,each path is given a maximum of increase to 637 (batik)and 1042689 (jfreechart), 5 minutes to be sliced.If a reflective call has N representative respectively,if the library code is also included.For example, paths,then the traditional slicer is given a maximum of 5*N in findbugs,MIRROR finds only two new reflectively called minutes to slice from the reflective call. methods,findbugs.qui.FindBugsFrame.main ( As is clear from Table IV,MIRROR is far superior to the and findbugs.qui2.Driver.main ()However,both traditional slicer.On average,MIRROR spends 35.9 seconds methods can reach 22328 call-graph edges in the application while including at least 89.1%fewer methods and 87.4% code and 134769 call-graph edges if the library code is also fewer statements than the traditional slicer.Note the use of"at considered.These call-graph edges found can significantly least'”here.As indicated in Column“TO(r/y)”,the traditional increase the code coverage of a variety of bug detection and slicer times out in x out of y reflective calls analyzed in a security analysis tools. program.Note that a slice produced by the traditional slicer As for efficiency,MIRROR spends an average of only 362.8 includes the methods and statements obtained before it times seconds (i.e.,just above 6 minutes)on analyzing a program, out.The traditional slicer remains unscalable for these time- by performing the fastest for pmd (in 77.2 seconds)and the outed calls even if the budget is tripled,causing more methods slowest for jftp (in 950.6 seconds).It is not informative to and statements to be included in their slices. compare TAMIFLEX and MIRROR in terms of their analysis Both slicers obtain similar results for pmd and xalan, times.MIRROR is fully automatic without requiring any user since the reflective calls analyzed are close to main ()The inputs.However,TAMIFLEX can only run under some given traditional slicer is faster for pmd (with only one reflective inputs.As discussed in Section I,when applying TAMIFLEX call analyzed),since MIRROR needs to spend some time on to analyze GUI applications,the user needs to spend a lot of building the sub-call graph even for analyzing just one call. 21

TABLE IV: Comparing reflection-oriented and traditional slicing in terms of slice sizes and slicing times. For a program, a slice is measured by the number of methods/statements sliced for all its reflective calls considered (Column 4 of Table II). For the traditional slicer, “TO (x/y)” indicates that out of y reflective calls analyzed, x Times Out under the budget allocated. Program Budget (mins) Reflection-Oriented Slicing Traditional Slicing #Mtds #Stmts Time (secs) #Mtds #Stmts Time (secs) batik 40 12 117 4.3 2080 16244 TO (1/1) findbugs 55 12 91 3.4 3081 18893 TO (2/3) freecs 90 71 746 78.9 2403 22032 TO (5/6) gruntspud 50 11 129 33.6 9382 53304 TO (6/7) h2 150 19 138 63.7 23757 162117 TO (7/10) jEdit 130 12 124 7.1 7691 49452 TO (3/6) jfreechart 65 21 211 3.6 40883 346618 TO (13/13) jftp 150 63 1676 40.5 22956 189145 TO (12/16) pmd 75 10 104 3.5 10 109 0.1 (0/2) xalan 30 6 572 120.4 125 2295 TO (1/3) Average 84 24 391 35.9 11237 86021 TO (5/7) new targets in freecs, because it has activated a path with many reflective targets read from a file. For all the 10 programs, TAMIFLEX finds 154 targets at 48 reflective calls and MIRROR finds 165 targets at 67 reflective calls. In total, MIRROR resolves 104.2% more reflective calls and 87.7% more reflective targets, measured by (((MIRROR − TAMIFLEX ∩ MIRROR)/TAMIFLEX) × 100)%. MIRROR discovers reflective targets that are not found by TAMIFLEX in all programs. For reflective calls, the percentage improvements range from 0.0% (batik) to 375.0% (jftp) with an average of 118.7%. For reflective targets, the percentage improvements range from 12.5% (xalan) to 933.3% (freecs) with an average of 208.9%. Finally, Table III provides a breakdown of the results in Table II on the effectiveness of MIRROR, together with the analysis times of MIRROR for the 10 programs to demonstrate its efficiency. Due to the new reflective targets discovered, MIRROR enables between 5 (gruntspud) and 174949 (jedit) call-graph edges to be reached from these new targets in the application code. These numbers increase to 637 (batik) and 1042689 (jfreechart), respectively, if the library code is also included. For example, in findbugs, MIRROR finds only two new reflectively called methods, findbugs.gui.FindBugsFrame.main() and findbugs.gui2.Driver.main(). However, both methods can reach 22328 call-graph edges in the application code and 134769 call-graph edges if the library code is also considered. These call-graph edges found can significantly increase the code coverage of a variety of bug detection and security analysis tools. As for efficiency, MIRROR spends an average of only 362.8 seconds (i.e., just above 6 minutes) on analyzing a program, by performing the fastest for pmd (in 77.2 seconds) and the slowest for jftp (in 950.6 seconds). It is not informative to compare TAMIFLEX and MIRROR in terms of their analysis times. MIRROR is fully automatic without requiring any user inputs. However, TAMIFLEX can only run under some given inputs. As discussed in Section I, when applying TAMIFLEX to analyze GUI applications, the user needs to spend a lot of human efforts to manually launch GUI operations (in order to generate user inputs for these applications). B. RQ2: Reflection-Oriented Slicing Table IV compares MIRROR’s reflection-oriented slicer with a backward slicer that we have implemented in SOOT based on traditional slicing [23], [24] to reconfirm its known un￾scalability for object-oriented programs [25], [26]. For each program, Table II (Column 4) gives the number of reflective calls analyzed by MIRROR. For both slicers, the same time budget is allocated to a program (Column 2 in Table IV), which is calculated as follows. For each program, MIRROR computes path-based slices separately for its representative paths constructed at its reflective calls analyzed. Looking ahead in Figure 10, the number of representative paths per program ranges from 6 (xalan) to 30 (h2 and iftp) with an average of 17. The average number of paths per reflective call ranges from 1 (jfreechart) to 8 (batik) with an average of 4. For MIRROR, each path is given a maximum of 5 minutes to be sliced. If a reflective call has N representative paths, then the traditional slicer is given a maximum of 5 ∗ N minutes to slice from the reflective call. As is clear from Table IV, MIRROR is far superior to the traditional slicer. On average, MIRROR spends 35.9 seconds while including at least 89.1% fewer methods and 87.4% fewer statements than the traditional slicer. Note the use of “at least” here. As indicated in Column “TO (x/y)”, the traditional slicer times out in x out of y reflective calls analyzed in a program. Note that a slice produced by the traditional slicer includes the methods and statements obtained before it times out. The traditional slicer remains unscalable for these time￾outed calls even if the budget is tripled, causing more methods and statements to be included in their slices. Both slicers obtain similar results for pmd and xalan, since the reflective calls analyzed are close to main(). The traditional slicer is faster for pmd (with only one reflective call analyzed), since MIRROR needs to spend some time on building the sub-call graph even for analyzing just one call. 21