Offensive Program Analysis - tnballo/notebook GitHub Wiki

References:

  1. "Be a Binary Rockstar @ Infiltrate 2017" by Sophia d’Antoine, Peter LaFosse, Rusty Wagner (2017)

  2. "(State of) The Art of War: Offensive Techniques in Binary Analysis" by Yan Shoshitaishvili, Ruoyu Wang, Christopher Salls, Nick Stephens, Mario Polino, Andrew Dutcher, John Grosen, Siji Feng, Christophe Hauser, Christopher Kruegel, Giovanni Vigna (2016)

Binary Analysis Tradeoffs

  • Replayability - Systems that execute a whole application from the beginning can reason about exactly what must be true to trigger a vulnerability, those that analyze individual subsets for feasibility may not be able to reason about how to trigger a vulnerable subset and/or replay a crash.

    • High replayability implies low code coverage, since end-to-end understanding is required it becomes increasingly infeasible for larger binaries.

    • Low replayability implies high false positives, since inputs cannot be replayed to validate bugs.

    • For CGC binaries, non-replayable techniques (ex. VSA, under-constrained symbolic execution) produced mostly false positives due to lack of context.

  • Semantic Insight - some analyses lack the context to reason about what they're observing/tracing in meaningful ways.

    • High semantic insight implies storing large amounts of data (ex. exact list of conditions that must hold for a specific branch to be taken) whereas low semantic insight allows more tuning for data domains of interest (ex. track ranges instead of actual values).

  • Soundness - guarantee that all potential vulnerabilities will be discovered.

    • High soundness implies poor scalability, since achieving it implies both high reproducibility and high semantic understanding.

    • A high fidelity environmental model is required for soundness and semantic understanding, requiring the modeling of complex environmental interactions.

  • Performance Aside - Note that most binary analysis techniques are limited by algorithmic slowness as opposed to language runtime (ex. it's acceptable that angr is implemented in Python), so language choice is a very minor performance factor.

Intermediate Representation (IR)

  • Intermediate Representation (IR) and Intermediate Language (IL) - IR is a "lifted" symbolic form for reasoning abstractly about assembly instructions. Used internally by compilers and virtual machines, can make manual reverse engineering faster because IR is architecture independent (by abstraction) and potentially more readable. An intermediate language (IL) is an implementation of IR.

    • A design tradeoff is ease of lifting (converting assembly to IR) vs. ease of analysis (readability/parsibility) and the factor that balances between the two is instruction set size. A more complex IR with a larger instruction set is easier to lift to but harder to analyze, likewise a small instruction set is difficult to lift but generally easier to read.

    • Example IRs include:

      • BAP - tree-based, written in OCAML

      • VEX - over 1k instructions, large set, meant for emulation more so then analysis

      • REIL - 17 instructions, so lacks higher level abstraction

      • LLVM - more for compilation then de-compilation, requires type extraction

      • Binary Ninja IL family - multi-stage IL optimized for manual reversing and lifting new architectures

  • Single Static Assignment (SSA) form - IR property requiring every variable to be assigned (i.e written to) exactly once and defined before use. If a variable is re-used, make a copy of the variable.

Static Analysis Techniques

  • Static analysis in general - either models program properties as graphs or models the data itself. Not repayable, doesn't explain how to trigger the vulnerability, offers low semantic insight because of simplified data domains (over-approximation), and tends to produce a great deal of false positives.

  • Abstract Interpretation - Take a set of concrete values, map them to an abstract domain (smaller set of abstract properties, ex. type, sign). Useful for higher level reasoning and vulnerability analysis.

    • Galois Connection - the (Abstract <-> Concrete) mapping, formalizes relationships.

  • Control Flow Graph (CFG) - nodes are basic blocks of instructions, edges are possible control flow transfers between them. A pre-requisite for most vulnerability-specific static analysis.

    • CFG recovery has difficulty dealing with indirect jumps (control transfer based on value in register or memory location). There are 3 types of indirect jumps:

      • Computed - code calculates jump target (ex. determine index into a vector/jump table).

      • Context-sensitive - jump targets determined by caller or external context (ex. callback functions are an input parameter).

      • Object-sensitive - object oriented languages use virtual tables of pointers to virtual functions (supports polymorphism).

    • CFG soundness vs. CFG completeness - CFG recovery is sound if all control flow transfers represented in the generated graph are actually possible (true positive rate), and complete if all possible control flow transfers are represented in the graph (reduction of false negatives).

  • Graph-based Vulnerability Discovery - build a model of a bug as represented by a set of nodes in a control flow or data-dependency graph, then search applications for occurrences of the model. In practice can be effective for finding copies of existing vulnerable code, but not for the discovery of new vulnerabilities. This is an application of flow modeling.

  • Value-set Analysis (VSA) - over-approximate program state (values in memory and registers) for every given point in the program. Particularly useful for detecting overlapping buffers by looking at approximate access patterns of memory reads/writes. This is an application of data modeling.

Dynamic Analysis Techniques

  • Dynamic analysis in general - examine a programs execution in an emulated or actual environment, either concretely or symbolically. Highly repayable, but varying levels of semantic insight.

  • Dynamic Concrete Execution (DCE) - run the program in a minimally instrumented environment, typically reasoning about a single path taken given some specific input. The major limitation is that it requires test cases, which is a problem when the datasets are large or unknown.

    • Fuzzing - provide malformed input in an attempt to trigger a crash and thus discover a bug, mutate the input with some degree of randomness until a crash is found.

      • Coverage-based - attempt to produce inputs that maximize code executed in the target application, ex. American Fuzzy Lop (AFL). Low semantic insight, the fuzzer doesn't understand the relationship between a part of input that was mutated and the code block reached.

      • Taint-based - attempts to understand how the program processes inputs to know which parts of input in modify in future runs, but still can't tell exactly how they should be modified to reach a given block of code.

      • A limitation of fuzzers is de-randomization in execution - sources of randomness (current time, sensor input, process PID, etc) are hardcoded in to ensure results are repayable and because modeling randomness is difficult.

  • Dynamic Symbolic Execution (DSE) - executes a program in an emulated environment, but in the abstract domain of symbolic variables, tracking constraints throughout. Very high level of semantic insight, can reason about how to trigger a specific program state by accumulating path constraints during exploration and then using them to generate input.

    • Suffers from the state explosion problem - the number of paths grows exponentially with each branch taken (execution must fork and follow both paths, saving the branch condition as a path constraint) and quickly become impossible to reason about. The implication is that DSE can typically only reason about shallow paths.

    • Prioritizing promising paths or merging paths when appropriate can be mildly helpful, but state explosion is a major and open problem.

      • Under-constrained symbolic execution (ex. S2E) attempts to symbolically execute only parts of the application, but this can lead to false positives because proper context can't be ensured and thus trades replayability for scalability.

      • Veritesting attempts to selectively merge paths to keep state explosion in check and facilitate exploration of deeper paths. However, path merging can introduce complex expressions and overwhelm the constraint solver - hence Veritesting may identify shallow bugs for which DSE fails due to state explosion, but still miss longer paths due to constraint solver overload.

  • Symbolic-assisted Fuzzing - modifying fuzzer inputs with a dynamic execution engine, creating additional or better (increased coverage) test cases based on semantic insight and then offloading processing work on the fuzzer to mitigate state explosion.

    • This combination is currently an effective and scalable technique for vulnerability discovery, but for GCG binaries only found about 10% more vulnerabilities than the fuzzing (AFL) alone - a significant but not dramatic improvement.

Misc Notes on the DARPA Cyber Grand Challenge (CGC)

  • Announced October 2013, qualifying June 2015, finals August 2016.

  • Only 7 system calls in DECREE OS (by comparison modern Linux variants have 300+):

    • transmit, recieve, waitfd - send, recieve, and wait for data over file descriptors, respectively.

    • random - generate random data

    • allocate, dellocate - memory management

    • terminate - exit

  • Unlike many real applications, there was a stipulation that control flow cannot be impacted by random data (ex. system time, sensor input, randomized cookies/tokens) in CGC challenge binaries.

  • Two exploit types:

    • Type 1 - demonstrate attacker control of a general purpose register and the instruction pointer register.

    • Type 2 - demonstrate attacker capability to perform a controlled read from process memory space.

  • Challenge binaries ranging from 4kb to 10mb.

⚠️ **GitHub.com Fallback** ⚠️