Funstuff: Fighting LCBO and Beerstore by Brewing Your Own Stuff

"Wer nicht liebt Weib, Wein und Gesang,

Der bleibt ein Narr sein Lebenlang."

(Martin Luther, 1483 - 1546)

(In English: He who loves not wine, woman, and song, 

Remains a fool his whole life long.)

Canada is a lovely country: Nice people, a beautiful landscape and a relatively well developed education system; but a few things bother me since I arrived here, among them the existence of the LCBO in Ontario. Being originally from Germany the extremely high beer prices in Ontario are far from acceptable for me. Paying about 50 CAD for a decent 24-pack of your favorite beer is not ok. I do not want to go into the roots of the problem with LCBO, but the money collected over there is far away from the actual manufacturing cost of the beer for various arguable reasons. More recently the option to buy “de-alcoholized beer” emerged at several grocery stores. Unfortunately the reverse-osmosis process used to remove the alcohol, in my view, also takes away most of the beer’s flavor. Ironically, the de-alcoholizing step increases the cost of production significantly; however, it is sold far cheaper than the alcoholic equivalent in the LCBO. Out of curiosity, I paid 7 CAD for a 24 of “Compliments De-Alcoholized Beer" from Sobeys only to find out later that the taste is merely mediocre.

My current roommate, Phillip, is a visiting scholar in Chemistry from Germany, who is also very annoyed by “the beer situation” in Ontario. Together we decided to claim our independence from this suppressive legislation by brewing our own stuff. This article is a description of what we did to change the situation. Our objective was to find a way to brew our own stuff by just using readily available supplies from the Grocery store.

Solution Approach 
Brewing beer is a skill and it takes plenty time and effort to master the process. Moreover, most of the actual ingredients used to produce high-quality beer are not readily available in a grocery store. As such we resent to try Ginger Beer an ancient drink from Greece that made it later to Britain. The main reason for this decision is the straightforward brewing process that only requires a few readily available ingredients. According to Wikipedia, the fermentation process may yield up to 11% of alcohol; but according to my roommate it will actually be much less using grocery-store-ingredients and a short fermentation process.

Required utilities and ingredients for 1.5l of beer:

• 4-5 cm of a thumb-thick ginger root, 
• 1 cup of sugar (we used brown sugar but that is up to your flavor), 
• 2 tbsp of lemon juice, 
• 0.5 tsp of bakery yeast, 
• 1.5l of water, 
• An empty 2 liter plastic bottle, a plastic funnel, a big pot, and, optional, a coffee filter (or cooked towel).

Procedure

At first start by cleaning and cutting the ginger. Cut it into very tiny pieces to ensure a good flavor extraction later on.

Next, mix the ginger, sugar, lemon juice in the big pot and bring it to simmer. Stir it, so nothing sticks to the pot.

After simmering it for 3-5 minutes, let it cool off for some time. It needs to cool off below +35C; otherwise you would kill the yeast, which is added afterwards. The Canadian winter is your friend in that regard; we just put it out in the snow for 25 minutes and watched the Olympics.

When the mixture is cold, add the yeast and stir it.

Next put the stuff into a 2l plastic bottle and leave about ¼ of the bottle empty. This air pocket is needed to start the aerobic fermentation. Although most of you might expect the yeast to get busy creating alcohol but at first it actually converts the sugar and the oxygen into carbonic acid, which you might see as tiny bubbles (i.e., carbonic acid dissolves to carbon dioxide and water).

Keep the bottle in a warm spot (i.e., a furnace channel as shown in the picture) to keep the yeast busy. Periodically monitor the pressure in the plastic bottle. The yeast can produce a lot of carbonic acid. If you do not pay attention the bottle may actually explode and create a big mess. If you cannot press-in the plastic of the plastic bottle anymore it is time to set the yeast out of work. The yeast slows down the fermentation process if you put it in a cold spot, preferably a fridge.

Leave the closed bottle inside the fridge for 24 hours.

The following step is optional and a matter of taste. In order to remove the ginger pieces and any clusters of yeast, you may want to filter the beer after the brewing process. A coffee filter works best to remove most of the remaining solids.

Because of the filtering step, however, most of the carbonic acid will dissolve to carbon-dioxide and water; such that, the sparkling is gone. The very short fermentation process will give you mainly carbonic acid and little alcohol; however, I can assure you that your own brewed ginger beer will outperform any of the refined ginger ales (i.e., alcohol removed) from nearby grocery stores by taste.

Risks and Potential Improvements
Since the described fermentation process actually only takes a matter of hours the procedure is relatively safe. If however, you want to push the alcohol concentration higher and extend the duration of the fermentation you might get problems. The issue with limiting yourself to grocery store ingredients is that the quality of the produced alcohol will be low due to the yeast used. If you perform the following process for lengthy periods to have a high alcohol yield you will end up with a heavy headache at best and vision problems at worst. In the anaerobic phase (i.e., all the oxygen is gone) of the fermentation the bakery yeast actually generates traces of complex alcohols, including methanol, propanol and isopropanol (a.k.a. heavy headache!). A high-quality brewer’s yeast would generate more ethanol in the anaerobic phase than baker’s yeast and, therefore, probably be better suitable for brewing for lengthy periods. In order to obtain the claimed 11% of Wikipedia, you would have to have the fermentation going for a matter of weeks.

Conclusion and Future Work

In my eyes the policies and concepts of the LCBO are antiquated at best and arguably at worst. Canada compared to Germany is the other extreme, back home one could end up with store configurations that would sell beer cheaper than soda water. Unfortunately, it is not in my hand to change legislation in Ontario in favor of that. In order to overcome the impact of that legislation, you need to take your fate into your own hands and claim your own independence. Producing ginger beer for personal consumption provides a relatively safe low-cost alternative to commercially sold beer in Ontario. If you only consider the cost of the ingredients, you even fare cheaper than refined ginger ale (i.e., alcohol removed) brands. And the best of it is that it is your own stuff.
Having established the basics of alcoholic fermentation we actually might consider some advanced topics of beer brewing, wine-making, or even fractional distillation to create liquor (after the legal issues in Canada are reviewed) in the near future.

Here another "educational" scene for home-brewing and the risks from my favorite kid's movie "Werner". It explains how Werners boss tries to home-brew alcoholic beverages to make his number-one client drunk during a garden party and sign a contract to save his business. During the process the apprentice actually gets the idea of using Methanol as alternate fuel, which provides the basis of the entire movie. If you speak German or are currently learning it I can recommend this movie. A few comedies like this one actually manage to incorporate so many of the stereotypes that people might have about Germans in 2h.

This do-it-spirit is what contributes to the large number of US patents filed by individuals in Germany :D.

References

• Ginger Beer
• Alcohol Fermentation
• What is the LCBO

Hands-On Discrete Control with Decision Processes (Part 1)

Hint: Use a decent browser (e.g, Google Chrome, Mozilla Firefox) otherwise the formulas will not display accurately.

In my research I recently needed into discrete control and started to dive into Markov Decision Processes (MDP) and Partial Observable Markov Decision Processes (POMDP). At a first glance just these terms may seem sophisticated to the naked eye, but I will show that these two are actually very powerful tools to model decision making and therefore implement discrete control paradigms.

Unfortunately this topic is usually covered with plenty of math in textbook which leaves poor grad students like me with converting the math into usable code. In this and the following articles I want to share some experience I have gained so far in implementing Markov Decision processes.

In order to make this hands-on and not just dump math at you, I will provide example code in Python/numpy, with all algorithms implemented from scratch, and explain the guts using the formulas and the implementation.

Background: Decision Processes

Suppose you are confronted with making a decision, you are usually confronted with a number of possible actions you can perform that will have some effects on your environment and each decision has some benefit or cost associated with it. The effects of the immediate actions are usually easy to see, however the long-term consequences are hard to predict. Coming up with a general model for decisions is non-trivial because making the decisions can depend on many factors of the environment; especially other people in your environment; your beliefs, your observations, your capabilities, and the questions you try to answer with your model. To get a sense of this claim the reader is referred to the large domain of Game Theory that actually comes up with many models for “toy-problems”. Unfortunately, the questions Game Theoretic approaches seek to address are usually different from what someone needs to build a decision process to model a control problem.

For example, consider yourself in a clothing store. Your initial objective is to buy nice clothing and you may consider going back to the store if you like it. The shelves in the store have some items to choose from and some cost associated with it. Suppose you like the friendly lady in the store and you do not want to look old fashioned in front of her. Soon your objectives, available actions and system boundaries change and you need to take her views and beliefs into consideration. Worse, consider belief nesting: What if she thinks that I think she might think… in short coming up with a realistic model which jacket to choose or paying subsequent visits to the store is not easy.

When approaching technical control problems, we need to sacrifice some aspects of real life we deem less important. The first step in simplification is to close the problem space, by only considering...

• A finite number of states of the environment. 
• A finite number of actions to choose from. 
• A finite number of effects on the environment. 
• Associating defined cost with each action in each state.

Making the above simplifications eases the process a lot. Since a decision making process involves a sequence of decisions. Another huge simplification is to only consider the effects of the last decision made, this is called Markov assumption.

Making the above assumptions opens the door to use two standard frameworks for modelling decision processes, namely the Markov Decision Process (MDP) and the Partial Observable Markov Decision Process (POMDP) which will be covered in part two of the article.

Markov Decision Process (MDP)

A Markov Decision Process is a simple stochastic control process that satisfies the assumptions and model of the previous topics. It is well suited for problems where you can model the entire environment as states and make them visible to your agent (i.e., the entity making the decisions). In addition most solution algorithms that compute the control action assume that the definition of states, cost and actions and is fixed and time-invariant. That means that the reward for a particular action in a particular state does not change from time to time. Ok let’s get dirty and formalize this stochastic tool:

• $\mathbb{S}$ is the finite set of states 
• $\mathbb{A}$ is a finite set of actions, with $\mathbb{A}_{s} \subseteq \mathbb{A}$ being the available actions in a particular State $s \in \mathbb{S}$ 
• $\text{P}_a(s, s_n)$ the probability that Action $a \in \mathbb{A}$ in State $s \in \mathbb{S}$ leads to State $s_n \in \mathbb{S}$. Because most solution algorithms consider this function to be time-invariant, it can be easily modeled as a family of matrices, one matrix per action. 
• $\text{R}_a(s, s_n)$ is the expected immediate reward (or cost) after the transition from State $s \in \mathbb{S}$ to State $s_n \in \mathbb{S}$ given a particular action. If the rewards are time-invariant, this function can be represented as a family of matrices as well.

An MDP is fully specified when those functions are given.

There are two key control problems that can be answered with MDPs. 

• What is the optimal action to advance into any other state? 
• What is the optimal plan to for a finite number of transitions?

Having a complete view of the expected rewards, the states of the environment and the current state, the computation of one step and a finite number of steps is a straightforward optimization problem. Before digging into the math, let’s consider a simple example. A model how to become one of the rich and famous (this was originally proposed by Andreas Krause at CALTECH University, see references).

In this model there are two actions. First we can spend money on advertising to become famous (f) or save our money to become rich (r). Depending on the state we are in we have different chances of becoming famous or rich. In the diagram the red lines show the effects of advertise action, the green lines the save action. Each edge is labelled with the transition probability and the associated reward or (cost for negative numbers). Assume being poor (p) and unknown (u) and deciding to advertise (green lines). Then we have a 50-50 of becoming poor and famous or remain poor and unknown; in both cases we have a cost of 1. The decision to advertise yields a cost of one in both cases. From this simple model we can construct our mathematical model.

• $\mathbb{S}$ = $\lbrace pu, pf, ru, rf \rbrace$ 
• $\mathbb{A}$ = $\lbrace \text{advertise}, \text{save} \rbrace$ 
• $\text{P}$ and $\text{R}$ are initialized as shown in the graph.

Python and numpy support easy initialization of matrices and arrays. The complete model definition is shown in the source below.

import numpy

# definition of states
S = numpy.array(['pu', 'pf', 'ru', 'rf'])
# definition of actions (just for output
# we will work with int indices of them
A = numpy.array(['advertise', 'save'])

# definition of expected rewards
R = [ numpy.array( # advertise
    [#pu   pf   ru   rf 
     [-1.0, -1.0, 0.0, 0.0], # pu
     [ 0.0, -1.0, 0.0, 0.0], # pf
     [-1.0, -1.0, 0.0, 0.0], # ru
     [ 0.0, -1.0, 0.0, 0.0], # rf
    ]),
    numpy.array( # save
    [#pu   pf   ru   rf 
     [0.0, 0.0, 0.0, 0.0],  # pu
     [0.0, 0.0, 0.0, 10.0], # pf
     [0.0, 0.0, 10,  0.0],  # ru
     [0.0, 0.0, 10,  10],   # rf
    ])]

# definition of transition probabilities
T = [numpy.array( # advertise
    [#pu   pf   ru   rf 
     [0.5, 0.5, 0.0, 0.0], # pu
     [0.0, 1.0, 0.0, 0.0], # pf
     [0.5, 0.5, 0.0, 0.0], # ru
     [0.0, 1.0, 0.0, 0.0], # rf
    ]),
    numpy.array( # save
    [#pu   pf   ru   rf 
     [1.0, 0.0, 0.0, 0.0], # pu
     [0.5, 0.0, 0.0, 0.5], # pf
     [0.5, 0.0, 0.5, 0.0], # ru
     [0.0, 0.0, 0.5, 0.5], # rf
    ])]

Based on that model, how do we derive an optimal policy that maximizes the reward in each step? The beauty about this example is that the transitions are actually stochastic and therefore the expected rewards. In this example the rewards are fully defined, but for many real-world problems these rewards are not fully defined upfront or distributed with an unknown distribution. In that case we should instead explore the world and update our model based on the observations. A tool that enables this type of online learning is reinforcement learning specifically a Q-learner. In a nutshell the Q-learner learns a function that assigns utility to making a particular action in state s for future states. The beauty about a Q-learner is its ability to learn transition probabilities and rewards from observations. Its parameters give control about how much an agent should plan ahead when making a decision and how fast to learn. Formally the learning is performed as follows.

$\text{Q}(s_t, a_t) := \text{Q}_n(s_t, a_t) (1-\alpha) + \alpha (r + \gamma \text{argmax}_{a}\text{Q}(s_{t+1}, a)$

The formula is straightforward. The individual parameters are as follows:

• $\text{Q}_n(s_t, a_t)$: the old utility value of the current state $s_t$, given the action $a_t$. 
• $\text{Q}(s_{t+1}, a_t)$: Is the expected utility of traversing into state $s_{t+1}$ by committing action $a_t$. Note this utility is approximated from past observations and is therefore defined. 
• $\alpha$: The learning rate. It specifies how much the agent learns from the current observation. A value of 0 means it learns nothing, a value of 1 would only consider the most recent observation. 
• $\gamma$: The discount factor. It specifies the importance of future rewards and therefore the planning horizon of the agent. A factor of 0 makes the agent opportunistic and only lets it consider the next state. A value of 1 would make it strive for long-term results. Note that larger values than 1 make the learning instable. 
• $r$ is the observed reward after committing action $a_t$.

One question to answer is now how to make the agent explore the state space to approximate the utility of actions in particular states. A naïve approach is to just randomly select an available action in each state; this would probably exercise most of the action/state configurations but yields suboptimal results since we are already controlling something while learning. A slight optimization is to stochastically select the next action based on the observed utilities, but also this could push the learning into a local optimum. Another approach is to take a tool from Thermodynamics and model the “stupidity” of the agent using the Boltzmann distribution. The Boltzmann distribution originally was used to model the velocity distributions of particles in gases based on the temperature. Instead of modeling particles, we model individual decisions based on an underlying distribution of utilities. We (mis-)use the “temperature” parameter of the distribution to model stupidity. A value approaching 0 would generate stochastic decisions following the distribution of utilities; a higher value would smooth the underlying distribution and distribute the values more uniformly. Putting that into context of making decisions, a high value would generate decisions alike the shopping behaviour of a young rich college girl (no offence intended) and a low value would model the shopping behaviour of a retiree that is trying to get the most of his pension (no offence intended either).

$p_i := \frac{e^{\frac{u_i}{k}}}{\sum_j e^{\frac{u_j}{k}}}$

The components of the Boltzmann distribution are as follows:

• $k$ is the temperature parameter 
• $u_i$ is some measure (e.g., utility or success probability) for the action $i$ 
• $p_i$ is the success probability for an action $i$ given the temperature $k$

A neat thing, when incorporating the Boltzmann distribution into our model we can make it dynamic and become more conservative about the decisions made by decreasing the temperature parameter within each step, the more we learn about the world. Ok let’s look at the implementation of the Boltzmann distribution in numpy.

@staticmethod
    def BOLTZMANN(k, Qs):
        '''Computes the Boltzmann distribution
        for doing something "stupid".
        @param k: temperature (aka stupidity)
        @param Qs: array of q values of the
        current state.
        '''
        # compute e^(q)/k for all actions
        Es = numpy.exp(Qs/k)
        
        # [x_j : e^[ q(a_j,s)/k ] / 
        # [sum_j e^[q(a_j, s)/k]]]
        return Es/numpy.sum(Es)

Numpy supports element-wise array operations which makes the implementation straightforward and short. The function returns an array of probabilities for making decisions.

The next building block we need is a random number generator that can generate the decisions based on a discrete probability distribution. Unfortunately, neither numpy nor Python provide a function that performs this mapping. However, one can easily implement their own distribution by leveraging the uniform(0,1) distribution. The technique works as follows:

1. Pick a random number from uniform(0,1) 
2. Stick it into the quantile-function (i.e. the inverse cumulative probability distribution function) of the target distribution 
3. Take this value and enjoy your custom random process.

The above approach is also referred to as Smirnoff-transformation.

The quantile function of our array of probabilities is a mapping from a probability to an index. This can be implemented by computing the cumulative distribution function (CDF) of the probabilities on the fly and comparing it to the input probability. Once the CDF is larger than the probability we can take the previous index. If you look at the following code this procedure becomes more obvious.

@staticmethod
    def DECIDE(distro):
        ''' pick a state at random given a
        probability distribution over
        discrete states
        @param distro: the prob. distribution'''
        # make decision
        r = numpy.random.rand()
        tmp = 0
        for a in xrange(len(distro)):
            tmp += distro[a]
            if r < tmp:
                # decision made
                break
        return a

Ok putting all the building blocks together, we can implement iteration as follows.

def iterate(self):
        '''Performs one action in the current
        state and updates the q-values'''
        
        # decide which action to take based
        # on Boltzmann distro of q-values of
        # the current state
        dist = self.BOLTZMANN(self.k, self.Qs[self.cs])
        
        # normalise
        dist /= numpy.sum(dist)
        
        # pick a random action
        a = self.DECIDE(dist)
        
        # decide new state based on transition
        # probabilities
        tsp = self.T[a][self.cs,:]
        newState = self.DECIDE(tsp)
        
        # compute reward
        r = self.R[a][self.cs, newState]
        
        self.Qs[self.cs, a] = (
             self.Qs[self.cs, a] * (1.0 - self.alpha) +
             self.alpha * (r + self.gamma * numpy.max(self.Qs[newState])))
        
        # update strategy for state
        self.cs = newState

The model parameters are the same as described above in the initialization. The matrix Qs models the utilities of particular states given an action. When invoking this method we can adjust the learning parameters which are gamma, the discount factor that controls the long-term outlook of the learner, alpha, the learning rate that weights the observations made, and k which models the stupidity of making decisions. In the sample code only k is reduced in a linear fashion with each learning step.
The optimal policy for this model is to advertise in the poor-unknown state and save in all other states until you are rich and famous.

Conclusion

In this first part, I introduced stochastic Markov Decision processes and exemplified the learning of such processes with stochastic rewards using a Q-learner. The exploration of the process is controlled using a dynamic Boltzmann distribution that makes the learner make more conservative decisions the more it knows about the environment. All of the artefacts of this model were implemented in python using numpy. Although python is an interpreted language, by leveraging the performance of numpy's array operations we can implement an affordable learner. The reader should note that there are more efficient policy iteration methods for MDPs if the rewards are fixed (i.e., value-iteration and policy iteration), however this is not generally the case. Furthermore the model presented here may not make you rich, there are other ways of getting rich in practice :D. I hope you enjoyed this part of tutorial.

• Sample Code (provided under the terms of the LGPL)

References

• Markov Decision Processes
• Andreas Krauses' course notes
• Numpy website 
• Boltzmann distribution
• Q-learning 
• Smirnoff transformation

Funstuff: Proving the Myth of Cuban Glass

Legal Disclaimer: You should not perform the actions described here. If you do, you do it at your own risk!
THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE DESCRIBED ACT IS WITH YOU. SHOULD THE ACT PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR CONVEYS THIS ACT, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE ACT, EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.


This is an experience that I made during New Year festivities in at home in Germany. My cousin is a big fan of a particular Cuban Rum brand and got some “Cuban Glasses” as gift from someone else. The story behind Cuban glass is curious. Under Castro and his current replacement the average population in Cuba chronically appears to lack of something, in this case it was cocktail drinking glasses. The myth is that using a piece of heating fan wire and an old motorcycle piston ring and empty rum bottles, creative Cubans were able to cut their own glasses from empty rum bottles. This heroic procedure actually made it into the Havanna Club advertisements, as shown below.

After a long new year’s dinner and being reinforced with an industrial strength drink, my uncle, a retired physics and biology teacher, and I decided to actually bust or prove this myth with the bottle that was emptied earlier. Unfortunately, we did not have a fancy rum bottle ready, just an empty advocaat bottle to prove the concept. Trying to get as close as possible to the myth, we got a piece of heating fan wire from a broken fan, a couple nails and a piece of wood and model-train transformer and later on grandpas old radio transformer.

The nails and the piece of wood were used to build a support stand for the bottle, because we did not have the piston ring to align the heating wire. The idea is to wrap the heating wire around the bottle to enforce a clean crack in the Glass from the tension caused by the temperature gap where the heating wire sits. Note that using a regular wire is not going to work because the resistance is too low to convert current into heat.

The first attempt shown in the above picture with a model transformer resulted in nothing but a slightly charred label. The voltage delivered by the model train transformer (approx. 20V) was not enough to provide enough power to actually crack the class. Fortunately, we still had grandpas’ old radio transformer that he used to build and test his home radio equipment several decades ago. Most of the components he used in that transformer predate WWII.

The voltage on that transformer is freely adjustable between 0 to 250V and we made the glass crack at around 50V, incidentally setting the wooden support-stand on fire (a piston ring would have been more appropriate).

The edge on the glass followed exactly the line of the heating wire. Because it was not smoothly aligned you also see this misalignment in the crack.

Alternate Approach
The success got me curious and I started digging through some old books for other examples of the act. There is actually another workable procedure for making these classes, documented in an old WWII book (see references). According to the notes, you could actually “repair” broken bottle necks by filling the empty bottle with oil (e.g., engine oil or vegetable oil whatever was available during the war) take a glowing piece of hot iron (i.e., a rabble that was heated in the fire) and stick it into the oil. That would ignite the oils surface at an instant and the glass would crack exactly at the fill line of the oil. Then you could blow out the flame and try it over at another broken bottle.

Conclusion
Overall we considered the Cuban glass myth to be true. The next step to create a professional grade glass would involve sanding the edges of the crack to create a smooth surface (this is also shown in the Havanna club ad). The act provides a dangerous but workable framework to create any kind of glass that you would want in the household. Some people use alike techniques to create feeding bowls for their pets or artistic creations. This act involves significant risk, be sure to be safe or not perform this act at all.

References:

• Havanna Club Advertisement
• Bönicke, Gerhard: „Tornister-Lexikon für Frontsoldaten“, Tornisterschrift des Oberkommandos der Wehrmacht, Abt. Inland : nur für den Gebrauch innerhalb der Wehrmacht, 1943 (In English: Bönicke: „Tornister Encyclopedia for Front-Line Soliders“, Memo of the Wehrmacht supreme command for domestic affairs: only for Wehrmacht use, 1943) 

On Designing Boot Loaders and Grey-box-Testing Firmware (Part 2/2)

In the past tutorial, we have established how to integrate two pieces of code together, exemplifying a boot-loader and firmware interaction. The difference to the previous scenario is that in a test-suite, you actually need to maintain a symmetric interaction among those two different pieces of code. There are several approaches how this can be achieved.

• Explicitly pin each data-structure to specific locations in the memory. So each of the code pieces knows where to look for the others code and data.
• Pin an entry point of the firmware to a specific memory section that registers tests in another shared memory section.
• Pin an entry point of the firmware to a specific memory section that registers tests in a data-structure provided by the test-suite.

Looking at the different options it becomes apparent, why we talk about “grey-box testing”. In all cases we need to know some memory sections within the other pieces of code. The approaches differ by the number of memory sections required to be pinned. In addition, you might want to load tests dynamically through the boot loader requiring additional pinned sections.

Step One: How to Customize the Locations of Code and Data

In principle you want to place individual data structures and code into labelled memory sections, defining the location and label in the linker script and referencing label in GCC for the linker. The attribute-section paradigm allows us to do so. Suppose we want to load a function called test into a block of memory at an absolute address. First, we need to define this memory section in the linker script as follows:

MEMORY
{
    ram        : ORIGIN = 0x10200000, LENGTH = 1M
}

SECTIONS
{
.text :
    {
    *(.text)
    *(.rodata*)
    } > ram

.data :
    {
    *(.data)
    } > ram

.bss :
    {
    *(.bss)
    } > ram

__TESTS__ 0x10300000:
    {
    *(__TESTS__)
    }
}

Second, we need to reference this section in the code. This is done by declaring an attribute in the function’s specification as follows:

void __attribute__ ((section ("__TEST_INIT__"))) init_tests() {
...
}

The listing shows that the function is indeed stored at that particular location.

Sections:
Idx Name          Size      VMA       LMA       File off  Algn
...
3 __TEST_INIT__ 00000030  10400000  10400000  00006000  2**1
...
Disassembly of section __TEST_INIT__:

10400000 :
...

Likewise global data structures and variables can be stored at such particular locations.

typedef struct {
void (*test1_fun)();
} TestFixture;

TestFixture __attribute__ ((section("__TESTS__"))) tests;

Step Two: Designing the Tests

We proposed three options for the test integration in the introduction.

Option One: (Naïve) Tell everything

The first naïve approach is to actually pin each testable primitive and global data structure to a particular memory region. In this scenario, all entry points to these primitives and global data structures are declared in the linker script of the test code. The linker script of the firmware declares all of those sections and the primitives are pinned to these sections using the attribute-section paradigm. This approach reduces the overhead of implementing tests vastly, since all locations are defined and no futher registration of the firmware with the tests is needed. Expected results can be directly checked against the data structures. However, maintaining the linker scripts in-sync, handling fragmentation of the firmware code (i.e., huge gaps between the declared sections) and changing the firmware code incur at significant overhead.

Option Two: Let the Firmware Register with a Global Data Structure

This approach is geared to minimize the overhead of maintaining the memory locations. In this scenario the firmware voluntarily registers with the test code, placing the information into a shared data-structure. In this scenario, two locations need to be shared across the firmware and the test-code.

• The location of the registration routine that is to be implemented by the firmware code.
• The location of the global data structure that contains the test information.

In addition the specification of the test data structure as well as the registration interface need to be shared among the two pieces of code. This can be achieved by sharing a common header file.

This scenario is useful when the test information is known beforehand. It also enables testing slightly modified versions of the firmware because the test code does not need to be aware of the location of the primitives or data structures. The firmware voluntarily provides this information through the registration routine. Both linker scripts define the section of the global data structure. Both linker scripts define the sections of the global data structure and registration routine. In order to avoid adverse effects the test code may prevent explicit writing to the registration routine. Here the test linker script:

MEMORY
{
    sram     : ORIGIN = 0x10200000, LENGTH = 1M
}

__FIRMWARE_ = 0x10100000;

/* firmware's test registration routine */
__REGISTER_TEST__ = 0x10300000;

SECTIONS
{
...
    /* shared test data goes here */
    __TEST_DATA__ 0x10400000:
    {
    *(__TEST_DATA__)
    }
}

And the firmware linker script looks like this:

MEMORY
{
    sram     : ORIGIN = 0x10100000, LENGTH = 1M
}

SECTIONS
{
...
/* firmware's test registration routine */
__REGISTER_TEST__ 0x10300000:
    {
    *(__REGISTER_TEST__)
    }

/* shared test data goes here */
__TEST_DATA__ 0x10400000:
    {
    *(__TEST_DATA__)
    }
}

The shared header among the firmware and the test code defining the structure of the shared data structure and the registration interface:

typedef struct {
void (*firmware_fun)();
} TestFixture;

TestFixture __attribute__ ((section("__TEST_DATA__"))) gTestFixture;

extern void __REGISTER_TEST__();

The test code inside the bootloader simply registers with the firmware and invokes the required primitives of the firmware:

int main(void)
{
    debug_puts("Inside boot-loader test suite!\r\n");

    /* register test structure */
    __REGISTER_TEST__();
    /* execute a firmware function to test */
    gTestFixture.firmware_fun();

    debug_puts("Inside boot-loader again!\r\n");

    return 0;
}

The location of the registration code inside the firmware is pinned as follows:

void  __attribute__ ((section ("__REGISTER_TEST__"))) test_register() {
gTestFixture.firmware_fun = myprimitive;
}

Merging the test suite with the firmware and executing it in the coldfire simulator, as described in Part one of this tutorial, yields the following output. The test code can be obtained from option2.zip (see attachments below).

Use CTRL-C (SIGINT) to cause autovector interrupt 7 (return to monitor)
Loading memory modules...
Loading board configuration...
  Opened [/usr/local/coldfire/share/coldfire/cjdesign-5307.board]
Board ID: CJDesign
CPU: 5307 (Motorola Coldfire 5307)
  unimplemented instructions: CPUSHL PULSE WDDATA WDEBUG
  69 instructions registered
  building instruction cache... done.
Memory segments: dram  timer0  timer1  uart0(on port 5206)
           uart1(on port 5207)  sim  flash  sram

!!! Remember to telnet to the above ports if you want to see any output!
Hard Reset...
Initializing monitor...
Enter 'help' for help.
dBug> dl merged.s19
Downloading S-Record...
Done downloading S-Record.
dBug> go 0x10200000
... telnet on uart0
Inside boot-loader test suite!
Inside firmware primitive!
Inside boot-loader again!

Option Three: Only Register with the Firmware

This option obviates the use of a shared data structure and may be used in the case where the test code has access to enough memory to allocate its own data structures. Usually, the constraints on boot loaders and such testers are relatively low that this is not an option. In this case we only have to share parts of the test data structure and the specification of the registration interface. The only difference to the previous example is that now the registration routine takes a pointer to the test structure provided by the test code. In addition only the prefix of the structure needs to be identical across the two pieces of code. For example the test code may choose to store test results in the structure that are hidden from the firmware. Let’s look at an example. As follows the specification of the test structure for the bootloader. Notice the removal of the pinned global variable and the additional value.

typedef struct {
void (*firmware_fun)();
int someTestingValue;
} TestFixture;

extern void __REGISTER_TEST__(TestFixture *tests);

And here the specification of the test structure for the firmware:

typedef struct {
void (*firmware_fun)();
} TestFixture;

This time the test definition structure is allocated by the bootloader and passed in as parameter to the firmware. The example code is included in option3.zip (see attachments below). The interaction with the simulator is identical to the previous example.

Step Three: Dynamic Tests

In many cases the space constraints for the test code are limited. So flashing an entire precompiled suite of tests may be impossible or undesirable. In order to overcome this issue you may want to consider dynamic tests. In this scenario only individual tests are uploaded through the boot loader and executed against the firmware. This approach can be combined with all of the above methods. In addition to the specified memory sections required by the test procedure (see Step two) you also need to define a section that holds the dynamic code. In the boot loader this section is referenced as array to store and replace the code and as function pointer to execute the test. The following example shows this with an already written array that is stored at the location of the test-code. The example code of the test is shown as follows:

/* dynamically loaded structure */
unsigned char __attribute__ ((section("__TEST_CODE__")))code [] = {
...
};
...
extern int __TEST_CODE__();
extern unsigned char * code;

...

int main(void)
{
  debug_puts("Inside boot-loader test suite!\r\n");

  /* perform test from loaded array */
  __TEST_CODE__();

  debug_puts("Inside boot-loader again!\r\n");

  return 0;
}

To build the test code, you link it using a script that places the text, data and bss segment at the location of the test-code; or pin the test function explicitly to the section of the test code of the boot loader. The former option is useful, when the tests consist of several subroutine calls. The latter is useful for unit tests consisting of a single function call, having no global data structures. In addition, you might want to consider allocating a separate stack inside the test routine to avoid corruption.

The array containing the test cases can be created from the SREC-S19 file of the compiled test-case. The python script srec_to_c.py included in the sample code performs that conversion for continous S19 files.

Discussion

In this tutorial, we have shown how to leverage the boot-loader-firmware-paradigm introduced in the previous part of this tutorial to perform dynamic firmware testing. It is up to the software engineer to select the degree to which the firmware has to interact with the tests to register with the test-suite.

In addition to the procedures shown, you may want to consider using your host systems timers to check the progress of executed tests. If the firmware does not register with the tests properly or a test becomes stalled, the boot loader can be able to recover itself using a timer interrupt.

A substantial risk using these approaches is that the firmware and the bootloader still share the same address space. You may want to consider introducing explicit checks that ensure that the firmware does not touch boot loader code (i.e., through heap operations) and vice-versa.

The srec_to_c.py script performs the transformation of the test-case’s SREC/S19 files to the array. You can modify this script to create binary images that are uploaded through your devices interface.

Sample Code:

• option2.zip
• option3.zip
• dynamic_tests.zip

On Designing Boot Loaders and Grey-box-Testing Firmware (Part 1/2)

I am currently TAing SE350. The students’ deliverable is a small real-time executive kernel (RTX) that runs on a Freescale Coldfire chip. We got the idea of building an automated embedded test suite for the students’ term projects. However, instead of having to compile the students’ code from scratch we would only want to take their firmware binary directly and test it. This testing would involve injecting several test processes in the students’ OS. These tests would stress their implementation and dump the results to a serial port of the actual Coldfire board. Having worked in the embedded field this problem is similar to integrating boot-loaders with firmware. In the project, the boot-loader is the testing code and the actual firmware is the code to be tested.

You end up with two pieces of binary code that will be programmed into your device. So the challenge is to make them talk to each other. In the case of the boot-loader, you have the boot-loader invoking the firmware, and in the case of the testing code the testing code invokes the RTX.

In the following sections, I describe the steps for…

• Building a tool-chain,
• Developing the boot-loader-, firmware-code,
• And integrating the different SREC/S19 files

In the second part I will describe how to leverage the established framework to design a native testing suite.

Step 1: What tools do I need?

In order to run stuff on bare (i.e., no existing OS) chips you need to have a tool chain that translates your source code into ELF files (ELF = Executable and linkable format) and SREC/S19 files for flashing it onto the device. We need:

• Binutils,
• The GNU C Compiler,
• And the Coldfire simulator.

A detailed description, how to build these tools is already here on my website.

Step 2: Where to put my firmware code?

If you are going to integrate two pieces of code, you need to make sure they do not overlap in flash and do not access themselves in an undesired fashion. Since you are developing on the bare hardware, you actually have complete control over the former property and can enforce the latter by a careful code design. Your generated ELF file will consist of three major sections, as follows:

• The text segment (.text), where your executable code goes,
• The data segment (.data), where initialized global variables go,
• The BSS segment (.bss), where uninitialized global variables go.

Note that the BSS segment exists for some historic reason and in almost all OS lectures it is implied by the data segment (i.e. data := data + BSS). By convention the text segment starts at a lower address than data and BSS segments. When your program is executed the data the values of the data and BSS segments are copied into the main memory. However the size is not established at runtime. The program’s stack for function calls and local variables resides on the heap which is by convention allocated after the BSS segment and grows dynamically. The GNU tool-chain you just build includes the GNU Linker that allows specifying these locations explicitly by linker scripts (i.e., LD files). GNU LD files have a simple structure describing:

• The memory banks and locations,
• How to spread your code across those locations.

The following simple example file describes an embedded system (i.e. in my case: CJDesign’s MCF5307 board). Most evaluation boards, like mine, come with a huge SRAM and actually have a ROM that allows you to load stuff in main memory. As such, we will dump all code into SRAM for testing purposes. The following example specifies the assignment 1 MB at address 0x10100000 to SRAM and dumps all sections of the code into that segment. Hint the space after the section names is required to ensure the uniqueness of the names. The actual code will execute from the SRAM start address, which is 0x10100000.

/* firmware.ld */
MEMORY
{
  sram        : ORIGIN = 0x10100000, LENGTH = 1M
}

SECTIONS
{
  .text :
  {
    *(.text)
    *(.rodata*)
  } > sram

  .data :
  {
    *(.data)
  } > sram

  .bss :
  {
    *(.bss)
  } > sram
}

A note for SE350 students: Guys please do not attempt to hack the linker file provided by the course. You may run into serious trouble by using my linker script or hacking the existing one!

Step 3: Building your firmware

To compile and link your source (firmware.c) with this file, use the following command.

m68k-elf-gcc -Tfirmware.ld -Map=firmware.map –o firmware.elf firmware.c

You may want to generate a listing of the file to see that everything is at the expected location, as follows:

m68k-elf-objdump -xdC firmware.bin > firmware.lst

In order to flash or deliver this file to the customer we actually need to convert it into the Motorola S19/SREC file as follows.

m68k-elf-objcopy --output-format=srec firmware.bin firmware.s19

Step 4: Building the other piece of code

What’s left to build is the boot-loader. In order to ensure distinct flash and memory regions you need to provide another linker script that puts all the boot-loader code into a different location than the other code. A wise choice is to put this code as far away from the actual firmware as possible, possibly at the end of the available memory. The following code offsets the memory bank by 1MB and dumps the code there.

/* bootloader.ld */
MEMORY
{
  sram        : ORIGIN = 0x10200000, LENGTH = 1M
}

__FIRMWARE__ = 0x10100000;

SECTIONS
{
  .text :
  {
    *(.text)
    *(.rodata*)
  } > sram

  .data :
  {
    *(.data)
  } > sram

  .bss :
  {
    *(.bss)
  } > sram
}

In order to invoke the firmware we need to put a symbol inside the linker script that identifies the expected starting address of the firmware, which is in this case called firmware. This symbol can be used from the C-code directly as function call. In order to avoid any compilation warnings you should forward declare this function as external. The compilation and transformation into the S19 file is analog to creating the firmware code. You should end up with a bootloader.s19.

Step 5: Throwing things together

In practice when you build an embedded device. It should have the boot-loader and some firmware programmed in when it leaves assembly. In many cases the interface that the end-user has to the device (i.e. a USB connector) is different from what you have during assembly (e.g., an in-system flash tool). As such it is necessary to throw the boot-loader and the firmware together.

The S19 format is a simple ASCII data exchange format, originally developed by Motorola, for executable code. It is widely accepted by most programmers for Motorola-based embedded systems. The files are processed line by line; each line contains a control code, a record size, an address, an optional data sequence and a checksum. You find the details here.

GNU Object Copy usually outputs:

• A block header (S0),
• A sequence of data records (S1-S3)
• And the start-address (S5-S9).

The block header usually contains the name of the file (e.g., firmware.s19 or bootloader.s19). Most ROM loaders on evaluation boards will actually processes start address record, which is in our case the declared origin of the SRAM, and fail to load if they do not find it, so it needs to be included.

So in order to put the boot-loader and the firmware together into one file you need to provide one header, the data of both programs and one starting address:

• Header: any of the firmware/boot-loader, or a custom header (see below)
• Data: concatenate the data records of both original programs
• Starting address: the start address of the boot-loader

Step 5a: Composing your own header

Yes, geeky people like me actually like implementing checksum algorithms and brand their creation. In order to do so we need to dive into the checksum procedure used by S-records. According to Wikipedia the checksum is “[…]the least significant byte of ones' complement of the sum of the values represented by the two hex digit pairs for the byte count, address and data fields.” So guys, its time to dig out those algorithm-class-notes and figure that out, … oh wait …, found it:

• Sum up all bytes starting from the byte count record.
• Set: checksum = 0xFF – (0x00FF & sum)

Why the hell would anyone use such a check-summing algorithm? The answer is simple: It can be easily checked! While processing the S19 records, you can actually sum everything up, including the provided checksum and should get 0xFF. That is a simple compare operation and that can be evaluated in no time.

Step 6: Testing your Creation

If you build the Coldfire simulator according to my instructions you can invoke the simulator as follows…

coldfire --board cjdesign-5307.board

and load the code like this…

Use CTRL-C (SIGINT) to cause autovector interrupt 7 (return to monitor)
Loading memory modules...
Loading board configuration...
        Opened [/usr/local/coldfire/share/coldfire/cjdesign-5307.board]
Board ID: CJDesign
CPU: 5307 (Motorola Coldfire 5307)
        unimplemented instructions: CPUSHL PULSE WDDATA WDEBUG
        69 instructions registered
        building instruction cache... done.

Memory segments: dram  timer0  timer1  uart0(on port 5206)
                 uart1(on port 5207)  sim  flash  sram

!!! Remember to telnet to the above ports if you want to see any output!

Hard Reset...
Initializing monitor...
Enter 'help' for help.
dBug> dl merged.s19
Downloading S-Record...
Done downloading S-Record.

dBug> go 0x10100000 <- the actual firmware
... some garbage, because RTS returns to nowhere...
dBug> go 0x10200000 <- the boot-loader invoking the firmware

You should yield the following output on the terminal (telnet localhost 5206).

Trying ::1...
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.

uart0
Inside firmware! <- 1st go of the firmware
Inside boot-loader! <- 2nd go inside firmware!
Inside firmware!
Back in boot-loader!

Discussion

In this part of the how-to I explained the basics of building two pieces of binary Coldfire code and integrating them into a single file that can be processed by most programmers and ROM-loaders. A popular application is the integration of boot-loader and firmware code for embedded system assembly. Another application is embedded grey box testing. In this technique, instead of a boot-loader a test-suite is evaluated against the firmware to check for potential defects. In the next post, I’ll describe how to design such a test framework.

You can find the sample code of this post here. The code will contain some modified linker scripts that deal with particular alignment problems of the simulator. Furthermore, the boot-loader and the firmware should have different stacks so some assembly files have been added to do so. The S19 merging is done by the python script merge.py.

References and Sample Code

• Sample Code
• My build instructions for the Coldfire GCC toolchain
• GNU linker script documentation
• S19/SREC format description
• Infos on text-, data-, and bss-segments
• A comprehensive Coldfire simulator

Beginning the Blog

I recently got intrigued by the idea of having my own Blog and just started this one. My Blog will be complementary to my website, giving hints and useful tips about surviving Computer Engineering grad school and several challenges of the daily life. I also want to provide resources for undergraduate students attending tutorials that I am co-hosting.

As many people I know might have suspected, I am not Canadian. I am originally from Germany. I studied Computer Systems in Engineering (CSE) there and discovered the University of Waterloo during a four month internship. After finishing grad school in Germany, I decided to take on a PhD in Waterloo. I am currently researching error detection and fault diagnosis in business information systems.

My hobbies are working on old Diesel-Mercs, Goju Ryu Karate and technical challenges, including, building your own car-alarm system or custom CNC machines, hacking mobile devices and hanging out with model engineers. Future posts of this Blog will, therefore, probably be a mixture of these topics and my research interests.