pyecsca.sca.re.tree module¶

Tools for working with distinguishing maps and trees.

        ________
    ,o88~~88888888o,
  ,~~?8P  88888     8,
 d  d88 d88 d8_88     b
d  d888888888          b
8,?88888888  d8.b o.   8
8~88888888~ ~^8888  db 8
?  888888          ,888P
 ?  `8888b,_      d888P
  `   8888888b   ,888'
    ~-?8888888 _.P-~
        ~~~~~~

Here we grow the trees.

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⠀⢿⢢⡀⠸⣱⡀⢀⢤⡶⡄⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⢰⣤⡴⣴⠢⣧⣿⢤⣈⠺⡧⣺⠷⡟⠓⠃⣇⢧⣶⣀⠀⠀⠀⠀⠀⠀
⠀⢀⡀⢠⠽⣇⣹⠓⠽⡌⠓⠹⢶⢿⠀⢠⠁⡈⡶⠓⠋⠙⢻⡹⢓⡶⠀⠀⠀
⠀⣬⣿⡎⠓⠒⠻⢄⡀⢳⡀⠀⢸⠈⢦⢸⠀⣸⢇⠀⢀⣠⡞⢉⣡⣴⣲⠄⠀
⢠⣽⣈⣇⣴⣲⠖⠀⠉⠚⠳⣄⢸⠀⠈⣿⠊⡼⡦⢏⠉⠀⠉⢙⠮⢱⡆⠀⠀
⠘⢎⡇⠘⢧⡀⣀⣤⣤⠄⠀⠈⢻⣇⢀⣽⠖⢣⣣⡤⠤⠒⠚⣝⣆⠀⠀⠀⠀
⠀⠀⠓⠢⠤⠽⢧⣀⠀⠀⠀⠀⠀⣿⠏⢹⡴⠋⠙⠒⠶⢖⢤⡀⢀⣤⣶⠗⠀
⡢⢄⠐⠮⠷⢆⠀⠈⠙⠛⠛⠻⢶⣿⠀⣾⢀⣀⣀⣤⠤⡼⡓⢋⣿⠫⢕⡆⠀
⠈⣻⠧⠤⠤⠤⠿⠗⠒⠒⠛⠶⣤⣿⣼⠛⠉⠙⠒⣶⡖⠳⡗⠺⡿⣤⣤⢄⡀
⠰⣹⠀⠀⠀⢟⡆⠀⠀⠀⠀⠀⠈⣿⡿⠀⠀⠀⠀⢧⠇⠀⠀⠀⠀⠙⠮⡯⠀
⠀⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣤⠾⠛⣿⠙⠛⠶⢦⠄⠀⠀⠀⠀⠀⠀⠀⠀⠀

class Map(mapping, cfg_map, domain, codomain)[source]¶

Bases: object

A distinguishing map.

                      domain
                      ======
                     ┌───┬───┬───┬───┬───┬───┐
                     │P1 │P2 │P3 │P4 │P5 │P5 │
                     └───┴───┴───┴───┴───┴───┘
                       :   :   :   :   :   :
                       :   :   :   :   :   :
                       :   :   :   :   :   :
                       :   :   :   :   :   :
 cfg_map     mapping ┌───┬───┬───┬───┬───┬───┐   codomain
 =======     ======= │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │   ========
┌────┬───┐       ┌───┼───┼───┼───┼───┼───┼───┤
│cfg1│  0│:::::::│  0│ T │ F │ T │ F │ T │ T │   {T, F}
├────┼───┤       ├───┼───┼───┼───┼───┼───┼───┤
│cfg2│  1│:::::::│  1│ F │ F │ F │ F │ T │ T │
├────┼───┤       ├───┼───┼───┼───┼───┼───┼───┤
│cfg3│  2│:::::::│  2│ T │ T │ F │ F │ T │ T │
└────┴───┘       └───┴───┴───┴───┴───┴───┴───┘

mapping: DataFrame[source]¶

A dataframe containing the map outputs.

Both the columns and the index are simply numeric. The columns are the domain. The items in the rows are from the codomain. The index may have gaps. To map it back into the set of configs for each unique row, see the cfg_map.

cfg_map: DataFrame[source]¶: A dataframe containing the map from the cfgs to the index (integers).

domain: List[Any][source]¶: The (ordered) domain of the mapping.

codomain: Set[Any][source]¶: The (unordered) codomain of the mapping.

classmethod from_sets(cfgs, mapping, deduplicate=False)[source]¶

Build a distinguishing map with binary outputs from a set of configs and a mapping.

Given configs {a, b, c} and a mapping of {a: {1}, b: {1, 2}, c: {2}}, this will build a distinguishing map with the following structure:

                      domain
                      ======
                     ┌───┬───┐
                     │ 1 │ 2 │
                     └───┴───┘
                       :   :
                       :   :
                       :   :
                       :   :
 cfg_map     mapping ┌───┬───┐   codomain
 =======     ======= │ 0 │ 1 │   ========
┌────┬───┐       ┌───┼───┼───┤
│ a  │  0│:::::::│  0│ T │ F │   {T, F}
├────┼───┤       ├───┼───┼───┤
│ b  │  1│:::::::│  1│ T │ T │
├────┼───┤       ├───┼───┼───┤
│ c  │  2│:::::::│  2│ F │ T │
└────┴───┘       └───┴───┴───┘

Parameters:

cfgs¶ (Set[Any]) – The set of configs.
mapping¶ (Mapping[Any, Set[Any]]) – The mapping from configs to a subset of inputs for which the oracle returns True.
deduplicate¶ (bool) – Whether to deduplicate the rows of the map.

Returns:

The distinguishing map.

classmethod from_io_maps(cfgs, mapping)[source]¶

Build a distinguishing map with arbitrary outputs from a set of configs and a mapping that gives the oracle responses for each config and input.

Given configs {a, b, c} and a mapping of {a: {x: 1, y: 2}, b: {x: 2, y: 1}, c: {x: 1}}, this will build a distinguishing map with the following structure:

                      domain
                      ======
                     ┌───┬───┐
                     │ x │ y │
                     └───┴───┘
                       :   :
                       :   :
                       :   :
                       :   :
 cfg_map     mapping ┌───┬───┐   codomain
 =======     ======= │ 0 │ 1 │   ========
┌────┬───┐       ┌───┼───┼───┤
│ a  │  0│:::::::│  0│ 1 │ 2 │   {1, 2}
├────┼───┤       ├───┼───┼───┤
│ b  │  1│:::::::│  1│ 2 │ 1 │
├────┼───┤       ├───┼───┼───┤
│ c  │  2│:::::::│  2│ 1 │ - │
└────┴───┘       └───┴───┴───┘

Parameters:

cfgs¶ (Set[Any]) – The set of configs.
mapping¶ (Mapping[Any, Mapping[Any, Any]]) – The mapping from configs to a mapping from inputs to outputs.

Returns:

The distinguishing map.

property cfgs: Set[Any][source]¶: The set of configs in this distinguishing map.

deduplicate()[source]¶: Deduplicate the configs of this distinguishing map based on the rows.

merge(other)[source]¶

Merge in another distinguishing map operating on different configs.

Parameters:: other¶ (Map) – The other distinguishing map.

describe()[source]¶

Describe some important properties of the distinguishing map.

Return type:: str
Returns:: A string with the description.

class Node(cfgs, dmap_index=None, dmap_input=None, response=None, parent=None, children=None)[source]¶

Bases: NodeMixin

A node in a distinguishing tree.

cfgs: Set[Any][source]¶: Set of configs associated with this node.

dmap_index: Optional[int][source]¶: The dmap index to be used for the oracle call for this node.

dmap_input: Optional[Any][source]¶: The input for the oracle call for this node (is from dmap at dmap_index in the Tree).

response: Optional[Any][source]¶: The response to the previous oracle call that resulted in this node.

property parent[source]¶

Parent Node.

On set, the node is detached from any previous parent node and attached to the new node.

>>> from anytree import Node, RenderTree
>>> udo = Node("Udo")
>>> marc = Node("Marc")
>>> lian = Node("Lian", parent=marc)
>>> print(RenderTree(udo))
Node('/Udo')
>>> print(RenderTree(marc))
Node('/Marc')
└── Node('/Marc/Lian')

Attach

>>> marc.parent = udo
>>> print(RenderTree(udo))
Node('/Udo')
└── Node('/Udo/Marc')
    └── Node('/Udo/Marc/Lian')

Detach

To make a node to a root node, just set this attribute to None.

>>> marc.is_root
False
>>> marc.parent = None
>>> marc.is_root
True

property children[source]¶

All child nodes.

>>> from anytree import Node
>>> n = Node("n")
>>> a = Node("a", parent=n)
>>> b = Node("b", parent=n)
>>> c = Node("c", parent=n)
>>> n.children
(Node('/n/a'), Node('/n/b'), Node('/n/c'))

Modifying the children attribute modifies the tree.

Detach

The children attribute can be updated by setting to an iterable.

>>> n.children = [a, b]
>>> n.children
(Node('/n/a'), Node('/n/b'))

Node c is removed from the tree. In case of an existing reference, the node c does not vanish and is the root of its own tree.

>>> c
Node('/c')

Attach

>>> d = Node("d")
>>> d
Node('/d')
>>> n.children = [a, b, d]
>>> n.children
(Node('/n/a'), Node('/n/b'), Node('/n/d'))
>>> d
Node('/n/d')

Duplicate

A node can just be the children once. Duplicates cause a TreeError:

>>> n.children = [a, b, d, a]
Traceback (most recent call last):
    ...
anytree.node.exceptions.TreeError: Cannot add node Node('/n/a') multiple times as child.

property ancestors[source]¶

All parent nodes and their parent nodes.

>>> from anytree import Node
>>> udo = Node("Udo")
>>> marc = Node("Marc", parent=udo)
>>> lian = Node("Lian", parent=marc)
>>> udo.ancestors
()
>>> marc.ancestors
(Node('/Udo'),)
>>> lian.ancestors
(Node('/Udo'), Node('/Udo/Marc'))

property anchestors[source]¶

All parent nodes and their parent nodes - see ancestors.

The attribute anchestors is just a typo of ancestors. Please use ancestors. This attribute will be removed in the 3.0.0 release.

property depth[source]¶

Number of edges to the root Node.

>>> from anytree import Node
>>> udo = Node("Udo")
>>> marc = Node("Marc", parent=udo)
>>> lian = Node("Lian", parent=marc)
>>> udo.depth
0
>>> marc.depth
1
>>> lian.depth
2

property descendants[source]¶

All child nodes and all their child nodes.

>>> from anytree import Node
>>> udo = Node("Udo")
>>> marc = Node("Marc", parent=udo)
>>> lian = Node("Lian", parent=marc)
>>> loui = Node("Loui", parent=marc)
>>> soe = Node("Soe", parent=lian)
>>> udo.descendants
(Node('/Udo/Marc'), Node('/Udo/Marc/Lian'), Node('/Udo/Marc/Lian/Soe'), Node('/Udo/Marc/Loui'))
>>> marc.descendants
(Node('/Udo/Marc/Lian'), Node('/Udo/Marc/Lian/Soe'), Node('/Udo/Marc/Loui'))
>>> lian.descendants
(Node('/Udo/Marc/Lian/Soe'),)

property height[source]¶

Number of edges on the longest path to a leaf Node.

>>> from anytree import Node
>>> udo = Node("Udo")
>>> marc = Node("Marc", parent=udo)
>>> lian = Node("Lian", parent=marc)
>>> udo.height
2
>>> marc.height
1
>>> lian.height
0

property is_leaf[source]¶

Node has no children (External Node).

>>> from anytree import Node
>>> udo = Node("Udo")
>>> marc = Node("Marc", parent=udo)
>>> lian = Node("Lian", parent=marc)
>>> udo.is_leaf
False
>>> marc.is_leaf
False
>>> lian.is_leaf
True

property is_root[source]¶

Node is tree root.

>>> from anytree import Node
>>> udo = Node("Udo")
>>> marc = Node("Marc", parent=udo)
>>> lian = Node("Lian", parent=marc)
>>> udo.is_root
True
>>> marc.is_root
False
>>> lian.is_root
False

iter_path_reverse()[source]¶

Iterate up the tree from the current node to the root node.

>>> from anytree import Node
>>> udo = Node("Udo")
>>> marc = Node("Marc", parent=udo)
>>> lian = Node("Lian", parent=marc)
>>> for node in udo.iter_path_reverse():
...     print(node)
Node('/Udo')
>>> for node in marc.iter_path_reverse():
...     print(node)
Node('/Udo/Marc')
Node('/Udo')
>>> for node in lian.iter_path_reverse():
...     print(node)
Node('/Udo/Marc/Lian')
Node('/Udo/Marc')
Node('/Udo')

property leaves[source]¶

Tuple of all leaf nodes.

>>> from anytree import Node
>>> udo = Node("Udo")
>>> marc = Node("Marc", parent=udo)
>>> lian = Node("Lian", parent=marc)
>>> loui = Node("Loui", parent=marc)
>>> lazy = Node("Lazy", parent=marc)
>>> udo.leaves
(Node('/Udo/Marc/Lian'), Node('/Udo/Marc/Loui'), Node('/Udo/Marc/Lazy'))
>>> marc.leaves
(Node('/Udo/Marc/Lian'), Node('/Udo/Marc/Loui'), Node('/Udo/Marc/Lazy'))

property path[source]¶

Path from root node down to this Node.

>>> from anytree import Node
>>> udo = Node("Udo")
>>> marc = Node("Marc", parent=udo)
>>> lian = Node("Lian", parent=marc)
>>> udo.path
(Node('/Udo'),)
>>> marc.path
(Node('/Udo'), Node('/Udo/Marc'))
>>> lian.path
(Node('/Udo'), Node('/Udo/Marc'), Node('/Udo/Marc/Lian'))

property root[source]¶

Tree Root Node.

>>> from anytree import Node
>>> udo = Node("Udo")
>>> marc = Node("Marc", parent=udo)
>>> lian = Node("Lian", parent=marc)
>>> udo.root
Node('/Udo')
>>> marc.root
Node('/Udo')
>>> lian.root
Node('/Udo')

separator = '/'[source]¶

property siblings[source]¶

Tuple of nodes with the same parent.

>>> from anytree import Node
>>> udo = Node("Udo")
>>> marc = Node("Marc", parent=udo)
>>> lian = Node("Lian", parent=marc)
>>> loui = Node("Loui", parent=marc)
>>> lazy = Node("Lazy", parent=marc)
>>> udo.siblings
()
>>> marc.siblings
()
>>> lian.siblings
(Node('/Udo/Marc/Loui'), Node('/Udo/Marc/Lazy'))
>>> loui.siblings
(Node('/Udo/Marc/Lian'), Node('/Udo/Marc/Lazy'))

property size[source]¶

Tree size — the number of nodes in tree starting at this node.

>>> from anytree import Node
>>> udo = Node("Udo")
>>> marc = Node("Marc", parent=udo)
>>> lian = Node("Lian", parent=marc)
>>> loui = Node("Loui", parent=marc)
>>> soe = Node("Soe", parent=lian)
>>> udo.size
5
>>> marc.size
4
>>> lian.size
2
>>> loui.size
1

class SplitCriterion[source]¶

Bases: object

A splitting criterion to be used in tree building.

is_better(score, current_best)[source]¶

Whether the score is better than the current best.

Return type:: bool

is_optimal(score, n_cfgs, n_codomain)[source]¶

Whether the score is optimal and no further splits need to be examined.

Return type:: bool

class Tree(root, *maps)[source]¶

Bases: object

A distinguishing tree.

maps: List[Map][source]¶: A list of dmaps. Nodes index into this when choosing which oracle to use.

root: Node[source]¶: A root of the tree.

property leaves: Tuple[Node][source]¶: Get the leaves of the tree as a tuple.

property height: int[source]¶: Get the height of the tree (distance from the root to the deepest leaf).

property size: int[source]¶: Get the size of the tree (number of nodes).

property precise: bool[source]¶: Whether the tree is precise (all leaves have only a single configuration).

render()[source]¶

Render the tree.

Return type:: str
Returns:: A string with the tree.

render_basic()[source]¶

Render the tree in a basic form, with number of configs as nodes.

Return type:: str
Returns:: A string with the tree.

describe()[source]¶

Describe some important properties of the tree.

Return type:: str
Returns:: A string with the description.

expand(dmap)[source]¶

Expand a tree with a new distinguishing map.

Parameters:: dmap¶ (Map) – The distinguishing map to expand the tree with.
Return type:: Tree

classmethod build(cfgs, *maps, split='largest')[source]¶

Build a tree.

Parameters:

cfgs¶ (Set[Any]) – The set of configs to build the tree for.
maps¶ (Map) – The distinguishing maps to use.
split¶ (Union[str, SplitCriterion]) – The split criterion to use. Can be one of “degree”, “largest”, “average”.

Return type:

Tree

Returns:

The tree.

pyecsca

Navigation

Related Topics

pyecsca.sca.re.tree module¶