|
1
19
20 package soot.jimple.toolkits.callgraph;
21 import soot.*;
22 import soot.options.*;
23 import soot.jimple.*;
24 import java.util.*;
25 import soot.util.*;
26 import soot.util.queue.*;
27
28
31 public final class OnFlyCallGraphBuilder
32 {
33
34 private CallGraph cicg = new CallGraph();
35 private HashSet analyzedMethods = new HashSet();
36
37 private LargeNumberedMap receiverToSites = new LargeNumberedMap( Scene.v().getLocalNumberer() ); private LargeNumberedMap methodToReceivers = new LargeNumberedMap( Scene.v().getMethodNumberer() ); public LargeNumberedMap methodToReceivers() { return methodToReceivers; }
40
41 private SmallNumberedMap stringConstToSites = new SmallNumberedMap( Scene.v().getLocalNumberer() ); private LargeNumberedMap methodToStringConstants = new LargeNumberedMap( Scene.v().getMethodNumberer() ); public LargeNumberedMap methodToStringConstants() { return methodToStringConstants; }
44
45 private CGOptions options;
46
47 private boolean appOnly;
48
49
50 private ReachableMethods rm;
51 private QueueReader worklist;
52
53 private ContextManager cm;
54
55 private ChunkedQueue targetsQueue = new ChunkedQueue();
56 private QueueReader targets = targetsQueue.reader();
57
58
59 public OnFlyCallGraphBuilder( ContextManager cm, ReachableMethods rm ) {
60 this.cm = cm;
61 this.rm = rm;
62 worklist = rm.listener();
63 options = new CGOptions( PhaseOptions.v().getPhaseOptions("cg") );
64 if( !options.verbose() ) {
65 G.v().out.println( "[Call Graph] For information on where the call graph may be incomplete, use the verbose option to the cg phase." );
66 }
67 }
68 public OnFlyCallGraphBuilder( ContextManager cm, ReachableMethods rm, boolean appOnly ) {
69 this( cm, rm );
70 this.appOnly = appOnly;
71 }
72 public void processReachables() {
73 while(true) {
74 if( !worklist.hasNext() ) {
75 rm.update();
76 if( !worklist.hasNext() ) break;
77 }
78 MethodOrMethodContext momc = (MethodOrMethodContext) worklist.next();
79 SootMethod m = momc.method();
80 if( appOnly && !m.getDeclaringClass().isApplicationClass() ) continue;
81 if( analyzedMethods.add( m ) ) processNewMethod( m );
82 processNewMethodContext( momc );
83 }
84 }
85 public boolean wantTypes( Local receiver ) {
86 return receiverToSites.get(receiver) != null;
87 }
88 public void addType( Local receiver, Context srcContext, Type type, Context typeContext ) {
89 FastHierarchy fh = Scene.v().getOrMakeFastHierarchy();
90 for( Iterator siteIt = ((Collection) receiverToSites.get( receiver )).iterator(); siteIt.hasNext(); ) {
91 final VirtualCallSite site = (VirtualCallSite) siteIt.next();
92 InstanceInvokeExpr iie = site.iie();
93 if( site.kind() == Kind.THREAD
94 && !fh.canStoreType( type, clRunnable ) )
95 continue;
96
97 if( site.iie() instanceof SpecialInvokeExpr ) {
98 targetsQueue.add( VirtualCalls.v().resolveSpecial(
99 (SpecialInvokeExpr) site.iie(),
100 site.subSig(),
101 site.container() ) );
102 } else {
103 VirtualCalls.v().resolve( type,
104 receiver.getType(),
105 site.subSig(),
106 site.container(),
107 targetsQueue );
108 }
109 while(targets.hasNext()) {
110 SootMethod target = (SootMethod) targets.next();
111 cm.addVirtualEdge(
112 MethodContext.v( site.container(), srcContext ),
113 site.stmt(),
114 target,
115 site.kind(),
116 typeContext );
117 }
118 }
119 }
120 public boolean wantStringConstants( Local stringConst ) {
121 return stringConstToSites.get(stringConst) != null;
122 }
123 public void addStringConstant( Local l, Context srcContext, String  constant ) {
124 for( Iterator siteIt = ((Collection) stringConstToSites.get( l )).iterator(); siteIt.hasNext(); ) {
125 final VirtualCallSite site = (VirtualCallSite) siteIt.next();
126 if( constant == null ) {
127 if( options.verbose() ) {
128 G.v().out.println( "Warning: Method "+site.container()+
129 " is reachable, and calls Class.forName on a"+
130 " non-constant String; graph will be incomplete!"+
131 " Use safe-forname option for a conservative result." );
132 }
133 } else {
134 if( constant.charAt(0) == '[' ) {
135 if( constant.length() > 1 && constant.charAt(1) == 'L'
136 && constant.charAt(constant.length()-1) == ';' ) {
137 constant = constant.substring(2,constant.length()-1);
138 } else continue;
139 }
140 if( !Scene.v().containsClass( constant ) ) {
141 if( options.verbose() ) {
142 G.v().out.println( "Warning: Class "+constant+" is"+
143 " a dynamic class, and you did not specify"+
144 " it as such; graph will be incomplete!" );
145 }
146 } else {
147 SootClass sootcls = Scene.v().getSootClass( constant );
148 if( !sootcls.isApplicationClass() ) {
149 sootcls.setLibraryClass();
150 }
151 for( Iterator clinitIt = EntryPoints.v().clinitsOf(sootcls).iterator(); clinitIt.hasNext(); ) {
152 final SootMethod clinit = (SootMethod) clinitIt.next();
153 cm.addStaticEdge(
154 MethodContext.v( site.container(), srcContext ),
155 site.stmt(),
156 clinit,
157 Kind.CLINIT );
158 }
159 }
160 }
161 }
162 }
163
164
165
166 private void addVirtualCallSite( Stmt s, SootMethod m, Local receiver,
167 InstanceInvokeExpr iie, NumberedString subSig, Kind kind ) {
168 List sites = (List) receiverToSites.get(receiver);
169 if (sites == null) {
170 receiverToSites.put(receiver, sites = new ArrayList());
171 List receivers = (List) methodToReceivers.get(m);
172 if( receivers == null )
173 methodToReceivers.put(m, receivers = new ArrayList());
174 receivers.add(receiver);
175 }
176 sites.add(new VirtualCallSite(s, m, iie, subSig, kind));
177 }
178 private void processNewMethod( SootMethod m ) {
179 if( m.isNative() || m.isPhantom() ) {
180 return;
181 }
182 Body b = m.retrieveActiveBody();
183 getImplicitTargets( m );
184 findReceivers(m, b);
185 }
186 private void findReceivers(SootMethod m, Body b) {
187 for( Iterator sIt = b.getUnits().iterator(); sIt.hasNext(); ) {
188 final Stmt s = (Stmt) sIt.next();
189 if (s.containsInvokeExpr()) {
190 InvokeExpr ie = (InvokeExpr) s.getInvokeExpr();
191
192 if (ie instanceof InstanceInvokeExpr) {
193 InstanceInvokeExpr iie = (InstanceInvokeExpr) ie;
194 Local receiver = (Local) iie.getBase();
195 NumberedString subSig =
196 iie.getMethodRef().getSubSignature();
197 addVirtualCallSite( s, m, receiver, iie, subSig,
198 Edge.ieToKind(iie) );
199 if( subSig == sigStart ) {
200 addVirtualCallSite( s, m, receiver, iie, sigRun,
201 Kind.THREAD );
202 }
203 } else {
204 SootMethod tgt = ((StaticInvokeExpr) ie).getMethod();
205 addEdge(m, s, tgt);
206 if( tgt.getSignature().equals( "<java.security.AccessController: java.lang.Object doPrivileged(java.security.PrivilegedAction)>" )
207 || tgt.getSignature().equals( "<java.security.AccessController: java.lang.Object doPrivileged(java.security.PrivilegedExceptionAction)>" )
208 || tgt.getSignature().equals( "<java.security.AccessController: java.lang.Object doPrivileged(java.security.PrivilegedAction,java.security.AccessControlContext)>" )
209 || tgt.getSignature().equals( "<java.security.AccessController: java.lang.Object doPrivileged(java.security.PrivilegedExceptionAction,java.security.AccessControlContext)>" ) ) {
210
211 Local receiver = (Local) ie.getArg(0);
212 addVirtualCallSite( s, m, receiver, null, sigObjRun,
213 Kind.PRIVILEGED );
214 }
215 }
216 }
217 }
218 }
219
220 private void getImplicitTargets( SootMethod source ) {
221 List stringConstants = (List) methodToStringConstants.get(source);
222 if( stringConstants == null )
223 methodToStringConstants.put(source, stringConstants = new ArrayList());
224 final SootClass scl = source.getDeclaringClass();
225 if( source.isNative() || source.isPhantom() ) return;
226 if( source.getSubSignature().indexOf( "<init>" ) >= 0 ) {
227 handleInit(source, scl);
228 }
229 Body b = source.retrieveActiveBody();
230 boolean warnedAlready = false;
231 for( Iterator sIt = b.getUnits().iterator(); sIt.hasNext(); ) {
232 final Stmt s = (Stmt) sIt.next();
233 if( s.containsInvokeExpr() ) {
234 InvokeExpr ie = (InvokeExpr) s.getInvokeExpr();
235 if( ie.getMethod().getSignature().equals( "<java.lang.reflect.Method: java.lang.Object invoke(java.lang.Object,java.lang.Object[])>" ) ) {
236 if( !warnedAlready ) {
237 if( options.verbose() ) {
238 G.v().out.println( "Warning: call to "+
239 "java.lang.reflect.Method: invoke() from "+source+
240 "; graph will be incomplete!" );
241 }
242 warnedAlready = true;
243 }
244 }
245 if( ie.getMethod().getSignature().equals( "<java.lang.Class: java.lang.Object newInstance()>" ) ) {
246 if( options.safe_newinstance() ) {
247 for( Iterator tgtIt = EntryPoints.v().inits().iterator(); tgtIt.hasNext(); ) {
248 final SootMethod tgt = (SootMethod) tgtIt.next();
249 addEdge( source, s, tgt, Kind.NEWINSTANCE );
250 }
251 } else {
252 if( options.verbose() ) {
253 G.v().out.println( "Warning: Method "+source+
254 " is reachable, and calls Class.newInstance;"+
255 " graph will be incomplete!"+
256 " Use safe-newinstance option for a conservative result." );
257 }
258 }
259 }
260 if( ie instanceof StaticInvokeExpr ) {
261 SootClass cl = ie.getMethodRef().declaringClass();
262 for( Iterator clinitIt = EntryPoints.v().clinitsOf(cl).iterator(); clinitIt.hasNext(); ) {
263 final SootMethod clinit = (SootMethod) clinitIt.next();
264 addEdge( source, s, clinit, Kind.CLINIT );
265 }
266 }
267 if( ie.getMethodRef().getSubSignature() == sigForName ) {
268 Value className = ie.getArg(0);
269 if( className instanceof StringConstant ) {
270 String cls = ((StringConstant) className ).value;
271 constantForName( cls, source, s );
272 } else {
273 Local constant = (Local) className;
274 if( options.safe_forname() ) {
275 for( Iterator tgtIt = EntryPoints.v().clinits().iterator(); tgtIt.hasNext(); ) {
276 final SootMethod tgt = (SootMethod) tgtIt.next();
277 addEdge( source, s, tgt, Kind.CLINIT );
278 }
279 } else {
280 VirtualCallSite site = new VirtualCallSite( s, source, null, null, Kind.CLINIT );
281 List sites = (List) stringConstToSites.get(constant);
282 if (sites == null) {
283 stringConstToSites.put(constant, sites = new ArrayList());
284 stringConstants.add(constant);
285 }
286 sites.add(site);
287 }
288 }
289 }
290 }
291 if( s.containsFieldRef() ) {
292 FieldRef fr = (FieldRef) s.getFieldRef();
293 if( fr instanceof StaticFieldRef ) {
294 SootClass cl = fr.getFieldRef().declaringClass();
295 for( Iterator clinitIt = EntryPoints.v().clinitsOf(cl).iterator(); clinitIt.hasNext(); ) {
296 final SootMethod clinit = (SootMethod) clinitIt.next();
297 addEdge( source, s, clinit, Kind.CLINIT );
298 }
299 }
300 }
301 if( s instanceof AssignStmt ) {
302 Value rhs = ((AssignStmt)s).getRightOp();
303 if( rhs instanceof NewExpr ) {
304 NewExpr r = (NewExpr) rhs;
305 SootClass cl = r.getBaseType().getSootClass();
306 for( Iterator clinitIt = EntryPoints.v().clinitsOf(cl).iterator(); clinitIt.hasNext(); ) {
307 final SootMethod clinit = (SootMethod) clinitIt.next();
308 addEdge( source, s, clinit, Kind.CLINIT );
309 }
310 } else if( rhs instanceof NewArrayExpr || rhs instanceof NewMultiArrayExpr ) {
311 Type t = rhs.getType();
312 if( t instanceof ArrayType ) t = ((ArrayType)t).baseType;
313 if( t instanceof RefType ) {
314 SootClass cl = ((RefType) t).getSootClass();
315 for( Iterator clinitIt = EntryPoints.v().clinitsOf(cl).iterator(); clinitIt.hasNext(); ) {
316 final SootMethod clinit = (SootMethod) clinitIt.next();
317 addEdge( source, s, clinit, Kind.CLINIT );
318 }
319 }
320 }
321 }
322 }
323 }
324
325 private void processNewMethodContext( MethodOrMethodContext momc ) {
326 SootMethod m = momc.method();
327 Object ctxt = momc.context();
328 Iterator it = cicg.edgesOutOf(m);
329 while( it.hasNext() ) {
330 Edge e = (Edge) it.next();
331 cm.addStaticEdge( momc, e.srcUnit(), e.tgt(), e.kind() );
332 }
333 }
334
335 private void handleInit(SootMethod source, final SootClass scl) {
336 addEdge( source, null, scl, sigFinalize, Kind.FINALIZE );
337 FastHierarchy fh = Scene.v().getOrMakeFastHierarchy();
338 }
339 private void constantForName( String cls, SootMethod src, Stmt srcUnit ) {
340 if( cls.charAt(0) == '[' ) {
341 if( cls.charAt(1) == 'L' && cls.charAt(cls.length()-1) == ';' ) {
342 cls = cls.substring(2,cls.length()-1);
343 constantForName( cls, src, srcUnit );
344 }
345 } else {
346 if( !Scene.v().containsClass( cls ) ) {
347 if( options.verbose() ) {
348 G.v().out.println( "Warning: Class "+cls+" is"+
349 " a dynamic class, and you did not specify"+
350 " it as such; graph will be incomplete!" );
351 }
352 } else {
353 SootClass sootcls = Scene.v().getSootClass( cls );
354 if( !sootcls.isApplicationClass() ) {
355 sootcls.setLibraryClass();
356 }
357 for( Iterator clinitIt = EntryPoints.v().clinitsOf(sootcls).iterator(); clinitIt.hasNext(); ) {
358 final SootMethod clinit = (SootMethod) clinitIt.next();
359 addEdge( src, srcUnit, clinit, Kind.CLINIT );
360 }
361
362 }
363 }
364 }
365
366 private void addEdge( SootMethod src, Stmt stmt, SootMethod tgt,
367 Kind kind ) {
368 cicg.addEdge( new Edge( src, stmt, tgt, kind ) );
369 }
370
371 private void addEdge( SootMethod src, Stmt stmt, SootClass cls, NumberedString methodSubSig, Kind kind ) {
372 if( cls.declaresMethod( methodSubSig ) ) {
373 addEdge( src, stmt, cls.getMethod( methodSubSig ), kind );
374 }
375 }
376 private void addEdge( SootMethod src, Stmt stmt, String methodSig, Kind kind ) {
377 if( Scene.v().containsMethod( methodSig ) ) {
378 addEdge( src, stmt, Scene.v().getMethod( methodSig ), kind );
379 }
380 }
381 private void addEdge( SootMethod src, Stmt stmt, SootMethod tgt ) {
382 InvokeExpr ie = stmt.getInvokeExpr();
383 addEdge( src, stmt, tgt, Edge.ieToKind(ie) );
384 }
385
386 private final NumberedString sigMain = Scene.v().getSubSigNumberer().
387 findOrAdd( "void main(java.lang.String[])" );
388 private final NumberedString sigFinalize = Scene.v().getSubSigNumberer().
389 findOrAdd( "void finalize()" );
390 private final NumberedString sigExit = Scene.v().getSubSigNumberer().
391 findOrAdd( "void exit()" );
392 private final NumberedString sigStart = Scene.v().getSubSigNumberer().
393 findOrAdd( "void start()" );
394 private final NumberedString sigRun = Scene.v().getSubSigNumberer().
395 findOrAdd( "void run()" );
396 private final NumberedString sigObjRun = Scene.v().getSubSigNumberer().
397 findOrAdd( "java.lang.Object run()" );
398 private final NumberedString sigForName = Scene.v().getSubSigNumberer().
399 findOrAdd( "java.lang.Class forName(java.lang.String)" );
400 private final RefType clRunnable = RefType.v("java.lang.Runnable");
401
402 }
403
404 |
Popular Tags |
Java API By Example, From Geeks To Geeks.