Using Conditional Complexity to Test Embedded Software

One of the areas of embedded software development that engineers seem to struggle with is testing.  Engineers often get excited about the design and implementation phases but when it comes to proving that the system works, efforts and or interest really start to wane.  This is completely understandable considering the time and effort that can be required.  There are many different ways to test an embedded system but they can be boiled down into two primary types of testing, white and black box testing.

Black box testing is usually performed by a third party or a quality assurance group who has an understanding of the external system behavioral requirements but lacks an in depth understanding of the internal structure or operation of the code.  An embedded software engineer on the other hand is much more likely to perform white box testing since they understand the structure and implementation of the software.  In this type of testing, the engineer takes into account the software structure to ensure that every branch, every case and every line of code has been executed and verified through testing.

This can be quite a daunting task even for relatively small programs.  Thankfully there is a simple way to understand and generate the number of test cases required to ensure proper test coverage and that is to use conditional complexity, also known as cyclomatic complexity (which is a great term to use in a conversation if you want to see people’s eyes glaze over).  Traditionally, conditional complexity metric testing is recommended during the implementation phase to ensure code quality.  The idea is that every function in the program is analyzed and provides a resultant complexity value.  The higher the value, the more complex the function is which results in higher risk for bugs, difficulties in testing and during maintenance.  Typical ranges can be found in Figure 1 below.

Figure 1 Figure 1 – Conditional Complexity Risk

What is really interesting about this measurement is that it directly measures the number of linearly independent paths through the function!  The complexity value provides an upper bound for the number of test cases needed for complete branch coverage!  This means that by performing this simple metric check on the source code will not only help to ensure that code is kept simple but also can be used to check that enough test cases have been defined for branch coverage tests!

The question that now comes to mind is how can we use this complexity value to create test cases?  The answer is in how the conditional complexity is calculated in the first place.  There are two ways to go about it.  The first is to simply add up the number of ifs, the number of loops and add one.  The second is to generate a control flow graph, identify the number of edges, nodes and connected components and then subtract the number of nodes from the edges and then add the connected components.  Since this is much more complex than simply looking at the source code, the first method is much easier and more likely to be done during the development cycle.  To demonstrate this, take a look at the function that is listed in Figure 2.

Figure 2

Figure 2 – Example Function Listing

This is a simple PWM initialization function that accepts a pointer to a configuration table and loops through the configuration table and sets the PWM registers accordingly.  It contains a single for loop and two if statements.  One would expect the complexity metric to be 1+1+2=4.  This can be easily verified by using an automated testing tool that reports the result as seen in Figure 3.  The developer of this function would now know that there are four test cases needed in order to properly test all of the branches.

Figure 3

Figure 3 – Conditional Complexity Analysis

The first, and most obvious test case would be to test the for loop.  Since the configuration will modify the registers for each of the PWM modules, monitoring each of the registers for change will show that indeed the for loop is being executed.  Next, a test case can be setup for the PWM enable if case.  This test case can simply be to verify that any PWM channel that was configured to be enabled is in fact enabled.  The final two test cases would be created to verify that the interrupt enable and interrupt disable work as expected.  In all of these cases this low level of test cases would require verifying that the corresponding registers in the module are set appropriately.

There are many different types and ways of performing testing on a test base and using conditional complexity is just one simple example of how testing can be performed.  Testing often requires more than just simple branch testing but requires testing along multiple layers of the implementation and system behavior requirements.  In any case, creating tests from code metrics that are used during the development cycle is at a minimum a good place start.

Share >

2 thoughts on “Using Conditional Complexity to Test Embedded Software

    • You can get these types out of reports from static analyzers. The one that I have been using for years is from Msquared Technologies called RSM. I hope that helps!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.