CFR Limitations

[task3r]

Hi there, I am considering using CFR mode for a use case that has low patching coverage. In my scenario, missing a single patch would result in a loss of soundness, so it is crucial to ensure that this does not happen.

Although I have read the PR and the referenced commit about CFR, I still have some questions regarding the compromises made regarding robustness. You mentioned that CFR provides weaker guarantees, but only listed two exceptions. Is there a more detailed description available regarding the heuristics and trade-offs? Additionally, is there a list of unsupported behaviors a binary might have that I can check to determine whether the patching will be robust or not?

Thank you in advance.

[GJDuck]

See the following link for the trade-offs: https://github.com/GJDuck/e9patch/blob/master/doc/e9tool-user-guide.md#modes

CFR-mode depends on a conservative control-flow recovery analysis that attempts to overapproximate the set of jump targets. This analysis does use some heurstics/assumptions about common patterns (e.g., jump tables) emitted by standard compilers, such as gcc/clang. If these assumptions turn out to wrong, e.g., weird hand-written assembly, or compilers doing unexpected things, the set of jump targets may be an underapproximation, which means control-flow could jump to a location that is not handled by E9Patch. This will usually result in a SIGTRAP, but could cause other unexpected behaviour.

Unfortunately, it is not possible to detect if a binary rewritten under CFR mode has a problem or not. At best, you could try testing, fuzzing, etc., to increase confidence.

If your application requires perfect coverage, then you should also try the 100% mode:

    $ e9tool -100 ...

This will use illegal opcodes and signal handlers to patch any left-over instructions as a last resort. This mode is also robust and sound. However, this mode can be slow if an illegal opcode is installed in a critical inner loop. The 100% and CFR modes can also be combined.

[task3r]

Thank you for the quick response. Could I somehow extract e9patch's presumed set of jump targets? That way I could instrument the jump instructions in the binary and run a preliminary execution to collect the actual jump targets. Assuming branch coverage, this could validate CFR's robustness for that binary and fallback to worse but robust patching otherwise. Nevertheless, if possible, it would be great if this collection of assumptions was available somewhere (I understand it is in the code, by I am not smart enough to fully understand it :)).

About the 100% mode, from my understanding of posix signals, unless a mask is applied, they can be caught by any thread inside the process, right? Does this mode work with multithreaded code?

Once again, thank you.

[GJDuck]

There is currently no way to extract the CFR analysis result from the command-line.

However, the code is reasonably simple if you want to try yourself. The analysis result is stored in B->targets, which is nothing more than a bitmap mapping ELF file offsets to 1 (jump target) or 0 (not jump target). The addrToOffset() helper function maps addresses to the corresponding offset, which can be passed to isTarget() to query the bitmap.

As mentioned, the analysis is an over-approximation, so non-targets may be marked as 1, but a real-target should not be marked as 0 (this would indicate a bug in the analysis, or the binary uses non-conventional indirect jumps not covered by the analysis).

The assumptions for the CFR analysis are:

• Any byte sequence that is (1) in executable memory, and (2) a valid x86_64 jump/call/address-load instruction, is assumed to actually be that instruction (whether it really is or not does not matter, since we are computing an over-approximation).
• Apparent jump tables (with the common/standard layout) really are jump tables
• Executable addresses stored in data really are jump targets (again, over-approximation)
• ELF entry-points/symbols are jump targets
• Any byte sequence that matches the endbr64 instruction really is a jump target if Intel CET is enabled.
• Maybe some other cases...

The result is an over-approximation of the actual jump targets, but this is fine for E9Patch. Basically, E9Patch will use this information purely as an optimization, i.e., by opportunistically optimizing the case where the instruction(s) are not targets. Otherwise, for instructions that are apparent targets, E9Patch will fall back to its default mode that is control-flow agnostic. Compare this approach with traditional rewriters/reassemblers (e.g., RetroWrite), which I believe requires accurate control-flow-recovery (not an over-approximation) in order to correctly rewrite the binary.

As for 100% mode, it uses illegal opcodes to generate a SIGILL, and SIGILL is a thread-directed signal, meaning that it should always be handled by the thread that attempted to execute the illegal opcode. So the 100% mode should work fine for multi-threaded applications.

[task3r]

Thank you very much for the in-depth response. My questions are totally clarified. I'll close the issue.