3 ms·

Converting Boolean-Logic Decision Trees to Finite State Machines

44 points by bkudria 6y ago

mpoteat 6y 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 6y 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 6y 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_automaton https://en.wikipedia.org/wiki/Nondeterministic_finite_automa... [1] https://en.wikipedia.org/wiki/Binary_decision_diagram https://en.wikipedia.org/wiki/Binary_decision_diagram
- thomasdullien 6y 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 6y ago
  Binary Decision Diagrams were also the first thing that came into my mind while reading the article.
mamp 6y 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 6y ago
Completely tangentially: I didn't really appreciate this technique until I played TIS-100.
kimi 6y 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 https://github.com/clojure/core.match/wiki/Overview

44 points by bkudria 6y 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 6y 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 6y 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_automaton https://en.wikipedia.org/wiki/Nondeterministic_finite_automa... [1] https://en.wikipedia.org/wiki/Binary_decision_diagram https://en.wikipedia.org/wiki/Binary_decision_diagram

thomasdullien 6y 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 6y ago
Binary Decision Diagrams were also the first thing that came into my mind while reading the article.

mamp 6y 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 6y ago

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

kimi 6y 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 https://github.com/clojure/core.match/wiki/Overview