1 /* 2 * Copyright (C) 2018. Uber Technologies 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 package com.uber.nullaway.jarinfer; 17 18 import com.google.common.base.Preconditions; 19 import com.google.common.collect.ImmutableList; 20 import com.google.common.collect.ImmutableMap; 21 import com.ibm.wala.cfg.ControlFlowGraph; 22 import com.ibm.wala.classLoader.IMethod; 23 import com.ibm.wala.ipa.cfg.ExceptionPrunedCFG; 24 import com.ibm.wala.ipa.cfg.PrunedCFG; 25 import com.ibm.wala.ssa.IR; 26 import com.ibm.wala.ssa.ISSABasicBlock; 27 import com.ibm.wala.ssa.SSAAbstractInvokeInstruction; 28 import com.ibm.wala.ssa.SSAGetInstruction; 29 import com.ibm.wala.ssa.SSAInstruction; 30 import com.ibm.wala.ssa.SSAPutInstruction; 31 import com.ibm.wala.ssa.SSAReturnInstruction; 32 import com.ibm.wala.util.collections.Iterator2Iterable; 33 import com.ibm.wala.util.graph.Graph; 34 import com.ibm.wala.util.graph.GraphUtil; 35 import com.ibm.wala.util.graph.dominators.Dominators; 36 import com.ibm.wala.util.graph.impl.GraphInverter; 37 import com.ibm.wala.util.graph.traverse.DFS; 38 import java.util.ArrayList; 39 import java.util.HashMap; 40 import java.util.HashSet; 41 import java.util.Map; 42 import java.util.Set; 43 44 /** 45 * /** Identify definitely-dereferenced function parameters 46 * 47 * @version v0.1 Basic analysis that identifies function parameter dereferences in BBs that 48 * post-dominate the exit node. 49 */ 50 public class DefinitelyDerefedParams { 51 private static final boolean DEBUG = false; 52 private boolean USE_EXTENDED_APPROACH = true; 53 LOG(boolean cond, String tag, String msg)54 private static void LOG(boolean cond, String tag, String msg) { 55 if (cond) { 56 System.out.println("[JI " + tag + "] " + msg); 57 } 58 } 59 60 private final IMethod method; 61 private final IR ir; 62 63 // the exploded control-flow graph without exceptional edges 64 private final ControlFlowGraph<SSAInstruction, ISSABasicBlock> cfg; 65 private PrunedCFG<SSAInstruction, ISSABasicBlock> prunedCFG; 66 67 /** List of null test APIs and the parameter position. */ 68 private static final ImmutableMap<String, Integer> NULL_TEST_APIS = 69 new ImmutableMap.Builder<String, Integer>() 70 .put( 71 "com.google.common.base.Preconditions.checkNotNull(Ljava/lang/Object;)Ljava/lang/Object;", 72 0) 73 .put("java.util.Objects.requireNonNull(Ljava/lang/Object;)Ljava/lang/Object;", 0) 74 .put("org.junit.Assert.assertNotNull(Ljava/lang/Object;)V", 0) 75 .put("org.junit.Assert.assertNotNull(Ljava/lang/String;Ljava/lang/Object;)V", 1) 76 .put("org.junit.jupiter.api.Assertions.assertNotNull(Ljava/lang/Object;)V", 0) 77 .put( 78 "org.junit.jupiter.api.Assertions.assertNotNull(Ljava/lang/Object;Ljava/lang/String;)V", 79 1) 80 .put( 81 "org.junit.jupiter.api.Assertions.assertNotNull(Ljava/lang/Object;Ljava/util/function/Supplier<String>;)V", 82 1) 83 .build(); 84 85 /** 86 * The constructor for the analysis class. 87 * 88 * @param method The target method of the analysis. 89 * @param ir The IR code for the target method. 90 * @param cfg The Control Flow Graph of the target method. 91 */ DefinitelyDerefedParams( IMethod method, IR ir, ControlFlowGraph<SSAInstruction, ISSABasicBlock> cfg)92 DefinitelyDerefedParams( 93 IMethod method, IR ir, ControlFlowGraph<SSAInstruction, ISSABasicBlock> cfg) { 94 this.method = method; 95 this.ir = ir; 96 this.cfg = cfg; 97 prunedCFG = null; 98 } 99 100 /** 101 * This is the core analysis that identifies definitely-dereferenced parameters. 102 * 103 * @return The ordinal indices of formal parameters that are definitely-dereferenced. 104 */ analyze()105 Set<Integer> analyze() { 106 // Get ExceptionPrunedCFG 107 LOG(DEBUG, "DEBUG", "@ " + method.getSignature()); 108 prunedCFG = ExceptionPrunedCFG.make(cfg); 109 // In case the only control flows are exceptional, simply return. 110 if (prunedCFG.getNumberOfNodes() == 2 111 && prunedCFG.containsNode(cfg.entry()) 112 && prunedCFG.containsNode(cfg.exit()) 113 && GraphUtil.countEdges(prunedCFG) == 0) { 114 return new HashSet<>(); 115 } 116 117 // Get number of params and value number of first param 118 int numParam = ir.getSymbolTable().getNumberOfParameters(); 119 int firstParamIndex = 120 method.isStatic() ? 1 : 2; // 1-indexed; v1 is 'this' for non-static methods 121 122 Set<Integer> derefedParamList; 123 if (USE_EXTENDED_APPROACH) { 124 derefedParamList = computeDerefParamList(numParam, firstParamIndex); 125 } else { 126 derefedParamList = computeDerefParamListUsingPDom(numParam, firstParamIndex); 127 } 128 return derefedParamList; 129 } 130 computeDerefParamList(int numParam, int firstParamIndex)131 private Set<Integer> computeDerefParamList(int numParam, int firstParamIndex) { 132 Set<Integer> derefedParamList = new HashSet<>(); 133 Map<ISSABasicBlock, Set<Integer>> blockToDerefSetMap = new HashMap<>(); 134 135 // find which params are treated as being non-null inside each basic block 136 prunedCFG.forEach( 137 basicBlock -> { 138 Set<Integer> derefParamSet = new HashSet<>(); 139 blockToDerefSetMap.put(basicBlock, derefParamSet); 140 checkForUseOfParams(derefParamSet, numParam, firstParamIndex, basicBlock); 141 }); 142 143 // For each param p, if no path exists from the entry block to the exit block which traverses 144 // only basic blocks which do not require p being non-null (e.g. by dereferencing it), then 145 // mark p as @NonNull 146 for (int i = firstParamIndex; i <= numParam; i++) { 147 final Integer param = i - 1; 148 if (!DFS.getReachableNodes( 149 prunedCFG, 150 ImmutableList.of(prunedCFG.entry()), 151 basicBlock -> !blockToDerefSetMap.get(basicBlock).contains(param)) 152 .contains(prunedCFG.exit())) { 153 derefedParamList.add(param); 154 } 155 } 156 return derefedParamList; 157 } 158 computeDerefParamListUsingPDom(int numParam, int firstParamIndex)159 private Set<Integer> computeDerefParamListUsingPDom(int numParam, int firstParamIndex) { 160 Set<Integer> derefedParamList = new HashSet<>(); 161 // Get Dominator Tree 162 LOG(DEBUG, "DEBUG", "\tbuilding dominator tree..."); 163 Graph<ISSABasicBlock> domTree = Dominators.make(prunedCFG, prunedCFG.entry()).dominatorTree(); 164 // Get Post-dominator Tree 165 Graph<ISSABasicBlock> pdomTree = GraphInverter.invert(domTree); 166 LOG(DEBUG, "DEBUG", "post-dominator tree:" + pdomTree.toString()); 167 // Note: WALA creates a single dummy exit node. Multiple exits points will never post-dominate 168 // this exit node. (?) 169 // TODO: [v0.2] Need data-flow analysis for dereferences on all paths 170 // Walk from exit node in post-dominator tree and check for use of params 171 LOG(DEBUG, "DEBUG", "\tfinding dereferenced params..."); 172 ArrayList<ISSABasicBlock> nodeQueue = new ArrayList<ISSABasicBlock>(); 173 nodeQueue.add(prunedCFG.exit()); 174 LOG(DEBUG, "DEBUG", "param value numbers : " + firstParamIndex + " ... " + numParam); 175 while (!nodeQueue.isEmpty()) { 176 ISSABasicBlock node = nodeQueue.get(0); 177 nodeQueue.remove(node); 178 // check for use of params 179 checkForUseOfParams(derefedParamList, numParam, firstParamIndex, node); 180 for (ISSABasicBlock succ : Iterator2Iterable.make(pdomTree.getSuccNodes(node))) { 181 nodeQueue.add(succ); 182 } 183 } 184 LOG(DEBUG, "DEBUG", "\tdone..."); 185 return derefedParamList; 186 } 187 checkForUseOfParams( Set<Integer> derefedParamList, int numParam, int firstParamIndex, ISSABasicBlock node)188 private void checkForUseOfParams( 189 Set<Integer> derefedParamList, int numParam, int firstParamIndex, ISSABasicBlock node) { 190 if (!node.isEntryBlock() && !node.isExitBlock()) { // entry and exit are dummy basic blocks 191 LOG(DEBUG, "DEBUG", ">> bb: " + node.getNumber()); 192 // Iterate over all instructions in BB 193 for (int i = node.getFirstInstructionIndex(); i <= node.getLastInstructionIndex(); i++) { 194 SSAInstruction instr = ir.getInstructions()[i]; 195 if (instr == null) { // Some instructions are null (padding NoOps) 196 continue; 197 } 198 LOG(DEBUG, "DEBUG", "\tinst: " + instr.toString()); 199 int derefValueNumber = -1; 200 if (instr instanceof SSAGetInstruction && !((SSAGetInstruction) instr).isStatic()) { 201 derefValueNumber = ((SSAGetInstruction) instr).getRef(); 202 } else if (instr instanceof SSAPutInstruction && !((SSAPutInstruction) instr).isStatic()) { 203 derefValueNumber = ((SSAPutInstruction) instr).getRef(); 204 } else if (instr instanceof SSAAbstractInvokeInstruction) { 205 SSAAbstractInvokeInstruction callInst = (SSAAbstractInvokeInstruction) instr; 206 String sign = callInst.getDeclaredTarget().getSignature(); 207 if (((SSAAbstractInvokeInstruction) instr).isStatic()) { 208 // All supported Null testing APIs are static methods 209 if (NULL_TEST_APIS.containsKey(sign)) { 210 derefValueNumber = callInst.getUse(NULL_TEST_APIS.get(sign)); 211 } 212 } else { 213 Preconditions.checkArgument( 214 !NULL_TEST_APIS.containsKey(sign), 215 "Add support for non-static NULL_TEST_APIS : " + sign); 216 derefValueNumber = ((SSAAbstractInvokeInstruction) instr).getReceiver(); 217 } 218 } 219 if (derefValueNumber >= firstParamIndex && derefValueNumber <= numParam) { 220 LOG(DEBUG, "DEBUG", "\t\tderefed param : " + derefValueNumber); 221 // Translate from WALA 1-indexed params, to 0-indexed 222 derefedParamList.add(derefValueNumber - 1); 223 } 224 } 225 } 226 } 227 228 public enum NullnessHint { 229 UNKNOWN, 230 NULLABLE, 231 NONNULL 232 } 233 234 /** 235 * This is the nullability analysis for the method return value. 236 * 237 * @return NullnessHint The inferred nullness type for the method return value. 238 */ analyzeReturnType()239 NullnessHint analyzeReturnType() { 240 if (method.getReturnType().isPrimitiveType()) { 241 LOG(DEBUG, "DEBUG", "Skipping method with primitive return type: " + method.getSignature()); 242 return NullnessHint.UNKNOWN; 243 } 244 LOG(DEBUG, "DEBUG", "@ Return type analysis for: " + method.getSignature()); 245 // Get ExceptionPrunedCFG 246 if (prunedCFG == null) { 247 prunedCFG = ExceptionPrunedCFG.make(cfg); 248 } 249 // In case the only control flows are exceptional, simply return. 250 if (prunedCFG.getNumberOfNodes() == 2 251 && prunedCFG.containsNode(cfg.entry()) 252 && prunedCFG.containsNode(cfg.exit()) 253 && GraphUtil.countEdges(prunedCFG) == 0) { 254 return NullnessHint.UNKNOWN; 255 } 256 for (ISSABasicBlock bb : prunedCFG.getNormalPredecessors(prunedCFG.exit())) { 257 for (int i = bb.getFirstInstructionIndex(); i <= bb.getLastInstructionIndex(); i++) { 258 SSAInstruction instr = ir.getInstructions()[i]; 259 if (instr instanceof SSAReturnInstruction) { 260 SSAReturnInstruction retInstr = (SSAReturnInstruction) instr; 261 if (ir.getSymbolTable().isNullConstant(retInstr.getResult())) { 262 LOG(DEBUG, "DEBUG", "Nullable return in method: " + method.getSignature()); 263 return NullnessHint.NULLABLE; 264 } 265 } 266 } 267 } 268 return NullnessHint.UNKNOWN; 269 } 270 } 271