Expressions module

Creating and manipulating abstract expressions.

Reference
- Classes
- Enums
- Typedefs
- Functions
- Variables

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)