blob: 8ffa82838cc93ad8e25adff74f4799833b8be586 [file] [log] [blame] [raw]
// Copyright (c) 2012-2018, Najjar Chedy
//
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.
const _ = require('underscore-node'),
logger = require('./logger').logger;
const InstructionType_jmp = 0;
const InstructionType_conditionalJmpInst = 1;
const InstructionType_notRetInst = 2;
const InstructionType_retInst = 3;
// deal with typeinfo name for, typeinfo for, vtable for
const isFunctionName = x => x.text.trim().indexOf('.') !== 0 && !x.text.includes(' for ');
const gccX86 = {
filterData: asmArr => {
const jmpLabelRegex = /\.L\d+:/;
const isCode = x => x && x.text && (x.source !== null || jmpLabelRegex.test(x.text) || isFunctionName(x));
return _.chain(asmArr)
.map(_.clone)
.filter(isCode)
.value();
},
isFunctionEnd: x => x[0] !== ' ' && x[0] !== '.' && x.indexOf(':') !== -1,
isBasicBlockEnd: (inst, prevInst) => inst[0] === '.' || prevInst.includes(' ret'),
getInstructionType: inst => {
if (inst.includes('jmp')) return InstructionType_jmp;
else if (inst.trim()[0] === 'j') return InstructionType_conditionalJmpInst;
else if (!inst.includes(' ret')) return InstructionType_notRetInst;
else return InstructionType_retInst;
},
extractNodeName: inst => inst.match(/\.L\d+/) + ':',
isJmpInstruction: x => x.trim()[0] === 'j'
};
const clangX86 = {
filterData: asmArr => {
const jmpLabelRegex = /\.LBB\d+_\d+:/;
const isCode = x => x && x.text && (x.source !== null || jmpLabelRegex.test(x.text) || isFunctionName(x));
const removeComments = x => {
const pos = x.text.indexOf('#');
if (pos !== -1)
x.text = x.text.substring(0, pos - 1);
return x;
};
return _.chain(asmArr)
.map(_.clone)
.filter(isCode)
.map(removeComments)
.value();
},
isFunctionEnd: x => x[0] !== ' ' && x[0] !== '.' && x.indexOf(':') !== -1,
isBasicBlockEnd: (inst, prevInst) => inst[0] === '.' || prevInst.includes(' ret'),
getInstructionType: function (inst) {
if (inst.includes('jmp')) return InstructionType_jmp;
else if (inst.trim()[0] === 'j') return InstructionType_conditionalJmpInst;
else if (!inst.includes(' ret')) return InstructionType_notRetInst;
else return InstructionType_retInst;
},
extractNodeName: inst => inst.match(/\.LBB\d+_\d+/) + ':',
isJmpInstruction: x => x.trim()[0] === 'j'
};
function splitToFunctions (asmArr, isEnd) {
if (asmArr.length === 0) return [];
const result = [];
let first = 1;
const last = asmArr.length;
const fnRange = {start: 0, end: null};
while (first !== last) {
if (isEnd(asmArr[first].text)) {
fnRange.end = first;
result.push(_.clone(fnRange));
fnRange.start = first;
}
++first;
}
fnRange.end = last;
result.push(_.clone(fnRange));
return result;
}
function splitToBasicBlocks (asmArr, range, isEnd, isJmp) {
let first = range.start;
const last = range.end;
if (first === last) return [];
const functionName = asmArr[first].text;
++first;
let rangeBb = {nameId: functionName.substr(0, 50), start: first, end: null, actionPos: []};
const result = [];
const newRangeWith = function (oldRange, nameId, start) {
return {nameId: nameId, start: start, actionPos: [], end: oldRange.end};
};
while (first < last) {
const inst = asmArr[first].text;
if (isEnd(inst, asmArr[first - 1] ? asmArr[first - 1].text : '')) {
rangeBb.end = first;
result.push(_.clone(rangeBb));
//inst is expected to be .L*: where * in 1,2,...
rangeBb = newRangeWith(rangeBb, inst, first + 1);
}
else if (isJmp(inst)) {
rangeBb.actionPos.push(first);
}
++first;
}
rangeBb.end = last;
result.push(_.clone(rangeBb));
return result;
}
function splitToCanonicalBasicBlock (basicBlock) {
const actionPos = basicBlock.actionPos;
let actPosSz = actionPos.length;
if (actionPos[actPosSz - 1] + 1 === basicBlock.end) {
--actPosSz;
}
if (actPosSz === 0)
return [{
nameId: basicBlock.nameId,
start: basicBlock.start,
end: basicBlock.end
}];
else if (actPosSz === 1)
return [
{nameId: basicBlock.nameId, start: basicBlock.start, end: actionPos[0] + 1},
{nameId: basicBlock.nameId + '@' + (actionPos[0] + 1), start: actionPos[0] + 1, end: basicBlock.end}
];
else {
let first = 0;
const last = actPosSz;
const blockName = basicBlock.nameId;
let tmp = {nameId: blockName, start: basicBlock.start, end: actionPos[first] + 1};
const result = [];
result.push(_.clone(tmp));
while (first !== last - 1) {
tmp.nameId = blockName + '@' + (actionPos[first] + 1);
tmp.start = actionPos[first] + 1;
++first;
tmp.end = actionPos[first] + 1;
result.push(_.clone(tmp));
}
tmp = {nameId: blockName + '@' + (actionPos[first] + 1), start: actionPos[first] + 1, end: basicBlock.end};
result.push(_.clone(tmp));
return result;
}
}
function concatInstructions (asmArr, first, last) {
return _.chain(asmArr.slice(first, last))
.map(x => x.text.substr(0, 50))
.value()
.join('\n');
}
function makeNodes (asmArr, arrOfCanonicalBasicBlock) {
return _.map(arrOfCanonicalBasicBlock, e => {return {
id: e.nameId,
label: `${e.nameId}${e.nameId.indexOf(':') !== -1 ? '' : ':'}\n${concatInstructions(asmArr, e.start, e.end)}`,
color: '#99ccff',
shape: 'box'
};});
}
function makeEdges (asmArr, arrOfCanonicalBasicBlock, rules) {
const edge = {};
const edges = [];
const setEdge = function (edge, sourceNode, targetNode, color) {
edge.from = sourceNode;
edge.to = targetNode;
edge.arrows = 'to';
edge.color = color;
};
const isBasicBlockEnd = rules.isBasicBlockEnd;
const hasName = function (asmArr, cbb) {
const asm = asmArr[cbb.end];
return asm ? isBasicBlockEnd(asm.text, '') : false;
};
const generateName = function (name, suffix) {
const pos = name.indexOf('@');
if (pos === -1)
return name + '@' + suffix;
return name.substring(0, pos + 1) + suffix;
};
// note: x.end-1 possible value: jmp .L*, {jne,je,jg,...} .L*, ret/rep ret, call and any other instruction that doesn't change control flow
_.each(arrOfCanonicalBasicBlock, function (x) {
let targetNode;
const lastInst = asmArr[x.end - 1].text;
switch (rules.getInstructionType(lastInst)) {
case InstructionType_jmp: {
//we have to deal only with jmp destination, jmp instruction are always taken.
//edge from jump inst
targetNode = rules.extractNodeName(lastInst);
setEdge(edge, x.nameId, targetNode, 'blue');
edges.push(_.clone(edge));
break;
}
case InstructionType_conditionalJmpInst: {
//deal with : branch taken, branch not taken
targetNode = rules.extractNodeName(lastInst);
setEdge(edge, x.nameId, targetNode, 'green');
edges.push(_.clone(edge));
targetNode = hasName(asmArr, x) ? asmArr[x.end].text : generateName(x.nameId, x.end);
setEdge(edge, x.nameId, targetNode, 'red');
edges.push(_.clone(edge));
logger.debug(edge);
break;
}
case InstructionType_notRetInst: {
//precondition: lastInst is not last instruction in asmArr (but it is in canonical basic block)
//note : asmArr[x.end] expected to be .L*:(name of a basic block)
// this .L*: has to be exactly after the last instruction in the current canonical basic block
if (asmArr[x.end]) {
targetNode = asmArr[x.end].text;
setEdge(edge, x.nameId, targetNode, 'grey');
edges.push(_.clone(edge));
}
break;
}
case InstructionType_retInst:
break;
}
});
logger.debug(edges);
return edges;
}
function generateCfgStructure (version, asmArr) {
const rules = version.includes('clang') ? clangX86 : gccX86;
const code = rules.filterData(asmArr);
const funcs = splitToFunctions(code, rules.isFunctionEnd);
if (!funcs.length) {
return funcs;
}
const result = {};
_.each(funcs, _.bind(function (rng) {
const basicBlocks = splitToBasicBlocks(code, rng, rules.isBasicBlockEnd, rules.isJmpInstruction);
let arrOfCanonicalBasicBlock = [];
_.each(basicBlocks, _.bind(function (elm) {
const tmp = splitToCanonicalBasicBlock(elm);
arrOfCanonicalBasicBlock = arrOfCanonicalBasicBlock.concat(tmp);
}, this));
result[code[rng.start].text] = {
nodes: makeNodes(code, arrOfCanonicalBasicBlock),
edges: makeEdges(code, arrOfCanonicalBasicBlock, rules)
};
}, this));
return result;
}
module.exports.generateStructure = generateCfgStructure;