Auditing C code

[CptDondo]

I'm working with some legacy C code. Apparently the author didn't know
or care about the difference between int, int16_t, unsigned int, and so
on. He does a lot of bitwise |, &, etc on signed int, without regard to
the size of int and sign flipping. The result is that the code produces
valid results most of the time, and garbage the rest of the time.

I've already lost a few days to auditing the code by hand. Is there
some way to audit the code for a) consistency between passed parameters,
to make sure that all passed parameters are of the same type, and b)
something to warn me if I am doing bitwise |, &, >>, etc on signed ints?

 

[jacob navia]

I'm working with some legacy C code. Apparently the author didn't know
or care about the difference between int, int16_t, unsigned int, and so
on. He does a lot of bitwise |, &, etc on signed int, without regard to
the size of int and sign flipping. The result is that the code produces
valid results most of the time, and garbage the rest of the time.

I've already lost a few days to auditing the code by hand. Is there
some way to audit the code for a) consistency between passed parameters,
to make sure that all passed parameters are of the same type,

If you compile the code with a normal compiler using the
maximum warning level you SHOULD see a warning when
the type of the passed parameter differs from the
expected type.


and b)

something to warn me if I am doing bitwise |, &, >>, etc on signed ints?

This will be more difficult since those operations are
well defined for integers. Can you present a specific
case where a problem appears with those operations?
Are you 100% sure that the observed problems come from
those operations?

jacob

 

[CptDondo]

If you compile the code with a normal compiler using the
maximum warning level you SHOULD see a warning when
the type of the passed parameter differs from the
expected type.

OK, thanks. I'll follow up....

and b)



This will be more difficult since those operations are
well defined for integers. Can you present a specific
case where a problem appears with those operations?
Are you 100% sure that the observed problems come from
those operations?

This bit of code would fail occasionally until I changed the int to
unsigned int; now I see I really need to change it uint16_t..... I am
cross-compiling so I am striving for portability across multiple platforms.

unsigned int crc(byte trame[],int n)
{
unsigned int crc,i,j,carry_flag,a;
crc=0xffff;
for (i=0;i<n;i++)
{
crc=crc^trame;
for (j=0;j<8;j++)
{
a=crc;
carry_flag=a&0x0001;
crc=crc>>1;
if (carry_flag==1)
crc=crc^0xa001;
}
}
trame[n+1]=crc>>8;
trame[n]=crc&255;
return crc;
}

 

[jacob navia]

If you compile the code with a normal compiler using the
maximum warning level you SHOULD see a warning when
the type of the passed parameter differs from the
expected type.

OK, thanks. I'll follow up....

and b)




This will be more difficult since those operations are
well defined for integers. Can you present a specific
case where a problem appears with those operations?
Are you 100% sure that the observed problems come from
those operations?

This bit of code would fail occasionally until I changed the int to
unsigned int; now I see I really need to change it uint16_t..... I am
cross-compiling so I am striving for portability across multiple platforms.

unsigned int crc(byte trame[],int n)
{
unsigned int crc,i,j,carry_flag,a;
crc=0xffff;
for (i=0;i<n;i++)
{
crc=crc^trame;
for (j=0;j<8;j++)
{
a=crc;
carry_flag=a&0x0001;
crc=crc>>1;
if (carry_flag==1)
crc=crc^0xa001;
}
}
trame[n+1]=crc>>8;
trame[n]=crc&255;
return crc;
}

This code is exactly the code of the JBUS protocol CRC. In the
original source code we have an UNSIGNED int specified.
Using the published source code for this protocol CRC
in:
http://www.cppfrance.com/codes/CRC-16_31553.aspx
The 0xa001 constant is the polynomial used (x^15+x^13+x^0 or
1010000000000001

 

[Jack Klein]

I'm working with some legacy C code. Apparently the author didn't know
or care about the difference between int, int16_t, unsigned int, and so
on. He does a lot of bitwise |, &, etc on signed int, without regard to
the size of int and sign flipping. The result is that the code produces
valid results most of the time, and garbage the rest of the time.

I've already lost a few days to auditing the code by hand. Is there
some way to audit the code for a) consistency between passed parameters,
to make sure that all passed parameters are of the same type, and b)
something to warn me if I am doing bitwise |, &, >>, etc on signed ints?

PC-Lint, http://www.gimpel.com, should catch most of this.

 

[Clark S. Cox III]

If you compile the code with a normal compiler using the
maximum warning level you SHOULD see a warning when
the type of the passed parameter differs from the
expected type.


and b)

This will be more difficult since those operations are
well defined for integers.

You sure about that? From 6.5.2:

Some operators (the unary operator ~, and the binary operators <<, >>,
&, ^, and|, collectively described as bitwise operators) are required to
have operands that have integer type. These operators return values that
depend on the internal representations of integers, and have
implementation-defined and undefined aspects for signed types.

 

[websnarf]

If you compile the code with a normal compiler using the
maximum warning level you SHOULD see a warning when
the type of the passed parameter differs from the
expected type.

It depends on the compiler. In fact what I recommend is that you use
the maximum warning level on *multiple* compilers plus lint (PC-Lint
which Jack Klein suggests is good) and even SPlint. Without automated
assistance this can be seriously difficult. I find that satisfying the
maximum warning levels on WATCOM C/C++, gcc, MSVC and Intel C++
simultaneously puts me in a pretty good standing.

Its kind of interesting what each compiler misses that the others
don't. WATCOM is the only compiler I know of that can flip the sign of
char, for example. WATCOM also tries to manifest enum's as char's
sometimes which can sometimes have implications on how enums are cast
and passed around. Microsoft's latest compiler is extremely anal about
potential integer type value truncation. Intel finds some really
obscure problems which include the non-abelian nature of the C language
versus ordinary mathematics (because of the order of side-effects).
gcc balks on a lot of inadvertent "windows-isms", and differs in its
header files for POSIX support from most other C compilers.

 

[sjdevnull]

Its kind of interesting what each compiler misses that the others
don't. WATCOM is the only compiler I know of that can flip the sign of
char, for example.

Do you mean making "char" either signed or unsigned at your request?
gcc offers "-fsigned-char" and "-funsigned-char"

Thanks for the splint recommendation, looks handy.

 

[Robert Latest]

On Tue, 19 Sep 2006 11:06:48 -0700,

for (i=0;i<n;i++)

On highest warning level, gcc would tell you about signed-unsigned
comparison here.

robert

 

[Chris Torek]

This bit of code would fail occasionally until I changed the int to
unsigned int; now I see I really need to change it uint16_t..... I am
cross-compiling so I am striving for portability across multiple platforms.

Except for the use of "int n" (which may or may not be a problem
depending on the range supplied for n), and the question of whether
"byte" is a name for an unsigned type -- if it is "unsigned char"
things should be fine -- this code is itself fine:

unsigned int crc(byte trame[],int n)
{
unsigned int crc,i,j,carry_flag,a;
crc=0xffff;

This line might be better-written "crc = 0xffffU;", but it should
assign 65535U to crc in every case. (UINT_MAX is required to be
at least 65535U, although it may be greater.)

for (i=0;i<n;i++)

As someone else pointed out, comparing "unsigned int i" with
(signed) int n is not always wise. Fortunately, in this case,
the one "unsigned" will override so that the overall comparison
will be the same as:

i < (unsigned int)n

which will "do the right thing" in most cases. It would be better
to give both i and n the size_t type, though.

{
crc=crc^trame;

As long as both crc and trame are bounded by the range 0..65535,
the result in "crc" at this point will also be in that range. The
initial value of "crc" is 65535 and hence is so bounded; we need
only verify that the rest of the loop maintains this invariant.

for (j=0;j<8;j++)
{
a=crc;
carry_flag=a&0x0001;

Here "a" will be in the same range that "crc" had earlier, and
carry_flag will be either 0 or 1 depending on the least significant
bit of "a" (which is the same as the LSbit of "crc").

crc=crc>>1;

At this point, crc should be in the range [0..32767]. (The LSbit
has been discarded and the remaining value divided by 2.)

if (carry_flag==1)
crc=crc^0xa001;
}

Since "carry_flag" is either 0 or 1 (depending on the low bit of
"crc" before shifting, as saved in "a", which is not actually
needed -- carry_flag could be set based on "crc" instead of "a"),
the test for "== 1" is unnecessary but harmless. Since crc was
in the range 0..32767 [0..0x7fff], the result of the xor is in
the range [0..0xffff] or [0..65535].

Hence, the loop maintains the invariant that crc is in [0..65535],
and a type that holds at least that range (like "unsigned int")
always suffices.

}
trame[n+1]=crc>>8;
trame[n]=crc&255;
return crc;
}

This suggests that "byte" is a typedef-name for "unsigned char",
so my earlier guess that trame is in the range [0..255] seems
reasonable.

It seems a bit odd to store the crc of the input data in the input
data, as well as returning it. The routine would be more generally
useful if the crc were not stored anywhere but just returned.
Alternatively, the output region could be given as a parameter.
(For source compatibility one might then:

#define COMPAT_CRC(arr, size) new_crc(arr, size, (arr) + (size))

and change calls to crc(x,y) to COMPAT_CRC(x,y), verifying that
the parameters are OK when macro-ized like this.)

(The routine can be sped up enormously by performing the CRC
calculations one 8-bit-unit at a time, with a 256-entry table, but
that is a separate issue. This also makes the code somewhat harder
to eyeball as "obviously correct" -- here, only the magic xor value
need be inspected to make sure it has the right powers of two in
it.)