Unable to hook branch execution?

[csujedihy]

There are two limitations I've found. Just want to confirm with you guys.

1. No way to hook &&, || as a binary operation. There is a conditional(iid, result) for those but it only provides the result. However, I want to analyze the the left and right value for && and ||.

2. No way to hook branch execution.

if (expr) {
    do A;
} else {
    do B;
}

1. There is no hook to notify me which branch the code is entering.
2. Difficult to obtain the final expr value.

I think there should be a unique id to mark a if-else, do-while block. Furthermore, a callback is fired when every sub-block starts and ends. Thus, analysis for branch execution can be done.

[esbena]

With enough pre-processing of the instrumented AST, you can have the information. It is inconvenient to write the AST-analysis, but it is not a limitation of Jalangi itself.

The astHandler (https://github.com/Samsung/jalangi2/blob/master/src/js/utils/api.js#L99) argument allows you to do the pre-processing.

---

Furthermore, a callback is fired when every sub-block starts and ends. Thus, analysis for branch execution can be done.

I implemented the analysis for that some time ago, I have pasted the AST-part of it below (typescript), but I do not know how well it behaves with the current Jalangi instrumentation. I hope it can be of some help to you.

The general idea is to identify the branches of a conditional and extract all IIDs inside them. At runtime, you will know that you have left a branch when you observe an IID outside the set of IIDs associated with the branch. (You will also need to manually maintain a call-stack for any calls inside the branch).

/// <reference path="./types.d.ts" />
/// <reference path="./jalangi/jalangi.d.ts" />
import jalangi = require('./jalangi/jalangi-interface');
var astUtil = jalangi.getAstUtil();

export class ControlStructureImpl implements ControlStructure {
    /**
     * @param condition as the iid of the last evaluated expression before entering the body
     * @param conditionBody as all the iids in the condition
     * @param body as all the iids evaluated after the condition (including the 'i++' part of for loops!)
     */
    constructor(public condition:IIDPrimitive, public body:IIDPrimitive[]) {
    }

    toJSON() {
        return {
            condition: this.condition,
            body: this.body
        }
    }
}
export class ControlStructuresImpl implements ControlStructures {
    constructor(public values:ControlStructure[]) {
    }

    toJSON() {
        return {values: this.values};
    }

}

function isJalangiFunctionCall(node:Node) {
    return node.type === 'CallExpression' &&
        node.callee.type === 'MemberExpression' &&
        node.callee.object.type === 'Identifier' &&
        node.callee.object.name === astUtil.JALANGI_VAR;
}
function controlStructureAnalysis(node:AST, nodeName:string, conditionChooser:(n:Node) => Node, bodyPartsChooser:(n:Node) => [Node]):ControlStructures {
    function collectAllPrimitiveIIDsInFunction(node:Node):IIDPrimitive[] {
        var iids:IIDPrimitive[] = [];
        var visitorPre = {
            "CallExpression": function (node:Node) {
                if (isJalangiFunctionCall(node) && node.arguments.length > 0) {
                    iids.push(node.arguments[0].value);
                }
            }
        };

        function ignoreSubAst(node:Node) {
            return node.type === "FunctionDeclaration" || node.type === "FunctionExpression";
        }

        astUtil.transformAst(node, undefined, visitorPre, 1 /*CONTEXT.RHS*/, false, ignoreSubAst /* NB: requires patched jalangi2! */);
        return iids;
    }

    var controlStructures:ControlStructure[] = [];
    var visitorPre:any = {};
    visitorPre[nodeName] = function (node:Node) {
        var conditionNode = conditionChooser(node);
        if (!conditionNode ||
                /* The Jalangi while(true){...} loop */
            (node.type === "WhileStatement" && conditionNode.type === 'Literal' && conditionNode.value === true) ||
                /* The Jalangi function return/backtrack and script return*/
            (node.type === "IfStatement" && isJalangiFunctionCall(conditionNode) && (conditionNode.callee.property.name === "Fr" || conditionNode.callee.property.name === "Sr"))
        ) {
            return;
        }
        var conditionBody = collectAllPrimitiveIIDsInFunction(conditionNode);
        var condition = conditionBody[0];
        var body:IIDPrimitive[] = [];
        body = body.concat(conditionBody);

        var bodyParts = bodyPartsChooser(node);
        for (var i = 0; i < bodyParts.length; i++) {
            var bodyPart = bodyParts[i];
            if (!!bodyPart) {
                body = body.concat(collectAllPrimitiveIIDsInFunction(bodyPart));
            }
        }
        controlStructures.push(new ControlStructureImpl(condition, body));
    };
    astUtil.transformAst(node, undefined, visitorPre, 1 /*CONTEXT.RHS*/);
    return new ControlStructuresImpl(controlStructures);
}
interface Node {
    // acorn node
    type: string
    callee?: Node
    object?: Node
    name?:string
    arguments?: Node[]
    value?: any
    property?: Node
}

export function astAnalysis(instrumentedAST:AST):ExtraASTInfo {
    return {
        // forIns: controlStructureAnalysis(instrumentedAST, "ForInStatement", (n:Node)=>[n.body.statements[0]["APPROX"]], (n:Node)=>(n:Node)=>n.body.statements.slice(1)),
        fors: controlStructureAnalysis(instrumentedAST, "ForStatement", (n:any)=>n.test, (n:any)=>[n.update, n.body]),
        whiles: controlStructureAnalysis(instrumentedAST, "WhileStatement", (n:any)=>n.test, (n:any)=>[n.body]),
        ifs: controlStructureAnalysis(instrumentedAST, "IfStatement", (n:any)=>n.test, (n:any)=>[n.consequent, n.alternate]),
        ternaries: controlStructureAnalysis(instrumentedAST, "ConditionalExpression", (n:any)=>n.test, (n:any)=>[n.consequent, n.alternate])
    };
}