[Nauty] Undefined behavior in nauty (Going over bounds)

[Brendan McKay]

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