Translator::translate_function_extended leads to Index does not exist for set entry

[2over12]

When retrieving the Loader::program of cyberblogger from https://github.com/trailofbits/cb-multios (compiled with clang 8.0.1) an error Err("Index does not exist for set_entry") is returned from the line control_flow_graph.set_entry(block_indices[&function_address].0)?; at the end of translate_function_extended. This occurs because for the function at address 0x45008 returns from the translate_block call in the x86 decoder immediately due to a CS_ERR_OK. This leaves the translation block with no instructions which results in a bogus insertion to the block_indices at block_indices.insert(*result.0, (block_entry, block_exit)); in translate_function_extended because block entry is set to 0 and block exit is set to 0 as nothing was inserted into the overall Function CFG and the block_entry variable was never set.

My hacky fix for an empty translation block is up at https://github.com/2over12/falcon

I simply check if there are no instructions for a block and add a new empty CFG to the block if so. There probably should not be an empty function though, it is currently unclear to me why falcon_capstone immediately returns a CS_ERR_OK, but it also probably worth handling an empty function in some sort of sane way.

[endeav0r]

Yeah, I think this is pretty ok. I'm going to implement the same logic here.

[endeav0r]

@2over12 if you get a chance, can you see if this fix solves that issue?

[endeav0r]

Also, I see your, "In progress interprocedural analysis."

Raptor is a higher-level IR over Falcon IL, similar to LLIL and MLIL. I think you may have better luck implementing over Raptor. https://github.com/falconre/raptor . Let me know if I need to get that cleaned up.

[2over12]

Hey, thanks for looking at this. So the fix does not quite work because in x86 translator.rs line 90 if capstone returns a CS_ERR_OK then a successor to this block is added at the next address. Since it failed immediately the offset is 0 resulting in the block being added as a successor of itself, which is not valid. This later results in a duplicate edge being added to the CFG during the merge on 327. That's why in my implementation I had block_translation_result.successors = Vec::new();. I believe this is safe because if there are no instructions then no successors should have been added except the invalid one.

Also, Raptor looks interesting. Trying to just get some basic context insensitive points-to analysis working. Will definitely check out operating over Raptor instead of Falcon IL

[endeav0r]

Can you stick the binary somewhere?

[2over12]

Yeah oops accidentally versioned it on my repo so you can find it here https://github.com/2over12/falcon/blob/master/bins/cyber_blogger

[endeav0r]

Yep, ok I understand now. I commented up the part in the x86 lifter where we call into Capstone a bit better:

falcon/lib/translator/x86/translator.rs

Line 86 in de99bf8

let instructions = match cs.disasm(disassembly_bytes, address + offset as u64, 1) {

I'm a little afraid of returning something, "Wrong," so what I'm going to do instead is return an error here. There's a new error, ErrorKind::DisassemblyFailure.

Loader::program() will work essentially the same way it does. However, if a function fails to lift, it will be omitted from the result.

There is now also Loader::program_verbose, which collects all of the errors and returns them as well as the result. It will keep going even if things fail.

I'm also noticing now I have program_recursive, which I'll probably want to break out the same way.

[endeav0r]

@2over12 if you have a chance sometime to test the branch fix-loader and can let me know if this fixes your stuff, let me know. https://github.com/falconre/falcon/tree/fix-loader

Otherwise, sometime tomorrow I'll merge this in and bump falcon to 0.4.6

[2over12]

Yeah, that makes a lot of sense to me and works on my tests when I merged it in. Also, I quickly looked over the MIPS and PPC translators and I don't think similar cases exist where you would need to throw a DisassemblyFailure, but might be worth double-checking since I'm not super familiar with that code. Thanks again!

Also was thinking programming loading may potentially end up taking several options at some point so instead of 4 methods might be advantageous to have an options structure for loading. Probably not at the point where that is required yet.