Converting boolean-logic decision trees to finite state machines

cybermaggedon on 2019-12-28

Converting Boolean-Logic Decision Trees to Finite State Machines

for simpler, high-performance detection of cybersecurity events

When analyzing cybersecurity events, the detection algorithm evaluates attributes against boolean expressions to determine whether the event belongs to a class. This article describes converting boolean expressions to finite state machines to permit simpler, high-performance evaluation.

The open-source project Cyberprobe features this implementation. Conversion of rules to finite state machine (FSM) and application of the rules in FSM form is implemented in Python. Cyberprobe supports the use of millions of rules, which can be applied at greater than 200k events/second on a single processor core.

Problem

Applying boolean logic criteria to events solves many scanning and detection problems. For instance, an event occurs that is generated from an interaction with a service under protection. The event has the following attributes:

One or more boolean expressions for the class of thing I am trying to detect:

If TCP port number is 80 or 8080 AND IP address is 10.0.0.1 AND URL is http://www.example.com/malware.dat OR http://example.com/malware.dat …

The aim is to analyze a high-rate stream of such events against a large set of boolean expressions to classify the events.

The boolean expressions get unreadable quickly with English, which has no built-in operator precedence.

Boolean expressions

Boolean operators are represented as functions, and type:value represents attribute type/value match terms.

and(
    or(
        tcp:80, tcp:8080
    ),
    ipv4:10.0.0.1,
    or(
        url:http://www.example.com/malware.dat,
        url:http://example.com/malware.dat
    )
)

A boolean expression consists of a combination of, and(…), or(…) and not(…) functions, along with type:value match terms. I am using type:value pairs for match terms as that is useful in the domain I’m working in, but we could just as easily use strings.

Input

When evaluating the attributes of an event, attributes are type:value pairs. e.g.

ipv4:123.123.123.123
tcp:14001
ipv4:192.168.0.1
tcp:19001
url:https://myservice.com/path1

A basic evaluation algorithm

A simple approach for evaluation of a boolean expression using type:value pair input is to represent the boolean expression as a tree, and then use type:value pairs to trigger evaluation. Observations are stored in the tree.

The rules for evaluating a boolean tree against an event are:

That’s a straightforward algorithm; the point of this article is to provide an optimization.

There is a compromise here, the algorithm to convert the boolean tree to an FSM is compute intensive: it has complexity which is non-linear with the number of nodes: it is linear with the product of combination nodes (described below) and type:value terms. In real-world scenarios, boolean expressions will be converted to FSM when the rule is parsed, thereafter the FSM can be used numerous times.

Converting to an FSM

Step 1: Identify the ‘basic states’

In order to find the FSM, we look for all of the nodes in the boolean tree where state needs to be observed as evaluation proceeds. If you look at the example above, you can see that or nodes and and nodes are different. A child of an or node when evaluated as true immediately results in its parent being true, so no state needs to be kept regarding the children of or nodes. Whereas, when a child of an and node is true this is something which may need to be stored for later evaluation to determine the point at which the and node can be evaluated true.

The evaluation of not nodes is also complicated: a not node can be evaluated as true by virtue of its child maintaining a false evaluation for the duration of analysis.

The rules we state here are that some nodes in the boolean tree can be described as basic states:

  1. The root of a tree is inherently a hit state, which means the boolean expression is true. This is a basic state.
  2. A not node is never a basic state.
  3. A child of an and node is a basic state unless it is a not node.
  4. A child of a not node is a basic state unless it is a not node itself.

In the above example, the basic states are the two or nodes, and the ip:10.0.0.1 node. All qualify under rule 3.

The implementation gives each state a state name which consists of the letter s plus a unique number, assigned in a depth-first walk. The example boolean tree with states is shown below; the three children of the and node are given states, with the parent and node representing the hit state.

Step 2: Identify the ‘combination states’

The basic states are nodes where partial state needs to be recorded. One node in an FSM represents all state at the same time i.e. all the valid basic state combinations. Hence the combination states set consists all combinations of basic states. This includes the empty set, and a union of all states.

Combination states need to have a state name: in my implementation, I combine states to a name by ordering, separating state numbers with a hyphen preceded by s. For example, a combination of states s4, s7, s13 is called s4–7-13.

The empty set has a special name which we call init. It represents the initial state of the FSM where no information is known.

There is a special state hit which is used to describe any combination of basic states which include the root node evaluating to true. The combination of other states is ignored.

In the above example, the combination state set consists of:

Step 3: Find all match terms

This is the set of all type:value match nodes in the boolean expression tree.

Step 4: Find all transitions

This step is essentially about working out what all type:value match nodes do to all combination states. There is a special match term, end: which is used to evaluate what happens to not nodes when the list of terms is completed.

The algorithm is:

For every combination state:
    Work out the state name of that 'input' combination state
    For every match term:
        Given the input state
        What state results from evaluating that term as true?
        Work out the state name of that 'output' combination state
        Record a transition (input, match term, output)
    Given the input state
    What state results from evaluating end: as true?
    Work out the state name of that 'output' combination state
    Record a transition (input, end:, output)

For this analysis, when the whole boolean expression evaluates as true i.e. the root node of the boolean expression is true, we give that a special name hit.

The result is a complete set of triples: (input, term, output). If the input and output states are the same, we can ignore the transition so that the FSM only contains edges which change state.

At this point, the FSM has some inefficiencies: there may be areas of the FSM which it is not possible to navigate to from init. This is addressed in the next step.

Step 5: Remove invalid transitions

Not all combination states can be reached from init, and so some of the transitions discovered can be discarded as irrelevant.

We start by constructing a set of states which can navigate to hit:

  1. Create a set containing only the combination state hit.
  2. Iterate over the FSM adding all transitions for which there is a navigation to any state in the set.
  3. Repeat 2. until the full set of states is discovered.

At this point we know all states which can lead to hit. However, there will be transitions which lead to states which are not in this set, and thus cannot ever travel to hit. So, the first simplification of invalid transitions is to reduce all transitions to states which are NOT in this set to the single state named fail.

There is a second simplification of the FSM: some of the states are not navigable from init, and can be removed:

  1. Construct a set containing only init.
  2. Iterate over the FSM finding all transitions for which there is a navigation from any state in the set.
  3. Repeat 2. until the set of states is discovered.

At this point we know areas of the FSM which are not reachable, and they can be removed.

Resultant FSM

The FSM of the above binary tree is depicted below. The init state represents the initial FSM state. The hit state represents successful evaluation of the boolean expression as true. We have mentioned the fail state, which only occurs when not expressions are used, which do not appear as a result of the boolean expression described as above. See below for an example.

Using the FSM

Evaluation of a boolean expressions using the FSM is simple:

The fact that for each term a single FSM lookup is needed means that this approach has performance advantages.

Example 2: Using not

For this example, the not node is used:

and(
    not(
        or(
            tcp:8081, tcp:8082
        )
    ),
    and(
        tcp:80,
        or(
            url:http://www.example.com/malware.dat,
            url:http://example.com/malware.dat
        )
    )
)

It is interesting to view this graph before removal of invalid transitions and discovery of fail states. Some example artifacts:

After removal of invalid transitions and mapping to fail states, the FSM is easier to understand:

This example illustrates the fail state: once transitions lead to this state, it is not possible for further information to permit transition to the hit state. Discovering tcp:8081 or tcp:8082 to be present in any state causes a transition to the fail state. The fail state could be useful depending on your analysis strategy: it may be a point to fast-fail and shortcut further evaluation. This example also illustrates the special end: term which leads to hit.

Example 3: More state

This example requires much more state to be kept as a result of all of the and conditions.

and(
    or(
         url:http://www.example.com/malware.dat,
         url:http://example.com/malware.dat
    ),
    ipv4:10.0.0.1,
    not(
        and(
            or(
                tcp:8081,
                tcp:8082
            ),
            ipv4:10.0.0.2
        )
    )
)

The resultant FSM has many states as a result:

Evaluating many rules concurrently

The FSM model lends itself to highly performant scanning using a large set of rules, each converted to an FSM using the approach described above. While it is theoretically possible to produce an uber-FSM from the individual FSMs, the size of the FSM rapidly becomes unwieldly. As there needs to be a single state in the uber-FSM for each combination of states in the set of contributary FSMs.

However, tracking a large number of FSM states concurrently could be compute-intensive.

A simple evaluation approach is to identify a set of initiators, which are the set of terms which lead away from the init state in each FSM. If any of the initiators are detected while analyzing attributes, the corresponding FSM is activated and put on the set of FSMs which are being tracked for state changes in subsequent match term evaluation. This approach reduces the number of FSMs which need to be tracked. I find in practice, this results in a small set of FSMs used for evaluation.

Using this approach, it is not appropriate to fast-fail an FSM and remove it from the set of tracked FSMs; FSMs must be tracked to the fail state, to prevent the FSM from subsequently being re-activated.

Implementation: cyberprobe indicators

The cyberprobe project includes a means to write rules in JSON format. There are a number of utilities which parse the rule format and output FSM information e.g. indicators-show-fsm takes a rule/indicator file and dumps out the FSMs of every rule in the file. This is output in human-readable form showing the state transitions:

[indicators]$ indicators-show-fsm case1.json 
3ce77704-abe4–4527–84e6-ed6a745aebcf: URL of a page serving malware
 init — tcp:8080 -> s6
 init — tcp:80 -> s6
 init — url:http://example.org/malware.dat -> s3
 init — url:http://www.example.org/malware.dat -> s3
 s3 — tcp:8080 -> hit
 s3 — tcp:80 -> hit
 s6 — url:http://example.org/malware.dat -> hit
 s6 — url:http://www.example.org/malware.dat -> hit

indicators-graph-fsm is a utility which takes a rule/indicator file and a rule ID, and outputs a Graphviz format graph describing the FSM, which is how I generated the diagrams in this article:

[indicators]$ indicators-graph-fsm case1.json \
    3ce77704-abe4–4527–84e6-ed6a745aebcf > graph.dot
[indicators]$ dot -Tpng graph.dot > graph.png

indicators-dump-fsm is a utility which takes an indicator file and outputs the FSM in a JSON form.

You can embed the FSM transformation in your code using the cyberprobe.fsm_extract module:

#!/usr/bin/env python3
import sys
import cyberprobe.fsm_extract as fsme
from cyberprobe.logictree import And, Or, Not, Match
expression = And([
    Or([
        Match("tcp", "80"), Match("tcp", "8080")
    ]),
    Match("ipv4", "10.0.0.1"),
    Or([
        Match("url", "http://www.example.com/malware.dat"),
        Match("url", "http:/example.com/malware.dat")
    ])
])
fsm = fsme.extract(expression)
# Dump out FSM
for v in fsm:
    for w in v[1]:
        print("  %s -- %s:%s -> %s" % (v[0], w[0], w[1], v[2]))

A quick word on performance

To benchmark my algorithm, I have compared the performance of the FSM approach with the basic boolean-tree algorithm discussed at “A basic algorithm” above, coding both in Python. The plot below shows the number of rules in use as the x-axis, and the event handling rate as the y-axis. This is a way to show how the number of rules in use affects event throughput. The orange line represents the performance of the FSM. You can see that the number of rules in use has very little affect on algorithm throughput. Note logarithmic scale on the x-axis.

This was run on VirtualBox on my old MacBook, expect better performance from a cloud VM, for instance.

That’s a very quick look at performance, maybe I’ll do a follow-up article on performance later.

Conclusion

In this article I have discussed: