Skip to content

Commit

Permalink
Move Flatten to Lib (BinaryAnalysisPlatform#1390)
Browse files Browse the repository at this point in the history 
* Moved flattener code into lib from plugins

* Added trailing space

* ocp-indent

* Inlined module names

* added oasis section and expanded doc comments
  • Loading branch information
@philzook58
philzook58 authored Jan 5, 2022
1 parent 92d67c8 commit 3d90994
Show file tree
Hide file tree
Showing 6 changed files with 171 additions and 135 deletions.
24 changes: 24 additions & 0 deletions lib/bap/bap.mli
View file
Original file line number Diff line number Diff line change
Expand Up @@ -8502,6 +8502,14 @@ module Std : sig
*)
val compute_liveness : t -> (tid, Var.Set.t) Solution.t


(** [flatten sub] returns [sub] in flattened form in which all
operands are trivial.
@see Blk.flatten for more information about flattening.
@since 2.5.0 *)
val flatten : t -> t

(** other names for the given subroutine.*)
val aliases : string list tag

Expand Down Expand Up @@ -9066,6 +9074,22 @@ module Std : sig
[def] in [blk]. *)
val occurs : t -> after:tid -> tid -> bool

(** [flatten blk] translates [blk] into the flattened form.
In the flattened form, all operations are applied to variables,
constants, or unknowns, i.e., the operands could not be compound
expressions. E.g.,
{v
#10 := 11 * (#9 + 13) - 17
v}
is translated to,
{v
#11 := #9 + 13
#12 := 11 * #11
#10 := #12 - 17
v}
@since 2.5.0 *)
val flatten : t -> t

(** Builder interface. *)
module Builder : sig
(** This interface provides an efficient way to build new
Expand Down
3 changes: 3 additions & 0 deletions lib/bap_sema/bap_sema.ml
View file
Original file line number Diff line number Diff line change
Expand Up @@ -3,6 +3,7 @@ open Graphlib.Std
open Bap_disasm_std

module Ssa = Bap_sema_ssa
module Flatten = Bap_sema_flatten
module Ir_lift = Bap_sema_lift
module Ir_graph = Bap_ir_graph
module FV = Bap_sema_free_vars
Expand All @@ -25,6 +26,7 @@ module Std = struct
let lift = Ir_lift.blk
let from_insn = Ir_lift.insn
let from_insns = Ir_lift.insns
let flatten = Flatten.flatten_blk
end
module Sub = struct
include Ir_sub
Expand All @@ -36,6 +38,7 @@ module Std = struct
let is_ssa = Ssa.is_transformed
let free_vars = FV.free_vars_of_sub
let compute_liveness = FV.compute_liveness
let flatten = Flatten.flatten_sub
end

module Taint = Bap_sema_taint
Expand Down
138 changes: 138 additions & 0 deletions lib/bap_sema/bap_sema_flatten.ml
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,138 @@
open Core_kernel
open Bap_types.Std
open Bap_ir


let get_direct_typ (e : exp) : Type.t = match e with
| Bil.Var v -> Var.typ v
| Bil.Unknown (_,t) -> t
| Bil.Int w -> Type.Imm (Word.bitwidth w)
| _ -> failwith "the expression is not flattened"

class substituter (x : var) (x' : var) = object
inherit Exp.mapper as super

method! map_var v =
if Var.equal x v then Var x' else super#map_var v

method! map_let v ~exp ~body =
let exp = super#map_exp exp in
let body = if Var.equal x v then body else super#map_exp body in
Let (v, exp, body)
end

let flatten_exp (exp : exp) (blk : blk term) (before : tid) : exp * blk term =
let is_virtual = true in
let fresh = true in
let rec aux (exp : exp) (blk : blk term) = match exp with
| Bil.Load (x, y, endian, s) ->
let x, blk = aux x blk in
let y, blk = aux y blk in
let vtype = Type.Imm (Size.in_bits s) in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.Load (x, y, endian, s) in
let def = Ir_def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def
| Bil.Store (x, y, z, endian, s) ->
let x, blk = aux x blk in
let y, blk = aux y blk in
let z, blk = aux z blk in
let vtype = Type.Imm (Size.in_bits s) in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.Store (x, y, z, endian, s) in
let def = Ir_def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def
| Bil.BinOp (b, x, y) ->
let x, blk = aux x blk in
let y, blk = aux y blk in
let vtype = get_direct_typ x in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.BinOp(b, x, y) in
let def = Ir_def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def
| Bil.UnOp (u, x) ->
let x, blk = aux x blk in
let vtype = get_direct_typ x in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.UnOp(u, x) in
let def = Ir_def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def
| Bil.Var _
| Bil.Int _ -> exp, blk
| Bil.Cast (c, n, x) ->
let x, blk = aux x blk in
let vtype = Type.Imm n in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.Cast (c, n, x) in
let def = Ir_def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def
| Bil.Let (v, x, y) ->
let x, blk = aux x blk in
let var, blk = match x with
| Var v -> v, blk
| _ ->
let vtype = Var.typ v in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let def = Ir_def.create var x in
var, Term.prepend def_t ~before blk def in
let y = (new substituter v var)#map_exp y in
aux y blk
| Bil.Unknown (_, _) -> exp, blk
| Bil.Ite (x, y, z) ->
let x, blk = aux x blk in
let y, blk = aux y blk in
let z, blk = aux z blk in
let vtype = get_direct_typ y in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.Ite (x, y, z) in
let def = Ir_def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def
| Bil.Extract (n, p, x) ->
let x, blk = aux x blk in
let vtype = get_direct_typ x in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.Extract (n, p, x) in
let def = Ir_def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def
| Bil.Concat (x, y) ->
let x, blk = aux x blk in
let y, blk = aux y blk in
let vtype = get_direct_typ x in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.Concat (x, y) in
let def = Ir_def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def in
aux exp blk

let flatten_blk original_blk =
let rec flatten_elts (elts : Ir_blk.elt seq) (blk : blk term) =
let rec flatten_jmp (jmp : Ir_jmp.t) (expseq : exp seq) (blk : blk term) =
match Seq.next expseq with
| Some(hd, tl) ->
let exp, blk = flatten_exp hd blk (Term.tid jmp) in
Ir_jmp.substitute jmp hd exp |> Term.update jmp_t blk |>
flatten_jmp jmp tl
| None -> blk in

match Seq.next elts with
| Some (hd, tl) -> (match hd with
| `Def def ->
let exp, blk = flatten_exp (Ir_def.rhs def) blk (Term.tid def) in
Ir_def.with_rhs def exp |> Term.update def_t blk |>
flatten_elts tl
| `Jmp jmp -> flatten_jmp jmp (Ir_jmp.exps jmp) blk
| `Phi phi -> flatten_elts tl blk)
| None -> blk in

flatten_elts (Ir_blk.elts original_blk) original_blk

let flatten_sub =
Term.map blk_t ~f:flatten_blk
4 changes: 4 additions & 0 deletions lib/bap_sema/bap_sema_flatten.mli
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,4 @@
open Bap_ir

val flatten_sub : sub term -> sub term
val flatten_blk : blk term -> blk term
1 change: 1 addition & 0 deletions oasis/bap-std
View file
Original file line number Diff line number Diff line change
Expand Up @@ -203,5 +203,6 @@ Library sema
Bap_sema,
Bap_sema_lift,
Bap_sema_ssa,
Bap_sema_flatten,
Bap_sema_taint,
Bap_sema_free_vars
136 changes: 1 addition & 135 deletions plugins/flatten/flatten_main.ml
View file
Original file line number Diff line number Diff line change
Expand Up @@ -3,141 +3,7 @@ open Core_kernel

include Self()

let get_direct_typ (e : exp) : Type.t = match e with
| Bil.Var v -> Var.typ v
| Bil.Unknown (_,t) -> t
| Bil.Int w -> Type.Imm (Word.bitwidth w)
| _ -> failwith "the expression is not flattened"

class substituter (x : var) (x' : var) = object
inherit Exp.mapper as super

method! map_var v =
if Var.equal x v then Var x' else super#map_var v

method! map_let v ~exp ~body =
let exp = super#map_exp exp in
let body = if Var.equal x v then body else super#map_exp body in
Let (v, exp, body)
end

let flatten_exp (exp : exp) (blk : blk term) (before : tid) : exp * blk term =
let is_virtual = true in
let fresh = true in
let rec aux (exp : exp) (blk : blk term) = match exp with
| Bil.Load (x, y, endian, s) ->
let x, blk = aux x blk in
let y, blk = aux y blk in
let vtype = Type.Imm (Size.in_bits s) in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.Load (x, y, endian, s) in
let def = Def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def
| Bil.Store (x, y, z, endian, s) ->
let x, blk = aux x blk in
let y, blk = aux y blk in
let z, blk = aux z blk in
let vtype = Type.Imm (Size.in_bits s) in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.Store (x, y, z, endian, s) in
let def = Def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def
| Bil.BinOp (b, x, y) ->
let x, blk = aux x blk in
let y, blk = aux y blk in
let vtype = get_direct_typ x in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.BinOp(b, x, y) in
let def = Def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def
| Bil.UnOp (u, x) ->
let x, blk = aux x blk in
let vtype = get_direct_typ x in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.UnOp(u, x) in
let def = Def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def
| Bil.Var _
| Bil.Int _ -> exp, blk
| Bil.Cast (c, n, x) ->
let x, blk = aux x blk in
let vtype = Type.Imm n in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.Cast (c, n, x) in
let def = Def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def
| Bil.Let (v, x, y) ->
let x, blk = aux x blk in
let var, blk = match x with
| Var v -> v, blk
| _ ->
let vtype = Var.typ v in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let def = Def.create var x in
var, Term.prepend def_t ~before blk def in
let y = (new substituter v var)#map_exp y in
aux y blk
| Bil.Unknown (_, _) -> exp, blk
| Bil.Ite (x, y, z) ->
let x, blk = aux x blk in
let y, blk = aux y blk in
let z, blk = aux z blk in
let vtype = get_direct_typ y in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.Ite (x, y, z) in
let def = Def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def
| Bil.Extract (n, p, x) ->
let x, blk = aux x blk in
let vtype = get_direct_typ x in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.Extract (n, p, x) in
let def = Def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def
| Bil.Concat (x, y) ->
let x, blk = aux x blk in
let y, blk = aux y blk in
let vtype = get_direct_typ x in
let var = Var.create ~is_virtual ~fresh "flt" vtype in
let e = Bil.Concat (x, y) in
let def = Def.create var e in
Bil.Var var,
Term.prepend def_t ~before blk def in
aux exp blk

let flatten_blk original_blk =
let rec flatten_elts (elts : Blk.elt seq) (blk : blk term) =
let rec flatten_jmp (jmp : Jmp.t) (expseq : exp seq) (blk : blk term) =
match Seq.next expseq with
| Some(hd, tl) ->
let exp, blk = flatten_exp hd blk (Term.tid jmp) in
Jmp.substitute jmp hd exp |> Term.update jmp_t blk |>
flatten_jmp jmp tl
| None -> blk in

match Seq.next elts with
| Some (hd, tl) -> (match hd with
| `Def def ->
let exp, blk = flatten_exp (Def.rhs def) blk (Term.tid def) in
Def.with_rhs def exp |> Term.update def_t blk |>
flatten_elts tl
| `Jmp jmp -> flatten_jmp jmp (Jmp.exps jmp) blk
| `Phi phi -> flatten_elts tl blk)
| None -> blk in

flatten_elts (Blk.elts original_blk) original_blk

let flatten_sub =
Term.map blk_t ~f:flatten_blk

let main = Project.map_program ~f:(Term.map sub_t ~f:flatten_sub)
let main = Project.map_program ~f:(Term.map sub_t ~f:Sub.flatten)

;;
Config.manpage [
Expand Down

0 comments on commit 3d90994

Please sign in to comment.