How to parse one STIX pattern to generate multi-patterns for OR logic?

user_1498924 0
Viewed 92

I have a STIX pattern as below:

stix_ptn_and_or_case2 = '''[(x:x.x = 'A' OR x:x.x = 'B' ) AND ( x:x.x = 'C' OR x:x.x = 'D' )]'''

The pattern's logic is (A OR B) AND (C OR D)

The pattern can be parsed to an expression tree by dendrol (python lib) as below

enter image description here

The logic of (A OR B) AND (C OR D) can be separated to 4 small and AND only logic below

  • A AND C
  • A AND D
  • B AND C
  • B AND D

I want to parse the expression tree to get the 4 AND only logic

enter image description here

So I written the python code as below. The python lib dendrol can convert STIX pattern to expression tree.

import os, sys, datetime, copy
from dendrol import Pattern

stix_ptn_and_or_case2 = '''[(x:x.x = 'A' OR x:x.x = 'B' ) AND ( x:x.x = 'C' OR x:x.x = 'D' )]'''

ptn = Pattern(stix_ptn_and_or_case2)
pdt = ptn.to_dict_tree()
obj = pdt['pattern']
all_ptn_element_list = []

# the recursion function for expression tree to and-only logic
def ptnct(obj, ptn_element_list):
    if('observation' in obj or 'expression' in obj):
        if('observation' in obj):
            join = obj['observation']['join']
            expressions  = obj['observation']['expressions']
        else:
            join = obj['expression']['join']
            expressions  = obj['expression']['expressions']
        if(join=='AND' or join==None):
            for exp in expressions:
                p = ptnct(exp, ptn_element_list)
                if(p!=None):
                    ptn_element_list.append(p)
            if(len(ptn_element_list)==len(expressions)):# all and 
                all_ptn_element_list.append(ptn_element_list)
        elif(join=='OR'):
            for exp in expressions:
                p = ptnct(exp, ptn_element_list)
                tmp = copy.deepcopy( ptn_element_list )
                tmp.append(p)
                all_ptn_element_list.append(tmp)                    

    elif('comparison' in obj):
        exp = obj
        tag = '{0}:{1}.{2}'.format(exp['comparison']['object'], exp['comparison']['path'][0], exp['comparison']['path'][1])
        value = exp['comparison']['value']
        return value

x=ptnct(obj, [])
print(all_ptn_element_list)

The output of the code is 

[[u'A'], [u'B'], [u'C'], [u'D']]

But the desired output is 

[[u'A', u'C'], [u'A', u'D'], [u'B', u'C'], [u'B', u'D']]

Actually the code works for most of the cases, but not this one.

Any suggestion for parsing an AND-OR logic expression tree to AND-only expressions(patterns)?

data-structures python
1 Answers

Using the ever-handy itertools.product and itertools.chain, we can convert the tree of disjunct expressions into a list of all possible conjunct expressions

from itertools import product, chain

from dendrol import Pattern


def extract_atomic_chunks(root):
    container = root.get('observation') or root.get('expression')
    comparison = root.get('comparison')

    if container:
        join = container['join']
        expressions = container['expressions']

        if join == 'OR':
            # Return all possibilities under this node
            return chain(
                extract_atomic_chunks(expression)
                for expression in expressions
            )

        elif join == 'AND':
            # Generate all possible N-tuples, where N=len(expressions) 
            groups = [
                extract_atomic_chunks(expression)
                for expression in expressions
            ]
            return product(*groups)

    elif comparison:
        return comparison['value']


if __name__ == '__main__':
    stix_expr = "[(x:x.x = 'A' OR x:x.x = 'B') AND (x:x.x = 'C' OR x:x.x = 'D')]"

    pattern = Pattern(stix_expr)
    tree = pattern.to_dict_tree()
    root = tree['pattern']

    print(list(extract_atomic_chunks(root)))

I think that gets you where you want

[('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D')]
user_1485850
Related