11 Nov 2015 - The Dark Side

Debugging Randomness

tl;dr: This article explains how to debug (and somehow test) programs involving randomness.


Many "smart" algorithms involve randomness as a way to test different potential solution to some problem or just getting randomness. Among others, they are common in optimization, machine learning and image processing.

Ideally we all like to view a program as a mathematical function, in the sense it is deterministic: given the same input it will provide the same output accross different calls. This is very helpful when you debug because errors are supposed to be deterministic as well, if it crashes once, it should crash twice. One of the most frustrating moment that a programmer can experience is called an heisenbug, named after the Observer Effect of Heisenberg, the physicist. An heisenbug occurs only from time to time and there is no given way to be sure to reproduce it, which also means that there is no given way to make sure that you have properly fixed it.

Dealing with randomness

Unfortunately introducing randomness can introduce a lot of heisenbugs, just because your program is not supposed to be deterministic anymore.

The code in this article is written in Ruby.

# Some function we have developed
def average(some_array)
  sum = 0.0
  some_array.each do |value|
    sum += value
  end
  sum / some_array.length
end

# The test
to_generate = (Random.rand() * 10).to_i

min_generated = nil
max_generated = nil
sample_array = []
to_generate.times do
  sample_value = Random.rand()

  if min_generated == nil || sample_value < min_generated
    min_generated = sample_value
  end

  if max_generated == nil || sample_value > max_generated
    max_generated = sample_value
  end

  sample_array.push sample_value
end

sample_average = average(sample_array)

puts sample_average

assert(!sample_average.nil? && !sample_average.nan?,
       'The average must not be nil or NaN')

assert(sample_average > max_generated,
       'The average must be at most the max_generated')

assert(sample_average < min_generated,
       'The average must be at least the min_generated')

Simulating randomness using a deterministic computer is a complex topic. If interested you should dig around what Pseudo Random Number Generators (PRNG) are, the quick take away here is that most PRNGs are initialized using a seed that is just a representation of the PRNG internal state.

This seed is usually automatically set for you using things that are changing (it could be the current timestamp), but if you set it your random number generator is now deterministic and will output the exact same values from a call to another one.

Random.srand(12)

puts Random.rand() # 0.1541...
puts Random.rand() # 0.7400...

We can apply to detect the buggy cases. At every call of our program we will generate a random seed and output it. If the program crashes we will just have to set the same seed again in the program to see what doesn't work.

#####################################
###### The interesting things, ######
###### insert this at the top  ######
###### of you file.            ######
#####################################
seed = (Random.rand() * 1000000).to_i

# Some value of seeds will raise an
# error (like, 483620) you will just
# have to fix the seed to reproduce
# this bug.
# Like:
# seed = 483620

puts seed
Random.srand(seed)
#####################################

Now if your bug is only showing from time to time you may want to run it until it crashes:

watch -e -n 0.1 ruby buggy.rb

Once it crashes, you will know for what seed it does and will be able to reproduce it by forcing the seed, as described in the comment of the above snippet.

In many language, note that the PRNG has a global state, if you set its seed somewhere it will affect all modules.

If you just try to copy paste the above Ruby code, you may need a quick assert function to get this running:

def assert(condition, message)
  if !condition
    raise Exception.new 'Assertion error: ' + message
  end
end

Concrete case

Gimuby is a stochastic optimization tool, which means that while it is iterating over potential solutions they should improve over time. "Should" means that this is statistically happening but that on a given case solutions quality could decrease.

It is perfectly legitimate to write a test asserting that the optimizer does optimize. Though doing this may also sometimes lead to random errors, or failed test cases.

The solution is to set a seed for which you know that your tests are valid.

The pro of this is to make your test suite deterministic, the same code will always pass or fail.

As a con, note that you may get false positive regression trigger. Adding or removing a call to any random function will affect the PRNG state and may put us in one of those cases where what should work doesn't work.

Here is a link to the line that makes our tests deterministic in Gimuby (the seed is reset for each test) in our abstract test case.


Fräntz Miccoli

This blog is wrapping my notes about software engineering and computer science. My main interests are architecture, quality and machine learning but content in this blog may diverge from time to time.

Ideas are expressed here to be challenged.


About me Out Of The Comfort Zone Twitter