bap-std 2.3.0 · OCaml Package

Regular interface for BIL statements

type t = Bil.stmt

class state : object ... end

All visitors provide some information about the current position of the visitor

class 'a visitor : object ... end

Visitor. Visits AST providing lots of hooks.

class 'a finder : object ... end

A visitor with a shortcut. Finder is a specialization of a visitor, that uses return as its folding argument. At any time you can stop the traversing by calling return function of the provided argument (which is by itself is a record with one field - a function accepting argument of type 'a option).

class mapper : object ... end

AST transformation. mapper allows one to map AST, performing some limited amount of transformations on it. Mapper provides extra flexibility by mapping stmt to stmt list, thus allowing to remove statements from the output (by mapping to empty list) or to map one statement to several. This is particularly useful when you map if or while statements.

class constant_folder : mapper

constant_folder is a class that implements the fold_consts

val fold : 'a visitor -> init:'a -> t -> 'a

fold ~init visitor stmt folds a stmt with a visitor. See Bil.fold and Exp.fold for more details.

val iter : unit visitor -> t -> unit

iter visitor stmt iters over a stmt with a visitor. See Bil.iter and Exp.iter for more details.

val map : mapper -> t list -> t list

map mapper bil applies mapper to the program bil

val find : 'a finder -> t -> 'a option

find finder stmt performs a lookup into the Bil statement. See Bil.find and Exp.find for more details.

val exists : unit finder -> t -> bool

exists finder stmt is true iff find finder stmt <> None. See Bil.exists and Exp.exists for more details.

val is_referenced : var -> t -> bool

is_referenced x stmt is true is x is used in the stmt in any place other then right hand side of the assignment. E.g., is_referenced x Bil.(x := var x) is true, but is_referenced x Bil.(x := var y) is false. see Bil.is_referenced for more details.

val normalize : ?normalize_exp:bool -> stmt list -> stmt list

normalize ?normalize_exp xs produces a normalized BIL program with the same^1 semantics but in the BIL normalized form (BNF). There are two normalized forms, both described below. The first form (BNF1) is more readable, the second form (BNF2) is more strict, but sometimes yields a code, that is hard for a human to comprehend. The BNF1 is the default, to request BNF2 pass normalize_exp:true.

Precondition: xs is well-typed.

The BIL First Normalized Form (BNF1) is a subset of the BIL language, where expressions have the following properties:

Memory load expressions can be only applied to a memory. This effectively disallows creation of temporary memory regions, and requires all store operations to be committed via the assignment operation. Also, this provides a guarantee, that store expressions will not occur in integer assignments, jmp destinations, and conditional expressions, leaving them valid only in an assignment statement where the rhs has type mem_t. This is effectively the same as make the Load constructor to have type (Load (var,exp,endian,size)).

No load or store expressions in the following positions: 1. the right-hand side of the let expression; 2. address or value subexpressions of the store expression; 3. storage or address subexpressions of the load expression;

The BIL Second Normalized Form (BNF2) is a subset of the BNF1 (in a sense that all BNF2 programs are also in BNF1). This form puts the following restrictions:

No let expressions - new variables can be created only with the Move instruction.

All memory operations have sizes equal to one byte. Thus the size and endianness can be ignored in analysis. During the normalization, the following rewrites are performed

       let x = <expr> in ... x ... => ... <expr> ...
       x[a,el]:n => x[a+n-1] @ ... @ x[a]
       x[a,be]:n => x[a] @ ... @ x[a+n-1]
       m[a,el]:n <- x => (...((m[a] <- x<0>)[a+1] <- x<1>)...)[a+n-1] <- x<n-1>
       m[a,be]:n <- x => (...((m[a] <- x<n-1>)[a+1] <- x<n>)...)[a+n-1] <- x<0>
       (x[a] <- b)[c] => m := x[a] <- b; m[c]

^1: The normalization procedure may duplicate expressions that might be considered non-generative. For example,

let x = m[a] in x + x

is rewritten to m[a] + m[a]. Given a concrete semantics of a memory (for example, if memory is mapped to a device register that changes every times it is read) this expression may have different value. It will also have different effect (such as two memory accesses, page faults etc).

However, in the formal semantics of BAP we do not consider effects, and treat all expressions as side-effect free, thus the above transformation, are preserving the semantics.

parameter normalize_exp
(defaults to false) if set to true then the returned program will be in BNF2.

since 1.3

val simpl : ?ignore:Eff.t list -> t list -> t list

simpl ?ignore xs recursively applies Exp.simpl and also simplifies if and while expressions with statically known conditionals, e.g., if (true) xs ys is simplified to xs, while (false) xs is simplified to xs.

since 1.3

val fixpoint : (t -> t) -> t -> t

fixpoint f x applies transformation f until it reaches fixpoint. See Bil.fixpoint and Exp.fixpoint.

val free_vars : t -> Var.Set.t

free_vars stmt returns a set of all unbound variables, that occurs in stmt.

val eval : t list -> Bili.context as 'a -> 'a

eval prog eval BIL program under given context. Returns the context which contains all effects of computations.

include Regular.Std.Regular.S with type t := t

val bin_size_t : t Bin_prot.Size.sizer

val bin_write_t : t Bin_prot.Write.writer

val bin_read_t : t Bin_prot.Read.reader

val __bin_read_t__ : (int -> t) Bin_prot.Read.reader

val bin_shape_t : Bin_prot.Shape.t

val bin_writer_t : t Bin_prot.Type_class.writer

val bin_reader_t : t Bin_prot.Type_class.reader

val bin_t : t Bin_prot.Type_class.t

val t_of_sexp : Sexplib0__.Sexp.t -> t

val sexp_of_t : t -> Sexplib0__.Sexp.t

val to_string : t -> string

val str : unit -> t -> string

val pps : unit -> t -> string

val ppo : Core_kernel.Out_channel.t -> t -> unit

val pp_seq : Stdlib.Format.formatter -> t Core_kernel.Sequence.t -> unit

val pp : Base__.Formatter.t -> t -> unit

val (>=) : t -> t -> bool

val (<=) : t -> t -> bool

val (=) : t -> t -> bool

val (>) : t -> t -> bool

val (<) : t -> t -> bool

val (<>) : t -> t -> bool

val equal : t -> t -> bool

val compare : t -> t -> int

val min : t -> t -> t

val max : t -> t -> t

val ascending : t -> t -> int

val descending : t -> t -> int

val between : t -> low:t -> high:t -> bool

val clamp_exn : t -> min:t -> max:t -> t

val clamp : t -> min:t -> max:t -> t Base__.Or_error.t

type comparator_witness

val validate_lbound : min:t Base__.Maybe_bound.t -> t Base__.Validate.check

val validate_ubound : max:t Base__.Maybe_bound.t -> t Base__.Validate.check

val validate_bound : 
  min:t Base__.Maybe_bound.t ->
  max:t Base__.Maybe_bound.t ->
  t Base__.Validate.check

module Replace_polymorphic_compare : sig ... end

val comparator : (t, comparator_witness) Core_kernel__Comparator.comparator

module Map : sig ... end

module Set : sig ... end

val hash_fold_t : 
  Ppx_hash_lib.Std.Hash.state ->
  t ->
  Ppx_hash_lib.Std.Hash.state

val hash : t -> Ppx_hash_lib.Std.Hash.hash_value

val hashable : t Core_kernel__.Hashtbl.Hashable.t

module Table : sig ... end

module Hash_set : sig ... end

module Hash_queue : sig ... end

type info = string * [ `Ver of string ] * string option

val version : string

val size_in_bytes : ?ver:string -> ?fmt:string -> t -> int

val of_bytes : ?ver:string -> ?fmt:string -> Regular.Std.bytes -> t

val to_bytes : ?ver:string -> ?fmt:string -> t -> Regular.Std.bytes

val blit_to_bytes : 
  ?ver:string ->
  ?fmt:string ->
  Regular.Std.bytes ->
  t ->
  int ->
  unit

val of_bigstring : ?ver:string -> ?fmt:string -> Core_kernel.bigstring -> t

val to_bigstring : ?ver:string -> ?fmt:string -> t -> Core_kernel.bigstring

val blit_to_bigstring : 
  ?ver:string ->
  ?fmt:string ->
  Core_kernel.bigstring ->
  t ->
  int ->
  unit

module Io : sig ... end

module Cache : sig ... end

val add_reader : 
  ?desc:string ->
  ver:string ->
  string ->
  t Regular.Std.reader ->
  unit

val add_writer : 
  ?desc:string ->
  ver:string ->
  string ->
  t Regular.Std.writer ->
  unit

val available_readers : unit -> info list

val default_reader : unit -> info

val set_default_reader : ?ver:string -> string -> unit

val with_reader : ?ver:string -> string -> (unit -> 'a) -> 'a

val available_writers : unit -> info list

val default_writer : unit -> info

val set_default_writer : ?ver:string -> string -> unit

val with_writer : ?ver:string -> string -> (unit -> 'a) -> 'a

val default_printer : unit -> info option

val set_default_printer : ?ver:string -> string -> unit

val with_printer : ?ver:string -> string -> (unit -> 'a) -> 'a

val find_reader : ?ver:string -> string -> t Regular.Std.reader option

val find_writer : ?ver:string -> string -> t Regular.Std.writer option

val pp_adt : Stdlib.Format.formatter -> t -> unit

package bap-std