README.md

   1 [![Build Status](https://github.com/pfalcon/ScratchABlock/actions/workflows/pycopy-test.yml/badge.svg)](https://github.com/pfalcon/ScratchABlock/actions/)
   2
   3 **Q**: Why is there a need for yet another decompiler, especially a
   4 crippled one?
   5
   6 **A**: A sad truth is that most decompilers out there are crippled. Many
   7 aren't able to decompile trivial constructs, others can't decompile more
   8 advanced, those which seemingly can deal with them, are crippled by
   9 supporting only the boring architectures and OSes. And almost every
  10 written in such a way that tweaking it or adding a new architecture is
  11 complicated. A decompiler is a tool for reverse engineering, but ironically,
  12 if you want to use a typical decompiler productively or make it suit your
  13 needs, first you will need to reverse-engineer the decompiler itself, and
  14 that can easily take months (or years).
  15
  16 How ScratchABlock is different?
  17 -------------------------------
  18
  19 The central part of a decompiler (and any program transformation framework)
  20 is Intermediate Representation (IR). A decompiler should work on IR, and
  21 should take it as an input, and conversion of a particular architecture's
  22 assembler to this IR should be well decoupled from a decompiler, or
  23 otherwise it takes extraordinary effort to add support for another
  24 architecture (which in turn limits userbase of a decompiler).
  25
  26 Decompilation is a complex task, so there should be easy insight into the
  27 decompilation process. This means that IR used by a decompiler should be
  28 human-friendly, for example use a syntax familiar to programmers, map as
  29 directly as possible to a typical machine assembler, etc.
  30
  31 The requirements above should be quite obvious on their own. If not, they
  32 can be learnt from the books on the matter, e.g.:
  33
  34 > "The compiler writer also needs mechanisms that let humans examine the IR
  35 > program easily and directly. Self-interest should ensure that compiler
  36 > writers pay heed to this last point."
  37 >
  38 > (Keith Cooper, Linda Torczon, "Engineering a Compiler")
  39
  40 However, decompiler projects, including OpenSource ones, routinely violate
  41 these requirements: they are tightly coupled with specific machine
  42 architectures, don't allow to feed IR in, and oftentimes don't expose or
  43 document it to user at all.
  44
  45 ScratchABlock is an attempt to say "no" to such practices and develop a
  46 decompilation framework based on the requirements above. Note that
  47 ScratchABlock can be considered a learning/research project, and beyond
  48 good intentions and criticism of other projects, may not offer too much
  49 to a casual user - currently, or possibly at all. It can certainly be
  50 criticised in many aspects too.
  51
  52
  53 Down to Earth part
  54 ------------------
  55
  56 ScratchABlock is released under the terms of GNU General Public License v3
  57 (GPLv3).
  58
  59 ScratchABlock is written in Python3 language, and tested with version 3.3
  60 and up, though may work with 3.2 or lower too (won't work with legacy
  61 Python2 versions). There're a few dependencies:
  62
  63 * PyYAML, https://pypi.python.org/pypi/PyYAML
  64 * nose-tests, https://pypi.python.org/pypi/nose (required only for unit
  65   tests).
  66
  67 On Debian/Ubuntu Linux, these can be installed with
  68 `sudo apt-get install python3-yaml python3-nose`. Alternatively, you can
  69 install these via Python's own `pip` package manager (should work for
  70 any OS): `pip3 install -r requirements.txt`.
  71
  72 ScratchABlock uses the *PseudoC* assembler as its IR. It is an assembler
  73 language expressed as much as possible using the familiar C language
  74 syntax. The idea is that any C programmer would understand it intuitively
  75 ([example](tests/ifelse2.lst)), but there is an ongoing effort to
  76 [document PseudoC more formally](docs/PseudoC-spec.md).
  77
  78 Note that based on the requirements described in the previous section of
  79 the document, and following well-known "Unix paradigm", ScratchABlock
  80 does "one thing" - analyses and transformations on PseudoC programs,
  81 and explicitly *not* concerned with converting machine instructions of
  82 particular architectures into PseudoC (at least, for now). That means
  83 that ScratchABlock doesn't force you to use any particular converter/
  84 lifter - you can use any you like. Caveat: you would need to have one
  85 to use it. See the end of the document for some hints in that regard.
  86
  87 Source code and interfacing scripts are in the root of the repository.
  88 The most important scripts are:
  89
  90 * `apply_xform.py` - A central driver, allows to apply a sequence of
  91 transformations (or in general, high-level analysis/transformation
  92 scripts) to a single file or a directory of files ("project directory").
  93
  94 * `inter_dataflow.py` - Interprocedural (global) dataflow analysis driver
  95   (WIP).
  96
  97 * `script_*.py` - High-level analysis/transformation scripts for
  98    `apply_xform.py` (`--script` switch).
  99
 100 * `script_i_*.py` - Analysis scripts for `inter_dataflow.py`.
 101
 102 * `run_tests` - The regregression testsuite runner. The majority of
 103 testsuite is high-level, consisting of running apply_xform.py with
 104 different passes on file(s) and checking the expected results.
 105
 106 Other subdirectories of the repository:
 107
 108 * `tests_unit` - Classical unit tests for Python modules, written in
 109 Python.
 110
 111 * `tests` - The main testsuite. While integrational in the nature, it
 112 usually tests one pass on one simple file, so follows the unit testing
 113 philosophy. Tests are represented as PseudoC input files, while
 114 expected results - as PseudoC with basic blocks annotation and (where
 115 applicable) CFG in .dot format. Looking at these testcases, trying
 116 to modify them and seeing the outcome is the best way to learn how
 117 ScratchABlock works.
 118
 119 * `docs` - A growing collection of documentation. For example, there's a
 120 [specification](docs/PseudoC-spec.md) of the PseudoC assembler language
 121 serving as the intermediate representation (IR) for ScratchABlock and
 122 a [survey](docs/ir-why-not.md) why another existing IR was not selected.
 123
 124 The current approach of ScratchABlock is to grow a collection of
 125 relatively loosely-coupled algorithms ("passes") for program analysis
 126 and transformation, have them covered with tests, and allow easy user
 127 access to them. The magic of decompilation consists of applying these
 128 algorithms in the rights order and right number of times. Then, to
 129 improve the performance of decompilation, these passes usually require
 130 more tight coupling. Exploring those directions is the next
 131 priority after implementing the inventory of passes as described
 132 above.
 133
 134 Algorithms and transformations implemented by ScratchABlock:
 135
 136 * Graph algorithms:
 137   * Construction and querying (predecessors, successors, etc.)
 138   * Traversal (depth first search (DFS), postorder)
 139   * Dominator tree/dominance frontiers
 140   * Node splitting
 141
 142 * Static Single Assignment form (SSA):
 143   * Construction
 144
 145 * Data flow analysis:
 146   * Generic iterative dataflow algorithm framework
 147   * Dominator tree
 148   * Reaching definitions
 149   * Live variables
 150   * Building def-use chains
 151
 152 * Propagation:
 153   * Constant
 154   * Copy
 155   * Memory references
 156   * Expressions
 157
 158 * Dead code elimination (DCE)
 159
 160 * Rewriting:
 161   * Of stack variables
 162   * Of structure fields (TODO)
 163   * Devirtualization (TODO)
 164
 165 * Control flow structuring:
 166   * Removal of jumps-over-jumps
 167   * Single exit
 168   * Loop single landing site
 169   * if/if-else/if-elif-else ladders
 170   * Control-flow "and" (if (a && b))
 171   * Abnormal selection via node splitting
 172   * while/do-while/infinite loops
 173   * Generic loop structuring (TODO)
 174   * Unreachable basic blocks elimination (TODO)
 175
 176 * Output formats:
 177   * PseudoC
 178   * PseudoC with annotated basic blocks
 179   * C
 180   * .dot (for control flow (CFGs) and other graphs)
 181   * YAML (for function properties database)
 182
 183 ScratchABlock's partner tool is [ScratchABit](https://github.com/pfalcon/ScratchABit),
 184 which is an interactive disassemler intended to perform the lowest-level
 185 tasks of decompilation process, like separation of code from data, and
 186 identifying function boundaries. ScratchABit usually works with a native
 187 architecture assembler syntax, but for some architectures (usually, faithful
 188 RISCs), if a suitable plugin is available, it can output a PseudoC syntax,
 189 which can serve as input to ScratchABlock.