A survey of static analysis methods for identifying security vulnerabilities in software systems <s> The MARCO algorithm <s> A technique is presented for global analysis of program structure in order to perform compile time optimization of object code generated for expressions. The global expression optimization presented includes constant propagation, common subexpression elimination, elimination of redundant register load operations, and live expression analysis. A general purpose program flow analysis algorithm is developed which depends upon the existence of an "optimizing function." The algorithm is defined formally using a directed graph model of program flow structure, and is shown to be correct. Several optimizing functions are defined which, when used in conjunction with the flow analysis algorithm, provide the various forms of code optimization. The flow analysis algorithm is sufficiently general that additional functions can easily be defined for other forms of global code optimization. <s> BIB001 </s> A survey of static analysis methods for identifying security vulnerabilities in software systems <s> The MARCO algorithm <s> In Java 2 and Microsoft.NET Common Language Runtime (CLR), trusted code has often been programmed to perform access-restricted operations not explicitly requested by its untrusted clients. Since an untrusted client will be on the call stack when access control is enforced, an access-restricted operation will not succeed unless the client is authorized. To avoid this, a portion of the trusted code can be made privileged. When access control is enforced, privileged code causes the stack traversal to stop at the trusted code frame, and the untrusted code stack frames will not be checked for authorization. For large programs, manually understanding which portions of code should be made privileged is a difficult task. Developers must understand which authorizations will implicitly be extended to client code and make sure that the values of the variables used by the privileged code are not tainted by client code. This paper presents an interprocedural analysis for Java bytecode to automatically identify which portions of trusted code should be made privileged, ensure that there are no tainted variables in privileged code, and detect unnecessary and redundant privileged code. We implemented the algorithm and present the results of our analyses on a set of large programs. While the analysis techniques are in the context of Java code, the basic concepts are also applicable to non-Java systems with a similar authorization model. <s> BIB002
In this section, we review static analysis algorithms based on the Mandatory Access Rights Certification of Objects (MARCO) algorithm.  BIB002 The MARCO algorithm has been implemented and released as part of the IBM Security Workbench Development for Java (SWORD4J).  The Java SBAC architecture mandates that, at the point where checkPermission is invoked with a Permission parameter p, all the code on the execution thread's stack be granted the authorization represented by p. MARCO computes permission requirements by modeling the stack inspection mechanism on a computed call graph G ¼ (N, E), representing the execution of the program. For each call graph node n corresponding to a checkPermission call, MAR-CO identifies a set of abstract Permission objects that may flow to n as a parameter. The tool solves a data-flow problem, propagating sets of Permission abstract objects backward in G, until a fixed point is reached. BIB001 In Java, permission requirements propagated on the stack by a call to doPrivileged do not propagate beyond the predecessors of the doPrivileged node itself. MARCO handles this precisely by killing dataflow propagation of upwardly exposed permissions at doPrivileged nodes, and computing permission requirements for doPrivileged predecessors as a post-pass to the fixed-point computation. When the data-flow algorithm just described terminates, each node n 2 N is mapped to a set P(n) of Permission abstract objects. P(n) over-approximates the permissions required to execute the method modeled by n. MARCO can help detect which code could be made privilege asserting, while minimizing the risks of violating the Principle of Least Privilege. A static analysis of Java's class-loading behavior can identify intercomponent calls. If e ¼ (m, n) is an intercomponent edge and P(n) 6 ¼ Ø, then the call represented by e can potentially lead to a securitysensitive resource access. Such a call is a candidate for a privilege-asserting block. For example, e may be the edge resulting from calling the constructor of FileOutputStream from method createSocket in Figure 1 . Figure 2 shows how to wrap the FileOutputStream constructor call into a privilege-asserting block. As described, MARCO's analysis of permissions on intercomponent edges suffices to determine component code that is a candidate for privilege assertion and to identify the associated permissions. Additionally, the tool can recommend privilegeasserting code locations that lie closest to the authorization checks.  If code does not require authorizations, it is poor security practice to include it in privilege-asserting code.  For example, the following instruction in the run method of Figure 5 appears in a privilegeasserting block even though it does not access restricted resources: Such code should be moved to a non-privilegeasserting block of code even though, in this case, P(d) 6 ¼ Ø. MARCO can statically detect statements that have unnecessarily been inserted into otherwise valid privilege-asserting blocks. Specifically, let d be a doPrivileged node and r its PrivilegedAction or PrivilegedExceptionAction run successor. If P(r) 6 ¼ Ø and r has a successor node n such that P(n) ¼ Ø, then the method invocation represented