Identifikation der Rahmenlänge für ein unbekanntes serielles Protokoll

Nehmen wir an, du reverse-engineeringst ein serielles Protokoll. Du kennst bereits die korrekte Konfiguration für den seriellen Port (Baudrate etc.) und nimmst an, dass das Protokoll aus Rahmen gleicher Länge besteht.

Der Einfachheit halber nehmen wir auch an, dass das Gerät die Daten sendet, ohne dass zuvor Daten von ihm angefordert werden müssen. Wenn dies nicht der Fall ist, kannst du einen anderen und viel einfacheren Ansatz verwenden (sende einfach das Anforderungszeichen und s

Der nächste Schritt ist die Bestimmung der Rahmenlänge des Protokolls. Dieser Beitrag beschreibt nicht nur zwei Varianten eines der Algorithmen, die du dafür verwenden kannst, sondern bietet auch ein fertiges Python-Skript, das du für deine eigenen Protokolle verwenden kannst. Ansatz 1: Autokorrelation mit argmax

Wir werden einen einfachen mathematischen Ansatz verwenden, um herauszufinden, was die wahrscheinlichste Rahmenlänge ist. Dies basiert auf der Annahme, dass Rahmen einen hohen Grad an Selbstähnlichkeit aufweisen, d.h. viele der Bytes in einem einzelnen Rahmen stimmen mit den entsprechenden Bytes im nächsten Rahmen überein.

Es ist nicht erforderlich, dass alle Bytes in jedem Rahmen gleich sind, aber wenn du in jedem Rahmen völlig unterschiedliche Bytes hast, wird der Ansatz wahrscheinlich nicht die korrekte Rahmenlänge ableiten.

Dieser Ansatz basiert auf Autokorrelation. Obwohl es kompliziert klingt, bedeutet es nichts anderes als eine Sequenz mit einer verzögerten/verschobenen Version ihrer selbst zu vergleichen.

Das bedeutet, wir werden die folgenden Schritte ausführen:

• Eine Menge von Zeichen vom seriellen Gerät lesen
• Die Menge von Zeichen mit verschobenen Versionen ihrer selbst korrelieren
• Die Rahmenlänge ist die Verschiebung, bei der die maximale Ähnlichkeit auftritt (mittels np.argmax)

Als Ähnlichkeitsscore verwenden wir 1, wenn die Bytes gleich sind, sonst 0. Für spezifische Protokolle könnte es ein besserer Ansatz sein, einzelnes Bit-Matching einzuführen, aber dies wird auch Rauschen in den Prozess einbringen.

Für die meisten einfachen Protokolle, die ich gesehen habe, funktioniert dieser Ansatz sehr gut für sowohl ASCII als auch binär.

Das Plotten der Korrelation sieht so aus:

Ansatz 2: Mehrfach-Verschiebungs-bewusste Autokorrelation

Dieser modifizierte Algorithmus funktioniert gut für Protokolle, bei denen es unbedeutende Ähnlichkeit zwischen zwei Rahmen gibt oder wenn es viel Rauschen gibt. Für solche Protokolle liefert der Maximum-Score-Ansatz nicht das korrekte Ergebnis.

Wir können jedoch die Eigenschaft von Protokollen mit konstanter Rahmenlänge nutzen, dass wir hohe Übereinstimmungs-Scores erhalten, wenn wir einen Rahmen um ein ganzzahliges Vielfaches der (unbekannten) Rahmenlänge verschieben. Anstatt nur einen maximalen Peak zu nehmen, multiplizieren wir alle Scores für die ganzzahligen Vielfachen einer beliebigen Länge.

Während dieser Ansatz im Vergleich zum ersten nicht zu kompliziert klingt, hat er mehr Tücken und Fallstricke, z.B. dass es keine ganzzahligen Vielfachen innerhalb des Daten-Arrays für die zweite Hälfte des Korrelationsergebnis-Arrays gibt, und das zweite Viertel ist nicht sehr signifikant, da es nicht viele Vielfache zu multiplizieren gibt.

Das Skript (siehe unten) umgeht diese Probleme, indem es nur das erste Viertel des möglichen Ergebnisraums berechnet. Verwende den Parameter -n, um die Anzahl der vom Skript gelesenen Zeichen zu erhöhen.

Nach der Berechnung der Mehrfach-Verschiebungs-bewussten Korrelation können wir argmax genau wie im ersten Ansatz verwenden, um die beste Korrelation zu finden. Manchmal identifiziert dies ein Vielfaches der Rahmenlänge aufgrund von Rauschen. Du kannst dir den Plot ansehen (verwende -p) und die Rahmenlänge manuell bestimmen, um die korrekte Rahmenlänge zu finden.

Wie man am Ergebnis sehen kann, ist das „Rauschen“ (zwischen den Rahmenlängen-Verschiebungs-Übereinstimmungen, verursacht durch zufällige Übereinstimmungen zwischen Zeichen) größtenteils verschwunden.

In vielen realen Anwendungsfällen wird dieser Algorithmus ein deutlicheres Signal im Plot erzeugen, aber die automatisch berechnete Rahmengröße wird nicht korrekt sein, da mehrere Effekte dazu neigen, die Lappenhöhe für Vielfache der Rahmenhöhe zu erhöhen. Daher ist es ratsam, sich den Plot anzusehen (-p im Skript), bevor man das Ergebnis als gegeben hinnimmt. Automatisierung des Algorithmus

Hier ist das Python3-Skript zu diesem Artikel, das ohne Modifikation gut funktioniert, aber für einige Protokolle musst du es möglicherweise an deine Bedürfnisse anpassen:

#!/usr/bin/env python3
"""
ProtocolFrameLength.py

Bestimmen der Rahmenlänge eines unbekannten seriellen Protokolls
mit konstanter Rahmenlänge, das ähnliche Bytes in jedem Rahmen enthält.

Eine Erklärung findest du unter
https://techoverflow.net/2017/07/30/identifying-the-frame-length-for-an-unknown-serial-protocol/

Beispielverwendung:
$ python3 ProtocolFrameLength.py -b 115200 /dev/ttyACM0
"""
import serial
import numpy as np
import math
from functools import reduce
import operator

__author__ = "Uli Köhler"
__license__ = "Apache License v2.0"
__version__ = "1.0"
__email__ = "[email protected]"

def match_score(c1, c2):
    """
    Korrelations-Score für zwei Zeichen, c1 und c2.
    Verwendet einen einfachen binären Score
    """
    if c1 is None or c2 is None:  # Fill chars
        return 0
    return 1 if c1 == c2 else 0

def string_match_score(s1, s2):
    assert len(s1) == len(s2)
    ln = len(s1)
    return sum(match_score(s1[i], s2[i]) for i in range(ln))

def compute_correlation_scores(chars, nomit=-1):
    # Lass die letzten nomit Zeichen weg, da Einzelzeichen-Übereinstimmungen überbewertet würden
    if nomit == -1: # Auto-Wert
        nomit = len(chars) // 10
    corr = np.zeros(len(chars) - nomit)
    # Hinweis: Autokorrelation für Verschiebung null ist immer 1, absichtlich weggelassen!
    for i in range(1, corr.size):
        # Präfix mit Nones aufbauen
        prefix = [None] * i
        s2 = prefix + list(chars[:-i])
        # Normalisieren durch den maximal erreichbaren Score aufgrund der Nones und der Sequenzlänge (es gibt i Nones)
        corr[i] = string_match_score(chars, s2) / (len(chars) - i)
    return corr

def print_most_likely_frame_length(correlations):
    # Finde den größten Korrelationskoeffizienten. Dieses Modell erfordert keinen Schwellwert
    idx = np.argmax(correlations)
    print("Rahmenlänge ist wahrscheinlich {} Bytes".format(idx))

def plot_correlations(correlations):
    from matplotlib import pyplot as plt
    plt.style.use("ggplot")

    plt.title("Korrelations-Scores für ein Protokoll mit 16-Byte-Rahmen")
    plt.gcf().set_size_inches(20,10)
    plt.plot(correlations)

    plt.title("Korrelations-Scores")
    plt.ylabel("Normalisierter Korrelations-Score")
    plt.xlabel("Verschiebung")

    plt.show()

def multishift_adjust(correlations):
    """
    Mehrfach-Verschiebungs-bewusster Algorithmus
    """
    corr_multishift = np.zeros(correlations.size // 4)
    for i in range(1, corr_multishift.size):
        # Iteriere über Vielfache von i (inklusive i selbst)
        corr_multishift[i] = reduce(operator.mul,
            (correlations[j] for j in range(i, correlations.size, i)), 1)
    return corr_multishift

if __name__ == "__main__":

    import argparse
    parser = argparse.ArgumentParser()
    parser.add_argument('port', help='Der zu verwendende serielle Port')
    parser.add_argument('-b', '--baudrate', type=int, default=9600, help='Die zu verwendende Baudrate')
    parser.add_argument('-n', '--num-bytes', type=int, default=200, help='Die Anzahl der zu lesenden Zeichen')
    parser.add_argument('-m', '--multishift', action="store_true", help='Den Mehrfach-Verschiebungs-bewussten Autokorrelations-Algorithmus verwenden')
    parser.add_argument('-p', '--plot', action="store_true", help='Die resultierende Korrelationsmatrix plotten')
    args = parser.parse_args()

    ser = serial.Serial(args.port, args.baudrate)
    ser.reset_input_buffer()
    chars = ser.read(args.num_bytes)

    corr = compute_correlation_scores(chars)
    if args.multishift:
        corr = multishift_adjust(corr)
    print_most_likely_frame_length(corr)

    if args.plot:
        plot_correlations(corr)

Verwendungsbeispiel:

python3 ProtocolFrameLength.py -b 115200 /dev/ttyACM0

Du kannst -m verwenden, um den Mehrfach-Verschiebungs-bewussten Ansatz zu verwenden.

Verwende -p, um die Ergebnisse wie oben gezeigt zu plotten. Wenn einer der Ansätze nicht funktioniert, ist es ratsam, das Ergebnis zu plotten, um zu sehen, ob im Plot etwas sichtbar ist, das vom Algorithmus nicht erkannt wurde.

Da die Ergebnisse von den tatsächlichen gelesenen Daten abhängen, ist es ratsam, mehrere Durchläufe auszuführen und zu prüfen, ob die Ergebnisse variieren.