MQP:Static Analysis Strategies
|
Overview
This page summarizes some of our discussions on strategies for performing static analysis to infer permissions.
Goals
The best tool that we envision would be able to infer the permissions required at each program point. Showing this level of detail would give a developer the best chance to understand the security requirements of code. With this analysis, it would be simple to accomplish our more baseline objective, that of inferring the permissions required by an application at each method and class. This would be the minimum required to create a policy file that granted the needed permissions to the code. From either analysis, we would need to store the security data in an intermediate format to easily inform a dynamic or run time analysis at a later time. This format could also aid in the construction of policy files for the application.
Baseline Analysis
The methods we are considering for the baseline analysis are based on using graph searching algorithms on a call graph of the application. The general strategy is to find the points where checkPermission is called in the program, and traverse the graph against the direction of method invocation. That is, each method that could call the method containing the checkPermission call would be traversed. At each of these points, the method would be marked as requiring that permission and then all methods that invoke it would be recursively traverse in the same fashion.
There are a few special cases and stopping conditions for this algorithm. First, if a node (method) is reached in the graph and it is already marked with the set of permissions that need to be added, the current branch of the graph traversal can stop. Second, the doPrivileged() operator is a stopping condition as well, as it indicates that the code it annotates is responsible for encapsulating the current security context. Third, when a Thread object is passed to a different context, it needs to reflect that the context constructing the Thread requires the current set of permissions. These are general descriptions of the strategies and need to be formalized more. They are also based on some observations from Larry Koved's paper.
Deep Analysis
The deep analysis would provide a more detailed view of the permissions required by inferring the permissions at each program point. For example, it may be possible to show that a certain permission will be required only if a certain branch of an if statement is taken. This would normally not affect the policy file or permissions required by the application, as it is assumed that both branches of the if statement would execute at some point. However, this could be quite a useful tool for developers, who would be able to see what parts of their code they could move or edit to better encapsulate or understand the security requirements of a program.
To do this, the analysis would follow a similar pattern as the baseline analysis, with the exception of looking at special code blocks or groups of statements, like if-else blocks. Where there is a branching operation, the different blocks could be marked as needing different sets of permissions. While the method containing these blocks would still require all of the permissions contained within, it would be possible to see which parts of the method use the required permissions.
Special Cases
- A full example handling of the Thread.start() case is available here
- For calls to doPrivileged, the graph traversal simply terminates at nodes that have a edge from the doPrivileged method entering into them.
- Some applications have methods that anticipate SecurityExceptions being thrown, and so may not actually require the grant for the Permission object that is passed to a checkPermission call. This case is similar to the doPrivileged case, since the graph traversal does not need to continue past the method that caught the SecurityException, except in the case where there are transitive calls to checkPermission in the catch block, which need to be handled separately.
Locating Arguments Passed to Permission Constructors
Once the program point that calls SecurityManager.checkPermission is found, it is simple to extract the expression that is passed as the Permission argument to the method. From this program point, the list of statements in the body of the method is traversed backwards to find an instance of the constructor call to the relevant Permission type, or assignment statements to the variable passed to checkPermission. This analysis only considers the method that called checkPermission, which is a simplifying assumption. If the constructor is found, then the expressions passed to the constructor can be extracted, and a similar traversal can be performed on these expressions to find their initialization. The difference in this case is that these expressions (almost always String objects), are often declared as static fields, so the static initializers of the relevant methods are also inspected to find definitions of static fields. This analysis is sufficient for many simple cases, but misses many others, most commonly when the expressions passed to the Permission constructor come into the method as parameters and their runtime values are more difficult (or impossible) to determine.
Much of the simplicity of this traversal is due to the intermediate format Jimple from Soot, which simplifies compound expressions in Java statements. This creates a number of extra, temporary local variables, which makes the each relevant program point into either an assignment statement or a method invocation. At the moment, this analysis does not take into account branching in the control flow of the method, which could lead to finding multiple possible values for each argument. In this case, it would be necessary to report all possible values that could be found, leading to a more complicated result set.
Current Work
At the moment, we have completed the basic structure of the baseline analysis algorithm. Using the CallGraph created in the Soot analysis, we can find which methods call checkPermissions. Then we can traverse the call graph and accumulate the Permissions in the methods that can reach the permission-requiring methods. The result is a collection of Permissions needed by each method annotated by which method the Permission was originally checked in. This information has been integrated with the data structures for the analysis model to provide an organized way to represent the results in the eventual application.
Some issues that exist currently and may be worked out as the project progresses are:
- The call graph is large for several reasons, the most prominent of which is the difficulty of resolving virtual method calls. This leads to a overly conservative analysis.
- The analysis to find the fields of Permission objects is limited, which makes the results less valuable in some cases.
- The fields of Permission objects need to be further analyzed in many cases to resolve into grants in a policy file, for example parsing the String objects in a SocketPermission to find the actual socket or range of sockets in question.
More?
As the project continues, we may continue to consider different types of analysis with further goals in mind.
