Restricting the search scope to improve performance

One major issue with DeepWeaver is that any call that results in the body predicate executing results in substantial slowdown, particularly upon a large code base. Predicates that result in body being called include call(x,y,z) and assign(x,y,z) when x is a free variable.

In both cases here, x represents a statement, and without that statement being bound, the body predicate must be called to traverse all Units in the codebase to check whether it matches your criteria. This can be particularly slow if the matching criteria itself is expensive.

Remember DeepWeaver doesn't just analyse the class or package you specified, if you call an unbound assign or call predicate it will dive into the libraries and look for results. This includes looking through classes such as Object and Throwable from which common Java features are derived. Needless to say, it's going to slow you down.

At time of writing there's no artificial predicate to limit the scope based on what is specified in your command line, but there's an easy way to do this manually.
If you want to restrict yourself to a certain class or set of classes, simply specify:

scope(u)=class(c,"org.owasp.webgoat.session.User*"), units(body(sootmethod(c,<-),<-),u);

and then

scope(u), assign(u,y,z), ...

and now the first predicate in assign is bound to be a unit from some class beginning with User in the specified package. This dramatically restricts the scope of possible values for u and thus greatly improves the resulting performance.

Notice the use of wildcards here, you may use wildcards in both the class and package name but you must attempt to specify the class name to some degree. So you could say org.owasp.*.User* to find your classes, or ever org.*.* but that dot is essential to include, or it will assume your package to be a class name and fail to find the result you're looking for.

How to use the between predicate

The between predicate is an invaluable tool in your troubleshooting arsenal but it can also be quite tricky to use. The format of the predicate is:

between(a,z,x,b)

a and z should be code units that represent the start and end of the between block.
x is the code between a and z. If x is output, it will come in the form of one line of soot analysis at at time, in the form of units. If x is input, it should be a unit (or unit box) of one or more lines of code.
b is a boolean choice that selects between must (true) and may (false) analysis, eg. code in an if block between a and z may not be called between a and z and thus will be included in a may, but not a must analysis.

To use between to find the x variable, the most important thing is to ensure that you specify a and z as two non-equal code units. However, units are not necessarily the most instinctive way to specify a and z. For example, you may want to specify a or z in terms of a call. The wrong way to do this is:

between(call(<-,*,*), z, X, false)

This has a number of faults including:

• There's nothing to stop the result of your call being the same as z (an arbitrary unit) which could give a null exception
• Your input is likely to give multiple locations, which will give multiple results from between that may not be easily distinguishable from each other

Between is very powerful but you need to be firm about your input to it. Here is an example of how to use between to find all the code that may be between two method calls, one called begin, the other called commit.

getUnit(call(<-,p,*), y), getUnit(call(<-,q,*), z), methodMatches(p, "* begin(..)), methodMatches(q, "* commit(..)"), between(y, z, X, false )

This works because call's middle parameter returns a method. This method name can then be checked with methodMatches to ensure that it has an expected name. Since the two match parameters are different, this also ensures the two results won't be equal. Then we get the unit from the result so that we are sure between will be receiving a unit as both parameters. X is the result which may be multiple lines of code we can then test.

Predicate Specification

A couple of notes on how to specify your predicates in DeepWeaver, that are worth mentioning because they're different from how they're specified in Prolog.

When you're specifiying a predicate there are a number of reserved keywords, and an few restrictions.

name(fn,sn)=getName(fn,sn);

This is the basic standard specification, fn and sn are bound or unbound variables of any type.

name(in fn, out sn)=getName(fn,sn);

This restricts the standard specification, because fn must be bound and sn must be unbound when this predicate is called, otherwise it will be ignored. You could overload is by following it with the first example above.

name(String fn, out sn)=getName(fn,sn);

Now fn must be a String object, but may be bound or unbound, sn must still be unbound.

Points of note:

• Unless your variable name is one char long, it should start with a small letter or it will be mistaken for a type binding
• in and out should not be used as variable names
• Predicates can be overloaded, but they are overloaded in order (same as Prolog), meaning that if you have a predicate which has no binding or type restrictions, it should be the final specified predicate
• No error will be thrown if your bindings cause a predicate call that you did not expect
  

Modifications of standard Prolog

Deepweaver changes a number of standard Prolog syntactical features to bring it closer to Java, and make pattern cuts more familiar to Java developers

Declaring a predicate is no longer done using the Prolog iff term :-, instead the = symbol is used.
Terminating a predicate is no longer performed using the fullstop symbol . instead the semicolon is used ; Since the semicolon in Prolog represents or, this has now been replaced with the pipe character, |
Comments are now of standard Java form, so instead of % we have // for single line comments and /* .. */ for multiline comments
Negation is slightly different from standard Prolog in that \+ is no longer used to reperesent negation, instead use the not(A) predicate.

Finally, its worth noting that in a .dw file, only predicates preceeded by a question mark will be executed. One should declare all the required predicates and then select the one to be executed by writing ?runMe(A,B); at the end of the file.

eg. well_located(A,B) = statement(A,X), not(between(s, X, B, true));

Predicate Library Summary

A summary of the built-in DeepWeaver predicates and their expected functions.

• allBoxIter(A)
  
• args(A,B) A call to method A has a list of argument objects B
  
• assign(A,B,L) Variable A is assigned value B at location L
  
• between(a,z,X,B) X is a codeblock between ground/atomic codeblocks a and z if boolean B is true. If B is false, then X may or may not be between a and z.
  
• body(a,B) Finds a method body location B in an atom or ground variable a, the code block location may be in only non-abstract, real method bodys which should be included in a.
• call(A,B,C) Instruction A calls method B which takes some sort of object C.
  
• class(A) A is a class. Returns any class if A is unbound
  
• defBoxes(a,B) Finds a definition box B within unit a
  
• doms(A,B,C)
• element(A,N,B)
  
• end(a,B) B is the soot-generated final piece of code of method a. See start.
• forall(A,B) Standard Prolog forall, for all cases of A, B is true.
• jump(A) Returns a statment which causes a jump in the code
• target(A,L) Returns the Location of a jump in the code at statement A
• method(A,B)
  
• methodMatches(A,B)
  
• member(A,B) Standard Prolog member, returns true if A is an element of list B
• name(A,B)
  
• not(X) Standard Prolog negation, if X cannot be proved, this statement returns true.
  
• parentMethod(a,B) Gets the entire parent method of atom or ground variable a as a codeblock bound to B.
• path(A,B,C)
  
• precedes(A,B) Code block A occurs at or before Code block B in a method (or logical Soot code flow)
• pred(A,B)
  
• print(A) Prints the type and toString() result of A
  
• sameValue(A,B)
  
• sootmethod(A,B)
  
• start(a,B) B is the soot-generated first code piece of method a. Note that this is soot generated, so the start block includes all code that comes between the first method call, loop block, or other non-trivial piece of code.
• statement(A,B) A is the location of the statement that results in B.
• succ(A,B) Same as pred(B,A)
  
• type(A,a) Restricts A to be of the same type as a.
• units(A,B)
• unused(A)
  
• useboxes(A,B)
  
• uses(A,L) Code block A is used at location L.
• value(A,B) B is the value of variable A, returned as a CodeValue. Common usage: value(A,X), value(B,X).
  

Insertion of return values

Prolog variables don't have return values, but often there's a case where a function only works one way, meaning that an unbound variable essentially acts as a return value. While this detracts from the declarative power of Prolog, it certainly reduces the number of temporary variables hanging around programs.

So, to shorten the pattern cut implementations and reduce the number of temporary variables we use the notation <-
eg. We can rewrite bar(X), foo(X,c) as foo(bar(<-),c)

In useful terms, one nice rewrite we could have is

statement(Ta,CallA), statement(Tb, CallB), precedes(Ta,Tb)
rewrites to a much shorter and intuitve
precedes(statement(<-,CallA), statement(<-,CallB))

More extreme examples that certainly cut down on the number of inserted variables but potentially at the cost of legibility could be
dominates(a,b) = parentMethod(a,Ta), body(Ta,Tb), start(Tb, Tc), between(Tc,b,a,true)
which shortens to
dominates(a,b) = between(start(body(parentMethod(a,<-),<-),<-),b,a,true)

Its the type of predicate that's handy to have in your arsenal but its good to be aware of its impact on readability