commit b91a8b48614aec0f2a0324584378a6ee9d16de6d
parent 671b07d80623cc62aec232f63a31962d87263930
Author: Alex Balgavy <alex@balgavy.eu>
Date: Wed, 28 Apr 2021 15:46:39 +0200
Update BAMA notes
Diffstat:
1 file changed, 43 insertions(+), 0 deletions(-)
diff --git a/content/binary-malware-analysis-notes/tracking-control-flow.md b/content/binary-malware-analysis-notes/tracking-control-flow.md
@@ -39,4 +39,47 @@ You should:
- run the program multiple times, observe targets of indirect jumps and calls
- look for function prologue sequences (`push %rbp`, `mov %rsp, %rbp`)
+## Loops
+Loop: subgraph of CFG that is strongly connected (path from any node to any other node), single entry
+Two loops are either disjoint, or one is completely nested in the other.
+
+Identifying loops:
+- dominance: node a dominates b if all paths to b go through a (strictly if a and b are different, immediate if it's right before)
+
+Natural loops: single head node
+
+Dominator set D(i) = {i} ∪ (intersection for p ∈ Pred(i) of D(p)), where Pred is set of immediate predecessors
+
+Dominator tree: each node's children are nodes it immediately dominates
+
+Computing loops:
+1. compute dominator info, store it in a dominator tree
+2. identify back edges
+3. construct natural loops corresponding to back edges
+
+## Data-flow analysis
+Flow sensitivity
+- flow-sensitive analysis computes for each program point whatever you want to analyze
+- flow-insensitive pointer analysis computes what memory locations pointers may refer to, at any time in program execution
+
+Context-sensitive analysis considers calling context when analyzing target of function call
+
+### Reaching definitions
+Which data definitions can reach a point in the program.
+
+- For each basic block determine:
+ - which definitions the block generates (gen set)
+ - which it kills (kill set)
+- from this local solution build global one. determine:
+ - which definitions from anywhere can reach the start of a basic block
+ - in[B] = Union for p ∈ pred[B] of out[p]
+ - which definitions can still be alive after the basic block
+ - out[B] = gen[B] ∪ (in[B] - kill[B])
+- need to solve iteratively
+
+Definition-Use chains: definition of variable and all uses, reachable from that definition without other intervening definitions
+- compute: for each definition D, compute chain of uses that D may reach
+
+Use-definitions chains: use of variable and all definitions of that variable, that can reach that use without other intervening definitions
+- compute: for each use U, compute chain of definitions that reach U
