title: Finding images in RAM dump
body: <h2>Extracting screenshots from RAM dumps</h2>
  
  <p>Some classical security / hacking challenges include having to analyze the dump of the physical RAM of a system. <a href="http://www.volatilityfoundation.org/" rel="nofollow noreferrer">volatility</a> does a great job at extracting useful information, including wire-view of the windows displayed at the time (using the command <a href="https://github.com/volatilityfoundation/volatility/wiki/Command%20Reference%20Gui#screenshot" rel="nofollow noreferrer"><em>screenshot</em></a>). But I would like to go further and find the actual content of the windows.</p>
  
  <p>So I'd like to reformulate the problem as finding raw images (think matrix of pixels) in a large file. If I can do this, I hope to find the content of the windows, at least partially.</p>
  
  <p>My idea was to rely on the fact that a row of pixels is similar to the next one. If I find a large enough number of lines of the same size, then I let the user fiddle around with an interactive tool and see if it decodes to something interesting.</p>
  
  <p>For this, I would compute a kind of spectrogram. More precise a <a href="https://en.wikipedia.org/wiki/Heat_map" rel="nofollow noreferrer">heatmap</a> where the shade show how likely it is for the block of data #<em>x</em> to be part of an image of width <em>y</em> bytes, with <em>x</em> and <em>y</em> the axis of the spectrogram. Then I'd just have to look for horizontal lines in it. (See the examples below.)</p>
  
  <p>The problem I have right now is to find a method to compute that "kind of spectrogram" accurately and quickly. As an order of magnitude, I would like to be able to find images of width 2048 in RGBA (8192 bytes per row) in a 4GB file in a few minutes. That means processing a few tens of MB per second.</p>
  
  <p>I tried using FFT and autocorrelation, but they do not show the kind of accuracy I'm after.</p>
  
  <h2>The problem with FFT</h2>
  
  <p>Since finding the length of a mostly repeating pattern looks like finding a frequency, I tried to use a Fourier transform with 1 byte = 1 sample and plot the absolute value of the spectrum.</p>
  
  <p>But the main problem is the period resolution. Since I'm interested in finding the period of the signal (the byte length of a row of pixels), I want to plot the spectrogram with period length on the <em>y</em> axis, not the frequency. But the way the discrete Fourier transform work is that it computes the frequencies multiple of <em>1/n</em> (for <em>n</em> data points). Which gives me a very low resolution for large periods and a higher-than-needed resolution for short periods.</p>
  
  <p>Here is a spectrogram computed with this method on a 144x90 RGB BMP file. We expect a peak at an offset 432. The window size for the FFT was 4320 bytes.</p>
  
  <p><a href="https://i.stack.imgur.com/Kje5v.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Kje5v.png" alt="Spectrogram with FFT"></a></p>
  
  <p>And the segment plot of the first block of data.</p>
  
  <p><a href="https://i.stack.imgur.com/sBkqi.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/sBkqi.png" alt="Segment plot of FFT first block"></a></p>
  
  <p>I calculated that if I need to distinguish between periods <em>k</em> and <em>k+1</em>, then I need a window size of roughly <em>k²</em>. So for 8192 bytes, that makes the FFT window about 16MB. Which would be way too slow.</p>
  
  <p>So the FFT computes too much information I don't need and not enough information I would need. But given a reasonable window size, it usually show a sharp peak at about the right period.</p>
  
  <h2>The problem with autocorrelation</h2>
  
  <p>The other method I tried is to use a kind of discrete autocorrelation to plot the spectrogram.</p>
  
  <p>More exactly, what I compute is the cross-correlation between a block of data and half of it. And only compute it for the offsets where the small block is fully inside the large block. The size of the large block has to be twice larger than the max period to plot.</p>
  
  <p>Here is an example of spectrogram computed with this method on the same image as before.</p>
  
  <p><a href="https://i.stack.imgur.com/Xsbcv.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Xsbcv.png" alt="Spectrogram using correlation"></a></p>
  
  <p>And the segment plot of the autocorrelation of the first block of data.</p>
  
  <p><a href="https://i.stack.imgur.com/WZj4c.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/WZj4c.png" alt="Segment plot of the autocorrelation of first block"></a></p>
  
  <p>Altough it produces just the right amount of data, the value of the autocorrelation change slowly, thus not making a sharp peak for the right period.</p>
  
  <h2>Question</h2>
  
  <p>Is there a way to get both a sharp peak and around the correct period and enough precision around the large periods? Either by tweaking the afformentioned algorithms or by using a completely different one.</p>