Tabby 源码分析

FlowSet<T> clone(); //克隆当前FlowSet的集合
FlowSet<T> emptySet();//返回一个空集，通常比((FlowSet)clone()).clear()效率更高
void copy(FlowSet<T> dest);//拷贝当前集合到dest集合中
void clear();//返回该flowset的清空
void union(FlowSet<T> other); //并集，this = this ∪nion
void union(FlowSet<T> other, FlowSet<T> dest); // this ∪ other = dest，其中other、dest可以与该FlowSet一样
void intersection(FlowSet<T> other); //交集，this ∩ other = this
void intersection(FlowSet<T> other, FlowSet<T> dest); //FlowSet ∩ other = dest 其中，dest、other可以和该FlowSet一样
void difference(FlowSet<T> other); // 排除，this = this - other
void difference(FlowSet<T> other, FlowSet<T> dest); // this - other = dest,其中，dest、other和FlowSet可能相同。
boolean isEmpty();
int size();
void add(T var1); // 添加元素
void add(T obj, FlowSet<T> dest); // 添加元素至dest
void remove(T var1);	// 删除元素
void remove(T obj, FlowSet<T> dest); // dest删除
boolean contains(T var1);	// 
boolean isSubSet(FlowSet<T> var1); //
Iterator<T> iterator();
List<T> toList();

public MyAnalysis(DirectedGraph graph) { //构造函数
	super(graph);//传递给父类
  
	// TODO Auto-generated constructor stub
	emptySet = new ArraySparseSet();//自定义分析
  
	doAnalysis();//执行fixed-point
}

protected Object newInitialFlow() {
	// TODO Auto-generated method stub
	return emptySet.emptySet();
}
 

protected Object entryInitialFlow() {
	// TODO Auto-generated method stub
	return emptySet.emptySet();
}

protected void copy(Object source, Object dest) {
	// TODO Auto-generated method stub
	FlowSet srcSet = (FlowSet)source,
	FlowSet destSet = (FlowSet)dest;
	srcSet.copy(destSet);
}

protected void merge(Object in1, Object in2, Object out) {
	// TODO Auto-generated method stub
	FlowSet inSet1 = (FlowSet)in1,
	inSet2 = (FlowSet)in2,
	outSet = (FlowSet)out;
	//inSet1.union(inSet2, outSet);
	inSet1.intersection(inSet2, outSet);
}

protected void flowThrough(Object in, Object d, Object out) {
	// TODO Auto-generated method stub
	FlowSet inSet = (FlowSet)in,
	FlowSet outSet = (FlowSet)out;
	Unit u = (Unit) d;
	kill(inSet,u,outSet);
	gen(outSet,u);
}

void complement();	// 补充
void complement(FlowSet<T> dest);	//	补充
FlowSet<T> topSet();	// 全集

public class LiveVariableFlowSet extends AbstractBoundedFlowSet<Local> {

    private Set<Local> liveVariableSet = new HashSet<>();

// copy
protected void copy(LiveVariableFlowSet srcSet, LiveVariableFlowSet destSet) {
    //backward copy
    srcSet.copy(destSet);
}

// merge
protected void merge(LiveVariableFlowSet srcSet1, LiveVariableFlowSet srcSet2, LiveVariableFlowSet destSet) {
    // srcSet1 U srcSet2 = srcSet2
    srcSet1.union(srcSet2,destSet);
}

protected void flowThrough(LiveVariableFlowSet srcSet, Unit u, LiveVariableFlowSet destSet) {
    //transfer function
    // 1.1 kill leftOp
    kill(srcSet,u,destSet);
    // 1.2 gen rightOps
    gen(u,destSet);
}

private void kill(LiveVariableFlowSet inSet, Unit u, LiveVariableFlowSet destSet) {
    LiveVariableFlowSet kills = new LiveVariableFlowSet();
    Iterator<ValueBox> defIt = u.getDefBoxes().iterator();
    while(defIt.hasNext()){
        ValueBox defBox = defIt.next();
        defBox.getValue().apply(new AbstractJimpleValueSwitch() {
            @Override
            public void caseLocal(Local v) {
                Iterator inIt = inSet.iterator();
                while(inIt.hasNext()){
                    Local inValue = (Local)inIt.next();
                    if(inValue.equivTo(defBox.getValue())){
                        kills.add((Local) defBox.getValue());
                    }
                }
            }
        });
    }
    // inSet - kills = destSet
    inSet.difference(kills,destSet);
}

private void gen(Unit u, LiveVariableFlowSet destSet) {
    Iterator<ValueBox> it = u.getUseBoxes().iterator();
    while(it.hasNext()){
        ValueBox useBox = it.next();
        useBox.getValue().apply(new AbstractJimpleValueSwitch() {
            @Override
            public void caseLocal(Local v) {
                destSet.add((Local) useBox.getValue());
            }
        });
    }
}

actions {
	"param-0": ["param-1"],
	"param-1": ["param-0"],
	"return": ["param-0"]
}

class AbstractTableModel{
    private HashMap<String, IFn> __clojureFnMap;
    hashCode() {
        IFn f = __clojureFnMap.get("hashCode");
        f.invokeCall(this);
    }
}

private Context context; // 同一函数内共享的上下文内容
private DataContainer dataContainer;
private Map<Local, TabbyVariable> emptyMap;
private Map<Local, TabbyVariable> initialMap;
private StmtSwitcher stmtSwitcher;
private MethodReference methodRef; // method 引用，由tabby 定义的method
private Body body;	// soot JimpleBody，method.retrieveActiveBody() 而来

protected Map<Local, TabbyVariable> newInitialFlow() {
    return new HashMap<>(emptyMap);
}

protected void copy(Map<Local, TabbyVariable> source, Map<Local, TabbyVariable> dest) {
    dest.clear();
    for (Map.Entry<Local, TabbyVariable> entry : source.entrySet()) {
        Local value = entry.getKey();
        TabbyVariable variable = entry.getValue();
        dest.put(value, variable.deepClone(new ArrayList<>()));
    }
}

protected void merge(Map<Local, TabbyVariable> in1, Map<Local, TabbyVariable> in2, Map<Local, TabbyVariable> out) {
    // if else while 分支汇聚的时候 对结果集进行处理 取并集
    copy(in1, out);

    in2.forEach((local, in2Var) -> {// 取并集
        TabbyVariable outVar = out.get(local);
        if(outVar != null){
            outVar.union(in2Var);
        }else{
            out.put(local, in2Var);
        }
    });
}

protected void flowThrough(Map<Local, TabbyVariable> in, Unit d, Map<Local, TabbyVariable> out) {
    Map<Local, TabbyVariable> newIn = new HashMap<>();
    copy(in, newIn);
    context.setLocalMap(newIn);
    context.setInitialMap(initialMap);
    stmtSwitcher.setContext(context);
    stmtSwitcher.setDataContainer(dataContainer);
    d.apply(stmtSwitcher);
    out.putAll(clean(context.getLocalMap()));
}

public void doAnalysis(){
   	// getUseAndDefBoxes 获取jimple语言表示下的所有局部变量定义和调用情况
       for(ValueBox box:body.getUseAndDefBoxes()){
           Value value = box.getValue();
           Type type = value.getType();
           if(type instanceof PrimType){ // 对于基础数据类型 直接跳过
               continue;
           }
           if(value instanceof Local && !initialMap.containsKey(value)){
               initialMap.put((Local) value, TabbyVariable.makeLocalInstance((Local) value));
           }else if(value instanceof InstanceFieldRef){
               InstanceFieldRef ifr = (InstanceFieldRef) value;
               SootField sootField = ifr.getField();
               SootFieldRef sfr = ifr.getFieldRef();

               String signature = null;
               if(sootField != null){
                   signature = sootField.getSignature();
               }else if(sfr != null){
                   signature = sfr.getSignature();
               }

               Value base = ifr.getBase();
               if(base instanceof Local){
                   TabbyVariable baseVar = initialMap.get(base);
                   if(baseVar == null){
                       baseVar = TabbyVariable.makeLocalInstance((Local) base);
                       initialMap.put((Local) base, baseVar);
                   }
                   TabbyVariable fieldVar = baseVar.getField(signature);
                   if(fieldVar == null){
                       if(sootField != null){
                           fieldVar = TabbyVariable.makeFieldInstance(baseVar, sootField);
                       }else if(sfr != null){
                           fieldVar = TabbyVariable.makeFieldInstance(baseVar, sfr);
                       }
                       if(fieldVar != null && signature != null){
                           fieldVar.setOrigin(value);
                           baseVar.addField(signature, fieldVar);
                       }
                   }
               }
           }else if(value instanceof ArrayRef){
               ArrayRef v = (ArrayRef) value;
               Value base = v.getBase();
               if(base instanceof Local){
                   TabbyVariable baseVar = initialMap.get(base);
                   if(baseVar == null){
                       baseVar = TabbyVariable.makeLocalInstance((Local) base);
                       initialMap.put((Local) base, baseVar);
                   }
               }
           }
       }
       super.doAnalysis();
   }

public abstract class AbstractStmtSwitch implements StmtSwitch {
  Object result;

  public void caseBreakpointStmt(BreakpointStmt stmt)
  public void caseInvokeStmt(InvokeStmt stmt)
  public void caseAssignStmt(AssignStmt stmt)
  public void caseIdentityStmt(IdentityStmt stmt)
  public void caseEnterMonitorStmt(EnterMonitorStmt stmt) 
  public void caseExitMonitorStmt(ExitMonitorStmt stmt)
  public void caseGotoStmt(GotoStmt stmt)
  public void caseIfStmt(IfStmt stmt)

public interface Unit extends Switchable, Host, Serializable, Context {
...

public interface Switchable {
  /** Called when this object is visited. */
  void apply(Switch sw);
}

$stack5 = newarray (java.lang.Object)[0]

public void caseAssignStmt(AssignStmt stmt) {
    Value lop = stmt.getLeftOp();
    Value rop = stmt.getRightOp();
    TabbyVariable rvar = null;
    boolean unbind = false;
    rightValueSwitcher.setUnit(stmt);
    rightValueSwitcher.setContext(context);
    rightValueSwitcher.setDataContainer(dataContainer);
    rightValueSwitcher.setResult(null);
    rop.apply(rightValueSwitcher);
    Object result = rightValueSwitcher.getResult();
    if(result instanceof TabbyVariable){
        rvar = (TabbyVariable) result;
    }
    if(rop instanceof Constant && !(rop instanceof StringConstant)){
        unbind = true;
    }
    if(rvar != null && rvar.getValue() != null && rvar.getValue().getType() instanceof PrimType){
        rvar = null; // 剔除基础元素的污点传递，对于我们来说，这部分是无用的分析
    }
    // 处理左值
    if(rvar != null || unbind){
        leftValueSwitcher.setContext(context);
        leftValueSwitcher.setMethodRef(methodRef);
        leftValueSwitcher.setRvar(rvar);
        leftValueSwitcher.setUnbind(unbind);
        lop.apply(leftValueSwitcher);
    }
}

public void caseLocal(Local v) {
    if(v.getType() instanceof PrimType) return; // 提出无用的类属性传递

    TabbyVariable var = context.getOrAdd(v);

    generateAction(var, rvar, -1, unbind);
    if(unbind){
        var.clearVariableStatus();
    }else{
        var.assign(rvar, false);
    }
}

public void addAction(String key, String value){
    actions.put(key, value);
}

public void caseIdentityStmt(IdentityStmt stmt) {
    Value lop = stmt.getLeftOp();
    Value rop = stmt.getRightOp();
    if(rop instanceof ThisRef){
        context.bindThis(lop);
    }else if(rop instanceof ParameterRef){
        ParameterRef pr = (ParameterRef)rop;
        context.bindArg((Local)lop, pr.getIndex());
    }
}

public void caseReturnStmt(ReturnStmt stmt) {
    Value value = stmt.getOp();
    TabbyVariable var = null;
    // 近似处理 只要有一种return的情况是可控的，就认为函数返回是可控的
    // 并结算当前的入参区别
    if(context.getReturnVar() != null && context.getReturnVar().containsPollutedVar(new ArrayList<>())) return;
    rightValueSwitcher.setUnit(stmt);
    rightValueSwitcher.setContext(context);
    rightValueSwitcher.setDataContainer(dataContainer);
    rightValueSwitcher.setResult(null);
    value.apply(rightValueSwitcher);
    var = (TabbyVariable) rightValueSwitcher.getResult();
    context.setReturnVar(var);
    if(var != null && var.isPolluted(-1) && reset){
        methodRef.addAction("return", var.getValue().getRelatedType());
    }
}

public void caseInvokeStmt(InvokeStmt stmt) {
    // extract baseVar and args
    InvokeExpr ie = stmt.getInvokeExpr();
    if("<java.lang.Object: void <init>()>".equals(ie.getMethodRef().getSignature())) return;
    if(GlobalConfiguration.DEBUG){
        log.debug("Analysis: "+ie.getMethodRef().getSignature() + "; "+context.getTopMethodSignature());
    }
    Switcher.doInvokeExprAnalysis(stmt, ie, dataContainer, context);
    if(GlobalConfiguration.DEBUG) {
        log.debug("Analysis: " + ie.getMethodRef().getName() + " done, return to" + context.getMethodSignature() + "; "+context.getTopMethodSignature());
    }
}

import org.neo4j.procedure.Procedure;
import java.util.stream.Stream;

public class GetRelationshipTypes {
	@Procedure(value = "example.getRelationshipTypes")
    @Description("Get the different relationships going in and out of a node.")
    public Stream<RelationshipTypes> getRelationshipTypes(@Name("node") Node node) {
        List<String> outgoing = new ArrayList<>();
        node.getRelationships(Direction.OUTGOING).iterator()
            .forEachRemaining(rel -> AddDistinct(outgoing, rel));

        List<String> incoming = new ArrayList<>();
        node.getRelationships(Direction.INCOMING).iterator()
                .forEachRemaining(rel -> AddDistinct(incoming, rel));

        return Stream.of(new RelationshipTypes(incoming, outgoing));
    }

import org.neo4j.procedure.UserFunction;

public class Join {
    @UserFunction
    @Description("example.join(['s1','s2',...], delimiter) - join the given strings with the given delimiter.")
    public String join(
            @Name("strings") List<String> strings,
            @Name(value = "delimiter", defaultValue = ",") String delimiter) {
        if (strings == null || delimiter == null) {
            return null;
        }
        return String.join(delimiter, strings);
    }
}

import org.neo4j.procedure.UserAggregationFunction;
import org.neo4j.procedure.UserAggregationUpdate;
import org.neo4j.procedure.UserAggregationResult;

public class Last {
    @UserAggregationFunction("example.last")
    @Description("example.last(value) - returns last non-null row")
    public LastFunction last() {
        return new LastFunction();
    }

    public static class LastFunction {

        private Object lastValue;

        @UserAggregationUpdate
        public void aggregate(@Name("value") Object value) {
            if (value != null) {
                this.lastValue = value;
            }
        }

        @UserAggregationResult
        public Object result() {
            return lastValue;
        }
    }
}

TraversalDescription td;
try ( Transaction tx = graphDb.beginTx() ) {
     td = tx.traversalDescription();
}
Traverser traverser = td.traverse( startNode );
for ( Path path : traverser ) {
    // Extend as needed
}

TraversalDescription td = transaction.traversalDescription()
    .relationships(RelationshipType.withName("A"))
    .relationships(RelationshipType.withName("B"), Direction.OUTGOING);
return td.traverse(startNode);

TraversalDescription td;
try ( Transaction tx = graphDb.beginTx() ) {
     td = tx.traversalDescription()
            .evaluator(Evaluators.atDepth(2));
}

td.traverse( startNode );

class LabelEvaluator implements Evaluator {

    private final Label label;

    private LabelEvaluator(Label label) {
        this.label = label;
    }

    @Override
    public Evaluation evaluate(Path path) {
        if (path.endNode().hasLabel(label)) {
            return Evaluation.INCLUDE_AND_CONTINUE;
        } else {
            return Evaluation.EXCLUDE_AND_CONTINUE;
        }
    }
}

TraversalDescription td;
try ( Transaction tx = graphDb.beginTx() ) {
     td = tx.traversalDescription()
            .evaluator(Evaluators.atDepth( 2 ))
            .evaluator(new LabelEvaluator(Label.label("A")));
}

td.traverse( startNode );

td = tx.traversalDescription()
            .depthFirst();
td = tx.traversalDescription()
            .order(BranchOrderingPolicies.PREORDER_BREADTH_FIRST );

TraversalDescription td = transaction.traversalDescription()
    .expand(PathExpanders.forTypeAndDirection( RelationshipType.withName( "A" ), Direction.OUTGOING ));
td.traverse( startNode );

TraversalDescription td = transaction.traversalDescription()
    .expand(PathExpanderBuilder.empty()
                               .add(RelationshipType.withName("E1"))
                               .build());
td.traverse( startNode );

class MaxWeightPathExpander implements PathExpander<Double>
{

    private final double maxWeight;

    public MaxWeightPathExpander( double maxWeight ) {
        this.maxWeight = maxWeight;
    }

    @Override
    public Iterable<Relationship> expand( Path path, BranchState<Double> branchState )
    {
        if (path.lastRelationship() != null) {
            branchState.setState( branchState.getState() + (double) path.lastRelationship().getProperty( "weight" ) );
        }

        Iterable<Relationship> relationships = path.endNode().getRelationships( Direction.OUTGOING );
        ArrayList<Relationship> filtered = new ArrayList<>();
        for ( Relationship relationship : relationships ) {
            if ( branchState.getState() + (double) relationship.getProperty( "weight" ) <= maxWeight ) {
                filtered.add(relationship);
            }
        }
        return filtered;
    }

    @Override
    public PathExpander reverse()
    {
        throw new RuntimeException( "Not needed for the MonoDirectional Traversal Framework" );
    }
}

 public MonoDirectionalTraversalPathFinder(EvaluationContext context,
                                          PathExpander<State> expander,
                                          int maxDepth,
                                          State state,
                                          boolean depthFirst,
                                          Judgment judgment
) {
    super(context, expander, maxDepth, depthFirst);
    this.judgment = judgment;
    this.stack = new InitialBranchState.State<>(state, state.copy());
}

   public ForwardedPathExpander(boolean parallel, Processor processor) {
       this.processor = processor;
       String[] types = new String[]{"CALL>", "ALIAS>"};
...
   @Override
   public Iterable<Relationship> expand(Path path, BranchState<State> state) {
       final Node node = path.endNode();
       final Relationship lastRelationship = path.lastRelationship();
       processor.init(node, state.getState(), lastRelationship, calculator);

       if(processor.isNeedProcess()){
           Iterable<Relationship> relationships = node.getRelationships(direction, getRelationshipTypes(lastRelationship, state.getState()));
           List<Relationship> nextRelationships = StreamSupport.stream(relationships.spliterator(), parallel)
                   .map((next) -> processor.process(next))
                   .filter(Objects::nonNull)
                   .collect(Collectors.toList());
           state.setState(processor.getNextState());
           return nextRelationships;
       }

       return new ArrayList<>();
   }

// Branch 当前endNode
   public Node node = null;
   // 上一个State
   public State preState = null;
// 下一个State
public State nextState = null;
   // Branch 当前lastRelationship
   public Relationship lastRelationship = null;
   public Calculator calculator = null;
   public Set<Integer> polluted = null;

    public Relationship process(Relationship next) {
        Relationship ret = null;
        String nextId = next.getId() + "";
        // 如果是ALIAS关系
        if(Types.isAlias(next)){
            // nextState.positions.put
            // 增加一条边的污点信息，沿用上一个节点的
            nextState.put(nextId, polluted.stream().mapToInt(Integer::intValue).toArray());
            // alias 增加一条ALIAS
            nextState.addAliasEdge(next.getId());
            ret = next;
        }else{
        // 如果为CALL
        	// 获取 污点信息
            String pollutedStr = (String) next.getProperty("POLLUTED_POSITION");
            if(pollutedStr == null) return ret;
            // 解析污点映射关系，例如0->1,0->0
            int[][] callSite = JsonHelper.parse(pollutedStr);

//            // 为了处理当前设计的代码属性图的缺点，但测试后发现丢失的情况很多，暂不处理
//            if((!isAbstract || !isFromAbstractClass) && !PositionHelper.isCallerPolluted(callSite, polluted)){ // 如果当前调用边的调用者不可控，则下一次不进行alias操作
//                nextState.getNextAlias().add(next.getId());
//            }

            int[] nextPos = calculator.calculate(callSite, polluted);
            if(nextPos != null && nextPos.length > 0){
                nextState.put(nextId, nextPos);
                ret = next;
            }
        }
        return ret;
    }

private Map<String, int[]> positions; //保存id和污点信息
private List<Long> alias;
private List<Long> staticCalls;
private List<Long> nextAlias; 

public int[] v2(int[][] callSite, Set<Integer> polluted) {
    Set<Integer> nextPolluted = new HashSet<>();
    int length = callSite.length;
    for(int pos=0; pos<length; pos++){
        int[] current = callSite[pos];
        for(int c:current){
            if(polluted.contains(c)){
                nextPolluted.add(pos - 1);
                break;
            }
        }
    }
    return nextPolluted.stream().mapToInt(Integer::intValue).toArray();
}