Converting Boolean-Logic Decision Trees to Finite State Machines

https://medium.com/analytics-vidhya/converting-boolean-logic-decision-trees-to-finite-state-machines-180ad195abf2

by bkudria • 6 years ago

44 8 6 years ago

mpoteat• 6 years ago

In general I notice a trend in cybersecurity: it is very hard to do right, and it is very business critical.

This has led to a cottage industry of bad tech and bad science, whereby people peddle easy security solutions where none exist.

On what architecture would evaluating this abstract data structure be faster than a simple opcode?

atoav• 6 years ago

I guess what is used there is more or less a toy example. I used state machines once in a game and had quite good experience with it, especially when things grew more complex.

A lot of these abstraction patterns only start to show their true powers when in use in software that grew big.

That being said, I probably wouldn't use state machines there, I would use a type system..

mci• 6 years ago

While I have only skimmed the article, I have not noticed:

* an explanation how to test the multiple heterogenous out-transitions of a state efficiently,

* the reason for the silent assumption that at most one out-transition of a state is followed, i.e. that this is not an NFA [0],

* most importantly, a comparison with Binary Decision Diagrams [1].

[0] https://en.wikipedia.org/wiki/Nondeterministic_finite_automa...

[1] https://en.wikipedia.org/wiki/Binary_decision_diagram

thomasdullien• 6 years ago

Yeah, the (ro)BDD comparison really is missing; those would be the default data structure I'd reach for for such a problem.

lecunn• 6 years ago

Binary Decision Diagrams were also the first thing that came into my mind while reading the article.

mamp• 6 years ago

This approach seems to be simply implementing short-circuit boolean operators e.g. as soon as any AND condition is false, then false; as soon as any OR condition is true return true. The first example of evaluates every condition in a bottom up approach. While it's implemented as a FSM it doesn't need to be.

I think using ROBDDs (binary decision diagrams) or unrolling the AST into opcodes would be a more standard way of implementing optimisations.

mumblemumble• 6 years ago

Completely tangentially: I didn't really appreciate this technique until I played TIS-100.

kimi• 6 years ago

Clojure has something like this in clojure.core.match - with a good bibliography by the end of the page. https://github.com/clojure/core.match/wiki/Overview

Converting Boolean-Logic Decision Trees to Finite State Machines

Related Stories