malloc testing

malloc testing

[JIghtuse]

So, I am still working on testing malloc() of musl. My coding breaks by 
some increase of studing in university, but I have to say I want to 
participate. Is it real to join Summer of Security? After finished musl 
tests I want to try blists development also.

-- 
Sincerely yours, JIghtuse.

Re: malloc testing

[Solar Designer]

JIghtuse -

On Wed, Apr 27, 2011 at 10:24:15AM +0700, JIghtuse wrote:
> So, I am still working on testing malloc() of musl. My coding breaks by 
> some increase of studing in university, but I have to say I want to 
> participate. Is it real to join Summer of Security?

Sure.  Thanks for the status update.

> After finished musl tests

Luka is the primary person to work on these, but you're welcome to stay
involved as well - e.g., you may help test Luka's tests against more
libc's, report problems in here (both those of the tests and of the
libc's), and improve the tests.

> I want to try blists development also.

Sounds good.  This is off-topic for the musl list, though, so please
e-mail me off-list for it when you're ready.

Thanks,

Alexander

P.S. Somehow you started a new thread instead of posting to the existing
thread with the same Subject.  You should have used "reply" on a message
in the proper thread.

Re: malloc testing

[JIghtuse]

[-- Attachment #1: Type: text/plain, Size: 3870 bytes --]

On Fri, Apr 29, 2011 at 12:42 PM, Solar Designer <solar@openwall.com> wrote:

> JIghtuse -
>
> On Wed, Apr 27, 2011 at 10:24:15AM +0700, JIghtuse wrote:
> > So, I am still working on testing malloc() of musl. My coding breaks by
> > some increase of studing in university, but I have to say I want to
> > participate. Is it real to join Summer of Security?
>
> Sure.  Thanks for the status update.
>
> > After finished musl tests
>
> Luka is the primary person to work on these, but you're welcome to stay
> involved as well - e.g., you may help test Luka's tests against more
> libc's, report problems in here (both those of the tests and of the
> libc's), and improve the tests.
>
> > I want to try blists development also.
>
> Sounds good.  This is off-topic for the musl list, though, so please
> e-mail me off-list for it when you're ready.
>
> Thanks,
>
> Alexander
>
> P.S. Somehow you started a new thread instead of posting to the existing
> thread with the same Subject.  You should have used "reply" on a message
> in the proper thread.
>

So, my program creates array of structures of memory blocks and works with
it.
Source code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#define M 100000000
#define REPEATS 10

struct block {
    unsigned int* ptr;
    unsigned int size;
} blocks[M / 100];

int by_size(const void *, const void *);
int by_address(const void *, const void *);

int main(int argc, char *argv[])
{
    unsigned int i = 0, j, counter;
    unsigned int seed;
    unsigned int amount = 0;
    unsigned int size;

    if (argc > 1) {
        seed = atoi(argv[1]);
    } else {
        printf("Type seed: ");
        scanf("%u", &seed);
    }

    bzero(blocks, sizeof(blocks[0]) * (M / 100));

    for (counter = 0; counter < REPEATS; counter++) {
        while (amount < M) {
            size = rand() % (M / 100);
            if (size > 100000) {
                size |= 0xff0;
            }

            blocks[i].size = size;
            blocks[i].ptr = malloc(sizeof(int) * size);
            if (blocks[i].ptr == NULL) {
                printf("\nmalloc() error!\n");
                exit(EXIT_FAILURE);
            }
            amount += blocks[i].size;
            i++;
        }

        if (counter != REPEATS - 1) {
            qsort(blocks, i, sizeof(struct block), by_size);
            for (j = i / 4; j < i; j++) {
                amount -= blocks[j].size;
                free(blocks[j].ptr);
            }
            bzero((void *)(blocks + i / 4), sizeof(blocks[0]) * ((i / 4) * 3
+ 3));
            i /= 4;
        } else {
            qsort(blocks, i, sizeof(struct block), by_address);
        }
    }

    printf("%5s %12s %8s\n", "No.", "Address", "Size");
    for (j = 0; j < i - 1; j++) {
        printf("%5u %12u %8u\n", j, (unsigned int)blocks[j].ptr,
blocks[j].size);
        if (blocks[j].ptr + blocks[j].size >= blocks[j + 1].ptr) {
            printf("\nOverlaped!\n");
            exit(EXIT_SUCCESS);
        }
    }
    printf("%5u %12u %8u\n", j, (unsigned int)blocks[j].ptr,
blocks[j].size);
    exit (EXIT_SUCCESS);
}

int by_size(const void * a, const void * b)
{
  struct block *ia = (struct block *)a;
  struct block *ib = (struct block *)b;
  return (int)(ia->size - ib->size);
}

int by_address(const void * a, const void * b)
{
    struct block *ia = (struct block *)a;
    struct block *ib = (struct block *)b;
    return (void *)ia->ptr > (void *)ib->ptr;
}




Sample output:
  No.      Address     Size
    0    167530504     5211
    1    167551352    21530
    2    167637480    18456
    3    167711312    28624
<...>
  266   3071238152    36159
  267   3071651848    33333
  268   3073114120   204799
  269   3073937416   794617


I tried to plot this data with gnuplot, but it'll require parting data at
two or more parts because of big address range.

[-- Attachment #2: Type: text/html, Size: 4845 bytes --]

Re: malloc testing

[Rich Felker]

On Thu, Apr 21, 2011 at 09:11:37AM +0700, JIghtuse wrote:
> On 20.04.2011 11:34, Rich Felker wrote:
> >On Sun, Apr 10, 2011 at 10:59:08PM +0700, JIghtuse wrote:
> >>I have some questions about my task. I've written a program to test
> >>malloc() function of musl. But..
> >Any updates? Are you still interested in working on this?
> >
> >Ricih
> Yes, I interested in. Just some studying.
> Can you give some algorithms? I not found its on the Net. How chunks
> should be flipped?

Try something like:

1. Allocate blocks in random sizes until the total size exceeds the
configured limit M. For each block allocated, keep track of its
address and size.

2. Sort the allocated block records by size (with the qsort function).

3. Free all but the first 25% in the sorted list (i.e. all but the
smallest ones). Leave the ones you don't free in your list.

Repeat this procedure a few times, and the last time through, don't
free anything. Now sort the records by address instead of by size, and
check that they don't overlap.

For large allocations (>100k) I would bias the random numbers to be
just below a multiple of 4096. Something like:

if (size > 100000) size |= 0xff0;

This puts them in the "red zone" where bugs could (and in the past
did) lead to under-allocation.

Rich

Re: malloc testing

[JIghtuse]

On 20.04.2011 11:34, Rich Felker wrote:
> On Sun, Apr 10, 2011 at 10:59:08PM +0700, JIghtuse wrote:
>    
>> I have some questions about my task. I've written a program to test
>> malloc() function of musl. But..
>>      
> Any updates? Are you still interested in working on this?
>
> Ricih
>    
Yes, I interested in. Just some studying.
Can you give some algorithms? I not found its on the Net. How chunks 
should be flipped?


-- 
Sincerely yours, JIghtuse.