TritonAst

TritonAst is a class wrapper around Triton AstNode objects on top of which it provides many utility functions.

class qsynthesis.tritonast.TritonAst(ctx: TritonContext, node: AstNode, node_c: int, depth: int, vars: Dict[str, SymbolicVariable], children: List[TritonAst])[source]

Wrapping class on top of Triton AstNode objects. This is the main entity manipulated throughout the synthesis process. It provides many utility fonctions on these ASTs like TritonAst.node_count holding the number of node of the AST, or TritonAst.reassembly() that allows reassembling the AST into assembly.

Instanciate a TritonAst with some precomputed fields given in parameters.

Parameters

Warning

This class is not meant to be instanciated directly. It must be instanciated trough the make_ast() method.

compare_behavior(ast: TritonAst, inps: List[qsynthesis.types.Input]) int[source]

Compare the current expression with the one given in parameter wrt theirs behavior on the given set of inputs. The comparison returns -1 if not applicable (as involving different variables, 0 if different and 1 if equal.

Parameters
  • ast – other ast to compare against

  • inps – Set of inputs to use for evaluation

Returns

-1 if not applicable, 0 if different and 1 if equal

Return type

int

property depth: int

Pre-computed depth of the AST (complexity O(1))

Return type

int

duplicate() TritonAst[source]

Create a new distinct instance of TritonAst

static dyn_depth(expr: AstNode) int[source]

Returns the effective depth of the node of the expression by iterating the AstNode object recursively. The complexity is O(N) with N the depth of the AST.

Parameters

expr (qsynthesis.types.AstNode) – AstNode to iterate

Returns

AST depth

static dyn_node_count(expr: AstNode) int[source]

Returns the effective count of node of the expression by iterating the AstNode object recursively. The complexity is O(N) with N the number of node.

Parameters

expr (qsynthesis.types.AstNode) – AstNode to iterate

Returns

Number of nodes in the AST.

Note

The way of counting nodes is different from the number of nodes of Triton for which bitvector values are composed of 3 nodes. We count them as one.

eval_oracle(inp: qsynthesis.types.Input) qsynthesis.types.Output[source]

Oracle corresponding to the wrapped AST. It takes a valuation for all its symbolic variables and as an oracle returns the associated output.

Parameters

inp (qsynthesis.types.Input) – a mapping of variable to a given input value which will be used as concrete values for the symbolic variables in the wrapped AST

Returns

The result computed by means of evaluating the AST

Return type

qsynthesis.types.Output

static from_z3(ctx: TritonContext, expr: z3.z3.ExprRef) TritonAst[source]

Create a TritonAst out of a Z3 expressions

Parameters
  • ctx – Triton Context in which to create the expression

  • expr – Z3 expression

Returns

TritonAst

Warning

This function is mostly untested !

get_children() List[TritonAst][source]

Return the list of children TritonAst

has_children() bool[source]

True whether the object has children or not

property hash: int

Returns the Triton hash of the AstNode. This hash is meant to be unique for all AstNode, but is also meant to be similar to commutative expressions.

Return type

int

is_constant() bool[source]

Returns True if the type of the object is Bitvector (namely constant)

is_constant_expr() bool[source]

Returns whether the AST expression is constant or not (namely does not have any symbolic variables in it).

is_leaf() bool[source]

True if the AST has no children

is_root() bool[source]

Return True whether the object is a root node (namely does not have any parents).

is_semantically_equal(other: TritonAst) bool[source]

Allows checking if the current AST is semantically equal to the one provided.

Parameters

other – TritonAst on which to test against

Returns

bool – True if both ASTs are semantically equals

is_variable() bool[source]

Returns of the TritonAst is a variable node.

static make_ast(ctx: TritonContext, exp: AstNode) TritonAst[source]

Main staticmethod meant to create all TritonAst object. This method iterates all the given expression expr recursively to create TritonAst’s all the way down and pre-computing along the way the important fields like node_count, depth and symvars.

Parameters
  • ctx – Triton context on which to work on

  • exp – AstNode object to iterate

Returns

TritonAst instance wrapping the exp object

make_graph() Graph[source]

Generate a graph object representing the AST as a graph_tool object.

Warning

This method requires the graph_tool python library that can be installed by following https://git.skewed.de/count0/graph-tool/-/wikis/installation-instructions

property mapping: Dict[qsynthesis.types.Char, SymbolicVariable]

Mapping a placeholder character (‘a’, ‘b’, ‘c’ ..) to all the SymbolicVariable of the object.

Return type

Dict[qsynthesis.types.Char, SymbolicVariable]

mk_constant(v: int, size: int) TritonAst[source]

Create a new constant as a TritonAst (holding a Triton bv object).

mk_variable(alias: str, size: int) TritonAst[source]

Create a new variable node as a TritonAst (holding a Triton variable object). The variable is created in the TritonContext of the current object.

property node_count: int

Pre-computed O(1) count of the number of node contained in this AST.

Return type

int

normalized_str_to_ast(s: str) TritonAst[source]

Evaluate expression like “a + b - 1” creating a triton AST expression out of it. All variables have to be present in the AST.

Parameters

s – expression to evaluate

Returns

Triton AST node of the expression

Warning

the str expr must be obtained through the eval_oracle of the exact same TritonAst (otherwise names would be shuffled)

property parents: List[TritonAst]

Return the list of parents of a given AST. An AST is meant to have only ONE parent but Triton share common expression with multiple parents (wihtin the same expression)

Return type

List[TritonAst]

property pp_str: str

Hacky function that strips masks used in the AST_REPRESENTATION.PYTHON of Triton.

Return type

str

property ptr_id: int

Returns the hash of the AstNode object. This attribute is meant to differentiate to different python object have the exact same AST structure.

Return type

int

random_sampling(n: int) qsynthesis.types.IOVector[source]

Generates a random list of I/O samples pair.

Parameters

n – number of samples to generate

Returns

a list of n (inputs, output) tuples

Return type

qsynthesis.types.IOVector

reassemble(dst_reg: str, target_arch: Optional[str] = None) bytes[source]

Reassemble the TritonAst in assembly. dst_reg is the destination register of the result of the computation of the AST. Parameter target_arch is either a QtraceDB architecture object or the string identifier of the architecture as defined by the LLVM architecture triple: https://llvm.org/doxygen/classllvm_1_1Triple.html#a547abd13f7a3c063aa72c8192a868154 If no architecture is provided, use the same than the one that the AST.

Parameters
  • dst_reg – destination register as lowercase string

  • target_arch – target architecture in which to reassemble the AST

Returns

bytes of the AST reassembled in the given architecture

Raises

ReassemblyError

Warning

This method requires the arybo library that can be installed with (pip3 install arybo).

replace_self(repl: TritonAst, update_parents: bool = True) None[source]

Replace the current object by the given TritonAst. This function thus replace parents by replace the child that correspond to the current object by the replacement. :param repl: TritonAst used to replace the current object :param update_parents: whether to update parents or not

set_child(i: int, ast: TritonAst, update_node: bool = True, update_parents: bool = False) None[source]

Replace the ith child of the current TritonAst with new given ast object. Optional parameters indicates if inner fields of the object and its parent have to be updated.

Parameters
  • i – index of the child to replace

  • ast – TritonAst to be used as replacement of the child

  • update_node – whether to update internal field of the current node (node_count, depth, symvars)

  • update_parents – whether to update parents

property sub_map: Dict[qsynthesis.types.Char, AstNode]

Similar to mapping but map a placeholder character (‘a’, ‘b’, ‘c’ ..) to the AstNode counterpart of SymbolicVariables.

Return type

Dict[qsynthesis.types.Char, qsynthesis.types.AstNode]

property symbol: str

Returns the symbol of the current AstNode, operator if binary expression variable name if variable or constant value if constant.

Return type

str

static symvar_type(v: SymbolicVariable) SymVarType[source]

Static method returning the type of a given symbolic variable object

Parameters

v (qsynthesis.types.SymbolicVariable) – symbolic variable object

Returns

Type of the symbolic variables

Return type

qsynthesis.types.SymVarType

property symvars: List[SymbolicVariable]

Returns the list of SymbolicVariable object of the current object

Return type

List[qsynthesis.types.SymbolicVariable]

to_normalized_str() str[source]

Normalize the AST (replace variables by placeholder ‘a’, ‘b’ ..) and return it as a string.

to_z3() z3.z3.ExprRef[source]

Returns the Z3 expression associated with the Triton AST expression

property type: AstType

Returns the type of current AstNode object. The type is identical to the AST_NODE enum of Triton.

Return type

qsynthesis.types.AstType

update() None[source]

Update the current AST node, with information of its directly children. Information of children are thus considered genuine.

update_all() None[source]

Update all children recursively of the current object. Fields being updated are node_count, depth and symvars. This might be used when some of the AST has been rewritten. All pre-computed values are then ‘dirty’ and have to be updated.

update_parents(recursive: bool = True) None[source]

Update the parent of the current TritonAst. recursive indicates if it has to be performed recrusively. If so the complexity of the operation O(depth). :param recursive: whether to apply it recursively on parents

property var_num: int

Returns the number of different symbolic variables of the expression

Return type

int

property variable_id: int

Get the Triton unique id for a variable.

Raises

KeyError

visit_expr() Generator[TritonAst, None, None][source]

Pre-Order visit of all the sub-AstNode

visit_replacement(update: bool = True) Generator[TritonAst, TritonAst, None][source]

Triton AST expression replacement visitor in a Top-Down manner. It yields every sub-expression and replace it with the expression received throught the send mechanism.

Parameters

update – whether to update each node after having been replaced

Returns

generator of TritonAst, which for each AST yielded wait to receive either None meaning the it should not be replaced or a new TritonAst to be put in replacement.