Implementation of the LSTAR Grammatical Inference Algorithm

## Project description

pylstar is a free and open source Python implementation of the LSTAR Grammatical inference algorithm. It can be use to automaticaly infer the state machine that best describe the internal of a deterministic black box. To achieve this, pylstar observes the behavior of the target when stimulated with sequence of messages.

It has succesfully been used to infer various protocols such as Botnet protocols, Smart Cards protocols, Cryptographic protocols and Web Servers.

## Sample usage

One that wants to use pylstar must write a class that communicates with the targeted black box (i.e. it exposes the Minimaly Adequate Teacher of the targeted reactive System). This can be done by subclassing pylstar.ActiveKnowledgeBase.ActiveKnowledgeBase. If the targeted process is a network server, one can solely subclass pylstar.NetworkActiveKnowledgeBase.

For example, the following class can be use to start and stop a fake coffee machine (coffeemachine.py) through it API (localhost:3000). This class inherits from pylstar.NetworkActiveKnowledgeBase which exposes methods that can send (and read) network messages to (and by) the coffee machine API.

import time
import subprocess

from pylstar.NetworkActiveKnowledgeBase import NetworkActiveKnowledgeBase

class CoffeeMachineKnowledgeBase(NetworkActiveKnowledgeBase):

def __init__(self):
super(CoffeeMachineKnowledgeBase, self).__init__("localhost", 3000)
self.__sp = None

def start(self):
"""This methods starts the coffee machine (to be triggered before the learning process)."""
self.__sp = subprocess.Popen("/usr/bin/python coffeemachine.py", shell=True)
# lets wait 5 seconds for the coffee machine to start
time.sleep(5)

def stop(self):
"""This method stops the coffee machine (to be triggered after the learning process)."""
if self.__sp is not None:
self.__sp.kill()

Given this wrapper, the following snippet can be used to trigger the automatic inference of the coffee machine. This code declares the messages accepted by the API, an instance of our wrapper and returns a pylstar.automata.Automata.Automata (and prints its DOT code) that best describes the behavior of the coffee machine.

from pylstar.LSTAR import LSTAR
from CoffeeMachineKnowledgeBase import CoffeeMachineKnowledgeBase

# list of messages accepted by the coffee machine
input_vocabulary = [
"REFILL_WATER",
"REFILL_COFFEE",
"PRESS_BUTTON_A",
"PRESS_BUTTON_B",
"PRESS_BUTTON_C"
]
# instanciates our CoffeeMachine MAT
coffeeBase = CoffeeMachineKnowledgeBase()
try:
# starts the coffee machine
coffeeBase.start()
# learns its grammar
lstar = LSTAR(input_vocabulary, coffeeBase, max_states = 10)
# stores the coffee machine state machine
coffee_state_machine = lstar.learn()

# displays the DOT code of the state machine
print(coffee_state_machine.build_dot_code())
finally:
coffeeBase.stop()

The execution of this sample returns the state machine illustrated below:

A runnable example of the coffee machine inference is available in test/src/test_pylstar/coffee_machine_example.

## Installation

Pylstar is a typical python library. It relies on a setup.py file to describe its installation process.The following command can be use to install pylstar on your system:

## References

The LSTAR algorithm was introduced by Dana Angluin in the article

@article{Angluin:1987,
author = {Angluin, Dana},
title = {Learning Regular Sets from Queries and Counterexamples},
journal = {Inf. Comput.},
issue_date = {November 1, 1987},
}

This implementation also relies on the description of LSTAR provided by Colin de la Higuera in the book

@book{ColindelaHiguera,
author = {de la Higuera, Colin},
title = {Grammatical Inference: Learning Automata and Grammars},
year = {2010},
isbn = {0521763169, 9780521763165},
publisher = {Cambridge University Press},
address = {New York, NY, USA},
}

## Bugs and enhancements

I’m almost certain this code contains bugs. Please, report any bug found by opening a ticket and/or by submiting a pull requests.Obvisouly, the projet is opened to any minor and major enhancements.

## Changelog

Small bug fixes

Small bug fixes

### 0.1 - 2017-05-14

Initial version

Copyright (C) 2015-2017 Georges Bossert Copying and distribution of this file, with or without modification, are permitted provided the copyright notice and this notice are preserved.

## Project details

### Source Distribution

pylstar-0.1.2.tar.gz (57.1 kB view hashes)

Uploaded source