package bap-std

  1. Overview
  2. Docs
package bap-std
Legend:
Library
Module
Module type
Parameter
Class
Class type

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.

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
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct