Identifying the frame length for an unknown serial protocol

Let’s suppose you’re reverse-engineering a serial protocol. You already know the correct configuration for the serial port (baudrate etc.) and you assume the protocol is built from frames of equal length.

For simplicity we will also assume that the device sends the data without the necessity to request data from it first. If this is not the case, you can use a different and much simpler approach (just send the request character and se

The next step is to determine the the frame length of the protocol. This post not only details two variants of one of the algorithms you can use in order to do this, but also provides a ready-to-use Python script you can use for your own protocols.

Approach 1: Autocorrelation with argmax

We will use a simple mathematical approach in order to find out what the most likely frame length will be. This is based on the assumption that frames will have a high degree of self similarity, i.e. many of the bytes in a single frame will match the corresponding bytes in the next frame.

It is not required that all bytes are the same in every frame, but if you have entirely different bytes in every frame, the approach will likely not deduce the correct frame length.

This approach is based on autocorrelation. Although it sounds complicated, it means nothing more Compare a sequence by a delayed/shifted version of itself.

This means we will perform the following steps:

  • Read a set of characters from the serial device
  • Correlate the set of characters with shifted versions of itself
  • The framelength is the shift where the maximum similarity occurs (using np.argmax)

As similiarity score, we’ll use 1 if the bytes equal or 0 else. For specific protocols, it might be a more viable approach to introduce individual bit matching, but this will also introduce noise into the process. 

For most simple protocols I’ve seen, this approach works very well for both ASCII and binary.

Plotting the correlation looks like this:

Approach 2: Multiple-shift aware Autocorrelation

This modified algorithms works well for protocols where there is insignificant similarity between any two frames or if there is a lot of noise. For such protocol, the maximum score approach does not yield the correct result.

However, we can use the property of constant-framelength protocols that we get high matching scores by shifting a frame by an integer multiple of the (unknown) framelength. Instead of just taking one maximum peak, we multiply all the scores for the integer-multiples of any length.

While this approach doesn’t sound too complicated compared to the first one, it has more caveats and pitfalls, e.g. that there are no integer multiples within the data array for the second half of the correlation result array, and the second quarter is not very significant as there are not many multiples to multiply.

The script (see below) works around these issues by only computing the first quarter of the possible result space. Use the -n parameter in order to increase the number of characters read by the script.

After computing the multiple-shift aware correlation, we can use argmax just like in the first approach to find the best correlation. Sometimes this identifies a multiple of the frame length due to noise. You can look at the plot (use -p) and manually determine the frame length in order to find the correct frame length.

As you can see from the result, the “noise” (in between the frame-length shift matches, caused by random matches between characters) is mostly gone.

In many real usecases, this algorithm will produce a more distinct signal in the plot, but the automatically calculated frame size will not be correct as several effects tend to increase the lobe height for multiples of the frame height. Therefore, it is adviseable to have a look at the plot (-p in the script) before taking the result as granted.

Automating the algorithm

Here’s the Python3 script to this article which works well without modification, but for some protocols you might need to adjust it to fit your needs:

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

Determine the frame length of an unknown serial protocol
with constant-length frames containing similar bytes in every frame.

For an explanation, see
Identifying the frame length for an unknown serial protocol
Example usage: $ 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__ = "ukoehler@techoverflow.net" def match_score(c1, c2): """ Correlation score for two characters, c1 and c2. Uses simple binary 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): # Omit the last nomit characters as single-char matches would be over-valued if nomit == -1: # Auto-value nomit = len(chars) // 10 corr = np.zeros(len(chars) - nomit) # Note: autocorrelation for zero shift is always 1, left out intentionally! for i in range(1, corr.size): # build prefix by Nones prefix = [None] * i s2 = prefix + list(chars[:-i]) # Normalize by max score attainable due to Nones and the sequence length (there are i Nones) corr[i] = string_match_score(chars, s2) / (len(chars) - i) return corr def print_most_likely_frame_length(correlations): # Find the largest correlation coefficient. This model does not require a threshold idx = np.argmax(correlations) print("Frame length is likely {} bytes".format(idx)) def plot_correlations(correlations): from matplotlib import pyplot as plt plt.style.use("ggplot") plt.title("Correlation scores for a protocol with 16-byte frames") plt.gcf().set_size_inches(20,10) plt.plot(correlations) plt.title("Correlation scores") plt.ylabel("Normalized correlation score") plt.xlabel("Shift") plt.show() def multishift_adjust(correlations): """ Multi-shift aware algorithm """ corr_multishift = np.zeros(correlations.size // 4) for i in range(1, corr_multishift.size): # Iterate multiples of i (including i itself) 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='The serial port to use') parser.add_argument('-b', '--baudrate', type=int, default=9600, help='The baudrate to use') parser.add_argument('-n', '--num-bytes', type=int, default=200, help='The number of characters to read') parser.add_argument('-m', '--multishift', action="store_true", help='Use the multi-shift aware autocorrelation algorithm') parser.add_argument('-p', '--plot', action="store_true", help='Plot the resulting correlation matrix') 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)

 

Usage example:

python3 ProtocolFrameLength.py -b 115200 /dev/ttyACM0

You can use -m to use the multiple-shift aware approach.

Use -p to plot the results as shown above. If one of the approaches does not work, it is advisable to plot the result in order to see if there is something visible in the plot which has not been detected by the

As the results depend on the actual data read, it is advisable to perform multiple runs and see if the results vary.

Accurate short & long delays on microcontrollers using ChibiOS

How system ticks work

In order to understand how delays work, we’ll first need to have a look at system ticks. Although ChibiOS 3.x supports a feature called tickless mode, we’ll stick to a simple periodic tick model for simplicity reasons.

A system tick is simply a timer that interrupts the microcontroller periodically and performs some kernel management tasks. For example, with a 1 kHz system tick (systick) frequency, the program flow is interrupted every millisecond. When being interrupted, one of the things the kernel does is to check if a thread that is currently asleep needs to be woken up. In other words, if your thread has some code like this:

// [...]
chThdSleepMilliseconds(5);
// [...]

and the kernel has a 1 kHz systick frequency, the kernel will set your thread to sleep, wait for 5 system ticks (i.e. 5 ms) and then wake up the

Read more

Using Arduino Leonardo as an USB/UART adapter

In contrasts to older designs like the Arduino Uno, the Arduino Leonardo features a separate connection Serial1 for TTLUART whereas Serial is used for the USB CDC UART interface.

This allows one to use the Leonardo as an USB/UART bridge without having to resort to more expensive boards like the Arduino Mega 2560. In order to do this, use this sketch which can also be modified to provide an intelligent UART bridge.

Remember to adjust the baudrate for your application. This version of the sketch does not support automatic baudrate selection via the CDC peripheral.

Read more

Reading the STM32 unique device ID in C

All STM32 microcontrollers feature a 96-bit factory-programmed unique device ID. However, for me it was hard to find an adequately licensed example on how to read it in a manner compatible with different families and compilers.

Here’s a simple header that defines a macro for the device ID address. While I checked the address for both STM32F4 and STM32F0 families, other families might have slightly different addresses for the device ID. Check the reference manual corresponding to your STM32 family if errors occur.

Read more

Reading STM32F0 internal temperature and voltage using ChibiOS

The STM32F0 series of 32-bit ARM Cortex M0 microcontrollers contain a huge number of internal peripherals despite their low price starting at 0,32€ @1pc. Amongst them is an internal, factory-calibrated temperature sensor and a supply voltage sensor (that specifically senses VDDA, the analog supply voltage rail) connect to channels 16 and 17 of the internal ADC.

While I usually like the STM32 documentation, it was quite hard to implement code that produced realistic values. While the STM32F0 reference manual contains both formulas and a short section of example code, I believe that some aspects of the calculation are understated in the computation:

Section 13.9 in RM0091 provides a formula for computing the temperature from the raw temperature sensor output and the factory calibration values. However it is not stated anywhere (at least in Rev7, the current RM0091 revision) that this formula is only correct for a VDDA of exactly 3.30V.

Read more

Using the lwIP SNTP client with ChibiOS

A common task with embedded systems is to use the RTC to timestamp events. However, the system architect needs to find a way of synchronizing the devices RTC time with an external time source. Additionally, the designer needs to deal with the problem of drifting RTC clocks, especially for long-running devices. This article discusses an lwIP+SNTP-based approach for STM32 devices using the ChibiOS RTOS. The lwIP-specific part of this article is also applicable to other types of microcontrollers.

For high-accuracy or long-running applications, RTC clock drift also has to be taken into account. Depending on the clock source in use, the clock frequency can deviate significantly from the nominal value.

On the STM32F4 for example, you can derive the RTC clock from: The HSE/HSI main oscillator The LSI oscillator * The LSE oscillator, i.e. a 32.768 kHz external crystal.

Read more

Enforcing debugger breakpoints in ChibiOS chDbgAssert()

ChibiOS provides a variety of debug functions that can be enabled or disabled using preprocessor definitions.

When debugging ARM-based microcontrollers like the STM32, it can be useful to hardcode

This post provides a simple method of improving the definition of chDbgAssert() in chdebug.h so that a breakpoint is enforced in case of assertion failures. By using the ARM BKPT instruction, the overhead is only a single assembler instruction.

Read more

Reading STM32 unique device ID using OpenOCD

When working with the STM32 family of microcontrollers, it can be useful to evaluate the factory-programmed 96-bit UUID using JTAG. On all major operating systems, OpenOCD provides a simple yet highly compatible and free solution in order to do this.

In this example, we’ll use a JLink adapter together with the Olimex E407 evalation board. Both the adapter and the board are interchangable, provided you have working OpenOCD configurations available.

Read more

Yet another Atom Arduino blinker

While experimenting with Atom I produced a minimal example for making my old Arduino Uno blink its LED periodically.

Although there are plenty of examples out there (some of them even work!) I didn’t want to introduce any dependency to the Arduino libraries. Besides making it harder to build (even if arscons is quite nice) it increases the object size and Arduino only supports a limited range of processors. I need the flexibility to use the code on controlles like the ATTiny45

Read more