Tai-e Assignments

24 Jan 2023 on Courses

Tai-e Assignments: details and debug

Tai-e Assignments记录

• Assignments
• A1 LiveVar
• A2 Constant Propagation
• A3 DeadCode
• A4 Inter Constant Propagation
• A5 Context-Insensitive Pointer Analysis
• A6 Context-sensitive Pointer Analysis
• Alias-Aware Interprocedural Constant Propagation
• Taint Analysis

Assignments

A1 LiveVar

按照PPT完成对应的函数即可

A2 Constant Propagation

按照PPT完成对应的函数即可

A3 DeadCode

维护一个livecode，类似于BFS，将可达的加入进去即可。四种分支语句判断条件需要仔细一些。

A4 Inter Constant Propagation

CHA builder中讲义漏了一个interface,在OJ中，如果有CHA检测callsite不全，可能是resolve函数没有处理interface的情况

A5 Context-Insensitive Pointer Analysis

不会visit，在addReachable中判断stmt的类型添加PFGEdge。

stmt instanceof Invoke l && l.isStatic()情况下也要addReachable

A6 Context-sensitive Pointer Analysis

注意讲义上的selectContext的说明，heap是k-1，其他的是k。

Alias-Aware Interprocedural Constant Propagation

思想：讲义说是Load会meet所有对应store的值，所以在worklist中处理所有的store，将设涉及的Load全部加入LoadList，在后续transferNode中，进行meet的计算。

注意，loadarray需要考虑到meet别名的情况。如果当前的是constant，需要meet其他的constant和NAC两种情况。如果是NAC，则也需要meet所有不是undef的值。

这些值需要全局的一个map来记录（因为是flow insensitive）

if (index.isConstant()) {
    newVal = meetValue(newVal, ArrayMap.getOrDefault(new Pair<>(obj, index), Value.getUndef()));
    newVal = meetValue(newVal, ArrayMap.getOrDefault(new Pair<>(obj, Value.getNAC()), Value.getUndef()));
} else if(index.isNAC()) {
    for (var p: ArrayMap.entrySet()) {
        if (p.getKey().first().equals(obj) && p.getKey().second() != Value.getUndef()) {
            newVal = meetValue(newVal, p.getValue());
        }
    }
}

Taint Analysis

callSite解析需要resolveCallee来获得callee。

OJHidden有一个没有过是因为在计算Taint transfer的过程中，TaintObject需要改变returnType根据arg-to-base, base-to-result, arg-to-result,需要区分base和result的类型。