[Nauty] Undefined behavior in nauty (Going over bounds)
Brendan McKay
Brendan.McKay at anu.edu.au
Mon Nov 16 00:16:48 AEDT 2020
Not so fast.
There is a structural type declared like this:
typedef struct permnodestruct
{
struct permnodestruct *prev,*next; /* prev&next in circular list */
unsigned long refcount; /* number of references */
int nalloc; /* size of p[] in ints,
<= 0 for a perm marker */
int mark; /* a mark, 0 unless changed */
int p[2]; /* actual vector, extended to
nalloc enties */
} permnode;
Variables of this type are allocated in newpermnode() thus:
malloc(sizeof(permnode)+(n-2)*sizeof(int));
This allocates enough space for the member p to hold n ints. (The case
n=1 doesn't occur, but I don't remember why I used [2] instead of [1].)
This is a traditional way of having a dynamically-sized array in a
structure.
But here we see an awkward portability problem. In the C99 standard,
the correct way to achieve this is to use an "incomplete array", like this:
int p[];
However, that hasn't been allowed for long. The ANSI C standard and
ISO C (C89/90) explicitly forbade structure members of incomplete type.
I don't know about C95 or post-C99 standards.
See here for some discussion:
https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html
I'm not going to require nauty users to have C99-compatible compilers,
and I know as a fact that many don't. I try conservatively to not use
features newer than ANSI C unless necessary. Perhaps I should add this
issue to the configuration script. On the other hand, I can't see anything
in the C99 standard to forbid my usage and the sanitizers in gcc+clang
do not define what is legal.
Brendan.
On 15/11/20 9:20 pm, Mathieu Dutour wrote:
> Dear all,
>
> I found a memory problem in nauty. That is the array "int p[2]" in permnode
> is accessed above the bound of 2.
>
> The way to detect it is by compiling with
> clang -fsanitize=thread -fsanitize=undefined -fsanitize=bool
> -fsanitize=bounds -fsanitize=bounds -fsanitize=return -fsanitize=null
>
> The compiling nautyex9 with "make nautyex9"
>
> And then it goes:
> (base) ➜ nauty27r1 ./nautyex9
>
> enter n : 13
> schreier.c:687:45: runtime error: index 12 out of bounds for type 'int [2]'
> SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior schreier.c:687:45 in
> schreier.c:844:56: runtime error: index 3 out of bounds for type 'int [2]'
> SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior schreier.c:844:56 in
> Automorphism group size = 78
>
> Best wishes,
>
> Mathieu
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> http://mailman.anu.edu.au/mailman/listinfo/nauty
More information about the Nauty
mailing list