Several bugs - Githubissues

ZhangZhuoSJTU commented 6 years ago

[ ] When we construct SSA, there is possible a basic block only has a true conditional outgoing edges without false one, but in SSA'a API conditional_edges, we require both existed. Bug info sees in attached binary, function main.

[ ] In DCE, Phi node could also be selector and should not be removed. Bug info sees in attached binary, function fcn.00400da0.
[x] We might need a new opcode OpEq. There is a situation when a basic block only contains mov instructions. Right now, one opcode would contains all the registers moved into it. But, if this opcode belongs to another basic block, mentioned basic block will be removed. Bug info sees in attached binary, function fcn.00402650, block 0x402810.
[ ] When using symbols to identify functions, we have identified imported functions, thus there would be double imported functions in one RadecoModule.

Actually I can fix these bugs, but I do not know why my PR cannot pass the test. Thus, I leave this issue as a reminder.

mcf_strip.zip

New bug (08/28/2018):

[ ] When constructing SSA, we assume all the false edge of "?{" would come to the next instruction, like jz $-5 --> zf,?{,-5,rip,=,}, in which the assumption is all right. BUT for some instructions, like shr edx, 2 --> 0,cf,=,1,2,-,1,<<,edx,&,?{,1,cf,=,},2,edx,>>,edx,=,$z,zf,=,$p,pf,=,$s,sf,=, the assumption is totally wrong. This would cause serious problems in CFG.

New bug (09/01/2018):

[ ] In ESIL, what pushed into the stack actually is a value, not an identifier. For example, in push rsp --> rsp,8,rsp,-=,rsp,=[8], we first push rsp's value into the stack rather than rsp itself, which means the following opcodes should not influence the value on stack. In this case, if rsp's value is 0xfffffff8 at beginning, after this esil, we should have [0xfffffff0]=0xfffffff8. But the problem is, when constructing the SSA, we regards it as an identifier, which means 8,rsp,-= influences the value on stack. So if we do some simulation based on SSA, we will have [0xfffffff0]=0xfffffff0. Actually, this is something wrong about esil-rs's mechanism.

XVilka commented 6 years ago

@HMPerson1 @kriw @chinmaydd what do you think?

kriw commented 5 years ago

We might need a new opcode OpEq. There is a situation when a basic block only contains mov instructions. Right now, one opcode would contains all the registers moved into it. But, if this opcode belongs to another basic block, mentioned basic block will be removed. Bug info sees in attached binary, function fcn.00402650, block 0x402810.

Now OpMov is added by PR #230 .

XVilka commented 5 years ago

@Mm7 see also these regarding the correctness of the output.

kriw commented 5 years ago

In DCE, Phi node could also be selector and should not be removed. Bug info sees in attached binary, function fcn.00400da0.

I think selector is not deleted in DCE.

When using symbols to identify functions, we have identified imported functions, thus there would be double imported functions in one RadecoModule

Now, symbol is not used to identify functions. (See https://github.com/radareorg/radeco-lib/pull/224/commits/e1b81edb770d08b62a799aa754b2d1751b8e8839) But the problem will be reproduced if we use symbols.

ZhangZhuoSJTU commented 5 years ago

@kriw

In DCE, Phi node could also be selector and should not be removed. Bug info sees in attached binary, function fcn.00400da0.

I think selector is not deleted in DCE.

I have checked the DCE code, it seems possible for DCE to remove selector when the selector is a phi node.

Let's see the code. For function fn mark, it uses following code to check whether the code is dead.

pub fn mark<T>(ssa: &mut T)
where
    T: Clone
        + SSAExtra
        + SSAMod<ActionRef = <T as Graph>::GraphNodeRef, CFEdgeRef = <T as Graph>::GraphEdgeRef>,
{
    let nodes = ssa.values();
    let roots = registers_in_err!(ssa, exit_node_err!(ssa), ssa.invalid_value().unwrap());
    let mut queue = VecDeque::<T::ValueRef>::new();
    for node in &nodes {
        if let Ok(ref result) = ssa.node_data(*node) {
            if let NodeType::Op(ref op) = result.nt {
                if op.has_sideeffects() || ssa.is_selector(*node) {
                    queue.push_back(*node);
                }
            }
        } else {
            ssa.mark(node);
        }
    }
    ssa.clear_mark(&roots);
    queue.extend(&[roots]);
    while let Some(ni) = queue.pop_front() {
        if ssa.is_marked(&ni) {
            continue;
        }
        ssa.mark(&ni);
        queue.extend(ssa.operands_of(ni));
    }
}

It a phi node is selector and it is not used by other opcodes, following loop will miss it.

    for node in &nodes {
        if let Ok(ref result) = ssa.node_data(*node) { 
           // The phi node will go into this branch
            if let NodeType::Op(ref op) = result.nt {
                // The phi node will not go into this branch, because phi node is not opcode.
                // And also, this phi node is not used later.
                // As a result, the phi node will be removed later. 
                if op.has_sideeffects() || ssa.is_selector(*node) {
                    queue.push_back(*node);
                }
            }
        } else {
            ssa.mark(node);
        }
    }

If you check my attachment, I think you could reproduce this bug.

kriw commented 5 years ago

@ZhangZhuoSJTU I can't reproduce the bug. I tested following steps (at ee9b755dafbea341bcff8a5f83c7d3d2af7ff4d1)

$ ./target/debug/radeco mcf_strip
>> analyze fcn.00400da0
>> ir fcn.00400da0
    [@0x400963.0002] %61: $Unknown1(*?) = %60 | %38;
    JMP IF %61 0x400A60.0000 ELSE 0x400969.0000
...
    [@0x4009E8.0000] %293: $Unknown1(*?) = !%292;
    JMP IF %293 0x400A3D.0000 ELSE 0x4009EA.0000
...  
   [@0x400A32.0000] %497: $Unknown1(*?) = !%495;
    JMP IF %497 0x400A56.0000 ELSE 0x400A34.0000

It seems all selector nodes in fcn.00400da0 exist.

radareorg / radeco

Several bugs #221