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 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)