2019 · 44 citations · 40 references
ComputingComputer EngineeringComputer ScienceCompilersMalware AnalysisUncertainty QuantificationCode GenerationControl-flow AnalysisData-flow AnalysisBinary AnalysisBinary Control-flow AnalysisBinary DecompilationBinary DisassemblyData Flow PatternsInformation Loss AnalysisProbabilistic Control-flow Analysis
Disassembling stripped binaries is a prominent challenge for binary analysis, due to the interleaving of code segments and data, and the difficulties of resolving control transfer targets of indirect calls and jumps. As a result, most existing disassemblers have both false positives (FP) and false negatives (FN). We observe that uncertainty is inevitable in disassembly due to the information loss during compilation and code generation. Therefore, we propose to model such uncertainty using probabilities and propose a novel disassembly technique, which computes a probability for each address in the code space, indicating its likelihood of being a true positive instruction. The probability is computed from a set of features that are reachable to an address, including control flow and data flow features. Our experiments with more than two thousands binaries show that our technique does not have any FN and has only 3.7% FP. In comparison, a state-of-the-art superset disassembly technique has 85% FP. A rewriter built on our disassembly can generate binaries that are only half of the size of those by superset disassembly and run 3% faster. While many widely-used disassemblers such as IDA and BAP suffer from missing function entries, our experiment also shows that even without any function entry information, our disassembler can still achieve 0 FN and 6.8% FP.
40
Coverage-based Greybox Fuzzing as Markov Chain
Marcel Böhme, Van-Thuan Pham, Abhik Roychoudhury · 2016 · 619 citations
An Infrastructure for Adaptive Dynamic Optimization
2003 · 445 citations
Static disassembly of obfuscated binaries
Christopher Kruegel, William Robertson, Fredrik Valeur et al. · 2004 · 286 citations