Tools, Testing, & Virtual Systems

Simics 4.8 is Here

By Jakob Engblom

Simics 4.8 is now generally available for old and new users to enjoy. I will be doing a series of blog posts going into the details on what is new and improved in this release. Simics 4.8 represents a significant improvement in the Simics user interface and collaboration features, as well as tweaks to the simulator performance, debugger, and modeling workflow, so there  is quite a bit to talk about. We start off with an overview of the news.

The most visible new functions in Simics 4.8 are found in the Eclipse user interface. We have added several new views and features to help users gain insight into their simulations, debug more efficiently, ease device modeling, and communicate within and between teams. We have also added some significant new performance technologies and more collaboration features to Simics checkpoints.

Insight

The System Editor provides a GUI display of the hierarchy of components and devices that make up a Simics target system, making it much easier to understand how a system is constructed. It lets you inspect the properties of all parts of the system, and also to make changes to the setup including tasks like adding in new PCI cards or connecting and disconnecting network cables. TheDevice Register view provides information on the bit fields in a device register, making it easier to find the value of flags and other bit fields. I will discuss the details of the System Editor in an upcoming blog post.

Modeling

Modeling support in Eclipse has been extended in Simics 4.8, in particular with the ability to run device unit tests and to browse example source code. In the screenshot below, we see the Test Runner in the upper-right hand corner, and the Sample Device browser below it. The Eclipse “New Sample Device” wizard creates new devices (and other modules) based on the examples provided with Simics (or just an empty skeleton if that is all you need). The Sample Device view lets you look at the example code without necessarily creating a new device model in your own workspace, which is quite convenient.

Syntax highlighting for Simics DML is provided by the Simics Eclipse plugins. If you want syntax highlighting for Python code, it is simple to add a Python development environment to Eclipse. The popular PyDev environment works just fine with Simics, as would be expected from well-behaved Eclipse plugins.

Debugger

Building on TCF-based debugger, we have added several new views to the Simics Eclipse UI to help debug and analyze a system more efficiently. 

The most innovative view is the Stop Log, where the debugger notes where the execution has stopped and the time since the last stop. We have noted that it is quite easy to get lost in time and space when using reverse execution. As you move back and forth in time, just where are you and how did you get where you are? While the timeline view tells you where you are, the stop log tells you how you got there. Here is a simple example from a reverse debug session:

Note how we first run the execution forwards for 177 thousand steps (instructions), and then turn around and reverse back some 79 thousand steps to hit a breakpoint. After that, we finished up by doing some system-level single steps forwards and backwards. In this way, it is very easy to tell if you hit a breakpoint close in time, or if you misunderstood the situation and suddenly jumped way back in the execution history of the system. It makes it much easier to understand just where in time you are, and the debug actions that got you here.

The Symbol Browser is a TCF feature that was added to Simics 4.8 (and which is also rolling out in the Simics 4.6 Eclipse debugger). It makes it possible to search the debug information loaded for a target system to find particular symbols, variables, and functions. It provides an efficient workflow for setting breakpoints on functions and variable accesses, as well as a way to understand the symbols loaded and where they are located. This helps in working out low-level debug scenarios where you might have to manually relocate symbols or understand where something is loaded or mapped.

Collaboration

The Simics checkpoint system now includes the ability to include a recording of an execution as part of a checkpoint. This means that rather than just communicating the instantaneous state of the system at a single point in time, checkpoints can now communicate the system execution from a period of time. Checkpoints in Simics 4.8 can thus be considered like a movie recording of the execution of a system, making it very simple to show team members and others just what has been observed in a Simics run.

Users can also add comments to the simulation as it executes, attaching little notes of information to certain points in time. These comments are stored in checkpoints and provide a persistent log of major operations on the system, as defined by the user.

The collaboration features of Simics 4.8 will be explored in more depth in a future blog post.

Performance

There are some new performance technologies debuting in Simics 4.8.

First of all, we have automatic hypersimulation. Hypersimulation is the ability of Simics to run very quickly forward when nothing is happening in the virtual system. Essentially, since Simics has total control over the target, when the target software is idling, it can skip ahead to the next interrupt, device action, or timer event in the simulated system. Simics has always exploited simple waiting patterns like a branch-to-self instruction, the x86 HLT instruction, and a Power Architecture processor going into nap mode. With Simics 4.8, it can also analyze the instruction stream and automatically detect loops that do nothing, automatically turning them into hypersimulation. This ability catches most typical OS idle loops, and brings marked speed increases to many target systems that used to idle poorly.

A second technology is the use of the host MMU to simulate the target MMU, which reduces the overhead of MMU simulation for certain types of target code. This has significant effect on the performance of code that makes a lot of memory accesses. A third technology is the offloading of the Simics ISS JIT engine to a second host core, reducing the performance jitter resulting from the JIT compiler alternating with the main execution thread of an ISS.

Taken together, Simics 4.8 keeps advancing the performance of Simics, keeping Simics at the forefront of fast virtual platform instruction set simulation.

For additional information from Wind River, visit us on Facebook. 

Serving Windows Files from a Simics Quick-Start Platform

By Jakob Engblom

Windows file sharing has always felt a bit magical to me. I use it all the time, certainly, but I never quite understood how it worked; it was just this big chunk of Microsoft protocol that felt like it really did not want to talk to other types of operating systems. Sure, I have used the open-source "samba" server for a long time with great success… but it always seemed to suffer from issues with access rights (probably the fault of me and server setup and mixing Unix and Windows accounts, not a fault in the server itself).

With this background, I was really delighted and  surprised when I managed to almost effortlessly get a Simics target to share and serve files to my Windows host. A big-endian Power Architecture QSP target at that, running VxWorks, how cool isn’t that? The key to the puzzle was the Visuality NQ Server from Visuality Systems Ltd. in Israel. It just worked, and let me try some interesting and educational setups.

The setup I used is shown in the picture below. I have a Simics QSP for PPC (Power), running VxWorks 6.9.2. On top if this, I run the Visuality CIFS NQ version 7.00 Server software. The QSP target is on a virtual network, and this network is also connected to the host (otherwise, talking to it from the host would have been kind of hard). In some development work, we also used Wind River Workbench talking to a debug agent in the target VxWorks to debug the setup and load the server as a loadable kernel module. Basically, Simics provides the equivalent of a generic Power Architecture development board. The communication between the targets and the host is done using CIFS/SMB/SMB2 protocol. This protocol is natively supported in Windows while NQ  Server delivers it to the embedded/mobile world.  

When I opened up a Windows Explorer and directed it to \\10.10.0.2\, the view below results. We can see the default demo files included on the tffs-formatted flash disk image used with the QSP VxWorks setup (mounted as /tffs0 in VxWorks). The file listing from the VxWorks serial console is the same as the file listing seen in Windows explorer. My biggest issue here was just to convince Windows that the new network that showed up at 10.10.0.x was a friendly one that should be allowed to connect over CIFS to the host machine. For very good reasons, Windows does not necessarily consider an unknown network friendly, so I had tell it my Simics virtual network was really my home network.

This setup also lets us modify the files on the target. We can drag in new files, open files for editing and save the changes, and delete files. Once the target file system was changed, we saved the contents of the changed file system as a diff file which was added to the base image during the system setup. This was used in the next step to provide multiple target machines with individual persistent disk contents.

Indeed, the next step was to try to run a network of machines inside of Simics. This was very easy to setup. Once the targets were booted and up, and we tried starting the Visuality NQ servers, we hit a snag. If the server was started simultaneously on all the machines (using target serial-port scripted input it is trivial to type the same command at the same exact time on all target machines), all server instances immediately shut down. Strange. If we started first one, and then a second server, the first one stayed up and the second shut down. The reason turned out to be that all CIFS nodes need to have (actually the guilty protocols are NetBIOS and DNS but let’s call this CIFS for a sake of simplicity) a unique name, and the VxWorks instances we had here did not have any name set at all. Thus, a name collision ensued. The solution was simple enough: provide each target with a unique name from the scripted command-line setup.

What this demonstrates is that a virtual platform and virtual network lets you discover properties of the software that you might not have discovered until much later on hardware. Had we been working with hardware boards, it is quite unlikely that we would have tried a multiple-machine test, as that is a bit more work to do in hardware (scrounge a second board from some other developer, get it configured, hook into your little local test network, and try to bring it up). In Simics, we just made the script loop setting up target machines run until 2 instead of 1 (and we could just as well have made it run to 10 or 100).

Once this was sorted, we could mount multiple servers from Windows, each with their own individualized disk contents, as shown in this screenshot:

You can see the scripting of the startup setting the IP addresses and names of the boards, before starting the server with the nqStart command. This command starts both of the NQ daemon processes: NetBIOS and SMB. The setup looks like this in Simics:

Apart from testing and demonstrating the nice software from Visuality, this exercise provides excellent proof of some classic Simics values:

• A Simics QSP synthetic platform is a perfect tool to test and run applications and middleware that need the OS API and a particular architecture.
• A Simics QSP provided a stable proven VxWorks on top of which the Visuality software could be run immediately with network access and a disk with a file system, with no need to worry about choosing and configuring a particular target BSP and loading software and formatting a disk.
• You can build virtual networks of machines, and connect these to the real world either individually or as a whole group.
• The contents of target file systems are easy to customize, and the changes can be saved permanently as disk images (but you do not have to save them in case you badly messed up the data, like I did in my first attempts).
• Target scripting that automates the boot and setup of the target systems, including individual scripts for each target machine that makes each machine different from the common baseline.

Finally, for Visuality Systems, Simics provides simple access to a big-endian cross-target platform to test their software and its portability. It makes access to arbitrary architectures as easy as running a software program, rather than having to procure, configure, and maintain hardware development boards.

 

For additional information from Wind River, visit us on Facebook. 

A Better way to Connect: TCF and Simics

By Jakob Engblom

How do you actually connect an integrated development environment or a debugger to a target system? This question is more complicated than it might seem to the uninitiated outsider. Traditionally, a range of protocols have been used to connect the development host to a target, most of them vendor-proprietary, and often specialized for a particular purpose (such as debug, downloading code, or uploading profile data). However, there is a better alternative available today, the open-source TCF, Target Connection Framework. The TCF is much more than a debugger connection.  Based on decades of industry experience as to what you actually need to do with a target, TCF combines everything on a single connection: analysis, testing, configuration, control, provisioning, inspection, tracing, debugging, and anything else you might think of. Simics is making good use of TCF to simplify the connection between the Simics runtime engine and the Simics Eclipse-based GUI. In this blog post, I will go into how TCF is used with Simics and what it has enabled us to do that would have been very difficult without the TCF.

First, we need a little background on TCF itself. The TCF is a project in Eclipse, with contributions from Wind River, Xilinx, and others. The TCF protocol is service-based, and each target exposes the services that it supports to the host. The host can then activate the appropriate functionality, based on what the target reports. In this way, there is no need for the host to know very much about the target a priori, as all its capabilites are reported dynamically after a connection has been setup.

Anyway, on to Simics and TCF. Given what TCF is, how did we use it with Simics?

When using Simics from Eclipse, there are actually two processes running. There is the Simics-common process that contains the actual Simics simulator and the Eclipse process that contains the GUI. These two processes obviously need to be connected to each to allow the GUI to display the state of the simulation and control it.

As shown in the picture above, this connection is achieved using the TCF protocol over a TCP/IP connection.  Note that there always just a single connection, regardless of what you are doing with Simics and how many target machines the Simics session contains.

The screenshot above shows some of the basic Simics views in Eclipse, for a simple setup containing four target machines (see a previous blog post for more on this setup, and a video of the debugger in action). All the views get their content over the single TCF connection to Simics, for all the target systems. This includes not just  basic functions like starting and stopping the target, but also the system panel view showing the front panels of the targets, the device register viewer, the target information view, and the interactive Simics command-line (not shown above).  When we attach a debugger to this setup, the same TCF connection is used to also carry the debug session for the entire target system (all four target machines).

Without TCF, we would have needed many separate connections between Simics and Eclipse. Typically, one connection to control the Simics simulation, and then one debug connection to each target system or individual OS on a target system. It would look something like this:

Each of these connections would be established separately, and they would need to be coordinated both in Simics and in Eclipse to avoid interfering with each other. For example, even basic run control gets horribly complex in a situation where you have multiple debuggers trying to interact with the same target. Gdb, for example, has a very hard time with targets that start and stop under the control of other debuggers or control mechanisms – it is basically designed to assume that there is only one controlling debugger, not a whole bunch of equals. With TCF, run control is one service shared across all the targets (Simics starts and stops them all as a unit, remember?) and functions in the Simics GUI. It is even possible to connect a second Eclipse debugger to the same Simics without any issue, since TCF makes sure that the target system is the authority on its state. A funny effect of this is that anything typed on the Simics command-line in the first Eclipse is mirrored in the second Eclipse, since all state changes are mirrored via the Simics TCF server.

Thanks to TCF, we have been able to build a system-level debugger for Simics that integrates perfectly with the non-debugger features of Simics. When you reverse the simulation from the Simics control view, the debugger understands what happens. When the debugger stops the run on a breakpoint, the Simics controls update and the Simics command-line notes that the simulation is stopped. When a Simics script detects an erroneous state in the target and stops the simulation, the debugger immediately shows the location in the code where execution has stopped. If a Simics advanced breakpoint (such as breaking on log messages) stops the execution, the debugger kicks in and shows where in the code the breakpoint hit.

When used for debugging, TCF brings some unique benefits. TCF is capable of managing an arbitrarily complex target system over a single connection. There is no requirement that the target is homogeneous or uses a single OS image. With Simics as the backend, the debug session can cover multiple boards, each with multiple processors, potentially running multiple OSes on each board. Such a setup was used for the demo referenced above, and you can see it in action here.  With other debugger protocols, each board would have required a separate connection, and a separate debugger would have been needed to connect to each board since they tend to be target-architecture-specific. With TCF, system level debug across a four-machine networked setup featuring two different architectures and two different operating systems was trivial to realize.

Another important aspect of TCF is that it is designed to allow services to run anywhere along a daisy chain of units from the target to the final debugger. With Simics, this is not used, but when using a hardware setup, it is possible to run a simple agent on a target and add features like OS awareness and symbol lookup in a value-add process along the way. It would look like this, and note that we can also carry the data needed to drive analysis tools like performance profilers and event tracers over the same connection:

Still, the modularity of TCF is used with Simics. Thanks to the location-neutrality of TCF services, the debugger smarts are actually located within the Simics process. They might just as well have been run in their own process, but by putting them inside of Simics, the debugger functionality is made available to Simics scripts. This means that Simics command-line scripts, Python scripts, and arbitrary Simics modules in Python, C, or C++ can all make use of the debugger functions like OS awareness and symbol lookup. The debugger is also available from the Simics command-line, giving users a very powerful debug system that has direct access to all parts of the target. This debug system is automatically in sync with the GUI debugger, thanks to TCF, allowing a seamless mix of classic inside-of-Simics debug and debug from the Eclipse GUI.

The performance of the debugger is greatly improved by being located within Simics, as the evaluation of conditional breakpoints and other features that require interaction between debugger and target is done locally at very high speed. This is in contrast to protocols like gdb-serial where the separate debugger process has to be invoked to evaluate conditional breakpoints and do other debug tasks, leading to much higher latency and lower performance. The debugger is also able to take advantage of Simics OS awareness features like detecting when a process or thread is being scheduled by the OS. This would simply not be possible with a remote debugger, as the latency of communication would render it totally useless.

To summarize, TCF has allowed us to build a very robust and powerful integrated debugger and GUI for Simics, with a single consistent notion of the state of the target simulation and a single connection between the simulation backend and the GUI frontend.

For additional information from Wind River, visit us on Facebook.

Debug Quicker with Simics (video demo)

By Jakob Engblom

Late last year, I presented a one-hour webinar on how Simics lets you “resolve bugs in minutes instead of weeks.” Part of that webinar were two Simics demos that show Simics in action, from the first booting of a target system through loading software onto it and debugging a nasty crash in a server program. The webinar demos are now available as a single Youtube movie, on the Wind River Youtube channel.

The target system used in the demo is a heterogeneous network of four machines. Two ARM-based and two PPC-based. Two of them are running a client application, and two are running a server application. They are all connected on the same virtual Ethernet network, and the client applications can talk to the server applications over the network.

In the demo, we test how the server and client applications work when ported from PPC (where they originated) to ARM. All the possible combinations of client to server connections are tested, and in the process we make use of the key capabilities of Simics:

• Network simulation
• Checkpointing
• Automated boot and setup of target systems
• Scripted testing, automatically exploring all combinations of (ARM, PPC) and (client, server)
• Repeatability (see also my previous blog posts here and here)
• Bug transportation via checkpoints and scripting
• Eclipse CDT debugger (with reverse)
• Reverse execution
• Reverse debugging, across the entire system of four machines
• Synchronous system stop
• Network traffic inspection, including feeding data to Wireshark

This demo uses the Simics Quick Start Platforms, showing how you can debug application software and resolve their bugs without needing a model of the complete target system. See my previous blog post for more on how you can use QSP to quickly get started reaping the benefits from virtual platforms and simulation.

If you want to see more about reverse execution and debugging with Simics, we have another demo movie available that also shows to debug with an integrated physics model.

You can go to the full seminar recorded here by Open Systems Media.

For additional information from Wind River, visit us on Facebook.

Debugging Simics -- on Simics

By Jakob Engblom

I often write and talk about how useful Simics is for debugging concurrency bugs and glitches in multithreaded and multicore systems. Recently, we had a case where we proved this on a very complex application, namely Simics itself. This nicely demonstrated both the recursive completeness of Simics, and its usefulness for conquering tricky bugs in complex software.

The beginning of this story is a bug in Simics, triggered by a certain Simics configuration. The Simics target is a Power Architecture machine, running some bare-metal test code testing the processor simulation. Occasionally, this setup would crash Simics, due to some bug in Simics or the models. It was a difficult bug to track down, as it only happened in one run out of 50 or so. When attaching a debugger to try to diagnose it, it invariably did not happen (a classic Heisenbug).

Simics is the perfect tool to diagnose these kinds of issues, but in order to do that, we had to get the failing program into Simics. I.e., running Simics on Simics. The first step was to create a duplicate of the development host, inside of Simics. This was fairly simple, just a matter of installing a Fedora 16 standard Linux on an 8-core Intel target. Once the Linux was installed and booted, a checkpoint of the system was taken.

Next, the development code tree from the host was packaged up as a tar file and put on a DVD image file. Simics was started from the checkpoint of the booted target system, and the DVD image inserted into the virtual DVD drive and mounted by the Fedora Linux running on Simics. The tar file was copied to the file system on the target, and unpacked. A new checkpoint was taken after the Simics installation was thus completed and Simics could run on Simics. The result at this point was a completely self-contained, controllable, and repeatable environment.

The screenshot below shows Simics running on Simics, with the same desktop wallpaper being used for both the host and outer Simics Fedora system:

The next step was to replicate the bug inside of Simics. To this end, a shell command was used that repeatedly ran the inner Simics until the bug hit (obviously, this session was started from the checkpoint after the Simics installation).

The result was this setup, ready to run Simics until the bug hit:

To recap, we have Simics running on Simics. The “inner Simics” is configured with the Power Architecture setup that resulted in a crash on the host, and the “outer Simics” is running Fedora 16, providing a virtual replica of the development host (but inside of Simics).  

Additional scripting in the outer Simics was used to make the search for and replication of the bug more efficient.

• The Simics script varied the time slices given to the processors in the IA target system. This caused greater variation in scheduling of concurrent processes and threads in the Simics-simulated Fedora 16 OS, which in turn helped provoke the bug so that it appeared faster (after fewer runs of the inner Simics).
• A checkpoint was taken after the inner Simics had been started and the timing variation applied to the IA processors – but before it had started executing the test case. This meant that a checkpoint would be available that led straight to the bug, with no need to do any warm-up of the target or particular configuration of Simics. The checkpoint would in effect be a self-contained bug report for the issue.
• A magic instruction (blue star) was planted in the segfault handler of the inner Simics, making it very simple to catch the crash of the inner Simics. Often, using a magic instruction like this is simpler than trying to capture the right page fault or putting a breakpoint at the right place. A magic instruction is a live marker in the code that will always trigger, regardless of debug information or OS awareness. Furthermore, it has no overhead until it hits.

Eventually, after some 20 runs of the inner Simics, the bug was triggered. Thanks to the checkpoint and Simics repeatability, reproducing the bug is trivial. The Simics crash could now be reproduced any number of times, and it was time to go debug and figure out why Simics crash. An occasional Heisenbug had been converted into a 100% reproducible Bohrbug.

The first step of debugging was to figure out the mapping of the many dynamically loaded modules in the inner Simics. This was done by running the outer Simics and sending a Ctrl-Z to the Fedora shell, pausing the inner Simics. Then, the /proc file system on the Fedora Linux running on Simics was interrogated to find the load addresses. Since the checkpoint was taken after Simics was started, we know that this is the mapping in the software setup found in the checkpoint. Every time the checkpoint is opened, the same mapping applies – so the information was saved and used to setup symbolic debug information for the Simics modules used.

The next step of debugging was to open the checkpoint again, turn on reverse execution, and run forward until the magic instruction hit. Then, OS awareness was used to back up until the last time that the inner Simics was running prior to hitting the segfault handler. This placed the execution of the outer Simics at the precise instruction where the inner Simics crashed.

It turned out that Simics was trying to execute code in a location (BCDE) where no code was to be found.

Stepping back one instruction led to a JMP instruction to the location BCDE.

So where did this JMP BCDE come from? It was clearly not part of the static code of Simics, but something that was generated at run time by Simics itself (Simics contains a JIT compiler and thus modifying running code at run time is perfectly expected behavior).

To find out how the bad JMP was created, a memory write breakpoint was put on the instruction (JMP BCDE), and execution reversed. Simics stopped at the point where the “JMP” part of the instruction was written to memory. Doing a stack back trace at this point showed the code that was trying to write a five-byte “JMP XYZQ” instruction into the JIT-generated code stream. Since the breakpoint had hit on the write of the byte containing the JMP instruction code, indicating that the other four bytes (containing the actual JMP target location of XYZQ) were yet to be written when the instruction got executed and Simics crashed.

Stepping forward (on the processor) revealed that a thread switch happened in the inner Simics, and that the incoming thread immediately executed the five-byte JMP instruction, such as it was. Since only the JMP byte had been written, this was a jump to location BCDE, rather than the intended XYZQ (it would also have been OK to execute the original ABDCE code). Thus, the issue was diagnosed to be a read-write race condition, with the twist that the read was an execution of the memory as code and the write a regular data write. As soon as the problem was identified it was of course very easy to fix.

With the same setup, another race condition in Simics was also found and fixed, involving the more common case of multiple concurrent threads updating and reading a shared data structure without sufficient synchronization.

In summary, this blog post has described one instance where Simics was used to find and fix concurrency bugs in a real-world complex software system called Simics. The key to the success was the repeatability that Simics provides, even for timing-related occasional events, along with checkpoints, scripting, reverse execution, and debug facilities.

For additional information from Wind River, visit us on Facebook.

Determinism, Simics, and Flying Piggies

By Jakob Engblom 

In a recent Simics seminar, I was asked about repeatability, variability, determinism and Simics. This is a question that comes up almost every time I present about Simics in front of an audience with testing experience. The people asking the question intuitively think that determinism is a bad thing - since it sounds like it will limit the execution scenarios that will be explored in testing. For a tester, variation is a good thing. However, determinism is not in conflict with variation. And I think I found a perfect illustration of this in a setting that is a bit more accessible and easy to understand than computer simulators. In a computer game, Bad Piggies, from Rovio.  

Bad Piggies is a game based on a physics simulation (not particularly realistic, but still reasonably consistent with everyday experience), where you put together strange contraptions to guide an endearing little pig pilot from the starting point to a goal. What struck me about the game is its incredible sensitivity to inputs, while still being 100% deterministic. To me, this is absolutely analogous to how Simics works (and I guess drawing that analogy indicates a pretty warped mind too).

There are two types on inputs in the game that matter: the (static) configuration of the vehicular contraption that you build, and the interactive inputs you provide during a level to turn on engines, pop balloons, or fire off boxes of TNT. An utterly minor change in the timing of an action can mean the difference between success and failure. On the static side, moving the center of gravity of a vehicle by putting the pilot pig somewhere else can have a huge impact on the behavior. There are levels where all you do is just move the center of gravity around to see which location finally hits the perfect balance.

Still, the game is clearly deterministic. This is particularly obvious in levels where no interactive input is needed. All you do is put the vehicle together and watch it go (roll down a hill, float away on a balloon, or throw the pig by exploding a box of TNT underneath it). In these cases, each game plays out the exact same way, as the physics engine is intentionally and precisely crafted to be deterministic. Whether I play an HD version on an Android tablet or a regular version on a iPod touch, the outcome is the same and the way you clear the levels identical. This is strong determinism.

Is not predetermined, however - when you put a new vehicle together and let it go, you really cannot predict what is going to happen. You might have an idea in mind, and you might hope it does the right thing. But before you play it through, you do not know. It most likely fails on the first attempt, and you go back and tweak the design (in computer programming, this is known as debugging). And try again. Each time, something different will most surely happen, since the setup input is different. There is huge variability, and if we see the game as a way to test the contraptions we put together, there is infinite room for variation on top of the fundamentally deterministic game engine.

Imagine how this would be if the game was really nondeterministic. It would be pretty much unplayable. It would turn into a die-rolling exercise, where you would create the exact same initial conditions,  let it run, and hope that on some run, you would be lucky and get to the goal. Not my idea of fun, exactly. Determinism is clearly good and helpful for testing and development, as long as there is also variability and sensitivity to inputs. But if inputs do not changed, you do not want behavior to change. Normally, computer system are indeed random, and since this is a fact of life, many people make lemonade out of lemons and think of this randomness as a good tool for testing. But when you can do it, avoiding randomness is clearly superior as a way to approach systematic testing.  And as a way to fly computer game pigs to the goal.

Simics works in the same way as the Bad Piggies game. For a static test case like a non-interactive boot of an OS, it will play out the same each time you run it (provided no configuration changes are made). Change the target OS image, and you will get something different. Change the number of processors or the size of memory, and something different will happen. Change the host machine (the machine on which Simics runs), but not the target, and you will get the same result.

If we add uncontrolled interactive inputs to the mix, we will get different results each time. We can make interactive inputs deterministic by scripting or recording them. And given deterministic inputs, the execution will be the same.  This is how Simics achieves perfect repeatability.  Not by limiting what executes and how, but by controlling inputs to a system so that any particular variation can be reproduced.

Taking this one step further, a simulator also allows you to systematically explore issues by programming input variations into scripts. At one extreme, this is fault injection, but even just automatically varying inputs to a program within legal bounds can be very interesting. For example, Simics has been used to provoke OS bugs, or test how a program runs as the number of processor cores in a system is varied.

Repeatability and determinism just mean that we can repeat any execution we happen to chance upon - not that we limit the space that can be explored in testing. For any tester who ever had to try to replicate and report a failed test case that only was seen once, repeatability is a wonderful thing indeed.

For additional information from Wind River, visit us on Facebook.

Simulation is a competitive advantage!

By Michel Genard

The American general election is over. Pundits providing postmortem analysis will continue to generate a ton of studies. Let’s examine one aspect of the election that has already generated some interesting ink. This article in Time Magazine mentions how analytic teams tried to predict election results, even running as many as 66,000 simulations night after night. The Obama campaign managed to create hundreds of models (likely electors) and run election simulations each day to define and validate the “design” of the path to victory. Each morning, after looking at simulation results they would adjust the campaign. This process is recognized as a competitive advantage. Let’s now map this phenomenon to embedded software development. For years, we’ve been making the case that increasing complexity and errors in the back end of development are the kiss of death for OEMs. Fast functional system level simulation is the best path to manage risks, boost productivity and velocity. We constantly receive testimonials from customers indicating that indeed simulation transforms their business, even to the point that it becomes part of the backbone in their process. Modeling at the right level of abstraction (i.e. what the system is supposed to do and not how) and running quick simulations enable developers to run an unlimited number of use cases, validate design choice, start software development sooner, and debug with powerful, science fiction-like features. Business fundamentals have not changed in the last few decades; time to market, quality and security are still top concerns. What has changed is the cost of failure and the imperative to move fast and adjust to customer needs at the speed of their requirement. More than ever, our simulation platform Wind River Simics is here for you. To help customers quickly deploy simulation technologies even further, we introduced the Quick Start Platform with our last release. Let’s make 2013 a year of simulations!

For additional information from Wind River, visit us on Facebook. 

The Role of Tools in Improving Embedded Software Security / Part 3: Mapping the Tools to Activities

By Bill Graham

In the previous posts in this series, Part 1: Automation is the Key and Part 2: Security Improvement and the Software Development Lifecycle, I talked about the connection between the typical embedded device development process and the 5+1 improvement framework for embedded security.  Figure 1 is an illustration of this connection (and discussed in more detail in a previous post).

Figure 1: Mapping the security improvement framework and the device software lifecycle

In this post, I’m going to map out the tools that can help improve security and where they fit in the development lifecycle. Tools have different parts to play at each phase of the lifecycle, in some cases they are used throughout, and in others, their role is key in one phase and less so in others. In terms of security improvement, many of the tools and processes mentioned are not unique. In fact, the ideal situation is where security is considered a first class citizen in the priorities of a project.  In this respect, tools for requirements, modeling and change management are meant to be used in the same fashion and don’t represent unique capabilities required in the 5+1 improvement framework. Again, the better the requirements and risk management, the better the security solution (assuming that security is given the right priority.)

Figure 2 illustrates roughly where each class of tool plays a role in the embedded device lifecycle. In each case, the unique capabilities required for improving security are called out but these don’t preclude the tools used in other areas.

Figure 2: The mapping of major tools categories in the software lifecycle

The Tools

System Simulation

High fidelity, system-wide, comprehensive simulation is an invaluable software development too. State of the art simulators are more than just processor emulators, today they provide full networked system, board, peripheral and processor simulation. The key benefit of system simulation is pulling in your integration and test cycles much early than previously possible. Secure design and system vulnerability can be tested earlier and more often. In addition, simulators offer unique features that real hardware can’t do and the ability to arbitrarily inject faults at any part of the system. An example of a system simulation tool is Wind River’s Simics product.

Integrated Development Environment

The Integrated Development Environment (IDE) is the developer’s desktop. Most developers’ tools integrate into the IDE in order to be visible and usable from this desktop. All of the tools discussed here are integrated with the IDE. IDE’s also provide many tools that are useful in improving security. For example, memory (runtime) analysis tools are critical for finding buffer overflow errors that are the root cause of many security vulnerabilities. System behavior and analysis tools are critical for tracing complex defects – essential for detecting and debugging security issues. An example of an IDE is Wind River Workbench.

Static Analysis

Static analysis tools analyze source (and sometimes binary) code to find defects, security vulnerabilities and other programming issues. These tools can work on existing code bases and on new source as it is written by the developer. The key advantage of using static analysis is that security vulnerabilities are found as soon as the code is written – the cheapest and least riskiest time to find and fix them. In addition, vulnerabilities can be found in “hidden” parts of the code – code that is not executed during traditional testing. Static analysis tools can be run individually within each developer’s IDE and singularly on the project build providing a distributed and centralized analysis capability. Examples of static analysis tools include Coverity’s Security Advisor, Klocwork’s Insight, Programming Research’s QA-C/C++,  and Grammatech’s Codesonar products.

Build and Continuous Integration Tools

Modern iterative and agile development methods require more frequent build and test cycles. Proper tools support for high frequency build and test in order for the productivity and quality gains of new methods to pay off. These tools provide the same benefits for security assessment and testing – security vulnerabilities can be found, fixed and test in a short cycle. As development methods evolve to include secure development, the return on investment for state of the art build and integration tools increases. An example in this area of tools would Electric Cloud’s ElectricAccelerator and ElectricCommander products.

Test Automation and Management Tools

Increased testing effort of developing an embedded device is the largest factor in its schedule and cost impact of improving security. Typically, testing for security vulnerabilities requires additional testing that differs from functional testing in that is attempting to break the system. Most functional testing is looking at most common usage patterns of the device. Security testing is often looking at edge cases, erroneous input, and misuse. In addition, test automation tools are required to improve test efficiency and effectiveness. Security testing will add risk, cost and effort to the testing effort for an embedded device. However, innovation in testing tools has made this impact significantly smaller. An example tool in this category would be Wind River Test Management.

Robustness and Fuzz Testing Tools

Due to the nature of security testing – often requiring out of range and erroneous data - new tools are required. Fuzz testing tools are designed to send malformed data to the device to induce errors. These tools use knowledge of various communication protocols (including specialized embedded control protocols) to create incorrectly formed packets, bad data and various extreme cases. Often this data is enough to induce runtime errors in the device – exposing potential vulnerabilities. These vulnerabilities are previously unknown (so called zero-day vulnerabilities) are especially critical to find and fix. Fuzz testing can be applied well before the device is in final form. Leveraging system simulation, fuzz testing can used in a simulated environment as effectively as it is in the lab.  An example of a fuzz testing product is the security content package for Wind River Test Management (with technology licenses from Codenomicon).

Risk and Threat Management Tools

It’s likely that few embedded development projects are currently using automated risk and threat management tools. These tools are often used in highly safety critical projects where risk management processes are stringent and detailed traceability is required. However, these tools can prove valuable to any team that needs to maintain detailed information about their risk and security threat management plan. Automating the management security threats from early threat assessments all the way through the device lifecycle is important as a way to organize and retain the details, record the threat analysis, drive security test and fix priority, and end-to-end traceability. In addition, as security requirements start to become part of various industrial standards, threat management tools become increasingly essential. An example of this would be RSA Archer Threat Management.

Application Lifecycle Management Tools

Application Lifecycle Management (ALM) tools cover a wide variety of tools that are aimed at improving software development productivity and quality while managing and limiting schedule and budget risk. Requirements and change management, modeling and analysis tools, test management, product portfolio management and more. These tools are important for productivity, quality, compliance and security. Although not specific to security, incorporating security requirement management, secure design and security testing into the ALM scope is critical. In other words, the tools manage the security design lifecycle as they do the mainstream software development lifecycle. Examples of the ALM tools would be the IBM Rational suite of tools.

Summary

Tools are key to developer productivity and critical in improving security in embedded devices. In this age of increased scrutiny of security (and certainly other quality characteristics) and increased pressure for more features and tight schedules and budgets, the need for tools is greater now then ever. In this post I’ve mapped the tools to the embedded device development lifecycle and to the 5+1 step security improvement framework and what role each class of tool plays in the security improvement framework. I’d like to hear if there are other classes I’ve missed in the list and what tools you’ve found to be the most useful for improving your product security.

 

For additional information from Wind River, visit us on Facebook.

Systematically Exposing OS Kernel Races – An Interview with Ben Blum

By Jakob Engblom

Full-system simulators like Simics provide unparalleled insight into what is going on in a target system. Indeed, better insight is one of the main features of simulation that we get regardless of what we simulate and how. In addition, if we want to, we can also exert control over the target system to make it take different execution paths than it otherwise would. Earlier this year, Ben Blum at Carnegie-Mellon University  CMU presented a Master’s thesis that provides a very good example of just what can be achieved by combing the insight and control of a simulator with intelligence and domain knowledge. The system is called Landslide, and it is used to expose race conditions inside of operating-system kernels.

Landslide systematically explores the possible execution paths of the kernel in order to provoke latent bugs that might only happen very rarely in actual use of the operating system – but as we all know, such glitches are the ones that tend to be found by customers in critical situations and force engineering to spend months in reproduction attempts.

For this blog post, I interviewed the creator of Landslide, Ben Blum. 

Jakob Engblom: Please introduce yourself!

Ben Blum: I'm Ben Blum, a graduate student in the Computer Science Department at Carnegie Mellon (CMU) , advised by Garth Gibson. I spent last year doing this work as part of the Fifth Year Master's program in the Computer Science Department at CMU. Now I am staying on for several more years for a Ph.D. 

JE: What was the topic of your thesis?

BB: Systematic testing (or sometimes "exploratory testing" or "systematic exploration") is the idea of testing for race conditions in a concurrent system by forcing the system to execute as many different thread interleavings as possible.

Normally when you run a concurrent system, its threads run in an unpredictable pattern (governed by timer events or other device interrupts), and only one possible interleaving out of many is executed. And (by contrast), when you use conventional stress testing, you exercise a random set of thread interleavings, often a very small subset of the whole execution space. A systematic testing tool tries to enumerate and explore the whole state space of interleavings.

This approach is very powerful: it can find arbitrarily complicated race conditions, including TOCTTOU (Time of Check To Time of Use) bugs. Lighter-weight tools such as data race detectors or static analyses are often powerless against these, since simply adding locks around each access might satisfy such a tool but not actually solve the race.

But systematic testing is also very computationally expensive – you might be thinking "exponential explosion of possibilities", and you'd be right. A big part of the research involves figuring out how to reduce the coverage (and/or granularity) of possible interleavings in a way that still gives meaningful results. Sometimes we use sophisticated pruning algorithms; sometimes we use simple heuristics.

JE: How did you use Simics?

BB: I wrote my tool, called Landslide, as a Simics module. When Simics boots up a kernel, it also loads Landslide, which then gets to monitor and control the kernel's execution.

Being in a simulated environment gives a lot of power: Landslide sees every instruction and memory access the kernel runs, and so keeps fairly detailed internal representations of the kernel's state. There is about an order of magnitude slowdown in doing this (compared to regular Simics simulation speed), but it gets to know (for example) when each kernel thread is runnable and whether heap accesses are invalid.          

JE: And just what is Landslide and how does it work?

BB:  During the first run of a test case, Landslide identifies "decision points" - instructions during the execution at which it thinks that if the kernel had context switched to another thread, something interesting might have happened (the set of decision points defines the state space of thread interleavings). Annotations in the kernel (which I call "tell_landslide()") also help Landslide track what the kernel is doing (especially thread lifecycle events).

Then, when the test case finishes, Landslide chooses which decision point to execute differently (and chooses which thread to run instead), rewinds to that state, injects timer interrupts to force the kernel's scheduler to run that thread, and proceeds. (A pruning algorithm called Dynamic Partial Order Reduction drives the exploration - it chooses which interleavings to explore next in a way that skips over certain redundant ones.)

Simics has a really great feature that makes this possible: it supports setting bookmarks when the simulation is stopped and later doing reverse-execution back to that point. I used this to implement the "rewinding", and it turns out to be a lot faster than rebooting the kernel every time (especially in a depth-first search).

JE: Cool, so you actually make use of reverse execution to create a backtracking search through the state space of the target system. Kind of obvious once you see it, but also very clever.  Anyway, please continue.

BB: Finally, when Landslide finds a bug, it prints a "decision trace", which is a list of each thread switch that happened and a stack trace at each point. Landslide has a couple of bug-finding checks: tripped asserts, use-after-free heap accesses, deadlocks, and (heuristically) livelocks /infinite loops.

 

Which events to consider "decision points" was also a hard question. During the project, I used voluntary reschedules (such as calls to yield()) and synchronisation operations (such as calls to mutex_lock()/mutex_unlock()) as decision points. I felt this struck a good balance between fine-grained interleavings (more likely to find races) and coarse-grained interleavings (more feasible to explore the state space).

But I also wanted to harness the user's own intuition, to focus the search space more intelligently. So the user can also configure decision points of their own - they can write "tell_landslide_decide()" in the kernel's code to say "hey, put a decision point here!", and they can also use another config file to whitelist/blacklist certain modules of the kernel (maybe you don't want to waste any time exploring interleavings in the virtual memory subsystem).

 

---

Partial-Order Reduction Explained

Landslide uses an existing algorithm called Dynamic Partial Order Reduction to prune redundant subtrees out of the search space of different thread interleavings. The basic idea of the algorithm is to use a "memory independence relation", which identifies when certain state transitions of different threads have no conflicting shared memory accesses, to know when it wouldn't matter which order those transitions run in. In the picture above, the states are identical after "1" and "2", regardless of the order that these operations are done. Therefore, it is sufficient to explore only of the subtrees marked in yellow.

---

JE: That sounds like some pretty advanced Simics programming there (I would not call it scripting, it is way beyond that level of sophistication)!

BB: Thanks! Yes, Landslide is basically its own piece of software. It's about 4000 lines of code, written mostly in C.

JE: What types of kernel errors do you detect with Landslide?

BB: Well, in theory, the beauty of systematic testing is that it should be able to find any kind of race condition.

One example of a race that systematic testing can find that a data race detector couldn't is the everyday TOCTTOU: let's say the kernel validates a userspace buffer (with a lock held) then later accesses the buffer, but in the meantime another thread changed the permissions on that memory (with the same lock held), making the first thread's access fail. Because of the locking, it's not a data race, but Landslide can easily force an interleaving when the first thread drops the memory-validation lock (cf. mutex_unlock() being a good decision point, as I noted above).

Landslide itself is a little more limited than "in theory", of course. As implemented, the only source of nondeterminism it controls is the timer interrupts; so it controls thread scheduling, but not device input handling. As such, it's most useful for finding races in core or mostly-core parts of the kernel, such as the thread lifecycle implementation or the virtual memory system. Finding races in device drivers is beyond the scope of Landslide's current model (though potentially in the path of future work).

JE: Are you still working on the tool?

BB: Since I wrote my MS dissertation on it, I've put it on hold for a while. I've been doing some other concurrency-related projects in the meantime (which you could read about if you want on my website, linked above).

JE: What kinds of code have you tested Landslide on?

BB: I wrote Landslide targeting "Pebbles", which is a UNIX-like kernel architecture that students implement in six weeks in our undergrad operating systems class at CMU. Pebbles kernels have to be fully preemptible and support concurrent execution of standard thread-lifecycle events (fork, exec, exit, wait, yield, etc.). Using Pebbles as a case study was a good proving ground for potentially extending this work in the future to more mainstream kernels, such as Linux.

Students implement these kernels from the ground up (we only provide them enough starter code to boot up into an entrypoint function; none of the design or virtual memory or anything is done for them), so each kernel ends up with slightly different design and structure. Landslide had to be flexible enough to be able to attach to and control any of these kernels.

The real test was meeting with some of the students towards the end of the project to get them to try out Landslide, to see if it works "in the wild". Sometimes it was a struggle - the average time spent doing instrumentation was 100 minutes - but in the end, all four (out of five total) groups that completed the prerequisite instrumentation were able to find bugs in their kernels with Landslide.

JE: That is a very elegant twist to the project, I think. You both get to test your tool on real code that you know nothing about, and you teach the students that there are tools that can do almost magic things to help them check their code for errors.

JE: Do you have any fun examples from the work of bugs found?

BB: Sure. My favorite story is of one of the project's defining moments, a time when I just stopped in my tracks and thought "huh. I have made something smarter than me."

I had written a new unit test case, called double_wait, in which two threads in a parent process attempt to wait() on a single child process. I was testing it out on my own kernel (the one I wrote when I was an OS student), and I expected the search to complete with no bugs, each time having one parent thread succeed and the other return failure. Instead, after a bit of searching, Landslide made my kernel trip an assert in its condition variable linked-list logic.

This was a bug nobody ever knew about before - I'd written it three years before and didn't find it during stress-testing; and the TA who manually graded my kernel (by looking over it with a red pen) also overlooked it.

JE: That just goes to show how difficult reasoning about concurrency is for a human being.

JE: As you know, I previously interviewed the creator of SimTester. At a high level, these two tools built on Simics would seem to be similar, but I think that they are actually quite distinct. Could you expand a bit on that?

BB: Imagine my surprise when the SimTester interview came out just when I was writing my thesis's related work section. "Whoa, wait, another tool that runs in Simics and identifies key decision points and injects interrupts?"

So our projects are quite similar in those regards, but at a higher level my strategy is somewhat different from theirs. SimTester focuses on races involving device interrupt handling code, whereas Landslide is geared towards non-driver inter-thread races. Additionally, SimTester’s testing model involves forcing only one interrupt per test run, which is a lighter-weight approach than systematic exploration.

JE: Thank you for your time, this has been really interesting. Where can you go to find more information about Landslide?

BB: The thesis can be found at http://www.pdl.cmu.edu/PDL-FTP/associated/CMU-CS-12-118_abs.shtml (and the slides from the MSc defense at http://bblum.net/landslide-defence.pdf).

 

For additional information from Wind River, visit us on Facebook.

 

Analyzing Manycore Scaling with Simics

By Jakob Engblom

In my previous blog post on multicore scaling investigations with Simics, I tested a simple parallel program on a variety of machines. The scaling obtained was not particularly impressive, especially not on a 60-core target machine. In this post, we will use the Simics timeline view to look a bit closer at what is going on inside the target machines. In particular, with respect to operating system scheduling of the target threads. 

Before we look at the runs that indicated a lack of scaling, we should look at a well-behaved case to make sure we have something to compare to. For this, I brought up the 5-core heavy load experiment again, and reran it. Some things in the target setup had changed compared to the last blog post, so the scaling of the length 100 line is a bit different (once again showing the sensitivity of this program to noise and initial conditions just like it would be on physical hardware). If we look at the behavior for a nicely scaling line and compare it to the timeline view plotting the active threads, we can see that nice scaling does indeed correspond to good parallelism.

In this plot, each processor core in the target has its own color, and we see which threads run when on which core. In the picture, we see the cases with two to five worker threads. For two and three threads, we have each thread using a single processor core for the duration of the program. For four threads, where the scaling is a bit less ideal, we can see that two threads share a single processor. Finally, for five threads, we can see that we use four target cores on average across the run, and that the OS decides to have two threads share a core. Thus, we can conclude that scaling in the overall throughput graph does indeed correspond to parallel execution (no great surprise).

Next, I looked at the behavior on the 60-core target for the threads counts where scaling was essentially flat. Here, we have a rather different picture from the above. At six worker threads, we see a scheduling that only makes use of two cores, in a fairly erratic manner. It looks quite impressive, but it is not what you want from a scalable program.

Things get even more interesting as we go and look at many cores. When we use 19 worker threads, we see a regular pattern develop in the execution:

This was quite surprising. Note how each thread gets to run in order, and how sometimes we get two threads running in parallel and sometimes just a single one. It appears that the handling of the shared lock on the work queue is mostly FIFO, where a thread gets a unit of work and then goes to the end of the queue. This gives rise to the regular pattern seen, as each thread gets to run in turn (with some exceptions, indicating that the system does suffer from a little noise). Clearly, we are not getting anywhere near the theoretical parallelism that this problem offers.

All this indicates that the communication between threads needs to be fixed in order to increase performance. This is completely expected – as we expand the available hardware parallelism, software needs to be rewritten to minimize communication between threads and maximize independent execution.

If we plot the behavior of our program as a speedup over the case with one worker thread, we can see that it actually does not get worse as we add threads, it just plateaus at a speedup between 3 and 4. Thus, this program in its current form would not benefit from a platform that is any wider than quadcore.

So what does this give us?

We have determined that the program in its current incarnation, on a Linux OS, does not scale beyond four worker threads with any kind of benefit. Thus, if we want to run this program on a wider target machine (to either run bigger workloads or use more slower processors in order to save power), we need to first re-architect the software. Throwing hardware at the problem will have no positive effect.

We did this by exploiting the configurability of a virtual platform to change the number of cores, and the insight of the virtual platform to gather statistics and information about how the program executes without changing its behavior.

 

For additional information from Wind River, visit us on Facebook.