Archive for February, 2012

Why you really shouldn’t steal source code

Saturday, February 11th, 2012 Nigel Jones

As an embedded systems consultant, I spend a substantial part of my work time working on your typical embedded systems projects. However I also spend a significant amount of time working as an expert witness in legal proceedings. While the expert witness work is quite varied, one of the things I have noticed in the last few months is an increase in the number of cases related to source code theft. Typically these cases involve the plaintiff claiming that the defendant has stolen their source code and is using it in a competing product. These claims are often plausible, because as we all know, it’s trivial to walk out of a company with Gigabytes of information in your pocket. Even in companies with strong security measures, it’s normally the case that the engineers are smart enough to work out how to bypass the security systems, so the ‘there’s no way I could have got the code out of there’ defense isn’t usually very plausible.

Thus given how easy it is to steal source code, why shouldn’t you do it? Well let’s start with the obvious – it’s wrong. if you don’t understand this, go and have a chat with your mother – I’m sure she’ll spell it out for you. Notwithstanding the morality (and legality) of the issue, here’s another reason why you shouldn’t do it – there’s a great chance you’ll be found out. If that happens, you can find yourself in serious legal jeopardy.

So just how easy is it to show that someone has stolen your code?

Typically the first step is for the (future) plaintiff to have their suspicions aroused. If half the engineering department leaves and starts up a company with a competing product, then it’s hardly surprising that your ex-employer will be suspicious. Of course suspicions aren’t grounds for a lawsuit. The plaintiff needs at least some evidence of your malfeasance. Now sometimes this can be done purely by the functionality / look and feel of a product. However in other cases it’s necessary for the plaintiff to get at your code’s binary image. You can make this very hard (and hence expensive) to do. However for your typical microprocessor, this step is surprisingly easy. Indeed there are any number of organizations around the world that are quite adept at extracting binary images from processors.  So what you may ask? I took the code, moved stuff around, used a different compiler and compiled it for a different processor, so good luck with showing that I used your code. Well the trouble with this, is that using tools such as Ida-Pro, it’s easy to count the number of functions in the code, and the arguments they take. These metrics are a remarkably good signature. [BTW, there are other metrics as well, but I really don’t want to give the whole game away]. Thus if the original code base and the stolen code base have a very similar function call signature, then there’s an excellent chance that the plaintiffs have enough evidence to file a lawsuit.

It’s at this point that you are really in trouble. As part of the lawsuit, the plaintiffs are allowed to engage in discovery.  In a case like this, it means quite simply that the court will require you to turn your source code over to an expert that has been retained by the plaintiffs (i.e. someone like yours truly). At this point, I can use any number of tools that are available for comparing code bases. Some of the tools are designed expressly for litigation purposes, while others are just some of the standard tools we use as part of our everyday work. Anyway, the point is this: these tools are really good at finding all sorts of obfuscations, including things such as:

  • Renaming variables, constants functions etc.
  • Changing function parameter orders
  • Replacing comments
  • Adding / deleting white space
  • Splitting / merging files

In many cases, they can even detect the plagiarism (theft) even if you have switched languages. In other words, if you have indeed stolen the source code, then the chances of  it not being conclusively proven at this stage are pretty slim. In short, life is about to get very unpleasant.

Having said the above, I like to think that the readers of this blog are not the type that would engage in source code theft. However I suspect that some of you have been tempted to go into business competing against your current employer. If this describes you, then what should you do to ensure that you don’t get hit with a lawsuit a year or two after starting your own business?  Well clearly the best bet is not to go into a competing business. However if you must do this, then get some legal advice (please don’t rely on what is written here – I’m just an engineer!) before you start. You will probably be advised to do a ‘clean room’ design, which in a nutshell will require you to demonstrate that the code in your competing product was designed from scratch, using nothing from your former employer. Be advised that even in these cases, if you adopt the same algorithms, then you may still be in trouble.

 

 

 

The absolute truth about abs()

Wednesday, February 1st, 2012 Nigel Jones

One of the more depressing things about the C language is how often the results of various operations are undefined. A prime example of this is the abs() function that I’m fairly sure is liberally dispersed throughout your code (it is through mine). The undefined operation of the abs() function comes about if you have the temerity to use a compiler that represents negative numbers using 2’s complement notation. In this case, the most negative representable number is always numerically larger than the most positive representable number. In plain English, for 16 bit integers, the range is -32768 … + 32767. Thus if you pass -32768 to the abs() function, the result is undefined.

The problem of course in an embedded system is that undefined operations are just dangerous, so surely an embedded compiler will do something sensible, like return +32767 if you pass -32768 to abs? To test this hypothesis I whipped up the following code for my favourite 8 bit compiler (IAR’s AVR compiler).

#include <stdlib.h>
#include <inttypes.h>
#include <stdio.h>

void main(void)
{
    int16_t i;
    int16_t absi;

    i = INT16_MIN + 1;        /* Set i to one more than the most negative number */
    absi = abs(i);

    printf("Argument = %" PRId16 ". Absolute value of argument = %" PRId16, i, absi);

    i--;                    /* i should now equal INT16_MIN */
    absi = abs(i);
    printf("\nArgument = %" PRId16 ". Absolute value of argument = %" PRId16, i, absi);
}

If you don’t understand the printf strings, see this article. Here’s the output of this code:

Argument = -32767. Absolute value of argument = 32767
Argument = -32768. Absolute value of argument = -32768

Clearly abs(-32768) = -32768 is not a very useful result! If I look in <stdlib.h> I find that abs() is implemented as

  int abs(int i)
  {      /* compute absolute value of int argument */
    return (i < 0 ? -i : i);
  }

Clearly no check is being made on the bounds of the parameter, and so the result that we get depends upon how the negation of the argument is performed. Thus this leads me to my first suggestion, namely write your own abs function. I’ll call this function sabs() for safe abs(). The first pass implementation for sabs() looks like this (note you’ll have to include <limits.h> to get INT_MIN and INT_MAX):

int sabs(int i)
{
    int res;

    if (INT_MIN == i)
    {
        res = INT_MAX;
    }
    else
    {
        res = i < 0 ? -i : i;
    }

    return res;
}

Here’s the output:

Argument = -32767. Absolute value of argument = 32767
Argument = -32768. Absolute value of argument = 32767

I think for most embedded systems this is a better result. However what happens if you use a smaller integer than the native integer size (e.g. a 16 bit integer on a 32 bit system, or an 8 bit integer on a 16 bit system?). To test this question, I modified the code thus:

#include <stdlib.h>
#include <limits.h>
#include <inttypes.h>
#include <stdio.h>

int sabs(int i);

void main(void)
{
    int8_t i;
    int8_t absi;

    i = INT8_MIN + 1;        /* Set i to one more than the most negative number */
    absi = sabs(i);

    printf("Argument = %" PRId8 ". Absolute value of argument = %" PRId8, i, absi);

    i--;                    /* i should now equal INT8_MIN */
    absi = sabs(i);
    printf("\nArgument = %" PRId8 ". Absolute value of argument = %" PRId8, i, absi);
}

int sabs(int i)
{
    int res;

    if (INT_MIN == i)
    {
        res = INT_MAX;
    }
    else
    {
        res = i < 0 ? -i : i;
    }

    return res;
}

So in this case, the native integer size is 16 bits and I’m passing an 8 bit integer. Here’s the output:

Argument = -127. Absolute value of argument = 127
Argument = -128. Absolute value of argument = -128

Clearly, I still haven’t solved the problem, as I’d really like abs(-128) to be 127 when using 8 bit integers.  I suspect that I could come up with some fancy expression that handles all integer types.  However I’m a great believer in simple code, and so  my recommendation is that you write sabs() functions for all your integer types. Thus:

/* Safe 8 bit absolute function */
int8_t sabs8(int8_t i)
{
    int8_t res;

    if (INT8_MIN == i)
    {
        res = INT8_MAX;
    }
    else
    {
        res = i < 0 ? -i : i;
    }

    return res;
}
/* Safe 16 bit absolute function */
int16_t sabs16(int16_t i)
{
    int16_t res;

    if (INT16_MIN == i)
    {
        res = INT16_MAX;
    }
    else
    {
        res = i < 0 ? -i : i;
    }

    return res;
}
/* Safe 32 bit absolute function */
int32_t sabs32(int32_t i)
{
    int32_t res;

    if (INT32_MIN == i)
    {
        res = INT32_MAX;
    }
    else
    {
        res = i < 0 ? -i : i;
    }

    return res;
}

 

The above approach is all well and good, but let’s face it, I’ve added a lot of overhead for a very rare condition. So this raises the question as to whether there is a better way of doing things? Well in many cases we use the abs() function to check for some limit. For example

    if (abs(i) > SOME_LIMIT)
    {
        printf("\nLimit exceeded");
    }

In cases like these, you can use what I call a negative absolute function, aka nabs(). nabs() works with negative absolutes and so can’t overflow. To demonstrate, here’s the code:

int nabs(int i);

void main(void)
{
    int i;
    int absi;

    i = INT_MIN + 1;        /* Set i to one more than the most negative number */
    absi = nabs(i);

    printf("Argument = %d Negative absolute value of argument = %d", i, absi);

    i--;                    /* i should now equal INT_MIN */
    absi = nabs(i);
    printf("\nArgument = %d Negative absolute value of argument = %d", i, absi);

    i = INT_MAX;
    absi = nabs(i);
    printf("\nArgument = %d Negative absolute value of argument = %d", i, absi);
}

int nabs(int i)
{
    return i > 0 ? -i : i;
}

The output looks like this:

Argument = -32767 Negative absolute value of argument = -32767
Argument = -32768 Negative absolute value of argument = -32768
Argument = 32767 Negative absolute value of argument = -32767

Armed with this function, you merely flip your tests around, such that you have:

    if (nabs(i) < SOME_NEGATIVE_LIMIT)
    {
        printf("\nLimit exceeded");
    }

I’ll leave it to you to decide whether gaining the efficiency is worth it for the rather strange looking code.

As a final note, do a search for the abs() function on the Internet. You’ll find that most references don’t mention the undefined behavior of abs with INT_MIN as an argument. The notable exception is the always excellent GNU reference . It’s thus hardly surprising that most embedded systems use abs().