Make analysis and disassembly incremental

[XVilka]

Incremental computing, also known as incremental computation, is a software feature which, whenever a piece of data changes, attempts to save time by only recomputing those outputs which depend on the changed data. When incremental computing is successful, it can be significantly faster than computing new outputs naively. For example, a spreadsheet software package might use incremental computation in its recalculation feature, to update only those cells containing formulas which depend (directly or indirectly) on the changed cells.

When incremental computing is implemented by a tool that can implement it for a variety of different pieces of code automatically, that tool is an example of a program analysis tool for optimization.

Adapton is a good example of incremental computation framework implemented in Rust. Fungi is the typed incremental computation language based on Adapton.

BAP 2.0 recently switched its disassembly and analysis engine to be of incremental nature:

New Speculative Disassembling Driver

This PR also provides a completely new, written from scratch, driver for disassembling (as well as all existing disassemblers are rewritten to use this driver). The driver is using the new Knowledge Framework and builds the whole program CFG incrementally storing only the minimum information in the process memory. It could be used to implement disassemblers of different favors, e.g., linear, recursive descent, probabilistic, and superset disassemblers.

It is implemented as a recursive descent parser with arbitrary backtracking and is capable to automatically refute instruction chains which are not terminated by jumps, thus seriously reducing the generated CFG in speculative and superset modes.

More importantly, the disassembler is designed to work incrementally and build the CFG on the fly, so that we can analyze huge binaries, each subroutine independently. Which also relies on a new CFG reconstruction and function boundaries algorithm described below.

[radare]

I think i filled an issue for this some years ago. Mainly to make analysis interruptable

…

On 15 Aug 2019, at 09:20, Anton Kochkov ***@***.***> wrote: Incremental computing, also known as incremental computation, is a software feature which, whenever a piece of data changes, attempts to save time by only recomputing those outputs which depend on the changed data. When incremental computing is successful, it can be significantly faster than computing new outputs naively. For example, a spreadsheet software package might use incremental computation in its recalculation feature, to update only those cells containing formulas which depend (directly or indirectly) on the changed cells. When incremental computing is implemented by a tool that can implement it for a variety of different pieces of code automatically, that tool is an example of a program analysis tool for optimization. Adapton is a good example of incremental computation framework implemented in Rust. Fungi is the typed incremental computation language based on Adapton. BAP 2.0 recently switched its disassembly and analysis engine to be of incremental nature: New Speculative Disassembling Driver This PR also provides a completely new, written from scratch, driver for disassembling (as well as all existing disassemblers are rewritten to use this driver). The driver is using the new Knowledge Framework and builds the whole program CFG incrementally storing only the minimum information in the process memory. It could be used to implement disassemblers of different favors, e.g., linear, recursive descent, probabilistic, and superset disassemblers. It is implemented as a recursive descent parser with arbitrary backtracking and is capable to automatically refute instruction chains which are not terminated by jumps, thus seriously reducing the generated CFG in speculative and superset modes. More importantly, the disassembler is designed to work incrementally and build the CFG on the fly, so that we can analyze huge binaries, each subroutine independently. Which also relies on a new CFG reconstruction and function boundaries algorithm described below. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

[XVilka]

I wasn't able to find it. Maybe different wording? Anyway, it is a useful concept.