Grammar

Oracles contain pre-computed expression on a given grammar. A grammar is composed of variables, and operators (unary/binary) that can be applied on these variables. An oracle object is instanciated with such grammar class and an input vector.

class qsynthesis.grammar.grammar.TritonGrammar(vars: List[Tuple[qsynthesis.types.Char, qsynthesis.types.BitSize]], ops: List[BvOp])

Triton Grammar class. It represent a set of operators, and variables of a given size (only 64 bits at the moment).

Constructor taking a set of variables (name and size) and a set of operators.

Parameters

• vars (List[Tuple[qsynthesis.types.Char, qsynthesis.types.BitSize]]) – list of tuple of (name ,size)

• ops (List[BvOp]) – list of BvOp representing operators

static from_dict(g_dict: Dict) → TritonGrammar

Static method instanciating a TritonGrammar from its representation as a dictionnary.

Parameters

g_dict – dictionarry representation of the grammar

Returns

TritonGrammar object

gen_test_inputs(n: int) → List[qsynthesis.types.Input]

Generate a list of n input. Thus it generate a random valuation for each variables of the grammar and that n times.

Parameters

n (int) – Number of Input to generate (size of the list)

Returns

list of inputs

Return type

List[qsynthesis.types.Input]

property non_terminal_operators: List[Operator]

Return the list of non-terminal operators. All unary and binary operators are non terminal as they can be derived.

Returns

list of operators namedtuples

str_to_expr(s: str, *args) → TritonAst

Convert a string in the format of the grammar into a TritonAst. In practice an args[0] should be a TritonAst from which to spawn a new TritonAst. That is required to get the same mapping of normalized variables than the one used by expr.

Parameters

s – expression string to convert to TritonAst

Returns

the TritonAst representing the expressions string

Raises

NameError, TypeError

to_dict() → Dict

Return a dictionnary representation of the grammar. This is used for serialization in database etc.

Oracles

QSynthesis support any types of oracles as long as they implement InputOutputOracle base class which interface is given below. At the moment two children classes implement this interface:

• InputOutputOracleLevelDB: Main table object where entries are stored in a key-value database made by called Level-DB made by Google, that guarantee logarithmic read in database.

• InputOutputOracleREST: Class interfacing a InputOutputOracleLevelDB being served on a REST API (cf. Oracle REST server). This table avoids having a whole table locally.

class qsynthesis.tables.base.InputOutputOracle(gr: TritonGrammar, inputs: List[qsynthesis.types.Input], hash_mode: HashType = HashType.RAW, f_name: Union[Path, str] = '')

Base Lookup table class. Specify the interface that child class have to implement to be interoperable with other the synthesizer.

Constructor making a I/O oracle from a grammar a set of inputs and an hash type.

Parameters

• gr – triton grammar

• inputs – List of inputs

• hash_mode – type of hash to be used as keys in tables

• f_name – file name of the table (when being loaded)

add_entries(worklist: List[Tuple[qsynthesis.types.Hash, str]], calc_hash: bool = False) → None

Add the given list of entries in the database. The boolean calc_hash indicates whether hashes are already computed or not. If false the function should hash the hash first.

Parameters

• worklist (List[Tuple[qsynthesis.types.Hash, str]]) – list of entries to add

• calc_hash – whether or not hash should be performed on entries keys

Returns

None

add_entry(hash: qsynthesis.types.Hash, value: str) → None

Abstract function to add an entry in the lookuptable.

Parameters

• hash – already computed hash to add

• value (str) – expression value to add in the table

property bitsize: qsynthesis.types.BitSize

Size of expression in bit

Return type

qsynthesis.types.BitSize

static create(filename: Union[str, Path], grammar: TritonGrammar, inputs: List[qsynthesis.types.Input], hash_mode: HashType = HashType.RAW, constants: List[int] = []) → InputOutputOracle

Create a new empty lookup table with the given initial parameters, grammars, inputs and hash_mode.

Parameters

• filename – filename of the table to create

• grammar – TritonGrammar object representing variables and operators

• inputs (List[qsynthesis.types.Input]) – list of inputs on which to perform evaluation

• hash_mode – Hashing mode for keys

• constants – list of constants used

Returns

lookuptable instance object

generate(bitsize: int, constants: List[int] = [], do_watch: bool = False, watchdog_threshold: Union[int, float] = 90, linearize: bool = False, do_use_blacklist: bool = False, limit: int = 0) → None

Generate a new lookup table from scratch with the variables and operators set in the constructor of the table.

Parameters

• bitsize – Bitsize of expressions to generate

• constants – List of constants to use in the generation

• do_watch – Enable RAM watching thread to monitor memory

• watchdog_threshold – threshold to be sent to the memory watchdog

• linearize – whether or not to apply linearization on expressions

• do_use_blacklist – enable blacklist mechanism on commutative operators. Slower but less memory consuming

• limit – Maximum number of entries to generate

Returns

None

hash(outs: List[qsynthesis.types.Output]) → qsynthesis.types.Hash

Main hashing method that dispatch the outputs to the appropriate hashing function depending on the hash_mode of the table.

Parameters

outs (List[qsynthesis.types.Output]) – list of outputs to hash

Returns

Hash type (bytes, int ..) of the outputs

Return type

qsynthesis.types.Hash

property input_number: int

Number of inputs used in this table

Return type

int

is_expr_compatible(expr: TritonAst) → bool

Check the compatibility of the given expression with the table. The function checks sizes of expr variables against the one of its own grammar.

Parameters

expr – TritonAst expression to check

Returns

True if the table can decide on this expression

property is_writable: bool

Whether the table enable being written (with new expressions)

Return type

bool

static load(file: Union[Path, str]) → InputOutputOracle

Load the given lookup table and returns an instance object.

Parameters

file – Database file to load

Returns

InputOutputOracle object

lookup(outputs: List[qsynthesis.types.Output], *args, use_cache: bool = True) → Optional[TritonAst]

Perform a lookup in the table with a given set of outputs corresponding to the evaluation of an AST against the Input of this exact same table. If an entry is found a TritonAst is created and returned.

Parameters

• outputs – list of output result of evaluating an ast against the inputs of this table

• args – args forwarded to grammar and ultimately to the tritonAst in charge of building a new TritonAst

• use_cache – Boolean enabling caching the the hash of outputs. A second call if the same outputs (which is common) will not trigger a lookup in the database

Type

List[qsynthesis.types.Output]

Returns

optional TritonAst corresponding of the expression found in the table

lookup_hash(h: qsynthesis.types.Hash) → Optional[str]

Raw lookup for a given key in database.

Parameters

h (qsynthesis.types.Hash) – hash key to look for in database

Returns

string of the expression if found

Return type

Optional[str]

property name: str

Name of the table

Return type

str

property operator_number: int

Number of operators used in this table

Return type

int

property size: int

Size of the table (number of entries)

Return type

int

property var_number: int

Maximum number of variables contained in the table

Return type

int