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:

ctx (TritonContext) – Triton context
node (qsynthesis.types.AstNode) – Triton AstNode to wrap
node_c (int) – Number of nodes contained in the expression
depth (int) – Depth of the expression (depth of the AST)
vars (Dict[str, qsynthesis.types.SymbolicVariable]) – Variables contained in this expression
children (List[TritonAst]) – List of children as TritonAst instances

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: str | None = 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.