Expressions module

Creating and manipulating abstract expressions.

This module implements all the classes representing abstract expressions (as Abstract Syntax Trees), as well as many operators used to build new expressions from existing ones. Abstract expressions are the most basic object in Maat and are used everywhere: to represent register values, memory content, etc.

Abstract expressions should always be manipulated transparently through Expr instances.

❱   Classes

class maat::ValueSet

class maat::ExprObject

class maat::ExprCst
Constant expression.

class maat::ExprVar
Abstract variable.

class maat::ExprUnop
Unary operation.

class maat::ExprBinop
Binary operation.

class maat::ExprExtract
Bitfield extract.

class maat::ExprConcat
Concatenation of two expressions.

class maat::ExprITE
If-Then-Else expression.

class maat::Number
Represents a constant value on an arbitrary number of bits.

class maat::ExprSimplifier

class maat::Value

class maat::VarContext

❱   Enums

enum class ExprType { VAR, MEM, EXTRACT, CONCAT, UNOP, BINOP, ITE, CST, NONE }
Different types of abstract expressions.

enum class ITECond: uint8_t { EQ, LT, LE, SLT, SLE, FEQ, FLT, FLE }

enum class Op: uint8_t { ADD =0, MUL, MULH, SMULL, SMULH, DIV, SDIV, NEG, AND, OR, XOR, SHL, SHR, SAR, MOD, SMOD, NOT, NONE }

enum class ExprStatus: uint8_t { CONCRETE, SYMBOLIC, CONCOLIC, NOT_COMPUTED }

enum class Taint: uint8_t { NOT_TAINTED = 0, TAINTED = 1, NOT_COMPUTED = 2 }

❱   Typedefs

using Expr = std::shared_ptr<ExprObject>

using ExprSimplifierFunc = Expr(*)(Expr)

using hash_t = uint32_t
Unique hash identifying an abstract expression object.

using cst_t = int64_t
Signed constant integer value.

using ucst_t = uint64_t
Unsigned constant integer value.

using fcst_t = double
Float constant value (double precision / 64 bits)

❱   Functions

auto operator<(ExprType t1, ExprType t2) -> bool
Computes the priority of expression types. Used exclusively for expression canonization.

auto exprcst(size_t size, cst_t cst) -> Expr
Create new ExprCst instance.

auto exprcst(size_t size, std::string&& value, int base = 16) -> Expr
Create new ExprCst instance.

auto exprcst(const Number& value) -> Expr
Create a new ExprCst instance.

auto exprvar(size_t size, std::string name, Taint tainted = Taint::NOT_TAINTED) -> Expr
Create new ExprVar instance.

auto exprmem(size_t size, Expr addr, unsigned int access_count = 0xffffffff, Expr base = nullptr) -> Expr
Create new ExprMem instance.

auto exprmem(size_t size, Expr addr, unsigned int access_count, Expr base, ValueSet& addr_value_set) -> Expr
Create new ExprMem instance.

auto extract(Expr arg, unsigned long higher, unsigned long lower) -> Expr
Create new ExprExtract instance.

auto extract(Expr arg, Expr higher, Expr lower) -> Expr
Create new ExprExtract instance.

auto concat(Expr upper, Expr lower) -> Expr
Create new ExprConcat instance.

auto ITE(Expr cond_left, ITECond cond_op, Expr cond_right, Expr if_true, Expr if_false) -> Expr
Create new ExprITE instance.

auto operator+(Expr left, Expr right) -> Expr
Add two expressions.

auto operator+(Expr left, cst_t right) -> Expr
Add two expressions.

auto operator+(cst_t left, Expr right) -> Expr
Add two expressions.

auto operator-(Expr left, Expr right) -> Expr
Subtract two expressions.

auto operator-(Expr left, cst_t right) -> Expr
Subtract two expressions.

auto operator-(cst_t left, Expr right) -> Expr
Subtract two expressions.

auto operator*(Expr left, Expr right) -> Expr
Unsigned multiply two expressions (lower bits of result)

auto operator*(Expr left, cst_t right) -> Expr
Unsigned multiply two expressions (lower bits of result)

auto operator*(cst_t left, Expr right) -> Expr
Unsigned multiply two expressions (lower bits of result)

auto operator/(Expr left, Expr right) -> Expr
Unsigned divide two expressions.

auto operator/(Expr left, cst_t right) -> Expr
Unsigned divide two expressions.

auto operator/(cst_t left, Expr right) -> Expr
Unsigned divide two expressions.

auto operator&(Expr left, Expr right) -> Expr
Logical and between two expressions.

auto operator&(Expr left, cst_t right) -> Expr
Logical and between two expressions.

auto operator&(cst_t left, Expr right) -> Expr
Logical and between two expressions.

auto operator|(Expr left, Expr right) -> Expr
Logical or between two expressions.

auto operator|(Expr left, cst_t right) -> Expr
Logical or between two expressions.

auto operator|(cst_t left, Expr right) -> Expr
Logical or between two expressions.

auto operator^(Expr left, Expr right) -> Expr
Logical xor between two expressions.

auto operator^(Expr left, cst_t right) -> Expr
Logical xor between two expressions.

auto operator^(cst_t left, Expr right) -> Expr
Logical xor between two expressions.

auto operator%(Expr val, Expr mod) -> Expr
Unsigned modulo of two expressions.

auto operator%(Expr val, cst_t mod) -> Expr
Unsigned modulo of two expressions.

auto operator%(cst_t val, Expr mod) -> Expr
Unsigned modulo of two expressions.

auto operator<<(Expr val, Expr shift) -> Expr
Shift an expression to the left.

auto operator<<(Expr val, cst_t shift) -> Expr
Shift an expression to the left.

auto operator<<(cst_t val, Expr shift) -> Expr
Shift an expression to the left.

auto operator>>(Expr val, Expr shift) -> Expr
Shift an expression to the right.

auto operator>>(Expr val, cst_t shift) -> Expr
Shift an expression to the right.

auto operator>>(cst_t val, Expr shift) -> Expr
Shift an expression to the right.

auto sar(Expr arg, Expr shift) -> Expr
Arithmetic shift an expression to the right.

auto sar(Expr arg, cst_t shift) -> Expr
Arithmetic shift an expression to the right.

auto sar(cst_t arg, Expr shift) -> Expr
Arithmetic shift an expression to the right.

auto sdiv(Expr left, Expr right) -> Expr
Signed divide two expressions.

auto sdiv(Expr left, cst_t right) -> Expr
Signed divide two expressions.

auto sdiv(cst_t left, Expr right) -> Expr
Signed divide two expressions.

auto smod(Expr val, Expr mod) -> Expr
Signed modulo between two expressions.

auto smod(Expr val, cst_t mod) -> Expr
Signed modulo between two expressions.

auto smod(cst_t val, Expr mod) -> Expr
Signed modulo between two expressions.

auto mulh(Expr left, Expr right) -> Expr
Unsigned multiply two expressions (higher bits of result)

auto mulh(Expr left, cst_t right) -> Expr
Unsigned multiply two expressions (higher bits of result)

auto mulh(cst_t left, Expr right) -> Expr
Unsigned multiply two expressions (higher bits of result)

auto smull(Expr left, Expr right) -> Expr
Signed multiply two expressions (lower bits of result)

auto smull(Expr left, cst_t right) -> Expr
Signed multiply two expressions (lower bits of result)

auto smull(cst_t left, Expr right) -> Expr
Signed multiply two expressions (lower bits of result)

auto smulh(Expr left, Expr right) -> Expr
Signed multiply two expressions (higher bits of result)

auto smulh(Expr left, cst_t right) -> Expr
Signed multiply two expressions (higher bits of result)

auto smulh(cst_t left, Expr right) -> Expr
Signed multiply two expressions (higher bits of result)

auto operator~(Expr arg) -> Expr
Negate an expression.

auto operator-(Expr arg) -> Expr
Logical invert an expression.

auto operator<<(std::ostream& os, Expr e) -> std::ostream&
Print an expression in a stream.

auto NewDefaultExprSimplifier() -> std::shared_ptr<ExprSimplifier>
Instanciate a new expression simplifier that uses all of Maat's built-in simplifier functions.

auto es_constant_folding(Expr e) -> Expr
Constant folding simplifier function.

auto es_neutral_elements(Expr e) -> Expr
Neutral elements simplifier function.

auto es_absorbing_elements(Expr e) -> Expr
Absorbing elements simplifier function.

auto es_arithmetic_properties(Expr e) -> Expr
Arithmetic simplification function.

auto es_involution(Expr e) -> Expr
Involution simplifier function.

auto es_extract_patterns(Expr e) -> Expr
Simplifier function for 'Extract' expressions.

auto es_basic_transform(Expr e) -> Expr
simplifier function

auto es_logical_properties(Expr e) -> Expr
Logical properties simplifier function.

auto es_concat_patterns(Expr e) -> Expr
Simplifier function for 'Concat' expressions.

auto es_basic_ite(Expr e) -> Expr
Simplifier function on If-Then-Else expressions.

auto es_arithmetic_factorize(Expr e) -> Expr
Factorization simplifier function.

auto es_generic_factorize(Expr e) -> Expr
Generic factorization simplifier function.

auto es_deep_associative(Expr e, ExprSimplifier& simp) -> Expr
Simplifier for repeated associative operation.

Value()
Empty value.

Value(const Value& other) defaulted
Copy constructor.

Value(const Expr& expr)
Build value from abstract expression.

Value(const Number& number)
Build value from concrete number.

Value(size_t size, cst_t val)
Build value from concrete value.

auto operator=(const Value& other) -> Value& defaulted
Copy assignment.

auto operator=(Value&& other) -> Value& defaulted
Move assignment.

auto operator=(const Expr& e) -> Value&
Build Value from expression.

auto operator=(Expr&& e) -> Value&
Build Value from expression.

auto operator=(const Number& n) -> Value&
Build Value from number.

auto operator=(Number&& n) -> Value&
Build Value from number.

void set_cst(size_t size, cst_t val)
Build Value from constant and size in bits.

auto as_expr() const -> Expr
Return the value as an abstract expression.

auto as_int() const -> cst_t
Return the value as a concrete signed value.

auto as_uint() const -> ucst_t
Return the value as a concrete unsigned value.

auto as_float() const -> fcst_t
Return the value as a concrete floating point value.

auto as_int(const VarContext&) const -> cst_t
Return the value as a concrete signed value.

auto as_float(const VarContext&) const -> fcst_t
Return the value as a concrete unsigned value.

auto as_number() const -> const Number&
Return the value as a concrete number.

auto as_number(const VarContext&) const -> const Number&
Return the value as a concrete number.

auto class_uid() const -> uid_t virtual
Return the class uid (see ClassId enum)

void dump(serial::Serializer&) const virtual
Dump the object contents in a serializer stream.

void load(serial::Deserializer&) virtual
Restore an object from a deserializer stream.

auto operator+(const Value& left, const Value& right) -> Value
Add two values.

auto operator+(const Value& left, cst_t right) -> Value
Add two values.

auto operator+(cst_t left, const Value& right) -> Value
Add two values.

auto operator-(const Value& left, const Value& right) -> Value
Subtract two values.

auto operator-(const Value& left, cst_t right) -> Value
Subtract two values.

auto operator-(cst_t left, const Value& right) -> Value
Subtract two values.

auto operator*(const Value& left, const Value& right) -> Value
Multiply two values.

auto operator*(const Value& left, cst_t right) -> Value
Multiply two values.

auto operator*(cst_t left, const Value& right) -> Value
Multiply two values.

auto operator/(const Value& left, const Value& right) -> Value
Unsigned divide two values.

auto operator/(const Value& left, cst_t right) -> Value
Unisgned divide two values.

auto operator/(cst_t left, const Value& right) -> Value
Unisigned divide two values.

auto operator&(const Value& left, const Value& right) -> Value
Logical AND between two values.

auto operator&(const Value& left, cst_t right) -> Value
Logical AND between two values.

auto operator&(cst_t left, const Value& right) -> Value
Logical AND between two values.

auto operator|(const Value& left, const Value& right) -> Value
Logical OR between two values.

auto operator|(const Value& left, cst_t right) -> Value
Logical OR between two values.

auto operator|(cst_t left, const Value& right) -> Value
Logical OR between two values.

auto operator^(const Value& left, const Value& right) -> Value
Logical XOR between two values.

auto operator^(const Value& left, cst_t right) -> Value
Logical XOR between two values.

auto operator^(cst_t left, const Value& right) -> Value
Logical XOR between two values.

auto operator%(const Value& left, const Value& right) -> Value
Unsigned modulo.

auto operator%(const Value& left, cst_t right) -> Value
Unsigned modulo.

auto operator%(cst_t left, const Value& right) -> Value
Unsigned modulo.

auto operator>>(const Value& left, const Value& right) -> Value
Logical shift right.

auto operator>>(const Value& left, cst_t right) -> Value
Logical shift right.

auto operator>>(cst_t left, const Value& right) -> Value
Logical shift right.

auto operator<<(const Value& left, const Value& right) -> Value
Logical shift left.

auto operator<<(const Value& left, cst_t right) -> Value
Logical shift left.

auto operator<<(cst_t left, const Value& right) -> Value
Logical shift left.

auto sar(const Value& arg, const Value& shift) -> Value
Arithmetic shift right.

auto sar(const Value& arg, cst_t shift) -> Value
Arithmetic shift right.

auto sar(cst_t arg, const Value& shift) -> Value
Arithmetic shift right.

auto sdiv(const Value& left, const Value& right) -> Value
Signed divide two values.

auto sdiv(const Value& left, cst_t right) -> Value
Signed divide two values.

auto sdiv(cst_t left, const Value& right) -> Value
Signed divide two values.

auto smod(const Value& val, const Value& mod) -> Value
Signed modulo.

auto smod(const Value& val, cst_t mod) -> Value
Signed modulo.

auto smod(cst_t val, const Value& mod) -> Value
Signed modulo.

auto operator~(const Value& arg) -> Value
Negate an expression.

auto operator-(const Value& arg) -> Value
Logical invert an expression.

auto extract(const Value& arg, unsigned long higher, unsigned long lower) -> Value
Extract bitfield from value.

auto concat(const Value& upper, const Value& lower) -> Value
Concatenate two values.

auto operator==(const Value& left, const Value& right) -> Constraint
Equality constraint.

auto operator==(const Value& left, cst_t right) -> Constraint
Equality constraint.

auto operator==(cst_t left, const Value& right) -> Constraint
Equality constraint.

auto operator!=(const Value& left, const Value& right) -> Constraint
Not-equal constraint.

auto operator!=(const Value& left, cst_t right) -> Constraint
Not-equal constraint.

auto operator!=(cst_t left, const Value& right) -> Constraint
Not-equal constraint.

auto operator<(const Value& left, const Value& right) -> Constraint
Less-than constraint.

auto operator<(const Value& left, cst_t right) -> Constraint
Less-than constraint.

auto operator<(cst_t left, const Value& right) -> Constraint
Less-than constraint.

auto operator<=(const Value& left, const Value& right) -> Constraint
Less-or-equal constraint.

auto operator<=(const Value& left, cst_t right) -> Constraint
Less-or-equal constraint.

auto operator<=(cst_t left, const Value& right) -> Constraint
Less-or-equal constraint.

auto operator>(const Value& left, const Value& right) -> Constraint
Greater-than constraint.

auto operator>(const Value& left, cst_t right) -> Constraint
Greater-than constraint.

auto operator>(cst_t left, const Value& right) -> Constraint
Greater-than constraint.

auto operator>=(const Value& left, const Value& right) -> Constraint
Greater-or-equal constraint.

auto operator>=(const Value& left, cst_t right) -> Constraint
Greater-or-equal constraint.

auto operator>=(cst_t left, const Value& right) -> Constraint
Greater-or-equal constraint.

auto operator<<(std::ostream& os, const VarContext& c) -> std::ostream&

❱   Variables

static const uint64_t default_expr_taint_mask

❱   Enum documentation

enum class ExprType

Different types of abstract expressions.

Enumerators
VAR

Symbolic variable.

MEM

Result of a memory read.

EXTRACT

Bitfield extract.

CONCAT

Concatenation of two expressions.

UNOP

Unary arithmetic/logical operation.

BINOP

Binary arithmetic/logical operation.

ITE

If-Then-Else expression.

CST

Constant value.

NONE

enum class ITECond: uint8_t

The conditions for ITE expressions

Enumerators
EQ

Equal.

LT

Unsigned Lesser Than.

LE

Unsigned Lesser or Equal.

SLT

Signed Lesser Than.

SLE

Signed Lesser or Equal.

FEQ

Equal (float)

FLT

Lesser Than (float)

FLE

Lesser or Equal (float)

enum class Op: uint8_t

Types of operations that can be applied on expressions

Enumerators
ADD

Addition.

MUL

Unsigned multiply (lower half)

MULH

Unsigned multiply (higher half)

SMULL

Signed multiply (lower half)

SMULH

Signed multiply (higher half)

DIV

Unsigned divide.

SDIV

Signed divide.

NEG

Unary negation.

AND

Logical AND.

OR

Logical OR.

XOR

Logical XOR.

SHL

Logical shift left.

SHR

Logical shift right.

SAR

Arithmetic shift right.

MOD

Unsigned modulo.

SMOD

Signed modulo.

NOT

Unary logical NOT.

NONE

enum class ExprStatus: uint8_t

Symbolic status of an expression

Enumerators
CONCRETE

Concrete expression (no symbolic variables)

SYMBOLIC

Symbolic expression (contains fully symbolic variables)

CONCOLIC

Concolic expression (contains symbolic variables that have a contextual concrete value)

NOT_COMPUTED

Status was not yet computed.

enum class Taint: uint8_t

Taint of an expression

Enumerators
NOT_TAINTED

No bit is tainted.

TAINTED

At least one bit is tainted.

NOT_COMPUTED

Taint was not yet computed.

❱   Typedef documentation

typedef std::shared_ptr<ExprObject> Expr

Shared pointer to an ExprObject instance. Expressions should be manipulated only through Expr instances, the base class ExprObject and its child classes should never be used directly. Using Expr enables to seemlessly create and manipulate abstract expressions without worrying about their scope and lifetime.

typedef Expr(*ExprSimplifierFunc)(Expr)

A function that takes an expression and returns a simplified expression

❱   Function documentation

fcst_t as_float(const VarContext&) const

Return the value as a concrete unsigned value.

Return the value as a concrete floating point value

std::ostream& operator<<(std::ostream& os, const VarContext& c)

Print the context to a stream

❱   Variable documentation

static const uint64_t default_expr_taint_mask

Default mask to use when tainting expressions (all bits are tainted)